The Pasta Curves for Halo 2 and Beyond(Halo 2及更高版本的Pasta曲线)

Halo 2及更高版本的Pasta曲线

origin from: The Pasta Curves for Halo 2 and Beyond - Electric Coin Company

One of the most enjoyable things we do at ECC is working on cutting-edge cryptography. In our continued effort to ensure that Zcash benefits as much as possible from groundbreaking crypto innovations, part of what we do is to design our own cryptographic constructs to improve performance and security. For the Halo 2 project, we have designed a new cycle of elliptic curves, Pallas and Vesta, which we collectively refer to as the Pasta curves.

我们在ECC最爱做的事情之前就是致力于研究尖端的密码学,我们持续不断的努力确保zcash能更多的受益于开创性的密码学发明中, 我们一部分的工作就是设计我们自己的密码学构造,提升性能和安全性。 对 Halo2 这个项目,我们已经设计了一个新的椭圆曲线循环, Pallas 和 Vesta, 我们合起来称之为 Pasta 曲线。

Using the same elliptic curves as other projects is helpful in numerous ways. As an example, the pairing-friendly curve BLS12-381 that we designed for Sapling is now a de facto standard in the cryptocurrency world, being deployed in fundamental components of protocols such as Ethereum 2. This has allowed us to benefit from other projects’ research and development in BLS12-381, and it has increased the opportunities for cross-platform interoperability.

和其他项目使用相同的椭圆曲线有诸多好处。 比如说,我们给 Sapling 版本设计的对称友好型曲线BLS12-381,目前已经成为加密货币行业的事实上的标准,已经被应用在许多协议的基础组件中,比如以太坊 2.0中。 我们就可以从其他项目对于 BLS12-381的研发中收益,也就提高了跨平台互操作的可能性。

Since we originally presented the Tweedle cycle of curves in the Halo paper, we’ve had time to learn more about which engineering and cryptographic properties are useful (particularly the low-degree isogeny and 2-adicity tweaks described below). We invite projects that plan to deploy protocols using ideas from Halo to employ the same curve cycle, so that we can collectively benefit from shared analysis and engineering effort.

自从我们开始在 Halo的白皮书中展示过 Tweedle 曲线的周期,我们也就有了时间去学习更多关于实用的工程学和密码学的特性(尤其是下文描述的低度同源以及二元微调), 我们邀请其他想使用从 Halo 部署同样曲线周期获得灵感的项目去部署他们自己协议的, 这样我们就能共同的收益于共同的分析研究和工程成果。


Curve Parameters(曲线的参数)

Pallas:y^2 = x^3 + 5y2=x3+5overGF(0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001)GF(0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001)Vesta:y^2 = x^3 + 5y2=x3+5overGF(0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001)GF(0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001)

Like the Tweedle curves, the Pasta curves form a cycle with one another: the order of each curve is exactly the base field of the other. This property is critical to the efficiency of recursive proof systems. They are designed to be highly 2-adic, meaning that a large power-of-two multiplicative subgroup exists in each field. This is important for the performance of polynomial arithmetic over their scalar fields and is essential for protocols similar to PLONK.

Several other criteria are meant to ensure that the curves perform well and have nice symmetries:

Unlike with the Tweedle curves, both Pallas and Vesta have low-degree isogenies (both of degree 3) from curves with a nonzero j-invariant. This is useful when hashing to the curve using the “simplified SWU” algorithm, and perhaps for other not-yet-known purposes.

They have the same 2-adicity, 32, unlike the Tweedle curves that had 2-adicity of 33 and 34. This simplifies implementations and may assist in square root performance (used for point decompression and internally to Halo 2) due to a new algorithm recently discovered; 32 is more convenient for this algorithm.

They are both constructed over 255-bit prime fields. This gives 126-bit security against Pollard rho attacks, and allows the compressed representation of points to be an even 32 bytes.

Both moduli have sparse bit representations in order to improve the performance of Montgomery reduction and other common operations.

They both support an endomorphism that can be used to improve performance of scalar multiplication, similar to that available for secp256k1. This is even more useful after the recent expiry of related patents.

They have the same curve equation, y^2 = x^3 + 5y2=x3+5. For curves using this cycle construction it is also the case that an xx-coordinate of zero is not valid, which allows a convenient representation of all zeroes for the point at infinity.

Both fields do not have 5-order, 7-order, etc. multiplicative subgroups, so that exponentiation by these small primes is a permutation — a crucial requirement for algebraic hash functions such as Rescue and Poseidon.

These curves can be reproducibly obtained using a curve search utility we’ve published. The tool uses various techniques to quickly search the large space of elliptic curves for a pair that satisfies our performance and security goals. For the Tweedle curves we also ensured that the quadratic twist security for both curves was high; this criterion has been dropped for the Pasta curves because it was only defence-in-depth (for curve formulae that we do not recommend using) and was too strict of a requirement that precluded other more important design considerations.


Pasta is a portmanteau of Pa llas and Ve sta — two minor planets in the solar system: 2 Pallas and 4 Vesta. Like the curves, the minor planets are close in size; Pallas is the smaller minor planet and also the curve over the smaller base field. Pallas and Vesta were two of the earliest minor planets to be discovered, both by the German astronomer Heinrich Olbers. They are visible with binoculars when in favourable positions [2 Pallas, 4 Vesta].

Pasta 是 Pallas 和 Vesta 的合成词, 太阳系的两个小行星:2 Pallas 和 4Vesta. 就想曲线一样,这小行星大小非常相近,Pallas 行星是比较小的那一个,正如这个曲线的领域也更小。 Pallas 和 Vesta 是两个最早被德国宇航员 Heinrich Olbers 发现的小行星。在合适的位置上我们用双筒望远镜可以看到 2Pallas,4Vesta这两个小行星。

An unpublished 1805 work of Carl Friedrich Gauss connects 2 Pallas to the Halo proof system: Gauss developed a method of computing discrete Fourier transforms, which are used in Halo, partly to track the orbit of this minor planet. His method was very similar to the one published in 1965 byJames CooleyandJohn Tukey, who are generally credited for the invention of the modern generic FFT algorithm.

尚未公布的由Carl Friedrich Gauss开发的代号为1805的工作将2 Pallas 和 Halo凭证系统关联起来。 Gauss 开发了一个计算离散傅里叶变换的方法,这个方法被用在 halo 中, 部分追踪到这个小行星的轨迹。 他的方法非常类似于于 1965 年由James CooleyJohn Tukey发布的类似, 这两个人的被认定发明了现代类FTT算法。

In Greek mythology, Pallas (or Pallas Athena) is a goddess associated with wisdom, handicraft, and warfare, while Vesta is a goddess of the hearth, home, and family. In the original Temple of Vesta in Rome stood the Palladium, a statue of Pallas Athena. The sacred fire of Vesta and the Palladium were both held to be symbols of the safety and prosperity of Rome — just as we aim for these curves to provide a foundation for the future security of the Zcash protocol.

Pallas Athena and Vesta have another connection to Halo: they are the names of Artificial Intelligences in the universe of the Halo video games.

在希腊神话中, Pallas (或者说 Pallas Athena 帕拉斯雅典娜) 是智慧、手工艺品、战争之神, Vesta是灶台、住宅、家庭之神。 在早期的屹立在维斯塔神庙的守护神中,有帕拉斯雅典娜的雕像。 维斯塔神圣之火和守护神是罗马安全和繁荣的象征。 正如我们希望这些曲线能给zcash 协议提供未来安全基础。

1 Like