浅谈零知识证明:简短无交互证明(SNARK)
2019-12-31 18:48:53 今日快报 浏览

 

上一期文章发表之后,非常惊讶有那么多小伙伴读完了表示喜欢。那么我们接着这期继续吧!这次,我们专注的聊一聊SNARK。

相信看完前一篇文章的朋友们会有一点很不解的地方:为什么我们可以如此简短的创建一个证明,并且证明很长的信息呢?在上课前我也有这同样的疑惑,甚至觉得这个是一个“黑科技”,不过相信大家看完这篇文章,就会知道如何去驾驭这个“黑科技”了。

在详细讨论之前,我们得稍微严肃一点,系统性的学习一下SNARK的基本构造。

SNARK的四步构造

因为SNARK的“黑科技”特性,想要构建一套简短证明系统,其实流程是略微有些复杂的。总结一下一共可以分为四步,我们来一步一步详细描述。

第一步:确定有限域

在构造之前,我们先需要确定一个可以包含所有我们想要计算的数字的大小的一个有限域(Finite Field)。用通俗易懂的话来说,我们需要选一个很大很大的数字p,确保这个数字比我们要解决的问题里的所有数字都大

如果以前了解过类似于RSA密码学的朋友们可能对这个概念不陌生。有限域就是给我们所有数字加了一个天花板,确定了整个数学系统的计算空间,类似于在电脑里如果我们想创建一个存数字的变量,我们需要思考到底是需要一个uint32_t(32位),还是一个uint64_t(64位)一样。所有超过有限域的值,都会直接溢出之后再倒回去从0开始。

在数学界,符合这个特性的计算空间其实有很多种,最常见的一种就是RSA算法里面用到的正整数求模一个大质数(integer mod p)。上文说到的找到一个数字p,其实就是一个很大的质数,然后我们可以用它来生成一个计算空间。

在确定计算空间之后,我们就可以真正开始SNARK的搭建了。

第二步:构建数学运算电路(Arithmetic Circuit)

当我们找到一个数字空间之后,我们下一步要做的事情,就是要把我们想要证明解决的问题用数学运算电路表示出来

什么是数学运算电路呢?我们先来看一看传统的逻辑电路。

上图表述的是一个与非门(NAND)的电路。先不用过多了解电路的用处,我们可以发现的是,两组输入信号分别通过了AND和OR这两个基础逻辑门。像AND和OR这样的基础逻辑门是逻辑电路的基础模块,通过拼加和堆叠我们可以实现任何复杂逻辑。

数学运算电路也是同理,只不过基础模块从逻辑门变成了数学运算。因为加法和乘法是最基础的数学运算,通过加法和乘法我们也可以近乎实现所有其他的运算方法,所以我们可以

声明:本文版权归原作者所有,发布此文为传递更多市场信息,不代表币块报的观点和立场,请自行参考。如作者信息标记有误,请第一时间联系我们处理!