当然，这是一个非常低级的多项式承诺，但能帮助我们理解其具有哪些优势。观察下面这些属性：

　　1. 承诺大小是一个单散列（默克尔根）。一个足够安全的加密散列通常需要 256 个位元（bit），即 32 个字节（byte）。

　　2. 要想证明一个求值，验证人需要把所有的 pi 发出去，以此证明大小（proof size）与多项式的次数呈线性关系，校验人需要进行线性运算（通过计算

　　求出多项式在位置 z 处的值）。

　　3. 此方案未对多项式进行隐藏——验证人以非隐藏方式发送完整的多项式，及其每一个系数。

　　下面，我们探讨一下 Kate 方案以此类指标可以实现怎样的效果。

　　承诺大小是一个椭圆群的群元素，该群支持配对。例如，BLS12_381 有 48 个字节。

　　证明大小不受多项式大小的影响，也是一个群元素。校验多项式次数和大小的影响，始终需要一次两群相乘和两辆配对。

　　该方案基本实现了对多项式隐藏——实际上，将会出现无数多项式 Kate 承诺完全相同的情况。但是，完全隐藏仍未实现：如能猜出多项式（例如，当多项式很简单或只有几组可能的多项式时），就能找出承诺多项式。

　　另外，也可以把任意求值的证明合并到一个群元素中。正是这些属性使 Kate 方案通行于 PLONK、SONIC 等零知识证明系统，也使之可以作为向量承诺适用于一般情况。下文将予以详述。

　　椭圆曲线与配对

　　如上所述，本人强烈推荐 Vitalik Buterin 有关椭圆曲线配对的文章，其中介绍了理解本文所需的所有预备知识，尤其是有限域、椭圆曲线与配对等方面。

　　假设 G1 和 G2 为带有配对 e 的两条椭圆曲线：G1×G2→GT。G1 和 G2 的阶数均为 p，生成元（generator）分别为 G 和 H。用简化符号分别记作

　　[x]1=xG∈G1 和 [x]2=xH∈G2

　　任意 x∈Fp。

　　可信设置（Trusted setup）

　　假设完成了可信设置，则在某个秘密点 s 上，验证人和校验人均能获得 i=0、……n-1 时的 [si]1 和 [si]2 元素。

　　你可以这样理解这种秘密设置：用一台气隙计算机（airgapped computer）计算随机数 s，计算所有的群元素 [si]x，然后用有线方式只把这些元素发出去（不发送 s），最后把这台计算机销毁。当然，这种方案不够完美，因为你必须信任计算机操作员不会通过秘密通信通道获取到秘密点 s 的值。

　　在实践中，这通常是通过安全的多方计算（MPC）来实现的，此方法允许由一组计算机创建此类群元素，从而杜绝任何计算机获取秘密点 s 的值，而要想获取到 s，需要所有的计算机联手（或同时被攻破）才能做到。

　　注意，不会出现以下情况：即仅通过选择某个随机群元素 [s]1 （其 s 未知），计算出其他的群元素，最后得出 s。在 s 未知的情况下，无法计算出 [s2]1。

　　现在，椭圆曲线加密基本上说明了不可能通过可信设置的群元素得出 s 的实际值。s 是 Fp 中的一个数，但是验证人不可能找出这个数的实际值。验证人只能根据提供给他们的元素执行特定的计算。因此，验证人可以通过椭圆曲线乘法运算，很容易地计算出 c[si]1=csiG=[csi]1 等，且由于可以加上椭圆曲线点，还可以计算出 c[si]1+d[sj]1=(csi+dsj)G=[csi+dsj]1 等。实际上，如果

　　是多项式，验证人可以计算出：

　　有趣的是，几乎每个人都能使用这种可信设置在 s 未知的情况下，求出多项式在秘密点 s 处的值。除非他们没有得到自然数输出，而是只得到椭圆曲线点 [p(s)]1 = p(s)G，但是这就已经非常强大了。

　　Kate 承诺

　　在 Kate 承诺方案中，元素 C = [p(s)]1 是对多项式 p(X) 的承诺。

　　或许你会问：（在 s 未知的情况下）验证人能否找到另一个具有相同承诺的多项式 q(X) ≠ p(X)，即 [p(s)]1=[q(s)]1？假设存在这种情况。那将意味着 [p(s)-q(s)]1=[0]1，说明 p(s)-q(s)=0。

　　现在，r(X) = p(X)-q(X) 本身就是一个多项式。我们知道因为 p(X) ≠ q(X)，所以其并非常数。众所周知，任何次数为 n 的非常数多项式最多可以有 n 个零：因为如果 r(z) = 0，则 r(X) 可被线性因子 X-z 整除；因为我们可以将每个零除以一个线性因子，并且每除一次会使次数减一，所以次数不会超过 n。^2

　　由于验证人不知道 s，因此实现 p(s)-q(s) = 0 的唯一方法是在尽可能多的位置上实现 p(X)-q(X) = 0。但是，正如以上证明，由于验证人最多可以选 n 个位置，所以成功的可能性不高：由于 n 值远小于曲线 p 的次数，因此他们不太可能选择 s 点来使 p(X) = q(X)。为了感受此概率，假设采用当前可实现的最大可信设置，其中 n=228，并将其与曲线阶数 p≈2^256 进行比较：即便攻击者通过精心设计，使多项式 q(X) 在最多 n=228 个点上等于 p(X)，使这个多项式得出相同承诺（p(s) = q(s)）的概率也只有 228/2256 = 2^28-2^56 ≈ 2·10-69。概率极低。这其实就意味着攻击者无法实现其意图。

　　多项式相乘

　　到现在，我们已经证明了能够求出多项式在秘密点 s 处的值，这使得我们能够对一个唯一的多项式做出承诺——在某种意义上，尽管具有相同承诺 C=[p(s)]1 的多项式不止一个，但在实际中是无法计算出来的（密码学家称之为计算绑定（computationally binding））。

　　不过，在不将多项式完整地发送给校验人的情况下，我们仍无法「开启」承诺。而要「开启」承诺，我们需要用到配对。如上所述，我们可以用秘密元素进行某些线性运算；例如，我们可以把 [p(s)]1 计算为对 p(X) 的承诺，也可以把 p(X) 和 q(X) 的两个承诺相加，得出合并承诺 p(X)+q(X)：[p(s)]1+[q(s)]1=[p(s)+q(s)]1。

　　现在我们无法将两个多项式相乘。否则，就能使用多项式的某些属性实现目标。尽管椭圆曲线本身做不到，但所幸，我们可以通过配对来实现：我们知道：

　　其中引入了新符号 [x]T=e(G, H)x。因此，虽然我们不能把椭圆曲线里的两个域元素简单地相乘，然后将其乘积当作一个椭圆曲线元素（这是所谓的全同态加密（FHE）的属性之一；而椭圆形曲线仅是加法同态的），但是，如果在两个不同的曲线中对它们（一个在 G1 中，一个在 G2 中）进行承诺，并且输出是一个 G 元素的话，我们就能把两个域元素相乘。

　　这时就触及到了 Kate 证明的核心：还记得我们之前提到了线性因子么：如果多项式在 z 处为零，则多项式可被 X-z 整除。显然，反过来也是如此——如果多项式可被 X-z 整除，那么多项式在 z 处显然为零：被 Xz 整除意味着：我们可以得出某些多项式 q(X) 的 p(X) = (X-z)-q(X)，且多项式在 X = z 处显然为零。

　　现在要证明 p(z) = y。我们接着使用多项式 p(X)-y——由于该多项式在 z 处显然为零，因此我们可以运用线性因子的相关知识。使 q(X) 等于多项式 p(X)-y，被线性因子 X-z 整除，即

　　即等同于 q(X) (X-z) = p(X)-y。

　　Kate 证明

　　现在，将 p(z)= y 求值的 Kate 证明定义为π = [q(s)]1。对多项式 p(X) 的承诺被定义为 C = [p(s)]1。

　　校验人使用以下公式检查此证明：

　　注意，校验人可以计算出 [s-z]2，因为 [s-z]2 只是来自可信设置的元素 [s]2 与 z 的组合，且 z 是多项式的求值点。同样，把 y 当作声明值 p(z)，便可以计算出 [y]1。那么，为什么此检查能使校验人相信 p(z) = y；更准确地说，是使校验人相信由 C 所承诺的多项式在 z 处求出的值为 y？

　　我们需要评估两个属性：正确性和可靠性。正确性指验证人执行我们定义的步骤，可以得出能通过核验的证明。这一点一般不难。可靠性指校验人无法得出「不正确」的证明，即无法使校验人相信当 y'≠y 时，p(z) = y′。

　　首先，写出配对群中的方程式：

　　其正确性现在应该很明显了，即在未知随机点 s 上需要求值的方程 q(X) (X-z) = p(X)-y。

　　那么，我们怎么证明其可靠性以及验证人无法创建假证明呢？我们要用多项式思路来思考这个问题。如果验证人按我们的方法来构造证明，就必须以某种方式使 p(X)-y′被 X-z 整除。但是 p(z)-y′不为零，因此无法进行多项式除法运算，因为总会有余数。所以，这种方法显然行不通。

　　至此，就要尝试椭圆群：如果能计算出某些承诺 C 的椭圆群元素，结果又会怎样？

　　很显然，如果做到了这一点，就能证明一切。凭直觉来看，这一点很难实现，因为必须将与 s 相关的某些值指数化，但是 s 是未知的。出于证明的周密性考虑，需要提出配对的密码学假设，即所谓的 q-SDH 假设 3。

　　多值证明（Multiproofs）

　　现在，我们已经演示了如何证明多项式在一个点上的求值。注意，这已经非常了不起了：通过仅发送一个单群元素（例如，BLS12_381 中有 48 个字节），就能证明某个具有任意个次数（假设 228 个）的多项式在某个点上包含了某个值。在将默克尔树当作多项式承诺的小例子中，需要发送 228 个元素——多项式的所有系数。

　　现在，我们要更进一步，证明可以在任意数量的点上求出多项式的值，且仍然只使用一个群元素即可。为此，我们需要引入另一个概念：插值多项式。假设有一系列的 k 值 (z0, y0)、(z1, y1)……(zk-1, yk-1)：然后，总是能找到一个次数小于 k 的多项式能通过所有这些点。实现方法之一是使用拉格朗日插值法，此方法为该多项式 I(X) 提供了一个明确的公式：

　　现在，假设已知 p(X) 通过了所有点。则多项式 p(X)-I(X) 在 z0、z1……、zk-1 处均明显为零。这意味着它可以被所有线性因子（X-z0）、（X-z1）……（X-zk-1）整除。我们把所有因子都合并到所谓的零多项式中

　　就可以计算商数了

　　注意，这是可行的，因为 p(X)-I(X) 可被 Z(X) 中的所有线性因子整除，因此它可被整个 Z(X) 整除。

　　我们现在可以给求值 (z0, y0)、(z1, y1)……(zk-1, yk-1)：π=[q(s)]1 定义 Kate 多值证明——注意，这里仍然只有一个群元素。

　　现在，要进行检查，校验人还必须计算插值多项式 I(X) 和零多项式 Z(X)。借此，他们可以计算 [Z(s)]2 和 [I(s)]1，从而校验配对方程式

　　通过写出配对群中的方程，可以轻松地校验其能否以与单点 Kate 证明相同的方式进行验证：

　　其效果惊人：只需提供一个群元素，就可以证明任何数量的求值达一百万次！仅 48 字节即可证明所有求值！

　　用作向量承诺的 Kate 承诺

　　虽然 Kate 承诺方案被设计成了一种多项式承诺，但实际上也能成为非常好的向量承诺。向量承诺对向量 a0……an-1 进行承诺，为证明自己对某个 i 承诺了 ai 提供了方法。可以使用 Kate 承诺方案来进行重现：使 p(X) 为所有 i 均取为 p(i) = ai 的多项式。我们现在得到了这样一个多项式，可以用拉格朗日插值法来计算它：

　　利用这个多项式，我们可以仅使用一个群元素就能证明向量中任意数量的元素！（仅就证明大小而言）这种方法的效率要比默克尔树高得多：仅证明一个元素，一次默克尔证明会消耗 log n 个散列！