We now describe the STRmerge protocol for two groups. (A more general protocol for merging larger number of groups is a straight-forward extension.) We assume that, as in the case of join, the communication system simultaneously notifies all group members (in both groups) about the merge event. Moreover, reliable group communication toolkits typically include a list of all members that are about to merge in the merge notification. More specifically, we require that each member be able to distinguish between the group it was in from the group that it is merging with. This assumption is not unreasonable, e.g, it is satisfied in SPREAD [AAH00].
It is natural to merge the smaller group onto the larger one, i.e., to place a smaller tree directly on top of the larger one. If the two trees are of the same size, we can use an unambiguous ordering to decide which group joins which. (For example, compare the identifiers of the respective sponsors.) Consequently, the lowest-numbered leaf of the smaller tree becomes the right child of a new intermediate node. The left child of the new intermediate node is the root of the larger tree. Since the respective trees are known a priori (before the key management starts), all nodes can construct the new key tree before receiving or computing any cryptographic information.
In the first round of the merge protocol, the two sponsors(topmost members of each group) exchange their respective key trees containing all blinded keys. The highest-numbered member of the larger tree becomes the sponsorof the second round in the merge protocol. Using the blinded session randoms of the other group, this sponsorcomputes every (key, blinded key) pair upto the intermediate node just below the root node. It then broadcasts the key tree with the blinded keys and blinded session randoms to the other members. All members now have the complete set of blinded keys, which allows them to compute the new group key. In any case, the merge protocol runs in two communication rounds.