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

[Trevor Perrin]

On Mon, Dec 2, 2013 at 3:43 AM, Ximin Luo <infinity0 at gmx.com> wrote:
> On 02/12/13 02:53, Trevor Perrin wrote:
[...]
>>
>> 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.

That makes sense.  I'll admit I'm not super interested in
LostMsg/Retransmit algorithms, as we've got existing chat/messaging
protocols that do an adequate job with reliability (I think?)

You've talked about periodically broadcasting empty messages.  I think
that's a good idea, particularly if parties can expect that of each
other, as it allows checking for timeliness and liveness of the whole
group.  Tossing that in, here's my latest:

--

Each Message contains:
 - PREDECESSOR list containing the most-recently received message
number from each other participant (equivalently: the number of
messages received from each other Participant)
 - HASH over the predecessor messages (including the sender's previous message)

A Message's HASH can be verified once all predecessors have arrived.

Each Participant maintains:
 - An UNVERIFIED pool of received messages whose hashes have not yet
been verified, and an expiration time for each.
 - Lists of RECEIVED messages from each Participant.  The HEAD message
in each list is the latest message from that Participant, and has an
expiration.  The tail message in each list is the oldest message that
is referred to by an UNVERIFIED message (older messages don't need to
be kept around).

The expirations associated with UNVERIFIED and HEAD messages are for
timeliness checks:
 * If there's ever an expired UNVERIFIED message, that means you
haven't received some predecessor within a reasonable amount of time.
 * If there's ever an expired HEAD message, that means you haven't
heard anything from some party within a reasonable amount of time.

On receiving a message, do:
 - Check that the message has newer predecessors than the previous
message from this sender
 - Add the message to the UNVERIFIED pool and the appropriate RECEIVED
list, and set expiration times
 - If any message in UNVERIFIED can now be verified, do so, and either
raise a security fault or delete it from UNVERIFIED

If you haven't sent a message in X time, send an empty message.

Thoughts?


Trevor