Crate starkom_bluesky 

BlueSky

Overview

Starkom and Libernet are entirely based on a finite scalar field known as BlueSky.

BlueSky is a ~255-bit prime field and its order is the prime 0x7ffffffffffffffffffffffffffffffe0673ddf29e9b5547c000000000000001. We call this number p.

p takes slightly less than 50% of the 256-bit range, leaving the MSB unset so that it can be used for arbitrary purposes.

Factors of p-1

p-1, the greatest integer that fits in a BlueSky scalar, is factorized as follows:

$$ 2^{62} \cdot 3^{39} \cdot 31 \cdot 47491 \cdot 20313611 \cdot 117579359 \cdot 880985987837994013 $$

Adicity

The 2-adicity of 62 has been chosen to warrant a very large FFT capacity and evaluation domain for zkSNARK proofs. We didn’t pick a higher 2-adicity because we targeted 64-bit machines, where the implementation of 64-bit exponents is most efficient, so we intentionally kept the exponent below 64.

In addition to that, BlueSky also has 3-adicity. That allows implementing the 3-adic versions of the FFT and FRI folding algorithms. The latter are especially important for recursion because hashing a ternary Merkle tree results in a smaller witness than hashing a binary one (even though the Merkle proof itself is larger!). For certain circuit sizes that are closer to a power of 3, the 3-adic protocol is significantly more efficient.

We chose the exponent 39 for the 3-adicity because $3^{39}$ is roughly equal to $2^{62}$:

$$ 39 \cdot log_2(3) = 61.813… $$

therefore the 3-adic evaluation domain has roughly the same size as the 2-adic one.

S-box optimization

The factorization of p-1 does not contain 5, so raising to 5 is a permutation in the field and $x^5$ can be used as the S-box for algebraic hashes such as Poseidon.

$x^5$ is widely considered optimal for multiplicative complexity because it can be implemented using only 3 gates with quadratic constraints, and still achieves strong nonlinearity and extensive diffusion.

Implementation

The implementation is based on the interface from the starkom-ff crate and uses Montgomery form with four 64-bit limbs.

Structs

Scalar

A scalar over the BlueSky prime field.

Constants

MODULUS

The prime order of the BlueSky field stored as four 64-bit limbs in little endian order.

Functions

from_const

Alias for Scalar::from_const.

parse_scalar

Parses a scalar from a string using the FromStr trait and unwrapping the result.