# ECDSA Signature Verification in Private Kernel Circuit

**URL:** <https://forum.aztec.network/t/ecdsa-signature-verification-in-private-kernel-circuit/177>\
**Category:** Aztec\
**Created:** [April 10, 2023, 8:16pm UTC](https://forum.aztec.network/t/ecdsa-signature-verification-in-private-kernel-circuit/177 "2023-04-10T20:16:15Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![suyash67](https://avatars.discourse-cdn.com/v4/letter/s/9d8465/32.png) [@suyash67](https://forum.aztec.network/u/suyash67)\
**Post date:** [April 10, 2023, 8:16pm UTC](https://forum.aztec.network/t/ecdsa-signature-verification-in-private-kernel-circuit/177/1 "2023-04-10T20:16:15Z")

</div>

# ECDSA Verification in Private Kernel Circuit

###### tags: `aztec3-speccing-book`

The private kernel circuit is tasked with validating two types of transactions:

1. Contract deployment,
2. 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.

1. Private key: p\in\mathbb{F}\_r,
2. Public key:

P := p \* G \tag{1}

where G\in\mathbb{G}\_{\textsf{secp256k1}} is the generator of the secp256k1 curve,  
3. Ethereum address:

E := \textsf{uint160}(\textsf{uint256}(\textsf{keccak}(P))) \tag{2}

1. ECDSA signature construction:

\begin{aligned} & \textsf{ecdsa\_sign}(m, p):\\ & \qquad k \leftarrow \textsf{hmac}(m, p) & & \in \mathbb{F}\_r \\ & \qquad R := k \* G & & \in \mathbb{G}\_\textsf{secp256k1} \\ & \qquad r := R\_x \text{ mod } r & & \in \mathbb{F}\_r \\ & \qquad z := \textsf{hash}(m) & & \in \mathbb{F}\_r \\ & \qquad s := k^{-1} \cdot (z + r \cdot p) & & \in \mathbb{F}\_r \\ & \qquad \text{return } (r, s) & & \in \mathbb{F}\_r^2 \end{aligned} \tag{3}

1. ECDSA signature verification:

\begin{aligned} & \textsf{ecdsa\_verify}((r, s), m, P):\\ & \qquad z := \textsf{hash}(m) \\ & \qquad u\_1 := z \cdot s^{-1} & & \small{//} \ \ u\_1 = z \cdot k \cdot (z + r \cdot p)^{-1} \\ & \qquad u\_2 := r \cdot s^{-1} & & \small{//} \ \ u\_2 = r \cdot k \cdot (z + r \cdot p)^{-1} \\ & \qquad R' := (u\_1 \* G + u\_2 \* P) & & \small{//} \ \ R' = (u\_1 + u\_2 \cdot p) \* G \\ & & & \small{//} \hspace{0.65cm} = [z \cdot k \cdot (z + r \cdot p)^{-1} \ + \\ & & & \small{//} \hspace{1.4cm} r \cdot k \cdot (z + r \cdot p)^{-1} \cdot p] \* G \\ & & & \small{//} \hspace{0.65cm} = k \* G \\ & \qquad \text{return } R\_x \stackrel{?}{=} r \end{aligned} \tag{4}

1. ECDSA key recovery:

\begin{aligned} & \textsf{ecdsa\_pubkey\_recover}((r, s), m, P):\\ & \qquad z := \textsf{hash}(m) \\ & \qquad (y\_+, y\_-) \leftarrow \left( \pm \sqrt{x^3 + Ax + B}\right)\_{x = r} \\ & \qquad R\_+ \equiv (r, y\_+) & & \small{// \ \textsf{positive y-coordinate}} \\ & \qquad R\_- \equiv (r, y\_-) & & \small{// \ \textsf{negative y-coordinate}} \\ & \qquad L\_\pm := s \* R\_{\pm} & & \small{//} \ \ L = (s \cdot k) \* G \\ & & & \small{//} \hspace{0.55cm} = (z + r \cdot p) \* G \\ & & & \small{//} \hspace{0.55cm} = z \* G + r \* P \\ & \qquad P\_\pm = r^{-1} \* (L\_\pm - z \* G) & & \\ & \qquad \quad = (r^{-1} \cdot s) \* R\_\pm \ + \ (–r^{-1}\cdot z) \* G & & \\ & \qquad \text{return } (P\_+, P\_-) \end{aligned} \tag{5}

Key recovery in ECDSA needs a variable base size-2 MSM just like ECDSA verification. Additionally, it requires us to extract the y-coordinate of a point given its x-cordinate. 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.

- \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 y-coordinates for a given x-coordinate. 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 special-case 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 type `from_public_key: secp256k1_point` along with the corresponding ethereum address `from`.
  - 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`.

- \color{green}{\textsf{Pros}}:
  - No circuit-costs 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 key `from_public_key` using equation (2). A single-block 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.

#### [C] Replace all `address` types with curve points

- \textsf{Solution}:
  - Change the types of `from, to` in `TxContext` from `address` to `secp256k1_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).

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

- \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 to `TxRequest` 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 field-friendly 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.}}

---

<div class="post-metadata">

**Author:** ![spalladino](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.aztec.network/spalladino/32/32_2.png) [@spalladino](https://forum.aztec.network/u/spalladino)\
**Post date:** [April 26, 2023, 12:51pm UTC](https://forum.aztec.network/t/ecdsa-signature-verification-in-private-kernel-circuit/177/2 "2023-04-26T12:51:54Z")

</div>

I personally like option (c) just considering the pros/cons here, but that’d mean that the addresses that our users play use in Noir contracts will be different than Ethereum addresses, right? We could easily add a helper function to go from one to the other at the app level if actually needed, but it introduces an extra complexity for devs. I’m not sure how bad it is though.