Transparency logs for public identity keys

## Background

We rely on a user's public [cross-signing keys](https://spec.matrix.org/v1.13/client-server-api/#cross-signing) to verify that a device in a room actually belongs to the person we think we are talking to. In an ideal world, you would confirm out-of-band with each user that the key we see really belongs to them, rather than there being a MITM attack or similar. (This is what the emoji and QR code verification processes do.)

However, it is impractical to verify every user in a large community; further, a user may need to replace their cross-signing keys (due to compromise or loss of the private keys), which at best appears as a red flag and at worst would require everyone in the community to re-verify them.

## Suggestion

One technique to help with this is a public, append-only, directory, containing all public user identity keys. Such a directory can help prove that a server is not reverting previous changes, or equivocating (telling different users different things). An individual user can inspect the history of their own keys or that of a contact; an auditor can inspect the wider history and check for anomalies.

WhatsApp have done some very interesting work in this area: see in particular their [white paper](https://www.whatsapp.com/security/WhatsApp-Key-Transparency-Whitepaper.pdf) on the topic, as well as their implementation of the directory [akd](https://github.com/facebook/akd). The [documentation](https://docs.rs/akd_core/latest/akd_core/) on the operation of the directory is particularly interesting. (In a nutshell, it is based on a [Merkle Tree](https://en.wikipedia.org/wiki/Merkle_tree), which is a binary tree where every node is labelled with the cryptographic hash of the labels of its child nodes. Inserting a new directory entry involves creating a new leaf, which updates the hashes of all the parents up to the root. Any change anywhere in the tree therefore causes a change to the root hash.)

We would need to do some thinking about how best to apply such a technique in Matrix's distributed environment. Would you have one directory per homeserver, or is it better to aggregate them somehow -- and if the latter, how does one do so securely?

Start by reading the linked Matrix cross-signing specification, WhatsApp white paper, akd documentation, and Merkle Tree overview. The issue names no repository files or tests; done would require a settled design explaining how transparency logs could work securely across Matrix's distributed homeservers.

Written by the indexing model from the issue text.