halo2-baseの話

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

# halo2-baseを使うと

ガス代が安くなります！

# このトークでは

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

# zkp、仕組みを掴むだけでは使いこなせない！
# 理論家がとりあえず無視しているが、実際に業務で使おうとしたときに問題になることがいろいろある
# 例: Plonkのarithmetization
![](https://paper-attachments.dropboxusercontent.com/s_34097555201DB3C2BA9F89A7D8D8F5E11B57984CA3C06C817364E1E250399943_1701509597211_image.png)

![](https://paper-attachments.dropboxusercontent.com/s_34097555201DB3C2BA9F89A7D8D8F5E11B57984CA3C06C817364E1E250399943_1701509898504_image.png)


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

![](https://paper-attachments.dropboxusercontent.com/s_34097555201DB3C2BA9F89A7D8D8F5E11B57984CA3C06C817364E1E250399943_1701523407954_Screenshot+from+2023-12-02+22-23-08.png)

![](https://paper-attachments.dropboxusercontent.com/s_34097555201DB3C2BA9F89A7D8D8F5E11B57984CA3C06C817364E1E250399943_1701523629454_Screenshot+from+2023-12-02+22-24-14.png)

# ガス代が高すぎる

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

# 困った

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

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

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

# 微妙に違う方法でArithmetizeする
https://github.com/axiom-crypto/halo2-lib/blob/400122a6cf074783d0e5ee904a711e75ddfff3d4/halo2-base/src/gates/flex_gate/mod.rs#L30C1-L37C4

    /// # 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])
    }
![](https://paper-attachments.dropboxusercontent.com/s_34097555201DB3C2BA9F89A7D8D8F5E11B57984CA3C06C817364E1E250399943_1701523608608_00ae77f4df526d989fd2003d4d00f9c3.jpg)


鶴: 63匹
亀: 37匹

## Standard Plonk
赤がプライベートな値。青がパブリックな値。線が copy constraint。
![](https://paper-attachments.dropboxusercontent.com/s_34097555201DB3C2BA9F89A7D8D8F5E11B57984CA3C06C817364E1E250399943_1701622642423_originalplonk.svg)
either 足し算 or 掛け算 を、横に制約している。足し算フラグを立てるためだけの多項式 $q_L, q_R$ や、掛け算フラグを立てるためだけの多項式 $q_M$ にコミットする必要があり、vkのサイズが増えてしまう

## halo2-base
![](https://paper-attachments.dropboxusercontent.com/s_34097555201DB3C2BA9F89A7D8D8F5E11B57984CA3C06C817364E1E250399943_1701622361395_halo2base1.svg)

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])
    }
![](https://paper-attachments.dropboxusercontent.com/s_34097555201DB3C2BA9F89A7D8D8F5E11B57984CA3C06C817364E1E250399943_1701622372088_halo2base2.svg)

![](https://paper-attachments.dropboxusercontent.com/s_34097555201DB3C2BA9F89A7D8D8F5E11B57984CA3C06C817364E1E250399943_1701622380674_halo2base3.svg)



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

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](https://twitter.com/chokermaxx)