Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Our modular, high-performance Merkle Tree library for Rust

github.com

Post reply on HN
Print view View original

21–30 of 33 posts

Re: Our modular, high-performance Merkle Tree library for Rust

#21

Post by xpe »

xpe wrote: post #4
bibiver wrote: post #2

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 retrieva…

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://cer…

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.

Re: Our modular, high-performance Merkle Tree library for Rust

#22

Post by dafelst »

NoahZuniga wrote: post #11
bibiver wrote: post #2

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 retrieva…

Blockchains are an alternative way to make an append only data structure, so it's not clear why you would want to use a merkle tree to create a block chain.

Doesn't bitcoin use merkle-trees internally to create its blockchain?

Re: Our modular, high-performance Merkle Tree library for Rust

#23

Post by bibiver »

vlovich123 wrote: post #10

Nice. Since I/O is typically asynchronous, any ideas on how an async storage backend could be integrated elegantly? Also do you have any benchmarks in the repo that would stress the I/O layer for latency too?

open to integrate async storage backends. do you have one in mind? more benchmarks coming.

Re: Our modular, high-performance Merkle Tree library for Rust

#25

Post by tromp »

NoahZuniga wrote: post #11
bibiver wrote: post #2

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 retrieva…

Blockchains are an alternative way to make an append only data structure, so it's not clear why you would want to use a merkle tree to create a block chain.

A blockchain can use Merkle trees in several ways. First, the block header usually contains the Merkle root of all transactions. This makes the header, and in turn the Proof-of-Work, commit to all txs, which helps make the chain immutable. Second, the header can also directly commit to the UTXO set, simplifying the design of light clients (sadly, Bitcoin doesn't do this).

Re: Our modular, high-performance Merkle Tree library for Rust

#27

Post by raphinou »

xpe wrote: post #4
bibiver wrote: post #2

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 retrieva…

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://cer…

I'm working on a project where I need to prove that a file in a git repo is append only, ie all changes to the file only added lines. The only way I can think of is looking at the git history of the file, but would there be a faster way using Merkel trees somehow?

Re: Our modular, high-performance Merkle Tree library for Rust

#28

Post by Retr0id »

geopert wrote: post #14

nice crate thanks. I wasn't expecting sqlite to be faster than rocksdb, which is key-value. The way you store the leaves (level, index) should be super fast for a key-value store.

This surprised me too. My guess is that while rocks is typically faster for write-heavy workloads, inserting into the merkle tree actually require a fair few reads as part of the process (but I haven't looked closely).

Re: Our modular, high-performance Merkle Tree library for Rust

#29

Post by Retr0id »

NoahZuniga wrote: post #12
bibiver wrote: post #2

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 retrieva…

How are you supposed to show that two tree heads are consistent?

Isn't the whole point of a merkle tree that you just... compare them?

Re: Our modular, high-performance Merkle Tree library for Rust

#30

Post by jmount »

raphinou wrote: post #27
xpe wrote: post #4

Earlier quoted context omitted.

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://cer…

I'm working on a project where I need to prove that a file in a git repo is append only, ie all changes to the file only added lines. The only way I can think of is looking at the git history of the file, but would there be a faster way using Merkel trees somehow?

Is this trying to deal with that git history can be replaced?
Post reply on HN