[messaging] Matrix.org: Decentralized group chat

[Ximin Luo]

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>>:
>> 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

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