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 <[email protected]> wrote: > > Den 10 mar 2015 09:49 skrev "Ximin Luo" <[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. > > _______________________________________________ > Messaging mailing list > [email protected] > https://moderncrypto.org/mailman/listinfo/messaging _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
