[messaging] Transparency for a key directory without publishing usernames

[Trevor Perrin]

We've discussed a centralized key directory being monitored for
correctness via a "transparency log".  There was concern this would
require publishing all usernames, but I'm wondering if that's
necessary.

Suppose that each day the key directory constructs a "Sparse Merkle
tree" [1] that maps usernames to the user's identity public key(s) for
the previous 24 hours.  The "signed tree head" (STH) is a signed hash
of the sparse Merkle tree root and the previous day's STH.

Users could gossip the latest STH by including it in their encrypted
messages to each other.  Users would request proofs from the directory
that STHs are consistent, and that identity keys are consistent with
STHs.

Monitoring could be done by requesting daily proofs for your own key,
or delegating this to a monitor.  That's less efficient than if the
log is being published - in that case the monitors just download a
small list of daily changes.  Maybe that's the fatal flaw here?

Note the "Sparse Merkle Tree" can't be replaced with any
"authenticated dictionary", since the SMT has the special property of
being able to prove a username has a unique entry in a tree.  I wonder
if there's a name for this property, and other literature about it?

Trevor

[1] http://www.links.org/files/RevocationTransparency.pdf