[OTR-dev] Fwd: Ensuring transcript soundness in a multiparty chat setting

[Ximin Luo]

On 29/11/13 11:50, Мария Коростелёва wrote:
> 
> This approach reminds me more about OldBlue, than the algorithms described in
> papers [0] and [1], that were mentioned in the first letter. What's the
> difference?  
> 
> [..]
> 
> [0]: http://www-users.cs.umn.edu/~hopper/gotr.pdf
> <http://www-users.cs.umn.edu/%7Ehopper/gotr.pdf>
> [1]: http://matt.singlethink.net/projects/mpotr/oldblue-draft.pdf
> 

(Maria, [1] is the OldBlue paper?)

I just read that myself, and can now see that the DAG model it proposes is the
same as the one I mentioned in that other thread I started. Sorry for not
reading through everything. I was also thrown off by the description of the
"consensus check" which seems a separate thing from OldBlue, which requires
hashes of all previous messages.

I don't think this is necessary though - when you send a message with its
parent(s), this commitment is treated transitively, so you don't need to
explicitly publish that you've seen the non-direct ancestors. What does "all
previous messages" (explicit transitivity) gain us, Trevor?

I like the DAG, because it lets us model different types of attacks using very
specific language (and diagrams, woohoo!) I've also thought about the consensus
problem in terms of the DAG, but I will use the term "agreement" for reasons
explained below:

Using the terminology from the OldBlue paper, each party can additionally keep
a Map from ProcId, Frontier (equivalent to "branch heads" in my other thread).
Whenever they receive a message from ProcId with parents F, they can update
that ProcId's Frontier to F.

Periodically, one can broadcast helper empty "Frontier" messages to tell other
people about your current view. This can be a soft hint, and so doesn't need to
be added to the DAG. If anyone thinks someone else's Frontier is too old, they
can request that other ProcId to broadcast one of these messages.

In certain cases it would be useful to know what everyone else knows. Alice
wants to know that everyone has seen M, which might be her Frontier. She issues
a "verify" message asking "have you seen M?". Everyone else then sends helper
messages on top of this. Once Alice receives all of these, she knows that
everyone else has seen M. Note that, a "verify" message does not need to be
committed on top of, since it is private-use only by Alice; the conversation
can proceed on top of M instead.

Note that this only works for certain facts. If Alice were to try to get
consensus on "what is your Frontier", I don't think we can do this in a
satisfactory way, since people's Frontiers might change over time. (Perhaps you
could do it by forcing people not to talk at the same time though.) This also
doesn't work for the case of the Byzantine General's Problem of trying to reach
an agreement "let's attack at time T", because T is unknown to start with.

We can define "agreement" on a fact F (that satisfies the above caveat), as
"everyone knows that everyone knows F". (I'm pretty sure 2 levels is enough,
but please correct me if I'm wrong.) This does not have to result in a
quadratic number of messages - you can issue a single response that answers
multiple "verify" requests, so a minimum of 2n messages are needed under good
network conditions. Then, to enshrine this agreement, anyone can commit any
single message that contains all of the 2nd-level responses as parents. In
other words, that single message has all pairs (p's verify, q's response) as
2-hop paths from it. Once this message occurs, everyone knows that everyone
knows F.

Note - I specifically don't use "consensus" as that has connotations of the
Byzantine problem where multiple parties are trying to reach a *future*
potential agreement, not establish *past* knowledge.

We can use "agreement" to extend the OldBlue protocol, for example to support
proper leaving. If Alice wants to leave, all she cares about is that other
people have seen her Frontier. After Alice leaves, all other people care about
is "agreement" that Alice has left. So a leaving protocol might proceed as follows:

1. Alice issues a "verify" message on her Frontier.
2. Other people respond. Once they have, she issues a "leave" message on top of
all of these responses, and leaves unconditionally.
3. Then, the other parties try to reach "agreement" on this "leave" message.
4a. If just one good process has seen the leave message, it will eventually be
propagated to everyone else through LostMsg requests (if not then that's an
attack, and we detect that via other mechanisms)
4b. If no-one has seen the leave message, then we might expire Alice out of the
conversation after we don't see helper messages from her for some time.
5. The remaining processes may then start a new conversation, with a key that
Alice doesn't know.

Note that while this is going on, the conversation could have been proceeding
in parallel on top of Frontier, in which case messages would be sent to Alice,
and people should assume that Alice can read it. Any new message after Alice
leaves, can point to these messages as parents for continuity, as well as the
agreement message. This would mean "I saw this message that I think Alice saw
too, but I think she has left now".

Sorry for the long post, but I am very excited about this idea. :)

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