Re: [MLS] Efficiency and "Ampelmann trees"

[Raphael Robert <[e-mail]>]

Hey Richard,

I think this could work the way you intended it. My understanding of this is that we use the (second?) preimage resistance of the hashing algorithm to make it impossible for the server to forge arbitrary values anywhere in the (co)path it provides to clients. 
I think your assumption is right that the data requested from a server is indeed either a direct path or a copath. What both have in common is that they start at the leaf level and include one node from each level — all the way to the root.
This means the server just has to provide the sibling of each node as proof. 
The hash values could be computed by the server, as long as the commitment is part of HS messages (this could be either implicit in the group state, or sent as an explicit value).

For the sake of simplicity, couldn’t we simplify the node hash to H(L || R || V) instead of H(H(L || R) || V) ?

For leaf nodes, the values for R and L would probably just be null, effectively only the public key of the node would be hashed.

For blank nodes, we can maybe think of a mechanism similar to node resolution to compute the values of R and L. If L is blanked, and LL and LR are its children, we could substitute L by (LL || LR). This would have to be recursive as long as at least one child node is blanked. Alternatively, L could be substituted by H(LL || LR), if that provides additional security. This might be more in line with the per-level hashing we would do if there were no blank nodes.

In the extreme case of a tree that only contains leave nodes and no intermediate nodes (and we don’t do the per-level hashing mentioned above), the root hash value would be H(H(V_A) || H(V_B) || H(V_C) || …) where V_x are the values of the leaf nodes.

Is that the other layer of math you had in mind?

Happy Holidays!

Raphael

> On 24 Dec 2018, at 16:53, Richard Barnes <[e-mail]> wrote:
> 
> 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 <https://en.wikipedia.org/wiki/Ampelm%C3%A4nnchen>
> 
> 
> 
> <Dirpath Proofs.pdf><Hashing Structure.pdf><Ampelmännchen!.pdf><Copath : Frontier Proofs.pdf>_______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls