Revision as of 19:03, 8 September 2014

This builds on the server-dictated ordered transcript hashes currently mentioned in SenderKeys.

Definitions

A message m is fully-acked (from the POV of a given member u) iff, for all recipients r, u has accepted a message by r where seqnum(parent(r)) ≥ seqnum(m).

• recipients possibly includes u, but certainly excludes m's sender
• accepted means delivered locally, i.e. received, then decrypted-verified including parent hash checks; all causally-previous messages must already be accepted
  • we assume a server-dictated ordering, so accepting a message at seqnum i means we have already accepted all messages j ≤ i.

Consistency

When a member u wants to part, they send a "farewell" message m:

• Everyone should explicit-ack this message ASAP
  • This message should contain the next-sender-key, to be used after u leaves, encrypted to everyone except u. This ensures old members can't read new messages even if they eavesdrop.
  • (We could probably do something similar for group keys.)
• When this message is fully-acked, u gains consistency for all previous messages up to m, and may leave.
  • Other messages should be probably be discarded - u won't have a chance to verify their consistency.
• TBD: need to think about simultaneous parts

When a member u accepts a non-explicit-ack message m at time t:

• if u did not send m, and they have not acked m by t+ACK_GRACE_INTERVAL, they should send an explicit-ack
• if m is not fully-acked (from their POV) by t+(2*BROADCAST_LATENCY)+ACK_GRACE_INTERVAL then issue a local UI warning. Cancel the warning if/when full-ack is reached later.

Parameters and properties

• BROADCAST_LATENCY should be based on the transport.
• ACK_GRACE_INTERVAL should be based on expected user communication rate.

Both of these should be defined to cover common cases (e.g. 95th-percentile) rather than being mean values.

The above checks should be applied for every single message. This guarantees that a warning shows up if we don't reach consistency within the timeout defined above, and works even if people don't manually send messages.

If we set ACK_GRACE_INTERVAL high enough to match the typical interval between a user's messages, then (in theory) the overhead is only incurred once everyone stops talking and we automatically send off one extra round of acks. While the lull in activity continues, there will be no extra messages, since we don't require explicit-acks to be fully-acked themselves. (Preliminary experiments on some code I wrote shows this to be effective.)

We are still vulnerable to a "drop everything" attack, but that can't be helped unless we have unconditionally-periodic heartbeats. Not sure if we want to put these in the upcoming spec.

(The above is basically my msg-notes stuff, except assuming reliable transport, without recovery or flow control, without heartbeats, and adapted to a server-dictated ordering.)

Relative ordering

Ensure that messages received out-of-order are highly visible to the user.

A message m is unsynced if seqnum(parent(m)) < seqnum(m) - MAX_UNSYNC_COUNT

• MAX_UNSYNC_COUNT may either be constant, or a linear function of the number of members, TBD.

These messages should be highlighted in some way in the UI that is not too severe. They are still valid messages; the user should just be informed that they refer to older context that may be surprising.

This definition is globally consistent (or else transcript consistency breaks) so it's easier to reason about, and the warning is simpler to explain than MAX_RTD.