rs-merkle-tree

Codecov (with branch)

GitHub License

다음과 같은 기능을 갖춘 Rust의 Merkle tree 구현체입니다:

• 고정 깊이(Fixed depth): 모든 증명(proof)은 Depth와 동일한 상수 크기를 가집니다.
• 추가 전용(Append-only): 리프는 인덱스 0부터 순차적으로 추가됩니다. 한 번 추가된 리프는 수정할 수 없습니다.
• Merkle proof 검색 최적화: 중간 리프를 저장하여 Merkle proof를 지연 계산할 필요 없이 메모리에서 가져올 수 있으며, 이는 매우 빠른 검색 시간을 보장합니다.
• 루트까지의 바닥 및 중간 리프 저장을 위한 구성 가능한 스토리지 백엔드(Configurable storage backends).
• 노드를 해시하기 위한 구성 가능한 해시 함수(Configurable hash functions).
• 간단하고 사용하기 쉬운 인터페이스: add_leaves, root, num_leaves, proof.

rs-merkle-tree를 Rust의 Cargo.toml에 의존성으로 추가하세요.

[dependencies]
rs-merkle-tree = "0.1.0"

다음과 같이 Merkle tree를 생성하고, 리프를 추가하며, 리프 수를 얻고, 주어진 인덱스의 Merkle proof를 얻을 수 있습니다. 이는 keccak256 해싱 알고리즘, 메모리 스토리지, 깊이 32를 사용하여 간단한 merkle tree를 만듭니다.

use rs_merkle_tree::to_node;
use rs_merkle_tree::tree::MerkleTree32;

...

다음과 같이 다른 스토어, 해시 함수 및 깊이를 선택하여 트리를 사용자 정의할 수 있습니다. 이때 feature를 수정해야 합니다. 이렇게 하면 필요하지 않은 부분을 가져오는 것을 방지할 수 있습니다. 다음 예시들을 참고하세요.

깊이: 32 | 해싱: Keccak | 스토어: sled

[dependencies]
rs-merkle-tree = { version = "0.1.0", features = ["sled_store"] }

use rs_merkle_tree::hasher::Keccak256Hasher;
use rs_merkle_tree::stores::SledStore;
use rs-merkle-tree::tree::MerkleTree;
...

깊이: 32 | 해싱: Poseidon | 스토어: rocksdb

rs-merkle-tree = { version = "0.1.0", features = ["rocksdb_store"] }

use rs-merkle-tree::hasher::PoseidonHasher;
use rs-merkle-tree::stores::RocksDbStore;
use rs-merkle-tree::tree::MerkleTree;
...

깊이: 32 | 해싱: Poseidon | 스토어: sqlite

rs-merkle-tree = { version = "0.1.0", features = ["sqlite_store"] }

use rs_merkle_tree::hasher::PoseidonHasher;
use rs_merkle_tree::stores::SqliteStore;
use rs_merkle_tree::tree::MerkleTree;
...

깊이 (Depth): 32 | 해싱 (Hashing): Keccak | 저장소 (Store): file

rs-merkle-tree = { version = "0.1.0", features = ["file_store"] }

use rs_merkle_tree::hasher::Keccak256Hasher;
use rs_merkle_tree::stores::FileStore;
use rs_merkle_tree::tree::MerkleTree;
...

테스트 (Tests)

모든 테스트 실행하기

cargo test --all-features

저장소 (Stores)

다음 저장소가 지원됩니다:

• rusqlite
• rocksdb
• sled
• file: 디렉터리 내 레벨별로 하나의 파일을 유지하는 플랫 저장소(데이터베이스 엔진 없음).

해시 함수 (Hash functions)

다음 해시 함수가 지원됩니다:

• keccak256
• Poseidon BN254 Circom T3

벤치마크 (Benchmarks)

다음 항목들은 MacBook Pro M4 24GB에서 측정되었습니다:

• 사용된 디스크 크기
• 초당 천 단위의 리프 삽입 처리량(throughput).
• Merkle 증명 생성 시간.

다음 명령어로 실행할 수 있습니다:

cargo bench --features=all

그리고 다음 테이블을 생성할 수 있습니다.

python benchmarks.py

add_leaves 처리량 (throughput)

proof 시간 (time)

라이선스 (License)

MIT License