[messaging] Necessary considerations of a linear order based on server-receive time

[Ximin Luo]

During the mpCAT summit we discussed the following idea:

- The server dictates the ordering of messages.
- For any message M sent by a given user, the server may validly insert others' messages before M.
- Everyone attests to the order, and checks others' attestations.

This is a simple way to achieve a canonical and consistent linear order, and it seems like a nice route to go down for server-based systems. On the UI side, we might do something like the following:

- Alice sends message T, her UI displays X in grey
- Alice receives R, S, T, her UI inserts R, S in black above T, then re-colours T to be black.

There are some additional consequences not immediately apparent, however.

To attest to the order, Alice (in message T) can point to the last message she received from the server. This might seem like it would be enough, however:

Say Alice's last message received from the server is Q. She sends two messages T, U. Using only single pointers, there are two options:

a) all of T, U point to Q. But then, the server could re-order T, U
b) Q <- T <- U. But then a server might validly insert messages (say, X) between Q, T, and T <- U will look like Alice has seen X.

To fix this, we must encode both the last message Alice received, *and* the last message she sent. The former should be done by unforgeable pointers, but the latter might be achievable using sequence numbers. Continuing with the example above, we would do:

- T(7, Q) and U(8, Q)

Note that if Alice receives T (that she sent) before she sends U, she would instead do:

- T(7, Q) and U(8, T)

X

P.S. Partial ordering is still very much definitely on the cards, but this scheme was thought of as conceptually simpler, and perhaps easier to achieve first. The topics above are the results of exploring that idea further.

[1] This is important not only for human reasons, but when designing a forward-secrecy ratchet. Encoding direct unforgeable references to "messages seen by the sender" lets us calculate what ratcheting material is actually appropriate for a given message - this is important for >2-party ratchets where trial decryption is much more costly - and it also makes robust deletion logic easier to implement.

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 880 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140426/68a1d094/attachment.sig>