
零知识证明 – zkHack mini挑战赛第一名
Trapdoor Tech获得zkHack mini挑战赛第一名
https://www.zkhack.dev/mini.html
这次的挑战赛由两道题目组成。一道题目一个星期的挑战时间。和第一期的挑战不同,这一期的题目都是基于STARK算法。STARK算法,AIR,FRI低阶测试等等技术会在后续的文章仔细介绍。本文先总结一下这次挑战赛的两个题目的解题思路。
第一题:There's something in the AIR
https://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;
state[15] = Felt::ZERO;
state[16] = priv_key[0];
state[17] = priv_key[1];
state[18] = priv_key[2];
state[19] = priv_key[3];
state[20] = topic[0];
state[21] = topic[1];
state[22] = topic[2];
state[23] = topic[3];
一个合法的nullifier应包括以下3个部分
[12 13 14 15] [ 16 17 18 19 ] [ 20 21 22 23 ]
nullifier = [8 0, 0, 0, --- 私钥Priv_key----------, -----主题Topic------- ] — 在执行到第 0 步时
然而,检查验证者的程序时,发现在evaluate_transition函数中没有设置对state[12-15]的验证, 类似的验证可以参考默克尔树验证的部分。
result.agg_constraint(1, hash_init_flag, are_equal(E::from(8u8), next[0]));
result.agg_constraint(2, hash_init_flag, is_zero(next[1]));
result.agg_constraint(3, hash_init_flag, is_zero(next[2]));
result.agg_constraint(4, hash_init_flag, is_zero(next[3]));
答案
可以为state[12-15]设置不同的值来伪造nullifier,例如[16, 0, 0, 0]。
pub fn get_fake_nullifier(&self, topic: Digest) -> Digest {
let key: Digest = self.0.into();
let mut state = [Felt::ZERO; 12];
state[4..12].copy_from_slice(Digest::digests_as_elements(&[key, topic]));
state[0] = Felt::new(0 as u64);
// apply the Rescue permutation and return the first four elements of the state
Rescue::apply_permutation(&mut state);
Digest::new(state
[4..8].try_into().unwrap())
}
同时在证明者产生证据时,将state[12-15]设置为伪造的nullifier所对应的值。
Prover.build_trace()
|state| {
......
// -- nullifier section of the trace --
state[12] = Felt::new(0);
第二题:Can you turn up the heat?
https://www.zkhack.dev/puzzleM2.html
本周的题目可以说是 zkHack 有史以来最难的一道题。本题的目标是伪造 STARK 证明,需要解题者对 STARK 证明的整个逻辑步骤有较为清晰的知识。
来回顾一下题目:Alice使用 STARK 电路写了一个斐波那契数列的计算程序,能够同时生成 STARK 证明并验证。某天她收到了一个错误的证明,计算出数列的第32项等于123(实际应为832040)。但这个证明却能通过她的 STARK 验证器。现在我们想要知道该证明是如何被伪造的。
。
比推快讯
更多 >>- Binance:新 TGE 项目 Palio 未能成功完成流动性存入,正积极解决
- BTFS 协议 v4.0 主网正式上线
- 香港投资推广署署长:目前有准稳定币营运商洽谈落户香港
- 美股盘前部分加密货币概念股冲高,SharpLink Gaming 涨近 6%
- 疑似 Arthapala 地址向 CEX 充值累计 57119 枚 ETH,约合 1.47 亿美元
- 英国 FCA 打击加密货币欺诈,两名犯罪分子获刑超 12 年
- TRON 生态启动星际热浪 7 月活动,六大板块联动助推 Meme 热潮
- 英国上市公司 Coinsilium Group 宣布增持 14.9 枚比特币,总持仓达到 88.63 枚
- 贝莱德在中国银行(03988.HK)的持股比例于 7 月 1 日从 5.99%升至 6.46%
- CoinShares:上周数字资产投资产品净流入 10.3 亿美元,连续 12 周流入
- MCNEX 与 PlayFirst 共同投资 500 万美元建立 Web3 金融与游戏聚合平台
- 机构:“大而美”法案对美国经济的实际拉动作用有限
- 国金证券:公司旗下国金证券有限公司正筹备申请虚拟资产相关交易牌照
- 某巨鲸/机构再次从 Binance 提出 700 万枚 FORM,约 1900 万美元
- 西班牙银行 BBVA 面向散户推出加密货币交易与托管服务
- 分析师:韩国正经历稳定币泡沫,$CRCL 成为韩资最热外股
- Backpack:此前仓位错乱时获利的用户可以自行处置资产,损失的用户全额赔付
- 美股上市瑞典公司 Hilbert Group 获得 2100 万美元融资,以支持加密货币储备策略
- 摩根士丹利分析关税政策 3 大剧本:关税政策仍是市场关键变量,7 月 9 日值得关注
- 泡泡玛特首位投资人麦刚:对比特币情有独钟,关键在于对本质问题的追寻
- FTX 债权人代表:预计允许索赔总额 110 亿美元,司法受限索赔总额 4.7 亿美元
- 野村证券:贸易关税进一步明确可能帮助市场最终走高
- 数据:某巨鲸链上分两笔买入 4862.95 枚 ETH ,总价值 1249 万美元
- Bitunix 分析师:宏观乐观情绪蔓延,ETH 震荡上行,关注 2525 与 2275 支撑区域
- Xterio 开启 PAL 质押活动,当前 XTER 池预期年化收益率为 5281.71%
- Ave.ai 支持 xStocks 协议,上线链上美股交易功能
- Matrixport:市场缺乏新的推动因素,散户交易活跃度持续疲软
- 去中心化 AI 训练平台 FLock.io 代币质押量突破 6000 万枚,占流通量 31%
- 某 Coinbase 黑客花费 1250 万枚 DAI 买入 4863 枚 ETH
- Binance:Alpha 用户参与 PAL TGE 积分门槛为 202 分
- 模块化自动化协议平台 Questflow.ai 正式接入 Circle Alliance Program
- 机构:市场并未对特朗普关税感到恐慌
- Virtuals:Genesis 空投将不再自动发放,用户需手动申领
- 英国上市公司 Tao Alpha 拟任命 UTXO Management BTCfi 负责人为非执行董事
- 数据:澳大利亚 Monochrome 现货比特币 ETF 的 BTC 持仓升至 937 枚
- 观点:若本轮牛市与此前两轮类似,则还有半年到达市场顶部
- 欧洲上市公司 The Blockchain Group 增持 116 枚比特币,总持仓达 1904 枚
- 土耳其本月已关闭 46 个加密货币平台的访问权限
- The Smarter Web Company 增持 226.42 枚比特币
- 数据:过去 7 天 BNB Chain 跨链桥净流入资金达 10.08 亿美元,以太坊净流出 9.86 亿美元
- 德勤调查:英国企业对投资美国失去兴趣
- MYX 短时上涨触及 0.14 USDT,24H 涨幅 96.22%
- CZ:币安在成立首年便实现了约 10 亿美元的利润
- 48 Club:因后台逻辑错误致用户误领 1807 枚 KOGE,约 86736 美元
- 无锡市委改革任务推进会:探索稳定币赋能外贸发展的实践路径
- Metaplanet 宣布增持 2205 枚比特币
- 俄罗斯开始建立全国加密货币挖矿设备注册系统,以打击非法挖矿活动并增加税收
- Letsbonk 近 24 小时 Solana 发币平台市场份额升至 55.1%,pump.fun 跌至 34.9%
- 数据:USDC Treasury 于以太坊链上销毁 6000 万枚 USDC
- 许正宇:代币化绿色债券结算周期缩短至 T+1,提升交易效率
比推专栏
更多 >>观点
比推热门文章
- BTFS 协议 v4.0 主网正式上线
- 香港投资推广署署长:目前有准稳定币营运商洽谈落户香港
- 美股盘前部分加密货币概念股冲高,SharpLink Gaming 涨近 6%
- 疑似 Arthapala 地址向 CEX 充值累计 57119 枚 ETH,约合 1.47 亿美元
- 英国 FCA 打击加密货币欺诈,两名犯罪分子获刑超 12 年
- TRON 生态启动星际热浪 7 月活动,六大板块联动助推 Meme 热潮
- 英国上市公司 Coinsilium Group 宣布增持 14.9 枚比特币,总持仓达到 88.63 枚
- 贝莱德在中国银行(03988.HK)的持股比例于 7 月 1 日从 5.99%升至 6.46%
- CoinShares:上周数字资产投资产品净流入 10.3 亿美元,连续 12 周流入
- MCNEX 与 PlayFirst 共同投资 500 万美元建立 Web3 金融与游戏聚合平台