[messaging] Group messaging consistency under resource constraints

[Ximin Luo]

On 12/10/14 04:57, David Leon Gil wrote:
> In short: I agree with Ximin; group messaging should be consistent.
> 
> Ximin's proposal: a sequentially consistent log. This is likely to
> cause excessive message delays, as Trevor rightly worries about, even
> with a pure reorder channel.
> 

Yes, I do understand the concern for sure, and I support anything that would reduce the delay time. But I think it's better to fundamentally allow for the possibility, and reduce it, because it grants some very strong security properties.

There have been arguments that "typical transports don't work like this" and I gave TCP as a counterexample. Trevor also mentioned Pond, but actually this is an example in my favour - Pond delays *sent* messages to defeat some types of timing attack. Come on, this is pretty counterintuitive, but it is made essentially invisible to the user and its security reasoning is solid. So why not delay some *received* messages to defeat some types of consistency attack? It can equally be invisible to the user, and the security reasoning (I hope) is solid. I welcome further scrutiny. :)

> -- 
> 
> Alternative: sequentially consistent, partially-ordered message trees.
> Causality == responding to a specific message: so just include the
> hash of the message you're responding to, per Ximin's proposal.
> 

I was unclear originally, but I actually did have partially-ordered message DAGs in mind. But the basic principle of "delivering messages in order, buffering if necessary" applies for both total- and partial-orders.

> Consensus on these trees is, in fact, possible. Lamport's Generalized
> Paxos paper describes how to do this for arbitrary posets. Relaxing
> total ordering to partial ordering speeds up time to consensus a
> lot.[paxos]
> 

It's possible, but with a probability that is low compared to cryptographic standards (like 99.9999%?). For transcript consistency purposes, I'm advocating to forget about the consensus / "common knowledge" problem, and focus on first-order knowledge instead.

consistency = I know P, I know that (everyone knows P)
consensus = I know P, everyone knows that (everyone knows P), everyone knows that (everyone knows that (everyone knows P)), etc.

In our case, P (for a message m) is "message m exists and is part of the session". (The original mpOTR paper also uses the first definition but calls it "consensus", which I'd like to correct before it gets too popular.)

> Concerns about the precise client-server architecture are rather
> separate from the consensus algorithm design; anything targeting a
> mass audience will require a reliable, available server. (IRC-style
> chatrooms are not a mainstream UX.)
> 

A distributed dumb "cache+forward" system might also work instead of a server. If the clients *have* end-to-end reliability logic built-in (which I also advocate), then the design is flexible and the middle of the network could be tweaked for any other security concerns (e.g. unlinkability).

X

-- 
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/20141016/f397c941/attachment.sig>