ZK Hack Puzzle 3 题解： 如何用Pedersen承诺实现漏洞攻破零知识内积证明系统
1Pedersen向量承诺
对长度的向量进行承诺，选取个生成元另加一个“隐藏”生成元，要求这个生成元两两之间或和任意线性组合之间的离散对数未知。
其中为随机数，为内积。
Pedersen承诺是一种同态承诺，即：
2挑战内容
https://github.com/kobigurk/zkhack-double-trouble
Bob开发了一个新的零知识内积证明系统，可以证明一个隐藏的要承诺的向量和公开向量的内积， 等于声称的承诺值。该内积证明系统可通过对下述协议应用Fiat-Shamir转换得到：
离线阶段
证明者计算并发送给验证者。
在线阶段（对于给定公开向量）
证明者采样随机向量和随机数 证明者计算并发送给验证者
验证者将随机挑战发送给证明者 证明者计算并发送给验证者
验证者验证
//检验真的是
//检验为的承诺
该协议的ZK/PoK两个性质的证明见：https://gist.github.com/kobigurk/0e9904f5a2602c628f0d3b95bcf01ffb
除了上述发布的协议，Bob宣称他有一个专利版的证明者实现，比上述快2倍，且依然是零知识的。为证明此断言他对同一个以及可能不同的多个发布了由该专利版证明者声称的几个证明，请大众仅通过这几个证明来恢复。
发布的两个证明（包括证明的全部脚本）和承诺密钥（即生成元)如下：
const COMMIT_KEY_BYTES: &'static str = "CAAAAAAAAACdCH9GccfV39AeGVy7HfoafpnPycDG3mTfZFrAP4yLmV58MOMpVnnd+N/PQPJZB7MEDQLFQM0mcBcX6KyR1JLLuqxH0weTEG9pdjkR9gXJkFHywrzbidCFG/X4jmnp9fBS1Dq59AgMgLJx5XtYC5+2SkZRUL9RAKRe6I/+1gXwv3nAJzmDnbOB7fYVjQE6rP0o8+ug0KE8DsZz+wAPWHRRQrfW96sx91gNz2IQarA5OSsqN3mBZNnaDbzibTohsGVHY6qTWg1sZCvnEK+ydGfwAHcMby25TrWvWB1zcUlkUL+bb36OncTqQY92Kkky23kVjMDySDMuQQB907aMVoExMnuluWWJVbupS80Dqyp1CA+K+lguoj+okO0b6ODYLro=";
const INSTANCE_AND_PROOF_BYTES: [&'static str; 2] = [
"ir8oQmlflodJky2AD9aoBlwPGPdvUIn76Qq7T+Bx4moIAAAAAAAAAM05+NtcfZ5IO5frFUEB4jN83JcTntCIvN6qNKVmDhgI5mKxry/cBj7PjshABNymrSdOv/XuzJGRrASsL4L7agPyNINAYPQt9Yd74CjGKz/rmptvhyEsHgQqn/fcI/7nDX5F17tLi7z0VtrJGOC6e24YUZ+MKFnt9xdX2uPhu5EIll4An28ygHbU24Qc1RX6mFr+axeFFivQo1BjQUwf2AU8Rakq8O/NPW28bo1As+wp3nVFJLv/o/MkilBnhuXVBsu9HAesl9gHoGXttu2Mf46ipsS0UUBi7lPTa3ymR7wGWjEkxSZ6E3zXs/f+79KT2UiUwbdbjlYJI28LXtPZ9gwo7Bid8PoEi93gobn1E3Qlg6Y0UUjHwuTMUrrjSTgQVOERjASsf9LDNgeZr0dc6gi27mBt9THa1VuCjf6pn9yK9SAqfLZrh1nksjUQZP5E2c3T4SP4kf0SUmuEuh9r/ZkIAAAAAAAAAJuiWXTvJTaJquMJ6UcoLvOp8S2X+cyPWkOheOlynr8DL6VuxUV25oVGAW+uu3lLN6Efn1Gd6SOgKLckWIlM1AcCjd8gv2TlIlP5I+KtJ1yQL2sbuw7wPdHuKpVDOxorBejjSVaH8RRVMI9/7rJuNmuaewLrG/Aq4FEwzXe/y38KLe6P3tu14ntXc1v4VJg6a9wS4w8cXPq5zG5ZL1pEQwAWl2Xw8j+6RtHjchFLmAv1Pd0EcxFhtgBNNHNpdqhJAg4Jx6mjh3wHG4lZkFDkl9Q1bVtbZAVh8iSoRXwXOXsI5H6Kx0ipSSR9WsYnjFNGrWgEPZNmYe/uf4C3NKXNxwOOE+dYFeTGUUrj2PJCL4yXJQtaOVT+HDo0xtF8dA68AQoNkDEWyt1ncUbuelaCACl0VGcoiMbI1qylWDE76mQB",
"ir8oQmlflodJky2AD9aoBlwPGPdvUIn76Qq7T+Bx4moIAAAAAAAAAM05+NtcfZ5IO5frFUEB4jN83JcTntCIvN6qNKVmDhgI5mKxry/cBj7PjshABNymrSdOv/XuzJGRrASsL4L7agPyNINAYPQt9Yd74CjGKz/rmptvhyEsHgQqn/fcI/7nDX5F17tLi7z0VtrJGOC6e24YUZ+MKFnt9xdX2uPhu5EIll4An28ygHbU24Qc1RX6mFr+axeFFivQo1BjQUwf2AU8Rakq8O/NPW28bo1As+wp3nVFJLv/o/MkilBnhuXVBsu9HAesl9gHoGXttu2Mf46ipsS0UUBi7lPTa3ymR7wGWjEkxSZ6E3zXs/f+79KT2UiUwbdbjlYJI28LXtPZ9gwgzQ9q7nJCNjnM0ZihHb8osXE+lY9ZLgg2UK/ckY4JEIy2Bt+IzqiwnrDmnkOhq0/KfXXOZzWkMQTwLXyClWoviyAcIijtc6hF9+3HAl2dNb/37rWE106q/6uK6LbhDREIAAAAAAAAAP1RSBw3PvBPG4ntyo4R18++OpEOrzIQVtEjGpzECXUJEppprdaJdzlAiopoyJOpzfmRkzYtZjK0/+QOLctEDQMx1O7++cSsayZt/TAp3SDLhPN1G74i/5ljYTIR9XCCArZaVA4JVusXhwg9mkeYyGmlNd2zxLMdeSkVT28Yh7MFcFSm6XP9MVtlx5zV/aiM7uJn4OgPGBkK6ZQXFUC2/QAQ54E08vZXo1M9PkXv3qaO/BmWL6qXnUAT5u2znrI5CdZ01rpJFaTHVJ12EoeqYF1sVbdOsFnIo5WsGqei1xwFpOJCvaTV5iNA/HUT3/BlI88dOeOOhb0Jn/f6zKZungLus1pim4mqCAVm1DSVhWZ77Hfv1LC8ii2TbZ6v2AQhBawub5eLCD8zb9Dfh6s93qNlHdNQ+eONQOne0Q5u+EII"
];
记证明脚本分别为：
3题解
解法1
注意到是唯一一个无需求离散对数的和有关的公开元素。由，想要求唯一不知道的就是。
同理想要求，就要关注公开元素
由，得
如果能找到的关系，则可以通过解出（或）再带回去求出。而想要找到的关系，最好的方法是去观察他们分别的承诺值之间的关系。
重要观察：
搜索脚本如下：
let (commit_key, [(instance_1, proof_1), (instance_2, proof_2)]) = puzzle_data();
let cr_1 = proof_1.commitment.comm_r;
let cr_2 = proof_2.commitment.comm_r;
let elements = vec![
cr_1,
cr_2,
];
let mut elements_copy = Vec::clone(&elements);
let mut i = 2;
loop {
elements_copy
.iter_mut()
.zip(elements.iter())
.for_each(|(copy, orig)| *copy += *orig);
elements_copy
.iter()
.enumerate()
.for_each(|(copy_idx, copy)| {
elements.iter().enumerate().for_each(|(orig_idx, orig)| {
if copy == orig {
println!("elements[{}] * {} = elements[{}]", copy_idx, i, orig_idx);
}
})
});
i += 1;
}
此关系即为知晓了和之间的离散对数，严重违反了Pedersen承诺的安全假设。
由Pedersen承诺的同态性，则，则带入得
fn solve_for_r(s1: Vec<Fr>, s2: Vec<Fr>, challenge1: Fr, challenge2: Fr) -> Vec<Fr> {
// challenge1 - 2 * challenge2
let challenge_diff = challenge1 - challenge2.double();
let challenge_diff_inv = challenge_diff.inverse().unwrap();
let mut r = Vec::with_capacity(s1.capacity());
for (s1_num, s2_num) in s1.iter().zip(s2.iter()) {
let s_diff_i = *s1_num - *s2_num;
let r_i = s_diff_i * challenge_diff_inv;
r.push(r_i);
}
r
}
从而由得
fn solve_for_a(s1: Vec<Fr>, challenge1: Fr, r: Vec<Fr>) -> Vec<Fr> {
let mut a = Vec::with_capacity(s1.capacity());
for (s1_num, r_num) in s1.iter().zip(r.iter()) {
let a_i = *s1_num - challenge1 * *r_num;
a.push(a_i);
}
a
}
同理，
fn solve_for_rho(u1: Fr, u2: Fr, challenge1: Fr, challenge2: Fr) -> Fr {
let challenge_diff_inv = (challenge1 - challenge2.double()).inverse().unwrap();
// return rho
(u1 - u2) * challenge_diff_inv }
fn solve_for_alpha(u1: Fr, challenge1: Fr, rho1: Fr) -> Fr {
// return alpha
u1 - challenge1 * rho1
}
解法2
由验证正确性知，对:
通过如下代码检验发现 且 。
let (commit_key, [(instance_1, proof_1), (instance_2, proof_2)]) = puzzle_data();
let b_1 = instance_1.b;
let b_2 = instance_2.b;
let a_comm_1 = instance_1.comm_a;
let a_comm_2 = instance_2.comm_a;
assert_eq!(a_comm_1, a_comm_2);
assert_eq!(b_1, b_2);
最终目标是找到使得。
展开第一个验证方程可得如下等式：
变换得：
重要观察：
给方程1乘以方程2乘以得到：
相减得：
let u_1 = proof_1.response.u; let u_2 = proof_2.response.u;
let s_1 = proof_1.response.s; let s_2 = proof_2.response.s;
let two = Fr::from(2);
let alpha = (two * gamma_2 * u_1 - gamma_1 * u_2) / (two * gamma_2 - gamma_1);
let a: Vec<Fr> = s_1 .iter() .zip(s_2.iter()) .map(|(s1_e, s2_e)| (two * gamma_2 * s1_e - gamma_1 * s2_e) / (two * gamma_2 - gamma_1)) .collect();