ECDSA gadget

Now for the ECDSA gadget; this gadget can be found in the halo2wrong repo here.

The code included here can be found here.

Gadget design

This gadget is here to allow us to make proofs of ECDSA signature verification. This can allow somebody to prove that they know a valid signature without sharing it. There is going to be one primary function for this gadget - verify().

This gadget needs some preliminary structures to allow this to happen. The halo2wrong repo has already made non-native field arithmetic possible, and the next building bloc is elliptic curve cryptography in a proof. This of course has been built for this.

Next items would be structs to contain public keys and ECDSA values. Make sure you're aware of the ECDSA algorithm - perhaps recap it by looking through the order described in wikipedia.

The config for this gadget only needs to contain the main gate config and also the range config, we can build everything from these.

Next we create structs for items we will need along the way in the signature algorithm; these are the signature itself and also the associated public key. The Assigned keyword here refers to the fact that these structs contain within them AssignedCells as opposed to just data value.

Next we create the chip itself, and all this needs to contain is an elliptic curve cryptography (ECC) chip, because of course everything happening in the ECDSA algorithm is generally speaking an elliptic curve operation. To use this gadget you don't need to dice into the details of this ECC chip (though of course the more you know the better).

Finally we reach the core function. Now this may look like a lot, but as you read through the code you will see that the steps map pretty clearly onto the steps outlines in the wikipedia article - the ECDSA algorithm is actually pretty straightforward.

The function takes in a signature, public key and message hash, and from this it conducts the verification operation.

Example

Let's walk through a quick example of this gadget being used, we will do this in a specific curve setting to be more representative. We will make a proof of correctly verifying a message signature.

Firstly we make the test circuit config that we will need to use in this proof. It only needs to contains the main gate config and the range gate config.

Next we want some implementations for this config. Two of the functions are straightforward, one will return a range chip using the range config, and the other will return an ECC config using both the main and range configs to create it.

The new function seems more complicated, but there is actually not too much going on. It essentially takes in some of the context knowledge (limb bit length and number of limbs) to produce the right main and range configs before producing the test circuit config in return.

Next up we make the actual circuit that we want. This needs to be able to contain all the data that we need to fill out the rest of the circuit. This of course means it needs the public key, the signature, message hash, and some other data. We could actually remove the public key because we can derive it from the secret key but there is some use in adding it separately.

Now we can start implementing the Circuit trait on this circuit. The first two functions here are straightforward in this case. Synthesise will take more work.

To get started in the zk circuit construction, we want to first build an ECC chip since essentially everything happening in ECDSA is in this setting.

Next we want to assign a region where we will assign the auxiliary point; this is just a curve point used along the way.

Then we make variables for the ecdsa and scalar chips.

It is time to assign a region to conduct the actual ECDSA algorithm. You can see in the code that most of what happens here is just calling implemented functions on the ECC and scalar chips, and those functions will do the construction for us.

Of course the signature is already known so we simply assign these values into the circuit along with the message hash and public key. In fact the entire verification algorithm is done by calling the verify() function that we explored earlier.

We close synthesise by loading the range tables via the function config_range.

Now we want to define a function that will run this circuit in the setting we desire, and we will be done.

This function will take in everything we need to run this circuit, which is the secret key, message hash and signature. It creates the generator for the curve of choice (Secp256k1 for this example) and uses this to derive the public key.

We quickly check the correctness of the inserted data outside of the circuit setting as a sanity check before moving onto the actual circuit.

The auxiliary generator point is created, all the data is inserted into the circuit, and then we run mock_prover_verify() to construct a proof and verify its correctness.

Finally, here is the test that we run. It contains data for a valid signature on a certain public key and message. We insert the data into the run function, and if anything is wrong or incorrect the mock prover/verifier will fail.

Benchmark

Now is a good time to provide some benchmark figures for this gadget in both Halo2 and groth16 for comparison.

The following Halo2 times were taken on a 2020 M1 macbook air with 16GB RAM. 2^18 constraints are needed for a single run of this gadget. This benchmark was done over the Bn256 curve.

Process	2^18 constraints
Verifier key generation	3.85s
Prover key generation	4.47s
Proof generation	19.1s
Verification	11.1ms

These times can be compared with the Groth16 implementation of 0xParc here. Their times are copied here for your convenience. Note that our gadget conducts ECDSA verification, and so that would be the appropriate column to compare times with.