Re: [MLS] Unpredictable epochs?

[Richard Barnes <[e-mail]>]

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