# PoK of Valid ECDSA signature

## Notation

I'm using the same variable names as in your original note https://hackmd.io/XLu3oFIVRZuxF2Nfj1D50w

Relations are expressed as: $$\{ (\text{instance; witness}): \text{conditions} \} $$

## Protocol Description

Prove the following relation:
$$ \mathcal{R} := \{(m, R, G;s, Q_a): \text{ECDSA}.verify(m, (r,s), Q_a) = 1 \land r = \text{x_coord}(R) \} $$

In words: "I know the $s$ part of an ECDSA signature on $m$ such that verification succeeds for a hidden public key".

> **Sub-protocol (your circuit)**
> We use a sub-protocol for the following relation:
>
> $$ \mathcal{R}_{inner} := \{(A, B;x, Y): xA + B = Y $$
>
> Assume we have a ZK prover and verifier for this with correctness, knowledge soundness and ZK.

**Prover**:
- compute $r$ as the x-coordinate of $R$
- compute $A = r^{-1}R$
- compute $B = -(mr^{-1}G)$
- run the sub-protocol prover for public inputs $A,B$ and private inputs $s, Q_a$ to obtain proof $\pi$.
- output $\pi$

**Verifier**:
- compute $r$ as the x-coordinate of $R$
- compute $A = r^{-1}R$
- compute $B = -(mr^{-1}G)$
- run the sub-protocol verifier on $\pi$ for public inputs $A,B$ and return $1$ if verification passes and $0$ if it fails

## Security

### Correctness
You already have this from the series of equivalences shown in the original thread and the HackMD. You can also do it by showing that a valid $s$ and $Q_a$ will always make the verifier output $1$. (noting that when you reach the sub-protocol verifier, you can say that the sub-protocol has correctness, therefore its verifier will always output 1 given a valid input)

### Knowledge Soundness
Here we need to show that if someone, $P'$, has emitted a valid proof, then they know $s$ and $Q_a$. We do so by constructing an extractor $Ext$ which is allowed to force $P'$ to run different steps of the protocol on values of its choice.

The inner protocol also has knowledge soundness, therefore there exists an extractor $Ext_{inner}$ able to extract $s$ and $Q_a$ from a prover of the inner protocol, $P'_{inner}$.

What our extractor does is compute values $A$ and $B$ from the public inputs and then run $Ext_{inner}$ on $A$, $B$ and $P'_{inner}$ to obtain $s$ and $Q_a$.

### Zero-Knowledge
We get this for free as the only message sent is the output of the sub-protocol which is already ZK.

## Does $R$ leak anything about $s$ and $Q_a$?
I've sort of avoided this question in the way I formulated the relation that we are proving. But if $R$ does leak info, then maybe computing $s$ and $Q_a$ is simple and this ZK proof would be meaningless. So?

In your document you show that there is an equation relating $s$ to $r$. However $privKey$ is also in there. One equation, two unknowns so we're ok! It does however mean that the problem of producing a valid witness $(s, Q_a)$ is easier than guessing two random values.