Pallas and Elliptic Curves

Pallas and Elliptic Curves

Hopefully know will know about the famous secp256k1 curve, as it is the one that was used by Satoshi Nakamoto in the implementation of Bitcoin. It has since been adopted by Ethereum for the creation of key pairs and in digital signing. Its properties are:

Curve: secp256k1
====================
G:(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 ,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
Bit size: 256
order: 115792089237316195423570985008687907852837564279074904382605163141518161494337
p: 115792089237316195423570985008687907853269984665640564039457584007908834671663
a: 0
b: 7
====================

and where the field (p) is the prime number used with:

y² = x³ +7 (mod p)

The base point on the curve is then the G value defined above.

But have you heard of y²=x³ + 5 (mod p)? Well, this is the base of two new curves: Pallas and Vesta. These are defined as the Pasta curves and named after two minor planets in the solar system. It comes from the creators of the highly popular BLS12–381 curve (a pairing-friendly curve and which is used in zkSnarks), and which is now used extensively within cryptocurrency applications. The work is included in the zCash Halo 2 project [here] and is based on the Tweedle cycle paper [1]:

For Pallas curves, we have the curve parameters of:

y²=x³ + 5 (mod p)

and where

• p = 2²⁵⁴ + 45560315531419706090280762371685220353
• order = 2²⁵⁴ + 45560315531506369815346746415080538113

For y²=x³ + 5, we get th:e classic Weierstrass elliptic curve form:

When we add in the (mod p) part we will get (x,y) points which are integer values. An important feature of the Pasta curves is that they define a cycle of each other, and where the order of each curve equals the base field (p) of the other. This is used within recursive proof systems.

We can use the Kryptology library developed by Coinbase [here] to implement the Pallas curve [here]:

package main

import (
	"fmt"
	"os"
	"strconv"

	"github.com/coinbase/kryptology/pkg/core/curves"
)

func main() {

	m := "abc"
	val1 := 1

	argCount := len(os.Args[1:])

	if argCount > 0 {
		m = os.Args[1]
	}

	if argCount > 1 {
		val1, _ = strconv.Atoi(os.Args[2])

	}

	msg := []byte(m)

	curve := curves.PALLAS()

	toPoint := curve.Point.Hash(msg[:])

	fmt.Printf("Curve type: [%s]\n", curve.Name)

	x := curve.Scalar.New(val1)
	G := curve.Point.Generator()
	xG := curve.Point.Generator().Mul(x)

	lenb := len(G.ToAffineUncompressed())
	Gx := G.ToAffineUncompressed()[0 : lenb/2]
	Gy := G.ToAffineUncompressed()[lenb/2 : lenb]
	xGx := xG.ToAffineUncompressed()[0 : lenb/2]
	xGy := xG.ToAffineUncompressed()[lenb/2 : lenb]

	fmt.Printf("--- Basic point operation ---\n")
	fmt.Printf("x=%x\n", x.Bytes())
	fmt.Printf("G(x,y)=%x, %x\n", Gx, Gy)
	fmt.Printf("xG(x,y)=%x, %x\n  \n", xGx, xGy)

	fmt.Printf("--- Basic hashing method ---\n")
	fmt.Printf("Message: [%s]\n", msg)

	fmt.Printf("\n=== Hash to scalar ===\n")
	toScalar := curve.Scalar.Hash(msg[:])
	fmt.Printf("Scalar: %x\n", toScalar.Bytes())
	fmt.Printf(" Scalar: %s\n", toScalar.BigInt())

	fmt.Printf("\n=== Hash to point ===\n")
	fmt.Printf("Point: %x\n", toPoint.ToAffineUncompressed())

	fmt.Printf("X: %x\n", toPoint.ToAffineUncompressed()[0:lenb/2])
	fmt.Printf("Y: %x\n", toPoint.ToAffineUncompressed()[lenb/2:lenb])

}

A sample run shows that a valid encryption key produces a valid proof, and then an invalid one generates an incorrect proof [here]:

Curve type: [pallas]
--- Basic point operation ---
x=0100000000000000000000000000000000000000000000000000000000000000
G(x,y)=0100000000000000000000000000000000000000000000000000000000000000, bb2aedca237acf1971473d33d45b658f54ee7863f0a9df537c93120aa3b5741b
xG(x,y)=0100000000000000000000000000000000000000000000000000000000000000, bb2aedca237acf1971473d33d45b658f54ee7863f0a9df537c93120aa3b5741b
  
--- Basic hashing method ---
Message: [hello]

=== Hash to scalar ===
Scalar: 9aa0a043085c0d87a5352529461f1bddb4f900590c8240086c8443b77a434322
 Scalar: 15497481330589861685559178500652669593434588772520007648502320661205407015066

=== Hash to point ===
Point: 10b1ab197c646fbcbf52eb2d0ea71ee44b9d3519b120bcd012fb6aabf7d604237d0fbb89dc5c3e86c59d3a319fadc9efff305f879750e7300cede12b16225411
X: 10b1ab197c646fbcbf52eb2d0ea71ee44b9d3519b120bcd012fb6aabf7d60423
Y: 7d0fbb89dc5c3e86c59d3a319fadc9efff305f879750e7300cede12b16225411

Reference

[1] Bowe, S., Grigg, J., & Hopwood, D. (2019). Recursive proof composition without a trusted setup. Cryptol. ePrint Arch., Tech. Rep, 1021, 2019 [here].