[messaging] Group messaging consistency under resource constraints

[Ximin Luo]

Some of us have been working on group secure messaging, and there is an
outstanding issue within the broader topic of how to achieve consistency. Those
who have followed this topic can Ctrl-F to "Tradeoffs with causal ordering".

Model of consistency
--------------------

We have pairwise communication, but a group communication adds some notion of
coherency or unity. Previously, consistency has been described (e.g. in the
original mpOTR paper) in terms of members believing the same transcript at the
end of the session. I'll re-introduce it instead using a model that I believe
is probably equivalent, but is more simple to understand and direct to achieve.

I'll start by talking about consistency of a given message, rather than of the
entire session. This is simpler; we only have one message to think about. One
may think of consistency as verifying the (other) recipients of a message m:

- as the sender, you verify everyone has received it.
  - the adversary is the transport; you assume recipients are honest.

- as the recipient, you verify everyone else has received the same thing.
  - the adversary is the transport *and the sender*; you assume other
    recipients are honest.

This is different from what is commonly called "consensus". Consensus would be
"everyone knows that everyone received the mesage, and everyone knows that
everyone knows, etc", aka "common knowledge" [1]. It's a well-known theorem in
computer science that this is impossible to guarantee. By contrast, consistency
as defined above is first-order knowledge, "I know P", where P = "other
recipients saw this message".

We (i.e. each recipient) can gain this knowledge with full confidence, if we
receive authenticated acks from every other recipient that claims "I have seen
m", assuming that the recipients are honest. So that others may gain this
knowledge too, you should also send such a message yourself. If you don't
receive these acks within a timeout, you warn the user, and maybe try to
recover (out of scope for this post).

A: a1
B: ack(a1)
C: ack(a1)

What is the cost of this? For every message that is sent, all the recipients
have to broadcast an ack to everyone else. So the cost per message is O(n^2).
Can we make this more efficient?

More efficient acks
-------------------

One strategy that reduces the number of acks, is to not send acks immediately.
In a typical session, several messages are sent by several different users. So,
instead of acking each message individually, we can wait a while, then ack all
the messages we received in this period all at once. We can even do this within
a message that the user sends manually, so there is no extra cost. (To avoid
others timing out on us, we should not wait for the user to do this, though.)
So this cuts down on the number of messages we have to send.

A: a1
A: a2
B: b1, ack(a1, a2)
C: c1, ack(a1, a2, b1)

However, in this model, we'd still have to refer to every single message, i.e.
explicitly refer to every single message sent in the sesion. So the size cost
of acks is still O(n^2) per message, but the number of extra messages is now
greatly reduced, so the constant factor in the O-notation is less in practise.
But can we make this even more efficient?

If we commit to delivering messages in causal order, then instead of claiming
"I have seen m", we can instead claim "I have seen m and all messages causally
before it." This means that I only need to refer to a maximum of n messages in
each ack I send out - because there are n members and acking each member's
latest message implicitly acks all of them. Ideally, I'd only have to refer to
1 message, namely if there are no concurrent sends.

A: a1
A: a2
B: b1, ack(a1) # hasn't seen a2 yet
C: c1, ack(a2, b1) # implicitly acks a1, since a1 was acked in b1

with a fast, reliable transport:

A: a1
A: a2
B: b1, ack(a2)
C: c1, ack(b1) # implicitly acks a2, a1, since a2 was acked in b1

This latter technique also strengthens our original model of "consistency of a
message" into "consistency of a message and the full history", which is a more
powerful model than the traditional "consistency of a transcript" since it
works incrementally.

Tradeoffs with causal ordering
------------------------------

Committing to delivering messages in causal order has been controversial for
those with resource constraints [2], because it involves queueing some messages
from being displayed until their ancestors arrive. The argument is that this
breaks user expectations, and/or would not work if delivery is unreliable
(assuming a reliability algorithm would be too costly).

I believe that this cost is over-estimated, and that it would *improve* user
experience in the minority of cases where the queueing behaviour would actually
come into effect (i.e. when the transport behaves badly). Having implemented
such an algorithm myself, I see that the time for which a message is queued is
never significantly large (compared to average transport latency), assuming the
transport works well some of the time, which it does because you've received at
least *one* message out-of-order.

It would also be a shame to prevent stronger properties (i.e. consistency of
history) from being achieved even when resources are *not* constrained and the
transport works well. Other arguments are presented in [3].

However, I invite other proposals, suggestions, and comments on the matter. The
primary scenario discussed previously was TextSecure SMS, but apparently they
are stopping support for that? [4] So the resource constraints could be
different now, and I'd be interested to know if the arguments still hold with
the same strength.

One previous suggestion [5] mixes up the models, using "last-message-seen"
pointers, implying the meaning "seen *all messages* before m", but at the same
time allowing for the situation where you could show m to the user, but
not some of its ancestors. That link also contains a specific example of why
it's bad, but the TL;DR version is that the semantics of the pointers doesn't
match the reality of the rest of the system, which is going to break user
expectations even more severely.

If one wants to try to achieve consistency without reliability or ordering, one
can fall back to the single-message consistency I introduced originally.
However, as mentioned before, this does mean that each message has to be
referred to *explicitly*, which goes up against message size constraints.

There are also a few other suggestions in [3] but they also go up against
similar constraints, but perhaps it could inspire someone else to propose a
tweaked version that fits within the constraints.

X

[1] https://en.wikipedia.org/wiki/Common_knowledge_(logic)
[2] https://moderncrypto.org/mail-archive/messaging/2014/000375.html
[3] https://github.com/infinity0/msg-notes/blob/master/causal/01-ordering.rst#concerns-about-buffering
[4] https://moderncrypto.org/mail-archive/messaging/2014/000902.html
[5] https://moderncrypto.org/mail-archive/messaging/2014/000373.html

-- 
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: 819 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141006/b2d88a7f/attachment.sig>