零知识证明 – 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 验证器。现在我们想要知道该证明是如何被伪造的。
。
比推快讯
更多 >>- Upbit运营商Dunamu 2023年净利润约6亿美元
- GSR Markets和Wintermute过去7日累计向CEX转入4820万枚ARB
- 1kx为其新基金募资7500万美元
- 香港金融公司VSFG计划最早于5月推出现货比特币ETF
- dappOS以3亿美元估值融资1530万美元
- Euroclear对区块链泛欧基金市场Iznes进行股权投资
- Vitalik:人类需要创造一个区块链和人工智能共同发挥作用的世界
- 韩国RWA区块链技术开发公司PARAMETA完成约750万美元新一轮融资
- 老虎证券在香港获批第9类牌照,拟提供资产管理服务
- 亚马逊于昨日向人工智能公司Anthropic再注资27.5亿美元
- 加拿大调查QuadrigaCX联创Michael Patryn其大笔财富的来源
- Celestia 在 Base 上推出 Blobstream
- 尼日利亚央行行长:加密货币监管由尼日利亚证券交易委员会负责
- OKX Ventures宣布战略投资AI集成的Web3技术先驱Myshel
- BTC跌破69000美元
- ARKB管理资产超过30亿美元
- KuCoin CEO:将为忠实用户空投价值1000万美元的KCS和BTC
- Layer N 与 Modulus Labs 合作推出 AI Functions
- 贝莱德CEO:即使ETH被SEC定义为证券,推出现货以太坊ETF仍是可能的
- 收益协议Ethena将于4月2日向用户空投ENA代币,占总供应量的5%
- 美联储理事Waller:需要“几个月”更好的通胀数据才能进行降息
- 贝莱德代币化投资基金BUIDL推出一周内已流入 1.6 亿美元
- 荷兰检察官寻求对 Tornado Cash 开发者 Alexey Pertsev 判处 64 个月监禁
- Deribit 3 月份到期的比特币期权未平仓合约创下历史新高,达 95 亿美元
- ZK Rollup Zircuit 推出“Build to Earn”计划以奖励生态系统贡献者
- 9个现货比特币ETF今日增持3469枚BTC,价值2.4亿美元
- 分析师:ETHFI 的强劲价格表现可能会提振其他LRT代币的空投估值
- 加密做市商 GSR 将现货以太坊 ETF 5 月份获批的概率下调至 20%
- Web3游戏工作室7 Digital Labs完成400万美元种子轮融资,Avalanche基金会等参投
- 超8300万枚DOGE从Robinhood钱包地址转出
- 黄立成推出Solana Meme项目Bobaoppa,已募集超11万枚SOL
- 以太坊再质押协议Unstable完成250万美元种子轮融资,Laser Digital等参投
- DEGEN创始人:拟于本周五进行第二季积分快照拍摄
- Fetch.ai:ASI代币总供应量将为26.3亿枚,合并提案4月2日开启投票
- Web3游戏平台Elixir Games完成1400万美元种子轮融资,生态系统拟于第二季度上线
- 混合型第 2 层区块链BOB完成1000万美元种子轮融资,Castle Island Ventures领投
- 以太坊链上累计验证者总量已突破100万
- Immutable zkEVM完成 Shanghai 硬分叉升级
- Base总锁仓价值达到28.9亿美元,超越Blast成为第三大L2网络
- Pyth Network将为Caldera Rollups提供数据服务
- MNT上市公告发布后,Dragonfly Capital和Fenbushi Capital向Bybit存入超1300万枚MNT
比推专栏
更多 >>观点
项目
比推热门文章
- Upbit运营商Dunamu 2023年净利润约6亿美元
- GSR Markets和Wintermute过去7日累计向CEX转入4820万枚ARB
- 1kx为其新基金募资7500万美元
- 香港金融公司VSFG计划最早于5月推出现货比特币ETF
- 币安 OK 双向加持:StakeStone,万链时代的流动性自来水公司
- 福布斯:市值数十亿美元,僵尸企业在加密世界游走
- dappOS以3亿美元估值融资1530万美元
- Euroclear对区块链泛欧基金市场Iznes进行股权投资
- Ordinals 创始人发布 Runes 文档,超越 BRC-20 的代币发行方式?
- 深入了解积分场外交易市场Whales Market