On Mon, Dec 2, 2013 at 3:43 AM, Ximin Luo <[email protected]> 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 _______________________________________________ OTR-dev mailing list [email protected] http://lists.cypherpunks.ca/mailman/listinfo/otr-dev
