
零知识证明 – 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 验证器。现在我们想要知道该证明是如何被伪造的。
。
比推快讯
更多 >>- Coinbase 成为 ReserveOne 加密服务托管商
- 英国法院判处两名加密货币诈骗者入狱,涉案金额达 200 万美元
- 特朗普:关税将于 2025 年 8 月 1 日开始征收,不给予任何延期
- 英国法院判决两起金融诈骗案,涉案金额超 300 万美元
- Robinhood 就代币化股票与欧洲监管机构展开沟通
- OpenSea 收购 Rally Wallet 背后开发公司 Rally
- Vertex 将逐步淘汰原生代币 VRTX,并将其 DEX 迁至 Kraken 支持的 L2 网络 Ink
- 马斯克成立新党引发投资者担忧,但获 Ark Invest 创始人 Cathie Wood 力挺
- Ripple 股东 Linqto 已申请破产
- Greeks.live:比特币在 10.5-11 万美元区间震荡过久,缺乏明确方向
- Aevo 推出支持 1000 倍杠杆交易美股平台 Aevo Degen,已上线 COIN、HOOD、CRCL
- ETH 突破 2600 美元
- xStocks 将集成进即将上线的 Jupiter Lend
- 世界黄金协会:全球黄金 ETF 上半年增加 380 亿美元
- 美股加密货币概念盘初集体冲高,SharpLink Gaming 涨超 21%
- LibertyAgents.io 寻求战略投资者支持 WLFI 生态基础设施建设
- Tornado Cash 联创 Roman Storm 审判仍定于 7 月 14 日开始
- Resupply 上线 IP 留存激励计划,拟在 52 周内发放 250 万枚 RSUP
- DeFi Development 增持 47,272 枚 SOL,价值约合 719 万美元
- Greeks.live:部分加密交易者表现出“看涨但倾向于保护”态度
- MoonPay 在英美欧支持 Apple Pay 零手续费充值余额以购买加密货币
- 分析:日本 30 年国债收益率三天飙升逾 30 基点,或影响 BTC 等风险资产
- SharpLink 上周购入 7689 枚 ETH,总持仓突破 20 万枚并获 322 枚以太坊质押奖励
- 数据:过去 24 小时全网爆仓 1.66 亿美元,多单爆仓 1.06 亿美元,空单爆仓 6049.04 万美元
- 美股 BTCS 盘前涨 5%,此前宣布拟筹集 1 亿美元收购 ETH
- Robinhood CEO:收到大量公司请求发行代币化股票
- 特朗普媒体科技集团盘前上涨 1.5%,或受申请加密蓝筹 ETF 影响
- 以太坊执行客户端支持历史数据修剪,大幅节省节点存储空间
- 区块链技术上市公司 BTCS 拟年内募资 1 亿美元以战略收购 ETH
- 中信建投:稳定币合规化提速,资产代币化迎来“权益时代”
- MetaCene 显卡集群驱动的新链游《Cyber Crash》上线一周单日营收超 500 万美元
- 德银调查:特朗普政策加持推动美国加密货币采用率有所增长
- ETH 版微策略SharpLink 增持 7689 枚 ETH,买入均价 2501 美元
- Truth Social 加密蓝筹 ETF“篮子”内包括 BTC、ETH、SOL、XRP 和 Cronos
- 分析:BNB 价格窄幅波动,市场关注美国关税政策影响
- Truth Social 递交 S-1 文件,拟推出 Crypto Blue Chip ETF
- Circle 盘前下跌 3.3%,瑞穗银行首次给予“表现不佳”评级
- Hyperscale Data:6 月挖矿产出 13.7 枚 BTC,比特币持有量达 103.7 枚
- 市场猜测特朗普政府有意推动美元走弱
- Genius Group 购入 28 枚 BTC,比特币储备增至 148 枚
- 疑似 Arthapala 地址过去 5 小时再次向交易所充值 6570 枚 ETH,约 1677 万美元
- 义乌当地协会回应稳定币结算:几乎没有,认可度不高难以形成广泛流通
- Benchmark:给予 Semler Scientific“买入”评级,看好其比特币储备战略
- 巴基斯坦成立数字资产监管机构
- 特朗普宣布将对泰国征收 36%关税
- Orbiter Finance 与 Nano Labs 达成合作将推出合规稳定币跨链解决方案 NBNB.io
- Ego Death Capital 第二支基金完成 1 亿美元募资,专注支持比特币生态企业扩张
- KULR Technology 与 Coinbase Credit 达成 2000 万美元初始信贷融资协议
- Matador Technologies 在比特币链上推出数字黄金产品“Grammies”
- Tether 投资区块链取证公司 Crystal Intelligence
比推专栏
更多 >>观点
比推热门文章
- Coinbase 成为 ReserveOne 加密服务托管商
- 英国法院判处两名加密货币诈骗者入狱,涉案金额达 200 万美元
- 特朗普:关税将于 2025 年 8 月 1 日开始征收,不给予任何延期
- 英国法院判决两起金融诈骗案,涉案金额超 300 万美元
- Robinhood 就代币化股票与欧洲监管机构展开沟通
- OpenSea 收购 Rally Wallet 背后开发公司 Rally
- Vertex 将逐步淘汰原生代币 VRTX,并将其 DEX 迁至 Kraken 支持的 L2 网络 Ink
- 马斯克成立新党引发投资者担忧,但获 Ark Invest 创始人 Cathie Wood 力挺
- Ripple 股东 Linqto 已申请破产
- Greeks.live:比特币在 10.5-11 万美元区间震荡过久,缺乏明确方向