5 weeks ago, [Patract Hub](https://patract.io) applied a [treasury proposal #24](https://polkadot.polkassembly.io/treasury/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](https://github.com/HarryR/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](https://github.com/patractlabs/megaclite/blob/master/crates/curve/arkworks/src/ops.rs)
* Test cases: [megaclite/tree/master/crates/curve/arkworks/src/tests](https://github.com/patractlabs/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:

```rust
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:

```rust
// 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](https://github.com/patractlabs/jupiter/blob/features/runtime-interfaces/primitives/io/src/lib.rs)

```rust
/// 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](https://github.com/patractlabs/jupiter/blob/features/runtime-interfaces/pallets/template/src/lib.rs)

```toml
# 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.

```rust
//! 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:

```bash
# 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:

```bash
# 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](https://github.com/patractlabs/megaclite/blob/master/crates/curve/arkworks/src/groth16/verify.rs)
* Test cases：[megaclite/blob/master/tests/src/arkworks/bench.rs](https://github.com/patractlabs/megaclite/blob/master/tests/src/arkworks/bench.rs)

[gronth16](https://eprint.iacr.org/2016/260.pdf) 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:

![](https://i.imgur.com/MoEKfTK.png)

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

  ![](https://i.imgur.com/GBIEHmE.png)

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:

![](https://i.imgur.com/r9MZOmr.png)

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](https://github.com/patractlabs/jupiter/blob/features/runtime-interfaces/primitives/chain-extension/src/lib.rs)
* Test case：[jupiter/blob/features/runtime-interfaces/pallets/template/src/tests.rs](https://github.com/patractlabs/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.

```rust
//! 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](https://github.com/patractlabs/metis/tree/master/groth16/lib.rs)

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

Enable chain extension interfaces of Megaclite by using `ink` feautre.

```rust
// 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](https://github.com/patractlabs/jupiter/blob/19a1fb3a21e04a5e14b33a0f25c6f10e059cc6ea/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](https://github.com/patractlabs/megaclite/blob/master/crates/merkle-tree/src/mimc.rs)
* Merkle Tree: [megaclite/blob/master/crates/merkle-tree/src/merkle_tree.rs](https://github.com/patractlabs/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.

![](https://i.imgur.com/Rg2zjPW.png)

Source code:

```rust
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

![](https://i.imgur.com/aCExnKY.png)

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

![](https://i.imgur.com/fqD85VQ.png)

Source code:

```rust
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](https://github.com/patractlabs/megaclite/tree/master/crates/eddsa)

It is built on [JubJub curve](https://z.cash/technology/jubjub/). Jubjub is the [twisted Edwards curve](https://en.wikipedia.org/wiki/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:

![](https://i.imgur.com/clDEIqR.png)

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:

```rust
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.


- Problem Statement: Patract Hub has completed the v0.1 version of the Megaclite project, which aims to introduce basic zero-knowledge proof support for the Polkadot ecosystem. The intended audience includes developers who can develop applications through WASM smart contracts or Runtime.
- Significance: The project is significant as it provides on-chain support for elliptic curve alt_bn128 and bls12_381, and bls12-377, bw6_761, and integrates addition, scalar multiplication, and Pairing functions of the curves in Native layer and Runtime WASM layer.
- Proposed Solution: The solution includes providing these functions to the upper Runtime Pallets and Contracts to call, providing two zkSNARK Verify upper-layer interfaces, and starting the Metis project to implement EdDSA, MerkleTree, MiMC Hash, etc. contract library on the Ink! contract layer.
- Expected Outcomes: The expected outcomes include the creation of a sample payment DApp based on Megaclite, the provision of off-chain toolbox support for Ink! contract, and the development of more library contracts built by ink!. The value proposition includes improving execution efficiency and reducing development costs for developers in the Polkadot ecosystem.

#221 Patract Hub's treasury report for Megaclite v0.1 (ZKP support)

No Active Proposals