ZK Hack Puzzle 4 题解：如何攻破盲化KZG承诺隐私性

1KZG多项式承诺和PLONK

• KZG承诺参考此篇文章：KZG多项式承诺 （翻译：Star.LI @ Trapdoor Tech）
• 以及这篇文章：为以太坊引入 KZG 承诺：工程师视角（上）/为以太坊引入 KZG 承诺：工程师视角（下）（翻译: 阿剑）
• PLONK参见：V神的Understanding PLONK：https://vitalik.ca/general/2019/09/22/plonk.html
• 和 深入理解PlonK算法
• 原始KZG10论文：https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf

2挑战内容

见：https://github.com/kobigurk/zkhack-hidden-in-plain-sight

每个交易的接收者地址都通过盲化承诺隐藏。给出：

1. 1000个256位账户地址
2. 交易的盲化承诺
3. 盲化承诺的两个承诺打开
4. 公开可信设置

要求找出该交易接受者的账户地址。

为BLS12-381椭圆曲线群的生成元，是无一人知晓的秘密标量。

定义大小为的赋值域为 ，其中即为次单位根。

256位接收者账户地址被分为一个32字节的向量，每个字节（一个BLS12-381标量）作为一个阶为31的多项式的一个系数。

账户地址被分为32字节。将元组看作一个多项式的个赋值。使用逆FFT算法，插值计算出满足上述元组且阶小于的多项式

let target_acct_poly = DensePolynomial::from_coefficients_vec(domain.ifft(&target_acct));

交易发送者选择两个秘密盲因子，计算盲化多项式。

其中为消减多项式：对所有，

故

let blinding_poly = DensePolynomial::from_coefficients_vec(vec![Fr::rand(&mut rng), Fr::rand(&mut rng)]);
let blinded_acct_poly = target_acct_poly + blinding_poly.mul_by_vanishing_poly(domain);

对于多项式，其承诺为：

即为一个账户的盲化承诺。

let commitment: G1Affine = kzg_commit(&blinded_acct_poly, &setup);

3题解

将两个承诺打开展开：

得到关于两个未知数的线性方程组：

可以解出

// We compute P_a(x) 
let p = DensePolynomial::from_coefficients_vec(domain.ifft(&evals_p));

// Evaluate it at z_1,z_2 
let p_cha_1: Fr = p.evaluate(&cha_1); 
let p_cha_2: Fr = p.evaluate(&cha_2); 

// Here we just set up the 2 equations with 2 unknowns 
let e_cha_1 = opn_1 - p_cha_1; 
let e_cha_2 = opn_2 - p_cha_2; 
const N: u64 = 1024u64; 

// We compute b_0, b_1 
let b_1 = ((e_cha_1 / (cha_1.pow(&[N]) - Fr::from(1))) - (e_cha_2 / (cha_2.pow(&[N]) - Fr::from(1)))) / (cha_1 - cha_2); 
let b_0 = (e_cha_1 / (cha_1.pow(&[N]) - Fr::from(1))) - (b_1 * cha_1);

重构

观察多项式的系数：

如果两个多项式相等，则其对应系数相等：

全部已知，则可计算出

 // We set Q(x) = P(x) since most of the coeffients are the same 
 let mut q = vec![Fr::from(0); 1026]; 
 p.coeffs.iter().enumerate().for_each(|(idx, f)| q[idx] = f.clone());
 
 
 // We compute q_0,q_1,q_1024,q_1025 
 q[0] -= b_0; // q[0] = p[0] - b_0 
 q[1] -= b_1; // q[1] = p[1] - b_1 
 q[1024] = b_0.clone(); 
 q[1025] = b_1.clone();

还剩下计算并检验所得是否为给定交易的承诺：

// We compute comm(Q(x)) and check if it's equal to the given commitment 
let dp = DensePolynomial::from_coefficients_vec(q);
solution_commitment = kzg_commit(&dp, &setup); 
if (solution_commitment == commt) { 
 break; 
}

对所有账户迭代上述计算，accts[535]通过断言，即为给定交易的接收者。