PCS Multiproofs

rust verkle 的实现 https://github.com/crate-crypto/rust-verkle 使用了 multiproof 来优化。因此也需要了解相关的内容。

PCS 至少有两个方案，一个是 KZG，一个是 IPA。

KZG 可以参考 https://hackmd.io/@liquan/r1xt93zft6
IPA 可以参考 https://hackmd.io/@liquan/Bk6m487-A

并且它们都是支持加法同态，它们都可以应用 Multiproof。

因此这里我会分别介绍 KZG 和 IPA 的 Multiproofs。其中 KZG 的直接参考的：https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html ，IPA 是我自己的理解。

Origin version (KZG)

问题

在宽度为

$d$ 的 verkle 树中，我们希望尽可能高效地提供所有中间 KZG 证明。

示例

如上图，作为一个 trie，中间节点存 path，叶子节点存 value，从 root 到叶子节点的整个 path 组成 key。如果某个中间节点下面只有一个叶子节点，就会直接优化调这个中间节点，比如最左边的叶子节点 0101_0001_1111_0010 -> 1354。

如果外部从我们这里查询，0101_0111_1010_1111，我们返回 1213，以及相关的证明。

证明包含哪些：

• Node A 和 Node B 的 Commit
• 叶子节点 0101_0111_1010_1111 -> 1213 在 Node B 的 1010 path 上。具体是通过证明叶子节点的 root(hash of kv) is the evaluation of the commitment of Node B at the index 1010
• Node B 在 Node A 的 0111 path 上。具体是通过证明 Node B 的 root(hash of KZG Commitment) is the evalution of the commitment of Node A at the index 0111
• Node A 在 Root 的 0101 path 上。具体是通过证明 Node A 的 root(hash of KZG commitment) is the evalution of the Root commitment at the index 0101

commitments:

• $C_0$:
  $f_0(X)$ node B
• $C_1$:
  $f_1(X)$ node A
• $C_2$:
  $f_2(X)$ root

计算

$f_i$

need to prove:

• $f_0(w^{1010})=H(0101011110101111,1213)$, where
  $C_0=[f_0(s){]}_1$
• $f_1(w^{0111})=H(C_0)$, where
  $C_1=[f_1(s){]}_1$
• $f_2(w^{0101})=H(C_1)$, where
  $C_2=[f_2(s){]}_1$