←back to thread

Our modular, high-performance Merkle Tree library for Rust

(github.com)
141 points bibiver | 1 comments | 21 Oct 25 12:58 UTC | HN request time: 0s | source
Show context
bibiver ◴[21 Oct 25 12:58 UTC] No.45655191[source]▶
We've just released rs-merkle-tree, a Merkle tree crate designed with performance and modularity in mind. It comes with the following key features:

* Fixed depth: All proofs have a constant size equal to the depth of the tree. The depth can be configured via a const generic.

* Append-only: Leaves are added sequentially starting from index 0. Once added, a leaf cannot be modified.

* Optimized for Merkle proof retrieval: Intermediate nodes are stored so that proofs can be fetched directly from storage without recomputation, resulting in very fast retrieval times.

* Configurable storage and hash functions: Currently supports Keccak and Poseidon hashers, and in-memory, Sled, RocksDB, and SQLite stores.

The Rust ecosystem already offers several Merkle tree implementations, but rs-merkle-tree is built for a specific use case: append-only data structures such as blockchains, distributed ledgers, audit logs, or certificate transparency logs. It’s particularly optimized for proof retrieval, storing intermediate nodes in a configurable and extensible storage backend so they don’t need to be recomputed when requested.

replies(3): >>45656124 #>>45657554 #>>45657562 #
xpe ◴[21 Oct 25 14:16 UTC] No.45656124[source]▶
For those in the know... Do you have any recommended reading for Merkle-curious people that may have some scars from blockchain-related hype? It would be nice to find a nice introductory resource that covers some interesting use-cases that may not be well-known. Perhaps with nice graphics, interactivity, etc.?

For example, here is a slick web site that shows how certificate transparency uses Merkle trees: https://certificate.transparency.dev/howctworks/

replies(4): >>45656589 #>>45657564 #>>45658018 #>>45660006 #
1. xpe ◴[21 Oct 25 16:47 UTC] No.45658018[source]▶
I'm currently exploring how different APIs compute ETags [1]. I'm inclined to think the overhead of Merkle-trees make them relatively less useful for ETags for paginated APIs where responses are small and flat hashing is fast. One rule of thumb would be: the overhead isn't justified unless you need either (a) efficient updates on very large collections, or (b) collection-level state tracking across pagination boundaries. Sound about right?

[1]: https://developer.mozilla.org/en-US/docs/Web/HTTP/Reference/...

Also, ETags can use weak validators:

> W/ (case-sensitive) indicates that a weak validator is used. Weak ETags are easy to generate, but are far less useful for comparisons. Strong validators are ideal for comparisons but can be very difficult to generate efficiently. Weak ETag values of two representations of the same resources might be semantically equivalent, but not byte-for-byte identical. This means weak ETags prevent caching when byte range requests are used, but strong ETags mean range requests can still be cached.