主页
简介
多项式承诺是一种实用性比较强的密码学承诺方案，允许一个方（承诺者）向另一个方（验证者）承诺一个多项式的值，而不泄露多项式的具体形式。在零知识证明、可验证密码共享等领域有广泛应用，常见的多项式承诺有Kate多项式承诺、FRI多项式承诺，IPA多项式承诺等。本文将重点介绍Kate多项式承诺的构造和应用。
在阅读下文之前，了解基础的密码学承诺原理和应用是非常有必要的，读者可以参考以下几篇文章：
前言
多项式
[a.kuafortv.com)
[a.turotryv.com)
[a.xelentec.com)
[a.odiesel.com)
[a.tonarini.net)
[a.pc-yours.com)
[a.sints.net)
[a.tonytwei.com)
[a.micopan.com)
在详细介绍Kate多项式承诺之前，我们先来简单介绍一下多项式的基本概念。多项式一般表示为：
f(x)=a0+a1x+a2x2+⋯+adxd=∑i=0daixi
上述多项式中，a0,a1,a2,...,ad是多项式系数，x是多项式的变量，d是多项式的次数(或多项式的度)。多项式的次数是指多项式中最高次幂的指数，例如上述多项式的次数为t,因此上述f(x)我们也称作d次多项式。多项式系数a0,a1,a2,...,ad是多项式的重要组成部分，它们决定了多项式的形状和性质，也是需要保护的重要信息。
多项式的值是指将变量x代入多项式后的结果，例如f(β)表示将x=β代入多项式中，计算出的结果。
多项式的根是指多项式的值为0的点，即f(x)=0的点。
多项式有两个重要的性质：
- 一元n次多项式最多有n个根，假设根为β1,β2,...,βd，则多项式可以表示为：f(x)=(x−β1)(x−β2)...(x−βd)
- 商多项式，多项式减去在某一个点的多项式值(如点：<a,f(a)>), 可以被另一个多项式整除，这个多项式称为商多项式。商多项式表示为h(x)=f(x)−f(a)x−a
注：在零知识证明中，通常会将要证明的问题转化为多项式表达，并通过多项式与商多项式的等式关系来进行证明。
双线性映射
在多项式承诺验证中，会用到双线性映射的概念。双线性映射（Bilinear Map）是数学中一种重要的映射，尤其在密码学和数论中有广泛的应用。它是一种特殊的函数，具有以下性质：
定义
设G是一个乘法循环群, g是一个生成元, GT是另一个群。一个映射e:G×G→GT被称为双线性映射，如果满足以下条件：
- 双线性：对于任意的a,b∈Zp和g,h∈G，有e(ga,hb)=e(g,h)ab
- 非退化性：对于任意的g∈G，e(g,g)≠1
- 可计算性：对于任意的g,h∈G，e(g,h)可以在多项式时间内计算
重要性质：
- 可交换性：对于任意的g,h∈G，e(g,h)=e(h,g)
- 分配性：对于任意的g,h1,h2∈G，e(g,h1⋅h2)=e(g,h1)⋅e(g,h2)
- 为为e(g,g)为GT的一个生成元
多项式承诺
多项式承诺主要流程如下：
- [00] Setup初始化阶段：承诺者和验证者共享公共参考串CRS
- CRS：common reference string，是一个公开的字符串，一般通过可信的第三方生成，用于多项式承诺的构造
- [01] Commit承诺阶段：承诺者计算多项式承诺C=Commit(CRS,f(α))，并发送C给验证者。
- C的计算依赖于多项式f(x)和公共参考串CRS
- 注在多项式承诺中，多项式的度需要满足d≤t，其中t是公共参考串中的最高幂次
- [02] Open打开阶段：承诺者揭示多项式f(x)
- f(x)是多项式的具体形式，承诺者直接揭示多项式f(x)，如多项式参数和系数
- [03] VerifyPoly验证阶段：验证者重新计算多项式承诺C′=Commit(CRS,f(α))
- 验证者重新计算多项式承诺C′，并验证C′和C是否相等
以上方式的多项式承诺打开阶段是明文揭示，即承诺者直接揭示多项式f(x)，验证者重新计算多项式承诺C′=Commit(CRS,f(x))，并验证C′和C是否相等。
明文揭示的方式简单直接，但存在以下问题：
- 多项式阶数较高时，明文揭示的方式会导致通信量较大
- 明文揭示的方式无法保护多项式，必须公开
Kate多项式承诺
为了解决明文揭示多项式承诺存在的问题，Kate多项式承诺基于多项式点打开的方式，实现了多项式的承诺和验证。点打开方式指的是承诺者不直接揭示多项式f(x)，而是揭示多项式在某个点的值f(β)，并提供一个witness证明，验证者通过双线性映射验证多项式在β点的值是否正确。通过点打开的方式，Kate多项式承诺解决了明文揭示的问题，同时保护了多项式的隐私。
Kate多项式承诺的构造一般有两种方案，两种方案在安全性上有所不同：
- 计算隐藏的Kate多项式承诺：承诺的值在计算上是隐藏的，意味着对于任何多项式时间的攻击者，无法有效区分两个不同的承诺。换句话说，攻击者在计算上无法从承诺中推断出承诺的内容。
- 无条件隐藏的Kate多项式承诺：承诺的值在计算上是无条件隐藏的，意味着对于任何攻击者，无法从承诺中推断出承诺的内容。
定义上比较抽象，简单来说就是无条件隐藏通过引入随机性，使得承诺的值在计算上无法被推断出来，而计算隐藏仅使用离散对数困难性假设，使得承诺的值在计算上无法被推断出来。
计算隐藏的Kate多项式承诺
计算隐藏的Kate多项式承诺的构造如下:
[00] Setup初始化阶段
Kate多项式承诺需要初始化阶段，主要是生成和公开CRS，以及双线性映射e:G×G→GT。在Kate多项式承诺中CRS如下：
CRS=(G,gα,gα2,...,gαt)
其中，G代表乘法群，g是G的一个生成元，α是一个随机数，t是最高幂次。注：在零知识证明中，α是一个私密的值，不会公开，需要被安全销毁（通常被称为有毒废料）。
注：在Kate论文中，CRS被叫做PK，即公钥。
[01] Commit承诺阶段
承诺者计算多项式的承诺值C=Commit(CRS,f(x))，并发送C给验证者。多项式的承诺值计算方式如下：
C=gf(α)=g∑i=0daiαi=∏i=0dgaiαi=∏i=0d(gαi)ai
- ai是多项式的系数, 承诺者已知
- CRS是公共参考串，CRS中包含了gαi的值，因此承诺者可以在不知道α的情况下计算C
[02] CreateWitness点打开阶段
承诺者计算多项式在某个点的值f(β)，并提供一个witness证明w，其中w是多项式在β点的承诺，计算方式如下：
- 首先计算商多项式
φ(x)=f(x)−f(β)x−β=∑i=0d−1bixi
- 计算f(x)在β点的值
f(β)=∑i=0daiβi
- 计算商多项式在α点的承诺值
w=Commit(CRS,φ(x))=gφ(α)=g∑i=0d−1biαi=∏i=0d−1gbiαi=∏i=0d−1(gαi)bi
承诺者将(β,f(β),w)发送给验证者。
[03] VerifyEval点验证阶段
验证者使用双线性映射验证多项式在β点的打开值是否正确，验证方式如下：
e(C,g)=?e(w,gα/gβ)⋅e(g,g)f(β)
正确性验证：
e(w,gα/gβ)⋅e(g,g)f(β)=e(gφ(α),gα−β)⋅e(g,g)f(β)=e(g,g)φ(α)⋅(α−β)+f(β)
根据商多项式的定义，有：f(α)−f(β)=φ(α)⋅(α−β)，因此：
e(w,gα/gβ)⋅e(g,g)f(β)=e(g,g)f(α)−f(β)+f(β)=e(g,g)f(α)=e(gf(α),g)=e(C,g)
因此，e(C,g)=e(w,gα/gβ)⋅e(g,g)f(β)，验证通过。
无条件隐藏的Kate多项式承诺
无条件隐藏的Kate多项式承诺构造与计算隐藏的Kate多项式承诺流程类似，区别在于：
- 初始化阶段的CRS不同
- 承诺值的生成和验证方式不同（承诺值生成基于Pedersen承诺）
初始化阶段
CRS的构造如下：
CRS=(G,gα,gα2,...,gαt,h,hα,hα2,...,hαt)
其中，h是G的另一个生成元。
Commit承诺阶段
承诺者计算多项式的承诺值C=Commit(CRS,f(x))，计算方式如下：
C=gf(α)⋅hf(α)^f(α)=∑i=0daiαif(α)^=∑i=0dbiαi=∏i=0d(gαi)ai⋅∏i=0d(hαi)bi
CreateWitness点打开阶段
承诺者计算多项式在某个点的值f(β)，并提供一个witness证明w，计算方式如下：
- 计算商多项式
φ(x)=f(x)−f(β)x−βφ(x)^=f(x)^−f(β)^x−β
- 计算点打开值
w=Commit(CRS,φ(x))⋅Commit(CRS,φ(x)^)=gφ(α)⋅hφ(α)^
gφ(α)和hφ(α)^计算方式基于CRS（方式与上文相同，略），承诺者将(β,f(β),f(β)^,w)发送给验证者。
VerifyEval点验证阶段
验证者使用双线性映射验证多项式在β点的打开值是否正确，验证方式如下：
e(C,g)=?e(w,gα/gβ)⋅e(gf(β)⋅hf(β)^,g)
正确性验证：
h是G中的一个群元素，因此不是一般性可设h=gλ，其中λ是一个随机数。因此：
e(w,gα/gβ)⋅e(gf(β)⋅hf(β)^,g)=e(gφ(α)⋅hφ(α)^,gα−β)⋅e(gf(β)⋅hf(β)^,g)=e(gφ(α)+λφ(α)^,gα−β)⋅e(gf(β)+λf(β)^,g)=e(g,g)φ(α)⋅(α−β)+λφ(α)^⋅(α−β)+f(β)+λf(β)^=e(g,g)φ(α)⋅(α−β)+f(β)+λ⋅(φ(α)^⋅(α−β)+f(β)^)
根据商多项式的定义，有：f(α)−f(β)=φ(α)⋅(α−β)，f(α)^−f(β)^=φ(α)^⋅(α−β)，因此：
e(w,gα/gβ)⋅e(gf(β)⋅hf(β)^,g)=e(g,g)φ(α)⋅(α−β)+f(β)+λ⋅(φ(α)^⋅(α−β)+f(β)^)=e(g,g)f(α)−f(β)+f(β)+λ⋅(f(α)^−f(β)^+f(β)^)=e(g,g)f(α)+λ⋅f(α)^=e(gf(α)⋅gλ⋅f(α)^,g)=e(gf(α)⋅hf(α)^,g)=e(C,g)
因此，e(C,g)=e(w,gα/gβ)⋅e(gf(β)⋅hf(β)^,g)，验证通过。
结语
Kate多项式承诺是一种实用性比较强的多项式承诺方案，通过点打开的方式，可以在保护多项式隐私的同时，有效减少通信量。Kate多项式承诺在零知识证明、可验证密码共享等领域有广泛应用。了解Kate多项式承诺的原理和构造，对于学习zk-snarks、zk-starks等零知识证明协议是非常有帮助的。通过本文的介绍，希望读者能够对Kate多项式承诺有一个初步的了解，并为进一步学习零知识证明协议打下基础。
