owned this note   changed 3 years ago  
Linked with GitHub

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

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:

Outstanding issues

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.

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, ~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

Select a repo