Star Li · 18

IOSG Weekly Brief ｜零知识证明 - FPGA vs GPU #177

Part.1 Insight零知识证明 - FPGA vs. GPU作者：Star Li本文仅做行业学习交流之用，不构成任何投资参考。如需引用，请注明来源，转载请联系 IOSG 团队获取授权及转载须知。特别感谢作者 Star Li 提供的内容！零知识证明技术应用越来越广，隐私证明，计算证明，共识证明等等。在寻找更多更好的应用场景的同时，很多人逐步发现零知识证明证明性能是个瓶颈。Trapdoor Tech 团队从 2019 年开始深入研究零知识证明技术，并一直探索高效的零知识证明加速方案。GPU 或者 FPGA 是目前市面上比较常见的加速平台。本文从 MSM 的计算入手，分析 FPGA 和  GPU加速零知识证明计算的优缺点。TL;DRZKP是拥有未来广泛前景的技术。越来越多的应用开始采用零知识证明技术。但ZKP算法比较多，各种项目使用不同的ZKP算法。同时，ZKP证明的计算性能比较差。本文详细分析了MSM算法，椭圆曲线点加算法，蒙哥马利乘法算法等等，并对比了GPU和FPGA在BLS12_381曲线点加的性能差别。总的来说，在ZKP证明计算方面，短期GPU优势比较明显，Throughput高，性价比高，具有可编程性等等。FPGA相对来说，功耗有一定的优势。长期看，有可能出现适合ZKP计算的FPGA芯片，也可能为ZKP定制的ASIC芯片。ZKP 算法复杂ZKP是个零知识证明技术的统称（Zero Knowledge Proof）。主要由两种分类：zk-SNARK以及zk-STARK。zk-SNARK目前常见的算法是Groth16，PLONK，PLOOKUP，Marlin和Halo/Halo2。zk-SNARK算法的迭代主要是沿着两条方向：1/是否需要trusted setup 2/电路结构的性能。zk-STARK算法的优势是毋需trusted setup，但是验证计算量是对数线性的。就zk-SNARK/zk-STARK算法的应用来看，不同项目使用的零知识证明算法相对分散。zk-SNARK算法应用中，因为PLONK/Halo2算法是universal（无需trusted setup），应用可能越来越多。PLONK 证明计算量以PLONK算法为例，剖析一下PLONK证明的计算量。PLONK证明部分的计算量由四部分组成：1/ MSM - Multiple Scalar Multiplication。MSM经常用来计算多项式承诺。2/ NTT计算 - 多项式在点值和系数表示之间变换。3/ Polynomial计算 - 多项式加减乘除。多项式求值（Evaluation）等等。4/ Circuit Synthesize - 电路综合。这部分的计算和电路的规模/复杂度有关。Circuit Synthesize部分的计算量一般来说判断和循环逻辑比较多，并行度比较低，更适合CPU计算。通常来讲，零知识证明加速一般指的是前三部分的计算加速。其中，MSM的计算量相对来说最大，NTT次之。What's MSMMSM（Multiple Scalar Multiplication）指的是给定一系列的椭圆曲线上的点和标量，计算出这些点加的结果对应的点。比如说，给定一个椭圆曲线上的一系列的点：Given a fixed set of Elliptic curve points from one specified curve:[G_1, G_2, G_3, ..., G_n]以及随机的系数：and a randomly sampled finite field el...

1165天前IOSG#IOSG #零知识证明

[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

1771天前Star.Li#Star 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...

1813天前Star.Li#zkEVM #零知识证明

IOSG Weekly Brief | L2的理解与思考 #88

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验证状态证明。通过验证的状态证明...

1838天前IOSG#EVM #IOSG #L2 #Rollup #以太坊 #侧链

L2 - zkSync服务搭建

2020最后一天，感触颇多。一年时间，聚焦在零知识证明的技术应用，时间过的好快。新的零知识证明算法解决初始设置问题，解决FFT计算性能问题，解决递归证明问题。零知识证明有广阔的应用场景和空间，但是，目前工程应用还是偏弱。如何工程上更好的应用零知识技术，提高零知识证明的计算性能是Trapdoor Tech致力的方向和目标。zkSync是值得好好学习的L2方案。最近有空梳理了一下zkSync服务实战的流程，感兴趣的小伙伴可以对照着跑跑，感受一下L2的魅力，感受一下零知识证明的应用。安装环境准备zkSync提供了完整的前后端以及智能合约的实现。在运行zkSync系统之前需要安装很多依赖库和工具，大家可以按照下面的链接设置开发环境。https://github.com/matter-labs/zksync/blob/master/docs/setup-dev.md端口映射zkSync系统使用如下的一系列端口，总结如下：8080：客户端访问接口8545：以太坊web3接口3001：REST API接口3030：HTTP RPC接口3031：WS RPC接口7000：浏览器服务端口启动Server先下载源代码：https://github.com/matter-labs/zksync在“安装环境准备”的步骤中，设置了ZKSYNC_HOME和PATH环境变量，所以可以直接使用zksync命令启动server。zksync init ulimit -n 4096 zksync server默认情况下，Server会启动以太坊的local开发网络。在zksync init的步骤中，会在开发网络上部署智能合约。启动Prover零知识证明的计算是由Prover完成的。zksync prover启动前端服务修改 js/env-config.js，配置四个服务的IP以及端口：     "http://localhost": {          API_SERVER: "http://localhost:3001",          ETH_NETWORK: "localhost",          WS_API_ADDR: "ws://localhost:3031",          HTTP_RPC_API_ADDR: "http://localhost:3030",      }启动client：zksync client启动浏览器服务zkSync的浏览器提供区块以及交易信息，启动方式如下：zksync explorer启动前端zkSync依赖metamask进行交易签名，在打开前端页面之前需要配置metamask，RPC网络接口：在创建以太坊的local开发网络时，在创世纪区块...

2059天前Star.Li#zkSync #二层 #零知识证明

零知识证明 - 深入理解powersoftau

学习区块链技术的小伙伴不知道有没有同样的体验，每天脑袋都在膨胀，每天都有很多新鲜的知识需要学习总结。最近有些空闲时间看了看powersoftau。了解零知识证明算法的小伙伴的都知道，在利用某些零知识证明算法之前，需要可信设置。Groth16算法针对不同的电路需要单独的可信设置，生成CRS。PLONK算法是Univeral的零知识证明算法，针对不同的电路，在电路规模不超过一定范围的情况下，只需要一次可信设置。如何让多个参与方安全地进行可信设置，生成零知识证明的可信参数，就是powersoftau解决的事情。powersoftau，采用MPC以及随机Beacon，完成可信设置。理论基础目前开源的powersoftau采用的是2017发表的论文：Scalable Multi-party Computation for zk-SNARK Parameters in the Random Beacon Modelhttps://eprint.iacr.org/2017/1050参与方/协调方整个可信设置由参与方（player）以及协调方（coordinator）组成。协调方将前一个参与方生成的数据发送给下一个参与方。在所有参与方计算完成后，协调方再通过公开随机Beacon参与计算生成最后的参数。协调方，并不需要可信第三方，因为协调方通过公开随机Beacon生成的参数是可以验证的。所谓的公开随机Beacon，是在某个时间点之前并不知道的随机性数据，并且在同一个时间点后，所有人都可以验证随机数据。Phase1/Pahse2论文的第二章给出了整个协议的大体思路。假设Alice和Bob是两个参与方，整个协议逻辑上分成两步：Phase1和Phase2。Phase1计算出某个多项式项的tau对应的值。Phase2计算出整个多项式对应的值。注意这些值都是有限域上的点。简单的说，Phase1提供单个项的MPC的计算结果，Phase2提供多项组合的MPC的计算结果。Phase1和Phase2计算流程类似，参与方一个个的接着做。整个协议涉及两个基本计算：CONSISTENT和POK。CONSISTENTCONSISTENT用来检查两个配对函数的结果是否相等。检查A，B，C是否满足e(A,B) = e(C1,C2)，记为：consistent(A-B; C)。POKPOK - proof of knowledge。参数alpha是知识（knowledge）。为了证明知道知识alpha，先计算出r（alpha对应的G1上的点和公共字符串v），并生成G2上的点。通过提供alpha在G1上的点以及alpha*r，可以证明知道知识alpha。证明可以通过配对函数进行验证。协议逻辑论文的第四章给出了整个协议的定义。电路被抽象成两个结构：一个结构是计算过程只有乘除的电路部分，一个结构是组合部分。对一个电路，证明的计算过程如下：1(a) - 对电路中的每个输入，进行POK的证明。注意v是上一层的结果计算生成。1(b) - 在上一参与者计算结果的基础上，计算当前参与者的计算结果。其中M是电路的多项式函数。2 - 应用随机Beacon相对于计算过程，验证过程也比较清晰：验证POK证明，验证M的计算是否正确。论文的第6/7章，详细给出了Groth16算法参数的生成过程。感兴趣的小伙伴，可以自行查看。源代码分析powersoftau在github上有多个项目，大同小异。以matter labs的代码为例，分析一下代码逻辑。https://github.com/matter-labs/powersof...

2066天前Star.Li#powersoftau #零知识证明

Filecoin - 一个越界Bug引发升级

Filecoin在11月24号需要强制升级，好奇看了看最新的代码。不看不知道，一看吓一跳。一个越界的Bug引发了这次升级。这个越界的Bug使程序实现的SDR算法和协议不一致。利用这个越界的Bug可以提升SDR的性能50%左右。1 官方补丁在11.02号官方提交一个补丁：commit 0d17d7466f40e1228a4bab25f8b4861cb0d2da4d Author: Friedel Ziegelmayer <me@dignifiedquire.com> Date:   Mon Nov 2 12:06:36 2020 +0100     fix(storage-proofs-porep): fix graph generation     - expander: divide before casting to u32     - drg: move predecessor to the first position这个补丁比较重要，这个补丁“修正”了当前的协议。整个SDR算法中节点的连接关系也发生了改变。先讲讲简单的 drg: move predecessor to the first position改动，比较简单：-    parents[m_prime] = node - 1; +    // Immediate predecessor must be the first parent, so hashing cannot begin early. +    parents[predecessor_index] = node - 1;一个节点的Base父亲节点的依赖，从原来的是最后一个Base父亲节点依赖上一个节点，变成了第一个Base父亲节点依赖上一个节点。简单的说，如果Base父亲节点的最后一个才依赖上一个节点，那Base父亲节点的前面一些节点可以先计算，无须依赖上一个节点的计算。使用老的算法，虽然不能完全提前算整个节点的结果，但是能提前一点好一点。改成最新的协议，这一点点也不能提前算了。2 越界Bug重点在于这个改动：expander: divide before casting to u32改动：原始逻辑，就是在is_legacy包裹住的逻辑：transformed as u32 / self.expansion_degree as u32transformed的值是通过Feistel加密算法生成，具体的逻辑含义可以查看之前的文章。即使在不需要知道逻辑的情况下，可以估算出整个表达式的计算结果的范围。self.expansion_d...

2099天前Star.Li#Filecoin

L2 - 深入理解zkSync电路

zkSync的电路设计很有意思，值得好好学习。众所周知，一个区块中会打包不同的交易，如果只是针对一个个交易进行电路的证明，电路大小会变化。zkSync将交易切割成更小的“通用电路“。一个区块中包含固定的”通用电路“，间接支持多个交易。zkSync的源代码目录下的docs/circuit.md简述了zksync的电路实现的原理以及各个操作的结构。zkSync的Layer2交易证明基于PLONK证明系统，功能模块如下：1. 电路表示zksync的电路由FranklinCircuit结构表示。整个电路的逻辑实现在core/circuit/src/circuit.rs。pub struct FranklinCircuit<'a, E: RescueEngine + JubjubEngine> {     pub rescue_params: &'a <E as RescueEngine>::Params,     pub jubjub_params: &'a <E as JubjubEngine>::Params,     /// The old root of the tree     pub old_root: Option<E::Fr>,     pub initial_used_subtree_root: Option<E::Fr>,     pub block_number: Option<E::Fr>,     pub validator_address: Option<E::Fr>,     pub pub_data_commitment: Option<E::Fr>,     pub operations: Vec<Operation<E>>,     pub validator_balances: Vec<Option<E::Fr>>,     pub validator_audit_path: Vec<Option<E::Fr>>,     pub validator_account: AccountWitness<E>, }FranklinCircuit包括了Rescue以及Jubjub参数，老的状态根，Validat...

2107天前Star.Li#​zkSync

L2 - 深入理解OVM

Optimistic Rollup是Layer2潜在的一种方案。周末有点时间，在网络上翻了翻。网络上的文章，Optimistic Rollup深入技术的文章不多，介绍OVM底层技术细节的文章则更少。感兴趣看了看Optimism实现的OVM功能相关的智能合约，对Optimistic Rollup的理解很有帮助。总结一下，感兴趣的小伙伴可以看看。1. Optimistic Rollup vs. zk Rollup网络上对比这两种Rollup的方案文章不多。主要的一篇文章是：https://medium.com/matter-labs/optimistic-vs-zk-rollup-deep-dive-ea141e71e075国内也有对应的翻译文章：https://ethfans.org/posts/optimistic-vs-zk-rollup-deep-dive具体的性能和安全性对比，感兴趣的小伙伴可以直接看这篇文章。个人觉得，因为方案都不够成熟，目前方案能够达到的TPS都只是理论值。没必要太多的讨论。主要说说两种Rollup的技术实现的区别：两种方案都是Rollup，Layer2的所有Transaction的信息都会作为CallData“存储”在Layer1，并且Layer2的状态也及时同步到Layer1。两者的区别在于，Layer2的状态在Layer1的正确性保证。Optimistic Rollup采用的是“检察”的方式，任何一个节点发现Layer2的状态的错误，提交相关的证明。如果错误的状态被验证，在Layer1的Layer2的状态需要回滚，提交错误状态的节点被惩罚。zk Rollup采用的方式直接了当，在向Layer1提交Layer2状态的同时，提交相关状态改变的证明。这些证明都是在Layer2生成。也就是说，zk Rollup在向Layer1提交Layer2状态的同时，同时提交了Layer2状态转换的计算证明。这个计算证明是通过零知识证明的算法产生。简单的说，如果转换的状态复杂，生成零知识证明的时间越长。目前，zk Rollup只是支持简单的账户系统以及世界状态，并不能支持智能合约等复杂的世界状态。Optimistic Rollup虽然能支持智能合约，事实上，因为Layer1的计算能力比较弱，智能合约的支持也比较有限。Optimistic Rollup支持的智能合约的执行环境，类似EVM，称为 OVM（Optimistic Virtual Machine）。2 OVMOVM - Optimistic Virtual Machine。OVM是Layer2交易的执行环境。因为提交到Layer1的状态需要检验正确性，Layer1需要“重放”Layer2的交易，也就是说，Layer1在有些情况下需要执行OVM交易的执行。Optimistic Rollup最复杂的地方也在于此，用EVM模拟OVM，并执行Layer2的交易。Optimism实现了EVM模拟OVM的逻辑，相关的项目的Github地址：https://github.com/ethereum-optimism/contracts-v2本文中使用的代码的最后一个提交信息如下：commit ca1fede6c8cb9e4eacd8205c1d53284d0c8debdc Author: Mark Tyneway <mark.tyneway@gmail.com> Date:   Fri Oct&nbs...

2116天前Star.Li#OVM #二层

L2 - zkSync源代码导读

Layer2是一个大方向。最近一段时间，会围绕L2写一些文章。区块链技术有趣的地方就是一种技术的发展打开了一扇窗。零知识证明的发展拓宽了区块链L2的视角，提供了L2的另外一种实现可能，即zk Rollup。从另外一个角度看，区块链的进步是缓慢的，需要很多优秀的人才跨界把不同的技术揉杂在一起，让不可能成为可能。matter labs在zk Rollup方向的积累比较深，有一系列的开源项目可以学习。让我们从zkSync开始吧。zkSync的源代码地址，所有的逻辑使用rust语言开发：https://github.com/matter-labs/zksync.git特别注意的是，查看完整源代码需要查看dev分支，并不是master分支。master分支提供编译后的各种执行程序。本文采用的代码的最后一个提交信息如下：1 源代码目录结构zkSync项目实现了L2相关的方方面面。查看zkSync的提交记录，这个项目创建于2018年的11月份，已经有两年的开发时间。从matter labs公开的各种项目，matter labs在zk rollup想的很远，也已经走的蛮远。细想想，踏踏实实地思考区块链技术，认认真真地把一小点积累做好。整个源代码目录结构如下：bin - 一些二进制程序和脚步contracts - 智能合约逻辑core - L2的核心逻辑docker - docker相关的配置docs - 文档，比较详细的解释了zkSync的协议设计，电路实现，智能合约，K8如何配置，以及如何启动等等。etc - 配置信息js - zkSync客户端以及浏览器（explorer）zkSync的内容比较多，这篇文章主要给大家讲讲zkSync的大体逻辑结构，重点介绍智能合约以及core的相关逻辑。所有zkSync的核心逻辑都实现在core的目录下：core/circuit - 零知识证明电路实现core/crypto_exports - 零知识证明底层库封装core/data_restore - 状态恢复的相关逻辑core/eth_client - eth客户端的封装core/loadtest - 压力测试相关逻辑core/models - zkSync的模型定义core/plasma - zkSync的状态实现core/prover - 零知识证明的证明生成引擎core/server - 各种server的实现，包括eth的监测(watch)和交易发送(sender)，交易费用的计算(fee_ticker)，零知识证明的服务器(prover server)以及API服务等等core/storage - 所有状态的存储以及持久化逻辑2 整体架构zkSync目前主要实现了L2的转账功能。L2有自己的账户系统以及状态。zkSync总体的功能模块以及相互之间的关系如下：Eth Watch以及Eth Sender负责监控和发送zkSync智能合约的交易。Mem Pool负责收集交易。交易分为两种两种：L1交易和L2交易。Block Proposer将交易打包，并更改世界状态(Plasma State)。在世界状态更改后，通过Block Committer生成证明需要的信息。零知识的证明通过Plonk证明系统生成，其中包括Prover Server和Proving Client。API提供接口实现UI的信息展示和L2的交易提交。3 L2账户系统和世界状态zkSync并不需要独立生成新账户。zkSync的L2账户和L1账户一一对应，“共享”一份私钥。简单的说，L1的私钥的ECDS...

2123天前Star.Li#zkSync #二层