# Batch-ECDSA for optimistic rollups
Optimistic rollups may be able to reduce calldata costs by aggregating ECDSA signatures from their on-chain transaction data into a SNARK. This document outlines some of the steps that would be necessary specifically.

### Background on [batch ECDSA verification](https://www.math.snu.ac.kr/~jhcheon/publications/2007/BatchVer_PKC2007_CL.pdf)

An ECDSA signature on an elliptic curve group with base point `G` of order `n` consists of a pair of non-zero integers `(r, s)` mod `n`. To verify that a message `m` was signed by public key `Q`, we check for a hash `H(m) \in [0, n - 1]` that:
* `Q` is a valid public key
* for `(x, y) = (H(m) s^{-1}) G + (r s^{-1}) Q`, check that `(x, y)` is not `O` and that `r = x`.

We can extend this to ECDSA* verification, meaning that there is a point `R = (r, r')` so that `R = (H(m) s^{-1}) G + (r s^{-1}) Q`. We can ask the prover to provide `r'`.

For batch verification, suppose we have signatures `(r_i, s_i)` for messages `m_i` with hashes `h_i = H(m_i)` and public keys `Q_i`. For the completed signatures `R_i = (r_i, r_i')` provided by the prover and a random `t in [0, n - 1]`, we verify the RLC equation

sum_i t^i R_i = (sum_i t^i (h_i s_i^{-1})) G + sum_i t^i (r_i s_i^{-1}) Q_i

For `k` signatures, this requires:
1. Computation of the coefficients using `5k` BigInt multiplications mod `n`.
2. Verification of a MSM with `2k + 1` base points and these coefficients.
3. Verification that `R_i` is a valid completion of `(r_i, -)` to a point on the curve.

#### Costs without caching multiples of `G`

We do this by amortizing the double steps in the double and add algorithm, so if `n` has 256 bits, this should cost:
* 256 secp256k1 doubles
* `(2k + 1) * 256` secp256k1 adds

The cost of `k` independent ECDSA verifications is:
* `256 * k` secp256k1 doubles
* `2k * 256` secp256k1 adds

#### Costs with caching multiples of `G`

If we cache multiples of `G` with a window of size 10, we get
* 256 secp256k1 doubles
* `(2k) * 256 + 26 + 1` secp256k1 adds

The cost of `k` independent ECDSA verifications is:
* `256 * k` secp256k1 doubles
* `256 * k + 27 * k` secp256k1 adds

#### Costs with dynamic windowed method and caching for `G`

Suppose we use the dynamic windowed method with window size `w` and also cache `G` with window size 10. Our costs are:
* `2^w * 2 k` adds for dynamic caching of multiples of `R_i` and `Q_i`
* `256` doubles shared on the batch MSM
* `26` additions for `G`
* `(256 / w) * (2k)` additions for `R_i` and `Q_i`

This is a total of `256` doubles and `(2 * 2^w + 512/w)k + 26` additions when we ignore costs of selecting.

If we use the dynamic windowed method on each signature separately, we get:
* `2^w * k` adds for dynamic caching of multiples of `Q_i`
* `256 * k` doubles
* `26 * k` additions for `G`
* `(256/w) * k` additions

This is a total of `256k` doubles and `(2^w + 256/w + 26)k` adds.

**Note:** This is the strategy suggested at:
* https://hackmd.io/ncuKqRXzR-Cw-Au2fGzsMg#Batch-Multiplication
* Implementation: https://github.com/privacy-scaling-explorations/halo2wrong/pull/22.

#### Outstanding issues
* We may need to add an auxiliary random point to avoid checking if points are 0 / equal.
* Called Random Accumulator Initialization at: https://hackmd.io/ncuKqRXzR-Cw-Au2fGzsMg#Random-accumulation-initializer

### Technical roadmap

**ZK Circuits**

Snark spec:

Inputs:
* hash(T_i), addr_i, sig_i, 1<=i<=BATCH_SIZE, private inputs
* merkle_root(hash(T_i) || a_i for all i), public output

Compute witness variable:
* pubkey_i := ecrecover(hash(T_i), sig_i)

Constraints:
* pubToAddr(pubkey_i) == addr_i for all i
* BatchVerify(hash(T_i), sig_i, pubkey_i for all i) == true
* merkelize(hash(T_i) || a_i for all i).root is public output

Possibly will want to use batch [Keccak optmizations](https://hackmd.io/dhrKjIWlRQ-RyPY1-jQv-A).

**Steps to Production**
1. Auditing / verification for batch ECDSA circuit
2. Integration with sequencer + fault proofs
3. Trusted setup for circuits
4. Prover infrastructure

### Benefits and Tradeoffs

#### Gas Savings

We can estimate the gains from this approach in two ways:

* In a L1 transaction commitment with ~200 ECDSA signatures, which costs ~200K = 16 * 64 * 200 gas. If we replace this with a single SNARK (131 bytes) and sender addresses, this gas cost is reduced to ~66K gas.
* At one L1 transaction commitment per 3m and 30gwei gas cost, this is ~1.1 ETH = ~1.1K USD per day savings at $1000 ETH.
* If L1 transaction commitments increase in size to contain 400 ECDSA signatures, this would be 2.2 ETH = ~2.2k USD per day savings.
* In general for every additional 100 signatures per L1 transaction commitment, this saves 0.6 ETH per day.
* According to this [query](https://dune.com/queries/833016), ~40% of transactions on Optimism are <= 235 = 150 + 85 bytes, so by removing 44 = 64 - 20 bytes from the signature call data, we can save around at least 18% = 44 / 235 on gas costs.
* This is especially substantial for small transactions most likely to be run by retail users.
* We were not able to find the analogous query for Arbitrum.

A few consequences:
* Public keys of address signers will not be available, since we only store the address, not the pubkey.
* The transaction format will not contain the signature, which may affect wallets / block explorers, etc.

#### Additional latency

The SNARKs for batch ECDSA verification will need to be generated before commitment on L1, which may introduce more latency in this process.

### References
* Proxy contract for SequencerInbox: https://etherscan.io/address/0x4c6f947ae67f572afa4ae0730947de7c874f95ef
* Implementation contract for SequencerInbox: https://etherscan.io/address/0x9685e7281fb1507b6f141758d80b08752faf0c43#code