5 weeks ago, Patract Hub applied a treasury proposal #24 for Megaclite v0.1. Megaclite project will be dedicated to introducing basic zero-knowledge proof underlying support for the Polkadot ecology, so that developers can easily develop applications at the upper level through WASM smart contracts or Runtime.

Now, we have finished all the works of v0.1 and you can review our source code at those repos. We will introduce more details at the following report.

• ZKP library: https://github.com/patractlabs/megaclite
• Testnet example: https://github.com/patractlabs/jupiter
• Contract example: https://github.com/patractlabs/metis

1. Recap of Megaclite’s development plan (v0.1 ~ v0.3)

• v0.1: Provide on-chain support for elliptic curve alt_bn128 and bls12_381 and bls12-377, bw6_761
  • Integrate addition (ADD), scalar multiplication (MUL) and Pairing functions of the curves in Native layer and Runtime WASM layer.
  • Provide these three functions to the upper Runtime Pallets and Contracts to call.
  • In the Runtime layer and the Ink! contract layer, provide two zkSNARK Verify upper-layer interfaces ( verification function of groth16, similar to the Verifier library of ethsnarks ).
  • Start the Metis project and implement EdDSA, MerkleTree, MiMC Hash, etc. contract library on the Ink! contract layer.
• v0.2: Provide off-chain toolbox support for Ink! contract
• v0.3: Create a sample payment DApp based on Megaclite

2. Support and benchmark basic units in Native layer and WASM layer.

2.1 Encapsulate crypto units of the four curves from arkworks

• Arkworks library: https://github.com/arkworks-rs/curves.
• Source: megaclite/blob/master/crates/curve/arkworks/src/ops.rs
• Test cases: megaclite/tree/master/crates/curve/arkworks/src/tests

We inherited the PairingEngine trait through the CurveBasicOperations trait and combined the three methods of ADD, MUL, and 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 }

Three of the methods are exposed to the Runtime and ink! layers with byte slice interfaces. ADD and MUL return elliptic curve points in byte vector. Pairings are internally paired and accumulated in batches, and the result is then compared with Fqk::one(). Return true if they are equal, otherwise just return.

The CurveBasicOperations trait also encapsulates some different elliptic curve parameters needed to write groth16 verification code:

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

2.2 Import Megaclite through host calls in Native layer.

• Example：jupiter/blob/features/runtime-interfaces/primitives/io/src/lib.rs

/// 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 Import Megaclite as Runtime library in WASM layer

• Example：jupiter/blob/features/runtime-interfaces/pallets/template/src/lib.rs

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

megaclite-arkworks supports no_std，so we can import it directly in Runtime layer.

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

2.4 Benchmark of basic units

You can build the program like this:

# Clone the branch `curve-benchmark` of our fork
git clone https://github.com/patractlabs/jupiter.git \
    --branch features/runtime-interfaces \
    --depth=1

# Build the template
cd 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

Then, run the benchmark scripts like this:

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

Our benchmark result on ubuntu LTS 20.04. Time is measured in µs

| memory              | processor                           |
|---------------------|-------------------------------------|
| 64GiB System memory | AMD Ryzen 9 5900X 12-Core Processor |

| Curve             | Operation    | Native Time(µs) | WASM Time(µs) | Speed(Native/WASM) |
|-------------------|--------------|-----------------|---------------|--------------------|
| bls12\_377        | add          | 9.588           | 29.02         | ~3x                |
| (~9.5x)           | mul          | 183.1           | 1893          | ~10x               |
|                   | pairing\_two | 1732            | 15310         | ~7x                |
| bls12\_381        | add          | 13.9            | 28.31         | ~2x                |
| (~10x)            | mul          | 177.1           | 1879          | ~10x               |
|                   | pairing\_two | 1438            | 14770         | ~10x               |
| bn254             | add          | 5.631           | 16.05         | ~3x                |
| (~5x)             | mul          | 107.7           | 534.3         | ~5x                |
|                   | pairing\_two | 1150            | 5061          | ~5x                |
| bw6\_761          | add          | 26.9            | 92.94         | ~4x                |
| (~13x)            | mul          | 956.8           | 14330         | ~15x               |
|                   | pairing\_two | 5715            | 60960         | ~10x               |

• ADD: Test the addition of two generators by the test cases from arkworks.
• MUL: Test a random number with the size of a private key and multiply the generator by the test cases from arkworks.
• Pairing: Test bilinearity: e(s * a, b) = e(s * b, a) by using arkworks to generate test data.

3. Provide and benchmark Groth16 Verifier in ink! layer

3.1 Introduction of Groth16 Verification

• Source：megaclite/blob/master/crates/curve/arkworks/src/groth16/verify.rs
• Test cases：megaclite/blob/master/tests/src/arkworks/bench.rs

gronth16 is currently the zero-knowledge proof algorithm with the highest verification efficiency (only four pairings are required) and the smallest proof size, so we prefer to choose Groth16 proof system, its verification illustration is as follows:

In the paper, we can see that the core of verification is an equation:

For the convenience of use in the project implementation, the underlying pairing algorithm provide batch pairing calculation and accumulation, so we need to make a conversion:

It can be seen from the formula that four Pairings, l times ADD and MUL operation (related to the actual circuit) are required, and finally, the result of the four pairings will return true or false.

3.2 Expose Megaclite basic units for ink! contract to call through chain-extension

• Chain extension example: jupiter/blob/features/runtime-interfaces/primitives/chain-extension/src/lib.rs
• Test case：jupiter/blob/features/runtime-interfaces/pallets/template/src/tests.rs

Our allocation for Megaclite function id in chain extension:

| curve      | add        | mul        | pairing    |
|------------|------------|------------|------------|
| bls12\_377 | 0x01000000 | 0x01000001 | 0x01000002 |
| bls12\_381 | 0x01000010 | 0x01000011 | 0x01000012 |
| bn254      | 0x01000020 | 0x01000021 | 0x01000022 |
| bw6\_761   | 0x01000030 | 0x01000031 | 0x01000032 |

The corresponding interface of Megaclite supports chain extension (called from ink! contract) through conditional compilation or directly executes related functions.

//! 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.3 Call Megaclite basic units in ink! contract to provide Groth16 Verifier

• Source: metis/tree/master/groth16/lib.rs

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

Enable chain extension interfaces of Megaclite by using ink feautre.

// 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.4 Benchmark of Groth16 Verifier

• Source: jupiter pallets/template/src/benchmarking.rs#L68

You can build Jupiter by using the same way of above，but we need to pass groth16 to scripts/benchmark.sh

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

Our MiMC-Based Groth16 Verify Benchmark Results:

• mimc rounds : 322

| Curve      | Native Time(µs) | WASM Time(µs) | Speed(Native/WASM) |
|------------|-----------------|---------------|--------------------|
| bls12\_377 | 40860           | 60550         | ~1.5x              |
| bls12\_381 | 39120           | 58400         | ~1.5x              |
| bn254      | 30760           | 36800         | ~1.2x              |
| bw6\_761   | 63798           | 172900        | ~2.7x              |

NOTE: The implementation of MiMC-Based Groth16 Verifier here is that when Megaclite is imported into the contract, the verify function of ADD, MUL, Pairing can be run by calling the chain extension.
Test contract: https://github.com/patractlabs/metis/blob/master/groth16/lib.rs

4. Conclusion of Native version and WASM version

According to the test results of the basic units , there is 5-7 times gap between the performance of the WASM version and the Native version. But, according to the test results of upper-level ink! contract for MiMC Groth16 Verifier, the speed only has little difference, and the time consumption (36-170ms) is acceptable for the block producer.

The WASM version does not need to modify the Host Calls in Native layer, so Megaclite will continue to develop the future roadmap in WASM layer, and suspend the development direction of the Native layer, leaving the native layer design to ParityTech and W3F Research. In addition, Jupiter will integrate Megaclite in runtime and ink! to provide a public online test environment.

5. More library contracts built by ink!

5.1 MiMC-based Merkle Tree

• MiMC ：megaclite/blob/master/crates/merkle-tree/src/mimc.rs
• Merkle Tree: megaclite/blob/master/crates/merkle-tree/src/merkle_tree.rs

MiMC implements a hash algorithm based on Field on the elliptic curve of alt_bn128, so its circuit implementation in the prove system of ZKP (based on the alt_bn128 curve) is very friendly.

The mimc implementation is shown in the figure below, using Sponge mode instantiated by MiMC permutation with a fixed key.

Source code:

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;
}

In snark setting , MiMC-n/n block-cipher usually use Even-Mansour mode

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

Source code:

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)^7
t = &in_x + &c % &*SCALAR_FIELD + in_k % &*SCALAR_FIELD; // t = x + c_i + k
a = t.mulmod(&t, &*SCALAR_FIELD); // t^2
a = a.mulmod(&a, &*SCALAR_FIELD).mulmod(&a, &*SCALAR_FIELD);
in_x = a.mulmod(&t, &*SCALAR_FIELD); // t^7

5.2 EdDSA verifier

• Source code：megaclite/tree/master/crates/eddsa

It is built on 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 = 21888242871839275222246405745257275088548364400416034343698204186575808495617
r = 21888242871839275222246405745257275088696311157297823662689037894645226208583

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

It also implements ETEC (Extened Twisted Edwards coordinate). In the Extended coordinate system, it can provide faster addition operations. In the Projective coordinate system, it can avoid inversion operations and provide faster double operations.

The core verification algorithm of EdDSA signature is as follows:

Where (s, R) is the signature, Pk is the public key, and h is the hash value of the message. Because R is generated by the private key and the message hash, EdDSA is also a deterministic signature algorithm.

Source code:

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. Recap of verification of Megaclite v0.1

• 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

We will propose v0.2 and v0.3 later after some time for research.