• Stars
    star
    154
  • Rank 242,095 (Top 5 %)
  • Language
    Rust
  • License
    Apache License 2.0
  • Created almost 2 years ago
  • Updated 3 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Patricia Merkle Tree implementation in Rust

๐Ÿฆ€๐ŸŒฒ Patricia Merkle Tree in Rust ๐ŸŒฒ๐Ÿฆ€

Implementation of Ethereum's Patricia Merkle tree in Rust

Report Bug ยท Request Feature

Rust codecov license pr-welcome

Table of Contents

โš ๏ธ Disclaimer

๐Ÿšง This project is a work-in-progress and is not ready for production yet. Use at your own risk. ๐Ÿšง

๐Ÿ“– About

This crate contains an implementation of a Patricia Tree.

Its structure is implemented to match Ethereum's Patricia Merkle Trees.

๐Ÿš€ Usage

Here's an example to calculate the hash after inserting a few items.

use merkle_patricia_tree::PatriciaMerkleTree;
use sha3::Keccak256;

let mut tree = PatriciaMerkleTree::<&[u8], &[u8], Keccak256>::new();
tree.insert(b"doe", b"reindeer");
tree.insert(b"dog", b"puppy");
tree.insert(b"dogglesworth", b"cat");

let hash = tree.compute_hash().unwrap();
println!("{hash:02x}");

Testing

Run the following command:

make test

๐Ÿ“Š Benchmarking

make bench

To run external benches:

Run the one-time setup

make ext-bench-prepare
make ext-bench

Benchmarks are provided for the following use cases:

  • Retrieval of non-existant nodes.
  • Retrieval of existing nodes.
  • Insertion of new nodes.
  • Overwriting nodes.
  • Removal of nodes.
  • Removal of non-existing nodes (no-op).
  • Calculate the root Keccak256 hash.

Every use case is tested with different tree sizes, ranging from 1k to 1M.

On a AMD Ryzen 9 5950x 3.4 Ghz with 128 Gb RAM using Keccak256 as the hash function:

Bench 1k 10k 100k 1m 10m 100m
lambda's get() 38.287 ns 58.692 ns 118.90 ns 266.56 ns 365.52 ns 528.04 ns
geth get() 110.7 ns 139.6 ns 247.6 ns 484.5 ns 1286 ns timeout
paprika get() 48.14 ns 57.97 ns 77.95 ns 192.25 ns 244.59 ns timeout (memory)
lambda's insert() 327.44 ns 407.50 ns 778.76 ns 1.6858 ยตs 4.6706 ยตs 4.9003 ยตs
geth insert() 536.3 ns 820.3 ns 1.624 ยตs 2.649 ยตs 6.522 ยตs timeout
paprika insert() 2.251 ns 1.964 ns 3.650 ยตs 5.391 ยตs 5.270 us timeout (memory)
Bench 100 500 1k 2k 5k 10k
lambda's root Keccak256 113.63 ยตs 557.49 ยตs 1.1775 ms 2.3716 ms 5.8113 ms 11.737 ms
geth root Keccak256 102.358 ยตs 504.081 ยตs 989.531 ยตs 1.936 ms 5.59 ms 11.458 ms
Gets Inserts

Requires hyperfine:

make storage-bench
Storage Bench 100 1k 10k 1m
sled insert + hash 210.4 ms 204.6 ms 245.1 ms 861.3 ms
libmdx insert + hash 195.5 ms 262.3 ms 1.002 s 7.93 s

Profiling

Dependencies: valgrind, gnuplot, make

You can profile some example programs and generate plots using the following command:

make profile
Normal From Sorted Iter

๐Ÿ›  Contributing

The open source community is a fantastic place for learning, inspiration, and creation, and this is all thanks to contributions from people like you. Your contributions are greatly appreciated.

If you have any suggestions for how to improve the project, please feel free to fork the repo and create a pull request, or open an issue with the tag 'enhancement'.

  1. Fork the Project
  2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
  3. Commit your Changes (git commit -m 'Add some AmazingFeature')
  4. Push to the Branch (git push origin feature/AmazingFeature)
  5. Open a Pull Request

๐Ÿ“š Documentation

What is a Patricia Merkle Tree

PATRICIA is an acronym which means:

Practical Algorithm to Retrieve Information Coded in Alphanumeric

A compact representation of a trie in which any node that is an only child is merged with its parent.

Patricia tries are seen as radix trees with radix equals 2, which means that each bit of the key is compared individually and each node is a two-way (i.e., left versus right) branch

In essence, a patricia tree stores a value for the given path.

The path is encoded into bytes, and then each nibble of each byte is used to traverse the tree.

It is composed of 3 different types of nodes:

The branch node

It contains a 17 element array:

  • The 16 first elements cover every representable value of a nibble (2^4 = 16)
  • The value in case the path is fully traversed.

The leaf node

It contains 2 elements:

  • The encoded path.
  • The value.

The extension node

It contains 2 elements:

  • The prefix as a segment of the path.
  • A reference to the child node (which must be a branch).

This node allows the tree to be more compact, imagine we have a path that ultimately can only go 1 way, because it has no diverging paths, adding X nodes instead of 1 representing that would be a waste of space, this fixes that.

For example, imagine we have the paths "abcdx" and "abcdy", instead of adding 10 nodes (1 for each nibble in each character), we create a single node representing the path "abcd", thus compressing the tree.

Solving the ambiguity

Since traversing a path is done through it's nibbles, when doing so, the remaining partial path may have an odd number of nibbles left, this introduces an ambiguity that comes from storing a nibble as a byte:

Imagine we have the following remaining nibbles:

  • 1
  • 01

When representing both as a byte, they have the same value 1.

Thats why a flag is introduced to differenciate between an odd or even remaining partial path:

hex char bits node type path length
0 0000 extension even
1 0001 extension odd
2 0010 leaf even
3 0011 leaf odd
[flag] + path

Terms Used

  • nibble: 4bits, half a byte, a single hex digit.

โš–๏ธ License

This project is licensed under the Apache 2.0 license.

See LICENSE for more information.

More Repositories

1

lambdaworks

lambdaworks offers implementations for both SNARKs and STARKs provers, along with the flexibility to leverage their individual components for constructing customized SNARKs.
Rust
607
star
2

cairo-vm

cairo-vm is a Rust implementation of the Cairo VM. Cairo (CPU Algebraic Intermediate Representation) is a programming language for writing provable programs, where one party can prove to another that a certain computation was executed correctly without the need for this party to re-execute the same program.
Rust
514
star
3

lambdaclass_hacking_learning_path

LambdaClass Hobby Club, hacking learning path handbook. The journey starts here!
224
star
4

starknet_in_rust

A Rust implementation of Starknet execution logic
Rust
171
star
5

erlings

Small exercises to get you used to reading and writing Erlang code
Erlang
164
star
6

options_backtester

Simple backtesting software for options
Jupyter Notebook
159
star
7

riak_core_tutorial

An up to date riak_core tutorial, using basho's riak_core, Erlang/OTP 23-24-25 and rebar3.
Erlang
149
star
8

STARK101-rs

STARK 101 Workshop in Rust ๐Ÿบ๐Ÿฆ€
Jupyter Notebook
131
star
9

sparkling_water_bootcamp

Public repository for excersices, challenges and all the needs of the Sparkling Water Bootcamp
123
star
10

concrete

Concrete is a simple programming language specifically crafted for creating highly scalable systems that are reliable, efficient, and easy to maintain.
Rust
123
star
11

cairo_native

A compiler to convert Cairo's intermediate representation "Sierra" code to MLIR.
Rust
115
star
12

ethereum_rust

Lambda Ethereum Rust Execution client
Rust
113
star
13

lambda_ethereum_consensus

Elixir implementation of an Ethereum consensus client, which offers high reliance & fault tolerance
Elixir
97
star
14

finance_playground

Juypter notebooks playground to explore and analyse economy and finance ideas
Jupyter Notebook
95
star
15

webrtc-server

Signaling and ICE servers for WebRTC in Erlang
Erlang
91
star
16

lambdaworks_stark_platinum

STARK Cairo prover using lambdaworks. Cairo (CPU Algebraic Intermediate Representation) is a programming language for writing provable programs, where one party can prove to another that a certain computation was executed correctly. Cairo and similar proof systems can be used to provide scalability to blockchains.
77
star
17

mina_bridge

Bridge from Mina to Ethereum
Solidity
76
star
18

evm_mlir

An EVM written with MLIR
Rust
73
star
19

AES_zero_knowledge_proof_circuit

Rust
70
star
20

holiday_pinger

Erlang + ClojureScript app to send holiday reminders
Erlang
69
star
21

stark_compass_explorer

Stark Compass: the only open source explorer
Elixir
68
star
22

mirra_backend

Multiplayer 2D physics engine, matchmaking, market and leaderboard for 2D and 3D Games
Elixir
61
star
23

erlang-katana

๐Ÿ‘Œ erlang grab bag of useful functions. it should have been called swiss army knife but katanas are more deadlier ;)
Erlang
61
star
24

cairo-vm_in_go

cairo-vm_in_go is a Go implementation of the Cairo VM. Cairo (CPU Algebraic Intermediate Representation) is a programming language for writing provable programs, where one party can prove to another that a certain computation was executed correctly without the need for this party to re-execute the same program.
Go
56
star
25

libtorrent-rs

A Rust implementation of the BitTorrent V2 protocol
Rust
55
star
26

yet-another-swap

YAS is Yet Another Swap on Starknet but bringing the best prices and yield to Degens.
Cairo
54
star
27

starknet_tendermint_sequencer

Starknet sequencer built with Tendermint Core
Rust
53
star
28

zksync_era_precompiles

Yul precompile library to speedup elliptic curves operations.
Rust
51
star
29

champions_of_mirra

Champions of Mirra game codebase
C#
42
star
30

circom_export_to_cairo

Export Circom verifier to Cairo
Solidity
42
star
31

starknet_stack

Starknet Stack let's you easily create new Cairo Starknet chains with their own sequencers, provers and verifiers
Rust
42
star
32

throttle

Erlang/OTP application to rate limit resource access
Erlang
40
star
33

cairo-by-example

cairo-by-example.com
Shell
38
star
34

pinocchio_lambda_vm

Zero Knowledge Virtual Machine from scratch implementing Pinocchio
Rust
36
star
35

buzzconf

A conference by devs for devs. Functional Programming, Distributed Systems, Big Data and Machine Learning Conference in Buenos Aires, Argentina
HTML
34
star
36

zksync-web3-rs

Rust
33
star
37

julia_koans

Small exercises to get you used to reading and writing Julia code!
Julia
31
star
38

noir_backend_using_gnark

A Noir's backend implementation using Gnark
Go
31
star
39

cairo-vm-py

cairo-rs-py adds Python bindings to the cairo-rs Cairo VM
Rust
23
star
40

lambdaworks_kzg

An ABI compatible for KZG EIP-4844 in Rust
Rust
22
star
41

aleo_lambda_vm

Arkworks implementation of the VM of Aleo verifiable computing model built by LambdaClass
Rust
21
star
42

simpleworks

Arkworks made simple for us: the non cryptographer software plumbers
Rust
20
star
43

era_vm

EraVM implementation
Rust
19
star
44

cairo-vm.c

cairo-vm_in_C is a C implementation of the Cairo VM. Cairo (CPU Algebraic Intermediate Representation) is a programming language for writing provable programs, where one party can prove to another that a certain computation was executed correctly without the need for this party to re-execute the same program.
C++
19
star
45

programming_bitcoin_in_rust

Implementing the book "Programming Bitcoin" in Rust
Rust
17
star
46

tornado_cash_anonymity_tool

Anonymity Research Tools for TCash Users
Jupyter Notebook
17
star
47

aleo_lambda_blockchain

Tendermint implementation of the blockchain of Aleo verifiable computing model built by LambdaClass
Rust
16
star
48

starknet_prover

15
star
49

lambdaworks_exercises

Contains several examples and challenges to use Lambdaworks
Rust
14
star
50

austral.rs

An implementation of the Austral language compiler in Rust
Rust
14
star
51

aleo_minimum_anti_collusion_infrastructure

Aleo's Minimum Anti-Collusion Infrastructure / MACI
Rust
13
star
52

starknet_rollup_on_bitcoin

Soverign rollup based on Rollkit, Cairo VM for the application layer and Bitcoin as a DA layer
Rust
13
star
53

lambda_consensus

Ethereum Consensus Client
12
star
54

starknet_kraken

Kraken is a Starknet modular decentralized sequencer implementation.
Rust
11
star
55

cairo_karnak

Cairo bytecode compiler
10
star
56

data_etudes

LambdaClass statistics, machine learning and data science etudes
Jupyter Notebook
10
star
57

reconnections

We were tired of implementing a reconnection system for our database clients so we created this
Erlang
10
star
58

find_peers

Find other erlang peers in the same subnet
Erlang
9
star
59

PLONK101-rs

9
star
60

elephant_in_the_room

Simple wordpress replacement coded in Elixir + Phoenix + Ecto + PostgreSQL + Docker
CSS
9
star
61

zksync_local_stack

Makefile
9
star
62

game_of_life_wasm

Conway's Game of Life in Rust and WebAssembly
Rust
8
star
63

elixir_riak_core

Wrapper to Riak Core for Elixir
Elixir
8
star
64

cairo_codegen-rs

A Rust library providing a builder API to generate Cairo code
8
star
65

zkRust

Rust
8
star
66

lambda_msm_fpga

Low level (VHDL) hardware description for MSM acceleration over FPGA
Python
8
star
67

curse_of_mirra_assets

Open source game assets: 3D models, 2d concept art, lore, music and more!
8
star
68

pinpon

๐Ÿ“ lambdaclass ping pong tournament and player ranking
Python
7
star
69

ieeextreme

Course material for students who want to go from zero to participating in the IEEExtreme competence using Python
Jupyter Notebook
7
star
70

entropy_hacking_learning_path

Entropy1729's Learning path
7
star
71

metal_playground

A repo for learning how to parallelize computations in the GPU using Apple's Metal, in Rust.
Rust
7
star
72

aleo_roulette

Elixir
6
star
73

cairo_finance

Cairo finance utilities
Cairo
6
star
74

lager_logstash_backend

Send lager logs to logstash
Erlang
6
star
75

lambdaworks_plonk_prover

6
star
76

bonobot

accept the mystery
Python
6
star
77

beam_prometheus_exporter

Add this to your release to get standard erlang metrics in prometheus/grafana
Erlang
6
star
78

million_requests_per_second

Trying to achieve a few millions requests per second with different languages, libraries and protocol
Ruby
6
star
79

mithril-oxide

Bindings to MLIR using the full C++ API
Rust
6
star
80

fuzzing_examples

A collection of fuzzers built using Honggfuzz and Cargofuzz tools
Rust
5
star
81

data_science_exercise

Data science exercise
Jupyter Notebook
5
star
82

blockaderl

Blockade docker API wrapper written in Erlang
Erlang
5
star
83

starknet_orb

5
star
84

ethereum_war_game_tooling

We are slow while using the UI/UX of crypto wallets so we created our CLI version
Elixir
5
star
85

zk_stack_cli

CLI tool for ZKsync, built using zksync-ethers-rs SDK
Rust
5
star
86

erlang_log_to_kibana_example

Redirect Erlang shell output to kibana via logstash
Shell
5
star
87

cairo-rs-wasm

Rust
5
star
88

starknet-replay

Provides a way of reading a real Starknet State, so you can re-execute an existing transaction in any of the Starknet networks in an easy way
Rust
5
star
89

aggregation_aligned_layer

Rust
4
star
90

guidelines

Design and coding standards for LambdaClass
4
star
91

tendermint_consensus

Tendermint Consensus is a minimalistic implementation of the BFT consensus algorithm to securely replicate state machines on multiple machines.
4
star
92

go-http-ipfs

HTTP server in Go to interact with a local IPFS node
Go
4
star
93

cairo_wnn

Cairo Weightless Neural Network
4
star
94

chaos_monkey_ex

A Chaos Monkey for Elixir that kills random processes
Elixir
3
star
95

wasm2cairo

3
star
96

merkletree_leo

3
star
97

concrete-ml-fuzzer

A differential fuzzer for `concrete-ml` and `scikit-learn`
Python
3
star
98

consensus-workbench

Proof of concept Rust implementations for various distributed systems protocols
Rust
3
star
99

lambcast

A Farcaster client implementation in Elixir
Elixir
3
star
100

zksync_seaport

Seaport implementation on zkSync Era. Seaport is a marketplace protocol for safely and efficiently buying and selling NFTs.
Solidity
3
star