ZCash Halo2 代码解析

1. 引言

针对代码库：

https://github.com/zcash/halo2

其中：

src/arithmetic.rs：定义了多种multiexp、fft、poly evaluation、inner product、 q ( x ) = f ( x ) x − b q(x)=\frac{f(x)}{x-b} q(x)=x−bf(x)多项式求商、函数并行运行parallelize()、 l o g 2 log_2 log2 以及 lagrange插值运算。
src/poly.rs：定义的为单变量多项式：【有2种表示方式：Polynomial为系数表示；Polynomial为Lagrange点值表示。】

/// Represents a univariate polynomial defined over a field and a particular 
/// basis.
pub struct Polynomial {
    values: Vec,
    _marker: PhantomData, 
}

rotate用于将Lagrange点值表示的值左右移动， L ( X ) , L ( ω X ) , L ( ω − 1 X ) L(X),L(\omega X), L(\omega^{-1}X) L(X),L(ωX),L(ω−1X) 具有的特征为：

	let poly_rotated_cur = poly.rotate(Rotation::cur());
    let poly_rotated_next = poly.rotate(Rotation::next());
    let poly_rotated_prev = poly.rotate(Rotation::prev());

    let poly = domain.lagrange_to_coeff(poly);
    let poly_rotated_cur = domain.lagrange_to_coeff(poly_rotated_cur);
    let poly_rotated_next = domain.lagrange_to_coeff(poly_rotated_next);
    let poly_rotated_prev = domain.lagrange_to_coeff(poly_rotated_prev);

    let x = Scalar::rand();

    assert_eq!(
        eval_polynomial(&poly[..], x),
        eval_polynomial(&poly_rotated_cur[..], x)
    );
    assert_eq!(
        eval_polynomial(&poly[..], x * domain.omega),
        eval_polynomial(&poly_rotated_next[..], x)
    );
    assert_eq!(
        eval_polynomial(&poly[..], x * domain.omega_inv),
        eval_polynomial(&poly_rotated_prev[..], x)
    );

2. polynomial commitment（系数表示法）

src/poly/commitment/msm.rs：实现的为multiscalar multiplication运算。
src/poly/domain.rs：主要包含了EvaluationDomain，用于表示在scalar field域内的各种多项式运算。如计算Lagrange basis polynomial、多项式的点值与系数表示之间的相互转换、
src/poly/commitment.rs：定义了polynomial commitment scheme的公共参数：

pub struct Params {
    pub(crate) k: u32,
    pub(crate) n: u64,
    pub(crate) g: Vec, // 对以系数表示的多项式进行commit
    pub(crate) g_lagrange: Vec, //对以点值表示的多项式进行commit
    pub(crate) h: C,
    pub(crate) u: C,
}

其中定义了2种commitment实现，分别是对以系数表示的多项式的commit方法，和经FFT转换为点值表示的多项式的commit_lagrange方法，二者的实际commit效果是一样的：

assert_eq!(params.commit(&b, alpha), params.commit_lagrange(&a, alpha));

同时，实现了从buffer读写Params参数的接口。

2.1 单点polynomial commitment scheme（系数表示法）

可参考：

Halo2 学习笔记——背景资料之Polynomial commitment（6）
Halo2 学习笔记——设计之Proving system之Inner product argument（6）

具体见src/poly/commitment/*.rs中，相应的测试用例见src/poly/commitment.rs中的test_opening_proof()。

其中：

create_proof()过程对应为 Halo2 学习笔记——设计之Proving system之Inner product argument（6）中的第2节的 P C D L . O p e n PC_{DL}.Open PCDL.Open算法。
verify_proof()过程对应为Halo2 学习笔记——设计之Proving system之Inner product argument（6）中的第2节的 P C D L . C h e c k PC_{DL}.Check PCDL.Check算法，但是相应的 ∏ i = 1 k ( u i + u i − 1 x 2 i − 1 ) \prod_{i=1}^{k}(u_i+u_i^{-1}x^{2^i-1}) ∏i=1k(ui+ui−1x2i−1)由Verifier通过compute_b()函数计算得出，而未进行分摊。若使用compute_s()函数计算 g ( X ) = ∏ i = 1 k ( u i + u i − 1 X 2 i − 1 ) g(X)=\prod_{i=1}^{k}(u_i+u_i^{-1}X^{2^i-1}) g(X)=∏i=1k(ui+ui−1X2i−1)多项式的系数，并通过compute_g()函数计算commtiment值 G = c o m m i t ( g ( X ) ) + H G=commit(g(X))+H G=commit(g(X))+H。具体体现在Guard结构体中。

2.2 多点polynomial commitment scheme（系数表示法）

multiopen对应的测试用例参见src/poly/multiopen.rs中的test_roundtrip()。

可参考：

Halo2 学习笔记——设计之Proving system之Multipoint opening argument（5）
Halo2 学习笔记——设计之Proving system之Vanishing argument（4）
Plonk代码解析第2.3节“batch open different polynomials at different points”
Efficient polynomial commitment schemes for multiple points and polynomials学习笔记中的第3和第4节

其中src/poly/multiopen.rs中的 x 1 , x 2 , x 3 , x 4 x_1,x_2,x_3,x_4 x1,x2,x3,x4 challenge参数的含义参考 Halo2 学习笔记——设计之Proving system之Multipoint opening argument（5）第2节“Optimization steps”：

x 1 x_1 x1 challenge：用于compress openings at the same point sets together。
x 2 x_2 x2 challenge：用于keep the multi-point quotient polynomial terms linearly independent。
x 3 x_3 x3 challenge：为challenge open point。
x 4 x_4 x4 challenge：用于将分组后的多个多项式 + 组合后的一个quotient多项式组合在一起。即用于Collapse the openings of the various remaining polynomials at x 3 x_3 x3 together。

通过以上challenge，即可将multi-point open转换为单个多项式，然后直接调用单点Polynomial commitment scheme进行证明即可。

/// A polynomial query at a point
#[derive(Debug, Clone)]
pub struct ProverQuery { // 为Prover端输入
    /// point at which polynomial is queried
    pub point: C::Scalar,
    /// coefficients of polynomial
    pub poly: &'a Polynomial,
    /// blinding factor of polynomial
    pub blind: commitment::Blind,
}

/// A polynomial query at a point
#[derive(Debug, Clone)]
pub struct VerifierQuery { // 为Verifier端输入
    /// point at which polynomial is queried
    point: C::Scalar,
    /// commitment to polynomial
    commitment: CommitmentReference, // 有2种类型，Commitment或MSM。
    /// evaluation of polynomial at query point
    eval: C::Scalar,
}

3 Plonk lookup argument（Lagrange点值表示法）

可参考：

Halo2 学习笔记——设计之Proving system之Lookup argument（1）
PLOOKUP代码解析

具体代码参见：src/plonk/lookup.rs，相应的测试用例见tests/plonk_api.rs中的plonk_api()。

#[derive(Clone, Debug)]
pub(crate) struct Argument {
    pub input_expressions: Vec,
    pub table_expressions: Vec,
}

4. Halo2 circuit

expression：

/// Low-degree expression representing an identity that must hold over the committed columns.
#[derive(Clone, Debug)]
pub enum Expression {
    /// This is a constant polynomial
    Constant(F),
    /// This is a virtual selector
    Selector(Selector),
    /// This is a fixed column queried at a certain relative location
    Fixed {
        /// Query index
        query_index: usize,
        /// Column index
        column_index: usize,
        /// Rotation of this query
        rotation: Rotation,
    },
    /// This is an advice (witness) column queried at a certain relative location
    Advice {
        /// Query index
        query_index: usize,
        /// Column index
        column_index: usize,
        /// Rotation of this query
        rotation: Rotation,
    },
    /// This is an instance (external) column queried at a certain relative location
    Instance {
        /// Query index
        query_index: usize,
        /// Column index
        column_index: usize,
        /// Rotation of this query
        rotation: Rotation,
    },
    /// This is a negated polynomial
    Negated(Box),
    /// This is the sum of two polynomials
    Sum(Box, Box),
    /// This is the product of two polynomials
    Product(Box, Box),
    /// This is a scaled polynomial
    Scaled(Box, F),
}

pub struct MockProver {
    n: u32,
    cs: ConstraintSystem,

    /// The regions in the circuit.
    regions: Vec,
    /// The current region being assigned to. Will be `None` after the circuit has been
    /// synthesized.
    current_region: Option,

    // The fixed cells in the circuit, arranged as [column][row].
    fixed: Vec,
    // The advice cells in the circuit, arranged as [column][row].
    advice: Vec,
    // The instance cells in the circuit, arranged as [column][row].
    instance: Vec,

    selectors: Vec,

    permutation: permutation::keygen::Assembly,

    // A range of available rows for assignment and copies.
    usable_rows: Range,
}

/// The value of a particular cell within the circuit.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum CellValue {
    // An unassigned cell.
    Unassigned,
    // A cell that has been assigned a value.
    Assigned(F),
    // A unique poisoned cell.
    Poison(usize),
}

4.1 Constraint System

pub struct ConstraintSystem {
    pub(crate) num_fixed_columns: usize,
    pub(crate) num_advice_columns: usize,
    pub(crate) num_instance_columns: usize,
    pub(crate) num_selectors: usize,
    pub(crate) selector_map: Vec,
    pub(crate) gates: Vec,
    pub(crate) advice_queries: Vec,
    // Contains an integer for each advice column
    // identifying how many distinct queries it has
    // so far; should be same length as num_advice_columns.
    num_advice_queries: Vec,
    pub(crate) instance_queries: Vec,
    pub(crate) fixed_queries: Vec,

    // Permutation argument for performing equality constraints
    pub(crate) permutation: permutation::Argument,

    // Vector of lookup arguments, where each corresponds to a sequence of
    // input expressions and a sequence of table expressions involved in the lookup.
    pub(crate) lookups: Vec,

    // Vector of fixed columns, which can be used to store constant values
    // that are copied into advice columns.
    pub(crate) constants: Vec,

    pub(crate) minimum_degree: Option,
}

pub struct Rotation(pub i32); // 0表示当前行，1表示下一行，-1表示前一行

// Permutation argument
pub(crate) struct Argument {
    /// A sequence of columns involved in the argument.
    columns: Vec,
}

// Lookup argument
pub(crate) struct Argument {
    pub input_expressions: Vec,
    pub table_expressions: Vec,
}

/// Low-degree expression representing an identity that must hold over the committed columns.
#[derive(Clone, Debug)]
pub enum Expression {
    /// This is a constant polynomial
    Constant(F),
    /// This is a virtual selector
    Selector(Selector),
    /// This is a fixed column queried at a certain relative location
    Fixed {
        /// Query index
        query_index: usize,
        /// Column index
        column_index: usize,
        /// Rotation of this query
        rotation: Rotation,
    },
    /// This is an advice (witness) column queried at a certain relative location
    Advice {
        /// Query index
        query_index: usize,
        /// Column index
        column_index: usize,
        /// Rotation of this query
        rotation: Rotation,
    },
    /// This is an instance (external) column queried at a certain relative location
    Instance {
        /// Query index
        query_index: usize,
        /// Column index
        column_index: usize,
        /// Rotation of this query
        rotation: Rotation,
    },
    /// This is a negated polynomial
    Negated(Box),
    /// This is the sum of two polynomials
    Sum(Box, Box),
    /// This is the product of two polynomials
    Product(Box, Box),
    /// This is a scaled polynomial
    Scaled(Box, F),
}

4.2 Region

struct Region {
    /// The name of the region. Not required to be unique.
    name: String,
    /// The row that this region starts on, if known.
    start: Option,
    /// The selectors that have been enabled in this region. All other selectors are by
    /// construction not enabled.
    enabled_selectors: HashMap,
    /// The cells assigned in this region. We store this as a `Vec` so that if any cells
    /// are double-assigned, they will be visibly darker.
    cells: Vec,
}

pub struct Selector(pub(crate) usize, bool);

pub struct Column { //其中ColumnType为trait。
    index: usize,
    column_type: C,
}

pub enum Any {
    /// An Advice variant
    Advice,
    /// A Fixed variant
    Fixed,
    /// An Instance variant
    Instance,
}

4.3 permutation keygen Assembly

pub(crate) struct Assembly {
    columns: Vec,
    pub(crate) mapping: Vec,
    aux: Vec,
    sizes: Vec,
}

5. 要点

对于自定义的MyCircuit，需自己：

在configure() 函数中配置相应的 advice（private）变量、instance（public）变量、constant（fixed and private）变量。
在synthesize() 函数中设置相应的 circuit逻辑运算。

ZCash Halo2 代码解析

最近更新

热门博客

[ 申请 ]友情链接：