[MLS] Efficiency and "Ampelmann trees"

[Richard Barnes <[e-mail]>]

Hey all,

At the last IETF meeting, we had some discussion about the efficiency of
the protocol.  On the one hand, having endpoints ship around the whole tree
and keep it in memory seems like a bad bit of linearity; can't we just have
the server track that stuff, and have the clients download slices of the
tree as needed?  On the other hand, you need to make sure the server
doesn't lie, which requires some complicated hashing.  This email has some
thoughts about how complicated the hashing needs to be.

Recall that in order to do the group operations, an endpoint needs the
following parts of the tree:

- Add: Frontier == Copath of position N+1
- Update: Copath of the endpoint's own leaf
- Remove: Copath of the removed node's leaf

So we need a scheme for computing a commitment to the tree (which can go in
the GroupState/Welcome) such that it's easy to prove a copath.

You could do this with a Merkle tree over the nodes of the ratchet tree,
but it's kind of inelegant.  The commitment would obviously be the root of
the Merkle tree.  It's less clear how best to prove a copath, but it is
possible: The requester knows the indices in the tree of the copath nodes,
so in the worst case, the server could provide log(N) individual proofs for
those nodes (each of size log(N)).

In thinking about this a bit, it seems you could improve on this by
aligning the hash tree structure to the tree structure you're verifying.
Merkle trees assume there are no values at the intermediate nodes of the
tree; let's just hash them in: If an intermediate node has value V and
child hashes L and R, then set the value of the node to:

H(H(L || R) || V)

(instead of H(L || R) in the Merkle tree case). If you do that, then I
think you get copath proofs of size 2 * log(N) instead of log(N)^2.  The
attached figures (assuming they survive remailing) illustrate how this
works.  (I've been calling these "Ampelmann Trees", for their resemblance
to the famous indicators in Berlin [1])

Now, even assuming this scheme works, it isn't a total solution to the
problem.  Given that we have blanks in the tree to avoid double-joins,
we're going to need a way to handle blanks in the proof algorithms.  Pretty
sure it's still possible, but will require another layer of math.
Likewise, it would be nice if an endpoint could keep its view of its own
copath up to date based on Handshake messages alone, which isn't currently
possible (it requires the whole tree).

So there's plenty still to discuss!  Suggestions welcome, either here or at
the interim in a few weeks.

Happy Holidays!

--Richard


[1] https://en.wikipedia.org/wiki/Ampelm%C3%A4nnchen