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

[Ximin Luo]

On 01/12/13 01:57, Ximin Luo wrote:
> 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.
> 

Actually, we can short-cut this in even more ways. If the fact is "have you
seen message M", then we don't need to issue a "verify" request to anyone who
has already committed on top of M - this is where the Map from ProcId to
Frontier above comes in handy.

Secondly, we don't need to have all pairs of (p's verify, q's response). Alice
only needs all pairs of (her verify, q's response). (They are received
privately anyway, so my original claim doesn't even make sense.) Then she
broadcasts a single "acknowledge" message whose parents are all q's responses.
If other people receive this ack before they receive all of *their* responses,
they don't need to bother waiting for those responses. So, we will have 1 to n
possible acks, which eventually everyone will see, and the branches will merge
together.

Note! There is no "turtles all the way down" here. We are not trying to enforce
that "A knows everyone is in agreement on F" (for all A)[*]. We are only trying
to enforce that "A knows that everyone knows F" (for all A).

[*] or equivalently "there is agreement on (there is agreement on 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".
> 

It would be more correct to treat those messages (on top of Frontier, but not
on top of the "leave" message) as "they were sent to Alice, but she may not
have read them".

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