[messaging] Matrix.org: Decentralized group chat

[Jeff Burdges]

I haven’t looked up the IBLT stuff in bitcoin, but this sounds like exactly what the GNU Name System does too.  I suppose GNS records are state-based CRDTs although that’s not specifically mentioned anywhere.  I can find documentation in those papers too if you wish.  



On 10 Mar 2015, at 14:42, Natanael <natanael.l at gmail.com> wrote:

> 
> 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.
> 
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging