Star.Li

Bitpush 专栏 · 共41篇文章

零知识证明 - 说说Nova

前段时间在翻译一本零知识证明技术的书。上个月底基本内容已经翻译完成。翻译时间比我预想的长得多。目前正在和作者讨论书中的一些笔误，准备最后的定稿。anyway，终于有点时间看看新鲜东西。先从Nova算法开始～01，Nova算法相关资料三份资料可以帮助理解Nova算法：Nova论文：https://eprint.iacr.org/2021/370.pdf Nova潜在攻击和相应修正：https://eprint.iacr.org/2023/969.pdf Nova潜在攻击的理解总结：https://www.zksecurity.xyz/blog/posts/nova-attack/ 本文是上述资料的理解和总结。本文中的一些图来自于上述资料，在本文中不再一一标注。02，从IVC开始Nova算法是一种针对IVC（增量可验证计算，Incrementally Verifiable Computation）的新型的零知识证明算法。IVC，即同一个函数把前一个输出作为下一个输入迭代计算。F函数的迭代计算过程如下图：z0是最初的输入，通过F函数计算生成的结果，作为下一个F函数的输入。03，松弛R1CS以及松弛承诺R1CS众所周知，R1CS是零知识证明技术中电路约束表示形式。松弛R1CS（Relaxed R1CS)可以看成是R1CS的扩展形式。在R1CS的基础上，增加一个标量u以及一个错误向量E。松弛R1CS的实例用(E, u, x)表示。松弛承诺R1CS在松弛R1CS的基础上，将E以及W向量承诺。松弛承诺R1CS的实例用（\bar{E}, u, \bar{W}, x)表示，其中x和u是公开变量。从R1CS扩展到松弛R1CS，是为了折叠方案。注意的是，从松弛R1CS的角度看，R1CS是其的一种特例。也就是说，R1CS也是一种“特别“的松弛R1CS。04，折叠方案（Folding Scheme）直觉上来说，一个关系R的折叠方案就是将两个符合关系R的实例“折叠成”一个新的复合关系R的实例。松弛R1CS/松弛承诺R1CS就能进行类似的折叠。两者的折叠过程类似。松弛承诺R1CS的折叠方案如下：整个折叠方案由4步组成。第一步，证明者P发送一个交叉项T的承诺\bar{T}给验证者。第二步，验证者发送随机挑战r给证明者。第三步是证明者和验证者都需要执行的，承诺的折叠。第四步，证明者独自执行，将两个实例的E和W向量进行折叠。05，增广函数F' （Argumented Function)折叠方案，折叠的是松弛R1CS实例。那这些松弛R1CS实例证明的计算是什么？显然，这些计算要包括折叠的计算。这些计算不仅仅是IVC计算中的F函数了，也就被称为增广函数F‘。增广函数F’的计算主要由两部分组成：1/ IVC中的F函数2/ R1CS实例的折叠计算06，理想中的样子有了上述的这些理解，可以想象出折叠的过程：其中，circuit就是增广函数F’对应的电路。acc{1,2,3,4,5,6}是松弛承诺R1CS实例。circuit有两个计算：1/松弛承诺R1CS实例的折叠，比如acc1+acc2->acc3。2/计算F函数，将状态state1变为state2，再从state2变为state3等等。注意的是，增广函数F’对应的circuit，本身也是一个R1CS实例，其可以表示成松弛R1CS实例。也就是图中的acc4和acc6。“summarize”是将松弛R1CS实例转换为松弛承诺R1CS实例。仔细观察第二个电路的输入，acc3是折叠后的松弛承诺R1CS实例，acc4是证明acc3是正...

1031天前Star.LiStar Li

2022年，再出发，2.0!

2022年底到现在一直很忙，年终总结一直拖到现在。最近有点时间，回顾并总结一下2022。先闲话几句，2022年的疫情，让人在上海，魔幻地封闭几个月。封闭在家，相对封闭独处的环境对身体以及心理都有影响。在解封之前，我似乎已经适应封闭的生活，接受现实，每天也忙忙碌碌。感叹环境变化对人产生了潜移默化的影响，努力创造自由宽松的学习工作环境。2022年都做了些啥？ZPrize零知识证明计算性能的优化有趣又有挑战。ZPrize推动了零知识证明计算性能前进。MSM是目前零知识证明中计算量相对较大的模块。2022年，Trapdoor Tech赞助了ZPrize的MSM的GPU/FPGA奖项，也参于其他一些有趣的奖项，并获得了不错的成绩。https://www.zprize.io/blog/announcing-zprize-resultsZPrize各种奖项的成果几乎代表了目前零知识证明计算性能的最高水平。各种奖项的独特的优化思路也让人大开眼界。MSM的GPU/FPGA的优化成果比较有趣。从性价比的角度看，在2^26的规模下MSM的FPGA的性能比GPU差了差不多一个数量级。2022年也写了一篇文章详细分析MSM的GPU/FPGA性能预测：零知识证明 - FPGA vs. GPUZKHack IIIZKHack一直是零知识证明入门推荐的活动。2022年的zkWhiteBoard清晰明了地介绍了SNARK的整体框架，并结合具体的应用场景深入设计或者应用的细节。ZKHack III的题目比以往的活动都简单些。ZKHack的每条题目都是一个独立的测试环境，开发人员除了深入理解零知识证明外，可以快速的上手零知识证明的开发环境。https://zkhack.dev/zkhackIII/零知识证明技术总结零知识证明技术在最近几年发展迅速。前几年系统地学习了Groth16/PLONK/HALO/Marlin等等零知识证明协议。学习这些零知识证明协议的同时，一直想系统性梳理零知识证明的底层原理和结构。去年，陆陆续续地整理一些资料，尝试回答一些问题，比如零知识证明的底层原理是什么？零知识证明协议的迭代路线是什么？从工程应用的角度，零知识证明协议还有哪些可能性？可能还要花一段时间梳理，稍晚些分享理解和认识。再出发，Trapdoor Tech 2.0创业三年多，算是活下来了。技术人员早期创业，可能聚焦在某个技术本身，有清晰的技术难点和明确的客户。在进入市场后，往往需要再次明确市场需求，重新调整定位，明确产品价值，而不是技术难点。往往，确定产品价值和市场定位是个挑战。产品价值本身也随着市场的变化会做迭代。如何找到切合市场和团队的产品路径是个开放性问题，也是有挑战的问题。三年创业不易，是时候和志同道合的小伙伴一起稍做休整，重新出发。下一个阶段是积极探索，共同成长。2.0，会更有趣，会玩，会干活。...

1157天前Star.LiStar Li

零知识证明 - 深入理解Zinc

疫情在家，多看点代码。对于疫情也感慨几句，对于资深程序员，这么多年了还没有和家人在一起吃晚饭这么多天。老实讲，比平时公司附近晚上吃的好得多。上海停运了，连各种骚扰电话也少了。有空再翻了翻Zinc的设计和代码，感受一下Matter Labs对zkVM的设计和理念。Zinc提供一种可靠，简单的电路开发语言。Zinc不支持图灵完备。Zinc从2019年就开始开发，最后一个Patch是2021年9月份。commit 30d43721d98c727327bb92b6888f5903556a4261Author: Alex Z Date:   Sat Sep 25 15:21:42 2021 +0300    Update README.md1. 代码框架https://github.com/matter-labs/zinc.gitZinc项目代码包含了比较多的子项目，主要分为如下几部分：zinc-book - 系统介绍Zinc的方方面面，从变量类型的定义，表达式，智能合约的实现，vm的基本原理等等。zargo - 利用zinc实现的各种包的管理器。zinc-types - Zinc相关的基础类型的定义。zinc-compiler/zinc-lexical/zinc-syntax - Zinc编译器相关，zinc语言编译成ZincVM支持的指令集。zinc-vm - ZincVM的实现，主要实现ZincVM对应的约束系统。接下来分别介绍相关的子项目。重点介绍ZincVM的实现。2. Zinc BookZinc Book给出了Zinc语言的全貌。Zinc语言的语法类似rust语言。具体的语法和表达式，相对简单。利用Zinc语言可以开发智能合约。Zinc语言通过编译器可以编译成ZincVM可以运行的指令。ZincVM的好处是运行的程序可以描述成R1CS的约束，由此可以给出程序执行的证明。Zinc语言编译器实现在zinc-compiler/zinc-lexical/zinc-syntax，对应词法/语法分析。在深入ZincVM之前，先了解一下ZincVM对应的指令集。3. ZincVM指令集ZincVM指令集定义在zinc-types/src/instructions/mod.rs：pub enum Instruction {    /// The no-operation instruction.    NoOperation(NoOperation),    /// An evaluation stack instruction.    Push(Push),    /// An evaluation stack instruction.    Slice(Slice),    /// An evaluation stack instruction.    Copy(Copy),    /// A data stack instruction.    Load(Load),    /// A data stack instruction.    LoadByIndex(LoadByIndex),    /// A data stack instruction.   ...

1446天前Star.LiStar Li星想法

零知识证明 - zkEVM源代码分析（State Circuit）

zkEVM是零知识证明相对复杂的零知识证明应用，源代码值得反复阅读和学习。https://github.com/appliedzkp/zkevm-circuits.git本文中采用的源代码对应的最后一个提交信息如下：commit 1ec38f207f150733a90081d3825b4de9c3a0a724 (HEAD -> main)Author: z2trillion <z2trillion@users.noreply.github.com>Date:   Thu Mar 24 15:42:09 2022 -0400前一篇文章介绍了zkEVM的EVM Circuit的电路实现细节，接下来继续介绍State Circuit。零知识证明 - zkEVM源代码分析(EVM Circuit)State Circuit ConfigureState电路实现了Stack，Memory以及Storage的检查。State电路实现在zkevm-circuits/src/state_circuit/state.rs。pub struct StateCircuit<  F: FieldExt,  const SANITY_CHECK: bool,  const RW_COUNTER_MAX: usize,  const MEMORY_ADDRESS_MAX: usize,  const STACK_ADDRESS_MAX: usize,  const ROWS_MAX: usize,> {  /// randomness used in linear combination  pub randomness: F,  /// witness for rw map  pub rw_map: RwMap,}StateCircuit的configure逻辑由Config的configure函数实现。fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {  Config::configure(meta)}StateCircuit的大体电路结构如下图：先着重介绍一下keys，占用了5个column，表示Memory，Stack以及Storage的key信息。State Circuit约束大部分都是围绕key-value的约束。为了兼容Memory，Stack以及Storage的Key信息，采用如下的5个Column。keys[0] - tagkeys[1] - reservedkeys[2] - account address(memory/stack: 0)keys[3] - addresskeys[4] - storage key(memory/stack: 0)其中key2，key4是给Storage用的。Storage约束的信息还不够完整。Memory和Stack的约束逻辑类似。这篇文章详细介绍一下Stack的约束实现。在了解约束之前，先介绍Memory/Stack/Storage的信息组织形式：key0(tag)key1key2key3(address)key4read/writerw countervalueMEM0000100MEM0000020STACK0000100STACK0000020所有的witness信息...

1509天前Star.LiStar Li

零知识证明 - zkEVM源代码分析(EVM Circuit)

zkEVM是零知识证明相对复杂的零知识证明应用，源代码值得反复阅读和学习。https://github.com/appliedzkp/zkevm-circuits.git本文中采用的源代码对应的最后一个提交信息如下：commit 1ec38f207f150733a90081d3825b4de9c3a0a724 (HEAD -> main)Author: z2trillion Date:   Thu Mar 24 15:42:09 2022 -0400zkEVM的电路主要由两部分电路组成：EVM Circuit和State Circuit。本文先讲解EVM Circuit的电路相关的源代码。其他部分在后续的文章中介绍。这篇文章将详细讲解EVM Circuit各个Column的设计，每种Opcode如何约束以及多个Opcode之间是如何约束以及组合。整体电路结构EVM Circuit的整体的电路结构如下图所示：从Column的角度来看，EVM Circuit分为三部分：1/ Step选择子（包括当前Step，第一个Step，最后一个Step等等）2/ Step电路 3/ Fixed Table（固定的查找表）。Step电路逻辑是核心部分。所谓的Step是指从电路约束角度的执行的一步。这一部分又分为两部分：a/ execution state （Step状态选择子） b/ 各种执行状态的约束逻辑。图中用虚线画出了大体的约束逻辑模块。理解EVM Circuit从Configure和Assign入手。EVM Circuit ConfigureEVM Circuit电路实现在zkevm-circuits/src/evm_circuit.rs。从它的configure函数看起：    pub fn configure(        meta: &mut ConstraintSystem,        power_of_randomness: [Expression; 31],        tx_table: TxTable,        rw_table: RwTable,        bytecode_table: BytecodeTable,        block_table: BlockTable,    ) -> Self    where        TxTable: LookupTable,        RwTable: LookupTable,        BytecodeTable: LookupTable,        BlockTable: LookupTable,EVM Circuit的电路约束由两部分组成：1/ fixed_table 2/ Execution 部分。fixed_table是一些固定的表信息，占用4个column，分别对应tag/value1/value2/结果。tag的种类为10种，定义在zkevm-circuits...

1519天前Star.LiStar Li源代码

零知识证明 - 一个通俗解释

通俗理解零知识证明，有个很经典的阿里巴巴的例子。阿里巴巴能在不泄露咒语的情况下，向强盗证明他知道咒语的内容。最近在听斯坦福大学教授 Dan Boneh的讲座视频时，发现有另外一个形象的描述零知识证明的例子：https://youtu.be/V0JdeRzVndI?t=1972Dan Boneh教授是密码学大牛。如果对Dan Boneh不熟悉的，可以查看斯坦福大学Dan Boneh的主页：https://crypto.stanford.edu/~dabo/Dan Boneh教授在视频中利用”where is waldo“游戏，尝试向幼儿园的小朋友介绍零知识证明的作用。where is waldo 游戏是一款经典的纸上游戏，要求玩家在一张人山人海的图片中找出一个特定的人物 - waldo沃尔多。这样的图片类似：请问如何零知识证明你知道waldo的人像位置？你需要一把剪刀，背过去别让挑战者看见，先把waldo的人像剪下来，把剩余的纸板撕烂。把waldo的人像交给挑战者，就能非常好地证明你知道waldo的人像在哪里，但是并没有暴露具体的位置。这个例子中的知识就是“Waldo人像的位置“。

1526天前Star.LiStar Li零知识证明

2021年，努力仍需想象力！

2021年的年度总结，拖了好久。最近疫情严重起来了，正好在家，可以好好地想想理理。其实农历年前，把2021年记的一些笔记，写的一些文章拿出来翻了翻，想了想2021年都干了哪些事情。大大小小的topic，看了不少，做了不少。围绕零知识证明技术，整理Plookup算法，实现优化递归证明，翻译/研究Halo2算法等等。值得一提的是，11月份参加了zkHack的挑战赛。Trapdoor Tech团队顺利完成六道题目，获得第3题第二名，总体第五名的成绩。零知识证明 - zkHack挑战赛第五名Halo2 Book看完，迫不及待地就想把它翻译成中文。好的设计，从介绍文档都能给你一种厚积薄发的厚重感。零知识证明 - Halo2 Book中文翻译在年前，团队直播了对整个Halo2算法的理解。直播视频 - 深入理解Halo2算法忙忙碌碌的2021年过去了，还记得连续几天，凌晨，小伙伴还在一起讨论零知识证明算法。腾讯视频转码后的视频，清晰度不清晰。相关视频已经上传到哔哩哔哩：01 - Halo2入门基础介绍https://www.bilibili.com/video/BV1ML4y1M7iV/02 - 深入理解Permutation & Lookup算法https://www.bilibili.com/video/BV1C34y1t7pN/03 - Halo2协议基础及介绍https://www.bilibili.com/video/BV19L4y1T7ai/04 - Halo2电路进阶（sha256）https://www.bilibili.com/video/BV1LL411P7ba/05 - Halo2源代码导读https://www.bilibili.com/video/BV1HS4y1D7tX/翻开对比2020年的总结，我却无比惆怅，2020年定的目标，“业”在哪里？2021年，匆匆忙忙，却还在尝试。在一些点上，花的心思比较多。但是，这些点没有形成线，更别提面了。zkVM是个有意思的topic。零知识证明技术能证明计算。如果这种计算是一个完备的虚拟机，零知识证明就能证明一个虚拟机的执行以及相应的结果。也就是说，零知识证明技术能提供可信的虚拟机执行。Trapdoor Tech憧憬并拥抱这样的未来。2021年，创业一点感悟：志当存高远，但需想象力。想象力，构建未来符合市场需求的产品形态。在对市场充分分析和营收预估的情况下，提前投入资源和连接，调整并逐步实现想象目标。创业的近期目标比较好设立和实现，这些近期目标的连接以及积累需要想象力。创业团队，千万别在一个一个项目中迷失了自己的方向，慢慢耗散了自己的想象力。喜欢零知识证明技术的小伙伴，欢迎加入Trapdoor Tech，一起创造未来。...

1554天前Star.LiStar Li

零知识证明 - zkHack mini挑战赛第一名

Trapdoor Tech获得zkHack mini挑战赛第一名 :)  https://www.zkhack.dev/mini.html这次的挑战赛由两道题目组成。一道题目一个星期的挑战时间。和第一期的挑战不同，这一期的题目都是基于STARK算法。STARK算法，AIR，FRI低阶测试等等技术会在后续的文章仔细介绍。本文先总结一下这次挑战赛的两个题目的解题思路。第一题：There's something in the AIRhttps://www.zkhack.dev/puzzleM1.html该题需要找到一种方法来骗过基于ZK-STARK和winterfell构建的投票系统。该题实现的电路逻辑如下图：这个是典型的隐私保护的实现。通过Nullifier证明拥有私钥。解题思路如果用户Alice能对同一个主题(topic)完成2次有效投票，说明系统中存在一个漏洞使得：证明者(prover)能产生 > 1 个的nullifier，并基于此构建证据(witness)验证者(verifier)根据相应的公开输入和证据，无法分辨证明者伪造的nullifier首先，构造nullifier是在make_signal函数中，并将其作为验证者的输入//! - A nullifier is computed by hashing a private key together with a hash of the topic - i.e.://!   hash(priv_key, hash(topic)) using the same Rp64_256 hash function.  let nullifier = priv_key.get_nullifier(topic);  /// Creates a nullifier for the provided topic against this private key.  ///  /// A nullifier is computed simply as hash(key, topic).  pub fn get_nullifier(&self, topic: Digest) -> Digest {      let key: Digest = self.0.into();      Rescue::merge(&[key, topic])  }但是证明者进行证据的计算过程中，使用12列的执行轨迹, 即State[12..23]，来构成nullifier, 不只是私钥和主题。  // prover set the initial state  // -- nullifier section of the trace --              state[12] = Felt::new(8);              state[13] = Felt::ZERO;              state[14] = Felt::ZERO;          &nb...

1554天前Star.LiStar Li

直播视频 - 深入理解Halo2算法

最近疫情在家办公，把年前的直播视频整理了一下。总共分为5个视频，对Halo2算法感兴趣的小伙伴可以看看。目录：01 - Halo2入门基础介绍02 - 深入理解Permutation & Lookup算法03 - Halo2协议基础及介绍04 - Halo2电路进阶（sha256）05 - Halo2源代码导读视频详见链接所有视频对应的PPT，可以通过百度网盘下载：链接:https://pan.baidu.com/s/1wueRNkjeu8fKPrvK_doHQg  密码:qnwl星想法技术改变世界往期精彩回顾零知识证明应用和示例：零知识证明 - zkHack挑战赛第五名Dark Forest - 采用零知识证明技术的游戏零知识证明 - 电路及证明示例（libsnark）椭圆曲线：零知识证明 - 椭圆曲线基础zk-SNARK理论知识：零知识证明 - 深入理解powersoftau零知识证明 - 从理论到实践（视频）零知识证明 - zkSNARK入门零知识证明 - 从QSP到QAP零知识证明 - 基于多项式构造零知识证明零知识证明 - Groth16算法介绍零知识证明 - Groth16计算详解零知识证明 - 理解FFT的蝶形运算零知识证明 - zkSNARK的Nullifier Hash攻击零知识证明 - 一种新型的Merkle树（Shrubs）零知识证明 - 深入理解PlonK算法直播视频 - 深入理解PlonK算法零知识证明 - Plookup算法介绍零知识证明 - KZG多项式承诺零知识证明 - Halo2 Book中文翻译零知识证明的基本库源代码分析：零知识证明 - libsnark源代码分析零知识证明 - bellman源码分析零知识证明 - ethsnarks源代码导读零知识证明 - 深入理解ZoKrates零知识证明 - DIZK介绍零知识证明 - DIZK源代码导读零知识证明 - Halo2电路构建源代码导读年度总结：2018年，我都干了些啥？2019年，变化的一年！2020，机遇！...

1561天前Star.LiStar Li

Trapdoor Tech - Halo2技术直播（2021）

年底了，一年总结的时候，也是Trapdoor团队直播时间。今年我们给大家直播Halo2技术，一种支持查找表（lookup）并且毋需初始设置的零知识证明技术。Trapdoor团队已经将Halo2技术文档完整翻译成中文：https://trapdoor-tech.github.io/halo2-book-chinese/直播预告Halo2 技术直播 - 2022-01-1901基本概念及示例 (10:15am~11:00am)02Lookup/Permuation证明 (11:15am~12:00am)03协议介绍 (2:15pm~3:00pm)04SHA256 Chip电路实现 (3:15pm~4:00pm)05Halo2源代码导读 (4:15pm~5:00pm)直播的形式确定后，会提前更新在评论区。感兴趣的小伙伴，欢迎加入并讨论零知识证明技术。

1622天前Star.LiStar Li

零知识证明 - Halo2 Book中文翻译

前一段时间，密集地学习整理Halo2零知识证明算法的实现原理以及电路开发细节。2021年的最后一天，节奏慢一下，有点时间慢慢品品Halo2的设计思路和原理。真心感叹：好的设计，从介绍文档都能给你一种厚积薄发的厚重感。Plonk算法基于多项式承诺。Halo2 Book重点讲解了Halo2算法中多项式的构建。一旦，你掌握了Plonk算法的设计思想，你会发现Halo2在系统地娓娓道来它的设计。好的文章，好的算法，喜欢不需要理由，团队第一时间把Halo2 Book翻译成中文，方便更多的小伙伴理解。欢迎感兴趣的小伙伴一起更新迭代。Halo2 Book中文翻译https://trapdoor-tech.github.io/halo2-book-chinese/Halo2 Book清晰系统地讲解了halo2零知识证明的原理：电路算术表示，查找证明，置换证明以及整个协议的形式化表示。同时该文档也讲解零知识证明基础原理，是入门PLONK系零知识证明的极佳入门材料。在查看Halo2实现代码的基础上，对照Halo2 Book设计，团队总结出Halo2 Book对应的中文翻译。国内零知识证明技术相关的正规教程/教材比较少，有些术语并没有合适或者统一的翻译。针对用到的术语，整理了一个术语表。有些术语实在无法精准翻译，直接用英文代替。祝大家，2022元旦快乐～

1634天前Star.LiStar Li

零知识证明 - zkHack挑战赛第五名

zkHack算是这几年举办的比较有意思的零知识证明技术挑战的活动。整个活动由六道零知识证明的题目组成，每周三的北京时间凌晨3:00左右公布一道新题目。每一道题目在公布之前会提供相应的背景资料，参与者有一周左右的时间解题。Trapdoor Tech团队顺利完成六道题目，获得第3题第二名，总体第五名的成绩。Trapdoor Tech团队在解题后都会提交完整的解题思路。完整的解题思路可以从zkHack的网站查询。总结回顾一下每条题目的解题心得，分享给感兴趣的小伙伴：第1题：Let's Hash it Out - https://www.zkhack.dev/puzzle1.html第一题是个签名设计的问题。椭圆曲线的离散对数问题，保证在知道椭圆曲线点的情况下，无法推算出scalar。问题出在hash_to_curve的函数，只是按照hash的bit位进行椭圆曲线点的叠加。又因为椭圆曲线支持同态加计算，整个签名的计算过程可以看成是256个椭圆曲线点的0/1线性叠加。问题就转换成，需要求解256个椭圆曲线点。从题目给出的256个已知hash以及对应的签名结果，可以求解方程。第2题：Group Dynamics - https://www.zkhack.dev/puzzle2.html第二题是个有趣的题目。众所周知，椭圆曲线的子群上的点计算具有离散对数问题。深入一点看，这个子群有限制条件：子群的阶是质数，不能因子分解。如果某个子群的阶可以因子分解，则在这些因子上可以通过枚举的方法获取对应的scalar，并通过中国剩余定理（CRT）获取最初的子群上的阶。这条题目告诉大家，不能只看曲线的定义，还需要检查曲线上的点是否在合适的子群上。第3题：Double Trouble - https://www.zkhack.dev/puzzle3.html第三题需要一些想象力。该题设计的零知识证明系统本身没有问题。但是，为了加强Prover的计算性能，本来需要采用随机数的地方，简单的采用了之前证明计算的中间结果：没有完整的计算随机Scalar对应的Perdersen承诺，而是用之前计算的承诺值进行“Double”。这个Double操作是问题所在。该题目告诉大家，即使零知识证明系统设计没有问题，计算过程也需要多加小心，如果两个证明之间存在一些逻辑关系，有可能存在一些漏洞。第4题：Hidden in plain sight- https://www.zkhack.dev/puzzle4.html第4题的基础是多项式承诺KZG算法。承诺的设计采用了盲化多项式，但是这个盲化多项式是2阶，也就是这个盲化多项式有两个多形式系数。题目给出了两个挑战以及两个挑战对应的多项式的值，从而可以求解盲化多项式的系数，确定整个多项式的系数。第5题：To be Adaptive is to be Strong - https://www.zkhack.dev/puzzle5.html第5题涉及到Fiat-Shamir算法。这个算法可以将交互式的挑战转化为非交互式的挑战。该算法在零知识证明系统中大量运用。该算法实现了随机预言机，需要满足如下两个条件：1/ 每一次的不一样的查询返回随机数据 2/ 针对同样的查询返回同样的数据。只有在这样的前提下，这种非交互式的算法才是安全的。题目中的Fiat-Shamir算法的应用破坏了第一个条件，对于不一样的查询也返回了同样的数据。也就是说，采用Fiat-Shamir算法需要对挑战有关的所有数据进行hash计算，并不能只对其中的部分进行hash计算。第6题：So...

1650天前Star.LiStar Li星想法

[Star Li]零知识证明 - KZG多项式承诺

在网络上看到一篇非常棒的介绍KZG多项式承诺的文章：https://dankradfeist.de/ethereum/cryptography/2020/06/16/kate-polynomial-commitments.html翻译了一下，方便感兴趣的小伙伴查看。Dankrad多次帮忙校对翻译内容，甚至在他的blog创建了中文翻译链接。感谢Dankrad :)https://dankradfeist.de/ethereum/2021/10/13/kate-polynomial-commitments-mandarin.html

1712天前Star.LiStar Li零知识证明

[Star Li]零知识证明 - zkEVM解读

众所周知，zkRollup是L2中安全等级最高的Rollup方案，但是zkRollup目前没有可编程性，更无从谈起可组合性。zkEVM是用zk-SNARK技术将EVM的执行进行证明。zkRollup支持了zkEVM，在L2就能支持兼容EVM的智能合约。目前有几个团队都在研究zkEVM的实现。除了AppliedZKP公开了一些电路设计的思路和细节外，其他团队都没有详细的资料。AppliedZKP有关zkEVM的设计资料如下：https://github.com/appliedzkp/zkevm-specshttps://hackmd.io/Hy_nqH4yTOmjjS9nbOArgw本文详细分析AppliedZKP构想的zkEVM设计。本文中提到的zkEVM专指AppliedZKP提出的zkEVM方案。01背景以太坊的每一个节点为了确保交易的正确性，需要针对每一个区块中的每一笔交易执行。也就是说，每一个节点需要验证以太坊的整个交易历史，并且要一笔笔的进行执行验证。zkEVM利用零知识证明技术（zk-SNARK）证明：针对智能合约的交易执行，生成交易证明。在L2实现zkRollup支持可编程性。针对以太坊的每一个区块，生成区块证明。这些证明都由两部分组成：State proof（状态证明）和EVM proof（EVM执行证明）。在一条交易执行过程中，State包括Storage，Memory以及Stack的状态。Bus-mapping是设计的基础思想。一般的PC体系结构中，CPU通过总线访问存储（内存/硬盘），也就是计算和存储分开。zkEVM采用的同样的架构思想，状态的变化和指令的执行分开，并且分别由State proof和EVM proof进行证明。State proof负责Bus Mapping信息的一致性和正确性。一致性指的Bus Mapping和State之间的读写一致。正确性指的是Bus Mapping中的读写状态正确。EVM proof负责EVM的op code的执行正确（如果涉及到State的op code，保证存储相关的操作正确）。EVM Execution和存储之间好像有一条存储访问的总线一样：EVM Execution通过Bus Mapping获取或者存储执行需要的相关状态。采用Bus Mapping的方式，需要证明Bus Mapping和State以及EVM Execution之间的“总线”操作的正确性。逻辑上分成如下的几步：读取状态，EVM执行（修改状态），写回状态。Bus Mapping包括了读取以及写回状态。02Bus MappingBus Mapping包括了两种状态，一种是读取老的状态，一种是写回生成新的状态。无论是老的状态和新的状态，Bus Mapping都是“包含”关系。这种“包含”的mapping关系可以通过Plookup算法证明。存储状态（Storage/Memory/Stack），采用key-value的格式进行表示。key-value对的绑定关系可以实现为一个序列：def build_mapping():    keys = [1,3,5]    values = [2,4,6]    randomness = hash(keys, values)        mappings = []    for key , value in zip(keys,values):   &n...

1754天前Star.LizkEVM零知识证明

零知识证明 - zkEVM解读

众所周知，zkRollup是L2中安全等级最高的Rollup方案，但是zkRollup目前没有可编程性，更无从谈起可组合性。zkEVM是用zk-SNARK技术将EVM的执行进行证明。zkRollup支持了zkEVM，在L2就能支持兼容EVM的智能合约。目前有几个团队都在研究zkEVM的实现。除了AppliedZKP公开了一些电路设计的思路和细节外，其他团队都没有详细的资料。AppliedZKP有关zkEVM的设计资料如下：https://github.com/appliedzkp/zkevm-specshttps://hackmd.io/Hy_nqH4yTOmjjS9nbOArgw本文详细分析AppliedZKP构想的zkEVM设计。本文中提到的zkEVM专指AppliedZKP提出的zkEVM方案。01背景以太坊的每一个节点为了确保交易的正确性，需要针对每一个区块中的每一笔交易执行。也就是说，每一个节点需要验证以太坊的整个交易历史，并且要一笔笔的进行执行验证。zkEVM利用零知识证明技术（zk-SNARK）证明：针对智能合约的交易执行，生成交易证明。在L2实现zkRollup支持可编程性。针对以太坊的每一个区块，生成区块证明。这些证明都由两部分组成：State proof（状态证明）和EVM proof（EVM执行证明）。在一条交易执行过程中，State包括Storage，Memory以及Stack的状态。Bus-mapping是设计的基础思想。一般的PC体系结构中，CPU通过总线访问存储（内存/硬盘），也就是计算和存储分开。zkEVM采用的同样的架构思想，状态的变化和指令的执行分开，并且分别由State proof和EVM proof进行证明。State proof负责Bus Mapping信息的一致性和正确性。一致性指的Bus Mapping和State之间的读写一致。正确性指的是Bus Mapping中的读写状态正确。EVM proof负责EVM的op code的执行正确（如果涉及到State的op code，保证存储相关的操作正确）。EVM Execution和存储之间好像有一条存储访问的总线一样：EVM Execution通过Bus Mapping获取或者存储执行需要的相关状态。采用Bus Mapping的方式，需要证明Bus Mapping和State以及EVM Execution之间的“总线”操作的正确性。逻辑上分成如下的几步：读取状态，EVM执行（修改状态），写回状态。Bus Mapping包括了读取以及写回状态。02Bus MappingBus Mapping包括了两种状态，一种是读取老的状态，一种是写回生成新的状态。无论是老的状态和新的状态，Bus Mapping都是“包含”关系。这种“包含”的mapping关系可以通过Plookup算法证明。存储状态（Storage/Memory/Stack），采用key-value的格式进行表示。key-value对的绑定关系可以实现为一个序列：def build_mapping():    keys = [1,3,5]    values = [2,4,6]    randomness = hash(keys, values)    mappings = []    for key , value in zip(keys,values):      &nbs...

1757天前Star.LiRollupzkEVM

Dark Forest - 采用零知识证明技术的游戏

Dark Forest是一款MMO（大型多人在线游戏类型）游戏。我比较感兴趣的是这款游戏使用了零知识证明技术。零知识证明技术应用越来越丰富：隐私，跨链，zk Rollup，游戏等等。本文介绍Dark Forest的基本策略，如何结合零知识证明技术。在文章的最后，介绍最新版本v0.6 Round 3的游戏体验和截图。目前Dark Forest版本已经迭代到0.6。但是，github上的最新的代码并没有公开电路的部分。为了方便理解它如何采用零知识证明技术，可以查看github公布的0.3的完整代码：https://github.com/darkforest-eth/darkforest-v0.3.git01游戏策略看看智能合约的源代码，可以对Dark Forest的游戏策略有一定的了解。智能合约的源代码在目录：darkforest-v0.3/eth/contracts整个游戏宇宙由“星球”（Planet）组成：     struct Planet {         address owner;         uint256 range;         uint256 population;         uint256 populationCap;         uint256 populationGrowth;         PlanetResource planetResource;         uint256 silverCap;         uint256 silverGrowth;         uint256 silver;         uint256 silverMax;         uint256 planetLevel;         PlanetType planetType;     }一个星球有两种“资源”：人口（population）和矿（目前支持silver-银）。人口和矿慢慢增长，但是有上限。有矿可以升级。DarkForestInitialize.sol定义了几种星球类型。     struct ArrivalData {         uint256 id;         address player;         uint256 fromPlanet;         uint256 toPlanet;         uint256 popArriving;         uint256 silverMoved;         uint256 departureTim...

1772天前Star.LiStar Li，星想法，零知识证明

zkEVM - Hermez 设计思路

了解 Layer2 技术现状（特别是对 zk Rollup 技术）的小伙伴，知道 zk Rollup 目前不支持 EVM，缺失可编程性 / 可组合性，让 zk Rollup 限制在特定场景。zkEVM，通过 zkp 技术证明 EVM 的执行过程是非常有挑战的技术难点。EthCC 4 会议上 Hermez 团队介绍了他们对 zkEVM 的理解和设计：https://www.youtube.com/watch?v=17d5DG6L2nw Hermez 团队负责人 Jordi Baylina 比较清晰地给出了 zkEVM 大体的设计思路。本文梳理一下对 zkEVM 设计的理解。抛砖引玉，有理解偏差，小伙伴们可以留言讨论。虚拟机证明Jordi 在演讲开头提出：The Ethereum Virtual Machine was not designed to run in a zk-circuit （以太坊虚拟机在设计时并没有考虑 zk 电路证明）。也就是说，zkEVM 天生比较难。当初设计 EVM 的时候并没有考虑到后期还需要 zk 进行证明。在这种情况下，目前有三条路可以走：第一条：从头设计一种新的虚拟机，该虚拟机对 zk 友好，方便证明。不需要理会 EVM。第二条：从头设计一种新的虚拟机，该虚拟机对 zk 友好，方便证明。适配当前的 EVM 的开发工具，保持 solidity 兼容。第三条：直接支持 EVM 指令集，完全兼容 solidity 指令集。Hermez 团队选择了第三条。其他两种做法在当前的环境下，不太经济。Hermez 给出了选择第三条路的理由：总的来说，就是兼容性好，安全性高。总体思路因为 EVM 在设计当初没有考虑 zk 电路证明，支持 solidity 指令集需要引入中间指令（micro opcode）。这些中间指令比较适合电路证明。这些指令构成 uVM。EVM 需要编译在 uVM 中执行。众所周知，EVM 有一些变长的指令，比如 CALL，DATACOPY，EXP，CREATE 等等。这些指令天生对电路证明不友好。利用中间指令能相对友好地“表达”出这些指令的逻辑。对于一个区块中的所有交易，相关的指令可以一个个的执行。执行的模型是：老的状态 + 所有交易指令 -> 新的状态。一个细节是状态的迁移是以区块为单位，并不是以交易为单位的。多项式承诺在继续解释细节实现之前，Jordi 简单介绍了一下多项式承诺。多项式有两种表示方式：1/ 系数表示 2/ 点值表示。在给定一个多项式承诺（cm）的情况下，验证者可以提供随机挑战 r，证明者必须给出多项式在 r 的取值以及承诺证明。随机挑战值 r，可以通过 Fiat-Shamir 算法产生，将交互式的协议变成非交互式协议。在给出多个多项式承诺证明的前提下，通过取值的关系可以确定多项式之间的关系。通过多项式承诺可以证明如下的多项式关系：多项式相等，多项式取值等等。熟悉 Plonk 或者 Plookup 协议的小伙伴应该知道，这些协议的基础就是多项式承诺。零知识证明 - Plookup算法介绍零知识证明 - 深入理解PlonK算法uVM 的整体框架uVM 由如下的模块组成：ROM，RAM，Storage 以及各种计算功能模块。Main SM （主状态机）由子模块组成。需要证明程序的执行状态正确，要保证如下的一些状态正确：如何证明执行程序正确？执行程序存储在 ROM 中。将指令和位置进行编码后，得到执行程序的多项式表示 rom (x)。将 Main SM 中的代码执行指令和 PC 进行同样的编...

1777天前Star.LiHermezLayer 2

跨链 - 技术分类总结

最近看了看跨链相关的项目，总结一下跨链的相关技术。所谓“跨链”，一条链上的“跨链”语义能在另外链上正确执行。目前跨链项目主要实现在一个链上的资产映射到另外一条链上。从技术角度看，个人认为目前跨链技术主要有三种：HTLC，跨链桥（基于共识）和跨链桥（基于轻客户端）。相关的技术以及项目总结如下图：1.HTLC（Hash Time Lock Contract）HTLC原理比较简单：如果Alice和Tom之间想交换资产，Alice先创建HTLC，Tom接着创建具有同样Hash的HTLC。简单的说，Tom和Alice创建了具有同样秘钥的“锁”，锁住各自资产。当Alice用秘钥打开Tom的资产时，Tom用同样的秘钥可以打开Alice的资产。当然，Tom和Alice都需要确认资产和锁的时间。通过HTLC实现跨链，简单并且保证了交易双方的原子操作，但是要求两条链都支持智能合约，限定了两个交易方并且交换的资产不可分割。事实上，为了保证交易双方有效交易，交易双方需要额外的沟通渠道预先达成共识。2.跨链桥：基于共识基于其他共识的跨链桥逻辑上比较好实现，由共识确认一个链上的事件，并在另外一条链上执行。整个桥的安全性取决于共识的强弱。共识，除了传统意义的共识机制（BFT，PoS等等）外，还包括多方计算（MPC）和多签。3.跨链桥：基于轻客户端为了在一条链上能验证另外一条链上的信息，在这条链上“运行”另外一条链的轻客户端。通常轻客户端都是基于SPV（Simple Payment Verification）协议。SPV源自BTC，主要用在PoW共识的链中。Celo和Harmony也针对自己链的共识算法实现了轻客户端。纯粹的PoS共识的链比较难实现轻客户端，因为共识依赖Staking，而Staking由交易组成。为了实现轻客户端，穷举Staking交易不现实。跨链桥的两个链互相通过轻客户端验证对方链的状态。这种跨链桥依赖Relay（中继），及时同步链的区块头信息。因为要同步区块头，需要如下的一些因素：1.同步频次和费用：在另外一条链上存储区块头信息需要费用。特别是tps比较高的链，区块比较多。2.确认主链以及区块确认：根据链的共识，通过区块头信息确定主链。以PoW的链为例，区块确认一般通过后续区块个数确认。优化同步费用有几种思路：1/ 随机挑战（NiPoPOW，FlyClient）2/ zk-SNARK （包括recursive zk-SNARK）。选一些典型介绍：BTCRelay采用传统的SPV轻客户端的实现方式实现从BTC到ETH的跨链。显然为了同步BTC的区块头，在ETH消耗Gas。在以太坊Gas price比较高的情况下，同步费用比较高。FlyClientFlyClient采用随机挑战和MMR（Merkle Mountain Range)的技术，降低轻客户端同步区块的个数。随机挑战的目的是在一定范围的区块并不需要全部同步到链上，随机抽取一些区块同步。为了在链上能验证没有抽取到的区块，所有的区块信息通过MMR组织在一起。MMR是一种变种的Merkle树，适用于追加节点的场景。MMR，相对于普通二叉的Merkle树，具有更新叶子结点代价小的特点。zkRelayzkRelay也尝试降低链上轻客户端同步区块的费用。和FlyClient不同，zkRelay采用的是zk-SNARK证明。将一段范围内的区块有效性，通过将链下证明提交到链上，链上只需要检查证明是否有效。CeloCelo是个有意思的项目。Celo项目本身和跨链没有什么关系，但是给轻客户端提供了一些新思路。为了实现更...

1785天前Star.LiBFT，PoSHTLC

L2 - 理解和思考

Layer2是个大的话题。是否去中心化，是否安全，资金状态确认时间是Layer2的主要的讨论话题。最近有点时间，总结一下Layer2的理解和思考。Layer2交互模型Layer2，相对于Layer1，在Layer1的基础上提供更丰富功能，更好的用户体验。抽象一下Layer2的逻辑以及交互模型如下：图片除了Layer1的交易外（入金），其他Layer2的交易都在Layer2执行。为了Layer2在必要时恢复交易状态，所有Layer2的交易数据需要安全存储。简单起见，也为了和Layer1保持一样的安全性，所有Layer2的交易数据一般存储在Layer1。这种交易数据的随时可访问，称为"Data Availability"（数据可用性）。所有的Layer2交易都在Layer2执行，并同步到Layer1。如何证明Layer2同步的状态正确，不同的layer2方案有不同的实现方法。Layer2实现分类从Layer2状态同步方式，Layer2分为两类：一类是侧链实现（Side Chain），一类是Rollup。侧链，就是通过不同于Layer1的共识进行Layer2状态向Layer1的同步。仅从这一点，整个侧链的安全性，就降低到Layer2的共识的安全性。Rollup又分为两种：一种是zkRollup，一种是Optimistic Rollup。所谓Optimistic Rollup，乐观性Rollup，期望绝大多数情况下Rollup正确向Layer1同步状态。同时，为了防止同步错误的状态，提供了挑战机制。乐观预计挑战的机率比较小。在需要挑战的情况下，Layer1可以判断正确状态。zkRollup是最直接的状态同步方式，通过零知识证明技术，在向Layer1提交状态的同时提供状态变化的证明。Layer实现分类如下：zkRollup，按照采用的零知识证明协议又分为三类：1/ Groth16 2/ PLONK 3/ STARK。Groth16协议需要针对每一个电路进行初始设置(Trusted Setup)。PLONK协议在一定规模下的电路只需要一次初始设置。STARK协议不需要初始设置。但是，相对另外两种算法，STARK协议，证明数据量大，验证时间长。相对来说，在Layer2的场景下，PLONK是目前广泛使用的算法。STARK协议和SNARK(Groth16/PLONK)协议比较（来源于Matter Labs的github链接）：https://github.com/matter-labs/awesome-zero-knowledge-proofs总结一下，从安全性角度看，各种Layer2的排序如下：zkRollup，optimistic Rollup，侧链。从提现的时间也印证了安全性，zkRollup的提现是分钟级别，其他两种方案，小时甚至是天级别。zkSync是比较完善的zkRollup开源项目，感兴趣的小伙伴可以查看之前的分析文章：L2 - zkSync源代码导读L2 - 深入理解zkSync电路zkRollup，虽好，目前存在很大的缺陷：可编程性差。细看zkRollup相对其他Rollup方案，zkRollup方案多了zk证明系统。也就是说，在Layer2每个交易除了“执行”外，还需要生成证明，证明执行过程的正确性。熟悉零知识证明技术的小伙伴都知道，零知识证明的安全性在于”电路“的安全性。对于Layer2，每种交易的处理”固化“为电路，电路逻辑完全公开。对应于每种电路，存在唯一的验证秘钥。验证秘钥用在Layer1验证状态证明。通过验证的状态...

1806天前Star.LiArbitrumAVM

深入理解以太坊二层方案 Arbitrum 技术架构

Arbitrum是Layer2 Rollup的一种方案。和Optimism类似，状态的终局性采用“挑战”(challenge)机制进行保证。Optimism的挑战方法是将某个交易完全在Layer1模拟执行，判断交易执行后的状态是否正确。这种方法需要在Layer1模拟EVM的执行环境，相对复杂。Arbitrum的挑战相对轻便一些，在Layer1执行某个操作（AVM），确定该操作执行是否正确。Arbitrum介绍文档中提到，整个挑战需要大概500字节的数据和9w左右的gas。为了这种轻便的挑战机制，Arbitrum实现了AVM虚拟机，并在AVM虚拟机中实现了EVM的执行。AVM虚拟机的优势在于底层结构方便状态证明。Arbitrum的开发者文档详细介绍了Arbitrum架构和设计。对AVM以及L1/L2交互细节感兴趣的小伙伴可以耐心地查看"Inside Arbitrum"章节：https://developer.offchainlabs.com/docs/developer_quickstart整体框架Arbitrum的开发者文档给出了各个模块关系：Arbitrum的系统主要由三部分组成（图中的右部分，从下到上）：EthBridge，AVM执行环境和ArbOS。EthBridge主要实现了inbox/outbox管理以及Rollup协议。EthBridge实现在Layer1。ArbOS在AVM虚拟机上执行EVM。简单的说，Arbitrum在Layer2实现了AVM虚拟机，在虚拟机上再模拟EVM执行环境。用AVM再模拟EVM的原因是AVM的状态更好表达，便于Layer1进行挑战。EthBridge和AVM执行环境对应的源代码：https://github.com/OffchainLabs/arbitrum.gitArbOS对应的源代码：https://github.com/OffchainLabs/arb-os.git这个模块关系图太过笼统，再细分一下：EthBridge主要实现了三部分功能：inbox，outbox以及Rollup协议。inbox中“存放”交易信息，这些交易信息会“同步”到ArbOS并执行。outbox中“存放”从L2到L1的交易，主要是withdrawl交易。Rollup协议主要是L2的状态保存以及挑战。特别注意的是，Arbitrum的所有的交易都是先提交到L1，再到ArbOS执行。ArbOS除了对外的一些接口外，主要实现了EVM模拟器。整个模拟器实现在AVM之上。整个EVM模拟器采用mini语言实现，Arbitrum实现了AVM上的mini语言编译器。简单的说，Arbitrum定义了新的硬件（machine）和指令集，并实现了一种上层语言mini。通过mini语言，Arbitrum实现了EVM模拟器，可以执行相应交易。AVM State因为所有的交易都是在AVM执行，交易的执行状态可以用AVM状态表示。AVM相关实现的代码在arbitrum/packages/arb-avm-cpp中。AVM的状态由PC，Stack，Register等状态组成。AVM的状态是这些状态的hash值拼接后的hash结果。AVM使用c++实现，AVM表示的逻辑实现在MachineStateKeys类的machineHash函数（machinestate.cpp）中。AVM的特别之处就是除了执行外，还能较方便的表达（证明）执行状态。深入理解AVM的基本数据结构，AVM的基本的数据类型包括： using value = ...

1827天前Star.LiEVMLayer 2