Re: [MLS] Unpredictable epochs?

[Richard Barnes <[e-mail]>]

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?





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
>