tl;dr: 向量承诺 (VC) 方案的定义（例如， Merkle 树, KZG Based, Pointproofs[^GRWZ20], aSVC[^TABplus20] 等均满足此定义。）
初步内容
一个向量 $\mathbf{v}$ 的 $B$-子向量定义为仅来自 $\mathbf{v}$ 中位于 $B$ 的位置的元素：
即，$\mathbf{v}[B] \overset{\mathrm{def}}{=} (vj){j\in B}$。
定义
所有算法都是确定性的。
通常，VC 设置包括：
- 一个 证明者，计算向量的 承诺。
- 一个 验证者，得到这样的承诺，并且对验证一个元素 $v_j$ 确实位于承诺向量中的位置 $j$ 感兴趣。
Vanilla (普通) VC
$\mathsf{VC.Commit}(\mathbf{v} \overset{\mathrm{def}}{=} [v_1, v_2,\ldots,v_n])\rightarrow (c, ad)$
给定一个 向量 $\mathbf{v}$，计算其承诺 $c$ 和 认证数据(authData) $ad$，这有助于加速证明者。
{: .note}
根据 VC 方案的不同，$ad$ 可以存储向量 $\mathbf{v}$、承诺 $c$，和/或任何预先计算的证明。
对于 Merkle 基于的 VC，$ad$ 将包含 Merkle 树本身。
这样，拥有 $ad$ 的证明者可以通过提供到这个元素的 Merkle 路径来证明 $v_j$ 是第 $j$ 个元素。
对于 基于 KZG 的 VC 与 FK，$ad$ 将包含每个位置 $j\in[n]$ 的所有 $n$ 个预计算的 (个体) 证明。
$\mathsf{VC.Prove}(ad, j) \rightarrow (\pi_j)$
给定认证数据 $ad$，获取（或计算）元素 $v_j$ 在位置 $j$ 的 个体证明 $\pi_j$。
$\mathsf{VC.Verify}(c, j, v_j, \pi_j)\rightarrow {0,1}$
验证 个体证明 $\pi_j$，该证明表明 $v_j$ 是在 $c$ 中承诺的向量的第 $j$ 个元素。
SVCs
$\mathsf{VC.Aggregate}(c, (j,v_j,\pij){j\in B})\rightarrow \hat{\pi}$
给定一个 $B$-子向量 和每个位置 $j\in B$ 的个体证明 $\pi_j$，将它们 聚合 成一个 子向量证明 $\hat{\pi}$。
$\mathsf{VC.AggVerify}(c, B, \mathbf{v}[B], \hat{\pi})\rightarrow {0,1}$
验证子向量证明 $\hat{\pi}$，以确认 $\mathbf{v}[B]$ 确实是承诺在 $c$ 中的向量的 $B$-子向量。
可交叉聚合的 SVCs
$\mathsf{VC.CrossAggregate}\left({c_i, B_i,\mathbf{v}_i[B_i],\hat{\pi}i)}{i\in[\ell]}\right)\rightarrow \pi$
将许多不同向量的子向量证明 交叉聚合 成一个 交叉聚合证明 $\pi$。
$\mathsf{VC.CrossVerify}\left({c_i, B_i,\mathbf{v}_i[Bi]}{i\in[\ell]},\pi\right)\rightarrow {0,1}$
验证给定子向量及其相关向量的承诺的交叉聚合证明。
待办事项
- 普通 VC 和 SVC 的证明更新（也许还有交叉聚合 VC[^TXN20]？）
- 隐藏 VC
参考文献
- Pointproofs: Aggregating Proofs for Multiple Vector Commitments, by Gorbunov, Sergey and Reyzin, Leonid and Wee, Hoeteck and Zhang, Zhenfei, in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, 2020, [URL] ↩
- Aggregatable Subvector Commitments for Stateless Cryptocurrencies, by Tomescu, Alin and Abraham, Ittai and Buterin, Vitalik and Drake, Justin and Feist, Dankrad and Khovratovich, Dmitry, in Security and Cryptography for Networks, 2020
