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?
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
R is a large (128 bit) random number. An attacker can't check a guess for the value
V without knowing
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.