# Wait, what are these isomorphic elliptic curves doing on the secp256k1/secq256k1 cycle?

_Written by [Daira Hopwood](https://twitter.com/feministPLT) and [Sean Bowe](https://twitter.com/ebfull)._

--------

The [secp256k1](https://en.bitcoin.it/wiki/Secp256k1) elliptic curve is $y^2 = x^3 + 7$ defined over $\mathbb{F}_p$, with order $q$, given the primes:

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
q = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

It's commonly known that another curve we'll call "sec**q**256k1" exists (with the same curve equation!) defined instead over $\mathbb{F}_q$, and its order is $p$. This means the two curves form a $2$-cycle, and such a cycle is _very_ useful for things like [proof-carrying data](https://eprint.iacr.org/2014/595) implemented using discrete-log assumptions.

But open [SageMath](https://www.sagemath.org/) up and look what happens when you do this:

sage: EllipticCurve(GF(p), [0, 1]).order() == EllipticCurve(GF(q), [0, 1]).order()
True

Wait, what? There are two elliptic curves, each with the equation $y^2 = x^3 + 1$, _and with the same group order_, but defined over $\mathbb{F}_p$ and $\mathbb{F}_q$, respectively. It's kind of surprising that we could so easily find two large and isomorphic curves for which these fields share access. Normally, if we pick a random curve over a given field, the order can be anywhere within a very large [Hasse interval](https://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves), and so it would be vanishingly unlikely that two such curves over different fields would have the same order.

This is no coincidence, and so we dug in to find out why.

## secp256k1's origins

secp256k1 was published by Certicom a couple decades ago as part of a general effort to encourage the adoption of elliptic curve cryptography, and probably also as a way to monetize the multiple patents they had on ECC-adjacent ideas. One of these patents was over a technique for quickly performing scalar multiplication through the use of an endomorphism that exists for Koblitz curves of the form $y^2 = x^3 + b$ defined over a field $\mathbb{F}_p$ with $p \equiv 1 \pmod{3}$. These patents [expired in 2020](https://twitter.com/feministPLT/status/1212509061205430278).

secp256k1 is indeed one of these curves, though how it was chosen was never clearly specified. [[SEC 2]](https://www.secg.org/sec2-v2.pdf) only says that "The recommended parameters associated with a Koblitz curve were chosen by repeatedly selecting parameters admitting an efficiently computable endomorphism until a prime order curve was found." — which is quite vague.

One of the caveats of searching for a curve like secp256k1 is that this particular class of curves only has six distinct curves (up to isomorphism) for each prime field. Due to the sparsity of primes, Certicom likely searched through a space of finite fields until a point counting algorithm and primality test told them they found a prime order curve over one of them.

## CM curves

Koblitz curves over prime fields are also part of a class of curves called CM curves for which a simple relationship exists between the field characteristic and the group order. In particular, given $p \equiv 1 \pmod{3}$ the six possible orders of any j-invariant $0$ curve over $\mathbb{F}_p$ are given by

* $p + 1 \pm T_p$
* $p + 1 \pm \frac{3V_p}{2} \pm \frac{T_p}{2}$

where $V_p, T_p$ are integers. This presents another way to search for curves like secp256k1 that avoids point counting algorithms and relies only on primality testing. (We developed [a tool](https://github.com/daira/curvesearch) to find curves with special properties, leading to the [Pasta curves](https://electriccoin.co/blog/the-pasta-curves-for-halo-2-and-beyond/) that we now use in Zcash.)

Interestingly, these curves _always_ form a $2$-cycle when the curve's order is prime. As an example, suppose that $q = p + 1 - T_p$ is the group order. We can write $T_q = T_p - 2$ and rearrange to see $p = q + 1 + T_q$, which is one of the group orders written above but with $p$ swapped with $q$! This implies a j-invariant $0$ curve exists on $\mathbb{F}_q$ that has order $p$, forming a $2$-cycle. This is true for the other cases as well.

## Isomorphic Curves

The reason a curve exists over secp256k1's base field that is isomorphic to a curve over its scalar field stems from the fact that secp256k1's group order happens to be in the $q = p + 1 \pm T_p$ case mentioned before.

Here's why. Supposing that $q = p + 1 - T_p$ (and therefore that $p = q + 1 + T_q$, and without loss of generality) we can look at the orders of some of the other CM curves involved:

* $p + 1 \pm \frac{3V_p}{2} \pm \frac{T_p}{2}$ are the orders of other $j$-invariant $0$ curves over $\mathbb{F}_p$.
* $q + 1 \pm \frac{3V_p}{2} \pm \frac{T_q}{2}$ are the orders of other $j$-invariant $0$ curves over $\mathbb{F}_q$.

But with some simple arithmetic we see that e.g.

$$
\begin{array}{rl}
p + 1 + \frac{3V_p}{2} - \frac{T_p}{2} &= (q + 1 + T_q) + 1 + \frac{3V_p}{2} - \frac{T_p}{2} \\
&= q + 2 + \frac{3V_p}{2} - \frac{T_p}{2} + T_q \\
&= q + 2 + \frac{3V_p}{2} - \frac{T_q + 2}{2} + T_q \\
&= q + 1 + \frac{3V_p}{2} - \frac{T_q}{2} + T_q\\
&= q + 1 + \frac{3V_p}{2} + \frac{T_q}{2}
\end{array}
$$

which shows that one of the curves over $\mathbb{F}_p$ will have the same order as a curve over $\mathbb{F}_q$ whenever we're in the case that $q = p + 1 - T_p$. Accounting for the sign of $\pm \frac{3V_p}{2}$ we see that there is another pair of isomorphic curves in this case as well.

## Implications

There's no reason for us to think that these isomorphic curves pose any security danger for secp256k1. One reason we were interested in investigating this is that if they did, it would have implications for Zcash as well because Halo 2 is built using the Pasta curves, which are also a $2$-cycle of $j$-invariant $0$ curves that have these isomorphic curves attached.

Our main interest is in exploiting the isomorphic curves inside of Halo-style proof-carrying data, where it is convenient (for performance reasons) whenever the two fields $\mathbb{F}_p$ and $\mathbb{F}_q$ can "speak the same language" in a sense. As an example, a Pedersen vector commitment over one of the isomorphic curves can be provably transformed into a vector commitment over the other curve using random point testing, and in fact this test can be "accumulated" within recursive proofs in a similar sense to what is done in Halo.

The main stumbling block is that although the two curves are isomorphic, the actual isomorphism is not efficiently computable --- as far as we're aware. This limits us from the full range of possible tricks and techniques. Here's to hoping that someone can figure out a way to extend this observation to something useful lest it remains just an interesting footnote.