[OTR-dev] DAG-based multiparty conversation ensuring transcript soundness

[Ximin Luo]

On 30/11/13 22:18, Ximin Luo wrote:
> I came up with this idea today whilst talking with George K, inspired by Git. It's very similar, but different from, the idea Trevor mentioned in the other thread, so I thought I'd start a new thread.
> 
> For those that don't know, the git data model represents commits by DAGs. This works in a decentralised manner - parties don't need to see "the latest revision" since they just commit on top of the latest commit they see, then any branches are detected and merged together later.
> 
> You can use this as a very simple model for ensuring transcript soundness in a multiparty conversation. The user interface becomes slightly more complex, but I don't think this is too much of a problem since the user does not need to manage this complexity, just react to the warnings in the rare cases that out-of-order delivery does occur.
> 
> The idea is, when A wants to send a message ("make a commit" in git), the message contains the hash of the previous parent(s) messages that A knows about. A then broadcasts this to everyone else, who can verify each its authenticity (somehow! :p). Since the previous parent(s) themselves contain hashes of their parents, by induction this ensures transcript soundness. Thus, we entirely bypass the problem of trying to order messages. For example:
> 
> Current transcript is (1)<--(2)<--(3). B sends a message (3)<--(4) and A sends a message (3)<--(5). IT DOES NOT MATTER what order anyone receives (4) and (5) in, since at the time of sending, only (3) is relevant!
> 
> When a branch occurs, each sender simply uses all the branch heads as the parent(s) for the next message, similar to a merge commit in git, but here instead it has the semantics "I've seen both branches".
> 
> You can draw this DAG in the UI to represent accurately the context in which each person said a commment. When a party receives an incomplete transcript that looks like (1)<--(2)   (?)<--(4), you write a big warning in place of the missing message, "WARNING: PREVIOUS CONTEXT NOT YET RECEIVED; BEWARE HOW YOU INTERPRET THE NEXT MESSAGE", and replace this when you finally receive that message.
> 

In this case, you ought not to allow the user to send out any messages, since they don't know the entire context. Or, if there are multiple branches and some are complete, show only these branches (with warnings for the entirety of the incomplete branches so the user isn't tempted to be influenced by the messages on the incomplete branches) and allow the user to send out a message with only these branches as the parent.

This may be a better failure mode than simply erroring when the consensus check (from the idea in the other thread) fails. Especially if there is an attacker that is sending out selective messages to some parties in the conversation, the conversation can still continue, ignoring the attack branches that only some people have a complete view of.

> To avoid the attack where someone indefinitely DOSs one party, the parties periodically poll each other for the "latest branch head(s)". If they don't get a response, there is a problem.
> 

I recognise this part is the most hand-wavy, but hopefully can be made more precise. Apologies if this post is premature and the idea is incomplete, I am in a waiting room at the moment with nothing else to do. :p

> I do not yet have a proof of security, but the model is very like git, and constructed out of fairly simple building blocks.
> 
> There is lots more to do to develop this idea further, but I thought I'd let you guys know about it - I was very very excited that I thought up this idea, since ***it does not require a central server to define a total ordering on the messages***!!! The insight is that a "total ordering" is unnecessary for this problem - only the partial order from the POV of each recipient, which they can they authenticate.
> 
> Ximin
> 

-- 
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: 897 bytes
Desc: OpenPGP digital signature
URL: <http://lists.cypherpunks.ca/pipermail/otr-dev/attachments/20131130/a4c749e5/attachment.pgp>