# Efficient ECDSA in practice
Terms

- content
- e.g. tweet, form submission
- proof
- A zkSNARK that provides credibility/authenticity to the content
- Examples
- ZK proof of membership
- (non-zk Proof of signature verification (more on this later)
- UGC
- User-generated content

In this document, I will describe my current mental model of how efficient-ECDSA could be deployed, to achieve the following properties:

- Proof verifications on public blockchain(s) (i.e. decentralization) (i.e. liveness)
- Scaling to > 100,000,000 (or whatever million UGCs the platform should embrace) proof verifications. Twitter has [867 Million tweets per day](https://www.renolon.com/number-of-tweets-per-day/).
- (We assume that the signals are stored on decentralized storage networks)

### Efficient ECDSA in practice

There will be two circuits. One ran in the browser (weak prover), and one ran in a remote server (strong prover).

### Circuit ran in the browser (proof-1)

**Public inputs**
| Variable | Description |
| --- | --- |
| T | r^-1 * R |
| U | -(m * r^-1 * G) |
| merkleRoot | |
| CID | The content published on the decentralized storage should have a CID (content id), the hash of the content (as in IPFS). This prevents uploading different content with an already verified CID. In other words, prevents proof replay. In Arwevae, the CID will be the transaction id. |
| CIDSquared | To prevent tampering. As done in Semaphore. |

### Circuit ran in a remote server (proof-2)

**Public inputs**
| Variable | Description |
| --- | --- |
| T | |
| U | |
| R | |
| m | The CID. To prevent signature replays, the CID should be signed. |

**Checks**

- R.x^-1 * R == T
- -(m * R.x^-1 * G) == U

### Alternative circuits

By precomputing the powers of elliptic curve point T, we gain meaningful improvements on proving time. Although, the catch is that we need to pass the precomputes as a public input, significantly increasing the proof size. We can get around this by making the precomputes a private input in proof-1, hash them, and output the resulting hash as a public input. And we can check in proof-2 that the precomputes are correct and output the hash of the precomputes as proof-1 does.

Another possible way is to use the method from [my original post](https://ethresear.ch/t/efficient-ecdsa-signature-verification-using-circom/13629), which results in precomputes being a private input by default (i.e. we don’t need to check the validity of precomputes, since if the prover knows the precomputes, that implies that the prover can create valid signatures). However, the method is not formally verified, and requires an additional Keccak hash inside the circuit. (But Keccak could be pretty cheap in Halo2!!)

I’ve been contemplating which circuit version will make the most sense since

1. we now have Lookup (Halo2) which might realize fast Keccak inside circuit
2. we want to keep the proof size small so it can be verified on-chain

## From the perspective of dapps

When a dapp wants to check whether or not a particular content has a proof that attests to it, it does the following.

1. Checks if there exists on the blockchain, a verified proof-1 that has the CID in question, as the public input
2. Checks if there exists on the blockchain, a verified proof-2 that has the same T, U, and m = CID, as proof-1.

If both proof-1 and proof-2 are found, then the proof is indeed the one for the content.

Such (roughly) two-step checks are executable with ease.

## Storage layer

Storing UGC (user-generated content) requires a decentralized storage network such as Filecoin or Arweave.

## Execution layer

In short, what the execution layer (i.e.public blockchain) does is: verify the zkSANRKs.

The execution layer is separated from the storage layer but only provides meaning when combined with the storage layer.

The required scalability/decentralization of the execution layer for non-financial apps is another whole research space. I’m composing the details in a different writeup, but the outline is:

1. The scaling discussions that have been going on are mainly around scaling financial dapps. Scaling for non-financial dapps has a different set of assumptions/requirements (if I understand correctly, which is exactly what [MUD](https://www.youtube.com/watch?v=j-_Zf8o5Wlo&t=1926s) is for!).
- We don’t necessarily need a link between L1 (Ethereum) and L2. i.e. since we don’t need to transfer assets from L1, we can roll out a completely distinct blockchain that fits our needs.
- What matters is EOAs and the “information (e.g. NFT ownership)” on L1; EOAs, as in the name are externally owned accounts, so they work anywhere.
2. With 1. as the premise, we could have a purpose-built public blockchain that is dedicated to verifying zkSNARKs for non-financial dapps that require scalability. Such blockchain could be beneficial for not only privacy applications, but also signature-based SaaS-like applications (e.g. Snapshot, Storyform). That is, the signatures could be efficiently verified using batching/snarkifying. This provides robustness compared to lazily verifying the signature stored on IPFS as Snapshot does, which is DoS-prone.

### On MUD
**The case for MUD for non-gaming dapps**

The already established infrastructure of MUD is sufficient to build any kind of dapps upon it. It can be argued that a “monolithic execution layer” which embraces all kinds of applications leverages composability the most.

**The case against MUD for non-gaming dapps**

It can be argued that ECS is sub-optimal for dapps with UGC. The main diremption I see is: ECS is probably suited for systems where state diff matters, but dapps like Heyanon and Storyform mainly care about UGCs and proof verification (with the assumption that UGCs can’t be stored inside the ECS model).

### **Realistically**

Since we don’t have to expect millions of proofs to be submitted for the privacy applications of today, (or should we??), and we don’t need to be too hard on ourselves in terms of decentralization, opting for chains like MUD could be a good enough option.