# Project Proposal: Circuits for ECDSA and others

Repo: https://github.com/0xPARC/circom-secp256k1

## Team Members

@antimatter15, @gubsheep, @Jeff Lau, @tliu, @wdli, @yi

## Project Description

The goal is to produce a BigInt arithmetic library in Circom and use it to implement ECDSA signatures as a first application. Specifically, we aim to implement the following operations and possible extensions.

### BigInt arithmetic library
* BigAdd
* BigMult
* BigMod
* Algorithm for big integer division: https://people.eecs.berkeley.edu/~fateman/282/F%20Wright%20notes/week4.pdf
* BigSub
* BigPow

### Secp256k1 arithmetic
* Addition
* Scalar multiplication
* Public key compression / decompression (?)

### ECDSA signatures
* Circuit for private key -> public key mapping

 // keys are encoded as (x, y) pairs with each coordinate being
 // encoded with k registers of n bits each
 template ECDSAPrivToPub(n, k) {
     signal input privkey[k];
     
     signal output pubkey[2][k];
 }

| Stride | Constraints |
| -------- | -------- |
| 1 | 3733697 |
| 3 | 1237111 |
| 8 | 482276 |
| 9 | 436936 |
| 10 | 416883 |
| 11 | 432869 |

* Circuit for knowledge of private key which signed a certain signature

 // r, s, msghash, nonce, and privkey have coordinates
 // encoded with k registers of n bits each 
 // signature is (r, s)
 template ECDSASign(n, k) {
     signal input privkey[k];
     signal input msghash[k];
     signal input nonce[k];
     
     signal output r[k];
     signal output s[k];
 }

* Circuit for knowledge of private key which signed a certain extended signature

 // r, s, msghash, nonce, and privkey have coordinates
 // encoded with k registers of n bits each 
 // v is a bit
 // signature is (r, s, v)
 template ECDSAExtendedSign(n, k) {
     signal input privkey[k];
     signal input msghash[k];
     signal input nonce[k];
     
     signal output r[k];
     signal output s[k];
     signal output v;
 }

* Circuit for proof that signature verifies

 // r, s, msghash, and pubkey have coordinates
 // encoded with k registers of n bits each
 // signature is (r, s)
 template ECDSAVerify(n, k) {
     signal input r[k];
     signal input s[k];     
     signal input msghash[k];
     signal input pubkey[2][k];

     signal output result;
 }

* Circuit for proof that extended signature verifies

 // r, s, and msghash have coordinates
 // encoded with k registers of n bits each
 // v is a single bit
 // extended signature is (r, s, v)
 template ECDSAExtendedVerify(n, k) {
     signal input r[k];
     signal input s[k];
     signal input v;
     signal input msghash[k];

     signal output result;
 }

### [extension] Optimization of BigInt / ECDSA

* wdli: so an idea of "weak" mod p is to take advantage of the fact that secp256k1's prime = 2^256 - 2^32 - 2^9 -2^8 - 2^7 - 2^6 - 2^4 - 1
* wdli: so if we instead use 64 bit words then we can split the bigint representation to upper and lower half like a*2^256 + b
* wdli: then we can do a reduction like a*2^256 + b = (2^32 - 2^9 -2^8 - 2^7 - 2^6 - 2^4 - 1)*a + b mod P
* and after the "weak" mod p the value will be in the range of 0~2^(256 + 32)
* wdli: but can still fit into the 4 word because we can handle a bit of overflow
* wdli: but then it will get larger and larger over time so if we do some numerical range analysis then we can try to use this "weak" mod p and then do the real mod p less often
* wdli: oh wait I guess we should still really do mod p most of the time because 2^288 is still too large after a few multiplication

### [extension] BLS Signatures
* Knowledge of enough private keys to form a threshold signature. Should be doable using Lagrange interpolation and elliptic curve arithmetic.
* Knowledge of private key to a signed message. Requires a hash valued in an elliptic curve group.
* Proof of verification of a signature. Requires elliptic curve pairings.

### [extension] Merkle/Verkle tree proof verification

## Project Deliverables
Project deliverables include:
* A Github repo with BigInt, secp256k1, and ECDSA libraries implementing these operations.
* Comprehensive tests for correctness
* A proof of concept webapp or interface to the library, possibilites include:
* usage in the zk-identity project
* illustration in zkrepl

## Testing Plan
### Known Issues
* [ ] BigMod cannot handle b with zero leading register
* [ ] BigAdd, BigMult, BigMod require fixed register lengths
### bigint.circom
* [x] BigAdd -- Yi
* [x] BigSub -- Yi
* [x] BigSubModP -- Tony
* [x] BigMult -- Wen-Ding
* [x] BigLessThan -- Wen-Ding
* [x] BigMod -- Tony
* [ ] ModSum
* [ ] ModSub
* [ ] ModSubThree
* [ ] ModSumThree
* [ ] BigMultShortLong
* [ ] LongToShortNoEndCarry
* [ ] BigModInv
* Unused
* [ ] ModSumFour
* Unused
* [ ] ModProd
* Unused
* [ ] Split
* Unused
* [ ] SplitThree
* Unused
### secp256k1.circom
* [x] Secp256k1AddUnequal
* [ ] Secp256k1Double
* [ ] Secp256k1ScalarMult
### ecdsa.circom
* [x] ECDSAPrivToPub
* [ ] ECDSASign
* [ ] ECDSAVerify

## Demo Outline

1. Overview of Design
2. Brian's CLI demo with group sigs
3. Performance numbers
4. Optimizations
* Long/short registers
6. Testing strategy
7. Next steps
* Future work on testing framework
* ECDSAKeyGen + Recover in PLONK