A reference / document / README on MerkleTree design or decisions?

[Olshansk]

I've been looking (not too deeply) at the jellyfish and seahorse libraries and wanted to ask for a pointer or a link to a good resource on the design & decisions around the MerkleTree and KV store.

1. Choice of Ternary tree

In src/merkle_tree.rs, it says:

At a high level the Merkle tree is a ternary tree

Q1: What was the reasoning behind a ternary tree specifically?

2. Sparse Tree Implementation

In seahorse/src/sparse_merkle_tree.rs, a SparseMerkleTree was implemented.

Q2: I did not dive to deep into the implementation and was wondering if it followed a standard design (e.g. JMT, PMT) or other?

3. Key-Value Storage Databse Engine

From the CAPE System Components page, I found the following:

Alternative implementations of CAPE relayers may maintain a lightweight state of the CAPE system, allowing the relayer to validate CAPE transactions locally before forwarding them to the CAPE contract on Ethereum

Similarly, from another section on the same page:

The records Merkle tree stores every record commitment produced in the system. The CAPE smart contract stores a small digest of this set called the Merkle root

Q3: What is the key-value store database engine backing this?

[chancharles92]

Q1: What was the reasoning behind a ternary tree specifically? Our Rescue hash instantiation is 3-input-1-output. The ternary tree doesn't increase the required number of hash calls but decrease the tree depth, which enables more efficient Merkle membership proofs.

I'll delegate question 2, 3 to @zhenfeizhang or @tri-joe

[tri-joe]

Q2: I did not dive to deep into the implementation and was wondering if it followed a standard design (e.g. JMT, PMT) or other?

Technically that name is a bit of a misnomer. It is a sparse representation of an append-only Merkle tree, as the only modification it supports is push(). @shenkeyao @bfish713 any thoughts on potentially updating the name so it doesn't clash with key-value sparse merkle trees?

[tri-joe]

Q3: What is the key-value store database engine backing this?

The records merkle tree is a cryptographic accumulator, so the exact place that the data gets stored depends on how it is being used. In most cases we only store sparse representations: either the top level digest, a sparse "frontier", or some collection of specific merkle paths.

The seahorse keystore replays blocks to construct a sparse record merkle tree in memory, then uses that sparse tree to calculate the merkle paths it needs to store locally. The merkle paths get used to prove in zero knowledge that the records you are spending in a transaction already exist in the CAPE state.

[shenkeyao]

@shenkeyao @bfish713 any thoughts on potentially updating the name so it doesn't clash with key-value sparse merkle trees?

Yeah, we should rename it. I added an issue to Seahorse: https://github.com/EspressoSystems/seahorse/issues/229.

[Olshansk]

@chancharles92 @tri-joe Thank you very much for the very quick responses.

Going to keep researching and learning, but this definitely helped clarify things.

[zhenfeizhang]

Closed -- seems like the discussion is resolved and action will be taken in https://github.com/EspressoSystems/seahorse/issues/229.