You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Sarah Jamie Lewis 71d45ddbc7 Message History Length and Get Latest + Skettch of GroupPeer 6 months ago
model Message History Length and Get Latest + Skettch of GroupPeer 6 months ago
.gitignore Sketch of Constitution Logic 6 months ago Message model 6 months ago
go.mod Sketch of Constitution Logic 6 months ago
go.sum Sketch of Constitution Logic 6 months ago

Hybrid Protocol Sketch

This repository is intended to research and sketch a prototype of functional behavior for a hybrid protocol base for Cwtch.

The goal of the hybrid protocol is to allow the creation and maintenance of a set of generic shared information between a group of people in a way that is robust against reasonable adversaries.

  1. Out Group Adversaries: In closed groups, anyone who has not been invited to the group is labelled as an “Out Group Adversary” - in an ideal implementation they should not be able to learn the existence of the group under any circumstance outside of being explicitly invited to join the group. An out group adversary should not be able to manipulate the transcript between group members nor should they be able to trivially disrupt consensus.

  2. In Group Adversaries: In closed groups (and de-facto in open groups) an In Group Adversary is a member or a set of members within a group. In an ideal implementation they should not be able to disrupt consensus unless such disruption implies that the absolute majority of group members supports such a decision.

We note that in Open Groups the ability to arrive at consensus implies the existence of a absolute numbering of individuals that may not exist in some contexts. In this case all an in-group member can do is spam information to the group and surveil the messages of other members.

In open groups the existence of both spam and surveillance is an open problem and not one we intend to solve.

A Peer

As in Cwtch any individual entity in this system self assigns as ed25519 keypair that is used both for signing message updates and hosting a v3 onion service.

Signatures in this paper refer to properly constructed ed25519 cryptographic signatures.

Forming a Group

All groups start with a constitution which outlines the intrinsic properties of the group. A constitution defines:

  • The initial members of the group
  • The transcript consensus rules (the number of members that must acknowledge an action prior to it being accepted in the official transcript)
  • The group consensus (the set of members that must acknowledge a group action (e.g. adding a new member, rotating the group key) prior to it have an impact on the transcript consensus)
  • The (initially empty) set of signature for all the group members.

The constitution becomes active once all the initial group members have signed it and the constituion becomes the first message of the transcript.

Key Generation

The initial key generation is done out of band by the founder of the group and is transferred to each group member via the group setup protocol.

    "constitution": {...},
    "key": [...]

This sketch places no restriction on how the key is generated (one group member could do it or a set of founding members could engage in a group key generation protocol).


In practice we use libsodum’s authenticated encryption construct for group encryption.

Adding a Message

Every message has the same structure:

  • The authors public key

  • Message Body (padded to MessageSize)

  • A hash of a previous message sent to the group

  • A set of signatures (max length = group size)

    message = peer.CreateMessage(group.Hash(), body) encryptedMessage = group.EncryptMessage(message)

Accepting a Message

Once a message has been authored the author appends it to their own transcript with an acknowledgement from themselves.

ack, inConsensus = group.AcknowledgeMessage(encryptedMessage)

Where ack is a compressed from the message containing:

  • A hash of a previous message sent to the group
  • A set of signatures (max length = group size)

This can be merged with the unencrypted message by the group without issue, as signatures cannot be revoked.

If the message has fewer acknowledgements than necessary for consensus the author asks for an Acknowledgement from a set of n-2 peers (observers).

SelectObservers(peer, message):
    members = group.ListMembers
    members.Remove(peer) // redundant but explicitly called out
    members.Remove( // redundant but explicitly called out
    return random(members, group.threshold - len(message.acknowledgements)

The peer can then poll acknowledgement from the group until the threshold is met.

Acceptance (peer, group, encryptedMessage):
    observers = group.SelectObservers(peer, message)
    for member in observers
        ack = peer.AskForAcknowledgment(member, encryptedMessage) // peer to peer (async)
        _, inConsensus = group.AppendAcknowledgement(ack)
     if inConsensus == false
        Acceptance(peer, group, message)

It is worth noting that this exchange is symmetric and as such if the member receives acknowledgement requests they will incorporate any previous acknowledgment the requesting peer has collected into their own consensus.

The only difference in the two flows occurs when one peer has the message and another peer does not. The compressed acknowledgement does not contain the message and so if a peer does not possess it they must fetch it from another peer. This can be done in-band of the AskForAcknowledgment where a peer will ask for a copy of the message after receiving a request for acknowledgement (and will then subsequently acknowledge it) or out of band during a Sync phase.

This Acceptance process is repeated until the message is in consensus, at which point it is incorporated into the official transcript.

Note: Because multiple messages can be voted on at the same time the order of the message transcript is inherently fuzzy. We don’t care about an absolute order of events - and because of this we must note that is inappropriate to rely on this consensus algorithm for applications that require an absolute order of events (although we can add additional application level checks to strictly order events and reject conflicting entries)

Transcript Checkpoints

Any group member can issue a request for a transcript checkpoint that binds all messages that occurred before it. We define a meta message that identifies itself as a transcript checkpoint and contains a list of all messages that have not been referenced by another message.

The consensus mechanism for this message is the same as for regular messages.

Once this message is included in consensus none of the messages that occurred before it are valid reference points - it is the equivalent of resetting the transcript (and as such it is the perfect point to introduce a key rotation construct)

Rules for Rejection

  1. If a TC is received which doesn’t reference an in-consensus message then the TC must eb rejected by an honest node.
  2. If a TC is received which references a message that is not in consensus (or does not appear to be in consensus) then it should not be accepted until the referenced message is also in consensus.
  3. If a TC is received simultaneously with another message (i.e. there is a consensus competition) then the TC wins and the other message should be rejected from consensus (and recent by an honest peer using the newly derived key (see above))
  4. If two or more members attempt to issue a TC simultaneously then members acknowledge the one with the lowest hash
  5. A member can only publish one valid TC for a single set of messages. If a member publishes duplicate TC in an attempt to hold up consensus in the presence of multiple TC then this is considered malicious behavior and all checkpoints form that member should be rejected.

Key Rotation

Because we have a reliable transcript checkpointing mechanism we can now construct a key rotation scheme with perfect forward secrecy by allowing group members to derive a new key by combining the current key with a hash of the transcript after the checkpointing message.

The above two rules should force honest members to only issue TC after seeking out all possible update paths.