Den 10 mar 2015 14:52 skrev "Ximin Luo" <<a href="mailto:infinity0@pwned.gg">infinity0@pwned.gg</a>>: > > On 10/03/15 14:42, Natanael wrote: > > > > Den 10 mar 2015 09:49 skrev "Ximin Luo" <<a href="mailto:infinity0@pwned.gg">infinity0@pwned.gg</a> <mailto:<a href="mailto:infinity0@pwned.gg">infinity0@pwned.gg</a>>>: > >> 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. And I suspect we're diving down into MPC land if we want to solve that problem "perfectly" (zero ambiguity on ordering for all members regardless of when they joined the chat and regardless of network lag variance). My preference, like previously explained (although I still haven't gotten around to writing up the full approach I'd like to see) is to have each message reference (and this acknowledge) the previous not yet acknowledged ones by hash. As for the UX, messages show a spinning "loading circle" until all chat participants whose status you care about have acknowledged it OR 30 seconds have passed, whichever comes first. After that you get a flag saying some participant have yet to acknowledge receipt. You can mark a message and see which messages highlighted that the sender had already seen when he sent it (optionally show which order). It makes no sense to automatically reorder after the fact. You won't get all participants to re-read and see if it changes the meaning of anything. It might even change it the wrong way if the majority of the network received the messages out of order. It makes more sense to manually check the individual order seen by participants you care about. So by default you just see things in the order they come. To simplify this for usage in discussions where order matters, you could highlight which messages you explicitly want to reference. Everybody would get an icon on that message of yours allowing them to see the messages reordered and highlighted the way the sender wanted. Users just arriving will know there's messages they haven't seen and which nobody wants to relay to them. Everybody else will know what the newcomer in turn have and (probably, unless it gets quoted in another channel) haven't seen when he replies (if they chose to highlight his "ack history", the full list of message acknowledgments he have made that they have seen). You could also mark a message as important, telling your client to notify you about who has acknowledged it and optionally to relay it to specific groups of users (useful for channel announcements).