Skip to main content

zkMega v0.1 报告（Megaclite v0.1 报告）

1. 回顾 Megaclite v0.1 的设计目标#

  • Provide more on-chain underlying cryptography support than Ethereum. The current stage includes four curves: alt_bn128, bls12_377, bls12_381, bw6_761
  • Integrate ADD, Scalar MUL, Paring units under Runtime layer, and provide them to Runtime applications through Runtime-Interface, and further provide them to Wasm contract applications through Contract-Seal
  • Through Pallet and Ink! contract libraries, providing more higher-level verification and crypto tools than Ethereum, improving execution efficiency and reducing development costs
  • Provide typical sample applications through Ink! sample contracts

2. Pairing Friendly Curves#

我们基于 arkworks-curve 封装了bls12_377, bls12_381, bw6_761, bn254 这四条 Piaring Friendly Curves 的基础运算，通过在 Runtime 直接引入 与制作 Host Functions 的办法将它们集成到了 jupiter，并制作了 Benchmarks。

2.1 基于 arkworks-curve 的封装#

我们通过 CurveBasicOperations trait 继承 PairingEngine trait 组合了 add，mul，pairings 三个方法:

fn add(input: &[u8]) -> Result<Vec<u8>, SerializationError> { \\omit }fn mul(input: &[u8]) -> Result<Vec<u8>, SerializationError> { \\omit }fn pairings(input: &[u8]) -> Result<bool, SerializationError> { \\omit }

其中三个方法以字节切片类型的接口暴露给 runtime 和 ink 层, add, mul 返回的是字节向量类型的椭圆曲线点, pairings 内部通过批量配对然后累加，得到的结果再与 Fqk::one() 进行对比，相等则返回 true，否则返回。

在 CurveBasicOperations trait 里还封装了一些编写 groth16 verify 代码所需要用到的不同的椭圆曲线参数:

// curve basic parametersconst SCALAR_FIELD: &'static str;const MODULUS: &'static [u8];// G1 bytes lengthconst G1_LEN: usize;// G2 bytes lengthconst G2_LEN: usize;// Scalar bytes lengthconst SCALAR_LEN: usize;// Curve ID is used for adaptation chain extension const CURVE_ID: u32;

2.2 通过 Host Call 使用 megaclite#

/// Pairing runtime interface#[runtime_interface]pub trait Pairing {    /// | curve     | add        | mul        | pairing    |    /// |-----------|------------|------------|------------|    /// | bls12_377 | 0x01000000 | 0x01000001 | 0x01000002 |    /// | bls12_381 | 0x01000010 | 0x01000011 | 0x01000012 |    /// | bn254     | 0x01000020 | 0x01000021 | 0x01000022 |    /// | bw6_761   | 0x01000030 | 0x01000031 | 0x01000032 |    fn call(func_id: u32, input: &[u8]) -> Option<Vec<u8>> {        curve::call(func_id, input).ok()    }}

2.3 在 Runtime 中直接使用 megaclite#

# Cargo.toml[dependencies.curve]package = "megaclite-arkworks"git = "https://github.com/patractlabs/megaclite.git"features = ["tests"]default-features = false

megaclite-arkworks 支持 no_std，我们可以在 runtime 中直接引入。

//! lib.rsdecl_module! {    #[weight = 10_000 + T::DbWeight::get().writes(1)]    pub fn wasm_bls12_377_add(origin) {        curve::tests::add(0x2a);    }}

2.4 Benchmarks#

2.4.1 Building#

# Clone the branch `curve-benchmark` of our forkgit clone https://github.com/patractlabs/jupiter.git \    --branch features/runtime-interfaces \    --depth=1
# Build the templatecd jupiter  \  && git submodule update --init \  && cargo build -p jupiter-dev --all-features --release
# Check the command benchmark works fine./target/release/jupiter-dev benchmark -p pallet_template -e wasm_bls_12_381_add

2.4.2 Result#

# 1. Under the jupiter repo# 2. Has compiled the release version jupiter-dev./target/benchmark.sh
memoryprocessor
64GiB System memoryAMD Ryzen 9 5900X 12-Core Processor

Here we test the curevs on ubuntu LTS 20.04, Time is measured in µs

CurveOperationNative Time(µs)Wasm Time(µs)Speed(Native/Wasm)
bls12_377(~9.5x)add9.58829.02~3x
mul183.11893~10x
pairing_two173215310~7x
bls12_381(~10x)add13.928.31~2x
mul177.11879~10x
pairing_two143814770~10x
bn254(~5x)add5.63116.05~3x
mul107.7534.3~5x
pairing_two11505061~5x
bw6_761(~13x)add26.992.94~4x
mul956.814330~15x
pairing_two571560960~10x
  • Add: 取 arkworks 的 test 用例数据, 测试了两个 generator 相加。
  • Mul: 取 arkworks 的 test 用例数据, 测试了一个私钥大小的随机数和 generator 相乘.
  • Pairing: 使用 arkworks 产生测试数据, 测试了bilinearity: e(s * a, b) = e(s * b, a)

根据测试结果来看，Wasm 版本性能与 Native 版有一定差距，但从结果来讲，性能足以满足需求，在 3.1 中，我们将通过测试在 ink! 中调用链上的 megaclite 来进一步比较 Host Call 版本与 Wasm 版本的性能。

3. Groth16 Verify System#

gronth16 是目前零知识证明里验证效率最高(仅仅需要四次 pairing )且 proof 尺寸最小的算法, 所以我们优先选择了 groth16 proof system, 其 verifier 图示如下:

在论文里我们可以看到, verifier的验证核心是一个等式:

为了方便使用，工程实现中，底层pairing算法实现了批量 pairing 计算并进行累加，所以我们需要做个转化:

从公式中可以看出来，需要四次pairing，l次add和mul操作(与实际电路有关), 最终, 四次配对的结果会返回true或者false。

3.1 在 runtime 中 通过 chain-extension 暴露 megaclite 给 ink! 合约调用#

我们在 chain-extension 中对 megaclite function id 的分配如下：

curveaddmulpairing
bls12_3770x010000000x010000010x01000002
bls12_3810x010000100x010000110x01000012
bn2540x010000200x010000210x01000022
bw6_7610x010000300x010000310x01000032

Megaclite 的对应接口通过条件编译来支持(从 ink! 合约中调用)chain extension 或直接执行相关函数。

//! https://github.com/patractlabs/megaclite/blob/master/crates/curve/arkworks/src/lib.rs/// Call curve functions using chain extensions#[cfg(feature = "ink")]pub fn call(func_id: u32, input: &[u8]) -> Result<Vec<u8>> {    Ok(ink_env::call_chain_extension(func_id, &Vec::from(input))?)}
/// Call curve functions directly#[cfg(not(feature = "ink"))]pub fn call(func_id: u32, input: &[u8]) -> Result<Vec<u8>> {    Ok(match func_id {        0x01000000 => <ark_bls12_377::Bls12_377 as CurveBasicOperations>::add(input),        0x01000010 => <ark_bls12_381::Bls12_381 as CurveBasicOperations>::add(input),        0x01000020 => <ark_bn254::Bn254 as CurveBasicOperations>::add(input),        0x01000030 => <ark_bw6_761::BW6_761 as CurveBasicOperations>::add(input),        0x01000001 => <ark_bls12_377::Bls12_377 as CurveBasicOperations>::mul(input),        0x01000011 => <ark_bls12_381::Bls12_381 as CurveBasicOperations>::mul(input),        0x01000021 => <ark_bn254::Bn254 as CurveBasicOperations>::mul(input),        0x01000031 => <ark_bw6_761::BW6_761 as CurveBasicOperations>::mul(input),        0x01000002 => <ark_bls12_377::Bls12_377 as CurveBasicOperations>::pairings(input).map(b2b),        0x01000012 => <ark_bls12_381::Bls12_381 as CurveBasicOperations>::pairings(input).map(b2b),        0x01000022 => <ark_bn254::Bn254 as CurveBasicOperations>::pairings(input).map(b2b),        0x01000032 => <ark_bw6_761::BW6_761 as CurveBasicOperations>::pairings(input).map(b2b),        _ => Err(Error::new(ErrorKind::Other, "Invalid function id").into()),    }?)}

3.2 在 ink! 合约中调用链上的 megaclite 实现简单的 Groth16 Verifier#

[dependencies.curve]package = "megaclite-arkworks"git = "https://github.com/patractlabs/megaclite"features = [ "ink" ]

使用 ink feautre 开启 megaclite 的 chain extension 接口。

// ink! contract#[ink(message)]pub fn bls12_377_verify(    &self,    vk_gamma_abc: Vec<u8>,    vk: Vec<u8>,    proof: Vec<u8>,    public_inputs: Vec<Vec<u8>>,) -> bool {    if let Ok(res) = groth16::verify::<Bls12_377>(&vk_gamma_abc, &vk, &proof, &public_inputs) {        res    } else {        false    }}

3.3 Benchmarks#

3.3.1 Building#

Build jupiter 办法与 2.3.1 中相同，但在此我们需要传递 groth16 给 scripts/benchmark.sh

# 1. Under the jupiter repo# 2. Has compiled the release version jupiter-dev./target/benchmark.sh groth16

3.3.2 MiMC-Based Groth16 Verify Bench Result#

  • mimc rounds : 322
CurveNative Time(µs)Wasm Time(µs)Speed(Native/Wasm)
bls12_3774086060550~1.5x
bls12_3813912058400~1.5x
bn2543076036800~1.2x
bw6_76163798172900~2.7x

NOTE: 此处的 MiMC-Based Groth16 Verify 的实现为，在合约中引入 megaclite 中可以通过调用 chain extension 运行 add，mul，pairing 的 verify 函数，测试合约：https://github.com/patractlabs/metis/blob/master/groth16/lib.rs

根据 MiMC Groth16 Verifiy 的测试结果来看，两者的运行时间差别不大，而在实现上 Wasm 版本不需要修改 Host Call，因此 megaclite 后续将延续在 wasm 层的修改，暂停 native 层的开发方向。并且，Jupiter 将在 runtime 和 ink! 集成 megaclite，提供公共的线上测试环境。

4. More Libraries built for ink!#

4.1 mimc-based merkle tree 的实现#

mimc 是在 alt_bn128 这条椭圆曲线上实现了基于 Field 的一种 hash 算法,所以它在零知识证明的 prove system (基于 alt_bn128 曲线)里的电路实现十分友好.

mimc 实现如下图所示, 采用 Sponge mode, Sponge mode instantiated by MiMC permutation with a fixed key

代码实现:

let mut r = in_k.clone();for i in 0..in_x.len() {    r = &r + in_x[i] + mimc_pe7(&mut in_x[i], &r, &in_seed, round_count) % &*SCALAR_FIELD;}

在 snark setting 中, MiMC-n/n block-cipher 一般采用 Even-Mansour mode

Our MiMC-p/p with exponent of 7, so:

代码实现:

let mut keccak = Keccak::v256();let mut received = [0u8; 32];keccak.update(&c.to_bytes_be()[..]);keccak.finalize(&mut received);c = U256::from_bytes_be(&received) % &*SCALAR_FIELD;
// x = (x + c_i + k)^7t = &in_x + &c % &*SCALAR_FIELD + in_k % &*SCALAR_FIELD; // t = x + c_i + ka = t.mulmod(&t, &*SCALAR_FIELD); // t^2a = a.mulmod(&a, &*SCALAR_FIELD).mulmod(&a, &*SCALAR_FIELD);in_x = a.mulmod(&t, &*SCALAR_FIELD); // t^7

4.2 eddsa verifier 的实现#

这里 eddsa 签名算法是在JubJub curve上实现的:

Jubjub is the twisted Edwards curve -u^2 + v^2 = 1 + d.u^2.v^2 of rational points over GF(q) with a subgroup of prime order r.

q = 21888242871839275222246405745257275088548364400416034343698204186575808495617r = 21888242871839275222246405745257275088696311157297823662689037894645226208583

The choice of GF(q) is made to be the scalar field of the Bn254 elliptic curve construction.

且还实现了 ETEC(Extened Twisted Edwards coordinate), 在 Extended 坐标系下, 可提供更快的加法运算，在 Projective 坐标系下，可避免求逆运算, 提供更快的 double 运算。

eddsa 签名的核心验证算法如下所示:

其中(s,R)是签名, Pk 是公钥, h 是 message 的 hash 值,因为 R 通过私钥和 message 哈希产生的, 所以 eddsa 也是一种确定性签名算法.

核心验证代码实现:

if let Some(lhs) = scalar_mult(GENERATE[0].clone(), GENERATE[1].clone(), s) {   let t = hash_to_u256(&input);   if let Some((pk_x, pk_y)) = scalar_mult(public_key[0].clone(), public_key[1].clone(), t) {       let [r_x, r_y] = r;       let etec_point = etec_add(           &point_to_etec(r_x, r_y, Q.clone()),           &point_to_etec(pk_x, pk_y, Q.clone()),           &*Q,           &JUBJUB_A.into(),           &JUBJUB_D.into(),       );       if let Some(rhs) = etec_to_point(etec_point, Q.clone()) {           return lhs == rhs;       }   }}false

5. 回顾验证信息#

  • Provide more on-chain underlying cryptography support than Ethereum. The current stage includes two curves : alt_bn128 and bls12_381
  • Integrate ADD, MUL, Paring units under Runtime layer, and provide them to Runtime applications through Runtime-Interface, and further provide them to Wasm contract applications through Contract-Seal
  • Through Pallet and Ink! contract libraries, providing more higher-level verification and crypto tools than Ethereum, improving execution efficiency and reducing development costs
  • Provide off-chain cryptography toolbox through Rust SDK
  • Provide typical sample applications through Ink! sample contracts