[messaging] Minimal requirements for group chat

[Michael Rogers]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 17/04/14 17:59, Kurt Roeckx wrote:
> One way I think this can work is that the master is only 
> responsible for handing out ids.  That is, someone that wants to 
> send a message first asks the master and id.  Nobody else can get 
> an id until that message has been commited (or rolled back).
> 
> The ids should always be in sequence, no id can be skipped, and the
> id would be part of the signed data in the message.
> 
> I think then you should have to make sure that all members confirm 
> that they saw the same message.

If everyone has to check that everyone else saw the same message then
I'm not sure we gain anything by using a master - the communication
cost is O(n^2), the same as for a multi-master protocol. But I think
your idea of dividing each round into a proposal phase and a
comparison phase could fix the problems with the multi-master protocol
I suggested before.

Here's a sketch of a new multi-master protocol. As before, the group
membership is fixed and known to all members, and messages are
committed to an append-only log. This time I've slept before posting. ;-)

To propose a message m for round i, a member sends ("propose", i,
hash(m)) to everyone. A member who doesn't have a message to propose
sends the first proposal she receives to everyone. Each member records
the proposal received from each other member. If a member receives
more than one proposal from anyone she sends ("error") to everyone and
the conversation ends.

Once a member has received proposals from every other member, if she
received the same proposal from a majority of members then she sends
("elect", i, hash(m)) to everyone. If she proposed the elected
message, she also sends ("message", i, m) to everyone. If she didn't
receive the same proposal from a majority of members then she sends
("tie", i) to everyone.

If a member receives the same result from every other member as the
result she sent, she commits the result to the log and displays the
elected message, if any. Otherwise she sends ("error") to everyone and
the conversation ends.

A message that was not elected may be re-proposed in the next round.

Dishonest members can send different proposals to different members in
order to convince them that different messages were elected. But the
attack will be detected because all members compare their results
before committing.

The communication cost is 2n(n-1) transmissions per round.

Cheers,
Michael
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQEcBAEBCAAGBQJTUSX9AAoJEBEET9GfxSfMu0EH/2CPp7iDSrqfpnI9BqN8mqDB
tpMhuowPuE9lwWHyeDjkpanE92sIz3zZ/sXwzSrrcKSmbsUgnxMM8c+6+5xZwfR0
NWGpADclOMiInXkGnnQCzMZad7+Z4r9Lu8SqiuAqAdM5g4GD64zm7GVuUYCf81NV
Q2epgsaDb524fyH4UfN94jr//lj47yv+MsDHrClBJ7/XCRJ/PCKKsZDCcYubMLaF
jmR//A5CjG/CjPMjzpLoUKLrDrh//pgUtICQyCKyClAYvN1A+Kgoa34RdUSYLwPX
i/iA3a89OwgVns/RfPWGJI0C6lZBeCPAcv53AlR8ERaV9bI8IOhDTs0A26KgzfM=
=FikT
-----END PGP SIGNATURE-----