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

[Ximin Luo]

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.

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 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/d3af64bf/attachment.pgp>