PastaCurves

This module provides the Pasta Curves consisting of: the Pallas curve and its Fp field element, the Vesta curve and its Fq field element, and a variety of supporting functionality such as point/element arithmetic, serialization, and hash-to-curve. The algorithms are NOT constant time; Safety and simplicity are the top priorities.

\[ \text{Pallas: } y^2 = x^3 + 5 \text{ over } F_p(0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001) \]

\[ \text{Vesta: } y^2 = x^3 + 5 \text{ over } F_q(0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001) \]

The order of the Pallas curve is 0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001.

The order of the Vesta curve is 0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001.

The curves are designed such that the order of one matches the field characteristic of the other. For a brief introduction, see the Zcash blog titled "The Pasta Curves for Halo 2 and Beyond" at https://electriccoin.co/blog/the-pasta-curves-for-halo-2-and-beyond/. The reference Rust implementation (which inspired this implementation) can be found at: https://github.com/zcash/pasta_curves.

Example usage of this library implementation:

$ cabal repl

ghci> a = 9 :: Fp

ghci> a*a
0x0000000000000000000000000000000000000000000000000000000000000051

ghci> pointMul a base :: Vesta
Projective {_px = 0x3CDC6A090F2BB3B52714C083929B620FE24ADBCBBD420752108CD7C29E543E5E, 
            _py = 0x08795CD330B3CE5AA63BD2B18DE155AE3C96E8AF9DA2CC742C6BA1464E490161, 
            _pz = 0x1FA26F58F3A641ADFE81775D3D53378D6178B6CCBF14F9BD4AB5F10DEE28D878}

Documentation

type Fp = Fz 28948022309329048855892746252171976963363056481941560715954676764349967630337

Fp is the field element used as a coordinate in the Pallas elliptic curve. It is a type synonym for the internal Fz type, parameterized with the correct modulus. It is also typically used as a scalar to multiply a Vesta elliptic curve point. Note that pointMul does not enforce specific scalar/point combinations.

type Fq = Fz 28948022309329048855892746252171976963363056481941647379679742748393362948097

Fq is the field element used as a coordinate in the Vesta elliptic curve. It is a type synonym for the internal Fz type, parameterized with the correct modulus. It is also typically used as a scalar to multiply a Pallas elliptic curve point. Note that pointMul does not enforce specific scalar/point combinations.

type Pallas = Point 0 5 1 16529367526445723262478303825122581175399563069290091271396079358777790485830 Fp

Pallas represents a point on the Pallas elliptic curve using Fp coordinates. The curve was designed to have the some order as the Fq element's modulus. It is a type synonym for the internal Point type, parameterized with the curves a and b values and the affine base point as base_x and base_y. The underlying point is of type Point a b base_x base_y field.

type Vesta = Point 0 5 1 17521115379873687012324543952179862442514855490857619866290295271833908843935 Fq

Vesta represents a point on the Vesta elliptic curve using Fq coordinates. The curve was designed to have the some order as the Fp element's modulus. It is a type synonym for the internal Point type, parameterized with the curves a and b values and the affine base point as base_x and base_y. The underlying point is of type Point a b base_x base_y field.

class CurvePt a where

The CurvePt class provides the bulk of the functionality related to operations involving points on the elliptic curve. It supports both the Pallas and Vesta curve point types, as well as any other curves (using the arbitrary curve parameters). The curve order must be prime.

Methods

base :: a

Returns the (constant) base point.

fromBytesC :: ByteString -> Maybe a

The fromBytesC function deserializes a compressed point from a ByteString. An invalid ByteString will return Nothing.

isOnCurve :: a -> Bool

The isOnCurve function validates whether the point is on the curve. It is already utilized within fromBytesC deserialization, within hash-to-curve (for redundant safety) and within toBytesC serialization.

negatePt :: a -> a

The negatePt function negates a point.

neutral :: a

Returns the (constant) neutral point.

pointAdd :: a -> a -> a

The pointAdd function adds two curve points on the same elliptic curve.

toBytesC :: a -> ByteString

The toBytesC function serializes a point to a (compressed) ByteStream.

class (CurvePt a, Field b) => Curve a b where

The Curve class provides the elliptic point multiplication operation involving one CurvePt point on an elliptic curve and another Field field element as the scalar operand. It also provides the mapToCurveSimpleSwu which is used in the later stages of hashing-to-curve. It supports both the Pallas and Vesta curve point type.

Methods

pointMul :: b -> a -> a

The pointMul function multiplies a field element by a prime-order curve point. This, for example, could be a Fq field element scalar with a Pallas elliptic curve point (which happens to use Fp co-ordinates).

mapToCurveSimpleSwu :: b -> b -> a

hashToPallas :: ByteString -> Pallas

The hashToPallas function takes an arbitrary ByteString and maps it to a valid point on the Pallas elliptic curve (of unknown relation to the base point).

hashToVesta :: ByteString -> Vesta

The hashToVesta function takes an arbitrary ByteString and maps it to a valid point on the Vesta elliptic curve (of unknown relation to the base point).

rndPallas :: forall g. RandomGen g => g -> (g, Pallas)

The rndPallas function returns a random Pallas point when given a StdGen.

rndVesta :: forall g. RandomGen g => g -> (g, Vesta)

The rndVesta function returns a random Vests point when given a StdGen.

class (Num a, Eq a) => Field a where

The Field class provides useful support functionality for field elements.

Methods

fromBytesF :: ByteString -> Maybe a

The fromBytesF function is the primary deserialization constructor which consumes a big-endian ByteString sized to minimally contain the modulus and returns a field element. The deserialized integer must already be properly reduced to reside within [0..modulus), otherwise Nothing is returned.

_fromBytesF :: ByteString -> a

The _fromBytesF function is the secondary deserialization constructor which consumes an unconstrained big-endian ByteString and returns a internally reduced field element. This function is useful for random testing and hash2Field-style functions.

hash2Field :: ByteString -> String -> String -> (a, a)

The hash2Field function provides intermediate functionality that is suitable for ultimately supporting the hash2Curve function. This function returns a 2-tuple of field elements.

inv0 :: a -> a

The inv0 function returns the multiplicative inverse as calculated by Fermat's Little Theorem (mapping 0 to 0).

isSqr :: a -> Bool

The isSqr function indicates whether the operand has a square root.

rndF :: RandomGen r => r -> (r, a)

The rndF function returns a random (invertible/non-zero) field element.

sgn0 :: a -> Integer

The sgn0 function returns the least significant bit of the field element as an Integer.

shiftR1 :: a -> a

The shiftR1 function shifts the field element one bit to the right, effectively dividing it by two (and discarding the remainder).

sqrt :: a -> Maybe a

The sqrt function implements the variable-time Tonelli-Shanks algorithm to calculate the operand's square root. The function returns Nothing in the event of a problem (such as the operand not being a square, the modulus is not prime, etc).

toBytesF :: a -> ByteString

The toBytesF function serializes an element into a big-endian ByteString sized to minimally contain the modulus.

toI :: a -> Integer

The toI function returns the field element as a properly reduced Integer.

pallasPrime :: Integer

The Pallas field modulus https://neuromancer.sk/std/other/Pallas

vestaPrime :: Integer

The Vesta field modulus https://neuromancer.sk/std/other/Vesta

exampleFp :: Fp

An example Fp element (8).

exampleFq :: Fq

An example Fq element (999).

examplePallasPt :: Pallas

An example Pallas point generated by hashing a message.

exampleVestaPt :: Vesta

An example Vesta point (base * 8).

class Num a where

Basic numeric class.

The Haskell Report defines no laws for Num. However, (+) and (*) are customarily expected to define a ring and have the following properties:

Associativity of (+)

(x + y) + z = x + (y + z)

Commutativity of (+)

x + y = y + x

fromInteger 0 is the additive identity

x + fromInteger 0 = x

negate gives the additive inverse

x + negate x = fromInteger 0

Associativity of (*)

(x * y) * z = x * (y * z)

fromInteger 1 is the multiplicative identity

x * fromInteger 1 = x and fromInteger 1 * x = x

Distributivity of (*) with respect to (+)

a * (b + c) = (a * b) + (a * c) and (b + c) * a = (b * a) + (c * a)

Note that it isn't customarily expected that a type instance of both Num and Ord implement an ordered ring. Indeed, in base only Integer and Rational do.

Minimal complete definition

(+), (*), abs, signum, fromInteger, (negate | (-))

Methods

(+) :: a -> a -> a infixl 6

(-) :: a -> a -> a infixl 6

(*) :: a -> a -> a infixl 7

negate :: a -> a

Unary negation.

abs :: a -> a

Absolute value.

signum :: a -> a

Sign of a number. The functions abs and signum should satisfy the law:

abs x * signum x == x

For real numbers, the signum is either -1 (negative), 0 (zero) or 1 (positive).

fromInteger :: Integer -> a

Conversion from an Integer. An integer literal represents the application of the function fromInteger to the appropriate value of type Integer, so such literals have type (Num a) => a.

Instances

Num Word16

Since: base-2.1

Defined in GHC.Word

Methods

(+) :: Word16 -> Word16 -> Word16

(-) :: Word16 -> Word16 -> Word16

(*) :: Word16 -> Word16 -> Word16

negate :: Word16 -> Word16

abs :: Word16 -> Word16

signum :: Word16 -> Word16

fromInteger :: Integer -> Word16

Num Word32

Since: base-2.1

Defined in GHC.Word

Methods

(+) :: Word32 -> Word32 -> Word32

(-) :: Word32 -> Word32 -> Word32

(*) :: Word32 -> Word32 -> Word32

negate :: Word32 -> Word32

abs :: Word32 -> Word32

signum :: Word32 -> Word32

fromInteger :: Integer -> Word32

Num Word64

Since: base-2.1

Defined in GHC.Word

Methods

(+) :: Word64 -> Word64 -> Word64

(-) :: Word64 -> Word64 -> Word64

(*) :: Word64 -> Word64 -> Word64

negate :: Word64 -> Word64

abs :: Word64 -> Word64

signum :: Word64 -> Word64

fromInteger :: Integer -> Word64

Num Word8

Since: base-2.1

Defined in GHC.Word

Methods

(+) :: Word8 -> Word8 -> Word8

(-) :: Word8 -> Word8 -> Word8

(*) :: Word8 -> Word8 -> Word8

negate :: Word8 -> Word8

abs :: Word8 -> Word8

signum :: Word8 -> Word8

fromInteger :: Integer -> Word8

Num Integer

Since: base-2.1

Defined in GHC.Num

Methods

(+) :: Integer -> Integer -> Integer

(-) :: Integer -> Integer -> Integer

(*) :: Integer -> Integer -> Integer

negate :: Integer -> Integer

abs :: Integer -> Integer

signum :: Integer -> Integer

fromInteger :: Integer -> Integer

Num Natural

Note that Natural's Num instance isn't a ring: no element but 0 has an additive inverse. It is a semiring though.

Since: base-4.8.0.0

Defined in GHC.Num

Methods

(+) :: Natural -> Natural -> Natural

(-) :: Natural -> Natural -> Natural

(*) :: Natural -> Natural -> Natural

negate :: Natural -> Natural

abs :: Natural -> Natural

signum :: Natural -> Natural

fromInteger :: Integer -> Natural

Num Int

Since: base-2.1

Defined in GHC.Num

Methods

(+) :: Int -> Int -> Int

(-) :: Int -> Int -> Int

(*) :: Int -> Int -> Int

negate :: Int -> Int

abs :: Int -> Int

signum :: Int -> Int

fromInteger :: Integer -> Int

Num Word

Since: base-2.1

Defined in GHC.Num

Methods

(+) :: Word -> Word -> Word

(-) :: Word -> Word -> Word

(*) :: Word -> Word -> Word

negate :: Word -> Word

abs :: Word -> Word

signum :: Word -> Word

fromInteger :: Integer -> Word

Integral a => Num (Ratio a)

Since: base-2.0.1

Defined in GHC.Real

Methods

(+) :: Ratio a -> Ratio a -> Ratio a

(-) :: Ratio a -> Ratio a -> Ratio a

(*) :: Ratio a -> Ratio a -> Ratio a

negate :: Ratio a -> Ratio a

abs :: Ratio a -> Ratio a

signum :: Ratio a -> Ratio a

fromInteger :: Integer -> Ratio a

KnownNat n => Num (Zn n)

Defined in Basement.Bounded

Methods

(+) :: Zn n -> Zn n -> Zn n

(-) :: Zn n -> Zn n -> Zn n

(*) :: Zn n -> Zn n -> Zn n

negate :: Zn n -> Zn n

abs :: Zn n -> Zn n

signum :: Zn n -> Zn n

fromInteger :: Integer -> Zn n

(KnownNat n, NatWithinBound Word64 n) => Num (Zn64 n)

Defined in Basement.Bounded

Methods

(+) :: Zn64 n -> Zn64 n -> Zn64 n

(-) :: Zn64 n -> Zn64 n -> Zn64 n

(*) :: Zn64 n -> Zn64 n -> Zn64 n

negate :: Zn64 n -> Zn64 n

abs :: Zn64 n -> Zn64 n

signum :: Zn64 n -> Zn64 n

fromInteger :: Integer -> Zn64 n

Num (CountOf ty)

Defined in Basement.Types.OffsetSize

Methods

(+) :: CountOf ty -> CountOf ty -> CountOf ty

(-) :: CountOf ty -> CountOf ty -> CountOf ty

(*) :: CountOf ty -> CountOf ty -> CountOf ty

negate :: CountOf ty -> CountOf ty

abs :: CountOf ty -> CountOf ty

signum :: CountOf ty -> CountOf ty

fromInteger :: Integer -> CountOf ty

Num (Offset ty)

Defined in Basement.Types.OffsetSize

Methods

(+) :: Offset ty -> Offset ty -> Offset ty

(-) :: Offset ty -> Offset ty -> Offset ty

(*) :: Offset ty -> Offset ty -> Offset ty

negate :: Offset ty -> Offset ty

abs :: Offset ty -> Offset ty

signum :: Offset ty -> Offset ty

fromInteger :: Integer -> Offset ty