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 (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
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ArrayOfBigZeros ¶
ArrayOfBigZeros creates a *big.Int array with n elements to zero
func BigArraysEqual ¶
Types ¶
type PolynomialField ¶
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 ¶
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 ¶
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 ¶
NewPolZeroAt generates a new polynomial that has value zero at the given value
Source Files