Proofs for Inner Pairing Products and Applications代码解析

1. 引言

Benedikt Bünz 等人（standford,ethereum,berkeley） 2019年论文《Proofs for Inner Pairing Products and Applications》。

视频介绍：（2020年3月31日） https://www.youtube.com/watch?v=oYdkGIoHKt0

代码实现：

• https://github.com/scipr-lab/ripp【本文重点解析本代码库】
• https://github.com/qope/SIPP（Rust，基于Plonky2和Starky的BN254 pairing以及 ecdsa）：在M1 MacBookPro(2021)机器上运行cargo test test_sipp_circuit -r -- --nocapture，基本性能为：【排除circuit building时间，做128个pairing聚合用时约145秒。】

  Aggregating 128 pairings into 1
  Start: cirucit build
  End: circuit build. took 35.545641375s
  Start: proof generation
  End: proof generation. took 145.043526708s
  

注意该代码使用rust stable版本，且低版本可能会报错，建议升级到最新的stable版本：

rustup install stable

代码总体基本结构为：

• examples：scaling-ipp.rs，执行方式可为cargo run --release --example scaling-ipp 10 20 .

• plot：ipp-scaling.gnuplot为gnuplot脚本，使用examples/scaling-ipp 输出的*.csv作图。

• src：主源代码。 – rng.rs：主要实现FiatShamirRng，基于Fiat-Shamir来实现non-interactive proof。【注意，与Merlin实现Fiat-Shamir transform方案有所不同，Merlin transcript是基于STROBE的 封装。Strobe的主要涉及原则为：在任意阶段的密码学输出，除依赖于密钥外，还依赖于之前所有的输入。strobe主要采用对称加密方案，更侧重于简单和安全，而不是速度；noise协议采用非对称加密方案，已在WhatsAPP上落地应用。】（详细参加博客 Merlin——零知识证明（1）理论篇 和博客 strobe——面向IoT物联网应用的密码学协议框架）

/// A `SeedableRng` that refreshes its seed by hashing together the previous seed
/// and the new seed material.
// TODO: later: re-evaluate decision about ChaChaRng
pub struct FiatShamirRng {
    r: ChaChaRng,
    seed: GenericArray,
    #[doc(hidden)]
    digest: PhantomData,
}

– lib.rs：实现了论文《Proofs for Inner Pairing Products and Applications》中的SIPP协议。

2. 主要依赖

参见https://github.com/scipr-lab/ripp/blob/master/Cargo.toml中内容，分为[dependencies]和[dev-dependencies]，两者的异同点有：

• [dev-dependencies]段落的格式等同于[dependencies]段落，
• 不同之处在于，[dependencies]段落声明的依赖用于构建软件包，
• 而[dev-dependencies]段落声明的依赖仅用于构建测试和性能评估。
• 此外，[dev-dependencies]段落声明的依赖不会传递给其他依赖本软件包的项目

[dependencies]依赖主要有：

• algebra-core = { git = “https://github.com/scipr-lab/zexe”, features = [ “parallel” ] }：为Rust crate that provides generic arithmetic for finite fields and elliptic curves。其中features parallel = [ "std", "rayon" ]。
• rayon：为data-parallelism Rust库。非常轻量，很容易convert a sequential computation into a parallel one。（具体可参加博客 Rayon: data parallelism in Rust）

// sequential iterator
let total_price = stores.iter()
                        .map(|store| store.compute_price(&list))
                        .sum();
// parallel iterator
let total_price = stores.par_iter()
                        .map(|store| store.compute_price(&list))
                        .sum();

• rand_core：主要用于实现the core trait：RngCore。
• rand_chacha：为使用ChaCha算法实现的密码学安全的随机数生成器。
• digest：为https://github.com/RustCrypto/traits中的digest算法。

[dev-dependencies]依赖主要有：

• blake2：BLAKE2 hash function family库。
• rand：provides utilities to generate random numbers, to convert them to useful types and distributions, and some randomness-related algorithms.
• csv：A fast and flexible CSV reader and writer for Rust, with support for Serde.
• serde = { version = “1”, features = [ “derive” ] }：Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.
• algebra = { git = “https://github.com/scipr-lab/zexe”, features = [ “bls12_377” ] }：为 Rust crate that provides concrete instantiations of some finite fields and elliptic curves。

3. SIPP协议实现

参见博客 Proofs for Inner Pairing Products and Applications 学习笔记第3.1节“SIPP的构建”。 在lib.rs中的实现为 A ⃗ = { r 1 a 1 , ⋯   , r m a m } , B ⃗ = { b 1 , ⋯   , b m } \vec{A}=\{r_1a_1,\cdots,r_ma_m\},\vec{B}=\{b_1,\cdots,b_m\} A ={r1​a1​,⋯,rm​am​},B ={b1​,⋯,bm​}，其中 r i ∈ F r , a i ∈ G 1 , b i ∈ G 2 r_i\in\mathbb{F}_r,a_i\in\mathbb{G}_1,b_i\in\mathbb{G}_2 ri​∈Fr​,ai​∈G1​,bi​∈G2​。 在SIPP协议中 A ⃗ , B ⃗ , Z = A ⃗ ∗ B ⃗ = ∏ i = 1 m e ( A i , B i ) \vec{A},\vec{B},Z=\vec{A}*\vec{B}=\prod_{i=1}^{m}e(A_i,B_i) A ,B ,Z=A ∗B =∏i=1m​e(Ai​,Bi​)均为。在实际Verify时，并未逐轮计算 A ⃗ ′ , B ⃗ ′ \vec{A}',\vec{B}' A ′,B ′，而是将其展开了利用multi_scalar_mul来计算。同时使用FiatShamirRng将interactive proof转为了non-interactive proof。 详细的代码实现为：

• 初始化 a ⃗ , r ⃗ , B ⃗ \vec{a},\vec{r},\vec{B} a ,r ,B vector信息：

        for _ in 0..32 {
            a.push(G1Projective::rand(&mut rng).into_affine());
            b.push(G2Projective::rand(&mut rng).into_affine());
            r.push(Fr::rand(&mut rng));
        }

• 计算 Z = A ⃗ ∗ B ⃗ = ∏ i = 1 m e ( r i a i , B i ) Z=\vec{A}*\vec{B}=\prod_{i=1}^{m}e(r_ia_i,B_i) Z=A ∗B =∏i=1m​e(ri​ai​,Bi​)

let z = product_of_pairings_with_coeffs::(&a, &b, &r);

/// Compute the product of pairings of `r_i * a_i` and `b_i`.
pub fn product_of_pairings_with_coeffs(
    a: &[E::G1Affine],
    b: &[E::G2Affine],
    r: &[E::Fr],
) -> E::Fqk {
    let a = a.into_par_iter().zip(r).map(|(a, r)| a.mul(*r)).collect::();
    let a = E::G1Projective::batch_normalization_into_affine(&a);
    let elements = a
        .par_iter()
        .zip(b)
        .map(|(a, b)| (E::G1Prepared::from(*a), E::G2Prepared::from(*b)))
        .collect::();
    let num_chunks = elements.len() / rayon::current_num_threads();
    let num_chunks = if num_chunks == 0 { elements.len() } else { num_chunks };
    let ml_result = elements
        .par_chunks(num_chunks)
        .map(E::miller_loop)
        .product();
    E::final_exponentiation(&ml_result).unwrap()
}

• SIPP prove证明：（输入为 a ⃗ , r ⃗ , B ⃗ , Z \vec{a},\vec{r},\vec{B},Z a ,r ,B ,Z）

let proof = SIPP::::prove(&a, &b, &r, z);

/// Produce a proof of the inner pairing product.
    pub fn prove(
        a: &[E::G1Affine],
        b: &[E::G2Affine],
        r: &[E::Fr],
        value: E::Fqk
    ) -> Result {
        assert_eq!(a.len(), b.len());
        // Ensure the order of the input vectors is a power of 2
        assert_eq!(a.len().count_ones(), 1);
        let mut length = a.len();
        assert_eq!(length, b.len());
        assert_eq!(length.count_ones(), 1);
        let mut proof_vec = Vec::new();
        // TODO(psi): should we also input a succinct bilinear group description to the rng?
        let mut rng = FiatShamirRng::::from_seed(&to_bytes![a, b, r, value].unwrap());
        let a = a.into_par_iter().zip(r).map(|(a, r)| a.mul(*r)).collect::();
        let mut a = E::G1Projective::batch_normalization_into_affine(&a);
        let mut b = b.to_vec();

        while length != 1 {
            length /= 2;
            let a_l = &a[..length];
            let a_r = &a[length..];

            let b_l = &b[..length];
            let b_r = &b[length..];

            let z_l = product_of_pairings::(a_r, b_l);
            let z_r = product_of_pairings::(a_l, b_r);
            proof_vec.push((z_l, z_r));
            rng.absorb(&to_bytes![z_l, z_r].unwrap());
            let x: E::Fr = u128::rand(&mut rng).into();

            let a_proj = a_l.par_iter().zip(a_r).map(|(a_l, a_r)| {
                let mut temp = a_r.mul(x);
                temp.add_assign_mixed(a_l);
                temp
            }).collect::();
            a = E::G1Projective::batch_normalization_into_affine(&a_proj);

            let x_inv = x.inverse().unwrap();
            let b_proj = b_l.par_iter().zip(b_r).map(|(b_l, b_r)| {
                let mut temp = b_r.mul(x_inv);
                temp.add_assign_mixed(b_l);
                temp
            }).collect::();
            b = E::G2Projective::batch_normalization_into_affine(&b_proj);
        }

        Ok(Proof {
            gt_elems: proof_vec
        })
    }

• SIPP verify 验证：（输入为 a ⃗ , r ⃗ , B ⃗ , Z , p r o o f ⃗ \vec{a},\vec{r},\vec{B},Z,\vec{proof} a ,r ,B ,Z,proof ​）

let accept = SIPP::::verify(&a, &b, &r, z, &proof);

/// Verify an inner-pairing-product proof.
    pub fn verify(
        a: &[E::G1Affine],
        b: &[E::G2Affine],
        r: &[E::Fr],
        claimed_value: E::Fqk,
        proof: &Proof
    ) -> Result {
        // Ensure the order of the input vectors is a power of 2
        let length = a.len();
        assert_eq!(length.count_ones(), 1);
        assert!(length >= 2);
        assert_eq!(length, b.len());
        // Ensure there are the correct number of proof elements
        let proof_len = proof.gt_elems.len();
        assert_eq!(proof_len as f32, f32::log2(length as f32));

        // TODO(psi): should we also input a succinct bilinear group description to the rng?
        let mut rng = FiatShamirRng::::from_seed(&to_bytes![a, b, r, claimed_value].unwrap());

        let x_s = proof.gt_elems.iter().map(|(z_l, z_r)| {
            rng.absorb(&to_bytes![z_l, z_r].unwrap());
            let x: E::Fr = u128::rand(&mut rng).into();
            x
        }).collect::();

        let mut x_invs = x_s.clone();
        algebra_core::batch_inversion(&mut x_invs);

        let z_prime = claimed_value * &proof.gt_elems.par_iter().zip(&x_s).zip(&x_invs).map(|(((z_l, z_r), x), x_inv)| {
            z_l.pow(x.into_repr()) * &z_r.pow(x_inv.into_repr())
        }).reduce(|| E::Fqk::one(), |a, b| a * &b);

        let mut s: Vec = vec![E::Fr::one(); length];
        let mut s_invs: Vec = vec![E::Fr::one(); length];
        // TODO(psi): batch verify
        for (j, (x, x_inv)) in x_s.into_iter().zip(x_invs).enumerate() {
            for i in 0..length {
                if i & (1