Numen | 零知识证明引论Part 4

导语

本文是零知识证明引论系列的第四部分。前面我们介绍了零知识证明的背景,概念以及一些核心数学工具。本文我们将介绍匹诺曹协议和Groth16

匹诺曹协议

其实,介绍完上述的核心数学工具,一个接近可工程实践版本的非交互性零知识证明协议已经呼之欲出了,这一套完整的过程就是目前一系列zkSnark算法的基础——[PGHR13],俗称匹诺曹(Pinocchio)协议[7]

这篇匹诺曹协议的论文的理论基础基于[GGPR13][8],主要偏工程实践,也是首次用C语言实现了一个接近可用的零知识证明库。

Numen | 零知识证明引论Part 4

1 引入随机偏移量

在具体实现上,和上述过程的区别是,为了防止暴力破解的可能(比如在特殊的情况下,系数的数量和取值范围都有限),prover在构造p(x)的过程中,加入一个随机偏移量δ:

令原多项式为:

Numen | 零知识证明引论Part 4

加入Numen | 零知识证明引论Part 4偏移量后为:

Numen | 零知识证明引论Part 4

Numen | 零知识证明引论Part 4

Numen | 零知识证明引论Part 4

那么对于新的验证组合:

Numen | 零知识证明引论Part 4

仍然可以通过验证,但是不暴露更多系数知识,无法被暴力破解。

2 协议全流程

• Setup

  •  选择生成元G和加密配对e
  • 将变量总数为 n 其中输入/输出变量数位 m 的函数Numen | 零知识证明引论Part 4,拍平为数字电路并针对每个门电路改写为R1CS的形式,再转换为阶数为 d(和门的数量有关) 大小为 n+1 的多项式形式(QAP)    Numen | 零知识证明引论Part 4
  • 选择随机数
    Numen | 零知识证明引论Part 4
  • 设置
    Numen | 零知识证明引论Part 4和操作数生成元
    Numen | 零知识证明引论Part 4
  • 设置 proving key:
Numen | 零知识证明引论Part 4
  • 设置 verification key
Numen | 零知识证明引论Part 4
  • 丢弃随机数
    Numen | 零知识证明引论Part 4

• Proving

  • 代入输入值 u,执行 f(u)计算获取所有的中间变量值

    Numen | 零知识证明引论Part 4

  • 把所有未加密的变量多项式赋值给

    Numen | 零知识证明引论Part 4,

    并对 R(x) 和 O(x) 做同样的计算

  • Numen | 零知识证明引论Part 4
  • 计算 

Numen | 零知识证明引论Part 4

  • prover 的变量值赋值给加密的可变多项式

Numen | 零知识证明引论Part 4

  • 为其 α对变换赋值

    Numen | 零知识证明引论Part 4

  • 为变量值一致性多项式赋值

    Numen | 零知识证明引论Part 4

  • 计算并提交证明

    Numen | 零知识证明引论Part 4


• Verification

  • 解析提供的证明为

    Numen | 零知识证明引论Part 4

  • 将输入/输出值赋值给 verifier 的加密多项式:

    Numen | 零知识证明引论Part 4

  • 可变多项式约束检查:

    Numen | 零知识证明引论Part 4

  • 变量值一致性检查:

    Numen | 零知识证明引论Part 4

  • 有效性计算检查:

    Numen | 零知识证明引论Part 4

总结成图:

Numen | 零知识证明引论Part 4

Groth16

Groth16(filecoin, Tornado.cash, 旧版Zcash)、PlONK(zkSync, Mina)和Halo(新版ZCash)等。其中应用最广泛的算法是Groth16。

Groth16算法是Jens Groth提出的一种匹诺曹协议的改进,相关论文[9]不仅对已有算法进行改进,而且讨论了基于配对的非交互式零知识论证的证明大小问题。Groth16因其精简的证明大小和高效的验证效率,已经完全具备了工程应用的条件,在早期的ZCash等匿名币项目中多有应用,是最经典的零知识证明算法,也是在区块链领域应用最早的算法。

算法的基本框架仍然是匹诺曹协议,分为setup、prooving、verication三个部分,其对于匹诺曹协议最大的升级是setup和verification部分,通过增强了一些双线性映射对的安全假设,缩减了Proving Key的大小,将K1的element数量从7个缩减为2个,进而减小了验证的数据量和计算量,从需要验证12个双线性对缩减为验证3个。

本文介绍了零知识证明协议的zkSnark族中可实用的最基础的两个协议——匹诺曹Groth16。近期在区块链上应用比较火热的Plonk和Sonic算法,都是基于Groth16在可信设置上做的优化和改进。希望读者能够结合之前的数学工具,了解这两个算法的基本原理,为下篇文章的理解奠定基础。下篇文章我们将重点介绍这些改进算法和一些比较典型的非Snark算法。 

参考文献

[7] Parno B, Howell J, Gentry C, et al. Pinocchio: Nearly practical verifiable computation[C]//2013 IEEE Symposium on Security and Privacy. IEEE, 2013: 238-252.

[8] R. Gennaro, C. Gentry, B. Parno, and M. Raykova, “Quadratic span programs and succinct NIZKs without PCPs,” in EUROCRYPT, 2013. Originally published as Cryptology ePrint Archive, Report 2012/215.

[9] Groth J. On the size of pairing-based non-interactive arguments[C]//Annual international conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2016: 305-326.

Numen | 零知识证明引论Part 4

Numen 官网
https://numencyber.com/ 
GitHub
https://github.com/NumenCyber
Twitter
https://twitter.com/@numencyber
Medium
https://medium.com/@numencyberlabs
LinkedIn
https://www.linkedin.com/company/numencyber/

原文始发于微信公众号(Numen Cyber Labs):Numen | 零知识证明引论Part 4

版权声明:admin 发表于 2023年3月9日 下午5:45。
转载请注明:Numen | 零知识证明引论Part 4 | CTF导航

相关文章

暂无评论

暂无评论...