anonklub / anonklub Goto Github PK

The proof of concept circuit is likely to take ~150s on a large machine, which basically requires outsourcing computation to a trusted server who would know your identity.

Halo2 will hopefully have faster prover time if properly optimised. We can tradeoff prover and verifier time in halo2 by changing the width of the circuit (details here), or changing the polynomial commitment (examples here)

Overview

Tornado cash is being censored at the validator level due to regulatory compliance issues, so it might be useful to create a way to get funds out while being compliant. One idea is a gateway contract that checks whether a withdrawal is legal, where the set of legal transactions is defined by the contract (and controlled by the regulators), and the withdrawer remains private amongst the legal transactions.

I argue that ECDSA is not necessary for a compliance gateway because the best design is a simple transaction whitelist.

There are 4 basic methods to implement this: user whitelist, user blacklist, tx whitelist, and tx blacklist.
Regulators probably won't accept blacklists because they are easy to beat if the attacker can withdraw their funds faster than the regulators update the blacklist. Less importantly, blacklists are slightly more complex, requiring 2 merkle proofs, whereas whitelists require 1.
I argue below that any user whitelist would have to implement a tx whitelist anyway, making the user whitelist redundant.

Tx whitelist vs User whitelist

In a tx whitelist gateway, the contract contains the merkle root of all the explicitly permitted transactions. The user makes a zkp that proves knowledge of a note in the permitted merkle tree and outputs some nullifier. Then the gateway contract calls the tornado cash contract with the normal withdrawal zkp, provided that the nullifiers in both proofs are the same.

Naively, a user whitelist gateway is similar: the contract contains the merkle root of all the explicitly permitted users. The user makes a zkp proving they are allowed in the set using ecdsa. Then gateway contract calls the tornado cash contract with the normal withdrawal zkp.
However, in this naive implementation there is no link between the signer and the withdrawal. For example, an attacker could use a whitelisted account to withdraw funds they deposited with a non-whitelisted account. To implement a link between the signer and withdrawal you probably need tx whitelist, making the user whitelist redundant.

One application of zk-ecdsa is building a new version of tornado cash where the user doesn't need to manage the custody of a secret note (see product vision). In tornado cash the secret note is partially used as proof of membership, and partly as a nullifier to prevent double spend.

The obvious way to write an ecdsa-tornado circuit is to:

• verify an ecdsa signature of a message specifying a particular deposit
• prove membership in the deposit merkle tree
• output the hash of signature as a nullifier

However, the a signature of a hash doesn't work as a nullifier because ECDSA is non deterministic in that a signer can make n different signatures for the same messages (where n is very large for secp256k1.

There might be some way to solve this with deterministic ECDSA.

Include pages to describe the design of circom circuit in the docusaurus website. (reuse blog content)
https://github.com/privacy-scaling-explorations/e2e-zk-ecdsa/tree/main/docs/docs

Explore performing membership proofs using KZK and caulk+.

Benefits:

• faster proof generation
• faster insertion

https://geometry.xyz/notebook/geometry-presents-semacaulk-a-gas-efficient-zero-knowledge-set-membership-protocol

Different approach:
helping people constructing polynomial commitments instead of merkle trees.

objective

to expose proving server's http endpoint, which resides in private network, to the public internet

solution

attach ELB to EC2 instance

proving service

https://github.com/privacy-scaling-explorations/e2e-zk-ecdsa/tree/main/apis/proving

other consideration

using IaC tool like Pulumi to maintain infra configuration by code

note: 3000 port should be routed to public dns

A significant limitation of the current protocol is that strictly speaking, the proof is only valid for 1 block: the block at which the anonymity set was fetched.
Transactions post this block will alter blockchain state so that an address A which was part of the anonymity set at block N, may be out of at block N+1.
So the claims are actually only "I was a member of this group at block N".
This is a weak claim to build any anonymous application on.
How could we strengthen this claim to turn into something closer to "I have been a member of this group since block N ..."?

Improvement ideas

Let N be the latest block and N' the block mined 1 year ago.
What about collecting the anonymity sets for multiple blocks between N and N', build the corresponding proofs and finally aggregate them into a final proofs?

• check all blocks between N and N'
  This is the strongest claim (100% confidence). But that is impractical (impossible) to fetch all the corresponding data. Between N and N', 2 628 000 blocks are mined (24 * 3600 * 265 / 12s). For a token hold by ~1M addresses (e.g USDC), that is 2.628e12 balances data points.
• check only blocks N and N', aggregate corresponding proofs P and P'
• check blocks N, N' and a random block N'' between N and N', aggregate corresponding proofs P, P' , P''
  Best option?
  Stronger claim than when just fetching for N and N', without requiring fetching too much extra data.

https://github.com/marketplace/actions/add-an-issue-link

Protect access to zk proofs static files by e.g a JWT?

https://docs.github.com/en/actions/using-workflows/reusing-workflows

Right now we use a general purpose instance type.
See https://instances.vantage.sh/
We should pick an instance that has more CPU in the same price range: $100-$300/month.

Related discussion

It is more efficient (circuits have less constraints) to use public keys as inputs instead of addresses.

• Public key can be recovered from a signature (eth client api libraries include methods to do that easily, e.g ethers.recoverPublicKey).
• signature (r, s, v values) can be recovered for a given transaction with eth_getTransactionByHash
• getting a transaction hash for a given address is the only challenging task, there is no convenient json RPC method to do that (like getTransactionByAddressAndNonce(address, nonce)). So we need to either
  • look for it ourselves (scan past blocks until we find a tx hash) for each address (and maybe cache that): not very efficient
  • or use pre indexed data: better
    • index ourselves: will involve dev and hosting costs
    • rely on indexing services: better
      • centralized: google bigquery, dune
      • dencentralized: the graph: probably ideal solution, will involve GRT costs

no front end developed yet, create a dummy image to be able to test deploying the full app on a k8s cluster

Replace snarkjs by rapidsnark to generate proofs faster.

We can prove membership in a list of addresses by:

• Signing a message (probably where the message is a challenge determined by the verifier to avoid replay attacks)
• Creating a zkp (possibly done by a trusted server) where:
  • We verify the signed message using zkecdsa
  • We recover the address from the signed message
  • We prove that the signer is in a given set using a merkle proof

There are existing implementations in circom for poseidon merkle trees and ecdsa signature verification, and proving membership just requires combining the two together.

WIP branch

Add an expiration queue to automatically delete the zk proofs files on the server. Either after some time,
or after one GET requests has been made to fetch them.

Create or reuse an existing k8s cluster.

• #134
• create docker image for query api (already available)
• #135
• #136
  • query api deployment & service
  • proofs server api deployment & service
  • docs deployment & service
  • a redis instance
  • persistent volume?
  • a font end deployment & service
  • nginx ingress
    • /api/query: query-api service
    • /api/prove: proving api service
    • /docs: redirect to https://privacy-scaling-explorations.github.io/e2e-zk-ecdsa/
    • / (catch all): front end service
• wire deployment into gh action CD pipeline

Dune free tier now includes api credits.
So no need to use custom dune-ts lib anymore. We can directly use a dune api key instead or a lib that needs the api key, eg https://github.com/cowprotocol/ts-dune-client

Docker image build in GH deployment workflows keep failing.
https://github.com/privacy-scaling-explorations/e2e-zk-ecdsa/actions/runs/5134613003/jobs/9238863928#step:4:197
To debug... as locally it works fine.
Apps need to be redeployed manually atm with:

flyctl deploy \
            --config ui/fly-{prod,staging}.toml \
            --dockerfile ui/Dockerfile \
            --local-only

Description

https://github.com/marketplace/actions/add-to-github-projects

Use snarkjs npm lib instead of sync command.
See usage https://github.com/iden3/snarkjs#using-node

This way snarkjs doesn't need to be installed globally (makes remote server setup easier)

• Circom prover API should handle bad requests errors.
  #83 (comment)

• #96
  It is hard to debug why the server times out or crashes right now

Deploy anonklub app with the following architecture (to be confirmed):

graph TD
 linkStyle default interpolate basis
 ip((Client))<-.->router{<center>Ingress NGINX<br><br>http<strong>s</strong>://anonklub.xyz<br></center>}
 
 subgraph k8s cluster


 router--->|/|ui[<center>UI</center>]
 router--->|/docs|docs[<center>Docs</center>]
 router--->|/api/proof|proof[<center>Proof API</center>]
 router--->|/api/query|query[<center>Query API</center>]

subgraph Pod + Service
ui(UI<br>container)
 end

subgraph Pod + Service
docs(docs<br>container)
 end

subgraph Pod + Service
proof(proof<br>container)
end
redis<-->proof
subgraph PVC + Pod + Service
redis[(Redis)]
end

subgraph Pod + Service
query(query<br>container)
 end

 end

Need to page over queries result.
Should be possible with graph-client built-in auto-paging feature..

Otherwise will need to page over results manually.

Current /punk endpoint return only 100 addresses while there are 3k+ crypto punks owner.

We can't just have the clients wait 5 - 8 min for the proof response to come back.
Because

1. node fetch will time out (need to use e.g http.request instead)
2. It is bad UX. It would be better to have a "fire and forget" pattern: we send an acknowledgement response to the client and then it is up to the client to check again later the queue to get its result.

So we need to implement some kind of message queue (e.g https://www.rabbitmq.com/ ?)

• GET /anonymity-set/ens-proposal-voters
• and GET /anonymity-set/punks

Are broken

{"name":"TypeError","message":"Cannot read properties of null (reading 'punks')","stack":"TypeError: Cannot read properties of null (reading 'punks')\n    at GraphRepository.getPunkOwners (/app/dist/api/repositories/GraphRepository.js:17:21)\n    at process.processTicksAndRejections (node:internal/process/task_queues:95:5)"}

Probably newers versions of the subgraphs with a new schema were deployed.
Need to check and fix.

We can privately prove membership of some set with a merkle proof as per #34. There may be some cases where we want to prove non membership instead, such as proving you're not in a tornado cash blacklist (though a blacklist may not be the ideal way to gate tornado cash).

You can prove non membership in a sorted set by showing that your address would sit between two immediately adjacent addresses in a list:

• Prove that address a is in the set (merkle proof)
• Prove that address b is in the set (merkle proof)
• Prove that the indexof(a) + 1 = indexof(b) (single constraint)
• Prove that a < address and address > b

If the list is publicly available, as it would be for a blacklist, one can check that the list is sorted outside the circuit.