On 10/03/15 15:13, Natanael wrote:
>
> Den 10 mar 2015 14:52 skrev "Ximin Luo" <[email protected]
> <mailto:[email protected]>>:
>>
>> On 10/03/15 14:42, Natanael wrote:
>> >
>> > Den 10 mar 2015 09:49 skrev "Ximin Luo" <[email protected]
>> > <mailto:[email protected]> <mailto:[email protected]
>> > <mailto:[email protected]>>>:
>> >> 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
_______________________________________________
Messaging mailing list
[email protected]
https://moderncrypto.org/mailman/listinfo/messaging
