Megaclite

Megaclite is a zero-knowledge proof tool set building for the Polkadot ecology.

• Pairing
• Pallet Contracts
• Metis

• Polkadot Treasury report for v0.1: https://polkadot.polkassembly.io/post/221.
• Element group for discussion: https://app.element.io/#/room/#PatractLabsDev:matrix.org

ZK Rollup Introduction

Compared with the privacy function, the performance improvement brought by Rollup is the early application direction of zero-knowledge proof. At present, the Layer 2 expansion plan of the blockchain is to transfer a considerable part of the on-chain workload to off-chain to complete, and the most watched one is ZK Rollup. The essence of ZK Rollup is to compress the application on-chain state and store it in a Merkle tree, and move the state transition funtions to off-chain. At the same time, the correctness of the off-chain state transition process is guaranteed through the proof of zkSNARK. Compared with the high cost of directly processing state changes on the chain, the ZK Proof's on-chain smart contract verification is extremely cost low. At the same time, the compressed information will also be submitted to the chain together with the proof, which ensures data availability and obtains the same level of security as Layer 1.

The Ethereum Layer 2 protocols related to ZK Rollup are: zkSync, aztec, etc. Their contract verification modules share a part of the elliptic curve's basic algorithms. In 2017, Ethereum integrated three basic cryptographic calculation units of the alt bn128 curve in the form of pre-compiled contracts, which are EIP196’s ADD and Scalar_MUL algorithms, and EIP197’s Pairing algorithm. On top of this, due to the lack of rapid upgrade capabilities of Ethereum, the community can only encapsulate some tool libraries through costly Solidity contracts. On top of these basic contract libraries, many DApps can combine ZK Rollup technology to achieve some innovations, such as loopring, gitcoin and uniswap etc. However, in the past 3 years, ZK technology has further developed, such as the more practical BLS curve, and PLONK algorithm etc. Ethereum has not yet supported it.

LICENSE

Apache-2.0

Contract

Currently we are testing with CHAIN_EXTENSION, this chapter is OUTDATED Now, will be updated after the merging of #7548 and #592

Here we did some modifications on paritytech/substrate, added the curves mentioned in last chapters into runtime_interfaces, for more detail, check the pallet-contracts.

[dependencies.pallet-contracts]
git = "https://github.com/patractlabs/substrate"
branch = "patract-contracts"

We also modified ink! to adapt the new interfaces we provided, all of these modifications will test on patractlabs/jupiter in the future, and will pr to the offical repos if they are accepted by the Polkadot Ecology.

[dependencies.jupiter-ink-lang]
git = "https://github.com/patractlabs/ink"
branch = "megaclite"

Example

#![cfg_attr(not(feature = "std"), no_std)]

use jupiter_ink_lang as ink;

#[ink::contract]
mod altbn128 {
    use ink_env::zk_snarks::AltBn128;
    use ink_prelude::string::String;

    #[ink(storage)]
    pub struct Altbn128 {
        value: String,
    }

    impl Altbn128 {
        #[ink(constructor)]
        pub fn new(init_value: String) -> Self {
            Self { value: init_value }
        }

        #[ink(constructor)]
        pub fn default() -> Self {
            Self::new("hello, world".into())
        }

        #[ink(message)]
        pub fn bn_256_add(&mut self) {
            let mut result = [0; 64];
            ink_env::inflect_add::<AltBn128>(&[], &[], &mut result);
            self.value = ink_prelude::format!("0x{:x?}", result);
        }

        #[ink(message)]
        pub fn get(&self) -> String {
            ink_prelude::format!("{}", &self.value)
        }
    }
}

Example

Call curves in ink!

#![allow(unused)]
fn main() {
let result = ink_env::call_chain_extension(func_id, &Vec::from(input))?
}

MIMC

#![allow(unused)]
fn main() {
use zkp_u256::{U256, Zero};
use merkle_tree::mimc::{mimc,mimc_with_key}
let message = U256::from_decimal_str("49").unwrap();
let in_key = U256::zero();
assert_eq!(
    mimc(b"1"),
    mimc_with_key(vec![&message], &in_key)
);
}

Merkle Tree

#![allow(unused)]
fn main() {
use merkle_tree::MerkleTree;
let mut mt = MerkleTree::default();
let message = b"49";
let (leaf, index) = mt.insert(message).unwrap();
assert_eq!(mt.update(), mt.get_root());
let merkle_proof = mt.get_proof(index);
assert!(mt.verify_merkle_proof(leaf, merkle_proof, index));

let message = b"50";
let (leaf, index) = mt.insert(message).unwrap();
assert_eq!(mt.update(), mt.get_root());
let merkle_proof = mt.get_proof(index);
assert!(mt.verify_merkle_proof(leaf, merkle_proof, index));

let message = b"51";
let (leaf, index) = mt.insert(message).unwrap();
assert_eq!(mt.update(), mt.get_root());
let merkle_proof = mt.get_proof(index);
assert!(mt.verify_merkle_proof(leaf, merkle_proof, index));
}

EDDSA

TODO

Benchmark

We have constructed the tests of megaclite curves in pallet-template which imports the curves from megaclite directly(Wasm) and with runtime-interface(Native).

Building

# 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
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
./target/release/jupiter-dev benchmark -p pallet_template -e wasm_bls_12_381_add

Result

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

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

Milestones

M1: Integrate the basic units of alt_bn128 & bls12_381 (3 developer * 1 weeks)

1. Prepare the 3 basic algorithm codes (Add, Scalar_Mul, and Pairing) of alt_bn128 elliptic curve from zcash's official library bn.
2. Prepare the same 3 basic algorithm codes of bls12_381 from zcash's official library bls12_381 .
3. Integrate the above 6 algorithms into the under layer of Substrate Runtime.

M2: Provide to upper runtime and smart contract applications (3 developers * 1 weeks)

1. Add Runtime_interface to the Jupiter testnet and provide it to Runtime applications.
2. Add Contract_Seal to the contract module of the Jupiter testnet and provide it to the WASM contract application.

M3: Integrate upper-level verification and tool functions (3 developers * 1 week)

1. The runtime pallet that implements the zkSNARK verification algorithm.
2. The Metis contract library that implements the zkSNARK verification algorithm.
3. The Metis contract library that implements other commonly used algorithms, such as Poseidon, EdDSA, MerkleTree, MiMC and other commonly used algorithms.

M4: Test (3 developers * 1 week)

1. Test six basic elliptic curve algorithms
2. Test the zkSNARK verification algorithm of the Runtime layer
3. Test the zkSNARK verification algorithm implemented in the contract layer
4. Test Poseidon, EdDSA, MerkleTree, MiMC and other commonly used algorithm contract templates.

M5: Benchmark (3 developers * 1 week)

1. Provide benchmark results of all the above functions and develop them for the community as a reference for transaction weight and pricing.