r1csqap

README

R1CS to Quadratic Arithmetic Program

R1CS to QAP

• Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture, Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza https://eprint.iacr.org/2013/879.pdf
• Vitalik Buterin blog post about QAP https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
• Ariel Gabizon in Zcash blog https://z.cash/blog/snark-explain5
• Lagrange polynomial Wikipedia article https://en.wikipedia.org/wiki/Lagrange_polynomial

Usage

• R1CS to QAP

pf := NewPolynomialField(f)

b0 := big.NewInt(int64(0))
b1 := big.NewInt(int64(1))
b3 := big.NewInt(int64(3))
b5 := big.NewInt(int64(5))
b9 := big.NewInt(int64(9))
b27 := big.NewInt(int64(27))
b30 := big.NewInt(int64(30))
b35 := big.NewInt(int64(35))
a := [][]*big.Int{
  []*big.Int{b0, b1, b0, b0, b0, b0},
  []*big.Int{b0, b0, b0, b1, b0, b0},
  []*big.Int{b0, b1, b0, b0, b1, b0},
  []*big.Int{b5, b0, b0, b0, b0, b1},
}
b := [][]*big.Int{
  []*big.Int{b0, b1, b0, b0, b0, b0},
  []*big.Int{b0, b1, b0, b0, b0, b0},
  []*big.Int{b1, b0, b0, b0, b0, b0},
  []*big.Int{b1, b0, b0, b0, b0, b0},
}
c := [][]*big.Int{
  []*big.Int{b0, b0, b0, b1, b0, b0},
  []*big.Int{b0, b0, b0, b0, b1, b0},
  []*big.Int{b0, b0, b0, b0, b0, b1},
  []*big.Int{b0, b0, b1, b0, b0, b0},
}
alphas, betas, gammas, zx := pf.R1CSToQAP(a, b, c)
fmt.Println(alphas)
fmt.Println(betas)
fmt.Println(gammas)
fmt.Println(z)

w := []*big.Int{b1, b3, b35, b9, b27, b30}
ax, bx, cx, px := pf.CombinePolynomials(w, alphas, betas, gammas)
fmt.Println(ax)
fmt.Println(bx)
fmt.Println(cx)
fmt.Println(px)

hx := pf.DivisorPolinomial(px, zx)
fmt.Println(hx)

Documentation

Index

• func ArrayOfBigZeros(num int) []*big.Int
• func BigArraysEqual(a, b []*big.Int) bool
• func Transpose(matrix [][]*big.Int) [][]*big.Int
• type PolynomialField
  • func NewPolynomialField(f fields.Fq) PolynomialField
  • func (pf PolynomialField) Add(a, b []*big.Int) []*big.Int
  • func (pf PolynomialField) CombinePolynomials(r []*big.Int, ap, bp, cp [][]*big.Int) ([]*big.Int, []*big.Int, []*big.Int, []*big.Int)
  • func (pf PolynomialField) Div(a, b []*big.Int) ([]*big.Int, []*big.Int)
  • func (pf PolynomialField) DivisorPolynomial(px, z []*big.Int) []*big.Int
  • func (pf PolynomialField) Eval(v []*big.Int, x *big.Int) *big.Int
  • func (pf PolynomialField) LagrangeInterpolation(v []*big.Int) []*big.Int
  • func (pf PolynomialField) Mul(a, b []*big.Int) []*big.Int
  • func (pf PolynomialField) NewPolZeroAt(pointPos, totalPoints int, height *big.Int) []*big.Int
  • func (pf PolynomialField) R1CSToQAP(a, b, c [][]*big.Int) ([][]*big.Int, [][]*big.Int, [][]*big.Int, []*big.Int)
  • func (pf PolynomialField) Sub(a, b []*big.Int) []*big.Int

Functions

func ArrayOfBigZeros

func ArrayOfBigZeros(num int) []*big.Int

ArrayOfBigZeros creates a *big.Int array with n elements to zero

func BigArraysEqual

func BigArraysEqual(a, b []*big.Int) bool

func Transpose

func Transpose(matrix [][]*big.Int) [][]*big.Int

Transpose transposes the *big.Int matrix

Types

type PolynomialField

type PolynomialField struct {
	F fields.Fq
}

PolynomialField is the Polynomial over a Finite Field where the polynomial operations are performed

func NewPolynomialField

func NewPolynomialField(f fields.Fq) PolynomialField

NewPolynomialField creates a new PolynomialField with the given FiniteField

func (PolynomialField) Add

func (pf PolynomialField) Add(a, b []*big.Int) []*big.Int

Add adds two polinomials over the Finite Field

func (PolynomialField) CombinePolynomials

func (pf PolynomialField) CombinePolynomials(r []*big.Int, ap, bp, cp [][]*big.Int) ([]*big.Int, []*big.Int, []*big.Int, []*big.Int)

CombinePolynomials combine the given polynomials arrays into one, also returns the P(x)

func (PolynomialField) Div

func (pf PolynomialField) Div(a, b []*big.Int) ([]*big.Int, []*big.Int)

Div divides two polinomials over the Finite Field, returning the result and the remainder

func (PolynomialField) DivisorPolynomial

func (pf PolynomialField) DivisorPolynomial(px, z []*big.Int) []*big.Int

DivisorPolynomial returns the divisor polynomial given two polynomials

func (PolynomialField) Eval

func (pf PolynomialField) Eval(v []*big.Int, x *big.Int) *big.Int

Eval evaluates the polinomial over the Finite Field at the given value x

func (PolynomialField) LagrangeInterpolation

func (pf PolynomialField) LagrangeInterpolation(v []*big.Int) []*big.Int

LagrangeInterpolation performs the Lagrange Interpolation / Lagrange Polynomials operation

func (PolynomialField) Mul

func (pf PolynomialField) Mul(a, b []*big.Int) []*big.Int

Mul multiplies two polinomials over the Finite Field

func (PolynomialField) NewPolZeroAt

func (pf PolynomialField) NewPolZeroAt(pointPos, totalPoints int, height *big.Int) []*big.Int

NewPolZeroAt generates a new polynomial that has value zero at the given value

func (PolynomialField) R1CSToQAP

func (pf PolynomialField) R1CSToQAP(a, b, c [][]*big.Int) ([][]*big.Int, [][]*big.Int, [][]*big.Int, []*big.Int)

R1CSToQAP converts the R1CS values to the QAP values

func (PolynomialField) Sub

func (pf PolynomialField) Sub(a, b []*big.Int) []*big.Int

Sub subtracts two polinomials over the Finite Field