扣丁书屋

从零开始学习 zk-SNARK(二)——多项式的非交互式零知识证明

目前的证明协议仍然存在一些缺陷,本文将会针对这些薄弱项进行改进,进而最终构造出关于多项式的零知识证明协议。本文重点:KEA,交互式零知识证明,非交互式零知识证明和 Setup。

导读

上一篇文章(多项式的性质与证明)中,作者介绍了如何利用多项式的性质来证明某个多项式的知识,相信大家已经对构造证明有了一些基本的认识。目前的证明协议仍然存在一些缺陷,本文将会针对这些薄弱项进行改进,进而最终构造出关于多项式的零知识证明协议。本文重点:KEA,交互式零知识证明,非交互式零知识证明和 Setup。 —— even@安比实验室


作者:Maksym Petkus 翻译 & 注解:even@安比实验室(even@secbit.io) 校对:valuka@安比实验室 本系列文章已获作者中文翻译授权。

限制多项式

上文说到,多项式的知识其实就是它的系数 c0, c1, …, ci 的知识。协议中我们是通过对秘密值 s 的幂的加密值再进行求幂来对系数进行“赋值”。我们已经限制了 prover 对 s 幂的加密值的选择, 但是这个限制并不是强制的 ,也就是说,prover 可以使用任何可能的方法找到满足下面等式的值 $$Z_p$$ 和 $$Z_h$$

$$Z_p=(Z_h)^{t(s)}$$

再用这两个值来代替 gᵖ 和 gʰ 将它交给 verifier。所以 verifier 需要能够证明 prover 给出的值就是用 s 幂的加密值而不是其它值计算出来的。

我们看一个由一个变量和一个系数组成的一阶多项式的简单例子,对应的 s 的加密值为 E(s) = gˢ。这里我们要做的就是确保 prover 是拿 s 的加密值,即 gˢ ,而不是其他值与系数 c 做同态相乘的。所以结果一定是这个形式(c 为任意值):

$${(g^s)}^c$$

解决这个问题的一种方法就是用另一个“变换”的加密值做同样的操作,充当类似算术中“校验和”(Checksum) 的作用,以此确保结果是原始值的求幂值。

这个是通过 Knowledge-of-Exponent Assumption (简称 KEA) 方法来实现的,在 [Dam91] 中有介绍,更精准一点(注意 a 和 α(alpha)这两个字符的不同)说:

a)Alice 有一个值 a,她想要 Bob 对其进行任意指数的求幂(这里 a 是一个有限域群的生成器),唯一的要求是只能对 a 进行求幂,为了保证这一点,她要:

  • 选择一个随机数 α

  • 计算 a' = $${a^\alpha}$$(mod n)

  • 提供一个元组 (a, a') 给 Bob, 然后让他对这两个值执行任意的求幂运算,返回结果元组 (b, b'),这里的指数 “α-变换” 依然保持不变,即 $${b^\alpha}$$ = b'(mod n)

b) 因为 Bob 无法从元组 (a, a') 中提取 α 的值,通过暴力破解也难以实现,那就可以推断 Bob 生成有效元组的唯一方法就是执行下面的步骤:

选择一个值 c

计算 b=(a)c(mod n) 和 b' = (a')c (mod n)

回复 (b,b')

--未完待续--

最多阅读

去中心化交易所(DEX)协议整理 1年以前  |  1529次阅读
详解以太坊默克尔压缩前缀树-MPT 1年以前  |  1341次阅读
理解以太坊 Gas 燃料和交易手续费 1年以前  |  1152次阅读
以太坊基础配置 1年以前  |  1132次阅读
以太坊交易回执-Receipt 1年以前  |  1074次阅读
墨客区块链(MOAC BlockChain) 助记词 1年以前  |  974次阅读
区块链小白书 1年以前  |  901次阅读
【译】完全理解以太坊智能合约 1年以前  |  868次阅读
比特币白皮书中文版 1年以前  |  868次阅读
以太坊账户模型 1年以前  |  831次阅读
Substrate 入门(5)- 区块头 1年以前  |  797次阅读
关于学分 1年以前  |  789次阅读
中国的区块链雄心:舍我其谁 1年以前  |  760次阅读
以太坊创世区块 1年以前  |  759次阅读
详解区块链P2P网络 1年以前  |  755次阅读

手机扫码阅读