1
$\begingroup$

Merkle trees can be used for vector commitment scheme. In particular given two sequences S, S' with the same elements in the same order the merkle root for S will be the same as the one for S'. What if I need to append to S and S' the same elements over time but they may differ in ordering? Is there any specific commitment scheme best suited for this scenario?

$\endgroup$
0
$\begingroup$

The point of a commitment scheme is that the commitment doesn't reveal what has been comitted to until the prover releases some secret information. For hash based shemes generally the comitment is C=H(R+V) where R is a large (128 bit) random number. An attacker can't check a guess for the value V without knowing R.

For a Merkle tree vector commitment scheme, leaves in the Merkle tree would be commitments on the values. Each leaf in the tree is calculated as leaf[i]=Ci=H(Ri+Vi). A commitment for [A,B,C,D,A,B,C,D] would use different random Ri values for each leaf. Despite the values in the left and right sub-trees being identical ([A,B,C,D]) the leaf values and resulting subtrees are different.

There's optimizations that can be made in the implementation, Appending values to the list, requires only adding a new leaf to the merkle tree for example. Less obviously, the Ri values can be constructed using a binary tree to reduce the data size associated with the Ri sequence when revealing a slice of the value array.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.