Postscript document

Protocol Unification

 

Although described separately in the preceding sections, the four STR operations: join, leave, merge and partition, actually represent different expression of a single protocol. We justify this claim with an informal argument below.

Obviously, join and leave are special cases of merge and partition, respectively. It is less clear that merge and partition can be collapsed into a single protocol, because in either case, the key tree changes and the remaining group members lack some number (sometimes none) of blinded keys or blinded session randoms which prevents them from computing the new root key. When a partition occurs, the remaining members reconstruct the tree where some blinded keys are missing. In case of a merge, a shorter tree $A$ is merged into a taller tree $B$. Any member in $B$ now can compute the group key since it knows blinded session random of any member in $A$. The deepest member in $A$ also can compute the group key since it knows the blinded session random of any other member in $A$ and blinded group key of $B$. Using the broadcast message any member now can compute the new group key.

We established that both partition and merge initially result in a new key tree with a number of missing blinded keys. In case of merge, the missing blinded keys can be distributed in two rounds. This is because a sponsorin both of $A$ and $B$ broadcasts its own subtree including all blinded keys. Any member in a given subtree can compute the new root key after receiving both broadcasts. The case of partition is very similar except that the missing blinded keys and the new group key can be distributed in one round.

This apparent similarity between partition and merge allows us to lump the protocols stemming from all membership events into a single, unified protocol. The following figure shows the pseudocode.

The incentive for this is threefold. First, unification allows us to simplify the implementation and minimize its size. Second, the overall security and correctness are easier to demonstrate with a single protocol. Third, we can now claim that (with a slight modification) the STRprotocol is self-stabilizing and fault-tolerant as discussed below.