Proof of Coordinate Compression: Modular Square Roots

How can a full node reconstruct a full 64-byte public key point $(x, y)$ from a 33-byte compressed format containing only the $x$-coordinate and a parity prefix byte?

The answer lies in the algebraic symmetry of the curve equation and a specific shortcut in number theory for finding square roots in finite fields.

---

📈 Solving for $y$

The equation for the secp256k1 curve is:

$$y^2 = x^3 + 7 \pmod p$$

If we are given the $x$-coordinate of a point, we first calculate the value of the right side of the equation:

$$w = x^3 + 7 \pmod p$$

To reconstruct the $y$-coordinate, we must find the modular square root of $w$:

$$y \equiv \pm \sqrt{w} \pmod p$$

---

🔬 The Fermat / Euler Shortcut ($p \equiv 3 \pmod 4$)

Finding square roots over a finite field usually requires the complex Tonelli-Shanks algorithm. However, the prime modulus $p$ chosen for Bitcoin has a special property:

$$p = 2^{256} - 2^{32} - 977$$

If we divide $p$ by $4$, the remainder is $3$:

$$p \equiv 3 \pmod 4$$

In number theory, whenever a prime $p$ satisfies $p \equiv 3 \pmod 4$, any quadratic residue $w$ has modular square roots that can be calculated in a single step using Fermat's Little Theorem:

$$y_1 = w^{\frac{p+1}{4}} \pmod p$$

$$y_2 = p - y_1 \pmod p$$

📐 Mathematical Proof

To prove that $y_1$ is indeed a valid square root (i.e., $y_1^2 \equiv w \pmod p$):

1. Square our candidate root:

$$y_1^2 \equiv \left(w^{\frac{p+1}{4}}\right)^2 \equiv w^{\frac{p+1}{2}} \pmod p$$

1. Factor out a $w$:

$$w^{\frac{p+1}{2}} \equiv w^{\frac{p-1}{2} + 1} \equiv w^{\frac{p-1}{2}} \cdot w \pmod p$$

1. Apply Euler's Criterion. If $w$ is a quadratic residue (meaning a square root exists), then:

$$w^{\frac{p-1}{2}} \equiv 1 \pmod p$$

1. Substitute this back into our expression:

$$y_1^2 \equiv 1 \cdot w \equiv w \pmod p$$

Thus, our candidate $y_1$ is mathematically proven to be a valid square root!

---

🚦 Parity Selection and Prefix Rules

Because there are two square roots ($y_1$ and $y_2$), they will always have opposite parity (one is even, and the other is odd):

• If $y_1$ is even, then $y_2 = p - y_1$ must be odd (since $p$ is an odd prime, and an odd number minus an even number is always odd).
• If $y_1$ is odd, then $y_2 = p - y_1$ must be even.

When a node reads a compressed public key, it uses the prefix byte to determine which root to choose:

$$\text{Reconstructed } y = \begin{cases} y_{\text{even}} & \text{if Prefix is } \text{0x02} \ y_{\text{odd}} & \text{if Prefix is } \text{0x03} \end{cases}$$

This elegant mathematical symmetry allows Bitcoin nodes to reconstruct the full coordinate pair in microseconds while saving 32 bytes of transaction storage weight!