<div dir="ltr">Either I'm missing some common background, or there's an unaddressed ambiguity in "message ordering" in this thread:<div><br></div><div>Chat UIs typically present a linear sequence of messages. This presents a distinct problem if we assume an underlying DAG agreement protocol, because DAGs are not linear. Consider a simple DAG with arrows pointing to predecessor messages:</div>
<div><br></div><div>B -> A <- C</div><div><br></div><div>There are two ways to "squash" this into a linear order: [A, B, C], or [A, C, B]. This ambiguity is crucial for human interaction; imagine A is "Vanilla icecream is the best!", and B is "Are you planning to do something illegal?" and C is "Yes, without a doubt!"</div>
<div><br></div><div>Suppose we try to ensure every participant sees a *consistent linear serialization* of the DAG order. We could do this, for example, by sorting branches such as {B, C} consistently such as by the lexical sorting of the message hashes. When we consider time, this leads to a concerning UI behavior: over time, new messages may not only be appended to the linearization of messages, but new messages may also be inserted. For example, if B sorts consistently before C, then a user may at one time see [A, C], then later [A, B, C].</div>
<div><br></div><div>I believe all of these issues are already present in a two party chat, regardless of the underlying protocols ordering or reliability guarantees. (For example, XMPP would have this problem, given TCP without packet loss and without malice once there are multiple federated servers interacting, I believe.) Suppose Alice sends message A, and Bob receives A. Now Alice composes and sends B before receiving C while Bob composes and sends C before receiving B. The "typical" chat UI will show Alice [A, B] and Bob [A, C] at various times, but later both clients will show all three messages in some order.</div>
<div><br></div><div><br></div><div>I'm all on board for decentralized protocols that arrive at agreements about DAG structures, but let's keep an eye on the UX implications. Perhaps a better way to express my concern is to imagine a perfect DAG-order agreement protocol, then imagine an attacker which can influence only how the DAG is serialized in the UI, and they cannot alter message contents or the agreed partial ordering, only the ambiguous parts of the ordering. What attacks can they accomplish?</div>
<div><br></div><div>Maybe a good chat client would show the DAG structure directly, which I hope users could understand and which would remove the linearization requirement altogether which seems full of unavoidable trade-offs. Also, a good client must show messages which are not under agreement yet - at least the messages the user has entered - in some sort of pending state.</div>
<div><br></div><div>Regards,</div><div>Nathan</div><div><br></div><div>ps: This isn't just abstract nit-picking. I once had a multi-hour emotional altercation with a significant other and we later realized it was due to our two respective SMS clients showing different message orders and that one of us was responding to one question whereas the other believed the response was for a different question.</div>
<div><br></div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Dec 5, 2013 at 12:59 PM, Ximin Luo <span dir="ltr"><<a href="mailto:infinity0@gmx.com" target="_blank">infinity0@gmx.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On 03/12/13 18:12, George Kadianakis wrote:<br>
>> On Mon, Dec 2, 2013 at 3:43 AM, Ximin Luo <infinity0 at <a href="http://gmx.com" target="_blank">gmx.com</a>> wrote:<br>
>>> On 02/12/13 02:53, Trevor Perrin wrote:<br>
>> [...]<br>
>>>><br>
>>>> But I agree that committing to DAG predecessors would result in<br>
>>>> smaller messages, so could be advantageous.<br>
>>>><br>
>>>> OTOH, piggybacking all predecessors means the recipient learns<br>
>>>> all<br>
>>>> predecessors for a message upon receipt of that message. That<br>
>>>> has<br>
>>>> advantages too:<br>
>>>><br>
>>>> * In an OldBlue-type protocol, the recipient could issue LostMsg<br>
>>>> requests for all missing predecessors right away, instead of<br>
>>>> needing<br>
>>>> multiple rounds of waiting for lost messages to arrive before<br>
>>>> discovering more predecessors.<br>
>>>><br>
>>><br>
>>> Multiple rounds could be alleviated without resorting to "all<br>
>>> previous<br>
>>> messages", if they communicate their own Frontier in the LostMsg<br>
>>> message. Then,<br>
>>> people handling this LostMsg can infer that the grandparent(s) are<br>
>>> also Lost,<br>
>>> and retransmit those too.<br>
>><br>
>> That makes sense. I'll admit I'm not super interested in<br>
>> LostMsg/Retransmit algorithms, as we've got existing chat/messaging<br>
>> protocols that do an adequate job with reliability (I think?)<br>
>><br>
><br>
> I'm also not super interested in LostMsg/Retransmit algrorithms. That<br>
> said, I don't think that the current major chat protocols provide<br>
> reliability (when the server is adversarial or when a user suddenly<br>
> disconnects).<br>
><br>
> For example, I don't think that XMPP provides reliability or<br>
> in-order-delivery on its own (see XEP-0198 and XEP-0184). However,<br>
> because it's used over TCP, its streams are both reliable and<br>
> ordered. Still, communication between Alice and Bob over XMPP actually<br>
> involves two streams: Alice <-> Server and Server <-> Bob. While each<br>
> of those streams is reliable and ordered, nothing tells us that the<br>
> communication channel Alice <-> Bob is reliable or ordered if we<br>
> consider the server as an adversary (i.e. the server can reorder or<br>
> drop Alice's packets before forwarding them to Bob).<br>
><br>
> FWIW, based on <a href="https://otr.cypherpunks.ca/Protocol-v3-4.0.0.html" target="_blank">https://otr.cypherpunks.ca/Protocol-v3-4.0.0.html</a>, OTR<br>
> itself "assumes a network model which provides in-order delivery of<br>
> messages, but that some messages may not get delivered at all (for<br>
> example, if the user disconnects).". I think OTR provides its own<br>
> reliability by using NAKs and doing retransmissions (at least<br>
> according to section 5.1 of the otr-wpes.pdf paper).<br>
><br>
> Slightly off-topic, but lately when I'm thinking of the network model<br>
> of a secure multiparty chat, I've found it helpful to consider a<br>
> multiparty chat over a centralized chat protocol (like IRC or XMPP,<br>
> where clients send messages to the server and the server broadcasts<br>
> them to the other clients). It seems helpful for two reasons:<br>
> a) The server, in centralized protocols, is a powerful network<br>
> adversary that can easily reorder, delay or drop messages (it's like<br>
> the Global Active Adversary for the distributed case). Similar<br>
> attacks can also be performed by network links in a decentralized P2P<br>
> model, but thinking of the centralized case seems easier.<br>
> b) In the same protocol-agnostic fashion as OTR, it seems natural to<br>
> me that the first instances of secure multiparty chats will use the<br>
> popular chat protocols that are currently available. This probably<br>
> means XMPP MUCs and IRC, which are both centralized.<br>
><br>
> What I'm trying to say, is that even though providing reliability in a<br>
> multiparty chat protocol doesn't seem like a huge priority, a robust<br>
> such protocol should have a way to ensure reliable end-to-end delivery<br>
> of its messages.<br>
><br>
<br>
</div></div>Interesting that OTR assumes in-order delivery. If we assume a network-level adversary or untrusted central service, it could definitely deliver messages out-of-order. I think the DAG model already protects against this, though.<br>
<div class="im"><br>
>> You've talked about periodically broadcasting empty messages. I<br>
>> think<br>
>> that's a good idea, particularly if parties can expect that of each<br>
>> other, as it allows checking for timeliness and liveness of the<br>
>> whole<br>
>> group. Tossing that in, here's my latest:<br>
>><br>
>> --<br>
>><br>
>> Each Message contains:<br>
>> - PREDECESSOR list containing the most-recently received message<br>
>> number from each other participant (equivalently: the number of<br>
>> messages received from each other Participant)<br>
>> - HASH over the predecessor messages (including the sender's<br>
>> previous message)<br>
>><br>
<br>
</div>I still think hashing over all participants is redundant. You only need the direct predecessors, like in the git history DAG. From this, anyone can transitively infer your version of the PREDECESSOR list. A less dense DAG is also easier to analyse. We can run with your version for now, though.<br>
<div class="im"><br>
>> A Message's HASH can be verified once all predecessors have arrived.<br>
>><br>
>> Each Participant maintains:<br>
>> - An UNVERIFIED pool of received messages whose hashes have not yet<br>
>> been verified, and an expiration time for each.<br>
>> - Lists of RECEIVED messages from each Participant. The HEAD<br>
>> message<br>
>> in each list is the latest message from that Participant, and has an<br>
>> expiration. The tail message in each list is the oldest message<br>
>> that<br>
>> is referred to by an UNVERIFIED message (older messages don't need<br>
>> to<br>
>> be kept around).<br>
<br>
</div>I'm not sure this possible in general. If the unverified message has multiple chains of lost messages preceding it, you don't know which "oldest message" is referred to. Using the example from my last email:<br>
<br>
1<--2---3---4---5---9<br>
\<br>
+-6---7---8<br>
<br>
(This would occur when, e.g. whoever sent 6,7,8 did not yet receive 5,9. This might be multiple people. Note that this is using the sparse DAG; you can fill in extra pointers for a dense DAG.)<br>
<br>
Say Alice sees all messages except 6. She knows about 6 itself, because she has 7 which points to it. However, she does not know 6's own precedessors, so she must keep all messages *in case* 6 points to 1.<br>
<br>
With the expiry mechanism, you can toss all messages that *would be expired* if it was the HEAD, though. That might be a better approach rather than discarding things via DAG-based metrics.<br>
<div class="im"><br>
>><br>
>> The expirations associated with UNVERIFIED and HEAD messages are for<br>
>> timeliness checks:<br>
>> * If there's ever an expired UNVERIFIED message, that means you<br>
>> haven't received some predecessor within a reasonable amount of<br>
>> time.<br>
>> * If there's ever an expired HEAD message, that means you haven't<br>
>> heard anything from some party within a reasonable amount of time.<br>
>><br>
>> On receiving a message, do:<br>
>> - Check that the message has newer predecessors than the previous<br>
>> message from this sender<br>
<br>
</div>This is nice. In the sparse form of the DAG, this check would be equivalent to checking that a new message from a sender, say Bob, has their previous message as an ancestor through the DAG. (The same property for other participants follows transitively from this property, so you only need to check the sender. In the dense case, participants can lie about the extra redundant pointers, so we do need to check them.)<br>
<br>
However, this check is only possible if we have already verified all the predecessors, so I think it would be better to do this as part of "verifying". An example:<br>
<br>
1<--2 3<--4<br>
<br>
To simplify things, assume that Bob sends all messages. We receive 2 from Bob, then 4 from Bob, but we haven't received 3 yet. Doing this check here would fail, since we don't know what 3's parents are. Bob could be attacking us with a bogus message, or everything could work out when we later see that 3 has 2 as a parent.<br>
<div class="im"><br>
>> - Add the message to the UNVERIFIED pool and the appropriate<br>
>> RECEIVED<br>
>> list, and set expiration times<br>
>> - If any message in UNVERIFIED can now be verified, do so, and<br>
>> either<br>
>> raise a security fault or delete it from UNVERIFIED<br>
>><br>
>> If you haven't sent a message in X time, send an empty message.<br>
>><br>
>> Thoughts?<br>
>><br>
<br>
</div>Basic gist of it looks good, next we need more detail. I'll think about it as well. :)<br>
<br>
One comment (which might be redundant as I'm not up-to-date with all the contextual literature) is that this reduces scalability. This may or may not be a concern, but this would make e.g. a conversation with 30 people more costly. (But perhaps other parts of the protocol, like the handshake, already make this costly, so we will just restrict ourselves to a "small group".)<br>
<div class="im"><br>
><br>
> I like it. It seems like it would work.<br>
><br>
> (Would be even better if we could sketch a quick proof for its<br>
> soundness too.)<br>
><br>
> Also, IMHO, messages should not be forwarded to the chat client while<br>
> they are in the UNVERIFIED pool. Assuming normal (non-adversarial)<br>
> network operation, receiving message predecessors should be quick and<br>
> users shouldn't even notice the buffering.<br>
><br>
> We can even make some "Large amount of unverified messages" or<br>
> "Impossible to verify messages from participant X for a while"<br>
> warnings that we can forward to the chat application instead.<br>
><br>
> (I'm saying this, because forwarding unverified messages to the client<br>
> with a big fat "UNVERIFIED MESSAGE" warning seems like a recipe for<br>
> disaster. Similar to CA-SSL's "The site's security certificate is not<br>
> trusted" usability/security nightmare.)<br>
><br>
<br>
</div>I'm cool either way. It would also be easier to implement in the way that you say. My main motivation for suggesting the other approach was performance - to show the user *something* rather than having things block on one unreceived message. But maybe this is not important enough to outweigh the other security concerns.<br>
<div class="HOEnZb"><div class="h5"><br>
--<br>
GPG: 4096R/1318EFAC5FBBDBCE<br>
git://<a href="http://github.com/infinity0/pubkeys.git" target="_blank">github.com/infinity0/pubkeys.git</a><br>
<br>
</div></div><br>_______________________________________________<br>
OTR-dev mailing list<br>
<a href="mailto:OTR-dev@lists.cypherpunks.ca">OTR-dev@lists.cypherpunks.ca</a><br>
<a href="http://lists.cypherpunks.ca/mailman/listinfo/otr-dev" target="_blank">http://lists.cypherpunks.ca/mailman/listinfo/otr-dev</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>Nathan Wilcox<br>Least Authoritarian<br>
</div>