Scalability Question when using Merkle tree

[formal lantern]

Let's say I am using Merkle Tree in my zkApp. As we know we only store the root of the merkle tree right. So, what if there are multiple people trying to use the function that depends on the merkle tree ?
I mean if I and two other people are trying to using a function that updates the merkle tree won't it cause problem ?

Like we all three used the function at the same time, so the updated root will be different for us which will fail the validation check right ? So, is there any solution to it ?

[compact verge]

You can check out this link: https://github.com/o1-labs/o1js/issues/659

[formal lantern]

Hi Magestrio,

Thank you so much!!
Let me check 🙌

[sleek sigil]

I don't think there is an easy solution here, and you can try to use Actions to put info about new leaves into the Actions history. Then, in your centralized server/serverless code, you can get an action list from the archive node by timer or by listening to events and processing all the additions. You do not use an on-chain reducer in this design; effectively, you have a reducer off-chain.

Then, you can update the root value on-chain or, in a more complicated design, use recursive proofs to create a proof confirming the validity of the new Merkle Tree root.
Here's the example of ZKProgram calculating such recursive proofs:
https://github.com/dfstio/minanft-lib/blob/master/src/contract/metadata.ts

Another possible solution would be probably to use Sparse Merkle Trees. You can look into an Ethereum Deposit contract that uses those trees:

https://github.com/runtimeverification/deposit-contract-verification/blob/master/deposit-contract-verification.pdf

https://github.com/ethereum/consensus-specs/blob/34fc0a5d09fae6649e0c6ac7a0cb09ff5a999957/solidity_deposit_contract/deposit_contract.sol#L80

https://medium.com/@josephdelong/ethereum-2-0-deposit-merkle-tree-13ec8404ca4f

[compact verge]

o1js already utilizes SMT

[sharp stirrup]

the easiest solution is to use a framework like Protokit, which abstracts away merkle tree operations. you can learn more from our recent workshop: https://youtu.be/hqobPb3gIRo?si=6fPgAGOLQaic7DhD

i’m happy to answer any questions regarding Protokit, as i’m one of the co authors of the framework ✌️

here’s a rough architecture of how protokit works

[long umbra]

Hello @formal lantern, thank you for the question and sorry for the late response. As far as I understand, the problem you are referring to is named as "concurrency" issue, and it exists even when you do not use merkle trees. It is very common with zkApps, and it is easily solvable with o1js 🙂 It happens when two transactions happening at the same block try to set the same old state to two different new states. As one of them got executed first, the other transaction's preconditions fail on the old state, and the second transaction is rejected. One of the easiest ways of solving this in Mina is to use the Actions & Reducer module (https://docs.minaprotocol.com/zkapps/o1js/actions-and-reducer), which allows you to push state updates as actions on chain (without updating any state), and then later to reduce actions to a single state in one transaction and update the state with all the previous transactions at once. You can see an example here: https://github.com/o1-labs/o1js/blob/main/src/examples/zkapps/voting/voting.ts. Also, there are some other questions on how to use actions and merkle trees in the Discord forum, please search the forum for more information there. I hope this was helpful 🙂

Also yes, using Protokit is a very easy solution to fix concurrency issues. I just wanted to let you know solving this problem is also very easy on native Mina / o1js, it is of course up to you to decide what is the best way to go for your spesific application 🙂

[sleek sigil]

Can you please elaborate on the method of calculating the new root inside the reducer on-chain? You need to reconstruct the full Merkle Tree for this, or, in the case of Sparse Merkle Trees, have all branches, and this info is not present in Actions and, given that it is of variable size in the case of usual Merkle Tree, cannot be passed to the reducer.
How can you deal with this issue in the Actions and Reducer module (except for having a centralized reducer off-chain)?

[sharp stirrup]

"easily solvable" is an extreme understatement

you're neglecting the issues with the voting example. it does not utilise recursive proofs, therefore there are systemic issues such as not being able to keep up with reducing all pending actions to fit into the last 5 known sequence state hashes. Since the action batch is fixed, this is something you can very very easily run into and its out of your control - except if you use recursive proofs. And once you start designing your own recursive proof framework, you will end up designing protokit

as @sleek sigil is saying you are not gonna be able to decentralise the reducer unless you have data availability, and if you want to throw data availability into the mix, it becomes everything but easy to ensure all security guarantees are met - like data is being available for others to participate.

Then if you start working with large trees, even using recursive proofs, you will hit circuit limits, then you will start splitting up your circuits and eventually you will design protokit again.

[long umbra]

You can pass merkle paths (witnesses) to the reducer API, which will allow you to calculate the new root for the associated node update. You can see this in the voting example I have shared above. The example is developed by O(1) Labs, and it is working as far as I know. It is using a merkle tree to represent the state of voters and updates it to prevent voters from illegal voting. It is achieving this by using the Reducer module, so I think it is a valid solution for updating Merkle trees without concurrency problems

[sharp stirrup]

it "works" because the tree height is 3 🤌

[long umbra]

The reduce amount depends on the actual application needs. For a zkApp with very very heavy user load, you may be right and Reducer module may not be enough to allow keeping track of latests states, thus you may need to implement a recursive proof structure. However, this depends on the application needs, and I think it is important to share solutions that do not need a sequencer

[sharp stirrup]

you'd need to limit the amount of dispatched actions in places where dispatch is called, otherwise the systemic risk still remains and you have no other means of prevention or recovery

[long umbra]

This is also a right approach, and of course using Reducer API can be considered to be hurting the DA. However, this also depends heavily on the application needs

[sharp stirrup]

this means you can have 8 votes in the tree 😄

[long umbra]

All I try to emphasize is that the actual application makes the entire difference, and I do not feel it is logical to compare different approaches existing on Mina blockchain without knowing the zkApps spesifications

[long umbra]

Great point, but please always consider needs always depend on the actual application 🙂

[tardy pine]

Here's my take @formal lantern.
I agree with @sharp stirrup and @sleek sigil that achieving racing-free and decentralized Merkle tree is complicated. But definitely doable IMO.

The approach that I would try to take is to either use Protokit, or, if you want to do it on the L1:

• Put new Merkle leaves on chain in the form of actions/events (this guarantees native L1 data availability)
• In the reducer, perform updates to the onchain Merkle root. Whoever runs the reducer needs to know the Merkle tree (it can always be rebuilt from actions/events which can be pulled from an archive node.)
• In the reducer circuit, you pull in your MerkleWitness in a Provable.witness() block. The Merkle tree itself should never be part of the circuit, only witnesses.

I've implemented those ideas here: https://github.com/mitschabaude/o1js-offchain-state/blob/main/contracts/src/Offchain.ts (Beware: this isn't production code. It's just storing the Merkle tree in memory. But the circuit code should provide a good example)

To overcome the static size of actions a circuit can process, my example only processes a fixed batch of actions, and then uses a recursive proof which connects the last processed action to the current onchain action state. The recursive proof is very simple and can handle 100s of actions per proof. And it's very generic (doesn't have to be rewritten per project)

However, the more efficient solution would probably be to put the entire reducer logic (including Merkle updates) in a recursive proof. It will still be heavy though, and a downside is that the recursive part becomes application specific.

Some things to highlight from my example code:

Pulling in Merkle witnesses in Provable.witness():

let witness = Provable.witness(MyMerkleWitness, () => {
  return new MyMerkleWitness(
    tmpTree.getWitness(keyCommitment.toBigInt())
  );
});

Before running the reducer logic, I actually clone the tree and update a tmp tree within reduce(), but outside the circuit. The outside the circuit part is run in Provable.asProver():

// also update the tree! (not part of the circuit)
Provable.asProver(() => {
  // ignore dummy value
  if (isDummy.toBoolean()) return;
  tmpTree.setLeaf(keyCommitment.toBigInt(), valueCommitment);
});

Unfortunately these patterns to move back and forth between in-circuit and out-of-circuit logic are not very well documented, I want to change that when I have time

[storm ocean]

Here's another example of solving concurrency issues by using Actions and Reducer, @formal lantern.

People register their accounts concurrently by emitting actions. They also fund their accounts and spend their funds through actions. Then the server sets a range for the actions that it is going to process, and process it, while users can keep emitting actions even if the range hasn't been finished to be processed.
https://github.com/chrlyz/proof_of_commitment/tree/main

I would explore @tardy pine's solution, but having more examples never hurts 😃