decentralised.org 6.7 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#+TITLE: Decentralised MLS

[[https://messaginglayersecurity.rocks/][MLS]] requires that commits are made by only one participant at a time.  In the
MLS architecture, this is enforced by the [[https://messaginglayersecurity.rocks/mls-architecture/draft-ietf-mls-architecture.html#name-delivery-service][Delivery Service]].  However, Matrix
does not have a centralised delivery service, and so it does not have a way to
ensure that multiple users do not make simultaneous (and conflicting) commits.
Thus in order for MLS to be usable in Matrix, we must be able to resolve these
conflicts.

In our model, each device has its own view of the state of the MLS group.  A
commit made by one device may not necessarily be seen by other devices within
any given timeframe.  However, we assume that causal relationships are
preserved: if Alice receives an commit from Bob and then sends her own commit,
then if Carol receives Alice's commit (and was also in the MLS group when Bob
sent his commit), then she will also have received device Bob's commit.  (For
simplicity, in this document, we assume that each user has only one device, so
when we say "Alice sends ...", or "Alice receives ...", we do not have to worry
about specifying which device is being referred to.)

Since we do not assume there is a timeframe within which a commit will be
delivered to all participants, all participants will have to keep some old
group state in order to be able to decrypt messages from other users who may be
using the old state.

* Goals

The goals of the method presented here are to:

- allow multiple users to create new MLS epochs concurrently,
- allow users to resolve forks in the MLS epochs so that the end result is
  consistent between users,
- avoid needing to track too much information,
- avoid losing new keys from users,
- avoid too many changes to MLS,
- remain as secure (as possible) as standard MLS.

* Group membership

We will assume that the application has a way to allow clients to determine the
membership of the group in the face of concurrent changes to the group
membership.  For example, in Matrix, there is a state resolution algorithm.
Clients will use this information and make changes (~Add~ and ~Remove~) to the
MLS tree to match the membership given by the application.

* Identifying epochs

In MLS, the epoch is identified by a counter.  However, in the decentralised
setting, since multiple users can create a new epoch from the same epoch, there
will be multiple epochs with the same epoch number.  We can identify an epoch
by both the number and the user who created it.  For example, if Alice starts a
group, then the initial epoch is (1, Alice).  If both Bob and Carol make a
commit based on Alice's commit, then we would have the epochs (2, Bob) and (2,
Carol).  Thus, we need to ensure that no user will create two epochs with the
same counter, which can be done by ensuring that the numbers of the epochs
created by a user will be strictly increasing.

MLS messages identify the epoch that they refer to.  The epoch creator can be
identified within the application message, so that no changes to the MLS
message format are needed.

* Terminology

When two or more users try to make a commit to a given epoch at the same time,
we say that they *fork* the epoch.  The forks result in a directed acyclic
graph of epochs.  An *extremity*, from the point of view of a user, is an epoch
that does not have any children that the user knows about.  Each user has their
own set of extremities, which they update when they create or receive ~Commit~
messages.

* KeyPackage generation number

To ensure that epochs maintain the most recent ~KeyPackage~ for each user, a
new extension is added to each ~KeyPackage~ indicating the generation number.
All ~InitKey~ are generation 0, and each time a user updates their ~KeyPackage~,
they increment the generation number.

* Resolving forks

Each user keeps their extremities.  When the user wishes to send a ~Commit~, if
there is only one extremity, then they will create the new epoch as normal in
MLS.  Otherwise, they will choose one of the extremities as the "base" epoch,
and add any updates from the other extremities.  The user will reference the
other extremities, so that other users will know which extremities were
resolved.  The other extremities can be identified within the application message.

When choosing the base epoch, the user will choose the extremity that has the
highest epoch number.  If multiple extremities are tied for the highest epoch
number, than any of them can be chosen. (FIXME: do we want to make it
deterministic anyways?)

The user will then compare the MLS group membership in the base epoch with the
application's group membership:

- for any user who in the MLS group, but not in the application's group, a
  ~Remove~ proposal is added to remove them from the MLS group.
- for any user who is in both the MLS group and in the application's group,
  check if any extremity has a ~KeyPackage~ for that user with a higher
98
99
100
  generation number, and if so, a ~Remove~ proposal is added with the user's
  leaf number, and an ~Add~ proposal is added with the user's ~KeyPackage~ with
  the highest generation number.
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
- for any user who is not in the MLS group, but is in the application's group,
  an ~Add~ proposal is added.  If the user is present in any of the
  extremities, then the ~KeyPackage~ with the highest generation number is
  used.  Otherwise an ~InitKey~ is retrieved and used.  FIXME: if the user was
  previously in the group, use their last ~KeyPackage~ (that you know about)?

FIXME: do we need any additional rules for setting ~UpdatePath~, over what we
already have in MLS?

After sending the ~Commit~, the user sets their set of extremities to the set
only containing the new epoch.

When another user receives a ~Commit~, they should

- check that all ~Update~ proposals increase the generation number,
- remove the base epoch any referenced epochs from their set of extremities,
  and
- add resulting epoch to their set of extremities.

* Information that needs to be kept

- all previous private keys for old ~KeyPackage~
- all previous ~init_secret~
- FIXME: ...

* Problems

- we may lose entropy.  Suppose that Alice and Bob make concurrent Updates,
  both setting the ~UpdatePath~, and Carol then makes an Update, using Alice's
  epoch as the base.  Then the entropy added by Bob will be discarded.  If
  Carol's random number generator is good, then this may not be much of a
  problem.  Bob will also notice this, and can make a new Update to re-add
  entropy from his RNG (as long as his Update isn't discarded again).
134
135
- we will blank a bunch of nodes, which means that we may have decreased
  performance.
136
137
138
139
140

* Todo

This method does not (yet) consider ~ReInit~, ~PreSharedKey~, ~ExternalInit~,
or ~GroupContextExtensions~ proposals.