[messaging] Group messaging consistency under resource constraints

[Natanael]

Den 7 okt 2014 03:30 skrev "Andy Isaacson" <adi at hexapodia.org>:
>
> Of course a malicious-client-tolerant distributed cryptographic system
> will have a somewhat different set of failure modes to convey to the
> user, but I'm just responding to the argument that it is impossible to
> design a UX to handle even the simplest case of transcript inconsistency
> (of a missing message in the history).  The existing modern centralized
> chat systems handle this case OK and users find it acceptable.  Let's
> achieve feature parity in a distributed system and get on with finding
> and solving the actually hard problems.
>
> The first actually hard problem that we get to attack is, what happens
> when Bob sends m1 to Alice and m2 to Carlos, then Alice replies m3.
> What does Carlos see, and how can he prove it?  But there are more hard
> problems than just that one. A taxonomy of transcript consistency errors
> would be useful...

My opinion is that you should use a hash chain per device that is part of
the conversation. (This isn't substantially different from previous
proposals. But details may differ.)

You got both your phone and laptop in the conversation from your account?
You'll need either one hash chain per device, or proxy everything via one
of the two devices (to not leak as much usage metadata and preserve
consistency).

All messages sent acknowledges all of the last messages on each chain that
is part of the conversation. If you see a message from a broken chain (you
got message 1, 2 and 4 from Bob but not 3) then your message states that,
and hopefully somebody else relay that message to you, allowing you to
later acknowledge receipt.

If the network is unreliable, the devices should acknowledge more than one
message at a time from each chain. Maybe with the hashes listed directly
(reveals to other devices if you've seen something they haven't), maybe
with a bloom filter (smaller and faster but don't reveal if you've seen
something they haven't), or a Merkle tree hash (small, quick checks,
possible to confirm if you've seen messages they haven't by recomputing the
whole thing and checking if it is identical with the known messages - but
requesting the lacking messages isn't straightforward).

Messages acknowledged by all devices and received in-order could have a
green marker in the UI.

Messages received out of order would get a yellow flag, and there should be
a feature for allowing you to tap it and see which messages that was
created later than it but received earlier (maybe simple receipt order
counters, timestamps of receipt, or similar). You should be able to dismiss
the flag once you confirmed to your device that you are aware about the
correct order.

Messages not yet acknowledged by everybody has a triple dot symbol like
this ... to show "waiting for acknowledgement" for X minutes, then it
switches to a red flag. Tapping it should show who hasn't yet acknowledged
it. Note: devices going offline must try to signal it in advance to reduce
false negatives here.

Forked chains (where different messages was sent to different people) get a
red flag. Tapping it could show who reported receiving different messages
(Alice received a message 5 with hash X from Carol, Bob received a message
5 with hash Y).

Messages that others report that they received out of order would have a
small marker. This is because reordering could potentially cause the other
participants to misinterpret the intended message, so you should be able to
check this (it would be voluntary to let your device report what was
received out of order).

Seeing another device claim to not have received all messages you have
received will prompt your device to relay them.

Hopefully this won't be very resource heavy. Unless used in really huge
active groups, the load on RAM, CPU and bandwidth from the overhead
introduced by the hash chains should be manageable even by really cheap
Chinese budget smartphones. I don't believe devices weaker than that type
of devices are going to be common for messaging anywhere. It might however
cause you to exceed some carrier's limited data caps (a few hundred MB /
month isn't rare in some places, including USA).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141007/e9937f96/attachment.html>