SuperNova论文赏析

2024-03-15 08:59
文章标签 论文 赏析 supernova

本文主要是介绍SuperNova论文赏析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 引言

前序博客有:

  • Nova: Recursive Zero-Knowledge Arguments from Folding Schemes学习笔记

卡内基梅隆大学 Abhiram Kothapalli 和 微软研究中心 Srinath Setty 2022年论文《SuperNova: Proving universal machine executions without universal circuits》,为Nova对半结构化电路的扩展版,开源代码见:

  • https://github.com/jules/supernova(Rust)
  • https://github.com/hero78119/SuperNova(Rust)【活跃开发中】

本文主要参考:

  • 2023年3月视频分享 SuperNova with Srinath and Abhiram
  • 2022年8月在Session at Crypto 2022上分享 Nova: Recursive Zero-Knowledge Arguments from Folding Schemes - Abhiram Kothapalli
  • 2023年4月视频分享 zkStudyClub: Supernova (Srinath Setty - MS Research)

2. Nova回顾

2.1 IVC计算模型

所谓IVC(Incremental Verifiable Computation)计算模型,是指:

  • 对于(非确定性)函数 F F F 和 statement ( n , z 0 , z n ) (n, z_0, z_n) (n,z0,zn),证明存在 z 0 = z 0 ′ z_0=z_0' z0=z0 z i + 1 ′ ← F ( z i ′ , w i ) z_{i+1}'\leftarrow F(z_i', w_i) zi+1F(zi,wi),使得 z n = z n ′ z_n=z_n' zn=zn
    在这里插入图片描述

IVC(Incremental Verifiable Computation)最早由Valiant在其2008年论文[Val08] Incrementally verifiable computation or proofs of knowledge imply time/space efficiency 中首次提出,其核心思想为:
在这里插入图片描述
IVC的关键在于,随着迭代次数的增加,其proof size并不会增加。具体为:
在这里插入图片描述
不过,其中存在的问题在于:

  • 实际实现时,在电路中验证SNARK proof是昂贵的。

2.2 Nova(本文称为NIVC):为针对单个指令的IVC

从SuperNova的角度来看Nova(本文称为NIVC):

  • Nova为针对单个指令的IVC。
    在这里插入图片描述

Nova通过引入Folding scheme,在 F ′ F' F中不再做任何proof验证工作:
在这里插入图片描述

2.3 Folding Schemes

交互式folding scheme是指Prover P P P和Verifier V V V交互式地将"2个claim ( u 1 , w 1 ) , ( u 2 , w 2 ) ∈ R (u_1,w_1),(u_2,w_2)\in R (u1,w1),(u2,w2)R" reduce为 “1个claim ( u , w ) ∈ R (u,w)\in R (u,w)R”。
Folding scheme需满足如下属性:

  • Completeness完备性:若 u 1 , u 2 u_1,u_2 u1,u2为satisfiable的,则 u u u也是satisfiable的。
  • Knowledge Soundness可靠性:若Prover可输出satisfying w w w,则Prover必然知道satisfying w 1 , w 2 w_1,w_2 w1,w2
  • Efficiency高效性:Verifier “做Folding操作”,必须比, “对某instance做check操作(即验证proof)” ,要便宜很多。

在这里插入图片描述
以上交互式folding scheme可通过Fiat-Shamir Transformation 来实现非交互式folding scheme。
已知某NP的非交互式folding scheme,通过运行folding Verifier, F ′ F' Fverifiably fold u i u_i ui U i U_i Ui:【fold前后的3个instance具有相同的结构和相同的size。
在这里插入图片描述

2.4 针对R1CS约束系统的Folding Scheme

标准R1CS表示为:
在这里插入图片描述
其中:

  • Z = ( W , x , 1 ) Z=(W,x,1) Z=(W,x,1) W W W为witness vector, x x x为public input/output vector。

需在标准R1CS表示的基础之上,额外引入error vector E E E和scalar u u u,从而构建出Relaxed R1CS:
在这里插入图片描述
其中:

  • Z = ( W , x , u ) Z=(W,x,u) Z=(W,x,u) W W W为witness vector, x x x为public input/output vector。
  • u = 1 , E = 0 ⃗ u=1,E=\vec{0} u=1,E=0 ,则为标准R1CS。即可将标准R1CS看成是Relaxed R1CS的特例情况。

然后是结合具有加法同态属性的承诺方案,来实现对Relaxed R1CS的Folding Scheme:【为避免Prover作弊,并 实现Verifier succinctness,需将 ( E , W ) (E,W) (E,W)一起作为witness,并提前在statement中公开其承诺值 ( E ˉ , W ˉ ) (\bar{E},\bar{W}) (Eˉ,Wˉ)。】
在这里插入图片描述

3. SuperNova

3.1 NIVC计算模型

所谓NIVC(Non-uniform IVC)计算模型,是指:

  • 对于(非确定性)指令集 F 1 , ⋯ , F l F_1,\cdots, F_l F1,,Fl、控制函数 φ \varphi φ 和 statement ( n , z 0 , z n ) (n, z_0, z_n) (n,z0,zn),证明存在 z 0 = z 0 ′ z_0=z_0' z0=z0 z i + 1 ′ ← F φ ( z i ′ , w i ) ( z i ′ , w i ) z_{i+1}'\leftarrow F_{\varphi(z_i', w_i)}(z_i', w_i) zi+1Fφ(zi,wi)(zi,wi),使得 z n = z n ′ z_n=z_n' zn=zn
    在这里插入图片描述

以上为SuperNova核心思想,SuperNova为对Nova的扩展,理论上可将SuperNova用于实现虚拟机。在递归过程中,每个step可动态选择所执行的指令,不再需要在每个step实现 所有指令集 的电路,而是,在每个step只需实现 实际用到的指令 的电路。

SuperNova实现了"a la carte(按菜单点菜)" cost profile:

  • pay only for what is executed。

在这里插入图片描述

3.2 SuperNova的Folding Scheme

Nova中要求 fold前后的3个instance(claim)具有相同的结构和相同的size。
而SuperNova中,针对所支持的每个指令,构建了一个Running Claim(又名Running Instance):
在这里插入图片描述
其中:

  • 每个step的running instance集合 { U i , 1 , U i , 2 , ⋯ , U i , l } \{U_{i,1},U_{i,2}, \cdots, U_{i,l}\} {Ui,1,Ui,2,,Ui,l}可 以Merkle tree或multi-set hash等成熟技术来表示,因为实际在每个step仅使用该running instance集合中的一个,实际电路中没必要枚举所有的running instance。
  • p c i pc_i pci为program counter,用于:
    • 决定集合 { U i , 1 , U i , 2 , ⋯ , U i , l } \{U_{i,1},U_{i,2}, \cdots, U_{i,l}\} {Ui,1,Ui,2,,Ui,l} 中哪个running instance参与Fold。
    • 决定用Fold结果 来 更新集合 { U i + 1 , 1 , U i + 1 , 2 , ⋯ , U i + 1 , l } \{U_{i+1,1},U_{i+1,2}, \cdots, U_{i+1,l}\} {Ui+1,1,Ui+1,2,,Ui+1,l} 中哪个running instance。
  • 基于控制函数 φ \varphi φ w i , z i w_i,z_i wi,zi,来决定下一个step的program counter p c i + 1 pc_{i+1} pci+1

4. SuperNova并行化

具体见视频SuperNova and Parallelising Nova,讨论了实际使用SuperNova来实现zkEVM时的一些考量及并行化策略:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

Nova系列博客

  • Nova: Recursive Zero-Knowledge Arguments from Folding Schemes学习笔记
  • Nova 和 SuperNova:无需通用电路的通用机器执行证明系统
  • Sangria:类似Nova folding scheme的relaxed PLONK for PLONK
  • 基于Nova/SuperNova的zkVM
  • SuperNova:为多指令虚拟机执行提供递归证明
  • Lurk——Recursive zk-SNARKs编程语言
  • Research Day 2023:Succinct ZKP最新进展
  • 2023年 ZK Hack以及ZK Summit 亮点记
  • 基于cycle of curves的Nova证明系统(1)
  • 基于cycle of curves的Nova证明系统(2)
  • Nova代码解析
  • Nova中 Vitalik R1CS例子 的 folding scheme
  • 基于Nova的MinRoot VDF实现
  • 基于Nova的SHA256证明
  • Nova-Scotia代码解析
  • Customizable constraint systems for succinct arguments学习笔记(1)
  • Customizable constraint systems for succinct arguments学习笔记(2)

这篇关于SuperNova论文赏析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/811434

相关文章

AI hospital 论文Idea

一、Benchmarking Large Language Models on Communicative Medical Coaching: A Dataset and a Novel System论文地址含代码 大多数现有模型和工具主要迎合以患者为中心的服务。这项工作深入探讨了LLMs在提高医疗专业人员的沟通能力。目标是构建一个模拟实践环境,人类医生(即医学学习者)可以在其中与患者代理进行医学

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear

论文翻译:ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的,这引发了人们的担忧和猜测,即它们可能已

OmniGlue论文详解(特征匹配)

OmniGlue论文详解(特征匹配) 摘要1. 引言2. 相关工作2.1. 广义局部特征匹配2.2. 稀疏可学习匹配2.3. 半稠密可学习匹配2.4. 与其他图像表示匹配 3. OmniGlue3.1. 模型概述3.2. OmniGlue 细节3.2.1. 特征提取3.2.2. 利用DINOv2构建图形。3.2.3. 信息传播与新的指导3.2.4. 匹配层和损失函数3.2.5. 与Super

BERT 论文逐段精读【论文精读】

BERT: 近 3 年 NLP 最火 CV: 大数据集上的训练好的 NN 模型,提升 CV 任务的性能 —— ImageNet 的 CNN 模型 NLP: BERT 简化了 NLP 任务的训练,提升了 NLP 任务的性能 BERT 如何站在巨人的肩膀上的?使用了哪些 NLP 已有的技术和思想?哪些是 BERT 的创新? 1标题 + 作者 BERT: Pre-trainin

[论文笔记]LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale

引言 今天带来第一篇量化论文LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale笔记。 为了简单,下文中以翻译的口吻记录,比如替换"作者"为"我们"。 大语言模型已被广泛采用,但推理时需要大量的GPU内存。我们开发了一种Int8矩阵乘法的过程,用于Transformer中的前馈和注意力投影层,这可以将推理所需

2024 年高教社杯全国大学生数学建模竞赛 C 题 农作物的种植策略 参考论文 无水印

持续更新中,2024年数学建模比赛思路代码论文都会发布到专栏内,只需订阅一次!  完整论文+代码+数据结果链接在文末!  订阅后可查看参考论文文件 第一问 1.1 问题重述 这个问题围绕的是华北山区的某乡村,在有限的耕地条件下,如何制定最优的农作物种植策略。乡村有 34 块露天耕地和 20 个大棚,种植条件包括粮食作物、蔬菜、水稻和食用菌。除了要考虑地块的面积、种植季节等,还要确保

论文精读-Supervised Raw Video Denoising with a Benchmark Dataset on Dynamic Scenes

论文精读-Supervised Raw Video Denoising with a Benchmark Dataset on Dynamic Scenes 优势 1、构建了一个用于监督原始视频去噪的基准数据集。为了多次捕捉瞬间,我们手动为对象s创建运动。在高ISO模式下捕获每一时刻的噪声帧,并通过对多个噪声帧进行平均得到相应的干净帧。 2、有效的原始视频去噪网络(RViDeNet),通过探

2024年全国大学生数学建模A题借鉴论文

问题  1: 舞龙队的动态位置与速度计算 1. **螺旋线的几何建模**:根据题目描述,舞龙队沿着等距螺旋线前进。螺旋线的螺距为 55 cm, 需根据极坐标公式确定每节板凳的位置。 -  极坐标螺旋线方程:\( r = a + b\theta \), 其中  \( b \)  是螺距, 可以利用该方程计算 每秒舞龙队的各个节数的坐标。 2. **速度计算**:给定龙头的行进速度为 1 m/s ,