# 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$
-