Merkle Tree 的 position binding

vector commitment

prover 有一个数组，这个数组不直接公开，而是通过 vector commitment的形式展示。之后 prover 可以向 verifier 提供第 i 位置的数值及其证明，verifier 可以验证这个数确实就在前述数组第 i 位置。

这个特性称为 position binding。

position binding
Informally, this says that it should be infeasible, for any polynomially bounded adversary having knowledge of pp, to come up with a commitment C and two different valid openings for the same position i.^[1]

事实上，Merkle Tree 同样具备这个特性，prover 提供一个 leaf 的 Merkle Proof 以及这个leaf 的序号，verifOrr 可以验证这个序号的真实性。

Similar to vector commitments [21], Merkle trees provide position binding, which is that a malicious prover cannot open a commitment to two different values at the same position of a committed sequence.^[2]

这利用的原理是根据 sibling 计算得到 parent hash 的时候，sibling拼接时是讲究左右顺序的。

从叶子到 root 的路径中，需要先将2 个 sibling 拼接，对这个拼接后的值计算 hash 得到 parent node 的值。如果拼接顺序错了，那么计算得到的 hash 也是错的。

以下图为例，叶子 H(K) 的 Merkle Proof 包括 H(L), H(IJ), H(MNOP), H(ABCDEFGH)。验证 H(K)是这个 Merkle Tree 的叶子，需要沿着从 H(K)到 Merkle Root 的路径进行 hash 计算。

依次：

1. 将 H(K), H(L)左右拼接，hash 计算得到 H(KL)；
2. 将 H(IJ), H(KL)左右拼接，hash 计算得到 H(IJKL)；
3. 将 H(IJKL)，H(MNOP)左右拼接，hash 计算得到 H(IJKLMNOP)；
4. 将 H(ABCDEFGH)，H(IJKLMNOP)左右拼接，hash 计算得到最终的 Merkle Root。

只要上述环节有任何差错（sibling 错了，或者左右顺序错了），就不能得到正确的 Merkle Root。

那么 Verifier 是如何知道每次拼接的顺序的呢？
是因为 prover 告知了这个叶子所在的序号和总叶子数，verifier 可以据此构建一个树形结构，进而推断出每次sibling拼接时的左右顺序。

如果prover 提供的叶子的序号是错的，那么拼接时就会出错，无法得到正确的 Merkle Root，导致验证失败，即使 Merkle Proof 的所有数都是正确的。

只有当 Merkle Proof 正确，叶子的序号也正确，才能通过验证。

或者 verifier 可以向 prover 指定要 n 个叶子中的第 i 个叶子，verifier 提供：

• 这个叶子
• 以及有这个叶子推算得到 Merkle Root 沿途所需要的值

verifier 就可以根据前述的原理进行验证，这个叶子确实就是第 i 个叶子。

---

1. Catalano, Dario, and Dario Fiore. "Vector commitments and their applications." International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg, 2013. https://eprint.iacr.org/2011/495.pdf ↩

2. Flyclient: Super-Light Clients for Cryptocurrencies https://eprint.iacr.org/2019/226 ↩