halo2-baseの話

12/3のゼロ知識証明ミートアップで登壇しました。その時の発表資料。

halo2-baseを使うと

ガス代が安くなります！

このトークでは

halo2-baseを使ってサーキットを最適化していきます

zkp、仕組みを掴むだけでは使いこなせない！

理論家がとりあえず無視しているが、実際に業務で使おうとしたときに問題になることがいろいろある

例: Plonkのarithmetization

カラムの数が多いと、コミットしなければならない多項式の数が増える → vkのサイズが増える → 検証コントラクトのサイズが大きくなる。

ガス代が高すぎる

検証しなければならないオープニングプルーフの数が多すぎる

困った

どうにかして、同じことの制約を、少ない数のカラムで表現する → コミットする必要のある多項式の数が減る → 検証しなければならないオープニングプルーフの数が減る → ガス代が安くなる

どうやってカラムの数を減らす？

halo2-baseの仕組み: 足し算するか掛け算するかの切り替えを、セレクターカラムを使わずに実装する。代わりにcopy constraintを使って切り替える。

微妙に違う方法でArithmetizeする

/// # Vertical Gate Strategy:
/// `q_0 * (a + b * c - d) = 0`
/// where
/// * `a = value[0], b = value[1], c = value[2], d = value[3]`
/// * `q = q_enable[0]`
/// * `q` is either 0 or 1 so this is just a simple selector
/// We chose `a + b * c` instead of `a * b + c` to allow "chaining" of gates, i.e., the output of one gate because `a` in the next gate.


/// Constrains and returns `a + b * 1 = out`.
///
/// Defines a vertical gate of form | a | b | 1 | a + b | where (a + b) = out.
/// * `ctx`: [Context] to add the constraints to
/// * `a`: [QuantumCell] value
/// * `b`: [QuantumCell] value to add to 'a`
fn add(
    &self,
    ctx: &mut Context<F>,
    a: impl Into<QuantumCell<F>>,
    b: impl Into<QuantumCell<F>>,
) -> AssignedValue<F> {
    let a = a.into();
    let b = b.into();
    let out_val = *a.value() + b.value();
    ctx.assign_region_last([a, b, Constant(F::ONE), Witness(out_val)], [0])
}


/// Constrains and returns  `0 + a * b = out`.
///
/// Defines a vertical gate of form | 0 | a | b | a * b |, where (a * b) = out.
/// * `ctx`: [Context] to add the constraints to
/// * `a`: [QuantumCell] value
/// * `b`: [QuantumCell] value to multiply 'a' by
fn mul(
    &self,
    ctx: &mut Context<F>,
    a: impl Into<QuantumCell<F>>,
    b: impl Into<QuantumCell<F>>,
) -> AssignedValue<F> {
    let a = a.into();
    let b = b.into();
    let out_val = *a.value() * b.value();
    ctx.assign_region_last([Constant(F::ZERO), a, b, Witness(out_val)], [0])
}

鶴: 63匹
亀: 37匹

Standard Plonk

赤がプライベートな値。青がパブリックな値。線が copy constraint。

either 足し算 or 掛け算 を、横に制約している。足し算フラグを立てるためだけの多項式 $q_L, q_R$ や、掛け算フラグを立てるためだけの多項式 $q_M$ にコミットする必要があり、vkのサイズが増えてしまう

halo2-base

a + b * c - d = 0 を、縦に制約している。フラグを立てるための多項式が要らなくなる。vkのサイズが小さくなる。
掛け算のみを制約したい時には、足す値を0にすることでごまかす。足し算のみを制約したい時は、掛ける値を1にすることでごまかす。

/// Constrains and returns  `a * b + c = out`.
///
/// Defines a vertical gate of form | c | a | b | a * b + c |, where (a * b + c) = out.
/// * `ctx`: [Context] to add the constraints to
/// * `a`: [QuantumCell] value
/// * `b`: [QuantumCell] value to multiply 'a' by
/// * `c`: [QuantumCell] value to add to 'a * b'
fn mul_add(
    &self,
    ctx: &mut Context<F>,
    a: impl Into<QuantumCell<F>>,
    b: impl Into<QuantumCell<F>>,
    c: impl Into<QuantumCell<F>>,
) -> AssignedValue<F> {
    let a = a.into();
    let b = b.into();
    let c = c.into();
    let out_val = *a.value() * b.value() + c.value();
    ctx.assign_region_last([c, a, b, Witness(out_val)], [0])
}

検証コントラクトをデプロイできるようになったね

vkのサイズ: 458bytes!
コントラクトのサイズ: 15.6KB

ガス代が安くなったね

318819gas

プルーフが小さくなったね

プルーフサイズ: 992bytes
Groth16が288bytesなので、まあ3倍ぐらい

プルーフ生成に必要なRAMの量が減ったね

before: 8columns x 6rows = 48cells
after: 5columns x 6rows = 30cells

まとめ

R1CSと違い、Plonkベースのプルーフシステムでは、同じことを制約する方法が複数ある。
columnsが増えると、検証に必要なガス代が増える。
cellsが増えると、プルーフ生成に必要なRAMが増える。
rowsが増えると、プルーフ生成に必要な時間が増える。
要件に応じて、何を求めて最適化するのかを決める。

所信表明

サーキット最適化芸人として生きていこうと思います
Twitter: @chokermaxx