Re: [MLS] Unpredictable epochs?

[Kelvin Ritland <[e-mail]>]

>
> Not-pseudorandom implies some assumptions, e.g., that each sender would
> only send one Commit on top of each epoch

This isn't bad imo, it reduces complexity to some extent. I'm somewhat in
favour of a non-pseudorandom tiebreaker if there's no other arguments
against it.

How many bits of sequence number?

Have we considered using varints? Similar to the CTLS proposal -
https://tools.ietf.org/id/draft-rescorla-tls-ctls-02.html#rfc.section.3.1


Other forking considerations, I think there's more involved than just
changing the epoch identifier:

1. We'll need merges as well, since forks can lead to inconsistent group
membership:
Suppose in epoch 1 a group has A, B, and C
A removes C in epoch 2A
B adds D in epoch 2B

We now have two group states 2A with AB and 2B with ABCD - and it's unclear
which group to use to send with. We could mandate that any client MUST send
a "merge" commit on it's view of history before sending any message. This
commit could just be the list of epochs that are being merged (+a usual
DirectPath update?), and processing it would mean replaying all proposals
up to the common ancestor for those epochs on the common ancestor.

2. Forward secrecy issues.
By allowing forks, devices must now keep the previous epoch around to
derive possible future forks - but this means we'll be re-using
init_secret_. A possible solution could be to use the nth app secret from
the ASTree instead of init_secret_ as the start for the new epoch secret.
This ties nicely with using a non-pseudorandom tiebreaker.

3. Ordering implications
It's unclear what a sensible ordering strategy is for the DS if we allow
forking. (simply ensuring that each commit is based on the "current" epoch
isn't well defined since there can be multiple "current" epochs).

By allowing forks the DS need not enforce ordering at all imo. This means
that apps need to keep around old epochs, but this is already required per
(2). A different question is how many we need to keep around - perhaps a
TTL or the past N epochs after a topological sort would make sense.

Generally I think getting rid of server ordering is good idea:
- Helps Matrix and general federation use cases
- A common consistent mutated state for group operations can cause server
side DB contention in my experience

Forks is one way to remove ordering, and if we need to support it anyways
it's a nice benefit.

On Thu, Jan 2, 2020 at 12:52 PM Richard Barnes <[e-mail]> wrote:

> Argh, hit send too soon.  Continuing below...
>
> On Thu, Jan 2, 2020 at 3:38 PM Richard Barnes <[e-mail]> wrote:
>
>> Hey all,
>>
>> Resurrecting this thread, as it seems that we never came to resolution on
>> this question.
>>
>> I'd like to propose we scope down and solve a narrower problem, namely
>> the problem of enabling forks in the group's history.  So we're not going
>> to try to provide any privacy properties, just remove the impediment to
>> forking.  This seems like a worthwhile thing to me just because it seems
>> silly to have forking blocked just because of syntactic constraint, in
>> addition to it likely being necessary for some decentralized use cases
>> (e.g., Matrix).
>>
>> To allow forks, we really just need some "tie breaker" bits in the epoch
>> ID so that if a given epoch has multiple successors, they end up with
>> different epoch IDs.  And in order to avoid synchronization, each
>> participant needs to be able to generate those bits independently.  There
>> are a couple of basic questions about how to construct the tie breaker:
>>
>> 1. Pseudorandom or not?
>>   - Not-pseudorandom example: tiebreaker = commitSenderID
>>   - Pseudorandom example: tiebreaker = H(MLSPlaintext(Commit))
>>   - Not-pseudorandom implies some assumptions, e.g., that each sender
>> would only send one Commit on top of each epoch
>>   - Pseudorandom risks random collisions
>>   - Possible to do both: tiebreaker = commitSenderID ||
>> H(MLSPlaintext(Commit))
>>
>> 2. How many bits of tiebreaker?
>>
>   - Non-pseudorandom size will be dictated by what we include
>   - Pseudorandom size will be dictated by tolerable collision probability
>   - Probability of collision ~ (number of forks per seq no) / 2^{number of
> bits}
>
> 3. How many bits of sequence number?
> - DS might want to see sequence to help enforce ordering
> - Probably want this big enough to avoid wrapping.
>
> (Note that this is a value that goes in every message, so there's some
> incentive to keep things small.)
>
> Personally, my proposal would be something like:
>
> struct {
>   uint64 sequence_number;
>   uint64 commit_hash; // H(MLSPlaintext(Commit))
> } EpochID;
>
> That seems to strike a reasonable balance between low collision
> probability (~2^-64) and a reasonably small identifier.  If 128 bits is
> good enough for IPv6, it can be good enough for us :)
>
> Does that seem workable to folks?
>
> --Richard
>
>
>
>>
>>
>>
>>
>>
>> On Fri, Apr 26, 2019 at 4:18 PM Benjamin Beurdouche <
>> [e-mail]> wrote:
>>
>>>
>>> > On Apr 26, 2019, at 9:26 PM, Jon Callas <[e-mail]> wrote:
>>> >
>>> >> On Apr 26, 2019, at 2:22 AM, Michael Rosenberg <[e-mail]>
>>> wrote:
>>> >>
>>> >> So why not remove epoch entirely?
>>> >
>>> > An epoch lets you deal with things happening neither too often nor not
>>> often enough. Presume there is a client that is either malicious or just
>>> stupid. You want to keep it from forcing a rekey every 100µs. You want to
>>> force a rekey every so often. Hence epochs. Yeah, picking the right epoch
>>> size is an exercise left to the reader.
>>>
>>> You can’t use the epoch number for that as it is just global counter for
>>> group operations, we will have to keep track of the latest group operation
>>> “timestamp” for each member within the group state to check “update
>>> frequency” and handle some of the situations you described.
>>>
>>> Btw in the TreeKEM formal spec I use a 64 bit unsigned integer, and I
>>> feel like having more than 2^32 group operations over the lifetime of a
>>> group is not unrealistic in certain extreme use cases, especially with
>>> large groups forcing PCS for application messages by triggering an update
>>> after each app message...
>>>
>>> We could remove the epoch number if we really want but it is necessary
>>> to give the Delivery Service some ordering information (unpredictable or
>>> not is an interesting question) to handle concurrent handshake messages
>>> which is, I believe, the main current goal of that information.
>>>
>>> Benjamin
>>>
>> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>