ECDSA Verification in Private Kernel Circuit
tags: aztec3speccingbook
The private kernel circuit is tasked with validating two types of transactions:
 Contract deployment,
 Private function execution.
The private kernel circuit iterates over the items in the call stack to validate each of the calls and aggregated the verification information of the respective function proof. For the very first iteration of the private kernel circuit, we need to validate if the transaction is coming from a legitimate user. For this, the user has to sign over the transaction and the private kernel circuit can then validate the signature to confirm that the transaction was submitted by the rightful owner.
ECDSA Algorithms
Since our users will be Ethereum users, they will be signing the transactions with their Ethereum keys (i.e. secp256k1 public keys). Suppose the private key of Alice is p\in\mathbb{F}_r where \mathbb{F}_r is the subgroup field of the secp256k1 curve.
 Private key: p\in\mathbb{F}_r,
 Public key:
where G\in\mathbb{G}_{\textsf{secp256k1}} is the generator of the secp256k1 curve,
3. Ethereum address:
 ECDSA signature construction:
 ECDSA signature verification:
 ECDSA key recovery:
Key recovery in ECDSA needs a variable base size2 MSM just like ECDSA verification. Additionally, it requires us to extract the ycoordinate of a point given its xcordinate. Therefore, the cost of key recovery in a circuit would be more than the cost of verifying an ECDSA signature in a circuit.
Problem at Hand
The TxContext
has the from
and to
fields which are currently set to address
type. Behind the scenes, the address
is just a field_t
and refers to an Ethereum address. An ethereum address is derived from the secp256k1 public key as shown in equation (2).
The private kernel circuit gets E (from: address
) as one of the inputs and it also gets an ECDSA signature (r, s) signed by the user. The private kernel circuit requires the public key P to verify the signature (r, s), as shown in equation (5). It is possible to recover the public key P from the signature itself (see equation (6)) with an additional cost. Let us look a few way of getting around this.
[A] Recover public key from the signature in the circuit:

\textsf{Solution}:
 The
TxContext
remains unchanged,  We recover the signing public key from the signature (r,s) using equation (5),
 Then proceed to verify the signature using the recovered public key.
 The

\color{green}{\textsf{Pros}}:
 Nothing needs to be changed in the interfaces (circuit inputs and related TS code),
 Safely use
TxContext
with only ethereum addresses without any public keys.

\color{red}{\textsf{Cons}}:
 Expensive because recovering a public key costs more than verifying the signature.
 For secp256k1, there are two possible ycoordinates for a given xcoordinate. This would mean that we need to verify the signature against both possible public keys.
 Signature verification with two public keys might not mean twice verification costs because we need to verify signature against two public keys P_1, P_2 such that P_1 + P_2 = \mathcal{O}. So optimising verification of signature against such specialcase public keys is possible.
 Overall, additional circuit cost would be in the range of 40,000 gates primarily due to public key recovery.
[B] Modify the TxContext
to include a new type from_public_key

\textsf{Solution}:
 The
TxContext
will include a new typefrom_public_key: secp256k1_point
along with the corresponding ethereum addressfrom
.  This new
from_public_key
will need to be recovered from the signature (r,s) either in native C++ or in TS (not recovered in the circuit).  Then we can proceed to verify the signature using the new input
from_public_key
.
 The

\color{green}{\textsf{Pros}}:
 No circuitcosts for recovering the public key,
 We can natively recover the public key and pass it as a circuit input (i.e.
from_public_key
)^{\ast}. In this case, TS does not need to do any additional computation.

\color{red}{\textsf{Cons}}:
 Circuit will need to verify the relation between the address
from
and the public keyfrom_public_key
using equation (2). A singleblock keccak hash costs 17,000.^{\dagger}  Signature structure should be changed to (r,s,v) where v encodes which of the two possible public keys was used to sign the transaction.
 Circuit will need to verify the relation between the address
[C] Replace all address
types with curve points

\textsf{Solution}:
 Change the types of
from, to
inTxContext
fromaddress
tosecp256k1_point
and do away with addresses altogether.  It will be TS’s responsibility to supply only the public keys (even if it only has access to user’s ethereum address, it will have to recover public key(s) from the signature).
 Change the types of

\color{green}{\textsf{Pros}}:
 No
address
type instdlib
so no need to deal with any ethereum addresses  No conversions between
address
andpublic_key
anywhere in C++ circuits or natively.
 No

\color{red}{\textsf{Cons}}:
 TS will have to figure out how to fetch or compute public keys.
 The
TxContext
structure will no longer be analogous toTxRequest
in ethereum transaction.
Conclusion
Clearly, second solution seems to be the best in terms of additional gate costs and time required to implement the change.
^{\dagger}{\scriptsize \textsf{Using a fieldfriendly hash function is not possible here because of the definition of how an ethereum address is computed.}}
^{\ast}{\scriptsize \textsf{Thanks to Mike for this suggestion.}}