Re: [MLS] MLS in decentralised environments

[Martin Thomson <[e-mail]>]

Is it possible to have a common tie-breaker process and force the
loser to rebase?

That is, if the change c->c' wins, then d needs to apply their d->d'
change again on top of that change (or move to d'').

A simple tie breaker process would inform all participants of the head
of both forks and to pick a winner based on the one that gets the
largest result from H(root).  That's open to participants choosing
keys to influence the result, so you probably don't want that precise
design (esp. if forks include removals), but hopefully the idea makes
sense.

The next problem would be that repair of a fork can be expensive.  If
there are multiple changes on the losing fork, then all those changes
might also compete as the updates propagate.

On Tue, Apr 3, 2018 at 8:41 PM, Katriel Cohn-Gordon <[e-mail]> wrote:
> Hi Matthew,
>
> Thanks for thinking about this. I agree that it's a problem I think exists
> even in the centralised world, since it's much nicer to build a system that
> doesn't have to provide strict sequencing guarantees.
>
> # The problem
>
> I'll sketch out the underlying problem first, even though I think you
> spotted it pretty well, just to make sure we're on the same page. The
> problem is from the ratcheting tree construction: two updates which both
> want to change a particular intermediate node cannot both be applied at the
> same time. Let me try out some ASCII art: consider a simple tree like
>
> root
> ├── x
> │   ├── a
> │   └── b
> └── y
>     ├── c
>     └── d
>
> and suppose c wants to update to c', giving the following tree and
> publishing g^i(y') where y'=g^c'd
>
> root
> ├── x
> │   ├── a
> │   └── b
> └── y'
>     ├── c'
>     └── d
>
> while d also wants to update to d', giving the following tree and publishing
> g^i(y'') where y''=g^cd'
>
> root
> ├── x
> │   ├── a
> │   └── b
> └── y''
>     ├── c
>     └── d'
>
> These can't both be applied by A: A can either set their view of the last
> node on their copath to be y' or y'', but not both of them. Moreover, A has
> no way of "combining" the two updates.
>
> # Not the problem
>
> One thing I should highlight up front is that this does not necessarily
> prevent decrypting messages, only applying key updates. Specifically, if A
> receives either C's or D's update they can apply it and compute the
> resulting root key, then decrypt the message. Of course, if the update is
> one that should have bounced, then they might have to "un-apply" it.
> Moreover, if A wants to send their own update, they need to pick one of y'
> and y'' to base it on. This is something I don't think we've reasoned about
> in detail yet.
>
> For other reasons due to malicious group members, I think we're likely to
> come up with a system where each participant has various "proposed" updates
> sitting around, and then only confirms them after receiving some other
> message. This sort of algorithm should also help here, because I think it
> will also need the ability to unwind or not apply a potential update.
>
> # Things we tried that don't yet work
>
> One thing we thought about was using some tricks with Diffie-Hellman to
> allow both updates to be processed at the same time. Unfortunately we
> couldn't actually come up with a system that works (using a KDF to turn
> group elements back into integers hurts here), but there might well be one.
>
> Another thing is the observation that in fact it is sometimes possible to
> apply two updates at once: specifically, if two updates change different
> copath elements with respect to a recipient, then that recipient can apply
> both of them. Unfortunately this only helps some recipients, not all of
> them, so it doesn't really solve the whole problem.
>
> Another thing is having the server do some clever re-ordering. The challenge
> is that in the end, by construction the correct value of the intermediate
> node should only be computable by its children, so there's only so much the
> server can do.
>
> For the same reason, I'm not sure the server can unilaterally rebalance the
> tree; I think it would need some help from one of the participants. I'd have
> to think more carefully about the precise keys which it would need to do so,
> though. In particular, if you are more worried about re-ordering join events
> than re-ordering key updates, there might be some specialised tricks that
> work.
>
> # Question about the Matrix context
>
> In the Matrix setup, do nodes actually know when there is consensus on a
> particular set of messages? That is, is there some point at which they can
> conclude "ok, I know that the following messages are actually the right
> ones, and haven't been pre-empted or undone by successors"? (If so then I
> think the "multiple proposed updates" ideas will help here too.)
>
>
>
>
> does that make sense? :)
>
> best,
> K
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>