[messaging] Matrix.org: Decentralized group chat

[Natanael]

Den 10 mar 2015 14:52 skrev "Ximin Luo" <infinity0 at pwned.gg>:
>
> 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

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).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150310/0454f6d2/attachment.html>