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<D: Digest> {r: ChaChaRng,seed: GenericArray<u8, D::OutputSize>,#[doc(hidden)]digest: PhantomData<D>,
}

– 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\in {\mathbb{F}}_r,a_i\in {\mathbb{G}}_1,b_i\in {\mathbb{G}}_2$。
在SIPP协议中$\vec{A},\vec{B},Z=\vec{A}\ast \vec{B}={\prod }_{i=1}^{m}e(A_i,B_i)$均为。在实际Verify时，并未逐轮计算${\vec{A}}^{\prime },{\vec{B}}^{\prime }$，而是将其展开了利用multi_scalar_mul来计算。同时使用FiatShamirRng将interactive proof转为了non-interactive proof。
详细的代码实现为：

• 初始化$\vec{a},\vec{r},\vec{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=\vec{A}\ast \vec{B}={\prod }_{i=1}^{m}e(r_i{a}_i,B_i)$

let z = product_of_pairings_with_coeffs::<Bls12_377>(&a, &b, &r);/// Compute the product of pairings of `r_i * a_i` and `b_i`.
pub fn product_of_pairings_with_coeffs<E: PairingEngine>(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::<Vec<_>>();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::<Vec<_>>();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证明：（输入为$\vec{a},\vec{r},\vec{B},Z$）

let proof = SIPP::<Bls12_377, Blake2s>::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<Proof<E>, ()> {assert_eq!(a.len(), b.len());// Ensure the order of the input vectors is a power of 2assert_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::<D>::from_seed(&to_bytes![a, b, r, value].unwrap());let a = a.into_par_iter().zip(r).map(|(a, r)| a.mul(*r)).collect::<Vec<_>>();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::<E>(a_r, b_l);let z_r = product_of_pairings::<E>(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::<Vec<_>>();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::<Vec<_>>();b = E::G2Projective::batch_normalization_into_affine(&b_proj);}Ok(Proof {gt_elems: proof_vec})}

• SIPP verify 验证：（输入为$\vec{a},\vec{r},\vec{B},Z,\overrightarrow{proof}$）

let accept = SIPP::<Bls12_377, Blake2s>::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<E>) -> Result<bool, ()> {// Ensure the order of the input vectors is a power of 2let 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 elementslet 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::<D>::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::<Vec<_>>();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<E::Fr> = vec![E::Fr::one(); length];let mut s_invs: Vec<E::Fr> = vec![E::Fr::one(); length];// TODO(psi): batch verifyfor (j, (x, x_inv)) in x_s.into_iter().zip(x_invs).enumerate() {for i in 0..length {if i & (1 << (proof_len - j - 1)) != 0 {s[i] *= &x;s_invs[i] *= &x_inv;}}}let s = s.into_iter().zip(r).map(|(x, r)| (x * r).into_repr()).collect::<Vec<_>>();let s_invs = s_invs.iter().map(|x_inv| x_inv.into_repr()).collect::<Vec<_>>();let a_prime = VariableBaseMSM::multi_scalar_mul(&a, &s);let b_prime = VariableBaseMSM::multi_scalar_mul(&b, &s_invs);let accept = E::pairing(a_prime, b_prime) == z_prime;Ok(accept)}
}