`pasta_curves`

This crate provides an implementation of the Pasta elliptic curve constructions, Pallas and Vesta. More details about the Pasta curves can be found in this blog post.

Minimum Supported Rust Version

Requires Rust 1.51 or higher.

Minimum supported Rust version can be changed in the future, but it will be done with a minor version bump.

Curve Descriptions

Pallas: y² = x³ + 5 over GF(0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001).
Vesta: y² = x³ + 5 over GF(0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001).

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.

These curves can be reproducibly obtained using a curve search utility we’ve published.

License

Licensed under either of

Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Design

Note on Language

We use slightly different language than others to describe PLONK concepts. Here's the overview:

We like to think of PLONK-like arguments as tables, where each column corresponds to a "wire". We refer to entries in this table as "cells".
We like to call "selector polynomials" and so on "fixed columns" instead. We then refer specifically to a "selector constraint" when a cell in a fixed column is being used to control whether a particular constraint is enabled in that row.
We call the other polynomials "advice columns" usually, when they're populated by the prover.
We use the term "rule" to refer to a "gate" like $A (X) \cdot q_{A} (X) + B (X) \cdot q_{B} (X) + A (X) \cdot B (X) \cdot q_{M} (X) + C (X) \cdot q_{C} (X) = 0.$
- TODO: Check how consistent we are with this, and update the code and docs to match.

Implementation

Fields

The Pasta curves are designed to be highly 2-adic, meaning that a large $2^{S}$ multiplicative subgroup exists in each field. That is, we can write $p - 1 \equiv 2^{S} \cdot T$ with $T$ odd. For both Pallas and Vesta, $S = 32$ ; this helps to simplify the field implementations.

Sarkar square-root algorithm (table-based variant)

We use a technique from Sarkar2020 to compute square roots in pasta_curves. The intuition behind the algorithm is that we can split the task into computing square roots in each multiplicative subgroup.

Suppose we want to find the square root of $u$ modulo one of the Pasta primes $p$ , where $u$ is a non-zero square in $Z_{p}^{\times}$ . We define a $2^{S}$ root of unity $g = z^{T}$ where $z$ is a non-square in $Z_{p}^{\times}$ , and precompute the following tables:

$g t ab = ⎣ ⎡ g^{0} (g^{2^{8}})^{0} (g^{2^{16}})^{0} (g^{2^{24}})^{0} g^{1} (g^{2^{8}})^{1} (g^{2^{16}})^{1} (g^{2^{24}})^{1} ... ... ... ... g^{2^{8} - 1} (g^{2^{8}})^{2^{8} - 1} (g^{2^{16}})^{2^{8} - 1} (g^{2^{24}})^{2^{8} - 1} ⎦ ⎤$

$in v t ab = [(g^{2^{- 24}})^{0} (g^{2^{- 24}})^{1} ... (g^{2^{- 24}})^{2^{8} - 1}]$

Let $v = u^{(T - 1) /2}$ . We can then define $x = uv \cdot v = u^{T}$ as an element of the $2^{S}$ multiplicative subgroup.

Let $x_{3} = x, x_{2} = x_{3}^{2^{8}}, x_{1} = x_{2}^{2^{8}}, x_{0} = x_{1}^{2^{8}} .$

i = 0, 1

Using $in v t ab$ , we lookup $t_{0}$ such that $x_{0} = (g^{2^{- 24}})^{t_{0}} ⟹ x_{0} \cdot g^{t_{0} \cdot 2^{24}} = 1.$

Define $α_{1} = x_{1} \cdot (g^{2^{16}})^{t_{0}} .$

i = 2

Lookup $t_{1}$ s.t. $α_{1} = (g^{2^{- 24}})^{t_{1}} ⟹ x_{1} \cdot (g^{2^{16}})^{t_{0}} = (g^{2^{- 24}})^{t_{1}} ⟹ x_{1} \cdot g^{(t_{0} + 2^{8} \cdot t_{1}) \cdot 2^{16}} = 1.$

Define $α_{2} = x_{2} \cdot (g^{2^{8}})^{t_{0} + 2^{8} \cdot t_{1}} .$

i = 3

Lookup $t_{2}$ s.t.

$α_{2} = (g^{2^{- 24}})^{t_{2}} ⟹ x_{2} \cdot (g^{2^{8}})^{t_{0} + 2^{8} \cdot t_{1}} = (g^{2^{- 24}})^{t_{2}} ⟹ x_{2} \cdot g^{(t_{0} + 2^{8} \cdot t_{1} + 2^{16} \cdot t_{2}) \cdot 2^{8}} = 1.$

Define $α_{3} = x_{3} \cdot g^{t_{0} + 2^{8} \cdot t_{1} + 2^{16} \cdot t_{2}} .$

Final result

Lookup $t_{3}$ such that

$α_{3} = (g^{2^{- 24}})^{t_{3}} ⟹ x_{3} \cdot g^{t_{0} + 2^{8} \cdot t_{1} + 2^{16} \cdot t_{2}} = (g^{2^{- 24}})^{t_{3}} ⟹ x_{3} \cdot g^{t_{0} + 2^{8} \cdot t_{1} + 2^{16} \cdot t_{2} + 2^{24} \cdot t_{3}} = 1.$

Let $t = t_{0} + 2^{8} \cdot t_{1} + 2^{16} \cdot t_{2} + 2^{24} \cdot t_{3}$ .

We can now write $x_{3} \cdot g^{t} = 1 ⟹ ⟹ ⟹ ⟹ x_{3} u v^{2} uv uv \cdot g^{t /2} = = = = g^{- t} g^{- t} v^{- 1} \cdot g^{- t} v^{- 1} \cdot g^{- t /2} .$

Squaring the RHS, we observe that $(v^{- 1} g^{- t /2})^{2} = v^{- 2} g^{- t} = u .$ Therefore, the square root of $u$ is $uv \cdot g^{t /2}$ ; the first part we computed earlier, and the second part can be computed with three multiplications using lookups in $g t ab$ .

The Pasta Book