[messaging] Asynchronous Ratcheting Tree

[Jeff Burdges]

On Tue, 2018-01-09 at 22:44 +0000, Jonathan Millican wrote:


> 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. 

I see.  C and D could fold both those root keys into updates, but they
could only directly advance one tree until either A or B completes the
merge.  

In principle, C and D could incorporate both the DH(A', B) and DH(A', B)
trees in some other way, like adding their points, or placing them as
children of a new node.  I suppose 3-way DHs arranged in a tree make
this problem worse, but one could imagine maintaining a DAG outputs
given by distinct hash functions, but only choosing a nicely merging
subtree, and 3-way DHs could make you DAG shrink by 2/3 per level.  I
suspect all such schemes make private scalars live longer though, which
sounds problematic.

I suspect your optimal merge strategy would be for C and D to build on
either the DH(A', B) or DH(A', B) tree, but recognize both by
incorporating both root keys, and possibly change their mind later if
they see a DH(A'', B') or whatever.  In fact, this recognition might
even help force a malicious A and B to actually do the merge.  I think
this strategy is optimal in the sense that A and B must to keep their
old private scalar anyways until they merge.  


In general, it sounds like ART has larger compromise windows than
pairwise 2-step DH, axolotl/signal, etc. due to the need for more
members to confirm receipt before erasing private scalars.  Inherently
group chats are less secure though so this sounds appropriate. 

Jeff


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20180111/4a39121b/attachment.sig>