polynomial commitment及实现方式对比

1. commitment

1.1 commitment定义

commitment在密码学协议中是非常重要的组成部分。基本定义为：A commitment scheme allows a committer to publish a value, called the commitment, which binds her to a message (binding) without revealing it (hiding). Later, she may open the commitment and reveal the committed message to a verifier, who can check that the message is consistent with the commitment.

1.2 commitment特性

commitment一般分为commit和reveal两个阶段，commit整个过程可形象描述为a committer P将某个信息m放进了一个密码箱中，箱子上锁后归a verifier V所有，锁钥匙归P所有；reveal过程为P将钥匙给V，V打开箱子可查看里面的信息m。commitment具有如下特性：

• hiding特性：即V拥有了上锁的箱子，由于没有钥匙无法获取里面的信息m。
• binding特性：即尽管P拥有了钥匙，但是箱子归V所有，P无法在上锁后再次开锁修改其中的信息为m’。即某个值commit后，将不可修改。

当使用公私钥对来满足hiding特性进行上锁过程时，可称为Trapdoor commitment或者chameleon commitment。

根据binding属性，reveal过程可分为hard和soft两种。在commit阶段，可选择是创建hard还是soft commitment。hard commitment是指标准的commitment，即针对消息m进行commit，reveal后的结果也仅可能为m。soft commitment是指初始时，对空消息（no message）进行commit，然后后续可reveal为任意的消息m。

可参加博客Pedersen Commitment扫盲及sage和python脚本，commitment具有加法同态性。

1.3 commitment的实现方式

通常有3个著名的方式来实现a committer can use to commit to a message：
假设 g 和 h g和h g和h为group G G G（具有prime order p p p）的两个随机generator，对于消息 m ∈ R Z p m\in_RZ_p m∈R​Zp​：

• 1）commit计算方式为： C < g > ( m ) = g m C_{<g>}(m)=g^m C<g>​(m)=gm。此种方式，具有unconditionally binding特性，以及基于离散对数在 G G G中很难的假设的computationnally hiding特性。
• 2）Pedersen commitment，计算方式为： C < g , h > ( m , r ) = g m h r , r ∈ R Z p C_{<g,h>}(m,r)=g^mh^r,r\in_R Z_p C<g,h>​(m,r)=gmhr,r∈R​Zp​，由于 r r r为随机数，Pedersen commitment具有unconditionally hiding特性，以及基于离散对数假设的computationally binding特性。
• 3）计算方式为： H ( m )   o r   H ( m ∣ ∣ r ) H(m)\ or\ H(m||r) H(m) or H(m∣∣r)，其中 H H H为one-way function单向函数。实际常使用抗撞击的hash函数。

2. vector commitment

vector commitment是对一系列有序vector ( m 1 , m 2 , . . . , m q ) (m_1,m_2,...,m_q) (m1​,m2​,...,mq​) 进行commit和reveal操作。
对第一节的binding特性进行了加强，即具有position binding特性。postion binding特性是指对于同一位置i，不可能reveal出两个不同的值 m i , m i ′ m_i,m_i' mi​,mi′​。

同时vector commitment具有updatable特性，即对位置i的消息 m i m_i mi​更新为 m i ′ m_i' mi′​，可以同时将相应的commitment C C C更新为 C ′ C' C′，满足proof update特性。

详细的内容可参看论文《Vector Commitments and their Applications》第三章。

3. polynomial commitment

论文《Constant-Size Commitments to Polynomials and Their Applications》中指出，polynomial commitment可用于：verifiable secret sharing, zero-knowledge sets, credentials and selective disclosure of signed data。

3.1 polynomial commitment定义

基于verifiable secret sharing应用场景引出：
多项式 ϕ ( x ) ∈ R Z p [ x ] \phi (x)\in_RZ_p[x] ϕ(x)∈R​Zp​[x]，假设 ϕ ( x ) \phi (x) ϕ(x)多项式的阶为 t t t，系数为 ϕ 0 , . . . ϕ t \phi_0,...\phi_t ϕ0​,...ϕt​，polynomial commitment可表示为a commit to the string ( ϕ 0 ∣ ϕ 1 ∣ . . . ∣ ϕ t ) (\phi_0|\phi_1|...|\phi_t) (ϕ0​∣ϕ1​∣...∣ϕt​)，或者其它能明确代表 ϕ ( x ) \phi (x) ϕ(x)的string。

论文《Constant-Size Commitments to Polynomials and Their Applications》中主要基于以下代数属性：
对于多项式 ϕ ( x ) ∈ R Z p [ x ] \phi (x)\in_RZ_p[x] ϕ(x)∈R​Zp​[x]，对于任意的 i ∈ Z p i\in Z_p i∈Zp​，多项式 ϕ ( x ) − ϕ ( i ) \phi(x)-\phi(i) ϕ(x)−ϕ(i)都可以整除 ( x − i ) (x-i) (x−i)。

3.2 polynomial commitment实现方式对比

• 论文《Constant-Size Commitments to Polynomials and Their Applications》：
  provided protocols to commit to polynomials and then evaluate them at a given point in a verifiable way. Their protocols only require a constant number of commitments but security relies on pairing assumptions。
  基于的数学原理为：（论文《Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings》中的polynomial commitment也是基于此原理。）
  

• 论文《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》：
  Our polynomial commitment protocol has square root communication complexity but
  relies solely on the discrete logarithm assumption.
  基于的原理是：（将系数拆分为矩阵，每行作为一个vector，将polynomial commitment拆分由vector commitment组成。）
  

参考资料：
[1] 博客密码学上的commitment
[2] 博客Pedersen Commitment扫盲及sage和python脚本
[3] 论文《Vector Commitments and their Applications》
[4] 论文《Constant-Size Commitments to Polynomials and Their Applications》
[5] 论文《Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions》
[6] 论文《Zero-knowledge Argument for Polynomial Evaluation with Application to Blacklists》
[7] ppt分享《Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials》

polynomial commitment及实现方式对比

1. commitment

1.1 commitment定义

commitment在密码学协议中是非常重要的组成部分。基本定义为：A commitment scheme allows a committer to publish a value, called the commitment, which binds her to a message (binding) without revealing it (hiding). Later, she may open the commitment and reveal the committed message to a verifier, who can check that the message is consistent with the commitment.

1.2 commitment特性

commitment一般分为commit和reveal两个阶段，commit整个过程可形象描述为a committer P将某个信息m放进了一个密码箱中，箱子上锁后归a verifier V所有，锁钥匙归P所有；reveal过程为P将钥匙给V，V打开箱子可查看里面的信息m。commitment具有如下特性：

• hiding特性：即V拥有了上锁的箱子，由于没有钥匙无法获取里面的信息m。
• binding特性：即尽管P拥有了钥匙，但是箱子归V所有，P无法在上锁后再次开锁修改其中的信息为m’。即某个值commit后，将不可修改。

当使用公私钥对来满足hiding特性进行上锁过程时，可称为Trapdoor commitment或者chameleon commitment。

根据binding属性，reveal过程可分为hard和soft两种。在commit阶段，可选择是创建hard还是soft commitment。hard commitment是指标准的commitment，即针对消息m进行commit，reveal后的结果也仅可能为m。soft commitment是指初始时，对空消息（no message）进行commit，然后后续可reveal为任意的消息m。

可参加博客Pedersen Commitment扫盲及sage和python脚本，commitment具有加法同态性。

1.3 commitment的实现方式

通常有3个著名的方式来实现a committer can use to commit to a message：
假设 g 和 h g和h g和h为group G G G（具有prime order p p p）的两个随机generator，对于消息 m ∈ R Z p m\in_RZ_p m∈R​Zp​：

• 1）commit计算方式为： C < g > ( m ) = g m C_{<g>}(m)=g^m C<g>​(m)=gm。此种方式，具有unconditionally binding特性，以及基于离散对数在 G G G中很难的假设的computationnally hiding特性。
• 2）Pedersen commitment，计算方式为： C < g , h > ( m , r ) = g m h r , r ∈ R Z p C_{<g,h>}(m,r)=g^mh^r,r\in_R Z_p C<g,h>​(m,r)=gmhr,r∈R​Zp​，由于 r r r为随机数，Pedersen commitment具有unconditionally hiding特性，以及基于离散对数假设的computationally binding特性。
• 3）计算方式为： H ( m )   o r   H ( m ∣ ∣ r ) H(m)\ or\ H(m||r) H(m) or H(m∣∣r)，其中 H H H为one-way function单向函数。实际常使用抗撞击的hash函数。

2. vector commitment

vector commitment是对一系列有序vector ( m 1 , m 2 , . . . , m q ) (m_1,m_2,...,m_q) (m1​,m2​,...,mq​) 进行commit和reveal操作。
对第一节的binding特性进行了加强，即具有position binding特性。postion binding特性是指对于同一位置i，不可能reveal出两个不同的值 m i , m i ′ m_i,m_i' mi​,mi′​。

同时vector commitment具有updatable特性，即对位置i的消息 m i m_i mi​更新为 m i ′ m_i' mi′​，可以同时将相应的commitment C C C更新为 C ′ C' C′，满足proof update特性。

详细的内容可参看论文《Vector Commitments and their Applications》第三章。

3. polynomial commitment

论文《Constant-Size Commitments to Polynomials and Their Applications》中指出，polynomial commitment可用于：verifiable secret sharing, zero-knowledge sets, credentials and selective disclosure of signed data。

3.1 polynomial commitment定义

基于verifiable secret sharing应用场景引出：
多项式 ϕ ( x ) ∈ R Z p [ x ] \phi (x)\in_RZ_p[x] ϕ(x)∈R​Zp​[x]，假设 ϕ ( x ) \phi (x) ϕ(x)多项式的阶为 t t t，系数为 ϕ 0 , . . . ϕ t \phi_0,...\phi_t ϕ0​,...ϕt​，polynomial commitment可表示为a commit to the string ( ϕ 0 ∣ ϕ 1 ∣ . . . ∣ ϕ t ) (\phi_0|\phi_1|...|\phi_t) (ϕ0​∣ϕ1​∣...∣ϕt​)，或者其它能明确代表 ϕ ( x ) \phi (x) ϕ(x)的string。

论文《Constant-Size Commitments to Polynomials and Their Applications》中主要基于以下代数属性：
对于多项式 ϕ ( x ) ∈ R Z p [ x ] \phi (x)\in_RZ_p[x] ϕ(x)∈R​Zp​[x]，对于任意的 i ∈ Z p i\in Z_p i∈Zp​，多项式 ϕ ( x ) − ϕ ( i ) \phi(x)-\phi(i) ϕ(x)−ϕ(i)都可以整除 ( x − i ) (x-i) (x−i)。

3.2 polynomial commitment实现方式对比

• 论文《Constant-Size Commitments to Polynomials and Their Applications》：
  provided protocols to commit to polynomials and then evaluate them at a given point in a verifiable way. Their protocols only require a constant number of commitments but security relies on pairing assumptions。
  基于的数学原理为：（论文《Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings》中的polynomial commitment也是基于此原理。）
  

• 论文《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》：
  Our polynomial commitment protocol has square root communication complexity but
  relies solely on the discrete logarithm assumption.
  基于的原理是：（将系数拆分为矩阵，每行作为一个vector，将polynomial commitment拆分由vector commitment组成。）
  

参考资料：
[1] 博客密码学上的commitment
[2] 博客Pedersen Commitment扫盲及sage和python脚本
[3] 论文《Vector Commitments and their Applications》
[4] 论文《Constant-Size Commitments to Polynomials and Their Applications》
[5] 论文《Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions》
[6] 论文《Zero-knowledge Argument for Polynomial Evaluation with Application to Blacklists》
[7] ppt分享《Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials》