Bulletproofs+ 代码解析

1. 引言

Chung等人2020年论文《Bulletproofs+: Shorter Proofs for Privacy-Enhanced Distributed Ledger》

代码实现参见：

• https://github.com/ZenGo-X/bulletproofs

各算法细节参见博客 Bulletproofs+: Shorter Proofs for Privacy-Enhanced Distributed Ledger学习笔记

2. zk-WIP (zero-knowledge weighted inner product argument)

参见https://github.com/ZenGo-X/bulletproofs/blob/master/src/proofs/weighted_inner_product.rs中代码：

fn test_helper(n: usize) {
        let KZen: &[u8] = &[75, 90, 101, 110];
        let kzen_label = BigInt::from(KZen);

        let g_vec = (0..n)
            .map(|i| {
                let kzen_label_i = BigInt::from(i as u32) + &kzen_label;
                let hash_i = HSha512::create_hash(&[&kzen_label_i]);
                generate_random_point(&Converter::to_vec(&hash_i))
            })
            .collect::();

        // can run in parallel to g_vec:
        let h_vec = (0..n)
            .map(|i| {
                let kzen_label_j = BigInt::from(n as u32) + BigInt::from(i as u32) + &kzen_label;
                let hash_j = HSha512::create_hash(&[&kzen_label_j]);
                generate_random_point(&Converter::to_vec(&hash_j))
            })
            .collect::();

        let label = BigInt::from(2);
        let hash = HSha512::create_hash(&[&label]);
        let g = generate_random_point(&Converter::to_vec(&hash));
        let label = BigInt::from(3);
        let hash = HSha512::create_hash(&[&label]);
        let h = generate_random_point(&Converter::to_vec(&hash));

        let a: Vec = (0..n)
            .map(|_| {
                let rand: FE = ECScalar::new_random();
                rand.to_big_int()
            })
            .collect();

        let b: Vec = (0..n)
            .map(|_| {
                let rand: FE = ECScalar::new_random();
                rand.to_big_int()
            })
            .collect();

        let y_scalar: BigInt =
            HSha256::create_hash_from_slice("Seed string decided by P,V!".as_bytes());
        let c = super::weighted_inner_product(&a, &b, y_scalar.clone());

        let alpha_fe: FE = ECScalar::new_random();
        let alpha = alpha_fe.to_big_int();

        let y: FE = ECScalar::new_random();
        let order = FE::q();
        let yi = (0..n)
            .map(|i| BigInt::mod_pow(&y.to_big_int(), &BigInt::from(i as u32), &order))
            .collect::();

        let yi_inv = (0..n)
            .map(|i| {
                let yi_fe: FE = ECScalar::from(&yi[i]);
                yi_fe.invert()
            })
            .collect::();

        let hi_tag = (0..n).map(|i| &h_vec[i] * &yi_inv[i]).collect::();

        // R =  +  + c * g + alpha*h
        let c_fe: FE = ECScalar::from(&c);
        let g_c: GE = &g * &c_fe;
        let h_alpha: GE = &h * &alpha_fe;
        let gc_halpha = g_c + h_alpha;
        let a_G = (0..n)
            .map(|i| {
                let ai: FE = ECScalar::from(&a[i]);
                &g_vec[i] * &ai
            })
            .fold(gc_halpha, |acc, x: GE| acc + x as GE);
        let P = (0..n)
            .map(|i| {
                let bi: FE = ECScalar::from(&b[i]);
                &hi_tag[i] * &bi
            })
            .fold(a_G, |acc, x: GE| acc + x as GE);

        let L_vec = Vec::with_capacity(n);
        let R_vec = Vec::with_capacity(n);
        let ipp = WeightedInnerProdArg::prove(
            &g_vec, &hi_tag, &g, &h, &P, &a, &b, &alpha, &y_scalar, L_vec, R_vec,
        );
        let verifier = ipp.verify(&g_vec, &hi_tag, &g, &h, &P, &y_scalar);
        assert!(verifier.is_ok())
    }

3. 基于zk-WIP构建的range proof

• range proof中计算 A = g ⃗ a ⃗ L h ⃗ a ⃗ R h α ∈ G A=\vec{g}^{\vec{a}_L}\vec{h}^{\vec{a}_R}h^{\alpha}\in\mathbb{G} A=g ​a L​h a R​hα∈G的代码实现有： – https://github.com/dalek-cryptography/bulletproofs/blob/main/src/range_proof/party.rs 中利用了subtle crate (实现常量时间执行密码学操作的库)，且实际代码实现更巧妙：

let a_blinding = Scalar::random(rng);
        // Compute A =  +  + a_blinding * B_blinding
        let mut A = self.pc_gens.B_blinding * a_blinding;

        use subtle::{Choice, ConditionallySelectable};
        let mut i = 0;
        for (G_i, H_i) in bp_share.G(self.n).zip(bp_share.H(self.n)) {
			// 注意，a_R[i]=a_L[i]-1
            // If v_i = 0, we add a_L[i] * G[i] + a_R[i] * H[i] = - H[i]
            // If v_i = 1, we add a_L[i] * G[i] + a_R[i] * H[i] =   G[i]
            let v_i = Choice::from(((self.v >> i) & 1) as u8); //若v的该bit为1，则v_i=1，否则v_i=0。
            let mut point = -H_i;
            point.conditional_assign(G_i, v_i); //若v_i=1，则point=1*G_i+(1-1)*H_i=G_i; 若v_i=0，则point=0*G+(0-1)*H_i=-H_i
            A += point;
            i += 1;
        }

– https://github.com/ZenGo-X/bulletproofs/blob/master/src/proofs/range_proof_wip.rs 中的实现为：

//concat all secrets:
        secret.reverse();
        let secret_agg = secret.iter().fold(BigInt::zero(), |acc, x| {
            acc.shl(bit_length) + x.to_big_int()
        });

        let aL = (0..nm)
            .map(|i| {
                let shr_secret = secret_agg.clone().shr(i);
                shr_secret.modulus(&two)
            })
            .collect::();
        let aR = (0..nm)
            .map(|i| BigInt::mod_sub(&aL[i], &one, &order))
            .collect::();

        let secret_bits = (0..nm)
            .map(|i| {
                let bignum_bit: BigInt = aL[i].clone() & BigInt::one();
                let byte = BigInt::to_vec(&bignum_bit);
                byte[0] == 1
            })
            .collect::();

        // let mut index: usize = 0;
        let alpha: FE = ECScalar::new_random();
        let mut A = H * α
        A = g_vec.iter().zip(secret_bits.clone()).fold(A, |acc, x| {
            if x.1 {
                acc.add_point(&x.0.get_element())
            } else {
                acc
            }
        });
        A = h_vec.iter().zip(secret_bits.clone()).fold(A, |acc, x| {
            if !x.1 {
                acc.sub_point(&x.0.get_element())
            } else {
                acc
            }
        });