零知识证明 – 电路及证明示例(libsnark)
libsnark库代码层次非常清晰。libsnark也给出了SNARK相关算法的全貌,各种Relation,Language,Proof System。为了更好的生成R1CS电路,libsnark抽象出protoboard和gadget,方便开发者快速搭建电路。在阅读该示例代码前,请仔细阅读libsnark的源代码分析:
唯一有点遗憾的,libsnark没有给个完整的电路构造实例,入门者想搭建自己的电路,刚开始有点摸不着头脑。
为了方便入门者编写自己的电路,同事写了个基于libsnark构造电路,并生成并验证电路的实例:
https://github.com/StarLI-Trapdoor/libsnark_sample
入门者,可以基于这个示例开发自己的电路。选择默克尔树作为电路的示例,因为在零知识证明的应用中,大量的使用默克尔树数据结构。
1 代码结构
该示例构造了一条merkle路径的验证电路,生成并验证证明。merkle树的深度为3,并且merkle树的计算采用sha256散列函数。代码结构比较清晰,merkle目录中的main.cpp是主函数。circuit目录下的merklecircuit.h是电路的实现。整个项目用cmake进行编译。
2 电路实现
电路名为MerkleCircuit,主要依赖两个gadget:merkle_authentication_path_variable和merkle_tree_check_read_gadget。merkle_authentication_path_variable提供了merkle树的一条路径。merkle_tree_check_read_gadget检查给定一个叶子节点,是否能计算出正确的root。
实现一个电路,主要实现两个接口函数:
generate_r1cs_constraints – 生成R1CS,该电路比较简单,只要让依赖的两个gadget,生成R1CS即可。
generate_r1cs_witness – 给所有的变量进行赋值。该电路,需要赋值的变量有root,leaf(叶子节点),和叶子节点配套的默克尔路径,以及默克尔路径对应的地址信息(也就是每一层的节点的位置,左边还是右边)。
整个电路最复杂的就是电路的构造函数,申请变量,创建gadget。其中重点讲一讲,set_input_sizes函数。libsnark的框架中,使用简单的区分public和private变量的模型。通过set_input_sizes函数,设置前几个变量为public变量。
pb.set_input_sizes(root_digest->digest_size);
也就是说,该电路的公开变量为root的bit个数。
3 生成和验证证明
确定了电路的实现,看看main函数,如何生成和验证证明。
在main函数中定义了merkle树计算需要的一些类型:
typedef libff::default_ec_pp ppzksnark_ppT; typedef libff::Fr<ppzksnark_ppT> FieldT; typedef sha256_two_to_one_hash_gadget<FieldT> HashT;
FieldT默认是bn256椭圆曲线的的Fr,默克尔树计算采用是sha256算法。
3.1 setup
实现了generate_read_keypair函数,生成pk/vk。仔细看一下generate_read_keypair函数,逻辑简单清晰:构造MerkleCircuit,在生成R1CS后,调用r1cs_gg_ppzksnark_generator生成pk/vk。
protoboard<FieldT> pb; sample::MerkleCircuit<FieldT, HashT> mc(pb, tree_depth); mc.generate_r1cs_constraints(); r1cs_constraint_system<FieldT> cs = pb.get_constraint_system(); return r1cs_gg_ppzksnark_generator<ppzksnark_ppT>(cs);
pk存放在merkle_pk.raw文件中,vk存放在merkle_vk.raw中。
3.2 prove
prove逻辑,首先从输入参数构造一个完整的merkle树,并根据输入选定了默克尔路径。通过generate_read_proof函数生成证明。该函数逻辑也比较清晰:
protoboard<FieldT> pb; sample::MerkleCircuit<FieldT, HashT> mc(pb, tree_depth); mc.generate_r1cs_constraints(); mc.generate_r1cs_witness(pb, leaf, root, path, address, address_bits); return r1cs_gg_ppzksnark_prover<ppzksnark_ppT>(proving_key, pb.primary_input(), pb.auxiliary_input());
构造MerkleCircuit,在生成R1CS后,设置各个变量的值。接着通过r1cs_gg_ppzksnark_prover生成证明。
3.3 verify
在获知vk,证明以及公开信息(root)的基础上,调用r1cs_gg_ppzksnark_verifier_strong_IC的接口完成验证。这也就是verify_read_proof函数的逻辑。
4 编译和运行
在编译之前,同步该项目依赖的libsnark库:
git submodule update --init --recursive
4.1 编译
mkdir build; cd build; cmake ..
编译完成,merkle目录下会生成merkle的可执行文件。
4.2 可信设置(trusted setup)
./merkle setup
4.3 生成证明
./merkle prove [data1] [data2] [data3] [data4] [data5] [data6] [data7] [data8] [index]
prove命令,需要提供原始的3层merkle树的8个叶子节点,并指定需要证明的第几个叶子节点对应的路径(index指明)。
4.4 验证
./merkle verify [root]
其中,root信息是在prove中生成过程中打印出来的root信息(也是公开信息)。如果验证通过,就说明存在一条能生成root的merkle路径,虽然没有公开路径的具体信息。
总结:
libsnark库代码层次非常清晰,并抽象出protoboard和gadget,方便开发者快速搭建电路。本文给出了一个基于libsnark库开发的完整电路示例。示例实现了3层默克尔树的一条默克尔路径的验证。其中默克尔树采用sha256的散列函数。
技术改变世界
长按二维码关注我
比推快讯
更多 >>- 1亿枚 USDT 从 Tether Treasury 转移到 Bitfinex
- Optimism已修复其测试网的两个关键漏洞
- Arkham:与 Wisdomtree WBIT相关的钱包持有8900枚BTC,价值约 5.79 亿美元
- 纳指止步4周连跌,创去年11月以来最大单周涨幅
- DAI 单日链上转账金额达到 860 亿美元,创下历史新高
- 以太坊 Rollup 协议 Zircuit 拟于夏季启动主网,总锁仓价值已达25亿美元
- 美参议员警告用于交易儿童性虐待材料的加密活动有所增加
- 加密银行 Custodia Bank 就其美联储成员资格败诉一案提出上诉
- Yuga Labs裁员,专注于建立“更小、更灵活的加密原生团队”
- NFTfi基金会:NFTFI空投申领门户将从 4 月 30 日开放至 6 月 10 日
- dYdX Chain累计交易量突破1200亿美元
- Phoenix Wallet将从美国应用商店下架,Jack Dorsey称“感觉完全没有必要”
- 零知识 (ZK) 协议 Hinkal 完成140 万美元战略融资,估值 7000 万美元
- 姆爷Eminem取代马特·达蒙成为 Crypto.com 最新明星代言人
- 九只现货比特币ETF今日净减持2,987枚BTC,净流出约1.9亿美元
- Yuga Labs 聘请媒体资深人士 Won Kim 担任品牌合作主管
- 一巨鲸从3月1日至4月15日买入近2.5万枚BTC,价值达 16.8 亿美元
- Sam Altman、黄仁勋等科技巨头高管加入美国联邦人工智能安全委员会
- PENDLE 持仓第二巨鲸疑似在持有近一年后卖出 120 万枚 PENDLE ,预计获利 645 万美元
- 福克斯记者:马萨诸塞州参议员候选人John Deaton将提交法庭之友陈述,以支持Coinbase的上诉动议
- Azuki将Azuki #723捐赠给Arbitrum DAO财库
- 链上借贷协议Venus Protocol已于以太坊主网部署DAI市场
- 花旗现预计美联储将于7月降息,2024年共降息100个基点
- 零信任DePIN网络Staex完成战略轮融资,Moonrock Capital参投
- 灰度向Coinbase Prime等地址转入约1811.1枚BTC
- 比特币波动指数昨日降至60.53,日跌幅8.07%
- 美国利率期货合约交易员预计美联储九月首次降息的可能性增加
- 稳定币公司OpenDelta完成250万美元Pre-Seed轮融资
- 美国3月核心PCE物价指数年率2.8%,预期2.7%
- Web3游戏L3E7完成1000万美元融资
- 芝加哥期权交易所拟将数字资产衍生品业务整合到其全球衍生品和结算业务中
- 某鲸鱼地址将3527枚ezETH PT和3300枚ETH存入Zircuit
- Quantix Capital投资NFA Labs 1000万美美元
- Uniswap基金会向Auditless拨款120万美元以创建Protocol Grants Program
- Arthur Hayes:美财长耶伦或将推出天量流动性注入计划,加速加密牛市回归
- RWA协议The Conlony完成新一轮融资,TechStars等参投
- 名义价值93亿美元的BTC与ETH期权即将到期
- Amaranth基金会创始人花费2470万美元购买7814枚ETH
- Vitalik:PoW也相当中心化,PoW只是转向PoS之前的临时阶段
- 中国证监会科技监管司司长、信息中心主任姚前接受审查调查
- 比特币长期持有者已从1月份开始抛售仓位
- PenPad宣布获得加密投资机构Animoca Brands投资
- 富达现货比特币ETF首次录得资金流出
- 华盛证券成为首批虚拟资产现货ETF承销商
- Lava Network发布LAVA代币经济学,6.6%代币将用于API提供者奖励
比推专栏
更多 >>观点
项目
比推热门文章
- 【比推每日新闻精选】与 Wisdomtree WBIT相关的钱包持有8900枚BTC,价值约 5.79 亿美元;DAI 单日链上转账金额达到 860 亿美元,创下历史新高;芝加哥期权交易所拟将数字资产业务整合到其全球衍生品和结算业务中
- 1亿枚 USDT 从 Tether Treasury 转移到 Bitfinex
- Optimism已修复其测试网的两个关键漏洞
- Arkham:与 Wisdomtree WBIT相关的钱包持有8900枚BTC,价值约 5.79 亿美元
- 【比推每日市场动态】再测6.4万美元,BTC无聊走势或将持续3到6个月
- 纳指止步4周连跌,创去年11月以来最大单周涨幅
- DAI 单日链上转账金额达到 860 亿美元,创下历史新高
- 以太坊 Rollup 协议 Zircuit 拟于夏季启动主网,总锁仓价值已达25亿美元
- 美参议员警告用于交易儿童性虐待材料的加密活动有所增加
- 加密银行 Custodia Bank 就其美联储成员资格败诉一案提出上诉