Bulletproofs 代码解析

1. 引言

Benedikt B¨unz、 Jonathan Bootle和 Dan Boneh等人2018年论文《Bulletproofs: Short Proofs for Confidential Transactions and More》，相应的代码实现库有：

• https://github.com/dalek-cryptography/bulletproofs
• https://github.com/adjoint-io/bulletproofs
• https://github.com/lovesh/bulletproofs-r1cs-gadgets （基于 https://github.com/dalek-cryptography/bulletproofs ，将待证明statement转换为R1CS arithmetic circuit进行证明，包含的例子有：证明某值在特定范围；证明某值为非附属；证明某值不等于特定值；membership或non-membership证明等等。）
• https://github.com/KZen-networks/bulletproofs
• https://github.com/akosba/jsnark

https://github.com/akosba/jsnark 中提供了一个通用工具，用于构建Bulletproofs for any NP language，该工具可读取Pinocchio格式的arithmetic circuit，同时包含了将C语言编译为circuit fomat 的编译器。

本博文主要针对https://github.com/dalek-cryptography/bulletproofs 代码实现进行解析。

https://github.com/dalek-cryptography/bulletproofs 为当前速度最快的Bulletproofs算法实现，其使用https://github.com/dalek-cryptography/curve25519-dalek 中对 curve25519曲线 封装的 ristretto255 group ，当采用 AVX2 backend来进行并行计算时，对于64-bit的rangproofs，其速度要比 libsecp256k1实现的Bulletproofs 快将近2倍。 看https://github.com/dalek-cryptography/bulletproofs/blob/main/Cargo.toml 中配置可知，https://github.com/dalek-cryptography/bulletproofs 默认启动了avx2_backend并行计算.

[features]
default = ["std", "avx2_backend"]
avx2_backend = ["curve25519-dalek/avx2_backend"]
# yoloproofs = []
std = ["rand", "rand/std", "thiserror"]

为实现non-interactive zero-knowledge proof，其中的 Fiat-Shamir transform 采用的是 Merlin框架（https://github.com/dalek-cryptography/merlin）。

2. Inner product proof 代码实现 ipp

主要见https://github.com/dalek-cryptography/bulletproofs/blob/main/src/inner_product_proof.rs 中代码：

fn test_helper_create(n: usize) { //其中n为vector size
        let mut rng = rand::thread_rng();

        use crate::generators::BulletproofGens;
        let bp_gens = BulletproofGens::new(n, 1);
        let G: Vec = bp_gens.share(0).G(n).cloned().collect();
        let H: Vec = bp_gens.share(0).H(n).cloned().collect();

        // Q would be determined upstream in the protocol, so we pick a random one.
        let Q = RistrettoPoint::hash_from_bytes::(b"test point");

        // a and b are the vectors for which we want to prove c = 
        let a: Vec = (0..n).map(|_| Scalar::random(&mut rng)).collect();
        let b: Vec = (0..n).map(|_| Scalar::random(&mut rng)).collect();
        let c = inner_product(&a, &b);

        let G_factors: Vec = iter::repeat(Scalar::one()).take(n).collect();

        // y_inv is (the inverse of) a random challenge
        let y_inv = Scalar::random(&mut rng);
        let H_factors: Vec = util::exp_iter(y_inv).take(n).collect();

        // P would be determined upstream, but we need a correct P to check the proof.
        //
        // To generate P =  +  +  Q, compute
        //             P =  +  +  Q,
        // where b' = b \circ y^(-n)
        let b_prime = b.iter().zip(util::exp_iter(y_inv)).map(|(bi, yi)| bi * yi);
        // a.iter() has Item=&Scalar, need Item=Scalar to chain with b_prime
        let a_prime = a.iter().cloned();

        let P = RistrettoPoint::vartime_multiscalar_mul(
            a_prime.chain(b_prime).chain(iter::once(c)),
            G.iter().chain(H.iter()).chain(iter::once(&Q)),
        );

        let mut verifier = Transcript::new(b"innerproducttest");
        let proof = InnerProductProof::create(
            &mut verifier,
            &Q,
            &G_factors,
            &H_factors,
            G.clone(),
            H.clone(),
            a.clone(),
            b.clone(),
        );

        let mut verifier = Transcript::new(b"innerproducttest");
        assert!(proof
            .verify(
                n,
                &mut verifier,
                iter::repeat(Scalar::one()).take(n),
                util::exp_iter(y_inv).take(n),
                &P,
                &Q,
                &G,
                &H
            )
            .is_ok());

        let proof = InnerProductProof::from_bytes(proof.to_bytes().as_slice()).unwrap();
        let mut verifier = Transcript::new(b"innerproducttest");
        assert!(proof
            .verify(
                n,
                &mut verifier,
                iter::repeat(Scalar::one()).take(n),
                util::exp_iter(y_inv).take(n),
                &P,
                &Q,
                &G,
                &H
            )
            .is_ok());
    }

3. range proof (aggregated)

代码实现主要见https://github.com/dalek-cryptography/bulletproofs/blob/main/src/range_proof/mod.rs：

// m为value数量，n为范围的bitsize
/// Given a bitsize `n`, test the following:
    ///
    /// 1. Generate `m` random values and create a proof they are all in range;
    /// 2. Serialize to wire format;
    /// 3. Deserialize from wire format;
    /// 4. Verify the proof.
    fn singleparty_create_and_verify_helper(n: usize, m: usize) {
        // Split the test into two scopes, so that it's explicit what
        // data is shared between the prover and the verifier.

        // Use bincode for serialization
        //use bincode; // already present in lib.rs

        // Both prover and verifier have access to the generators and the proof
        let max_bitsize = 64;
        let max_parties = 8;
        let pc_gens = PedersenGens::default();
        let bp_gens = BulletproofGens::new(max_bitsize, max_parties);

        // Prover's scope
        let (proof_bytes, value_commitments) = {
            use self::rand::Rng;
            let mut rng = rand::thread_rng();

            // 0. Create witness data
            let (min, max) = (0u64, ((1u128  {
                assert_eq!(bad_shares, vec![1, 3]);
            }
            Err(_) => {
                panic!("Got wrong error type from malformed shares");
            }
            Ok(_) => {
                panic!("The proof was malformed, but it was not detected");
            }
        }
    }

    #[test]
    fn detect_dishonest_dealer_during_aggregation() {
        use self::dealer::*;
        use self::party::*;
        use crate::errors::MPCError;

        // Simulate one party
        let m = 1;
        let n = 32;

        let pc_gens = PedersenGens::default();
        let bp_gens = BulletproofGens::new(n, m);

        use self::rand::Rng;
        let mut rng = rand::thread_rng();
        let mut transcript = Transcript::new(b"AggregatedRangeProofTest");

        let v0 = rng.gen::() as u64;
        let v0_blinding = Scalar::random(&mut rng);
        let party0 = Party::new(&bp_gens, &pc_gens, v0, v0_blinding, n).unwrap();

        let dealer = Dealer::new(&bp_gens, &pc_gens, &mut transcript, n, m).unwrap();

        // Now do the protocol flow as normal....

        let (party0, bit_com0) = party0.assign_position(0).unwrap();

        let (dealer, bit_challenge) = dealer.receive_bit_commitments(vec![bit_com0]).unwrap();

        let (party0, poly_com0) = party0.apply_challenge(&bit_challenge);

        let (_dealer, mut poly_challenge) =
            dealer.receive_poly_commitments(vec![poly_com0]).unwrap();

        // But now simulate a malicious dealer choosing x = 0
        poly_challenge.x = Scalar::zero();

        let maybe_share0 = party0.apply_challenge(&poly_challenge);

        assert!(maybe_share0.unwrap_err() == MPCError::MaliciousDealer);
    }

5. Bulletproofs R1CS——用于Verifiable shuffle证明

如需运行，注意切换develop 分支，同时cargo test --feature "yoloproofs"。

其中的permutation为未知不公开的Verifiable shuffle证明。 主要思路为： 若committed x 1 , ⋯   , x n x_1,\cdots,x_n x1​,⋯,xn​为committed y 1 , ⋯   , y n y_1,\cdots,y_n y1​,⋯,yn​的某中permutation，则对于任意的challenge z z z，应有： ∏ i = 1 n ( x i − z ) = ∏ i = 1 n ( y i − z ) \prod_{i=1}^{n}(x_i-z)=\prod_{i=1}^{n}(y_i-z) ∏i=1n​(xi​−z)=∏i=1n​(yi​−z) 恒成立。

具体的代码实现见：https://github.com/dalek-cryptography/bulletproofs/blob/main/tests/r1cs.rs：

fn kshuffle_helper(k: usize) { // k为vector size
    use rand::Rng;

    // Common code
    let pc_gens = PedersenGens::default();
    let bp_gens = BulletproofGens::new((2 * k).next_power_of_two(), 1);

    let (proof, input_commitments, output_commitments) = {
        // Randomly generate inputs and outputs to kshuffle
        let mut rng = rand::thread_rng();
        let (min, max) = (0u64, std::u64::MAX);
        let input: Vec = (0..k)
            .map(|_| Scalar::from(rng.gen_range(min, max)))
            .collect();
        let mut output = input.clone();
        output.shuffle(&mut rand::thread_rng());

        let mut prover_transcript = Transcript::new(b"ShuffleProofTest");
        ShuffleProof::prove(&pc_gens, &bp_gens, &mut prover_transcript, &input, &output).unwrap()
    };

    {
        let mut verifier_transcript = Transcript::new(b"ShuffleProofTest");
        assert!(proof
            .verify(
                &pc_gens,
                &bp_gens,
                &mut verifier_transcript,
                &input_commitments,
                &output_commitments
            )
            .is_ok());
    }
}

参考资料

[1] 博客 Bulletproof现有代码实现说明 [2] 博客 bulletproofs for r1cs [3] 博客 ristretto255对外API抽象及基于Curve25519的ristretto255层实现 [4] 博客 ristretto对cofactor>1的椭圆曲线(如Curve25519等)的兼容（含Curve25519 cofactor的sage验证） [5] 博客 Zero knowledge proofs using Bulletproofs [6] 博客 curve25519-dalek并行运算性能 [7] 博客 Accelerating Edwards Curve Arithmetic with Parallel Formulas [8] 博客 Merlin——零知识证明（1）理论篇