[messaging] Asynchronous Ratcheting Tree

Tue Jan 16 07:12:00 PST 2018

Hi Jonathan! Thanks for your reply.

I confirmed what you said. Here's some notation I made up to understand the problem better myself, maybe it might be useful to other people following too. For example it makes explicit the fact that each node has both a public and private value, which sometimes get mixed up in diagrams.

Each node in the tree has a secret value calculable by the members beneath it, and a public value for others to consume, which can be recursively defined as follows:

S[x,y] = i(S[x] . P[y]) in the natural numbers
P[x,y] = S[x,y] . G     in the DH group

.    - is "multiplication" in a ECC DH group, or "exponentiation" in a normal DH group
i()  - is the injection from natural numbers to group elements
x, y - are either individuals or member-subtrees

so e.g.

  S[(a, b), (c, d)]
= i(S[a, b]        . P[c, d])
= i(i(S[a] . P[b]) . P[c, d])

When Alice wants to change their secret from S[a] to S[a'] she broadcasts P[a'], P[a', b], then everyone can calculate S[(a', b), (c, d)].

And similarly Carol in a separate branch of the conversation, broadcasts P[c'], P[c', d], so everyone can calculate S[(a, b), (c', d)].

If we want to calculate S[(a', b), (c', d)] this is equal to 

= i(i(S[a'] . P[b]) . P[c', d]) for Alice
= i(i(S[b] . P[a']) . P[c', d]) for Bob
= i(i(S[c'] . P[d]) . P[a', b]) for Carol
= i(i(S[d] . P[c']) . P[a', b]) for Dave

However if the overall tree is bigger than (a, b), (c, d) then to calculate S[abcd + others] other people would need P[(a', b), (c', d)], which is not calculable from their own secret, nor is available from any of the data broadcasted so far.

In other words, merges of a 2-fork are possible but only by members in the smallest containing-subtree that the branches operate on. In general, merges of n-forks by a single member are possible depending on what parts of the tree they change, but would have to involve co-operation/synchronisation in other cases.

I agree with your point that in principle you could set up another protocol to co-ordinate the latter case but it would be pretty complex.

I'd guess (contrary to Jeff) that a 3-party DH (e.g. Joux's pairing-based scheme) would probably improve the matter - you could probably support non-cooperative (asynchronous) merges of a 3-fork as long as they all belong in different subtrees. I haven't done the calculation for this yet though.

I do hope there's more research in this direction of mergeable scalable ratchets, because I think mergeability is important for asynchronity - otherwise you have to rely on some other effectively-synchronous protocol to provide some level of linear ordering as we can see for this ART, "undoing" the work towards asynchronity in the ratchet.

As mentioned in the paper, pairwise DH-ratchets work like that but don't scale to very large groups, which is the trade-off I've been making in a side-project of mine. (Larger groups inherently leak more anyways, so..)

X

Jonathan Millican:
> Hi, I was one of the Collaborators on this paper. Thanks for reading it!
> 
> You're absolutely right that we don't define a way to merge operations into
> a linear order. We actually deliberately left this out of scope: largely to
> keep things simpler for the initial proofs of the structure, and partly
> because there are potentially a number of ways to do this which may have
> different trade-offs in different situations. For example, a protocol could
> require a central server to rejects messages which are not premised on the
> correct root node; or perhaps you could require a strict global ordering on
> messages where the "winner" in an instance of conflicting updates is simply
> whichever update came first.
> 
> Regarding merge operations, conflicting updates to a tree shouldn't be
> commutative in the general case, but I think there may be circumstances
> where limited merges could occur:
> 
> Take the following tree:
> 
>         DH(DH(A, B), DH(C, D))
>        /                      \
>    DH(A, B)                DH(C, D)
>   /        \              /        \
>  A          B            C          D
> 
> If A and B were to send simultaneous updates, ( [A', DH(A', B)] and [B',
> DH(A, B')] ), then C and D are unable to merge them at all; as this would
> require computing DH(A', B') without access to either private key.
> 
> However, if A and C were to send simultaneous updates ( [A', DH(A',
> B)] and [C',
> DH(C', D)] ), then everybody is able to merge them. The general intuition
> here is that you should be able to merge a single update to each branch of
> your copath; but if two updates come off the same branch then merging them
> would require you to solve the Diffie-Hellman problem.
> 
> Assuming I got the above correct (it's late so I may not be thinking
> straight), I suspect that this may mean that a protocol could be built
> whereby between 0 and log(n) conflicting updates can be merged at a time,
> depending on who the sender is. Even if we don't have a situation like the
> above where absolutely everybody in the tree is able to compute the entire
> merged tree; so long as the person sending the next message is able to,
> then they can recompute all of the relevant copaths and send them to
> everybody else along with their own update.
> 
> Of course, this suggestion involves its own complexity and likely
> performance/network trade-offs; so I have no idea if it would actually be a
> good one in practice. Potentially though, it might be one model for limited
> merge support. I also haven't really considered whether this would
> compromise any security properties, which would be important to look into!
> 
> Hope that makes some sense,
> Jon
> 
> 
> On 9 January 2018 at 12:34, Ximin Luo <infinity0 at pwned.gg> wrote:
> 
>> I was just forwarded this: https://eprint.iacr.org/2017/666
>>
>> On Ends-to-Ends Encryption: Asynchronous Group Messaging with Strong
>> Security Guarantees, by Katriel Cohn-Gordon and Cas Cremers and Luke
>> Garratt and Jon Millican and Kevin Milner
>>
>> It looks very nice. However, on a quick glance through the paper, it
>> doesn't define a way to merge operations performed on the DH group tree.
>> That seems to constrain the group chat to rely on some external mechanism
>> to ensure that operations on the ratchet are performed (by everyone) in a
>> linear order - i.e. it would still have to operate synchronously.
>>
>> (This constraint is fulfilled trivially in a two-party ratchet because
>> each sender always sends in a linear order, wrt the other recipient.)
>>
>> I wonder if it's possible to define a merge operation on the DH group
>> tree, so that e.g. Bob and Carol can advance the ratchet independently of
>> each other (e.g. to B and C, each from state O) such that when Alice
>> receives B and C, she can construct the merged ratchet state X that
>> combines both changes (O to A) and (O to B)?
>>
>> Alternatively, an explicit merge algorithm is not necessary if it can be
>> proved that applying O->A and O->B on top of O is commutative.
>>
>> X
>>

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
https://github.com/infinity0/pubkeys.git