Transparent 且 Post-quantum zkSNARKs

1. 引言

前序博客有:

  • SNARK原理示例
  • SNARK性能及安全——Prover篇
  • SNARK性能及安全——Verifier篇

在这里插入图片描述
上图摘自STARKs and STARK VM: Proofs of Computational Integrity。
在这里插入图片描述
上图选自:Dan Boneh 斯坦福大学 CS251 Fall 2023 Building a SNARK 课件。

SNARK方案由 Polynomial IOP(信息理论对象) ➕ 多项式承诺方案(密码学对象) 组成。

当前的Polynomial IOP主要分为三大类:

  • 1)基于interactive proofs(IPs)的Polynomial IOP:如Hyrax、vSQL、Libra、Virgo等。【 P P P无需做FFT运算】
  • 2)基于multi-prover interactive proofs(MIPs)的Polynomial IOP:如Spartan、Brakedown、Xiphos等。【 P P P无需做FFT运算】
  • 3)基于constant-round的Polynomial IOP:如Marlin、PlonK、StarkWare的SNARKs等。【 P P P需要做FFT运算】

以上方案都是通过增加 P P P开销,来减少proof长度以及降低 V V V开销。
以上1)2)类,只要其结合的多项式承诺方案也不需要FFT,则 P P P无需做FFT运算。

当前的多项式承诺方案主要分为四大类:

  • 1)基于pairing的多项式承诺方案(既不transparent,也不post-quantum)
    • KZG10、PST13、ZGKPP18等。
    • 独特属性有:具有constant sized evaluation proofs。
  • 2)基于discrete logarithm的多项式承诺方案(transparent,但不post-quantum)
    • 如BCCGP16、Bulletproofs、Hyrax、Dory等。【其中Dory即需要discret-log hardness,还需要pairing。】
  • 3)基于IOPs+hashing(transparent 且 post-quantum)
    • 如Ligero、FRI、Brakedown等。
  • 4)基于Groups of unknown order的多项式承诺方案(若使用class groups具有transparent属性,但不是post-quantum的)
    • 如DARK、Dew等。
    • 由于使用class groups, P P P非常慢。

现有的多项式承诺方案有:

  • KZG多项式承诺:PlonK和Marlin采用KZG多项式承诺。其既不是transparent的,也不是post-quantum secure的。2020年。
  • Bulletproofs多项式承诺:为transparent的,但不是post-quantum secure的。2017年。
  • Hyrax多项式承诺:为transparent的,但不是post-quantum secure的。2017年。
  • Dory多项式承诺:为transparent的,但不是post-quantum secure的。2020年。
  • FRI多项式承诺:为post-quantum secure的。2017年。基于纠错码。
  • Ligero多项式承诺:为post-quantum secure的。2017年。基于纠错码。
  • Ligero++多项式承诺:为post-quantum secure的。2020年。基于纠错码。
  • Brakedown多项式承诺:为post-quantum secure的。2021年。基于纠错码。
  • Orion多项式承诺:为post-quantum secure的。2022年。基于纠错码。

上面的5种post-quantum secure多项式承诺方案均是基于纠错码,使用的唯一密码学原语为哈希。同时具有如下属性:

  • 验证开销随着bits of security的位数增加而增加。(所谓验证开销,是由 哈希evaluation数量以及field operation数量 来衡量的。)

粗略来说,这些post-quantum多项式承诺方案的单次“迭代”仅可实现小数量的bits of security(如2-4)。因此,需重复该协议多次来“放大”安全等级,而随着每次重复,验证开销也会随之增加。因此,控制PQ-SNARKs的验证开销(对应为区块链应用中的gas开销),协议设计者通常有动力将security level设置为较低值。

除极少数例外情况(见2018年论文 Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains)外,Non-PQ-SNARK(透明和不透明)中不会出现具体安全和验证成本之间的紧张关系。Non-PQ-SNARK使用椭圆曲线群,其中离散对数被认为很难计算,其安全级别由所使用的群确定。椭圆曲线群的合适大小,以及每个群操作的成本,随着所需的安全级别而增长。然而,proof 中群元素的数量与群的选择无关。

而在PQ-SNARKs中,不仅hash evaluation的size会随着所需的安全等级增加而增加,proof中所需的evaluation数以及Verifier计算的 evaluation数也将随着所需安全等级增加而增加。

本文重点关注Transparent 且 Post-quantum zkSNARKs,在:

  • libiop: a C++ library for IOP-based zkSNARKs(C++)【2021年5月后未更新】

中实现了几种仅依赖于lightweight symmetric cryptography(任意Cryptographic hash function)的 Transparent 且 Post-quantum zkSNARKs 方案:

  • 1)Ligero协议:argument size为 O ( N ) O(\sqrt{N}) O(N ),见2017年论文Ligero: Lightweight Sublinear Arguments Without a Trusted Setup。
  • 2)Aurora协议:argument size为 O ( log ⁡ 2 N ) O(\log ^2 N) O(log2N),见2018年论文Aurora: Transparent Succinct Arguments for R1CS。
  • 3)Fractal协议:argument size为 O ( log ⁡ 2 N ) O(\log ^2 N) O(log2N),见2019年论文FRACTAL: Post-Quantum and Transparent Recursive Proofs from Holography。

以上这3种Transparent 且 Post-quantum zkSNARKs 方案,均支持基于smooth prime fields和binary extension fields的R1CS。所谓R1CS,为一种NP-complete relation that generalizes arithmetic circuit satisfiability。

不同于Ligero,其中Aurora和Fractal中有额外有趣的点在于:

  • FRI low-degree test:详情见Fast Reed-Solomon Interactive Oracle Proofs of Proximity。

2. 由IOPs 到 zkSNARKs

Interactive Oracle Proofs(IOPs):

  • 为Probabilistically checkable proof 的multi-round generalization
  • IOPs的性能,优于,PCPs
  • libiop: a C++ library for IOP-based zkSNARKs库,通过Interactive Oracle Proofs(IOPs)(本文接下来按作者名,称为BCS transformation),实现了由IOPs构建的zkSNARKs。

BCS transformation:

  • 使用cryptographic hash function(模型化为random oracle)
  • 来将,任意public-coin IOP
  • 编译为某SNARG

该SNARG具有如下属性:

  • transparent:生成/验证proof strings所需的全局参数,仅为,该哈希函数
  • post-quantum:在quantum random oracle模型内,其是安全的
  • lightweight:除该哈希函数之外,无需其它密码学依赖

BCS transformation的描述见:

  • Eli Ben-Sasson、Alessandro Chiesa 和 Nicholas Spooner 2016年论文 Interactive Oracle Proofs

BCS transformation的post-quantum安全性论证见:

  • Alessandro Chiesa、Peter Manohar 和 Nicholas Spooner 2020年论文 Succinct Arguments in the Quantum Random Oracle Model

BCS transformation保持了proof of knowledge:

  • 若底层的IOP是proof of knowledge,则所生成的SNARG为an argument of knowledge(即 a SNARK)

同理,BCS transformation保持了zero knowledge:

  • 若底层IOP是(honest-verifier)zero knowledge,则所生成的SNARK是zero knowledge的(即 a zkSNARG)

同时,BCS transformation可扩展为:

  • 向holographic IOPs,编译为,preprocessing SNARGs
    • 详情见:Alessandro Chiesa、Dev Ojha 和 Nicholas Spooner 2019年论文 FRACTAL: Post-Quantum and Transparent Recursive Proofs from Holography
    • 该特性,使得SNARGs可为,任意计算(而不仅仅是结构化计算),提供fast verification。

3. IOP协议

  • https://github.com/scipr-lab/libiop/tree/master/libiop/iop:该目录下包含了编写IOP协议的基础设施。
  • https://github.com/scipr-lab/libiop/tree/master/libiop/protocols:该目录下包含了几个使用该基础设施实现的协议,具体为:
languageround
complexity
oracle length
(field elts)
query
complexity
indexer time
(field ops)
prover time
(field ops)
verifier time
(field ops)
Ligero-IOPR1CS2O(N)O(N0.5)N/AO(N logN)O(N)
Aurora-IOPR1CSO(log N)O(N)O(log N)N/AO(N logN)O(N)
Fractal-IOPR1CSO(log N)O(N)O(log N)O(N logN)O(N logN)O(log N)

其中:

  • 1)Ligero-IOP:见2017年论文Ligero: Lightweight Sublinear Arguments Without a Trusted Setup。
    • 更准确来说,Ligero论文中仅描述了arithmetic circuits构建。而Aurora论文附录中解释了如何将,该arithmetic circuits构建,扩展为,支持R1CS。因此,实际在libiop: a C++ library for IOP-based zkSNARKs代码库中所实现的Ligero协议,借助了Aurora论文中的该扩展技术。
  • 2)Aurora-IOP:见2018年论文Aurora: Transparent Succinct Arguments for R1CS。
  • 3)Fractal-IOP:见2019年论文FRACTAL: Post-Quantum and Transparent Recursive Proofs from Holography。

其中比Ligero-IOP更高效,的,Aurora-IOP和Fractal-IOP,结合了2大元素:【详情见 2018年论文Aurora: Transparent Succinct Arguments for R1CS 】

  • 1)RS-encoded IOP,即基于纠错码
    • https://github.com/scipr-lab/libiop/tree/master/libiop/protocols/encoded:该目录下包含了RS-encoded IOPs,覆盖了Ligero、Aurora和Fractal协议核心的RS-encoded IOPs。
  • 2)对RS code的proximity test
    • https://github.com/scipr-lab/libiop/tree/master/libiop/protocols/ldt:该目录下包含了对RS code的proximity tests。其包含了:
      • direct test:用于Ligero
      • FRI protocol:用于Aurora和Fractal。

4. BCS transformation

  • https://github.com/scipr-lab/libiop/tree/master/libiop/bcs:该目录下将BCS transformation作为独立组件。
  • https://github.com/scipr-lab/libiop/tree/master/libiop/snark:该目录下,包含,将BCS transformation用于以上IOP协议,所获得的zkSNARKs。具体有:
languageindexer timeprover timeargument sizeverifier time
Ligero-SNARKR1CS N/A Oκ(N logN)Oκ(N0.5)Oκ(N)
Aurora-SNARKR1CS N/A Oκ(N logN)Oκ(log2 N)Oκ(N)
Fractal-SNARKR1CSOκ(N logN)Oκ(N logN)Oκ(log2 N)Oκ(log2 N)

其中:

  • κ 用于表示上表中的asymptotics还依赖于该安全参数。
  • make_zk:设置该标签,表示该BCS transformation应保留zero knowledge属性;而不设置,则表示该所转换的IOP是非zero knowledge的,因此也无需保留zero knowledge属性。

5. libiop库安装及测试

编译运行前,需安装:

  • 依赖项Installation instructions

测试文件见:

  • https://github.com/scipr-lab/libiop/blob/master/libiop/tests

若运行所有测试用例,则运行:

make check

若仅运行Aurora协议所有测试用例,则运行:

	$ ./test_aurora_snark
	$ ./test_aurora_protocol

6. libiop库性能分析

  • https://github.com/scipr-lab/libiop/tree/master/libiop/profiling:该目录下包含生成,具有timing和argument size信息的,协议执行traces。
    • 这些traces均对应为单线程环境

如,可基于181 bit prime field(其中RS-extra-dimensions=3),采用如下命令,为Ligero、Aurora和Fractal创建traces:

  $ ./instrument_aurora_snark --make_zk 1 --is_multiplicative 1 --field_size=181 --optimize_localization=1
  $ ./instrument_fractal_snark --make_zk 1 --is_multiplicative 1 --field_size=181 --optimize_localization=1
  $ ./instrument_ligero_snark --make_zk 1 --is_multiplicative 1 --field_size=181 --RS_extra_dimensions=3

根据以上命令所生成的traces,绘制了如下性能分析图表:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

参考资料

[1] libiop: a C++ library for IOP-based zkSNARKs

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/693359.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

逻辑这回事(四)----时序分析与时序优化

基本时序参数 图1.1 D触发器结构 图1.2 D触发器时序 时钟clk采样数据D时,Tsu表示数据前边沿距离时钟上升沿的时间,MicTsu表示时钟clk能够稳定采样数据D的所要求时间,Th表示数据后边沿距离时钟上升沿的时间,MicTh表示时钟clk采样…

C语言王国——数据的内存管理

目录 一、引言 二、整形在内存中的存储 2.1 进制之间的转换 2.1.1 整形的二进制 2.1.2 十进制和二进制 2.1.3 十进制和八进制的转换 2.1.4 十六进制和十进制的转换 2.2 原码,反码,和补码 三、大、小端字节序 3.1 大小端的定义 3.2 为什么会有大…

【Linux进程篇】Linux中的等待机制与替换策略

W...Y的主页 😊 代码仓库分享💕 目录 ​编辑 进程等待 进程等待必要性 进程等待的方法 wait方法 waitpid方法 获取子进程status 阻塞与非阻塞 进程程序替换 替换原理 替换函数 进程等待 进程等待必要性 之前讲过,子进程退出&am…

【教学类-40-01】20240607类似MJ的免费AI绘画工具——文心一格与通义万相

背景需求: 风变的AI对话大师一年到期了,也没有看到续费的按钮。不能使用它写代码了。 MJ早就用完了,最后480次,我担心信息课题会用到它生图,所以不敢用。 最近探索其他类似MJ的免费出图工具 一、文心一格(…

C# E2Pose人体关键点检测(OpenVINO推理)

C# E2Pose人体关键点检测(OpenVINO推理) 目录 效果 模型信息 项目 代码 下载 效果 模型信息 Inputs ------------------------- name:inputimg tensor:Float[1, 3, 512, 512] --------------------------------------------------------------- Ou…

实验六、IPv4 地址的子网划分,第 2 部分《计算机网络》

你有没有发现,困的时候真的清醒不了。 目录 一、实验目的 二、实验内容 三、实验小结 一、实验目的 完成本练习之后,您应该能够确定给定 IP 地址和子网掩码的子网信息。 知道 IP 地址、网络掩码和子网掩码后,您应该能够确定有关该 IP 地…

二、Nginx原来是这样?(系列篇02)

二、Nginx原来是这样?(系列篇02) 大家好,我是秋意零。 今天分享Nginx系列篇的第二节。Nginx目录结构、运行原理、基本配置。 更多请关注,Nginx系列篇主页:https://mp.weixin.qq.com/mp/appmsgalbum?__b…

STM32 uc/OS-III多任务程序

目录 一、项目创建 二、代码移植 1、uC/OS-III源码处理 2、KEIL文件配置 ​编辑3、文件修改 启动文件 ​编辑app_cfg.h includes.h bsp.c和bsp.h main.c lib_ cfg.h app.c和app.h 三、总结 学习目标: 学习嵌入式实时操作系统(RTOS&#xf…

找素数第二、三种方法

文章目录 第一种 :使用标签第二种:本质是方法的分装 第一种 :使用标签 没有使用信号量。break和continue作用范围只是最近的循环,无法控制外部循环。 此时使用标签 对外部循环进行操作。 package com.zhang; /* 找素数 第二种方…

小白教程--- kali(po解)WIFI密码 (图文教程)

kali学得好,牢饭少不了!!! 原理: 模拟WiFi的已连接设备,强制让其下线重连,获取其握手包,使用密码字典(宝丽)婆洁。 环境(准备工作)&a…

计网仿真综合实验 实验十二

实验十二 综合网络实验 实验过程 IP配置说明参考连线配置OSPF使公司内部联通 路由器R1的OSPF配置路由器R2的OSPF配置路由器R3的OSPF配置R1、R2、R3的相关解释路由器R4的OSPF配置路由器R5的OSPF配置路由器R6的OSPF配置R4、R5、R6解释: 路由器R2的RIP配置路由器R7的RIP配置 总结 …

Unity DOTS技术(十五) 物理系统

要解决性能的瓶颈问题,在DOTS中我们将不再使用Unity自带的物理组件. 下面来分享一下在DOTS中当如何使用物理插件. 一.导入插件 在使用DOTS系创建的实体我们会发现,游戏物体无法受物理系统影响进行运动.于是我们需要添加物理系统插件. 1.打开Package Manager > 搜索插件Uni…

IT人的拖延——都是“分心”惹的祸?

典型表现 我们说到拖延的原因有很多,还有一个原因是因为“分心太多“造成的,分心太多的拖延大致上有以下表现: 无法集中注意力: 分心太多会导致我们无法集中注意力在当前的工作任务上,我们可能会经常性地走神或者在工…

你好GPT-4o——对GPT-4o发布的思考与看法

你好GPT-4o 前言 2024年5月13日,OpenAI官网发布了他们的新一代自然语言处理交互系统——GPT-4o。这是OpenAI继GPT4之后又一个新的旗舰模型。 GPT-4o(“o”代表“omni”)是迈向更自然的人机交互的一步——它接受文本、音频、图像和视频的任意…

Linux环境---在线安装MYSQL数据库

Linux环境—在线安装MYSQL数据库 一、使用步骤 1.安装环境 Mysql 驱动 8.0 需要 jdk1.8 才行。 JDK版本:1.8 参考文档 MYSQL版本:8.0.2 下载链接: https://pan.baidu.com/s/1MwXIilSL6EY3OuS7WtpySA?pwdg263 操作系统:CentOS 1.1 建立存…

Golang | Leetcode Golang题解之第133题克隆图

题目: 题解: func cloneGraph(node *Node) *Node {if node nil {return node}visited : map[*Node]*Node{}// 将题目给定的节点添加到队列queue : []*Node{node}// 克隆第一个节点并存储到哈希表中visited[node] &Node{node.Val, []*Node{}}// 广…

数据结构严蔚敏版精简版-栈和队列以及c语言代码实现

1栈的定义和特权 栈(stack)是限定仅在表尾进行插入或删除操作的线性表。 注:虽然说栈的实现就是一端插入和删除,但不一定是在“表尾”,这个“表尾”是广义的。 头插法实现链栈 尾插法实现链栈 因此,对栈来说,表尾…

从GAN到WGAN(01/2)

从GAN到WGAN 文章目录 一、说明二、Kullback-Leibler 和 Jensen-Shannon 背离三、生成对抗网络 (GAN)四、D 的最优值是多少?五、什么是全局最优?六、损失函数代表什么?七、GAN中的问题 一、说明 生成对抗网络 &#…

13_前端工程化_ES6

1.前端工程化概念 前端工程化是使用软件工程的方法来单独解决前端的开发流程中模块化、组件化、规范化、自动化的问题,其主要目的为了提高效率和降低成本。 前后端分离(前端代码工程化独立出来形成一个单独的app) 1.开发分离 2.部署分离 3.服务器分离…

012-Linux逻辑卷管理(LVM)

前言 安装 Linux 操作系统时遇到的⼀个常见的难以决定的问题就是如何正确地评估各分区大小,以分配合适的硬盘空间; 基本的磁盘分区管理方式在逻辑分区划分好之后就无法改变其大小。随着 Linux的逻辑卷管理功能的出现,这些问题都迎刃而解,用户…