零知识证明 – 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 验证器。现在我们想要知道该证明是如何被伪造的。
。
比推快讯
更多 >>- 通用证明聚合器Electron完成100万美元种子轮融资
- SCION软件提供商Anapaya Systems完成1000万瑞士法郎融资,Cape Capital等参投
- Coincheck正推进与SPAC公司合并协议以在美国纳斯达克上市
- Web3基础设施初创公司Hemera完成260万美元种子轮融资,LIF Capital等领投
- CryptoPunks以170万美元的销售额位居昨日销售排行榜榜首
- SEC认为Ripple并未违反任何规则但未来仍可能对其采取类似行动
- FOX记者:灰度从未为其以太坊期货ETF提交S-1申请
- Web3娱乐公司Imaginary Ones完成一轮超额认购融资
- Web3孵化服务提供商BlockBooster完成150万美元种子轮融资
- 基金管理巨头Vanguard暂无提供比特币ETF或其他加密相关产品计划
- KOR基金会推出KOR Protocol,Animoca Brands等为发布合作伙伴
- 门罗币P2P交易平台LocalMonero宣布结束运营
- Telos宣布获Presto Labs 100万美元战略投资
- OKX Ventures宣布投资Wild Forest
- Ola:面向早期Massive用户的首次代币分配快照拟于5月11日进行
- Liquidium宣布完成新一轮融资并已购入1 DeGod、1y00t和1 BTC DeGod
- 美SEC主席:收到的有关加密货币的问题“比例过大”
- 灰度撤回其以太坊期货ETF申请
- 美众议院民主党拟于本周提出针对加密货币混合服务的法案
- 摩根士丹利将美联储首次降息时间的预期从7月推迟到9月
- 彭博分析师:灰度现货比特币ETF净流入可能是短期交易的结果
- 前 NFL 巨星Rob Gronkowski同意支付 190 万美元以和解 Voyager Digital 投资者诉讼
- BTC短线跌破63000美元
- Advanced Blockchain AG在瑞士成立加密风投机构ABX Ventures
- Aragon 联合创始人推出自托管钱包 Tuyo
- 美联储Neel Kashkar:今年仍有可能降息
- Solana生态DePin项目Ambient完成200万美元融资,Borderless Capital 领投
- 美国国务院拟悬赏1000万美元以获取LockBit勒索软件组织头目信息
- 分析师:Robinhood第一季度营收有望创近三年新高,加密交易收入同比增幅或达一倍以上
- MoonPay 与 BitPay 合作简化加密货币交易
- Lava Foundation 完成1100万美元融资,未来几个月将推出Lava主网和空投
- Zora网络收购NFT铸造聚合器mint.fun
- 美联储Neel Kashkar:最有可能在较长时间内维持利率不变
- 扩容解决方案提供商ZKM完成500万美元Pre-A融资,OKX Ventures 领投
- 前红杉中国合伙人曹曦旗下投资公司Monolith Management拥有超过2400万美元的贝莱德现货比特币ETF
- 美国9只现货比特币ETF 昨日增持4412枚BTC,价值约2.8亿美元
- 渣打银行:美国财政主导地位和特朗普上台或将使比特币受益
- ETH 反弹突破 3100 美元,24小时涨幅1.13%
- BTC回升至64000美元
- 过去2个月某巨鲸/机构从Flow Traders收到2,261枚BTC,价值约1.49亿美元
- 贝莱德和富达比特币ETF共拥有超42万枚BTC,价值约 270 亿美元
- CBOE向SEC提交富兰克林比特币ETF规则修改申请
比推专栏
更多 >>观点
项目
比推热门文章
- Coincheck正推进与SPAC公司合并协议以在美国纳斯达克上市
- Web3基础设施初创公司Hemera完成260万美元种子轮融资,LIF Capital等领投
- CryptoPunks以170万美元的销售额位居昨日销售排行榜榜首
- SEC认为Ripple并未违反任何规则但未来仍可能对其采取类似行动
- FOX记者:灰度从未为其以太坊期货ETF提交S-1申请
- Web3娱乐公司Imaginary Ones完成一轮超额认购融资
- Web3孵化服务提供商BlockBooster完成150万美元种子轮融资
- 基金管理巨头Vanguard暂无提供比特币ETF或其他加密相关产品计划
- KOR基金会推出KOR Protocol,Animoca Brands等为发布合作伙伴
- 门罗币P2P交易平台LocalMonero宣布结束运营