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

[ismax]

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

Some ways to use ZK-SNARKs for privacy

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) ?

[ismax]

I just saw this answer from @fabrice :

Approval program's length

How are you planning to keep the biometrics secret and to prevent a user to re-use submitted biometrics for authentication? Note that everything on-chain is completely public to everybody. In particular, if a user submits their biometrics to a smart contract, they will be displayed to all users. You might be able to use SNARK / zero-knowledge for that purpose but current limitations on TEAL do not allow for verification of a SNARK.

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]

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:

• Circuits
• Core Deposit Circuit

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.

[ismax]

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)