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

[Ximin Luo]

On 02/12/13 02:53, Trevor Perrin wrote:
> On Sat, Nov 30, 2013 at 5:57 PM, Ximin Luo <infinity0 at gmx.com> wrote:
>>
>> (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 was assuming the message stream from any user to another is ordered
> and reliable, so committing to all predecessors is fairly easy, you
> just commit to the most recent message from each user.
> 
> But I agree that committing to DAG predecessors would result in
> smaller messages, so could be advantageous.
> 
> OTOH, piggybacking all predecessors means the recipient learns all
> predecessors for a message upon receipt of that message.  That has
> advantages too:
> 
>  * In an OldBlue-type protocol, the recipient could issue LostMsg
> requests for all missing predecessors right away, instead of needing
> multiple rounds of waiting for lost messages to arrive before
> discovering more predecessors.
> 

Multiple rounds could be alleviated without resorting to "all previous
messages", if they communicate their own Frontier in the LostMsg message. Then,
people handling this LostMsg can infer that the grandparent(s) are also Lost,
and retransmit those too.

For example, say this is the transcript:

1<--2---3---4---5---9
             \
              +-6---7---8

If A is missing {6, 7} (and it doesn't know about 6), it can send a LostMsg(7,
Frontier=(9)), in which case someone who has the full transcript can infer that
A is also missing 6, and retransmit that at the same time, without needing an
explicit request from A.

A generalised algorithm for a responder, would be to infer the Delivered
subgraph (for the requester of the LostMsg) from the transitive ancestors of
Frontier. Then you can calculative the transitive ancestors of the LostMsg id,
that are *not* in Delivered. (I think this is possible without needing to
calculate *all* the ids in Delivered.)

If the responder itself has LostMsgs, then there are some further corner cases,
but you could still do a best-effort inference of lost non-direct ancestors.

(This also does not allow the UI improvement you mentioned below, since it is
up to other people to infer these lost ancestors, not Alice herself.)

>  * In a simpler "consensus-check" protocol, if the "timeliness" check
> fails on a message's predecessor, the recipient has fuller information
> on the security fault.
> 
> For example:  Suppose that we're only piggybacking DAG predecessors,
> and A receives a message from B whose DAG predecessor is a message
> from C.  If the C message doesn't arrive within a time threshold, A's
> client could display:
>    "ERROR: messages from C are not arriving in time".
> 
> But the C message might have other predecessors that may (or may not)
> have arrived.  Yet A doesn't know about them!  If all predecessors
> were piggybacked, A could display a more accurate message, e.g.:
>    "ERROR: messages from C and D are not arriving in time".
> 
> 
> So this seems like a trade-off, one approach or the other may make
> sense in different situations.
> 
> Anyways, you wrote a lot else!, I'll try to look at some of it later...
> 

I'll write these up into proper notes too. :)

-- 
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/20131202/3da0405b/attachment.pgp>