# 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.
Last changed by  
 
ebfull
2715

Read more

Faster PLONK verification for Halo-like PCD

Prior to our discovery of Halo, proof-carrying data (PCD) was achieved using a straightforward transformation: find a SNARK that has a sublinear-time verifier in the circuit size, embed this verifier into the circuit, and now recursively compose your proofs. Linear-time verifiers can't work with this recursion approach because the recursive circuit will never converge to a finite size. The problem is that the most attractive SNARKs with sublinear-time verifiers that we are aware of today have either pairings and trusted setups (and are over huge elliptic curves) or have large proofs in practice. The inner product argument is a protocol that does not require a trusted setup and can be built over ordinary and efficient elliptic curves. It can be used as a subprotocol to build a wide variety of different SNARKs. Unfortunately, its verification routine is linear-time in the circuit size. As part of Halo, we sidestepped this problem by discovering a technique that could be used to build PCD using the inner product argument anyway. The idea was later formalized into a more general concept called an accumulation scheme. Informally, here's how it works: There's this object called an accumulator. This object does not grow in size. You create a proof that some previous proof(s) exist and that some previous state of the accumulator was "updated" with these proofs, producing a new accumulator state. Checking that this update to the accumulator was performed correctly is asymptotically more efficient than the circuit size of the proofs being added to it, allowing your circuits to converge in size. At any point, you can check the accumulator using a linear-time "decision" procedure. If it checks out, all the proofs previously added to the accumulator are correct by induction. This approach allowed us to use the inner product argument for PCD, and later works figured out that an even larger class of protocols can be used to build IVC/PCD, including ones that are not succinct at all and others that don't even have linearly homomorphic commitment schemes.

12/3/2021
Read more from ebfull
Published on HackMD