Groth16

zero-knowledge proof는 prover가 입력에 대한 어떤 정보도 드러내지 않고 어떤 진술이 참이라는 점을 검증할 수 있게 해준다. 예를 들어 prover는 해답을 공개하지 않고 sudoku puzzle의 해답을 알고 있음을 검증할 수 있다.

zero-knowledge succinct non-interactive argument of knowledge(zk-SNARKs)는 non-interactive하고, proof 크기가 작으며, 검증 시간이 효율적인 zero-knowledge proof 계열이다. 이 계열의 중요하고 널리 사용되는 변형으로는 Groth16 proof system 같은 pairing-based zk-SNARK가 있으며, 이는 가장 효율적이고 널리 사용되는 방식 중 하나이다.

Sui의 Move API를 사용하면 BN254 또는 BLS12-381 elliptic curve construction 중 하나에서 Groth16 zk-SNARK를 사용해 NP-complete language로 표현 가능한 어떤 진술이든 효율적으로 검증할 수 있다.

이러한 진술을 표현하기 위한 high-level language로는 다음 예시에서 사용하는 Circom이 있다.

Groth16은 verification key를 생성하기 위해 각 circuit마다 trusted setup을 요구한다. API는 특정 verification key를 pinning하지 않으며 각 사용자는 자체 parameter를 생성하거나 기존 verification을 자신의 app에 사용할 수 있다.

Usage

다음 예시는 Circom으로 작성한 진술에서 Groth16 proof를 만들고, 그 proof를 Sui Move API를 사용해 검증하는 방법을 보여준다. API는 현재 최대 8개의 public input을 지원한다.

Create circuit

이 예시에서는 공개적으로 알려진 수 c의 factorisation a * b = c를 a와 b를 드러내지 않고 알고 있음을 증명하는 proof를 만든다.

pragma circom 2.1.5;

template Main() {
    signal input a;
    signal input b;
    signal output c;

    c <== a * b;
}
component main = Main();

circom compiler has been installed되었다고 가정하면, 위 circuit는 다음 command로 compile된다:

$ circom main.circom --r1cs --wasm

이 command는 constraint를 R1CS format으로 출력하고 circuit를 Wasm format으로 출력한다.

Generate proof

Sui에서 검증 가능한 proof를 생성하려면 witness를 생성해야 한다. 이 예시는 이를 위해 Arkworks의 ark-circom Rust library를 사용한다. 이 코드는 circuit에 대한 witness를 구성하고, 주어진 입력에 대해 그 witness의 proof를 생성한다. 마지막으로 proof가 올바른지 검증한다.

use ark_bn254::Bn254;
use ark_circom::CircomBuilder;
use ark_circom::CircomConfig;
use ark_groth16::{Groth16, prepare_verifying_key};
use ark_serialize::CanonicalSerialize;
use ark_snark::SNARK;
use rand::rngs::StdRng;
use rand::SeedableRng;

fn main() {
    // witness와 proof 생성을 위해 WASM과 R1CS를 불러온다
    let cfg = CircomConfig::<Bn254>::new("../circuit/main_js/main.wasm", "../circuit/main.r1cs").unwrap();
    let mut builder = CircomBuilder::new(cfg);

    // private input: 숫자의 factorisation이다
    builder.push_input("a", 641);
    builder.push_input("b", 6_700_417);

    let circuit = builder.setup();

    // 무작위 proving key를 생성한다. 경고: 이는 안전하지 않다. 프로덕션에서는 ceremony에서 생성한 proving key를 사용해야 한다.
    let mut rng: StdRng = SeedableRng::from_seed([0; 32]);
    let pk =
        Groth16::<Bn254>::generate_random_parameters_with_reduction(circuit, &mut rng).unwrap();

    let circuit = builder.build().unwrap();
    let public_inputs = circuit.get_public_inputs().unwrap();

    // proof를 생성한다
    let proof = Groth16::<Bn254>::prove(&pk, circuit, &mut rng).unwrap();

    // proof를 검증한다
    let pvk = prepare_verifying_key(&pk.vk);
    let verified = Groth16::<Bn254>::verify_with_processed_vk(&pvk, &public_inputs, &proof).unwrap();
    assert!(verified);

    // verifying key를 출력한다
    let mut pk_bytes = Vec::new();
    pk.vk.serialize_compressed(&mut pk_bytes).unwrap();
    println!("Verifying key: {}", hex::encode(pk_bytes));

    // proof를 출력한다
    let mut proof_serialized = Vec::new();
    proof.serialize_compressed(&mut proof_serialized).unwrap();
    println!("Proof: {}", hex::encode(proof_serialized));

    // public input을 출력한다. 이 값들은 이어붙여진다는 점에 유의한다.
    let mut public_inputs_serialized = Vec::new();
    public_inputs.iter().for_each(|input| {
        input.serialize_compressed(&mut public_inputs_serialized).unwrap();
    });
    println!("Public inputs: {}", hex::encode(public_inputs_serialized));
}

이렇게 하면 prover가 factorisation을 알고 있다는 proof가 생성된다는 점을 다시 상기하자. 여기서는 5th Fermat number (2³² + 1 = 4294967297 = 641 * 6700417)에 대한 proof를 만든다.

위 function의 output은 다음과 같다.

Verifying key: 94d781ec65145ed90beca1859d5f38ec4d1e30d4123424bb7b0c6fc618257b1551af0374b50e5da874ed3abbc80822e4378fdef9e72c423a66095361dacad8243d1a043fc217ea306d7c3dcab877be5f03502c824833fc4301ef8b712711c49ebd491d7424efffd121baf85244404bded1fe26bdf6ef5962a3361cef3ed1661d897d6654c60dca3d648ce82fa91dc737f35aa798fb52118bb20fd9ee1f84a7aabef505258940dc3bc9de41472e20634f311e5b6f7a17d82f2f2fcec06553f71e5cd295f9155e0f93cb7ed6f212d0ccddb01ebe7dd924c97a3f1fc9d03a9eb915020000000000000072548cb052d61ed254de62618c797853ad3b8a96c60141c2bfc12236638f1b0faf9ecf024817d8964c4b2fed6537bcd70600a85cdec0ca4b0435788dbffd81ab
Proof: 212d4457550f258654a24a6871522797ab262dee4d7d1f89af7da90dc0904eac57ce183e6f7caca9a98755904c1398ff6288cec9877f98f2d3c776c448b9ad166839e09d77967b66129c4942eee6d3eaf4a0ce2a841acc873a46ae35e40f0088288d038857c70a1415300544d7cf376949a372049679afa35ee5206b58266184
Public inputs: 0100000001000000000000000000000000000000000000000000000000000000

proof를 검증하려면 이 모든 output이 필요하다.

Verification in Sui

Sui에서 proof를 검증하는 API는 특수한 processed verification key를 기대하며, 여기서는 값의 일부만 사용된다. 이 prepared verification key에 대한 계산은 이상적으로 circuit당 한 번만 일어나야 한다. 이 처리는 앞서 사용한 params.vk 값을 serialize한 값을 이용해 Sui Move API의 sui::groth16::prepare_verifying_key method로 수행할 수 있다.

prepare_verifying_key function의 output은 네 개의 byte array를 담은 vector이며, 이는 vk_gamma_abc_g1_bytes, alpha_g1_beta_g2_bytes, gamma_g2_neg_pc_bytes, delta_g2_neg_pc_bytes에 대응한다.

proof를 검증하려면 public_inputs_bytes와 proof_points_bytes라는 두 입력도 더 필요하며, 이는 위 프로그램이 출력한다.

다음 smart contract 예시는 위 프로그램의 output을 사용한다. 먼저 verification key를 준비한 뒤 대응되는 proof를 검증한다. 이 예시는 BN254 elliptic curve construction을 사용하며, 이는 prepare_verifying_key와 verify_groth16_proof function의 첫 번째 parameter로 전달된다. BLS12-381 construction에는 대신 bls12381 function을 사용할 수 있다.

use sui::groth16;

public fun groth16_bn254_test() {
    let pvk = groth16::prepare_verifying_key(&groth16::bn254(), &x"94d781ec65145ed90beca1859d5f38ec4d1e30d4123424bb7b0c6fc618257b1551af0374b50e5da874ed3abbc80822e4378fdef9e72c423a66095361dacad8243d1a043fc217ea306d7c3dcab877be5f03502c824833fc4301ef8b712711c49ebd491d7424efffd121baf85244404bded1fe26bdf6ef5962a3361cef3ed1661d897d6654c60dca3d648ce82fa91dc737f35aa798fb52118bb20fd9ee1f84a7aabef505258940dc3bc9de41472e20634f311e5b6f7a17d82f2f2fcec06553f71e5cd295f9155e0f93cb7ed6f212d0ccddb01ebe7dd924c97a3f1fc9d03a9eb915020000000000000072548cb052d61ed254de62618c797853ad3b8a96c60141c2bfc12236638f1b0faf9ecf024817d8964c4b2fed6537bcd70600a85cdec0ca4b0435788dbffd81ab");
    let proof_points = groth16::proof_points_from_bytes(x"212d4457550f258654a24a6871522797ab262dee4d7d1f89af7da90dc0904eac57ce183e6f7caca9a98755904c1398ff6288cec9877f98f2d3c776c448b9ad166839e09d77967b66129c4942eee6d3eaf4a0ce2a841acc873a46ae35e40f0088288d038857c70a1415300544d7cf376949a372049679afa35ee5206b58266184");
    let public_inputs = groth16::public_proof_inputs_from_bytes(x"0100000001000000000000000000000000000000000000000000000000000000");
    assert!(groth16::verify_groth16_proof(&groth16::bn254(), &pvk, &public_inputs, &proof_points));
}

Usage​

Create circuit​

Generate proof​

Verification in Sui​

Usage

Create circuit

Generate proof

Verification in Sui