The Math of ECDSA Verification: An Algebraic Proof

To validate a transaction spending authorization, full nodes must mathematically verify that a signature $(r, s)$ is valid for a specific message hash $z$ and a public key $K$.

Crucially, nodes perform this validation using only public coordinates, proving ownership without exposing the private key $k$.

---

⚙️ The Verification Pipeline

Given a signature $(r, s)$, a double-SHA256 message hash $z$, and a public key $K$:

Step 1: Range Boundaries Check

The verifying node checks that both signature integers are legally bounded:

$$1 \le r < n \quad \text{and} \quad 1 \le s < n$$

Step 2: Compute $w$

Calculate the modular multiplicative inverse of the signature component $s$:

$$w = s^{-1} \pmod n$$

Step 3: Compute Scalars $u_1$ and $u_2$

Use the inverse $w$ and the message hash $z$ to calculate two scalar values:

$$u_1 = z \cdot w \pmod n$$

$$u_2 = r \cdot w \pmod n$$

Step 4: Calculate Point $Q$

Perform elliptic curve scalar multiplication and add the resulting points together to compute a point $Q$ on the curve:

$$Q(x_Q, y_Q) = u_1 \cdot G + u_2 \cdot K$$

Step 5: Coordinate Comparison

The signature is mathematically valid if and only if the $x$-coordinate of point $Q$ is equivalent to the signature component $r$:

$$x_Q \equiv r \pmod n$$

---

🔬 Algebraic Proof of Correctness

Why is the coordinate $x_Q$ guaranteed to match $r$ if the signature is valid? Let's trace the algebraic proofs step-by-step.

1. Start with the original signing equation:

$$s \equiv k_{\text{ephemeral}}^{-1} \cdot (z + r \cdot k) \pmod n$$

1. Multiply both sides by $k_{\text{ephemeral}} \cdot s^{-1}$:

$$k_{\text{ephemeral}} \equiv s^{-1} \cdot (z + r \cdot k) \pmod n$$

1. Distribute $s^{-1}$ into the parentheses:

$$k_{\text{ephemeral}} \equiv z \cdot s^{-1} + r \cdot s^{-1} \cdot k \pmod n$$

1. Substitute our variable $w = s^{-1}$:

$$k_{\text{ephemeral}} \equiv z \cdot w + r \cdot w \cdot k \pmod n$$

1. Substitute our scalar variables $u_1 = z \cdot w$ and $u_2 = r \cdot w$:

$$k_{\text{ephemeral}} \equiv u_1 + u_2 \cdot k \pmod n$$

1. Multiply both sides of the scalar equation by the generator point $G$:

$$k_{\text{ephemeral}} \cdot G \equiv (u_1 + u_2 \cdot k) \cdot G$$

1. Distribute the point multiplication across the scalars:

$$k_{\text{ephemeral}} \cdot G \equiv u_1 \cdot G + u_2 \cdot (k \cdot G)$$

1. Substitute our known public values $R = k_{\text{ephemeral}} \cdot G$ and $K = k \cdot G$:

$$R \equiv u_1 \cdot G + u_2 \cdot K$$

1. Compare this to our definition of $Q = u_1 \cdot G + u_2 \cdot K$:

$$Q = R$$

Because $Q$ is equivalent to the ephemeral point $R$, the $x$-coordinate of $Q$ ($x_Q$) must equal the $x$-coordinate of $R$ ($x_R$), which is the definition of the signature parameter $r$.

This elegant, algebraic loop proves that verification is mathematically sound and unforgeable!