Home Coins Zcash (ZEC) The Pasta Curves for Halo 2 and Beyond

The Pasta Curves for Halo 2 and Beyond

- Advertisement -


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.

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.

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.

Curve Parameters

Pallas: y^2 = x^3 + 5 over GF(0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001)

Vesta: y^2 = x^3 + 5 over 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:

  1. 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.
  2. 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.
  3. 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.
  4. Both moduli have sparse bit representations in order to improve the performance of Montgomery reduction and other common operations.
  5. 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.
  6. They have the same curve equation, y^2 = x^3 + 5. We ensured that 5 is a primitive root in both fields so that an x-coordinate of zero is not valid, which makes the convenient representation of the point at infinity to be simply all zeroes.
  7. 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.

Naming

Pallas and Vesta are named after 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].

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.


ECC engineers Sean Bowe and Jack Grigg contributed to this article.



Source link

- Advertisement -
Mr Bitcointe
Mr Bitcointehttps://www.bitcointe.com/
“Fact You Need To Know About Cryptocurrency - The first Bitcoin purchase was for pizza.” ― Mohsin Jameel
468FansLike
76FollowersFollow
4,567FollowersFollow
5,261FollowersFollow
1,558FollowersFollow
2,230SubscribersSubscribe
USD - United States Dollar
EUR
1.21
GBP
1.36
CHF
1.13
NOK
0.12
JPY
0.01
CAD
0.78
AUD
0.77

Most Popular

bitcoin
Bitcoin (BTC) $ 32,213.00
ethereum
Ethereum (ETH) $ 1,335.92
ripple
XRP (XRP) $ 0.267295
tether
Tether (USDT) $ 1.00
bitcoin-cash
Bitcoin Cash (BCH) $ 433.71
bitcoin-cash-sv
Bitcoin SV (BSV) $ 174.83
litecoin
Litecoin (LTC) $ 136.36
eos
EOS (EOS) $ 2.64
binancecoin
Binance Coin (BNB) $ 41.47
okb
OKB (OKB) $ 5.62
tezos
Tezos (XTZ) $ 2.88
leo-token
LEO Token (LEO) $ 1.31
cardano
Cardano (ADA) $ 0.343178
monero
Monero (XMR) $ 137.77
stellar
Stellar (XLM) $ 0.260076
chainlink
Chainlink (LINK) $ 23.16
huobi-token
Huobi Token (HT) $ 5.66
tron
TRON (TRX) $ 0.029518
usd-coin
USD Coin (USDC) $ 0.999412
dash
Dash (DASH) $ 104.25
neo
NEO (NEO) $ 23.68
iota
IOTA (MIOTA) $ 0.430696
nem
NEM (XEM) $ 0.231909
zcash
Zcash (ZEC) $ 87.23
maker
Maker (MKR) $ 1,384.45
paxos-standard
Paxos Standard (PAX) $ 0.998409
ethereum-classic
Ethereum Classic (ETC) $ 7.44
vechain
VeChain (VET) $ 0.029674
true-usd
TrueUSD (TUSD) $ 1.00
ftx-token
FTX Token (FTT) $ 9.98
kucoin-shares
KuCoin Token (KCS) $ 1.14
waves
Waves (WAVES) $ 6.82