I was curious about how to validate proofs exported from merk.js and reading the code, I wasn't entirely sure. For the purpose of this issue, I just care about existence proofs for exactly one value (it seems you return general range proofs by default, maybe simpler to focus on one case).

The code seems to be this: https://github.com/nomic-io/merk/blob/master/src/verify.js#L15-L47

This is my understanding:

A child node contains {key, value} (both strings) An inner node contains {left, right, kvHash}

• left and right are either null?, a reference to another node (recurse), or the hash of that subset of the tree.
• kvHash is ??? (data stored in inner node also?)

In the case of serialized proofs, I would assume for every inner node, either left or right is a base64 hash of the subtree, and the other one is a reference to the child node leading to the leaf of interest.

So far, so good. The hash for a leaf node also seems quite simple:

function getKvHash ({ key, value }) {
  let input = Buffer.concat([
    VarString.encode(key),
    VarString.encode(value)
  ])
  return ripemd160(sha256(input))
}

varint length prefix the key and the value, concatenate, then hash. Solid.

But... looking at:

function childHash (child) {
  if (child == null) {
    return nullHash
  }
  if (typeof child === 'string') {
    return Buffer.from(child, 'base64')
  }
  if (typeof child === 'object') {
    return getHash(child)
  }
  throw Error('Invalid child node value')
}

function getHash (node) {
  let kvHash = node.kvHash
    ? Buffer.from(node.kvHash, 'base64')
    : getKvHash(node)

  let input = Buffer.concat([
    childHash(node.left),
    childHash(node.right),
    kvHash
  ])
  return ripemd160(sha256(input))
}

It seems that the hash of a child node is not just getKvHash, but getHash. Given left and right are both null for the child node. This ends up like:

kvhash = ripemd160(sha256(key.length || key || value.length || value))

Then one step that treats it like an inner node childHash = ripemd160(sha256([0, 0, ... (40 bytes 0)] || kvhash))

The inner node would be:

innerHash = ripemd160(sha256(child.left || child.right || inner.kvhash))

And then what is inner.kvhash?

I'd love to understand this algorithm well, and be able to validate it in another language (eg. go) as a step towards unifying merkle proofs on the road to ibc

I was surprised to read in https://github.com/nomic-io/merk/tree/develop#benchmarks that getting a proof is faster than a read!

I then looked at the code, in particular read and prove and realized that they create keys differently. Notably, read always queries an existent value, while prove queries a random value (which is not in the store).

I think you should update the benchmark to prove one value guaranteed to be in the store.

I also note the setup uses different batch sizes for writing, although I don't think this will affect the performance. It just seems like something else nice to normalize.

The proof format already supports range queries, but there isn't currently a way to use them. We will need the prover to include boundary keys to create a verifiable range proof, then verify the boundaries and ensure there are no missing nodes within the range on the client.

prove and verify_proof take in lists of keys, but we'll replace that with a Query type which contains a combination of unique keys and ranges to be included in the proof, or checked on verify.

One question will be whether verify_proof will still need to know about the list of queried keys (currently required to know which values to return and which keys to check for absence proofs). We could instead just verify the proof against the root hash, then have a type (e.g. Proof) which makes it easier to pull out data (by key or range), can check for arbitrary absence proofs, and can verify arbitrary ranges (either by keeping track of all contiguous KVNode ranges on the initial verify pass, or by going back into the proof data and checking them when a method is called).

Not a big deal, but one suggestion I have is to changeTreeOp::Put(&'a[u8]) to TreeOp::Put(Vec<u8>). Why?

1. The consumer Node.value is already a Vec<u8>
2. It simplifies TreeOp a bit (lifetime is not needed)
3. It's easier to use Put(Vec<u8>) from external calls - (again simplifies lifetime stuff)

With IAVL I believe it was (is) a best practice to sort transactions before committing them to the tree. Is this true for merk as well? Looking through the code it doesn't appear that it's doing so. Great work by the way...

This module can be easily optimized by porting performance-critical components (e.g. the tree operations) to a language that compiles to wasm (likely Rust). Also probably makes this module less prone to critical vulnerabilities since it's hard to reduce the complexity of this code and it pushes JS to its limits.

Using verify query on light clients would require them to be supplied with the expected root hash, in addition to the proof, keys and signature. Since the proof already contains the root_hash, and any other root hash wouldn't match for the signature, it would be optimal not to send it.

The change requested decomposes verify_query into a new function query_proof_root that returns the root hash as well as the result of querying the keys.

Closes #40

Description:

This branch makes changes to querying so that we can also query for ranges of keys rather than just individual keys.

Due to this change, we no longer return data from proofs just as a simple mapping of values for each queried key, but create a proofs::query::Map type which contains data for a verified proof, and verifies individual keys or ranges as they are pulled out by a consumer (so that we can, for instance, ensure the proof included all data for a desired range).

We also restructure some internal modules - namely renaming proofs::verify to proofs::tree since it contains the core Tree type (which represents a partial Merk tree when verifying a proof), and move the query-specific logic (as opposed to chunk proof logic) into proofs::query.

TODO:

• [ ] Add test coverage for newly added code

We'll need to store some auxiliary data in the store such as the most recent blockchain height or version information, which doesn't need to be part of the Merkle tree but will still need to be part of the same atomic commit. This should probably be stored in a separate column family.

We can possibly create a method like apply_aux(tree_ops: Batch, aux_ops: Batch).

This WIP PR contains the changes I have been working on for the past few months, which have over time replaced all parts of the existing codebase. While the tree algorithms have not changed and feature-wise it is in the same place as a few months ago, the internal types and interfaces have changed a lot and have resulted in much better code (the second time around I'm more experienced with Rust).

Main improvements:

• Caching/pruning - It is now possible to keep some or all tree nodes in memory across batches, meaning we don't have to fetch them from disk. This results in ~2.5x single-core performance increases if the entire tree can be held in memory, with the bottleneck then being disk writes.
• Succinctness - Comparable functions have been reduced by 50% LOC throughout the codebase.
• Maintainability - Saner abstractions in the internal interfaces, it will be much easier to change the code in the future.
• Performance - Compared to the previous benchmark of 18k updates per second, we can now get ~32k on a single core with <30MB memory usage (or 76k with the tree fully held in RAM) due to various optimizations. (These figures are on my 2017 MBP, with a 1M node tree).

I'll finalize this PR once the core Merk store API is finished, leaving it where the master branch currently is.

I stored a bunch of data and when querying on one key, get results for a different key back.

Please see https://github.com/confio/proofs-merk#issues-found

Code to reproduce https://github.com/confio/proofs-merk/blob/master/index.js#L45-L82

Am I mis-using the merkle tree?

Using verify query on light clients would require them to be supplied with the expected root hash, in addition to the proof, keys and signature. Since the proof already contains the root_hash, and any other root hash wouldn't match for the signature, it would be optimal not to send it.

The change requested adds a new function that executes the proof and returns the root hash and the elements. That root hash can then be verified by a signature scheme.

Hi, I am sorry to bother you guys and put my question in here which might not be the correct place. I have been looking for a Merkleized KV store for my project and this Merk looks pretty nice to me. After looking into the latest release 'v2.0.1' for a while, I noticed that the Merk is still using rocksdb 0.14.0 instead of 0.15.0, which is now being used in develop branch of Merk.

The question is that can I simply point underlying rocksdb to 0.15.0 on a fork of Merk "v2.0.1" and assume that everything will be working fine if "cargo test" pass? The reason I wanted to upgrade to rocksdb 0.15.0 was that it provides both upper_bound and lower_bound options for iterator. I appreciate it if any of you guys could help me on this. Thanks a lot.

Nodes are currently stored in individual Boxes, but this means we make a heap allocation for each new node and also don't get any cache locality.

Instead, we should store nodes in pages organized by the shape of the graph (e.g. the root of that subtree is node 0), then make a reference type which stores the reference to the containing page and the node index within the page (while also somehow respecting there borrow checker rules).

Each node must contain the keys of its children in order to be able to traverse the tree. This adds significant overhead compared to the actual data itself, especially when keys are long.

Since a node's children's keys will often be very similar to it's own and only differ at the last few bytes, we can cheaply shave down that data by instead storing keyA XOR keyB, removing leading zeroes. When traversing, we can expand into the full key by XORing once again with the parent node's key.

We also have to handle keys which are a different length, and this can be done with a second vector of additional bytes which are not part of the XOR.