前言

比特承诺是密码学中重要的协议之一，作为构建零知识证明，可验证秘密共享，掷币协议等基础，一直是学术界的研究热点之一

简而言之，比特承诺可以让Alice承诺一个值，这个值Bob无法知道，在之后的阶段，Alice再向Bob解开承诺，同时使得Bob确信承诺的确实是这个值，而不是其他的值

有点绕，直接进正题

承诺方案

承诺方案（Commitment Scheme）是一个包含两个阶段的协议，包含一个承诺方（Committer）和接收方（Receiver）

通常来说，Prover作为Committer的身份，Verifier作为Receiver的身份，不过有时候也会反过来

承诺方案过程如下：

承诺阶段（Commit）： Committer将需要承诺的值放入一个带锁的箱子内（箱子无法被暴力破解），然后Committer将箱子传递给Receiver，此时Receiver无法知道箱子内装的是什么，同时Committer也无法改变箱子内承诺的值

揭示阶段（Reveal）：Committer出示箱子的钥匙，由Receiver打开箱子，取出Committer承诺的值

用符号的方式描述：承诺阶段中，Committer向Receiver发送一个值$c=Com(m,r)$，其中m为Committer想要承诺的消息，r为协议中的随机性（比如某个随机值），承诺阶段可以大致理解为一个加密方式（可以这么理解，但是不完全是），在揭示阶段，Committer向Receiver发送$(m,r)=Dec(c)$，此时Receiver可以验证在第一阶段Committer对他的承诺

承诺方案的性质

承诺方案有三个性质

  • 完备性（Completeness）：C总是可以生成合法的承诺值$c=Com(m,r)$
  • 隐藏性（Hiding）：Receiver无论如何都不能在揭示阶段前知道承诺的值m
  • 绑定性（Binding）：在承诺阶段结束后，Receiver只能在揭示阶段获得唯一的承诺值m

此外，协议还必须是可执行的和有效的，可执行代表是如果Committer和Receiver都遵守协议，则揭示阶段结束时Receiver确实收到了Committer发送的有效的承诺值，有效代表可以在PPT内执行

承诺方案需要在承诺阶段不泄露任何知识给Receiver（至少不泄露Committer的知识），且Committer只能在承诺阶段将自己绑定到一个唯一的值上，而在揭示阶段，Receiver只能收到这个值

比特承诺方案

在正式介绍比特承诺概念之前，先介绍几个前置概念和符号

Receiver和Sender之间交互的观点记为$(r,{\over m})$，包括接收者使用的随即硬币(r)和接收者接收到的消息序列($\over m$)

或然$σ$承诺：令$\sigma \in \{0,1\}$，若存在一个字符串s，满足$\over m$描述当R使用本地硬币r，并且与使用本地硬币s且具有输入$(\sigma,1^n)$的机器S交互时，从R收到的消息，则称接收者对这样的观点是或然$σ$承诺的

接下来讲一下比特承诺方案的比较严谨的定义

比特承诺方案是一对PPT交互机$(S,R)$（对应于Sender和Receiver），其满足如下条件

  • 输入：公共输入为一元整数n（作为安全参数）
  • Sender的私密输入：一个比特位，记为$v$
  • 隐藏性：Receiver无论如何背离协议（无论何种方式作弊）都无法区分0承诺与1承诺，也即对于每个与S交互的PPT机器$R^*$，在$\{<S(0),R^*>(1^n)\}$和$\{<S(1),R^*>(1^n)\}$这两种情况，描述${R^*}$输出的概率总体是计算不可区分的
  • 绑定性：若接收者的观点既是或然0承诺，又是或然1承诺，则满足绑定性（也就是接收者的观点是不明确的）

看不懂没关系，我也没看懂，接下来讲个案例就懂了

比特承诺示例

讲一个具体的例子吧，帮助理解

单比特承诺协议

假设$f$是一个单向函数，$b$是一个断言

$$ f:\{0，1\}^* ↦ \{0，1\}^* \\ b: \{0，1\}^* ↦ \{0，1\} $$

承诺阶段：如果Sender需要承诺一个随机比特$v \in \{0,1\}$，此时他随机选择一个字符串$s \in \{0,1\}^*$，令$α = f(s)$以及$\sigma = b(s)\oplus v$,将二元组$(α,\sigma)$发送给Receiver

揭示阶段：Sender揭示其选择的字符串s，Recevier验证如下：如果$f(s)=α$和$b(s)\oplus v = \sigma$，则Receiver接受Sender对$v$的承诺

统计绑定承诺

统计绑定承诺指的是对于承诺方案的隐藏性与绑定性，要求做到计算隐藏性（Computational-Hiding）和和统计绑定性（Statistically-Binding，有的书也将统计绑定称为完备绑定），具体而言，就是满足下列两个式子

$$ Computational \ hiding:\forall PPT\ R^* \ \forall\ m_1,m_2\\Com(m_1) ≌_C Com(m_2) $$

$$ Statistical \ binding:\forall C^*,\forall m_1\neq m_2\\ Pr[C^* \ wins\ the\ binding\ game]\leq neg(n) $$

这里提到了绑定游戏binding game，$C^*$赢得绑定游戏的方式是，生成一个绑定值$c$，使其在揭示阶段可以揭示为两个不同的消息与随机数的组合$(m_1,r_1)$和$(m_2,r_2)$，也就是

$$ Dec(c)=(m_1,r_1)\\ Dec(c)=(m_2,r_2) $$

不能赢得绑定游戏的意思是：$C^*$不能生成一个绑定值c，使得绑定值会在揭示阶段揭示为两个不同的消息

接下来介绍几个常见的例子

比如说ElGamal，可以令$Com_{g,h}=(g^r,h^r·g^m)$，这里h指的是ElGamal中的公钥

对于单向置换（OWP）而言，可以令$Com=(f(r),b(r)\oplus m)$，这里的b指的是串r中的某一个特定位，比如$b(r)=LSB(r)$，或者$b(r)=MSB(r)$

这里提到了统计与计算两个要求，同一个承诺方案只能同时有一个性质是统计的，也就是只能是统计绑定计算隐藏，或者是计算绑定统计隐藏的，不能同时是统计绑定和统计隐藏（但是可以同时是计算绑定计算隐藏）

基于承诺的交互式证明

直接介绍概念有点枯燥，讲个例子可能会好一些

假设采用哈密顿图证明系统，图采用邻接矩阵的方式存储

先说一个要点，对于邻接矩阵存储的图，若这个图有哈密顿回路，则这个条回路通过邻接矩阵表示时，其恰有与顶点数量相同的1，且这些1均在不同行不同列，就像下面这样

协议执行时，需要承诺整个图，由于邻接矩阵的图只需要0和1表示，因此需要承诺N*N比特，得到一个承诺后的矩阵，就像下面这样

在揭示阶段，如果说需要解开一个哈密顿回路的承诺，则只需要解开回路对应的边即可，也就是解开邻接矩阵中对应的比特，就像下面这样

如果需要揭示整个图，那就揭示整个图

OK，有了承诺做基础，就可以开始协议了，具体的协议流程如下

协议开始之前，Prover和Verifier有一个公共输入的图G，且$G\in HAM$（意思就是G有哈密顿回路），Prover知道图G的一条哈密顿回路w

首先由P随机选择一个随机置换$\pi \in_R S_n$，然后将图G做置换，并对置换后的图做承诺，并发送给Verifier

$$ c=Com(\pi(G)) \tag{P→V} $$

然后Veriier随机选取一个比特$b\in_R \{0,1\}$，发送给Prover，接下来有两种情况

如果b=0：则Prover解开承诺c的一部分，即解开置换后的图的哈密顿回路

$$ b=0:\ u \in Dec(c) \tag{P→V} $$

然后Verifier验证u是否是一个哈密顿回路

如果b=1：则Prover解开整个图，并发送其选择的随机置换$\pi$，也即

$$ b=1: \ \pi,H=Dec(c) \tag{P→V} $$

之后Verifier验证解开承诺的图H是否与原图G经过置换$\pi$得到的图一致

需要注意的是，Verifier不仅需要验证Prover哈密顿证明系统是否正确，还需要验证承诺是被正确解开的

对于这个协议，其满足之前提到的零知识的三个特性

  • 完备性：Prover可以确保$G_0$和$G_1$是合法的
  • 可靠性：如果Prover不知道这个图的哈密顿回路，他只能确保$G_0$或$G_1$是合法的（保护Verifier）
  • 零知识性：对于给出的b，总是可以确保$G_b$是合法的（保护Prover）

承诺证明的模拟

首先，模拟器得到了b的样本值（比如通过Rewind的方式得到），然后对于b的值，模拟器令承诺值$G_b$是合法的，之后再提交一个对0串（0-string）的承诺

之后Verifier（带*代表是作弊的Verifier）根据收到的承诺c，向Prover（Simulator）返回一个b'（这里可以将$V^*(c)$视为$V^*$对收到的c作用的一个随机函数）

Simulator根据收到的b'，检查是否与之前的样本值一致，如果一致，则解开对应的承诺，否则重复上述过程

后记

比特承诺是构建ZK很重要的一个概念，本篇文章主要是简单介绍了一下比特承诺的基础，还有一些很重要的概念没有介绍

不过终于算是把负基础补到零基础了，之前比特承诺和统计隐藏这些知识都无，看论文看的一头雾水，更别说看数学符号了，现在再回看论文应该大致可以理解论文讲的协议了

下篇文章再结合一些其他的例子继续讲一下比特承诺，还有之前提到的并行零知识

本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正

参考文章

$[1]$ 陈原。计算复杂性理论导引 $[M]$. 西安电子科技大学出版社.

$[2]$ （以）Odeb Gol­dre­ich 著；温巧燕，杨义先译。密码学基础 $[M]$. 北京：人民邮电出版社.2003.

$[3]$ Cyn­thia Dwork, Moni Naor, Amit Sa­hai:Con­cur­rent Zero-Knowl­edge. STOC 1998: 409-418

$[4]$ The 9th BIU Winter School on Cryptography | BIU Cyber Center