[messaging] Matrix.org: Decentralized group chat

[Natanael]

Den 10 mar 2015 09:49 skrev "Ximin Luo" <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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150310/ffacd73e/attachment.html>