干货 | 什么是zkSNARKs:谜一般的“月亮数学”加密,Part-2

Ajian   |     |   1307 次阅读


干货 | 什么是zkSNARKs:谜一般的“月亮数学”加密,Part-1


两种证明:真理 vs 知识

上面的几个案例让我们对于零知识证明的理论及其应用有了一定的认识。但零知识证明该如何实际应用到区块链中?为什么大家对 Zcash 采用零知识证明(ZKP)大为赞赏,并非常期待以太坊能够做同样的事?在我们进入更深一层的讨论前,有件非常重要的事要先搞清楚。

我们使用零知识证明,究竟想证明什么?从广义的角度来看,我们可以用零知识证明来论证两种陈述,分别是关于真理的陈述和知识证明的陈述。

  • 真理:就是我们了解的关于宇宙的内在真理,而你想用零知识证明去论述。比如“数字X包含于集群Y”。
  • 知识证明:你也许会想证明自己拥有某种具体知识,同时不希望将知识透露出去。比如前面章节提到的关于数独、瓦尔多,和阿里巴巴的洞穴,都属于知识证明。

请注意这两者之间的不同。在加密数字货币领域,我们主要关注第二种,也就是”知识“的证明。在20世纪80年代,由 laus-Peter Schnorr 提出的 Schnorr 身份识别协议,成为利用零知识证明进行“知识证明”的重大突破之一。这项协议奠定了当代密码学中密钥签名的基础,同时也展示了零知识证明是如何被整合到现代密码学实践中的。

Schnorr 身份识别协议

为了方便理解 Schnorr 身份识别协议,让我们再次请出我们的老朋友,Anna 和 Carl!假设现在 Anna 已经对全世界宣布自己拥有一份公钥(编者注:疑是作者笔误,应为“私钥”),并且可以用这份公钥(同上句编者注)来收发讯息。而作为一个怀疑论者,Carl 认为 Anna 说谎。Anna 唯一能自证清白的办法,就是展示自己的私钥给 Carl 看,但她不想透露自己的私钥。

那么 Anna 该如何在不展示私钥的同时证明自己的确拥有该私钥呢?这就要用到 Schnor身份识别协议了。在我们开始研究协议运作之前,有些参数你需要知道。

  • p = 任何的素数
  • q = p-1 的因数
  • 数字 "a",使得 a^q =1 mod p

将这三个参数记下,因为在 Schnorr 协议中,这三个参数是全局变量。这表示在协议中的任意一个具体场景下,所有人都知道这三个参数是什么。

现在我们来看看两个密钥,私钥我们表示为"s",而公钥表示为"v"。

s 可以是任何值,且要满足 0<s<q。 v = a^(-s) mod q

公钥 v 和参数 p、q、a 一样,都是全局的,也就是所有人都知道。但是私钥 s 只有 Anna 一个人知道。

现在我们已经定义了接下来要用到的变量,让我们来看看 Anna 如何在不透露私钥的情况下,进行信息交换来证明自己的声明。

Anna 签名,并发送一条加密消息。

假设 Anna 使用她的私钥加密一条消息 "M",并发送给 Carl。在 Schnorr 协议下,这个过程是这样进行的:

首先,她要选择一个随机数 "r",使 0<r<q,接着计算X值: X = a^r mod p

接着 Anna 将 X 值与她要发送的消息"连接(concatenate)"。连接的意思很单纯,比如我们有两个字符串 "hello" 和 "world",将两个字符串连接就会得到 "hello world",也就是二合为一。

Anna 将 X 值和消息 M 连接得到 M||X。然后对 M||X 进行哈希运算,得到相应哈希值"e"。

计算如下: e = H(M||X) ,H()是哈希函数。

然后进行最后一步计算,得到 y : y = (r + s*e) mod q

现在 Anna 可以长吁口气,所有的计算结束了。她将下列信息发送给Carl:

  • 消息"M"
  • 数字签名 e 和 y

Carl 接收到消息并开始检查 Anna 的知识证明。重新汇整下,现在 Carl 从 Anna 那儿拿到了消息(M) 和数字签名(e 和 y)。除此之外,Carl 同样知道早就公诸于众的几个参数,分别是:

  • Anna 的公钥 "v"。
  • Anna 选择的一个素数 "p"。
  • 根据 Anna 选择的素数p,得到 (p-1) 的因数 q。
  • 同样根据 Anna 选择的素数p,得到 a,a^q = 1 mod p 。

现在 Carl 计算 X’:

X'= a^y * v^e mod p

接着我们进行一些简单的替换:

我们已经有 v = a^(-s) ,接着进行等式的互换:(校注:这里可能是作者手误了,原式应为 v = a^(-s) mod q 。)

  • X' = a^y * a^-se = a ^ (y-s*e)
  • 我们已经知道 y = r + s*e
  • 这意味着 r = y - s*e

我们将这个值带入上面等式中:

  • 得到:X'= a^r
  • 前面我们已经知道: X = a^r
  • 得 X = X'

因为 Carl 没有接收到 X 值,所以他不知道 X 是多少。现在他手上的讯息有:消息 M、数字签名(e 和 y),还有全局参数(公钥v,参数p、q、a)。

虽然 Carl 没有看到过 X,但是他知道如果 Anna 陈述为真,X‘ 就会与 X 相等。

而 Carl 也知道消息M。所以接着他会以下面的方式解决问题

计算 e = H ( M||X')

请注意,我们前面已经计算过 e = H(M||X)

所以根据此逻辑,如果两次计算的 e相同,这就表示 X = X'。这也表示 Anna 没有说谎:她的确拥有私钥。

现在,让我们基于零知识证明的三个特征,重新过一遍整个验证流程。

  • 完整性:因为最终 X' = X,所以 Carl 会相信 Anna 是诚实的。
  • 可靠性:整个过程中,Anna 只能靠着私钥来证明自己的陈述,试图撒谎没有用。
  • 零知识性:Carl 没有任何机会知道 Anna 的私钥是什么。

在现实世界中,Schnorr 协议使得零知识证明在密码学应用上大放异彩。

如何让零知识证明“非交互地”运作?

早期的零知识证明验证系统存在一个大毛病,也就是在进行验证的时候,要求证明者和验证者必须同时在线。换句话说,整个过程是“实时交互的”。这导致整个系统工作低效,且难以扩展。因为验证者不可能总是和证明者保持同时在线!我们需要一个系统来改善零知识证明的效率。

在1986年,Fiat 和 Shamir 发明了 Fiat-Shamir 启发式方法,并成功将“交互式”零知识证明升级为允许“非交互式”进行的零知识证明。这个方法使得整个零知识证明协议不再需要交互运行,而且这个方法背后的过程其实非常简单。

我们举个例子,重新捋一捋在 Fiat-Shamir 方法出现之前,零知识证明是如何进行的:

我们使用简单离散对数来说明。

  1. Anna 想要向 Carl 证明,她知道一个值 x,使得对一个底数 g,可以得到 y = g^x。
  2. Anna 从 Z 集合中随机挑选一个数 v,并计算 t = g^v ,接着发送给 Carl。
  3. Carl也从 Z 集合中随机挑选一个数 c,回传给 Anna。
  4. Anna拿到 c之后,计算 r = v-c*x ,再把结果 r 回给Carl。
  5. Carl接着验证 t= g^r * y^c 是否成立。(因为 r= v-c*x ,又 y= g^x ,经过替换 g^(v-c*x)* g ^ c*x = g^v = t
  6. Carl从头到尾都不知道 x值,他仅仅是确认 t = g^r * y^c 是否成立,成立则表示 Anna 的陈述也是成立的(知道 x 的值)。

虽然上述过程是零知识证明,但是这里的问题在于 Anna 和 Carl 始终必须保持在线。

Anna 该怎么做,才能既完成零知识证明,又不需要 Carl 始终在线呢?基于 Fiat-Shamir 方法,她可以利用简单的密码学哈希函数来解决问题。

我们现在重现上面的步骤,不过这次要在非交互的情况下完成。

  • Anna 想要向 Carl 证明,她知道一个值 x,使得对一个底数 g,可以得到 y = g^x
  • Anna 从 Z 集合中随机挑选一个数 v,并计算 t = g^v
  • Anna 计算 c = H(g,y,t) ,H() 是哈希函数。
  • 接着,Anna 再计算 r = v – c*x
  • Carl,或是任何人,都可以检查 t = g^r * y^c 是否成立。

如你所见,这么一来,零知识证明就在非交互的情况下完成了。这同时也是Zk-Snarks的理论基础。

Zk-Snarks的作用

Zk-Snarks,全称为“零知识下简明的非交互知识论证”。它在现代区块链技术中起了巨大的作用。要解释它的应用之前,我们必须先了解智能合约如何运作。简单来说,智能合约实现了一种资金托管功能,使得某些操作在特定条件被满足时自动触发。

举例来说,Anna 与 Carl 签署了一份智能合约,Anna 在里面放了 100ETH。并约定 Carl 必须完成一项特定任务,就可以得到智能合约里的 100ETH。

如果 Carl 要完成的任务属于多重的机密任务,整个情况就会变得复杂。假设你已经和 Anna 签署了智能合约,获得报酬的条件是完成任务 A、任务 B,以及任务 C。现在你虽然已经完成任务,但是你不想透露关于这些任务的细节给竞争对手知道,因为这是公司机密,这时候你该怎么做?

这时候就该 Zk-Snarks 出马了。Zk-Snarks 被部署在智能合约中,并提供你已经完成这些任务的证明,当然证明过程不会透露任何消息。这对于保护你个人和公司的隐私都有莫大的帮助。验证过程中Zk-Snarks也只会公开部分而不是全部信息,公开的部分足够证明你的陈述。

ZkSnarks 运作原理

Zk-Snarks由三种算法,G、P、V组成。

G 是密钥生成算法,它接受的输入包含一个参数 “lamda”(必须保密,在任何情况下都不能被公开),和一个程序 C。然后生成证明密钥 pk,和验证密钥 vk。这两个密钥都是公开的,任何需要使用的人都能取得。

P 算法扮演证明者角色,需要三个输入:证明密钥 pk、公开的任意输入值 x,还有想证明的知识的陈述,这里我们用“w”代表。P 算法生成证明 prf,使得:

prf = P(pk, x,w)

验证者算法 V 会返回一个布尔变量。布尔变量只会返回两种结果:为真(TRUE),或为假(FALSE)。验证算法同样需要三个输入:验证密钥 vk,公开的输入值 x,和证明prf:

计算 V(vk,x,prf)

......如果返回TRUE,就说明证明者是对的,反之则返回false。

关于参数 Lambda 必须再次提醒,Lamda 的值必须始终保密,因为任何人都可以使用它来生成假的证明。即使造假者不知道真正的陈述 w,这些使用 Lambda 生成的假的证明也会返回TRUE。

ZkSnarks的功能实现

为了说明 Zk-Snarks 的功能实现,我们将参考 Christian Lundkvist 为区块链公司 Consensys 所写的文章,并使用与该文章相同的示例函数。示例函数如下:

function C(x, w)

{

return ( sha256(w) == x );

}

函数 C 需要输入两个参数,一个是公开的哈希值“x”,另一个是需要被验证的私密陈述“w”。如果 w 的 SHA-256 哈希值和 “x” 相同,则函数C返回TRUE;反之则返回FALSE。(SHA-256就是应用于比特币网络中的那个哈希函数。)

让我们再一次,请出老朋友 Anna 和 Carl。Anna 扮演证明者(Prover),而 Carl 继续扮演多疑的验证者(Verifier)。

作为验证者,对于 Carl 而言,他需要做的第一件事,是通过密钥生成算法 G 生成证明密钥 (pk) 和验证密钥 (vk)。

为此,Carl 还得先生成一个随机数"Lambda"。如同前面说明的,Carl 必须非常小心地保管“Lambda”,因为只要 Lambda 被 Anna 知道了,她就能伪造正确的证明。

生成密钥过程如下:

G(C, lambda) = (pk , vk)

现在两个密钥已经有了,接着 Anna 必须证明自己的陈述的有效性。她将使用证明算法 P 来生成需要的证明。她必须证明自己的陈述 w,在经过哈希运算(SHA-256)后,能得到输出 x。证明算法 P 产生证明的行为如下所示:

prf = P( pk, x, w)

现在 Anna 已经有了证明(prf),她将把这个值交给 Carl 来进行 Zk-Snarks 的验证算法环节。

如下所示:

V( vk, x, prf)

现在,vk 是验证密钥,x 是已知的哈希值,prf 是 Anna 交给 Carl 的陈述证明。如果验证算法返回 TRUE,则表示 Anna 是诚实的,她的确拥有私密陈述“w”;如果返回FALSE,则表示 Anna 说谎,她并不知道“w”是什么。

ZkSnarks 在加密货币中的应用

-图片来源:Zcash-

Zcash,是 Zerocoin Electric Coin 公司于2016年9月9日推出的加密货币,也是第一个将区块链技术与 ZkSnarks 结合的加密货币。Zcash 的主旨是提供用户绝对安全且隔离的交易空间,不向任何人透露交易细节(比如地址)。

以太坊想要在“大都会(Metropolis)”阶段,ZkSnarks 整合入以太坊。他们的做法是与 Zcash 建立合作联盟,并互通有价值的资源。Zcash 的首席开发者,Zooko Wilco,在上海的 DevCon2(第三届全球以太坊开发者峰会)上,发表了关于这个合作联盟未来发展的演讲。在他的演说中,提到三种 Zcash(可以延伸到zk-snarks)与以太坊整合的方法:

第一种方法叫做 Baby Zoe(Zoe 即“Zcash on Ethereum”的首字母缩写)。这个方法打算在以太坊网路中增加 zk-snarks 预编译器,并在以太坊上部署一个小型的 Zcash 智能合约。这要考虑以太坊是否能在其区块链上创建兼容 zk-snarks 的 dAPP。

第二种方法是将以太坊的可计算功能集成到 Zcash 的区块链上。根据 Wilcox 的演讲,他表示以太坊最伟大的部分就是可计算功能,而大家也想知道,这个功能能否能集成到基于 zk-snarks 的区块链,像是 Zcash;以及能否在基于零知识证明的区块链网路里创建 dAPP?这些都是公众期待看到的。

第三种,也是最令人兴奋的,是 Alchemy 计划。这个方法想要连接两个区块链网络并实现互操作性,比如跨链的转移。Zcash 打算克隆 BTC Relay——在以太坊区块链上,由以太坊脚本写成的比特币轻客户端项目。Zcash 会基于相同概念来克隆,也就是在以太坊上创建 Zcash 轻客户端。

如果任何一种方法能成功,这将会是世界上第一个以零知识证明为原生生态,来辅助创建dAPP的去中心化数字货币系统!

展望未来

毫无疑问,引入零知识证明将会为以太坊带来巨变。随着我们的世界正朝着愈发开放、互联、受监督的方向前进,任何形式的隐私保护都会越来越受到重视。后续的整合该如何进行仍有待研究,但单单就概念本身,就足以令人感到兴奋!


原文链接: https://blockgeeks.com/guides/what-is-zksnarks/
作者: Ameer Rosic
翻译&校对: IAN LIU & Elisa

本文由作者授权 EthFans 翻译及再出版。


你可能还会喜欢:

Zcash对以太坊来说意味着什么?
干货 | 什么是以太坊大都会:终极指南
Vitalik Buterin问答集

 
0 人喜欢