search

hyperledger-labs / zeto

Privacy-preserving implementations of fungible and non-fungible tokens, using UTXO as the underlying transaction model
Apache License 2.0
20 stars 9 forks source link

Nullified with merkle tree root #34

Open alexcostars opened 1 month ago

alexcostars commented 1 month ago

Considering this quote: "The merkle proof is validated against a merkle tree root that is maintained by the smart contract."

In a scenario where we have a network with thousands of participants executing high-frequency transactions with this token, will this solution create many reverted transactions?

Let's me explain:

Imagine that Alice is about to send a UTXO to Bob and, at the same time, Mark is about to send a UTXO to Rebecca. Let's consider this order of execution of actions:

  1. Alice obtains the merkle tree root, to generate zkp_proof(merkle tree root hash)
  2. Mark obtains the merkle tree root, to generate zkp_proof(merkle tree root hash)
  3. Mark computes transaction data, generating all the proofs
  4. Alice computes transaction data, generating all the proofs
  5. Mark sends the Ethereum transaction to his node, which is broadcasted to the network
  6. Alice sends the Ethereum transaction to her node, which is broadcasted to the network

In this scenario, step 6 will fail, right? Because Alice is sending a transaction with an invalid proof, as the merkle tree root was modified by Mark in step 5.

Chengxuan commented 1 month ago

Hi @alexcostars , that's a great question.

When Alice and Mark spend the same UTXO, they'll unavoidably clash, and one will redo the transaction by selecting another UTXO. But with a good selection strategy and the randomness provided, the chance they select the same UTXO should be low in a high-volume transaction system.

I think the question you had is about when Alice and Mark spend different UTXO, because in step 5, Mark's transaction will change the merkle tree root, which would have invalidated Alice's merkle tree proof. Because of this concern, the contract validates merkle tree proof against all historical roots: https://github.com/hyperledger-labs/zeto/blob/b1be3ba230ee19d4fcf90fd7a59c074f9b9db109/solidity/contracts/lib/zeto_nullifier.sol#L82

Therefore, in step 6, the contract will be able to validate Alice's MTP using the one of the previous merkle tree roots.

jimthematrix commented 3 weeks ago

Thanks @Chengxuan for the response.

@alexcostars great question. Hope the above details sufficiently addressed your question. The mechanism of checking history roots works because in the smart contract we have an append-only tree. As long as the clients follow the same order as the smart contract to insert the leaf nodes, by using the orders dictated by the blocks and the transaction indexes inside the blocks, they will be able to calculate legitimate roots that can be recognized by the contract.

alexcostars commented 2 weeks ago

I'm following your explanation. I didn't realize that the smart contract stores all historical states of the tree roots. In this case, the problem is solved, but a new question arises: Is this chain scalable to an ecosystem with millions of transactions? Do we need a security implementation to remove items from this object?

jimthematrix commented 2 weeks ago

The merkle tree implementation uses a 256-bit key for the index of the leaf nodes, so it can accommodate enough UTXOs to fill up the entire universe (it's a larger number than the total number of atoms in the known universe). What's unclear is the performance implications when the onchain state gets bigger and bigger. But Ethereum mainnet today already deals with a scale similar to this, so hopefully how the public mainnet behaves today is a good indicator.