This update operation is how a tree starts in the first place: Each member contributes an initial value to begin with, and each time a member does an update operation it fills out its direct path to the tree. If all members performed this operation there would be a complete tree (though it is possible to get to a complete tree without all doing so).

This tree structure is incredibly powerful because we effectively have a symmetric group key derivable
from each binary subtree in this graph. For instance, if then it is easy enough to
see that they can communicate already by using . More importantly, thanks to the deterministic Key
Encapsulation Method, the public key from the computation can be used by
other nodes to encrypt values for this subgroup without being member to *S'*.

In this fashion, we can now complete the definition for an update operation such that the tree invariant continues holding for the whole tree:

**Definition 5** *TreeKEM Update Operation*

- The updating member computes a new secret value and propagates it up the direct path to the root, recursively computing for each subsequent value recursively.
- For all members that can no longer hash up their direct path to the root, the updating member computes the least number of common ancestors whom if they had the new values would ensure that all group members can reach the root. The algorithm for this computation will be provided later. Once those nodes get the missing value as an encryption to their public KEM key, they can synchronize their view of the tree.
- The updating member computes the KEM of its newly generated node values and posts publicly the public keys of these nodes to all members of the tree, to be used for future updates.

Members receiving information about updates should verify that the update is authenticated from a verified
group member (using a signature scheme), compute similarly which is the common ancestor that they are
part of (which *S'* do they belong to that received the new secret values), use their private key for that subtree
to decrypt the value, and then propagate it up to the root using *H* along its direct path to compute the new
key value for the group.

The problem of "which nodes need to receive encrypted values", or as I wrote earlier, computing "the
least number of common ancestors whom if they had the new values would ensure that all group members
can reach the root" is quite a simple one. Since each node's value is the hash of only one of two children,
then the child that was not used to generate the parent is the one that no longer shares knowledge of the root
key. It is these *non-updated* children that need to be given knowledge of the parent value via an encrypted
ciphertext in order to complete the full tree path to the root node. Therefore, we can identify such nodes
simply by looking at the one and only sibling at each level of the direct path. This of course assumes we
already have a completed tree. Update operations for trees with blank intermediate nodes are less efficient.

9