This forum is a read-only archive. Posting, replying and signing in are disabled.

Is AVM/TEAL compatible with verification of ZK-SNARK proof?

Uncategorized
ismax
ismaxIsmael EL ATIFI

I just read this post on Vitalik’s blog about ZK-SNARK :

I am interested in implementing the part “ZK-SNARKs for coins” of the article into an Algorand smart contract (the Verifier code).

Basically we need to store on-chain 2 sets of hashes :

  • hashes of type L when coins are created
  • hashes of type N when coins are spent

The smart contract needs to verify the (off chain made) ZK-SNARK proof proving that :

  • some L and N hashes come from the same secret (i.e. the prover is allowed to spend the coin L)
  • the L hash is indeed in the set of hashes L (i.e. the coin L exists)
  • the N hash is not in the set of hashes N (i.e. the coin L has not been already spent)

So I wonder if this is actually possible to implement the Verifier for this with current AVM and TEAL/PyTEAL (at least with small number of coins for a Proof Of Concept) ?

✔ Solved by HashMapsData2Value in post #3
edited
ismax
ismaxIsmael EL ATIFI

I just saw this answer from @fabrice :

So I’m afraid the answer to my question is no (as I need to implement verification of a SNARK in a smart contract).

HashMapsData2Value
HashMapsData2ValueYaredRegular

The answer is no. But work is being done here AVM: EC math by jannotti · Pull Request #4924 · algorand/go-algorand · GitHub that will add the ability to perform pairing checks, which are necessary to verify groth16 type ZK-SNARKs. The type used in e.g. Tornado Cash:

You are proving that you know (from Algorand account B) of a path in a merkle tree to the root (that you have contributed to, but from Algorand account A) without actually revealing the path (as that would reveal that account B is linked to account A). A nullifier is also provided ensuring that someone can only make this proof of the particular path once.

Another way of describing it is proving that withdrawer account B is actually a member of the set of depositors (among which account A is included), without actually revealing which exact member.

✔ Solutionedited
ismax
ismaxIsmael EL ATIFI

Thanks a lot for your answer and links !
I’m glad this is something being worked on, and I look forward to try those new AVM features for ZK proof verification when they will be released.

(By the way the use case you described is exactly the one I want to implement)