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
signature.asc
Description: OpenPGP digital signature
_______________________________________________ OTR-dev mailing list [email protected] http://lists.cypherpunks.ca/mailman/listinfo/otr-dev
