Zenn
Open5

Halo2のproofをEVMで検証する

zkp
halo2
zksnark
nunonuno

Halo2のバージョンについて

Halo2には大きく分けて2種類のバージョンがある。

  1. Zcashのオリジナル版
  2. PSE/Scroll版

1は楕円曲線にpasta curve, commitment schemeにIPA(inner product argument)を使うが、対応するprecompileがEVMに無いため、現実的なgas代でEVMでproof検証をすることができない。

2は楕円曲線にBn254, commitment schemeにKZG commitmentを用いることで、EVMで効率的にproof検証ができる。

このスクラップではPSEのsnark-veriferを使ってHalo2のproofをEVMで検証する方法を紹介する。

https://github.com/privacy-scaling-explorations/snark-verifier

nunonuno

上記のレポジトリの中にはsnark-verifier/examples/evm-verifier.rsファイルがある。

内容は次の通り。

evm-verifier.rs
use halo2_curves::bn256::{Bn256, Fq, Fr, G1Affine};
use halo2_proofs::{
    circuit::{Layouter, SimpleFloorPlanner, Value},
    dev::MockProver,
    plonk::{
        create_proof, keygen_pk, keygen_vk, verify_proof, Advice, Circuit, Column,
        ConstraintSystem, Error, Fixed, Instance, ProvingKey, VerifyingKey,
    },
    poly::{
        commitment::{Params, ParamsProver},
        kzg::{
            commitment::{KZGCommitmentScheme, ParamsKZG},
            multiopen::{ProverGWC, VerifierGWC},
            strategy::AccumulatorStrategy,
        },
        Rotation, VerificationStrategy,
    },
    transcript::{TranscriptReadBuffer, TranscriptWriterBuffer},
};
use itertools::Itertools;
use rand::{rngs::OsRng, RngCore};
use snark_verifier::{
    loader::evm::{self, encode_calldata, Address, EvmLoader, ExecutorBuilder},
    pcs::kzg::{Gwc19, KzgAs},
    system::halo2::{compile, transcript::evm::EvmTranscript, Config},
    verifier::{self, SnarkVerifier},
};
use std::rc::Rc;

type PlonkVerifier = verifier::plonk::PlonkVerifier<KzgAs<Bn256, Gwc19>>;

#[derive(Clone, Copy)]
struct StandardPlonkConfig {
    a: Column<Advice>,
    b: Column<Advice>,
    c: Column<Advice>,
    q_a: Column<Fixed>,
    q_b: Column<Fixed>,
    q_c: Column<Fixed>,
    q_ab: Column<Fixed>,
    constant: Column<Fixed>,
    #[allow(dead_code)]
    instance: Column<Instance>,
}

impl StandardPlonkConfig {
    fn configure(meta: &mut ConstraintSystem<Fr>) -> Self {
        let [a, b, c] = [(); 3].map(|_| meta.advice_column());
        let [q_a, q_b, q_c, q_ab, constant] = [(); 5].map(|_| meta.fixed_column());
        let instance = meta.instance_column();

        [a, b, c].map(|column| meta.enable_equality(column));

        meta.create_gate(
            "q_a·a + q_b·b + q_c·c + q_ab·a·b + constant + instance = 0",
            |meta| {
                let [a, b, c] = [a, b, c].map(|column| meta.query_advice(column, Rotation::cur()));
                let [q_a, q_b, q_c, q_ab, constant] = [q_a, q_b, q_c, q_ab, constant]
                    .map(|column| meta.query_fixed(column, Rotation::cur()));
                let instance = meta.query_instance(instance, Rotation::cur());
                Some(
                    q_a * a.clone()
                        + q_b * b.clone()
                        + q_c * c
                        + q_ab * a * b
                        + constant
                        + instance,
                )
            },
        );

        StandardPlonkConfig {
            a,
            b,
            c,
            q_a,
            q_b,
            q_c,
            q_ab,
            constant,
            instance,
        }
    }
}

#[derive(Clone, Default)]
struct StandardPlonk(Fr);

impl StandardPlonk {
    fn rand<R: RngCore>(mut rng: R) -> Self {
        Self(Fr::from(rng.next_u32() as u64))
    }

    fn num_instance() -> Vec<usize> {
        vec![1]
    }

    fn instances(&self) -> Vec<Vec<Fr>> {
        vec![vec![self.0]]
    }
}

impl Circuit<Fr> for StandardPlonk {
    type Config = StandardPlonkConfig;
    type FloorPlanner = SimpleFloorPlanner;

    fn without_witnesses(&self) -> Self {
        Self::default()
    }

    fn configure(meta: &mut ConstraintSystem<Fr>) -> Self::Config {
        meta.set_minimum_degree(4);
        StandardPlonkConfig::configure(meta)
    }

    fn synthesize(
        &self,
        config: Self::Config,
        mut layouter: impl Layouter<Fr>,
    ) -> Result<(), Error> {
        layouter.assign_region(
            || "",
            |mut region| {
                region.assign_advice(|| "", config.a, 0, || Value::known(self.0))?;
                region.assign_fixed(|| "", config.q_a, 0, || Value::known(-Fr::one()))?;

                region.assign_advice(|| "", config.a, 1, || Value::known(-Fr::from(5)))?;
                for (idx, column) in (1..).zip([
                    config.q_a,
                    config.q_b,
                    config.q_c,
                    config.q_ab,
                    config.constant,
                ]) {
                    region.assign_fixed(|| "", column, 1, || Value::known(Fr::from(idx)))?;
                }

                let a = region.assign_advice(|| "", config.a, 2, || Value::known(Fr::one()))?;
                a.copy_advice(|| "", &mut region, config.b, 3)?;
                a.copy_advice(|| "", &mut region, config.c, 4)?;

                Ok(())
            },
        )
    }
}

fn gen_srs(k: u32) -> ParamsKZG<Bn256> {
    ParamsKZG::<Bn256>::setup(k, OsRng)
}

fn gen_pk<C: Circuit<Fr>>(params: &ParamsKZG<Bn256>, circuit: &C) -> ProvingKey<G1Affine> {
    let vk = keygen_vk(params, circuit).unwrap();
    keygen_pk(params, vk, circuit).unwrap()
}

fn gen_proof<C: Circuit<Fr>>(
    params: &ParamsKZG<Bn256>,
    pk: &ProvingKey<G1Affine>,
    circuit: C,
    instances: Vec<Vec<Fr>>,
) -> Vec<u8> {
    MockProver::run(params.k(), &circuit, instances.clone())
        .unwrap()
        .assert_satisfied();

    let instances = instances
        .iter()
        .map(|instances| instances.as_slice())
        .collect_vec();
    let proof = {
        let mut transcript = TranscriptWriterBuffer::<_, G1Affine, _>::init(Vec::new());
        create_proof::<KZGCommitmentScheme<Bn256>, ProverGWC<_>, _, _, EvmTranscript<_, _, _, _>, _>(
            params,
            pk,
            &[circuit],
            &[instances.as_slice()],
            OsRng,
            &mut transcript,
        )
        .unwrap();
        transcript.finalize()
    };

    let accept = {
        let mut transcript = TranscriptReadBuffer::<_, G1Affine, _>::init(proof.as_slice());
        VerificationStrategy::<_, VerifierGWC<_>>::finalize(
            verify_proof::<_, VerifierGWC<_>, _, EvmTranscript<_, _, _, _>, _>(
                params.verifier_params(),
                pk.get_vk(),
                AccumulatorStrategy::new(params.verifier_params()),
                &[instances.as_slice()],
                &mut transcript,
            )
            .unwrap(),
        )
    };
    assert!(accept);

    proof
}

fn gen_evm_verifier(
    params: &ParamsKZG<Bn256>,
    vk: &VerifyingKey<G1Affine>,
    num_instance: Vec<usize>,
) -> Vec<u8> {
    let protocol = compile(
        params,
        vk,
        Config::kzg().with_num_instance(num_instance.clone()),
    );
    let vk = (params.get_g()[0], params.g2(), params.s_g2()).into();

    let loader = EvmLoader::new::<Fq, Fr>();
    let protocol = protocol.loaded(&loader);
    let mut transcript = EvmTranscript::<_, Rc<EvmLoader>, _, _>::new(&loader);

    let instances = transcript.load_instances(num_instance);
    let proof = PlonkVerifier::read_proof(&vk, &protocol, &instances, &mut transcript).unwrap();
    PlonkVerifier::verify(&vk, &protocol, &instances, &proof).unwrap();

    evm::compile_yul(&loader.yul_code())
}

fn evm_verify(deployment_code: Vec<u8>, instances: Vec<Vec<Fr>>, proof: Vec<u8>) {
    let calldata = encode_calldata(&instances, &proof);
    let success = {
        let mut evm = ExecutorBuilder::default()
            .with_gas_limit(u64::MAX.into())
            .build();

        let caller = Address::from_low_u64_be(0xfe);
        let verifier = evm
            .deploy(caller, deployment_code.into(), 0.into())
            .address
            .unwrap();
        let result = evm.call_raw(caller, verifier, calldata.into(), 0.into());

        dbg!(result.gas_used);

        !result.reverted
    };
    assert!(success);
}

fn main() {
    let params = gen_srs(8);

    let circuit = StandardPlonk::rand(OsRng);
    let pk = gen_pk(&params, &circuit);
    let deployment_code = gen_evm_verifier(&params, pk.get_vk(), StandardPlonk::num_instance());

    let proof = gen_proof(&params, &pk, circuit.clone(), circuit.instances());
    evm_verify(deployment_code, circuit.instances(), proof);
}

このコード内ではstandardなPlonkのconstraintに対応するcustom gateを作り、そのYulのコンパイル済みバイトコードdeployment_codeを生成し、内部のEVMシミュレータで検証を実行している。

nunonuno

main関数を次のように変更する。

fn main() {
    let params = gen_srs(8);

    let circuit = StandardPlonk::rand(OsRng);
    let pk = gen_pk(&params, &circuit);
    let deployment_code = gen_evm_verifier(&params, pk.get_vk(), StandardPlonk::num_instance());

    let proof = gen_proof(&params, &pk, circuit.clone(), circuit.instances());

    let calldata = encode_calldata(&circuit.instances(), &proof);
    let deployment_code_hex = "0x".to_string() + &hex::encode(deployment_code);
    let calldata_hex = "0x".to_string() + &hex::encode(calldata);
    let mut file = File::create("deployment_code.txt").unwrap();
    file.write_all(deployment_code_hex.as_bytes()).unwrap();
    let mut file = File::create("calldata.txt").unwrap();
    file.write_all(calldata_hex.as_bytes()).unwrap();
}

これでdeployment_codeと、そのEVM verifierが受理するproofのcalldataをファイルに保存することができる。

nunonuno

Solidityから呼び出す

EVM verifierを実際に使うには、まず先程のバイトコードをデプロイして、そのコントラクトアドレスに対してSolidityからaddress.staticcall()するという流れになる。

hardhatの新規プロジェクトを立ち上げ、次のようなコントラクトを書く。

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.9;

contract Verifier {
    address yulVerifier;

    constructor(address _yulVerifier) {
        yulVerifier = _yulVerifier;
    }

    function verify(bytes calldata input) external view returns (bool) {
        (bool success, ) = yulVerifier.staticcall(input);
        return success;
    }
}

そして、deploy.tsに次のようなコードを書く。

import { ethers } from "hardhat";
import * as fs from "fs/promises";

async function readFile(path: string): Promise<string> {
  try {
    const data = await fs.readFile(path, "utf-8");
    return data;
  } catch (err) {
    console.error(err);
    return "";
  }
}

async function main() {
  const CONTRACT_BYTECODE = await readFile("./deployment_code.txt");
  const CALLDATA = await readFile("./calldata.txt");

  const signer = await ethers.getSigners();
  const factory = ethers.ContractFactory.fromSolidity(
    { bytecode: CONTRACT_BYTECODE, abi: [] },
    signer[0]
  );
  const contract = await factory.deploy();
  await contract.deployed();

  const Verifier = await ethers.getContractFactory("Verifier");
  const verifier = await Verifier.deploy(contract.address);
  await verifier.deployed();

  const ret = await verifier.verify(CALLDATA);
  console.log(ret);
}

main().catch((error) => {
  console.error(error);
  process.exitCode = 1;
});

これを実行すると、EVMで正常にproofが検証され、trueが返ってくることが確認できる。

nunonuno

追記: 2024/1/29

現在はPSEのhalo2-solidity-verifierが良さそう。snark verifierは比較的小規模な回路でもコントラクトサイズのデプロイ上限を超えてしまう場合があったが、halo2-solidity-verifierは様々な工夫がなされていてコントラクトサイズを比較的小さく抑えることができる。

https://github.com/privacy-scaling-explorations/halo2-solidity-verifier