
零知识证明 – 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 验证器。现在我们想要知道该证明是如何被伪造的。
。
比推快讯
更多 >>- 全网比特币合约未平仓头寸达 735.9 亿美元
- 公链活跃度近 7 日排行榜:Solana 稳居首位
- 白宫经济顾问:部分贸易谈判可能会超过截止日期
- “内幕巨鲸”被多次清算后的目前残余仓位降至 4734 万美元
- 分析:BTC 内存池中交易数量与去年底相比明显减少,或有潜在危机
- 美国财长贝森特:马斯克应该专注于商业
- 分析师:WLFI 测试添加流动性为不实消息
- 比特币回升触及 10.9 万美元
- 美财长贝森特:若 8 月 1 日前未达成协议,关税将恢复至 4 月份水平
- 美国财长贝森特:将由美联储决定是否降息
- 人工智能交易市场 olaxbt 完成 338 万美元种子轮融资,Amber Group 领投
- 消息人士:美国和印度小型贸易协议谈判已经完成,平均关税税率或为 10%
- 美国财政部长:100 个较小的国家将获得固定的关税税率
- 疑似 Abraxas Capital 标记地址向 Kraken 转入 1000 枚 BTC
- 美国财政部长:贸易谈判进入最后阶段
- 某巨鲸循环做多 ETH,过去 2 小时建仓 2304.3 枚 stETH
- 马斯克已向美国联邦选举委员会提交美国党组织声明
- 马斯克发文询问“美国党”首次代表大会应在何时何地举行
- Boom 基金会:已完成 BOOM 代币空投资格快照
- 港媒:Circle 上市一个月录得逾 5 倍涨幅,光大控股于 2016 年成为其股东
- Michael Saylor 再次发布比特币 Tracker 信息,下周或将披露增持数据
- 中信建投:美股代币化大爆发,券商 IT 改造需求有望加速释放
- LetsbonkFun 以 45.7% 市场份额登顶,24 小时交易量达 4.02 亿美元
- 人大金融科技研究所:促进可控稳定币与数字人民币互通互认
- 劳埃德银行:下周美联储会议纪要或不会改变 7 月不降息市场预期
- Cartwright 建议英国首个 DB 养老基金将 3%资金投入配置 BTC
- 疑似 Arthapala 地址过去 5 小时再次向各大交易所充值 5850 枚 ETH
- Vitalik Buterin 联合发起 EIP-7983 提案,拟增强网络抗 DoS 攻击能力
- 美国党构想曝光:马斯克称打破两党垄断并不难
- 陈茂波:香港上市 ETP 锚定资产包括数字资产,也有追踪 Coinbase 等美股产品
- 近期沪深两市多家上市公司频繁被询问是否布局稳定币业务
- Endless Clouds 基金会:END 转账功能拟于 24 小时内生效
- 比特币于 65 分钟前在高度 904263 处挖出空区块
- 分析:马斯克成立“美国党”或需数年时间来解决法律和经济层面的困难
- 本周美国以太坊现货 ETF 净流入 2.191 亿美元
- 观点:马斯克虽有巨额财富和影响力,但历史上美国第三党很难成功
- 转移逾 8 万枚 BTC 的远古巨鲸疑似升级旧钱包,暂无抛售迹象
- 前 DigitalMint 勒索软件谈判专家被指控与黑客合谋敲诈受害者,遭美国司法部调查
- Toncoin 与阿联酋合作,向 TON 质押者提供 10 年黄金签证
- Polymarket 上预测WLFI 代币上线首日后 FDV 超过 130 亿美元概率达 56%
- Bankless 联创:以太坊 MEV 最小化投资或助力传统金融采纳
- Hash Epoch 平台代币 HEST 将于 7 月 9 日全网上线交易
- Matrixport 近 1 小时从 Binance 提取 1500 万 USDT
- 印度捣毁“最多产的暗网毒品集团”,嫌疑人使用门罗币洗钱
- 观点:因加密禁令没收中国用户 FTX 索赔资金缺乏法律依据,FTX 债权以美元计价并结算
- ZachXBT:不承接 Sui 生态相关案件,在该生态系统未得到支持
- 沉寂两年的鲸鱼向 Kraken 转入 230 枚 ETH,价值约 57.9 万美元
- 某巨鲸清仓 21.6 万枚 HYPE,亏损 29 万美元
- Miller Value Partners 首席投资官 Bill Miller IV 质疑比特币征税合理性
- Binance Alpha 昨日交易量报 4.586 亿美元,BR、KOGE、CARV 分列前三
比推专栏
更多 >>观点
比推热门文章
- 【比推周末重点新闻回顾】瑞银、花旗等 9 家机构因涉 22 亿美元洗钱案被新加坡罚款 2150 万美元;马斯克已向美国联邦选举委员会提交“美国党”组织声明;赵长鹏评论“TON 质押者可获 10 年阿联酋黄金签证”:若属实,将推动 BNB 享有同等待遇
- 全网比特币合约未平仓头寸达 735.9 亿美元
- 公链活跃度近 7 日排行榜:Solana 稳居首位
- 白宫经济顾问:部分贸易谈判可能会超过截止日期
- “内幕巨鲸”被多次清算后的目前残余仓位降至 4734 万美元
- 分析:BTC 内存池中交易数量与去年底相比明显减少,或有潜在危机
- 美国财长贝森特:马斯克应该专注于商业
- 分析师:WLFI 测试添加流动性为不实消息
- 比特币回升触及 10.9 万美元
- 美财长贝森特:若 8 月 1 日前未达成协议,关税将恢复至 4 月份水平