Key tree

Overview

Describe the key methods of creating a group tree, updating keys, adding members, and removing members with examples.

Preliminaries

Members in a group are organized (by an admin) in a left-balanced binary tree. Members are only at the leaf level. Each node in the tree is a tuple (priv_key, pub_key). We assume a DeriveKeyPair function that generates a key pair from a secret input.

priv_key, pub_key = DeriveKeyPair(secret)

Invariants

1. All group members know the tree structure and public keys of all nodes in the tree.
2. Each member knows the private keys of all nodes on its path to the root. Note: the admin may briefly know the private keys of leaf nodes and internal nodes.

Algorithms

Create:

Given a list of member IDs, the admin invokes the create method to construct a binary tree where the leaf node is derived by applying the DKP function on secret`` = DH(admin_priv_key, member_pub_key)`. Here is an example of group creation with four members.

1. At the leaf level, the admin runs DH with their private key and the member's long-term public key.
2. The secret of the parent P of two sibling nodes X, Y equals to DH(pub_X, priv_Y) or equivalently DH(priv_X, pub_Y). This is then used to derive key pair for the parent node.

The following shows the creation of a key tree among four participants A, B, C, and D. The group key (used as a symmetric key for group messages) is the root private key derived from DH: priv_AB, pub_CD.

graph BT;
    A(priv_A, pub_A, DH: admin, lt_pub_A) 
    B(priv_B, pub_B, DH: admin, lt_pub_B)
    C(priv_B, pub_B, DH: admin, lt_pub_C)
    D(priv_D, pub_D, DH: admin, lt_pub_D)
    E(priv_AB, pub_AB, DH: priv_A, pub_B)
    A-->E
    B-->E
    F(priv_CD, pub_CD, DH: priv_C, pub_D)
    C-->F
    D-->F
    G(priv_ABCD, pub_ABCD, DH: priv_AB, pub_CD)
    E-->G
    F-->G

Loading

Propose

A proposal can be one of three types: Update, Add, or Remove.

Update

The update is the simplest type of proposal. Here, a participant wishes to update their keys. To create such a proposal, the participant first updates their leaf node. The participant then recursively computes the updated public and private keys of all nodes on the path to the root. Finally, the proposal object contains A) participant_id and leaf position B) Updated public keys on the path

Add

The add proposal simply contains the lt_pub_key of the participant. Please note that this is only a request and the changes are reflected upon committing the proposals.

Remove

The remove proposal simply contains the position of the node that needs to be removed from the tree. Similar to other types of proposals this change is not reflected until the commit method is invoked by the admin.

Commit

In an asynchronous group, the proposals sent by various group members happen concurrently. The role of a committer is to batch these proposal requests and generate a control message that the participants can use to derive the next group secret. In this sense, the role of a committer is similar to that of an ordering service/miner in a consensus protocol.

More concretely, the committer takes a list of proposals, "applies" the changes from the individual proposals, and creates an aggregate control message.

Addition

In case of an add proposal, the committer performs a round of DH to generate the initial pub_key and priv_key pairs for the participant. The committer then adds this node to the tree, similar to the initial creation step.

Deletion

In case of a delete proposal, the committer generates an ephemeral key pair for the removed participant and performs an update. The committer then deletes the corresponding private key. An optimization for the committer is to reuse leaves of deleted participants for the new participants.

Update

For any node (_, A) where a proposal updates the public key to A', the committer updates the public key to A * A'.

Control message

Finally, the committer generates a single control message that includes the delta between the state of the tree before and after the update. The control message object contains A) an Updated participant list and B) the Updated public keys.

Process

The input for the process method is a control message. This is run by all the group participants to compute the private key for the next epoch. First, the tree structure along with the updated public keys are retrieved from the control message. A participant computes the updated root private key starting at their leaf node.

Say the previous state is

graph BT;
    A(priv_A, pub_A) 
    B(_, pub_B)
    P(priv_AB, pub_AB)
    A-->P;
    B-->P;

Loading

and A is on the direct path and B is the sibling of A. _ represents that the participant doesn't know the private key of the sibling node. Now, one of the following three cases happened

Both A and B have updated public keys

The committer would have updated the public keys as

graph BT;
    A(_, pub_A')
    B(_, pub_B')
    P(_, pub_AB * pub_A'B * pub_B'A)
    A-->P;
    B-->P;

Loading

The participant can derive the private key of P as priv_ab + DKP(DH(A', B)) + DKP(DH(A, B')). It's easy to see that the keys are compatible.

Only the public key of A is updated

Here, the participant has already computed this step when creating the proposal

Only the public key of B is updated

The committer would have updated the public of parent node P as

graph BT;
    A(_, pub_A)
    B(_, pub_B')
    P(_, pub_AB * pub_AB')
    A-->P;
    B-->P;

Loading

The participant derives the private key of P as priv_ab + DKP(DH(A, B')).

Both A and B have no changes

In this case, the committer would not have updated the public key of P. So, the participant simply goes one step up.

Key

The key method simply returns the private key of the root node

Policy

For the committer, policy determines if a given proposal is well-formed and has the expected signatures. In case of an update, the proposal must be signed with the previous private key. In addition, a zero-knowledge proof of private key is required. In case of an add/delete, the committer includes the IDs of the participants that are added/deleted.