
零知识证明 – 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 新一期 Alpha(TAKER)空投数据:77%账户已卖出,单号收益 44 美元
- 以太坊现货 ETF 昨日总净流入 4.02 亿美元,持续 11 日净流入
- James Wynn:错过了做空机会,将等到 PUMP 完全触底再考虑入场
- 7743 枚 BTC 从 Coinbase 转出,价值超 9.16 亿美元
- James Wynn 转空为多开设 25 倍 ETH 多单,仓位价值 1460 万美元
- 某鲸鱼地址过去 10 分钟买入 4772 枚 ETH,均价 3581 美元
- RootData:ALT 将于一周后解锁价值约 867 万美元的代币
- World Liberty Financial 战略购入约 40,000 美元等值 BANK,用于支持 Lorenzo Protocol 项目发展
- XION 上线 Kaito Yapper 排行榜,开放 10 万枚 XION 代币奖励池
- 21Shares 向美 SEC 申请两只加密指数 ETF
- 两个新建地址从 Kraken 提取 22,434 枚 ETH,价值约 7.95 亿美元
- Plasma:XPL 公售启动仅 1 天,社区已超额认购 211%
- 数据:过去 24 小时全网爆仓 8.19 亿美元,多单爆仓 5.46 亿美元,空单爆仓 2.73 亿美元
- 2 个新建地址共计从 Binance 提币 1000 枚 BTC
- 巨鲸 AguilaTrades 持仓总市值达 2.94 亿美元,ETH 空单大幅浮盈
- 5.06 万枚 ETH 于 6 小时前从 HTX 流入至 Binance
- James Wynn:BTC.D 回升,山寨币季节或将暂缓
- 2 个新钱包从 Kraken 提取了 24,252 枚 ETH,价值约 8609 万美元
- 数据:非营利性开发组织 Argot Collective 在 6 小时前再次出售 600 枚 ETH
- SharpLink Gaming 在 2 小时前再度购进 4904 枚 ETH,目前累计浮盈 2.6 亿美元
- 富达 FETH 昨日净流出 4540 万美元,FBTC 净流出 1790 万美元
- 某巨鲸/机构 10 小时前再度买入 19,550 枚 ETH,目前持仓约浮盈 4134 万美元
- 加密恐慌与贪婪指数升至 74,市场贪婪情绪维持
- Tether CEO:将确保 USDT 符合《GENIUS 法案》规定,但仍计划推出专门针对美国的稳定币
- SharpLink Gaming 再增持 19,084 枚 ETH
- 美股收盘:三大股指涨跌不一,Circle 跌 4.71%,Coinbase 涨 2.2%
- Sharplink Gaming 计划发行 50 亿美元股票以购入 ETH
- Ether.fi 将上线 HyperLiquid 生态,推出 beHYPE 质押代币
- 黑客持续侦察 TeleMessage 漏洞,已有多起攻击尝试
- 分析:GENIUS 法案禁收益型稳定币,将利好以太坊 DeFi
- 加密交易所 Bullish 向纽交所申请上市
- Aether Holdings 将融资 4000 万美元,并购买比特币以启用比特币财务储备
- 支付公司 Block 将加入标普 500 指数
- Cantor Equity Partners IV 提交 IPO 申请
- WLFI 代币计划两月内全面上线,预售表现已使其市值跻身前11
- 美国总统特朗普:致力于在今年签署加密市场立法
- 特朗普:承诺绝不允许在美国创建央行数字货币(CBDC)
- 特朗普:当关税信函上面写明征收 35%、40% 关税的时候,那就是协议
- 特朗普:加密货币涨幅超过任何股票,加密货币对美元和国家都有好处
- 特朗普签署GENIUS 法案
- 特朗普:稳定币法案是对加密货币的重大认可
- 特朗普:将很快宣布重大贸易协议
- 美国总统特朗普:《GENIUS 法案》(天才法案)——他们以我的名字命名
- 特朗普:《GENIUS 法案》将确保美国在加密技术领域实现全球主导地位
- Galaxy Digital高管:投资者对加密行业的犹豫正迅速消散
- WLFI:WLFI 代币可交易性已获批准,预计将在 6 到 8 周内全面启动
- WLFI 增持价值约 4 万美元的 BANK 及 TAG 代币
- 摩根大通:在美国以外,代币化银行存款比稳定币更受监管青睐
- Aave Prime 上的 wstETH 存款突破 10 亿美元
- 美国参议院农业委员会下周一将就 Brian Quintenz 出任 CFTC 主席的提名进行投票
比推专栏
更多 >>观点
比推热门文章
- 以太坊现货 ETF 昨日总净流入 4.02 亿美元,持续 11 日净流入
- James Wynn:错过了做空机会,将等到 PUMP 完全触底再考虑入场
- 7743 枚 BTC 从 Coinbase 转出,价值超 9.16 亿美元
- James Wynn 转空为多开设 25 倍 ETH 多单,仓位价值 1460 万美元
- 某鲸鱼地址过去 10 分钟买入 4772 枚 ETH,均价 3581 美元
- RootData:ALT 将于一周后解锁价值约 867 万美元的代币
- World Liberty Financial 战略购入约 40,000 美元等值 BANK,用于支持 Lorenzo Protocol 项目发展
- XION 上线 Kaito Yapper 排行榜,开放 10 万枚 XION 代币奖励池
- 21Shares 向美 SEC 申请两只加密指数 ETF
- 两个新建地址从 Kraken 提取 22,434 枚 ETH,价值约 7.95 亿美元