ZCash bellman版本 Groth16代码解析

1. 引言

Groth 2016年论文《On the Size of Pairing-based Non-interactive Arguments》。

相关代码实现有：

• https://github.com/matter-labs/bellman
• https://github.com/zkcrypto/bellman
• https://github.com/arkworks-rs/groth16

本文主要关注代码：

• https://github.com/zkcrypto/bellman

该代码库中的主要依赖有：

• https://github.com/zkcrypto/ff
• https://github.com/zkcrypto/group
• https://github.com/zkcrypto/pairing
• https://github.com/zkcrypto/bls12_381
• crossbeam：并发编程工具
• subtle：常量执行密码学操作的库
• futures_cpupool：用于excute work on a thread pool。
• futures：为Rust异步编程库。
• num_cpus：用于获取机器CPU的数量。

1.1 ff

https://github.com/zkcrypto/ff 为：

• 使用纯Rust语言编写的 finite field library，其中未使用任何unsafe{}代码。

其提供的traits有：

• BitView：Create a BitSlice view over some type that supports it.
• Field：表示an element of a field.
• PrimeField：表示an element of a prime field。

其提供的函数接口有：

• adc：计算a+b+carry，返回the sum以及modify the carry value.
• mac_with_carry：计算a+(b*c)+carry，返回the least significant digit以及setting carry to the most significant digit.
• sbb：计算a-b-borrow，返回the result以及modify the borrow value.

其定义的类型有：

• FieldBits：为bit representation of a field element.

若想实现自己的prime field，按如下操作即可：

• 首先启用derive feature

[dependencies]
ff = { version = "0.9", features = ["derive"] }

• 然后按如下顺序设置宏即可：【至此，Fp即实现了Field和PrimeField。】

#[macro_use]
extern crate ff;

#[derive(PrimeField)]
#[PrimeFieldModulus = "52435875175126190479447740508185965837690552500527637822603658699938581184513"]
#[PrimeFieldGenerator = "7"]
#[PrimeFieldReprEndianness = "little"]
struct Fp([u64; 4]);

1.2 group

https://github.com/zkcrypto/group 为：

• a crate for working with groups over elliptic curves。

其提供的trait主要有：

• Add、Sub、AddAssign、SubAssign等group operation GroupOps
• group scalar multiplication ScalarMul
• cryptographic group中an element的表示 Group
• elliptic curve 上point的高效表示 Curve （如to_affine坐标系表示，以及batch_normalize即批量将projective表示的元素转换为affine表示的元素。）
• GroupEncoding以及UncompressedEncoding
• PrimeGroup:Group+GroupEncoding：表示an element of a prime-order cryptographic group.
• PrimeCurve：表示an elliptic curve point guaranteed to be in the correct prime order subgroups.
• PrimeCurveAffine：为an elliptic curve point guaranteed to be in the correct prime order subgroups的affIne表示。
• WnafGroup:Group：为Extension trait on a [Group] that provides helpers used by [Wnaf]。

1.3 pairing

https://github.com/zkcrypto/pairing 为：

• a crate for using pairing-friendly elliptic curves.

其提供了构建pairing-friendly elliptic curve所需的基本traits。特定曲线的curve可参见特定的库。如BLS12-381 curve的实现见：https://github.com/zkcrypto/bls12_381。

其提供的trait主要有：

• Engine：为a collection of types (fields, elliptic curve groups, etc.) with well-defined relationships. In particular, the G1/G2 curve groups are of prime order r, and are equipped with a bilinear pairing function.
• PairingCurveAffine：为 affine representation of an elliptic curve point that can be used to perform pairings.
• MultiMillerLoop：为 an engine that can compute sums of pairings in an efficient way.
• MillerLoopResult：为pairing运算中最昂贵的部分。Represents results of a Miller loop, one of the most expensive portions of the pairing function. MillerLoopResults cannot be compared with each other until [MillerLoopResult::final_exponentiation] is called, which is also expensive.

1.4 bls12_381

https://github.com/zkcrypto/bls12_381 中构建了BLS12-381 pairing-friendly elliptic curve。该库：

• 未经过代码审计。
• 不需要Rust standard library。
• 除非明确标注，所有的操作都是constant time的。

其支持的主要特征有：

• bits：默认开启。允许通过API获取scalar的bit iterator。
• groups：默认开启。允许通过API进行group arithmetic with G1, G2和GT。
• pairings：默认开启。允许通过API进行pairing运算。
• alloc：默认开启。允许通过API获取allocator。包含了pairing优化。
• nightly：启用subtle/nightly，可阻止编译器优化影响constant time operations。需要nightly Rust compiler。
• endo：默认开启。允许借助curve endomorphism进行优化。已deprecated，在未来release将移除本功能。
• experimental：可启用一些测试特性。当前支持的测试特性有： – Hashing to curves

2. bellman

https://github.com/zkcrypto/bellman 中构建了zk-SNARK circuits。提供了：

• circuit traits
• primitive structures
• basic gadget implementations，如booleans和number abstractions。

其features为：

[features]
groth16 = ["pairing"]
multicore = ["futures-cpupool", "crossbeam", "num_cpus"]
default = ["groth16", "multicore"]

该代码库中各源码主要功能为：

• src/multicore.rs：提供了并行计算接口。当前仅为cpupool和crossbeam的简单封装。未来可能会扩展至支持多种并行策略。
• src/multiexp.rs：为 c = a 1 g 1 + a 2 g 2 + ⋯ + a n g n c=a_1g_1+a_2g_2+\cdots+a_ng_n c=a1​g1​+a2​g2​+⋯+an​gn​ multi-exponentiation运算提供了与多线程（CPU内核数）并行计算函数pub fn multiexp。
• src/domain.rs：主要包含了EvaluationDomain，用于表示在scalar field域内的各种多项式运算。（包含各种fft和ifft运算。具体见其中的测试用例。） 像Groth16这样基于pairing的SNARKs，需要计算某多项式 与 代表contraint的roots多项式 的商多项式。为了提升计算效率，对于n阶多项式，通常选择这些root为powers of 2 n 2^n 2n-th root of unity。使得相应的多项式运算为O(n) by performing an O(n log n) FFT over such a domain。
• src/gadget.rs：实现了Assignment trait，对于未分配的赋值，返回AssignmentMissing错误。
• src/lib.rs：定义了： – Circuit trait，Groth16中的arithmetic circuit以rank-1 quadratic constraint system形式表示。Circuit trait 代表可合成的circuit，其synthesize函数在生成CRS和Prove过程中会被调用。 合成过程中存在的错误类型有：

/// This is an error that could occur during circuit synthesis contexts,
/// such as CRS generation or proving.
#[derive(Debug)]
pub enum SynthesisError {
    /// During synthesis, we lacked knowledge of a variable assignment.
    AssignmentMissing,
    /// During synthesis, we divided by zero.
    DivisionByZero,
    /// During synthesis, we constructed an unsatisfiable constraint system.
    Unsatisfiable,
    /// During synthesis, our polynomials ended up being too high of degree
    PolynomialDegreeTooLarge,
    /// During proof generation, we encountered an identity in the CRS
    UnexpectedIdentity,
    /// During proof generation, we encountered an I/O error with the CRS
    IoError(io::Error),
    /// During CRS generation, we observed an unconstrained auxiliary variable
    UnconstrainedVariable,
}

验证过程中的错误类型有：

/// An error during verification.
#[derive(Debug, Clone)]
pub enum VerificationError {
    /// Verification was attempted with a malformed verifying key.
    InvalidVerifyingKey,
    /// Proof verification failed.
    InvalidProof,
}

– contraint system中的变量表示：

/// Represents a variable in our constraint system.
#[derive(Copy, Clone, Debug)]
pub struct Variable(Index);
/// Represents the index of either an input variable or
/// auxiliary variable.
#[derive(Copy, Clone, PartialEq, Debug)]
pub enum Index {
    Input(usize),
    Aux(usize),
}

– 基于变量的线性运算表示为：（其中Scalar表示的是变量的系数。）

/// This represents a linear combination of some variables, with coefficients
/// in the scalar field of a pairing-friendly elliptic curve group.
#[derive(Clone)]
pub struct LinearCombination(Vec);

– ContraintSystem：用于表示可allocate new variable和contrain这些variables关系的 constraint system。 – Namespace constraint system：borrow了a constraint system (pushing a namespace context)，当drop时，会pop out该namespace context。 需为Namespace struct实现ConstraintSystem trait和drop trait。 同时也为ConstraintSystem实现ConstraintSystem trait。

2.1 groth16

针对的为src/groth16目录下的代码。

• generators.rs：生成CRS。 ( σ ⃗ , τ ⃗ ) ← S e t u p ( R ) (\vec{\sigma},\vec{\tau})\leftarrow Setup(R) (σ ,τ )←Setup(R)：选择 α , β , γ , δ , x ← F ∗ \alpha,\beta,\gamma,\delta,x\leftarrow \mathbb{F}^* α,β,γ,δ,x←F∗，设置 τ ⃗ = ( α , β , γ , δ , x ) \vec{\tau}=(\alpha,\beta,\gamma,\delta,x) τ =(α,β,γ,δ,x)， σ ⃗ = ( [ σ ⃗ 1 ] 1 , [ σ ⃗ 2 ] 2 ) \vec{\sigma}=([\vec{\sigma}_1]_1,[\vec{\sigma}_2]_2) σ =([σ 1​]1​,[σ 2​]2​)，其中： σ ⃗ 1 = ( α , β , γ , δ , { x i } i = 0 n − 1 , { β u i ( x ) + α v i ( x ) + w i ( x ) γ } i = 0 l , { β u i ( x ) + α v i ( x ) + w i ( x ) δ } i = l + 1 m , { x i t ( x ) δ } i = 0 n − 2 ) , σ ⃗ 2 = ( β , γ , δ , { x i } i = 0 n − 1 ) \vec{\sigma}_1 = (\alpha,\beta,\gamma,\delta,\{x^i\}_{i=0}^{n-1},\{\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\gamma}\}_{i=0}^{l}, \{\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\delta}\}_{i=l+1}^{m}, \{\frac{x^it(x)}{\delta}\}_{i=0}^{n-2}), \vec{\sigma}_2=(\beta,\gamma,\delta,\{x^i\}_{i=0}^{n-1}) σ 1​=(α,β,γ,δ,{xi}i=0n−1​,{γβui​(x)+αvi​(x)+wi​(x)​}i=0l​,{δβui​(x)+αvi​(x)+wi​(x)​}i=l+1m​,{δxit(x)​}i=0n−2​),σ 2​=(β,γ,δ,{xi}i=0n−1​) 相关结构体有：

/// This is our assembly structure that we'll use to synthesize the
/// circuit into a QAP.
struct KeypairAssembly {
    num_inputs: usize,
    num_aux: usize,
    num_constraints: usize,
    at_inputs: Vec,
    bt_inputs: Vec,
    ct_inputs: Vec,
    at_aux: Vec,
    bt_aux: Vec,
    ct_aux: Vec,
}

alloc //构建私有变量
alloc_input //构建公有变量
enforce //约束`A` * `B` =`C`
synthesize //用于将circuit 合成为 rank-1 quadratic constraint system

其中verifier key中的 i c ic ic即为： i c = { [ β u i ( x ) + α v i ( x ) + w i ( x ) γ ] 1 } i = 0 l ic = \{[\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\gamma}]_1\}_{i=0}^{l} ic={[γβui​(x)+αvi​(x)+wi​(x)​]1​}i=0l​

• prover.rs：生成proof。 π ← P r o v e ( R , σ ⃗ , a 1 , ⋯   , a m ) \pi\leftarrow Prove(R,\vec{\sigma}, a_1,\cdots,a_m) π←Prove(R,σ ,a1​,⋯,am​)：选择 r , s ← F r,s\leftarrow \mathbb{F} r,s←F，计算 π ⃗ = ( [ A ] 1 , [ C ] 1 , [ B ] 2 ) \vec{\pi}=([A]_1,[C]_1,[B]_2) π =([A]1​,[C]1​,[B]2​)，其中： A = α + ∑ i = 0 m a i u i ( x ) + r δ A=\alpha+\sum_{i=0}^{m}a_iu_i(x)+r\delta A=α+∑i=0m​ai​ui​(x)+rδ B = β + ∑ i = 0 m a i v i ( x ) + s δ B=\beta+\sum_{i=0}^{m}a_iv_i(x)+s\delta B=β+∑i=0m​ai​vi​(x)+sδ C = ∑ i = l + 1 m a i ( β u i ( x ) + α v i ( x ) + w i ( x ) ) + h ( x ) t ( x ) δ + A s + r B − r s δ C=\frac{\sum_{i=l+1}^{m}a_i(\beta u_i(x)+\alpha v_i(x)+w_i(x))+h(x)t(x)}{\delta}+As+rB-rs\delta C=δ∑i=l+1m​ai​(βui​(x)+αvi​(x)+wi​(x))+h(x)t(x)​+As+rB−rsδ 相关结构体有：

struct ProvingAssignment {
    // Density of queries
    a_aux_density: DensityTracker,
    b_input_density: DensityTracker,
    b_aux_density: DensityTracker,

    // Evaluations of A, B, C polynomials
    a: Vec,
    b: Vec,
    c: Vec,

    // Assignments of variables
    input_assignment: Vec,
    aux_assignment: Vec,
}

pub struct Proof {
    pub a: E::G1Affine,
    pub b: E::G2Affine,
    pub c: E::G1Affine,
}

• verifier.rs：验证proof。 0 / 1 ← V f y ( R , σ ⃗ , a 1 , ⋯   , a l , π ⃗ ) 0/1\leftarrow Vfy(R,\vec{\sigma}, a_1,\cdots,a_l, \vec{\pi}) 0/1←Vfy(R,σ ,a1​,⋯,al​,π )：解析 π ⃗ = ( [ A ] 1 , [ C ] 1 , [ B ] 2 ) ∈ G 1 2 × G 2 \vec{\pi}=([A]_1,[C]_1,[B]_2)\in\mathbb{G}_1^2\times \mathbb{G}_2 π =([A]1​,[C]1​,[B]2​)∈G12​×G2​，对应的test为： [ A ] 1 ⋅ [ B ] 2 = [ α ] 1 ⋅ [ β ] 2 + ∑ i = 0 l a i [ ( β u i ( x ) + α v i ( x ) + w i ( x ) ) γ ] 1 ⋅ [ γ ] 2 + [ C ] 1 ⋅ [ δ ] 2 [A]_1\cdot [B]_2= [\alpha]_1 \cdot [\beta]_2 + \sum_{i=0}^{l}a_i[\frac{(\beta u_i(x)+\alpha v_i(x)+w_i(x))}{\gamma}]_1\cdot [\gamma]_2 + [C]_1\cdot [\delta]_2 [A]1​⋅[B]2​=[α]1​⋅[β]2​+∑i=0l​ai​[γ(βui​(x)+αvi​(x)+wi​(x))​]1​⋅[γ]2​+[C]1​⋅[δ]2​ 若以上test成立，则accept the proof。 会生成PreparedVerifyingKey：

pub fn prepare_verifying_key(vk: &VerifyingKey) -> PreparedVerifyingKey {
    let gamma = vk.gamma_g2.neg();
    let delta = vk.delta_g2.neg();

    PreparedVerifyingKey {
        alpha_g1_beta_g2: E::pairing(&vk.alpha_g1, &vk.beta_g2),
        neg_gamma_g2: gamma.into(),
        neg_delta_g2: delta.into(),
        ic: vk.ic.clone(),
    }
}

    // The original verification equation is:
    // A * B = alpha * beta + inputs * gamma + C * delta
    // ... however, we rearrange it so that it is:
    // A * B - inputs * gamma - C * delta = alpha * beta
    // or equivalently:
    // A * B + inputs * (-gamma) + C * (-delta) = alpha * beta
    // which allows us to do a single final exponentiation.

2.2 gadgets

1）boolean.rs：

/// Represents a variable in the constraint system which is guaranteed
/// to be either zero or one.
#[derive(Clone)]
pub struct AllocatedBit {
    variable: Variable,
    value: Option,
}

对AllocatedBit 实现了：

• conditionally boolean bit alloc约束
• 普通的boolean bit约束
• bit xor约束
• bit and约束
• bit and not约束
• bit nor约束
• u64_into_boolean_vec_le将u64转为64位little endian bit vec，同时对每个bit做了 普通boolean bit约束；
• field_into_boolean_vec_le将PrimeFieldBits转换为F::NUM_BITS位little endian bit vec，同时对每个bit做了 普通boolean bit约束。

Boolean的枚举类型有：

/// This is a boolean value which may be either a constant or
/// an interpretation of an `AllocatedBit`.
#[derive(Clone)]
pub enum Boolean {
    /// Existential view of the boolean variable
    Is(AllocatedBit),
    /// Negated view of the boolean variable
    Not(AllocatedBit),
    /// Constant (not an allocated variable)
    Constant(bool),
}
pub fn get_value(&self) -> Option {
        match *self {
            Boolean::Constant(c) => Some(c),
            Boolean::Is(ref v) => v.get_value(),
            Boolean::Not(ref v) => v.get_value().map(|b| !b),
        }
    }

 pub fn lc(
        &self,
        one: Variable,
        coeff: Scalar,
    ) -> LinearCombination {
        match *self {
            Boolean::Constant(c) => {
                if c {
                    LinearCombination::::zero() + (coeff, one)
                } else {
                    LinearCombination::::zero()
                }
            }
            Boolean::Is(ref v) => LinearCombination::::zero() + (coeff, v.get_variable()),
            Boolean::Not(ref v) => {
                LinearCombination::::zero() + (coeff, one) - (coeff, v.get_variable())
            }
        }
    }

对Boolean枚举，实现了：

• equal 约束
• not 运算
• xor 运算及约束
• and 运算及约束
• (a and b) xor ((not a) and c) 运算及约束（sha256_ch）
• (a and b) xor (a and c) xor (b and c) 运算及约束 （sha256_maj）

2）multieq.rs：

pub struct MultiEq {
    cs: CS,
    ops: usize,
    bits_used: usize,
    lhs: LinearCombination,
    rhs: LinearCombination, // vec
}

对MultiEq结构体，实现了：

• equal 约束。其中若Scalar::CAPACITY as usize) Result ...... /// Convert the allocated number into its little-endian representation. /// Note that this does not strongly enforce that the commitment is /// "in the field." pub fn to_bits_le(&self, mut cs: CS) -> Result ......

  在AllocatedBit和Boolean的基础上，对AllocatedNum实现了：

  • a*b=ab 约束；
  • a*a=aa 约束；
  • a不为零约束，即存在 1 / a 1/a 1/a，使得 a ∗ 1 / a = 1 a*1/a=1 a∗1/a=1成立；
  • conditionally_reverse约束，即：

  	 /// Takes two allocated numbers (a, b) and returns
      /// (b, a) if the condition is true, and (a, b)
      /// otherwise.
  

  可将AllocatedNum 转换为 Num：

  pub struct Num {
      value: Option,
      lc: LinearCombination,
  }
  

  4）multipack.rs： 提供了：

  • pack_into_inputs：Takes a sequence of booleans and exposes them as compact public inputs。
  • bytes_to_bits：将bytes转换为bits。
  • bytes_to_bits_le：将bytes转换为little-endian bits。
  • compute_multipacking：将bool bits转换为Scalar vec。

  5）uint32.rs：

  /// Represents an interpretation of 32 `Boolean` objects as an
  /// unsigned integer.
  #[derive(Clone)]
  pub struct UInt32 {
      // Least significant bit first
      bits: Vec,
      value: Option,
  }
  

  对UInt32实现了：

  • 自定义的 triop 三变量运算。
  • (a and b) xor (a and c) xor (b and c) 运算及约束 （sha256_maj）。
  • (a and b) xor ((not a) and c) 运算及约束（sha256_ch）。
  • 两变量xor运算及约束。
  • 多个UInt32变量求和取模运算及约束。

  6）sha256.rs： 为Circuits for the SHA-256 hash function and its internal compression。

  7）blake2s.rs： 为 The BLAKE2s hash function with personalization support.

  8）lookup.rs： 为Window table lookup gadgets。

  9）test/mod.rs： 为测试目的定义了constraint system。

  2.3 mimc

  https://github.com/zkcrypto/bellman/tree/main/tests/common/mod.rs中： 基于BLS12-381，实现了Albrecht等人 2016年论文《MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity》中的LongsightF322p3算法。

  相应的测试用例见：https://github.com/zkcrypto/bellman/blob/main/tests/mimc.rs