[messaging] Matrix.org: Decentralized group chat

[Ximin Luo]

On 10/03/15 15:13, Natanael wrote:
> 
> Den 10 mar 2015 14:52 skrev "Ximin Luo" <infinity0 at pwned.gg <mailto:infinity0 at pwned.gg>>:
>>
>> On 10/03/15 14:42, Natanael wrote:
>> >
>> > Den 10 mar 2015 09:49 skrev "Ximin Luo" <infinity0 at pwned.gg <mailto:infinity0 at pwned.gg> <mailto:infinity0 at pwned.gg <mailto:infinity0 at pwned.gg>>>:
>> >> Has there been any research on merging when only *partial* history is available, even when different users have different subsets of the history?
>> >
>> > See IBLT (Invertible Bloom filter Lookup Tables), being implemented for communicating between Bitcoin nodes. The basic idea - if you know that all pending transactions you hold are valid, you don't need to verify them again OR receive them when a block including them is created.
>> >
>> > So to save bandwidth, you need to compare your set of transactions with that of the node you get the block from. And all you need is data the size of the diff between your and their transaction set.
>> >
>> > So one IBLT blob equal to or greater in size than the difference between your locally known transactions and those that are new in the block allows you to reconstruct the block.
>> >
>> > This is probably the most bandwidth efficient set merging algorithm possible (you probably have a magic compression algorithm if you can do better).
>> >
>> > If you can accurately estimate how large the difference will be between the sets held by two nodes, you can create an IBLT blob that allows the other node to reconstruct what you have that they miss.
>> >
>>
>> Ah, I should have been more clear - in Bitcoin, git, CT, and pretty much any other system I can think of that has strong ordering, all events are authorised to be seen by everyone. So I guess that even with IBLT, you still need to have seen the old history in the past, even if you don't need to store it. Other designs for bitcoin clients delegate the storing of old history to trusted 3rd parties, and then you (the client) lose some confidence in the security (freshness, consistency, authenticity) of the head of the chain.
>>
>> However, with a private group chat, incoming new members are *not allowed* to see old history. Yet we would still like them to be able to authenticate *for themselves, without trusting anyone else* that merges are carried out correctly, and be able to do merges themselves correctly.
>>
>> Ximin
> 
> Merge *what*? I think the biggest problem here is definitions.
> 

Merge the unordered set of members. 

In the following diagrams, the node labels (e.g. "bd") represent the set of members ("b", "d") at a given message/node/event. Someone wants to merge the blue nodes, which are the same message in both diagrams. Black edges are 1-parent messages, grey edges represent merge messages that don't include a further membership operation. (If it is unrealistic to imagine membership operations taking only one event to complete, then instead imagine extra messages in between the nodes.)

>From b's point of view, they have full visibility of the history, and can execute the merge as normal:

https://people.torproject.org/~infinity0/res/mcrypt/partial-vis-1.png [1]

But when d executes the merge, they have an incomplete view of history, giving a different result:

https://people.torproject.org/~infinity0/res/mcrypt/partial-vis-0.png [0]

The problem is to resolve this difference, somehow. I suspect it's impossible in the general case; the "solution" I had been playing with is (roughly) to detect "impossible" conditions and wait until it is possible.

I agree with the rest of what you said, and have implemented it in a prototype.

X

[1] partial-vis-1.dot
rankdir=BT;
node [style="filled"];

O [label="b"];
A [label="abc"];
A1 [label="ab"];
A2 [label="bc"];
B [label="bd"];
C [label="abd",fillcolor="#6666ff"];
D [label="bcd",fillcolor="#6666ff"];
X [label="bd",fillcolor="#66ff66"];
A -> O [label="+ac"];
B -> O [label="+d"];
A1 -> A [label="-c"];
A2 -> A [label="-a"];
C -> B [color="#666666"];
D -> B [color="#666666"];
C -> A1 [color="#666666"];
D -> A2 [color="#666666"];
X -> C [color="#666666"];
X -> D [color="#666666"];

[0] partial-vis-0.dot
rankdir=BT;
node [style="filled"];

B0 [label="bd"];
C0 [label="abd",fillcolor="#6666ff"];
D0 [label="bcd",fillcolor="#6666ff"];
X0 [label="abcd",fillcolor="#66ff66"];
C0 -> B0 [label="+a"];
D0 -> B0 [label="+c"];
X0 -> C0 [color="#666666"];
X0 -> D0 [color="#666666"];

(both from https://raw.githubusercontent.com/infinity0/msg-notes/master/causal/05-visibility.rst but it is horrendously incomplete at the time of writing)

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git