Common use of Merge Protocol Clause in Contracts

Merge Protocol. Step 1 : All sponsors Msi in each Tsi – generate new share and compute all [key, bkey] pairs on the key-path of Tsi , ^ i – broadcast updated tree T^si including only bkeys. Msi Ts (BKs∗ ) i=1 Ci Step 2 : Every member – update key tree by adding new trees and new intermediate nodes, – remove all keys and bkeys from leaf node related to the sponsor to the root node. Each Sponsor Mst additionally – compute all [key, bkey] pairs on the key-path until it can proceed, ^ st t – and broadcast updated tree T^st including only bkeys. Mst Ts (BK∗ ) i=1 Ci Step 3 to h (Until a sponsor Msj could compute the group key) : For each sponsor Mst – computes all [key, bkey] pairs on the key-path until it can proceed, ^ st t – and broadcasts updated tree T^st including only bkeys. Mst Ts (BK∗ ) i=1 Ci Step h + 1 : Every member computes the group key using T^s point multiplications. The serial cost assumes parallelization within each proto- col round and presents the greatest cost incurred by any participant in a given round(or protocol). The total cost is simply the sum of all participants’ costs in a given round(or protocol). Table 6 summarizes the communication and computation costs of TGDH and our protocol. The number of current group members, merging groups and leaving members are denoted by n, k and p, respectively. The overhead of protocol depends on the tree height, the balance of the key tree, the location of the joining tree and the leaving nodes. In our analysis, we assume the worst case configuration and list the worst-case cost for TGDH and our protocol. Since we modified TGDH protocol, the number of communication is equals to TGDH except the number of rounds in merge and key length. But our proposed protocol can reduce the number of computation in each event operation because of low height of key tree. The number of pairings and point multiplications for Tree T5 <0,0> <1,0> <1,1> <1,2> <2,0> <2,1> <2,2> <2,3> <2,4> <2,5> <2,6> <2,7> <2,8> M4 M5 M6 M7 M8 M9 ▇▇▇ ▇▇▇ <3,0> <3,1> <3,2> M1 M2 ▇▇ ▇▇▇▇ ▇▇▇ <▇,▇> <1,0> <1,1> <1,2> ▇▇▇ ▇▇▇ ▇▇▇ Tree T5 <0,0> New Intermediate Node <1,1> <1,2> <2,0> <2,1> <2,2> <2,3> <2,4> <2,5> <2,6> <2,7> <2,8> M6 M7 M8 M9 ▇▇▇ ▇▇▇ <3,0> <3,1> <3,2> <3,3> <3,4> <3,5> <3,6> <3,7> M1 M2 M3 M12 M13 M15 M4 M5 Table 6. Communication and Computation Costs Communication Computation Rounds Messages Exponentiations Pairings Multiplications TGDH Join 2 3 3 2 flog2 n¶ 0 0 Merge log2 k +1 2k 3 2 flog2 n¶ 0 0 Partition min(log2 p, h) 2flog2 n¶ 3flog2 n¶ 0 0 Our Protocol Join 2 3 0 flog3 n¶− 1 flog3 n¶ +1 Leave 1 1 0 flog3 n¶− 1 flog3 n¶ +1 Merge log3 k +1 2k 0 flog3 n¶− 1 flog3 n¶ +1 Partition min(log3 p, h) 2flog3 n¶ 0 2flog3 n¶ 2flog3 n¶ our protocol depends on whether there exists the subtree with two member nodes or not. We thus compute the cost of average case.

Merge Protocol. Step Compared to CLIQUES, the main virtue of TGDH is that it is much simpler to merge two or more groups. Multiple join can be processed as follows. The protocol assumes that m members want to join group G1. The m individual members form a TGDH group G2. Then G2 merges with G1. The protocol considers first the merge of two groups. It can be simply extended to the merge of more than two groups, say k > 2, groups by executing the two-group merge k − 1 times. First the two trees are ordered from the highest to lowest, denoted T1 and T2. If they are of the same height, they are ordered according to some other criteria. T2 joins to T1, and the insertion point is determined. If the two trees are of the same height, it joins simply T2 to the root node of T1. Otherwise it first tries to find the rightmost shallowest node where the join would not increase the overall tree height. If no such node exists, the insertion point is the root node. Assume that we have m trees to be merged. They can be ordered from the highest to the lowest: All sponsors T1, · · · , Tm. To perform merge, each tree Ti has its rightmost shallowest leaf node as sponsor Msi . The process is illustrated as follows: 1) Each sponsor Msi in each Tsi – generate new share tree Ti updates its share, computes all keys and compute all [key, bkey] pairs on blinded keys in the key-path of Tsi Ti (including BK(0,0)), ^ i – broadcast broadcasts updated tree T^si Ti including only bkeysall blinded keys. Msi Ts (BKs∗ ) i=1 Ci Step 2 : Every For i = 1, 2, · · · , m. Each member – update additionally, updates the key tree by adding and determinates the new trees and new intermediate nodessponsors Ms1 , – remove · · · , Msm , removes all keys and bkeys from leaf node related to the blinded keys in sponsors’ key-paths. 2) To repeat this step until any sponsor to the root nodecomputes group key. Each Sponsor Mst additionally – compute all [keysponsor Msi with 1 ≤ i ≤ m, bkey] pairs on the key-path until it can proceed, ^ st t – and broadcast updated tree T^st including only bkeys. Mst Ts (BK∗ ) i=1 Ci Step 3 to h (Until a sponsor Msj could compute the group key) : For each sponsor Mst – computes all [keykeys and blinded keys pairs in the key- path as far as possible, bkey] pairs on the key-path until it can proceed, ^ st t – and broadcasts updated tree T^st including only bkeys. Mst Ts (BK∗ with all blinded keys. 3) i=1 Ci Step h + 1 : Every member computes the group key using T^s point multiplications. The serial cost assumes parallelization within each proto- col round and presents the greatest cost incurred by any participant in a given round(or protocol). The total cost is simply the sum of all participants’ costs in a given round(or protocol). Table 6 summarizes the communication and computation costs of TGDH and our protocol. The number of current group members, merging groups and leaving members are denoted by n, k and p, respectively. The overhead of protocol depends on the tree height, the balance of the key tree, the location of the joining tree and the leaving nodes. In our analysis, we assume the worst case configuration and list the worst-case cost for TGDH and our protocol. Since we modified TGDH protocol, the number of communication is equals to TGDH except the number of rounds in merge and key length. But our proposed protocol can reduce the number of computation in each event operation because of low height of new key tree. The number An example of pairings the merge of two groups is given in Figure 2.8. Both sponsors M5 and point multiplications M7 first update their shares respectively. Then M5 computes new K(1,1), BK(1,1), K(0,0), and BK(0,0) in tree T5, and M7 computes K(0,0), and BK(0,0) in tree T7. Both sponsors M5 and M7 broadcast their updated trees with all blinded keys. Each member merges both trees independently, and chooses M2 as the new sponsor. All members then remove all keys and blinded keys in M2’s key-path. M2 additionally updates its share and computes new K(2,1), BK(2,1), K(1,0), BK(1,0), and K(0,0). M2 then broadcasts the updated tree with all blinded keys. Equipped with the broadcast message, M1 computes K(2,0), K(1,0), and K(0,0). M6 and M7 compute K(1,0), and K(0,0). All other members M3, M4, and M5 compute only the new group key K(0,0). Since there is only one sponsor for Tree T5 <0,0> <1,0> <1,1> <1,2> <2,0> <2,1> <2,2> <2,3> <2,4> <2,5> <2,6> <2,7> <2,8> M4 M5 M6 M7 M8 M9 ▇▇▇ ▇▇▇ <3,0> <3,1> <3,2> M1 the merge of two groups, M2 ▇▇ ▇▇▇▇ ▇▇▇ <▇,▇> <1,0> <1,1> <1,2> ▇▇▇ ▇▇▇ ▇▇▇ Tree T5 <0,0> New Intermediate Node <1,1> <1,2> <2,0> <2,1> <2,2> <2,3> <2,4> <2,5> <2,6> <2,7> <2,8> M6 M7 M8 M9 ▇▇▇ ▇▇▇ <3,0> <3,1> <3,2> <3,3> <3,4> <3,5> <3,6> <3,7> M1 M2 M3 M12 M13 M15 M4 M5 Table 6. Communication knows all blinded keys in its co-path so that it is able to compute all keys and Computation Costs Communication Computation Rounds Messages Exponentiations Pairings Multiplications TGDH Join 2 3 3 2 flog2 n¶ 0 0 Merge log2 k +1 2k 3 2 flog2 n¶ 0 0 Partition min(log2 p, h) 2flog2 n¶ 3flog2 n¶ 0 0 Our Protocol Join 2 3 0 flog3 n¶− 1 flog3 n¶ +1 Leave 1 1 0 flog3 n¶− 1 flog3 n¶ +1 Merge log3 k +1 2k 0 flog3 n¶− 1 flog3 n¶ +1 Partition min(log3 p, h) 2flog3 n¶ 0 2flog3 n¶ 2flog3 n¶ our protocol depends on whether there exists the subtree with two member nodes or not. We thus compute the cost of average caseblinded keys in its key-path.