A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments.

Overview

Zerokit

A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments.

Initial scope

Focus on RLN and being able to use Circom based version through ark-circom, as opposed to the native one that currently exists in Rust.

Acknowledgements

Comments
  • RLN: use space-efficient Merkle Tree implementation

    RLN: use space-efficient Merkle Tree implementation

    Problem

    Currently, zerokit RLN supports naive Merkle Tree implementation: when a RLN object is created, a tree of height N+1 is initialized (including the leaves level) with a total of 2^(N+1)-1 allocated nodes that remain allocated for the whole life of the RLN object, even in case the tree is empty or accumulates less than 2^N leaves.

    For space-efficiency reasons we would like to add support to a Merkle trees implementations that progressively allocates only those nodes which are necessary to prove membership of currently non-empty leaves.

    Acceptance criteria

    • [x] Implement Incremental Merkle Tree with APIs compatible with current Merkle Tree implementation (aligned to https://github.com/vacp2p/zerokit/issues/28)
    • [ ] ~~No regression in performances with respect to current implementation.~~
    • [ ] ~~If regression in performance, evaluate space/time tradeoffs and followup with a better solution.~~
    track:zerokit track:rln 
    opened by s1fr0 9
  • RLN: Update Rust and C API

    RLN: Update Rust and C API

    This PR addresses https://github.com/vacp2p/zerokit/issues/19.

    Progress

    • [x] Implement byte serialization/deserialization of custom data structure (RLN Witness and Proof values);
    • [x] Extend/update RLN Rust public API to support all required features;
    • [x] Extend/update RLN C public API to support all required features.
    track:zerokit track:rln 
    opened by s1fr0 8
  • RLN: fix proof generation/verification and E2E tests

    RLN: fix proof generation/verification and E2E tests

    This WIP PR addresses https://github.com/vacp2p/zerokit/issues/16 solving previous issues with proving and verifying keys import, proof generation/verification, RLN witness fields, etc. It further removes some unnecessary crates.

    track:zerokit track:rln 
    opened by s1fr0 5
  • Milestone: zerokit release v0.1

    Milestone: zerokit release v0.1

    Problem

    UPDATE: This is becoming a waterfall release which keeps getting delayed, which was never the intention. We want to take existing code and cut it into an initial 0.1 release.

    We want to publish a release v0.1 for Zerokit with a first ~~mature~~ version of the RLN module.

    Before that, it is desirable to clean-up the RLN module library code and implement different optimizations which are already standard in other libraries.

    These allow to: make the RLN module more efficient and easily integrable in projects employing the RLN primitive; bring a cleaner code and optimized cross-module primitives (e.g., Merkle trees) to new zerokit modules.

    Scope

    Release zerokit v0.1 with a RLN module that can replace and improve Kilic's RLN module currently employed by nwaku.

    Must have:

    • [x] Sanity check main features included / bug fixes included -- Err on side of not accepting more scope
    • [x] Release branch with release note and tag
    • [ ] Announce release on Discord and Twitter

    Initial list of issues, many nice to haves that can be dealt with separately:

    • [x] https://github.com/vacp2p/zerokit/issues/29
    • [ ] Maximize usage of only arkworks dependencies (e.g., replace Semaphore's Field with arkworks Fr, etc.) and remove unnecessary ones (might require adapting/integrating used primitives e.g. Poseidon hash)
      • [x] https://github.com/vacp2p/zerokit/issues/35
      • [ ] https://github.com/vacp2p/zerokit/pull/44
    • [ ] Eventually add/update APIs to address new needs resulting from completions of milestones in the RLN-RELAY track https://github.com/status-im/nwaku/issues/1062 or other tracks:
      • [ ] https://github.com/vacp2p/zerokit/pull/45 (contains https://github.com/vacp2p/zerokit/pull/36)
    • [ ] Reduce size of compiled libraries (might require partial refactoring of dependencies) https://github.com/vacp2p/zerokit/issues/37

    Acceptance criteria

    Issues defined in scope addressed.

    Risks and uncertainty

    Removing some dependencies (e.g. semaphore-rs) might result not trivial, since there might some implementation used across the code base that should be ported to the replacing dependencies.

    Out of scope

    This milestone's scope requires a RLN module which can replace (in terms of APIs and efficiency) Kilic's RLN module. However, integration of zerokit v0.1 in nwaku is out-of-scope and is tracked in https://github.com/status-im/nwaku/issues/1061.

    Notes and links

    This first issue partially overlaps with https://github.com/vacp2p/research/issues/127, where a thorough performance analysis of employing Incremental Merkle trees is performed. This milestone will clearly benefit from completion of https://github.com/vacp2p/research/issues/127, and new items will be added to the above issues list to implement any eventual optimization found.

    track:zerokit milestone 
    opened by s1fr0 4
  • RLN: Use arkworks field arithmetic only

    RLN: Use arkworks field arithmetic only

    Problem

    Currently, zerokit RLN uses both semaphore-rs Field and ark-ec Fr data types to carry field arithmetic, in order to use natively primitives from dependencies implemented for one type and the other.

    However, while the semaphore-rs Field type corresponds to a big-endian byte vector without Montgomery reduction, the arkworks Fr type does operations directly in the more efficient Montgomery form, hence modulo p reduction is implicit.

    This issue partially overlaps with the second item of https://github.com/vacp2p/zerokit/issues/31: while, in the latter, we ask to maximize usage of the Fr type, here we aim to exclusively use Fr along the whole module. Such refactor might require much more time than what is expected for zerokit v0.1 release.

    Acceptance Criteria

    • [x] Use exclusively the arkworks Fr field type to perform arithmetic in zerokit RLN
    track:zerokit 
    opened by s1fr0 3
  • refactor(rln): use space-efficient Merkle tree implementation

    refactor(rln): use space-efficient Merkle tree implementation

    This PR addresses https://github.com/vacp2p/zerokit/issues/29 by adapting and integrating in a single space-efficient Merkle tree implementation:

    In contrast to the previous zerokit Merkle tree implementation (mainly based on semaphore-rs' one), preliminary performance tests for the one proposed in this PR shows that, on average:

    • an update_next call runs 4-5 microseconds slower (that is, ~4s overall delay for setting all leaves of a tree of depth 20);
    • a new tree is initialized ~60x times faster;
    • theoretically, setting N leaves should now require ~2^(log2(N)+1)*32 bytes instead of ~2^(N+1)*32;

    The first two items can be verified running: cargo test test_merkle_performance --release -- --nocapture However, the same test should be adapted to the previous zerokit implementation -now removed- to effectively compare results.

    A thorough analysis on storage performance (third item) and possible optimizations will follow in https://github.com/vacp2p/research/issues/127.

    track:zerokit track:rln 
    opened by s1fr0 3
  • RLN: ark-circom CircomBuilder loads circuit resources slowly

    RLN: ark-circom CircomBuilder loads circuit resources slowly

    Problem

    In zerokit RLN, CircomBuilder from ark-circom library is used to load the corresponding .wasm and .r1cs circuit files.

    This process may take up to 2-3 minutes at every RLN instance creation (witness generation and zk proof verification times are not affected)

    Acceptance criteria

    • [x] Find out if this is expected behavior;
    • [x] Minimize as much as possible loading time for circuit resources within ark-circom;
    • [x] If loading time are still not practical, implement alternative circuit loading mechanisms.
    track:zerokit 
    opened by s1fr0 3
  • RLN: Update API

    RLN: Update API

    This PR expands public zerokit RLN APIs by adding:

    • set_next_leaf : set leaf to the next available free index;
    • delete_leaf: to delete a leaf at a certain index;
    • generate_rln_proof and verify_rln_proof: to verify zk proofs with input/output similar to Kilic's RLN implementation;
    • key_gen: to generate a pair of (id, commitment), with commitment = PoseidonHash(id);
    • hash: for hashing arbitrary signals to field elements.

    Tests for each new rust and C API are also provided.

    In order to implement set_next_leaf, the module now integrates a slightly customized version of semaphore-rs merkle tree and poseidon_tree implementations.

    This PR will ease integration of zerokit RLN in nwaku implementation, with minimal edits to the latter.

    track:zerokit track:rln 
    opened by s1fr0 3
  • RLN: Merkle tree and proof

    RLN: Merkle tree and proof

    Problem

    Create a merkle tree that allows one to insert identity commitments and make merkle proofs.

    From spec (https://github.com/vacp2p/rfc/blob/670816fa01f84fbde12a44f72f30e9b9458aaf5a/content/docs/rfcs/32/README.md):

    {
      root: bigint
      indices: number[]
      path_elements: bigint[][]
    }
    

    See:

    • https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/tests/rln.test.ts#L44
    • https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/src/utils.ts#L27
    • https://github.com/kilic/rln/blob/7ac74183f8b69b399e3bc96c1ae8ab61c026dc43/src/merkle.rs
    • https://github.com/worldcoin/semaphore-rs/blob/main/src/merkle_tree.rs

    Acceptance criteria

    Merkle tree struct and merkle proofs can be created

    opened by oskarth 3
  • RLN: Epic for replacing existing C interface in nim-waku

    RLN: Epic for replacing existing C interface in nim-waku

    Problem

    We want to be able to use RLN through Circom circuits in Nim.

    Notes

    Currently this issue is a bit too big, so will probably want to split this up into smaller tasks.

    Some relevant links:

    • https://github.com/kilic/rln
    • https://github.com/status-im/nim-waku/blob/master/waku/v2/protocol/waku_rln_relay/rln.nim
    • https://github.com/appliedzkp/rln
    • https://github.com/appliedzkp/zk-kit/tree/main/packages/protocols/src
    • https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/tests/rln.test.ts#L44
    • https://github.com/appliedzkp/zk-kit/blob/acaf3f43a0aab447905cdd9d6b9b24a8d99344fb/packages/protocols/src/witness_calculator.js

    Acceptance criteria

    RLN API is usable through nim-waku and has feature parity with existing implementation.

    opened by oskarth 3
  • refactor(rln): Update Merkle tree initialization method

    refactor(rln): Update Merkle tree initialization method

    This PR addresses https://github.com/vacp2p/zerokit/issues/28, by updating zerokit RLN Merkle tree implementation so that trees are initialized by passing the tree_height = N in order to be able to accumulate at most 2^N hash leaves.

    Previously, Merkle tree implementation followed semaphore-rs one, and trees were initialized by passing the total number of node levels (including the pre-images of the hash leaves), i.e. tree_height+1.

    As a consequence, previous circuits embedded in zerokit RLN, correspond to height equal to 15 and 19. Since nwaku requires a tree of height 20 for implementing RLN-RELAY, the corresponding circuit was added in the library and tests were updated to cover this case as well.

    This PR affects https://github.com/vacp2p/zerokit/pull/27, and one between https://github.com/status-im/nwaku/pull/1030 and https://github.com/status-im/nwaku/pull/1060, mainly due to tests' hardcoded values that need to be updated.

    track:zerokit track:rln 
    opened by s1fr0 2
  • Refactor optimal MT

    Refactor optimal MT

    There are some reasons we might want to refactor this piece of code, to be elaborated on in this issue.

    This issue is not blocking the initial release.

    track:zerokit 
    opened by oskarth 0
  • Create a Makefile

    Create a Makefile

    It'd be useful with a Makefile that installs all dependencies etc in a uniform way. This makes it easier for new people to be onboarded to this project and reduces cognitive overhead. Probably per crate. See Nimbus/nwaku as examples.

    track:zerokit 
    opened by oskarth 0
  • WASM support

    WASM support

    It'd be great to have WASM support so we can use Zerokit through browsers directly.

    This issue corrsponds to already opened PR by @richard-ramos https://github.com/vacp2p/zerokit/pull/38

    track:zerokit 
    opened by oskarth 0
  • serialization lengths should be u32

    serialization lengths should be u32

    Currently in the code we have places where we do this conversion:

    usize::try_from( some_u64_value ).unwrap();
    
    // The u64 value might come from a function like u64::from_be_bytes
    
    

    This will cause an error in 32 bit architectures, since usize max value depends on the architecture. To avoid this, lengths should be stored as u32 instead of u64

    track:zerokit 
    opened by richard-ramos 1
  • feat: wasm

    feat: wasm

    How to compile zerokit for wasm and see example code:

    1. Make sure you have nodejs installed and the build-essential package if using ubuntu.
    2. Install wasm-pack
    curl https://rustwasm.github.io/wasm-pack/installer/init.sh -sSf | sh
    
    1. Compile zerokit for wasm32-unknown-unknown:
    cd rln
    wasm-pack build --release
    
    1. Launch example app
    cd www
    npm install
    npm start
    
    1. Browse http://localhost:8080 and open the developer tools to see console logs
    track:zerokit 
    opened by richard-ramos 12
  • Reduce static libraries sizes

    Reduce static libraries sizes

    Problem

    While attempting to implement go-rln-zerokit, I noticed that the resulting static libraries size are very large compared to kilic/rln:

    • kilic/rln ⁃ aarch64-apple-darwin: 21.9MB ⁃ x86_64-apple-darwin: 22.6MB ⁃ aarch64-apple-ios: 21.8MB ⁃ x86_64-apple-ios: 22.6MB ⁃ universal (supporting aarch64-apple-ios,x86_64-apple-ios): 44.4MB
    • vacp2p/zerokit ⁃ aarch64-apple-darwin: 57.7MB ⁃ x86_64-apple-darwin: 59.5MB ⁃ aarch64-apple-ios: 152MB ⁃ x86_64-apple-ios: 60.5MB ⁃ universal (supporting aarch64-apple-ios,x86_64-apple-ios): 212.5MB

    While this is not an issue for desktop architecture, it is certainly not nice to have an app size increase due to the libraries it uses (also, I find it interesting that aarch64-apple-ios is 152MB, compared to the 60.5MB of x86_64-apple-ios).

    I used the following commands to generate the static libs.

    rustup target add aarch64-apple-ios x86_64-apple-ios x86_64-apple-darwin aarch64-apple-darwin
    cargo build --release --target=x86_64-apple-darwin --lib
    cargo build --release --target=aarch64-apple-darwin --lib
    cargo lipo --release
    

    Acceptance criteria

    • [ ] Reduce as much as possible library size by checking/refactoring dependencies and the module
    track:zerokit 
    opened by richard-ramos 5
Releases(v0.1)
  • v0.1(Sep 19, 2022)

    Initial beta release.

    This release contain:

    • RLN Module with API to manage, compute and verify RLN zkSNARK proofs and RLN primitives.
    • This can be consumed either as a Rust API or as a C FFI. The latter means it can be easily consumed through other environments, such as Go or Nim.

    It also contains the following examples and experiments:

    Feedback welcome! You can either open an issue or come talk to us in our Vac Discord #zerokit channel.

    Source code(tar.gz)
    Source code(zip)
Owner
vac
Modular p2p messaging stack, with a focus on secure messaging.
vac
Mote is a systems-programming language designed to be practical, performant, and simple.

Mote NOTE: this following lists the goals for what Mote is supposed to be. It does not promise that any of the features here will be accomplished or a

The Mote Programming Language 14 Jul 28, 2021
A turing-complete programming language using only zero-width unicode characters, inspired by brainfuck and whitespace.

Zero-Width A turing-complete programming language using only zero-width unicode characters, inspired by brainfuck and whitespace. Currently a (possibl

Gavin M 2 Jan 14, 2022
In this repository you can find modules with code and comments that explain rust syntax and all about Rust lang.

Learn Rust What is this? In this repository you can find modules with code and comments that explain rust syntax and all about Rust lang. This is usef

Domagoj Ratko 3 Sep 2, 2022
Crabzilla provides a simple interface for running JavaScript modules alongside Rust code.

Crabzilla Crabzilla provides a simple interface for running JavaScript modules alongside Rust code. Example use crabzilla::*; use std::io::stdin; #[i

Andy 14 Feb 19, 2022
A cargo plugin for showing a tree-like overview of a crate's modules.

cargo-modules Synopsis A cargo plugin for showing an overview of a crate's modules. Motivation With time, as your Rust projects grow bigger and bigger

Vincent Esche 372 Sep 13, 2022
Compile-time stuff and other goodies for rustaceans 🦀

?? bagel: Always baked, never fried bagel is a collection of macros and other things that we frequently use at Skytable, primarily to get work done at

Skytable 3 Jul 4, 2022
rust channel benchmarks to keep stat of performance of Kanal library in comparison with other competitors.

Rust Channel Benchmarks This is a highly modified fork of the crossbeam-channel benchmarks. to keep track of Kanal library stats in comparison with ot

Khashayar Fereidani 2 Jul 14, 2022
👌 A smol functional language that targets other languages

ditto A small, pure functional language that targets other languages. Syntax highlighting coming soon Elevator pitch ⏱️ Ditto is a mashup of my favour

ditto 44 Aug 4, 2022
Elemental System Designs is an open source project to document system architecture design of popular apps and open source projects that we want to study

Elemental System Designs is an open source project to document system architecture design of popular apps and open source projects that we want to study

Jason Shin 9 Apr 10, 2022
Rust crates with map and set with interval keys (ranges x..y).

This crates implements map and set with interval keys (ranges x..y). IntervalMap is implemented using red-black binary tree, where each node contains

Timofey Prodanov 8 Aug 23, 2022
A typemap for a set of known types optionally without heap allocation, and supporting iterating by traits

fixed_typemap docs.rs GitHub Sponsors Implements typemaps that support a lot of extra funcctionality using procedural macros. docs.rs has a lot more t

Austin Hicks 2 Dec 27, 2021
Stack heap flexible string designed to improve performance for Rust

flexible-string A stack heap flexible string designed to improve performance. FlexibleString was first implemented in spdlog-rs crate, which improved

Sprite 6 Feb 9, 2022
The Devils' Programming Language (Quantum Programming Language)

devilslang has roots in Scheme and ML-flavored languages: it's the culmination of everything I expect from a programming language, including the desire to keep everything as minimalistic and concise as possible. At its core, devilslang is lambda-calculus with pattern-matching, structural types, fiber-based concurrency, and syntactic extension.

Devils' Language 2 Aug 26, 2022
Portable linked-list allocator designed for baremetal systems

Palloc Portable linked-list allocator for embedded / baremetal systems. Using the crate Include this in the [dependencies] section of Cargo.toml pallo

Pietro 3 Jan 11, 2022
Quickly set up a `probe-run` + `defmt` + `flip-link` embedded project

app-template Quickly set up a probe-run + defmt + flip-link embedded project Dependencies 1. flip-link: $ cargo install flip-link 2. probe-run: $ # ma

Knurling 189 Sep 24, 2022
Code to follow along the "Zero To Production" book on API development in Rust.

Zero To Production / Code (Chapter 10 - Part 1) Zero To Production In Rust is an opinionated introduction to backend development using Rust. This repo

Luca Palmieri 2.4k Sep 25, 2022
Rust 核心库和标准库的源码级中文翻译,可作为 IDE 工具的智能提示 (Rust core library and standard library translation. can be used as IntelliSense for IDE tools)

Rust 标准库中文版 这是翻译 Rust 库 的地方, 相关源代码来自于 https://github.com/rust-lang/rust。 如果您不会说英语,那么拥有使用中文的文档至关重要,即使您会说英语,使用母语也仍然能让您感到愉快。Rust 标准库是高质量的,不管是新手还是老手,都可以从中

wtklbm 467 Sep 25, 2022
:crab: Small exercises to get you used to reading and writing Rust code!

rustlings ?? ❤️ Greetings and welcome to rustlings. This project contains small exercises to get you used to reading and writing Rust code. This inclu

The Rust Programming Language 29.8k Sep 18, 2022