<aside> 💡 KZG Commitment用于Ethereum的Danksharding和Verkle Tree、zkSync、Aleo等项目中，是零知识证明算法PLONK和Marlin的重要组成部分

</aside>

<aside> 💡 本篇概述其基本原理，后续再根据播放情况来决定后面深入讲解计算过程的篇幅

</aside>

<aside> 💡 学习完本篇之后，预期能理解零知识证明算法为什么能用简短的proof来证明庞大的knowledge，并且不暴露knowledge的信息给验证者

</aside>

Polynomial

  1. 系数形式（Coefficient）
    1. $f(x) = x^3-2x+1$
    2. 4个系数(1, 0, -2, 1)
  2. 点值形式（Point-Value）
    1. (0, 1) , (1, 0), (2, 5) , (3, 22)
  3. 系数形式→点值形式：代入计算（evaluation）
  4. 点值形式→系数形式

    1. 需要几个点值才能求解所有系数？

      1. 定义Degree为最高次数
      2. 则需要d+1个点值确定d+1个系数

    2. 方法1：需要d+1元方程组求解d+1个系数

      Untitled

    3. 方法2：拉格朗日插值（Lagrange interpolation）

      Untitled

    4. 用途：Reed-Solomon erasure code

      1. d+1个点值记录原始数据，多取n个点值作为冗余
  5. Schwartz–Zippel Lemma
    1. 对于Degree为d的多项式$f(x)=0$最多只有d个解
      1. $f(x) = x^2+1=0$ 无解
      2. $f(x)=x^2-1=(x+1)(x-1)=0$ 2个解
      3. 因为最多分解成d个因式
    2. 如果x的取值范围大小是s，那随机取一个$x_0$，$f(x_0)=0$发生的概率$\le \frac{d}{s}$
      1. s远大于d，则不可能发生
      2. 衍生为：对于随机的$x_0$、$y_0$，$f(x_0)=y_0$不可能发生
      3. 衍生为：对于随机的$x_0$，如果我在不知道$f(x)$的情况下随机猜测$f(x_0)$的值，则不可能正好猜对
    3. 如果我能给出$f(x)$对于随机$x_0$的正确evaluation结果$f(x_0)$，则证明我知道$f(x)$的完整信息
      1. 用简洁的proof来证明我知道庞大的knowledge
      2. 这就是零知识证明中的Proof of Knowledge的核心原理
    4. 基于Schwartz–Zippel Lemma的Proof of Knowledge：形象表述

      1. 一段音乐的时间长度为d，频率范围长度为s，s远大于d

      2. 如果我能给出音乐在随机频率上的正确强度，则证明我知道这段音乐的完整信息

      3. 因为任一频率上的强度，需要所有时间点上的强度来参与计算

        Untitled

Vector Commitment

  1. Vector Commitment

    1. 将一组数据（vector）压缩后唯一表示为Commitment；类似hash算法
    2. 然后Open其中的一个数据，并在不展示其他数据基础上提供一个Proof证明其属于vector

  2. 实现1：Merkle tree

    1. Merkle root即Commitment，Merkle path即proof
    2. Merkle的缺点是proof长度为O(log n)

    https://bitcoin.org/bitcoin.pdf

    https://bitcoin.org/bitcoin.pdf

  3. 实现2：Polynomial Commitment

    1. 将长度为n+1的vector转换为多项式的点值$(v_0, v_1, ..., v_n)$→$(0, v_0), (1, v_1), ...,(n, v_n)$
    2. 将唯一对应的Degree=n的多项式$f(x)$，生成为Commitment
    3. Open其中的一个点，提供一个Proof证明点值$(k,v_k)$符合多项式$f(k)=v_k$

Interactive Oracle Proofs (IOP)

  1. 回顾Schwartz–Zippel Lemma和Polynomial Commitment
    1. 如果我能给出$f(x)$对于随机$x_0$的正确evaluation，则证明我知道$f(x)$的完整信息
    2. 可以用$f(x)$的Polynomial Commitment来证明$(x_0, y_0)$是正确的evaluation
  2. 两者的意义
    1. Schwartz–Zippel Lemma将Proof of Knowledge问题转化为证明Polynomial中一个随机evaluation正确性的问题
    2. Polynomial Commitment给出了证明Polynomial的一个evaluation正确性的方法，并且不会暴露Polynomial给Verifier
  3. 两者结合：基于Polynomial Commitment的交互式（Interactive） Proof of Knowledge
    1. Alice将Knowledge vector作为点值生成$f(x)$
    2. Alice生成$f(x)$的Commitment C告诉Bob
    3. Bob随机选取$x_0$给Alice
    4. Alice返回$y_0$和Proof给Bob
    5. Bob根据C、$(x_0,y_0)$、Proof验证正确性
    6. 正确则说明Alice知道$f(x)$的完整信息
  4. 基于Random Oracle的Non-interactive Proof of Knowledge
    1. Bob随机选取$x_0$给Alice → Alice计算$x_0=hash(C)$

KZG commitment

Knowledge -> Point-Values -> Coefficients -> Commitment -> Open&Prove&Verify
                         FFT             MSM
                                          ^
                                          |
                                    Trusted Setup