零知识证明
MAP Protocol 用零知识证明 (ZK) 优化轻客户端验证网络。
Last updated
MAP Protocol 用零知识证明 (ZK) 优化轻客户端验证网络。
Last updated
零知识证明最早出现在1985年的论文 —— “交互式证明系统的知识复杂性” —— 它是一种密码学协议，允许一方（证明者）向另一方（验证者）证明一个给定的陈述是真实的，而不会透露任何超出该陈述本身有效性的信息。这意味着验证者除了了解该陈述确实为真之外，不会学到任何关于陈述或支撑它的信息。
它基于挑战-响应协议的原理运作。证明者做出断言，并向验证者提供证据，而不泄露任何关键信息。然后，验证者向证明者提出挑战，证明者必须以一种方式回应，以使验证者相信断言的真实性。这个过程重复多次，以确保证明是准确的，而不是偶然的结果。零知识证明的安全性依赖于某些数学问题的计算难度，确保对手无法欺骗系统。
从金融交易和供应链到身份验证，零知识证明在各个行业都有广泛的应用。除了那些常见的用例，zk-proof还可用于提高网络验证效率。MAP协议已经使用zk-proof重构了其轻客户端验证网络。
脉波的跨链验证主要由部署在目标链上的起源链轻客户端智能合约执行以下两种验证：
区块头的正确性验证：验证维护者请求写入的区块头的合法性，根据链共识机制的不同，该验证方案会有所差异。对于采用PoS和BFT机制的链，通常是验证区块头中包含的合法签名所代表的投票权重超过2/3。
默克尔证明的验证：验证在特定的区块高度中有emit特定事件，所需的正确的Merkle根值在区块头中，由第一步确保正确性，在与以太坊结构类似的区块链群体中，该默克尔证明通常是Merkle Patricia Trie的存在性证明，也即收据树MPT中确实存在特定的event。
基于zkSNARK 技术来改进MAP中继链的轻客户端实现，旨在解决两个问题。
减少轻客户端合约中所需存储关于MAP中继链元信息的数量，降低轻客户端本身状态更新时的燃气费消耗；
将区块头合法性验证过程中签名合法性以及签名权重检查部分放入零知识证明电路中，利用Groth16方案完成验证，以降低燃气费消耗。
在MAP中继链轻客户端智能合约中，需要存储当前epoch的所有验证者的公钥以及质押权重信息。当验证新区块头的合法性时，根据区块头中的信息和轻客户端自身存储的当前验证者信息，轻客户端合约可以计算出验证区块头中聚合签名所需的聚合公钥。如果聚合签名验证通过，并且聚合公钥所代表的验证者的投票权重之和超过了2/3，那么区块头就会通过验证。基于zkSNARK构建的MAP中继链轻客户端中，只需要存储关于当前验证者集合元信息的commit值，即SHA256((pk_0, wt_0), (pk_1, wt_1), ... , (pk_n, wt_n))。这意味著轻客户端合约从需要存储n个公钥和权重信息精简为只需要存储256比特的commit值。
因此，基于zkSNARK构建的MAP中继链轻客户端的区块头验证逻辑可以简单表述为：输入的区块头在当前commit值所代表的验证者集合信息中是否为正确的区块。这一判断的成立与否取决于随著区块头一起输入的zkSNARK证明。
为了表述清晰，以下是引入zkSNARK后跨链流程中新引入的证明人 (Prover) 的角色以及更新的messenger/maintainer的逻辑，以及每一方所接受的输入：
Prover的输入为：区块头、当前验证者集合中每个验证者的公钥以及投票权重。
Circuit的输入为：t0 和t1、待验证的聚合签名、当前验证者集合中每个验证者的公钥以及投票权重、指示聚合验证者的bitmap.
轻客户端验证event合法性的输入为：区块头、zk-proof以及mpt-proof。
轻客户端验证sync commit合法性的输入为：区块头、zk-proof。
其中，t0和t1是区块头hashToG1的中间值，参考当前的轻客户端实现代码。之所以circuit选择t0 和t1作为输入，而非区块头整体作为输入的原因是：hashToG1的计算内部hashToBase用circuit来表达代价比较大，得不偿失。当prover服务器拿到maintainer或者messenger提交的区块头信息之后，继续执行相关操作。
Prover可以理解为生成证明的伺服器，对外暴露一个证明生成请求接口，接口的输入参数为：区块头、当前验证者集合每一个验证者的公钥以及投票权重。接口的输出为zk-proof。由于前述原因，prover在开始计算zk-proof之前，首先从请求中的区块头中抽取并计算出生成zk-proof所需的参数： t0 和和 t1 、指示参与聚合签名的验证者的bitmap，然后执行zk-proof的具体计算过程。
根据区块头中bitmap的指示以及全量的验证者集合的信息，计算出聚合公钥，校验聚合公钥所代表的签名权重超过了2/3。
根据 t0 和 t1，计算出 hashToG1 的最终结果，利用该值、待验证聚合公钥以及聚合BLS验证，检查签名合法性。
而最终的zk-proof也就是为上述statement在特定public input下的合法性做了断言。在轻客户端验证区块头的过程中，会根据自己存储的commit信息以及待验证的区块头信息，构造出public input，并验证zk-proof的合法性。如果能够验证通过，则意味著该zk-proof有效，进而证明了相应区块头的合法性。
以轻客户端验证事件合法性为例，其输入包括区块头、zk-proof以及merkle-proof。整个证明验证过程如下：
根据输入的区块头，以及hashToBase计算出t0和t1。
将t0和t1以及自身存储的当前验证者集合的commit作为公共输入，按照groth-16方案验证zk-proof的合法性。
如果第二步验证通过，则表示区块头是合法的，接著从中提取出Merkle Patricia Tree（MPT）的根节点（MPT root），继续验证mpt-proof的合法性。
步骤一是为了配合circuit的构造方式，引入的额外计算也是用合适的方案验证做合适的事情的原则体现：hashToBase所涉及到的计算用solidity完成代价不高，用circuit来做则得不偿失。区块头验证的关键步骤是第二步，第二步实际上是验证了一件事情：输入的区块头在轻客户端存储的commit所对应的验证者集合下是一个合法的区块头。这一推断根据circuit的内部逻辑容易推断出来。第三步则与目前轻客户端的实现没有差异。
轻客户端验证同步提交合法性的过程与上述过程基本保持一致，唯一不同的是将第三步的验证MPT根合法性的操作替换为根据新的验证者集合信息重新计算commit，并更新自身存储。
根据前述论述，MAP中继链的轻客户端在基于zkSNARK升级之后，maintainer/messenger需要做的相应调整如下：
Maintainer想要更新轻客户端状态前，需要从prover处获得zk-proof，并用区块头、zk-proof构造tx。
Messenger想要调用发起跨链请求前，也需要从prover处获得zk-proof，并用区块头、zk-proof以及mpt-proof构造tx。
透过前端进行跨链交互的用户，通常会感受到背后发生的变化。为了突出零知识证明的特性，可以在前端展示一些与零知识证明相关的信息：
当messenger提交zk-proof请求后，前端可以简单地显示通知提示，例如：“已提交跨链zk-proof请求给证明者”。
当messenger获得zk-proof请求后，前端可以简单地显示通知提示，例如：“已获得zk-proof”。
当messenger提交包含区块头、zk-proof以及mpt-proof的交易后，前端提示：“已提交zk-proof和跨链请求给目标链”。
在第三步的交易打包后，前端可以提示：“zk-proof和跨链请求已被目标链处理”。
