零知识证明(Zero-Knowledge Proof)是一种创新型的密码学协议，可以让证明方在不泄露隐私信息的前提下，证明自己拥有这项信息。零知识证明系统中有证明者(Prover)和验证者(Verifier)两个角色，证明者拥有一个秘密信息,想要让验证者相信自己拥有这个信息,而不泄露实际信息。证明者根据秘密信息生成一个证明,该证明不包含实际的秘密信息。这个证明通常经过数学运算构造,可以证明证明者确实拥有这个秘密信息。验证者收到证明后，通过预设的验证算法来检查证明的正确性，但验证者并不能从证明中获取实际秘密信息。证明者能通过验证,就可以说验证者相信了证明者拥有秘密信息,而没有获得任何有关秘密的实际信息，这就是证明的“零知识性”。

随着区块链交易所加密货币交易量的增长，用户需要确认交易所拥有足够的储备金来支持交易。但是用户资产详细数据、储备金的具体数额是交易所不希望公开的敏感信息，零知识证明可以做到在不暴露具体数额的情况下证明交易所拥有足够的储备金和具有相应的偿付能力，经过严格约束设计的证明电路可以确保最终的证明是由严谨的计算过程得出，杜绝证明造假的情况发生。采用这种先进的密码学技术可以大大增强用户对交易所的信任，同时增强交易所资金透明度，起到防范金融风险的作用。与传统的外部审计相比,零知识证明不需要将全部储备资产移交第三方审计,大大降低了操作成本和资金风险。这使得储备金证明成为一种常规化的进程，可以频繁进行，定期披露。

zksnark及Groth16原理简介

引言：

什么是zksnark？

首字母缩略词 zk-SNARK 代表“零知识简洁非交互式知识论证”，指的是一种证明结构，在这种结构中，人们可以证明拥有某些信息，例如秘密密钥，而无需透露该信息，并且两者之间没有任何交互。

“零知识”证明允许一方（证明者）向另一方（验证者）证明一个陈述是真实的，而不会透露任何超出陈述本身有效性的信息。例如，给定一个随机数的散列，证明者可以让验证者相信确实存在一个具有该散列值的数字，而无需透露它是什么。

在零知识“知识证明”中，证明者不仅可以说服验证者该数字存在，而且他们实际上知道这样一个数字——同样，无需透露有关该数字的任何信息。“证明”和“论证”之间的区别是相当技术性的，我们在这里不深入探讨。

“简洁”的零知识证明可以在几毫秒内得到验证，即使对于非常大的程序的陈述，证明长度也只有几百字节。在第一个零知识协议中，证明者和验证者必须来回通信多轮，但在“非交互式”结构中，证明由证明者发送给验证者的单个消息组成。

以下是现存的zk-snark简介：

Groth16：Groth16是目前最快、数据量最小的zk-SNARK，被用于Zcash等。Groth16不是通用的，其设置需要绑定到一个特定的电路。由于其速度和证明的小数据量，因此常常被新的zk-SNARK拿来比较性能。Groth16论文链接：https://eprint.iacr.org/2016/260

Sonic：Sonic是一个早期的通用zk-SNARK协议。论文发表于2019年1月。Sonic支持通用、可升级的参考字符串。Sonic的证明大小固定，但是验证成本高。理论上可以将多个证明分批验证以获得更好的性能。下面列举的许多新的zk-SNARK都是基于Sonic。Sonic论文链接：https://eprint.iacr.org/2019/099

Fractal：Fractal 是一种允许递归的zk-SNARK。通过对电路的预处理实现了透明设置。证明最大250KB，这笔其他构建生成的证明都要大的多。Fractal论文链接: https://eprint.iacr.org/2019/1076

Halo：Halo支持递归证据组织，无需可信设置。与其他新的zk-SNARK构建不同，Halo的验证时间是线性的。Halo论文链接: https://eprint.iacr.org/2019/1021

SuperSonic：SuperSonic 是Sonic的改进版，是第一个在验证时间和证明数据量方面实用化的透明zk-SNARK。SuperSonic论文链接: https://eprint.iacr.org/2019/1229

Marlin：Marlin 是Sonic的改进版，证明时间缩短10倍，验证时间缩短4倍。Marlin论文链接: https://eprint.iacr.org/2019/1047

Plonk：Plonk也是Sonic的改进，证明时间缩短5倍。Plonk论文链接: https://eprint.iacr.org/2019/953

我们的零知识证明采用的是groth16，下面是对该方案的详细介绍：

实现路线：

我们通过：如下六个流程来完成我们的证明。

这篇文档用一个现实的简单的例子来做说明帮助大家更好理解：

例子：如何证明我们知道方程x^3+x+5=35的解。

实现过程及简单原理：

因为我们的问题本身就是证明我们知道一个方程的解，那么我们直接从第二步：满足的计算方程组->r1cs电路开始进行说明。

2.1 满足的计算方程组->r1cs电路：

首先，将上面的计算方程组拆分成一次只做一次加减乘除中的一种运算的方程组。

E.g.：计算x^3+x+5=35 可以拆分为：

(1)X0 = x*x

(2)Y0 = X0*x

(3)Y1 = Y0+x

(4)Out = Y1+5

于是把x^3+x+5=35拆分成了四个约束(constraints)，换句话说，当我们能够证明我们同时满足上面的四个约束的时候，我们也就能够证明我们知道x^3+x+5=35的解。

之后我们需要使用一个向量组（a,b,c）与解向量s满足如下条件<s,a>*<s,b> = <s,c>。其中<*,*>表示向量内积。

为了满足上面所说的解向量s与向量组(a,b,c)所满足的关系，我们首先构造解向量s=(1,Out,x,X0,Y0,Y1)=(1,35,3,9,27,30)

由此我们可以根据解向量s 构造我们所需要的向量a1=(0,0,1,0,0,0)，b1=(0,0,1,0,0,0), c1=(0,0,0,1,0,0)。当我们分别把a1 b1 c1 带入<s,a>*<s,b> = <s,c>，并把s用(1,Out,x,X0,Y0,Y1)进行表示，我们可以很容易的得到式子(1) X0 = x*x，那么我们就得到了式子（1）的向量表达方式。同理，我们也可以通过构造如下的向量分别得到式子（2）（3）（4）所对应的向量表达方式。

a2=(0,0,0,1,0,0)，b2=(0,0,1,0,0,0), c2=(0,0,0,0,1,0)

a3=(0,0,1,0,1,0)，b3=(1,0,0,0,0,0), c3=(0,0,0,0,0,1)

a4=(5,0,0,0,0,1)，b4=(1,0,0,0,0,0), c4=(0,1,0,0,0,0)

所以当我们的解向量s输入正确的时候，就代表我们能够有这个方程组正确的解。

由此我们得到了方程组转r1cs电路的过程。（拆分+构造向量）也就是说，我们把给出方程解的问题变成了求r1cs电路相等的问题。上面介绍的内容：电路定义对应在我们公开项目里面的：circuit/group_user_circuit.go里面的Define()函数；电路编译成r1cs对应在我们公开的项目里面的src/keygen/main.go 里面的frontend.Compile（）函数。

如果想具体了解r1cs电路的问题，我们推荐阅读文献【1】。

1. r1cs电路—>QAP问题：

但是通过这四个向量组解决这个问题显得过于复杂，我们希望使用更加简单的办法

进行解决，由此我们需要把r1cs电路转化为QAP问题。

我们先将刚才得到的四个向量组在下方列出来：

a1=(0,0,1,0,0,0)，b1=(0,0,1,0,0,0), c1=(0,0,0,1,0,0)

a2=(0,0,0,1,0,0)，b2=(0,0,1,0,0,0), c2=(0,0,0,0,1,0)

a3=(0,0,1,0,1,0)，b3=(1,0,0,0,0,0), c3=(0,0,0,0,0,1)

a4=(5,0,0,0,0,1)，b4=(1,0,0,0,0,0), c4=(0,1,0,0,0,0)

从向量a1，a2，a3，a4分别选择第一个点：0,0,0,5构成y0，y1，y2，y3，选择1，2，3，4构成x0，x1，x2，x3。

通过拉格朗日插值可以构造多项式fa_0(x) 使得fa_0(1)=0,fa_0(2)=0,fa_0(3)=0,fa_0(4)=5

同理可以构造fa_1(x)…,fc_6(x)共18个多项式。

将这18个多项式按照如下方式排列：

向量a=(fa_0(x),fa_1(x),fa_2(x),fa_3(x),…,fa_6(x))

向量b以及向量c按照a的方式构造出来，由此我们得到三个6维向量（元素为多项式）分别取x=1,2,3,4即可带入到我们的向量a，b，c就可以还原我们的每一个向量组（a1,b1,c1）,…,（a4,b4,c4）。

这个时候当我们需要验证r1cs中的等式<s,a>*<s,b> = <s,c>的时候，只需要分别带入x=1，x=2，…，x=4进行验证都成立即可。（此时向量(fa_0(x),fa_1(x),fa_2(x),fa_3(x),…,fa_6(x))又变回了数字向量）。

但是分别带入太麻烦了，如何一次验证呢？

我们这里令Z(x)=(x-1)(x-2)(x-3)(x-4). 这里是对上面选择的x0，x1，x2，x3进行插值

当x为1，2，3，4的时候，我们的<s,a>*<s,b> = <s,c>成立也就是A（x）*B（x）-C（x）=0=H（x）Z（x）

其中A（x）=<s,a>，其中a是上面的向量a=(fa_0(x),fa_1(x),fa_2(x),fa_3(x),…,fa_6(x))，B（x），C（x）同理。

也就是说当我们验证了A（x）*B（x）-C（x）能够被Z（x）整除的时候，我们的电路r1cs就被验证了。由此我们完成了r1cs到QAP问题的转化。当我们完成了QAP问题的验证之后，也就代表我们完成了r1cs电路的验证，也就代表我们证明了我们知道原方程x^3+x+5=35的解。

上面是一个QAP问题的实例。

我们对上面的符号以及现实问题做一个一一对应。里面的A，B，C分别代表我们上面所讲的A（x），B（x）和C（x）。D代表的是我们上面展示的插值空间即D={1，2，3，4}。Z_D(x)即Z（x）=（x-1）（x-2）（x-3）（x-4）。其中小的zi代表的是我们的秘密向量s=(1, Out,x,X0,Y0,Y1)每一个点的值，即zi=si。hi代表上方所讲的H（x）的系数。通过把我们的秘密向量s按照上面的拆分方式进行拆分，secret witness向量w= (x,X0,Y0,Y1)，public witness向量x=(1,Out)。

上述过程通过使用开源项目中src/keygen/main.go()里面的函数groth16.SetupLazyWithDump()之中的部分功能实现。

如果想更加具体地了解QAP问题我们推荐阅读文献【2】。

1. QAP问题->生成证明：

在介绍该流程之前，我们首先对使用的符号进行说明：

我们通过QAP问题按照如下的方法使用prover生成我们需要的证明：

我们根据上面的方法使用prover生成我们需要的证明文件proof（prover做的只是随机选择数域F里面的元素，并对他们按照我们定义好的映射方式进行计算），将其保存在数据库中。

1. 生成证明->验证：

当我们的用户需要验证的时候，只需要从数据库中调取我们的proof以及用户验证需要的vk，以及input x对上方verifier里面的等式进行验证，其中x就是上面所说的public witness(1,Out）=(1,35)。如果等式成立，就说明我们的QAP问题验证成立，也就说明我们知道上方所提到的x^3+x+5=35的解。因为我们的多项式里面的元素都是使用的椭圆曲线群（group）里面的点，所以并不会泄漏任何其他的信息，由此保证了我们和用户的安全。

2.3生成证明的内容对应开源项目中src/keygen/main.go()里面的函数groth16.SetupLazyWithDump()进行实现。2.4证明内容通过开源项目中src/verifier/main.go进行实现。

如果想要了解具体的证明和验证正确性和安全性问题，我们推荐阅读文献【3】。

以上就是我们的zksnark groth16的整个证明思路。具体的zkpor内容，我们只需要将现实的问题抽象成方程组，按照上面的流程一步一步向下即可。对于我们的zkpor的具体方程（约束设计）我们推荐阅读：《基于零知识证明的PoR原理与实现》。

参考文献：

【1】Howard Wu, Wenting Zheng, Alessandro Chiesa, Raluca Ada Popa, and Ion Stoica. 2018. DIZK: a distributed zero knowledge proof system. In Proceedings of the 27th USENIX Conference on Security Symposium (SEC'18). USENIX Association, USA, 675–692.

https://eprint.iacr.org/2018/691.pdf

【2】Gennaro, Rosario et al. “Quadratic Span Programs and Succinct NIZKs without PCPs.” IACR Cryptology ePrint Archive (2013).

https://eprint.iacr.org/2012/215.pdf

【3】Jens Groth. 2016. On the Size of Pairing-Based Non-interactive Arguments. In Proceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 9666. Springer-Verlag, Berlin, Heidelberg, 305–326.

https://eprint.iacr.org/2016/260

APP内打开

为什么要使用零知识证明来做储备金证明？

2023/09/14 08:27

资产审计

zksnark及Groth16原理简介

引言：

什么是zksnark？

以下是现存的zk-snark简介：

Halo：Halo支持递归证据组织，无需可信设置。与其他新的zk-SNARK构建不同，Halo的验证时间是线性的。Halo论文链接: https://eprint.iacr.org/2019/1021

SuperSonic：SuperSonic 是Sonic的改进版，是第一个在验证时间和证明数据量方面实用化的透明zk-SNARK。SuperSonic论文链接: https://eprint.iacr.org/2019/1229

Marlin：Marlin 是Sonic的改进版，证明时间缩短10倍，验证时间缩短4倍。Marlin论文链接: https://eprint.iacr.org/2019/1047

Plonk：Plonk也是Sonic的改进，证明时间缩短5倍。Plonk论文链接: https://eprint.iacr.org/2019/953

我们的零知识证明采用的是groth16，下面是对该方案的详细介绍：

实现路线：

我们通过：如下六个流程来完成我们的证明。

这篇文档用一个现实的简单的例子来做说明帮助大家更好理解：

例子：如何证明我们知道方程x^3+x+5=35的解。

实现过程及简单原理：

因为我们的问题本身就是证明我们知道一个方程的解，那么我们直接从第二步：满足的计算方程组->r1cs电路开始进行说明。

2.1 满足的计算方程组->r1cs电路：

首先，将上面的计算方程组拆分成一次只做一次加减乘除中的一种运算的方程组。

E.g.：计算x^3+x+5=35 可以拆分为：

(1)X0 = x*x

(2)Y0 = X0*x

(3)Y1 = Y0+x

(4)Out = Y1+5

于是把x^3+x+5=35拆分成了四个约束(constraints)，换句话说，当我们能够证明我们同时满足上面的四个约束的时候，我们也就能够证明我们知道x^3+x+5=35的解。

之后我们需要使用一个向量组（a,b,c）与解向量s满足如下条件<s,a>*<s,b> = <s,c>。其中<*,*>表示向量内积。

为了满足上面所说的解向量s与向量组(a,b,c)所满足的关系，我们首先构造解向量s=(1,Out,x,X0,Y0,Y1)=(1,35,3,9,27,30)

a2=(0,0,0,1,0,0)，b2=(0,0,1,0,0,0), c2=(0,0,0,0,1,0)

a3=(0,0,1,0,1,0)，b3=(1,0,0,0,0,0), c3=(0,0,0,0,0,1)

a4=(5,0,0,0,0,1)，b4=(1,0,0,0,0,0), c4=(0,1,0,0,0,0)

所以当我们的解向量s输入正确的时候，就代表我们能够有这个方程组正确的解。

如果想具体了解r1cs电路的问题，我们推荐阅读文献【1】。

1. r1cs电路—>QAP问题：

但是通过这四个向量组解决这个问题显得过于复杂，我们希望使用更加简单的办法

进行解决，由此我们需要把r1cs电路转化为QAP问题。

我们先将刚才得到的四个向量组在下方列出来：

a1=(0,0,1,0,0,0)，b1=(0,0,1,0,0,0), c1=(0,0,0,1,0,0)

a2=(0,0,0,1,0,0)，b2=(0,0,1,0,0,0), c2=(0,0,0,0,1,0)

a3=(0,0,1,0,1,0)，b3=(1,0,0,0,0,0), c3=(0,0,0,0,0,1)

a4=(5,0,0,0,0,1)，b4=(1,0,0,0,0,0), c4=(0,1,0,0,0,0)

从向量a1，a2，a3，a4分别选择第一个点：0,0,0,5构成y0，y1，y2，y3，选择1，2，3，4构成x0，x1，x2，x3。

通过拉格朗日插值可以构造多项式fa_0(x) 使得fa_0(1)=0,fa_0(2)=0,fa_0(3)=0,fa_0(4)=5

同理可以构造fa_1(x)…,fc_6(x)共18个多项式。

将这18个多项式按照如下方式排列：

向量a=(fa_0(x),fa_1(x),fa_2(x),fa_3(x),…,fa_6(x))

但是分别带入太麻烦了，如何一次验证呢？

我们这里令Z(x)=(x-1)(x-2)(x-3)(x-4). 这里是对上面选择的x0，x1，x2，x3进行插值

当x为1，2，3，4的时候，我们的<s,a>*<s,b> = <s,c>成立也就是A（x）*B（x）-C（x）=0=H（x）Z（x）

其中A（x）=<s,a>，其中a是上面的向量a=(fa_0(x),fa_1(x),fa_2(x),fa_3(x),…,fa_6(x))，B（x），C（x）同理。

上面是一个QAP问题的实例。

上述过程通过使用开源项目中src/keygen/main.go()里面的函数groth16.SetupLazyWithDump()之中的部分功能实现。

如果想更加具体地了解QAP问题我们推荐阅读文献【2】。

1. QAP问题->生成证明：

在介绍该流程之前，我们首先对使用的符号进行说明：

我们通过QAP问题按照如下的方法使用prover生成我们需要的证明：

1. 生成证明->验证：

2.3生成证明的内容对应开源项目中src/keygen/main.go()里面的函数groth16.SetupLazyWithDump()进行实现。2.4证明内容通过开源项目中src/verifier/main.go进行实现。

如果想要了解具体的证明和验证正确性和安全性问题，我们推荐阅读文献【3】。

参考文献：

https://eprint.iacr.org/2018/691.pdf

【2】Gennaro, Rosario et al. “Quadratic Span Programs and Succinct NIZKs without PCPs.” IACR Cryptology ePrint Archive (2013).

https://eprint.iacr.org/2012/215.pdf

https://eprint.iacr.org/2016/260

2023/09/14 09:52

2023/09/14 09:51

2023/02/22 06:09

2023/02/22 06:08

2023/02/22 06:08

公告

搜索

为什么要使用零知识证明来做储备金证明？

zksnark及Groth16原理简介

zksnark及Groth16原理简介