第14回zk部

Roud1~2

https://scrapbox.io/files/63ee1c720aea9e001c45f6be.png

code:round1

# # Compute wire assignments for A, B, C, corresponding:

A_values = []

B_values = []

C_values = []

for w in program.wires():

# # Construct A, B, C Lagrange interpolation polynomials for

# # A_values, B_values, C_values

self.A = Polynomial(A_values, Basis.LAGRANGE)

self.B = Polynomial(B_values, Basis.LAGRANGE)

self.C = Polynomial(C_values, Basis.LAGRANGE)

# Compute a_1, b_1, c_1 commitments to A, B, C polynomials

a_1 = setup.commit(self.A)

b_1 = setup.commit(self.B)

c_1 = setup.commit(self.C)

code:round2

# Using A, B, C, values, and pk.S1, pk.S2, pk.S3, compute

# Z_values for permutation grand product polynomial Z

#

# Note the convenience function:

# self.rlc(val1, val2) = val_1 + self.beta * val_2 + gamma

# random liner combination = rlc?

w = Scalar.root_of_unity(group_order)

Z_values = []

prod = 1

Z_values.append(prod)

for j in range(group_order):

Z_values.append(prod)

...

# Construct Z, Lagrange interpolation polynomial for Z_values

# Cpmpute z_1 commitment to Z polynomial

Z_poly = Polynomial(Z_scalar, basis=Basis.LAGRANGE)

z_1 = setup.commit(Z_poly)

https://scrapbox.io/files/641e504c7f5f7f001b966b5e.png

code:round3.py

group_order = self.group_order

setup = self.setup

# Compute the quotient polynomial

# List of roots of unity at 4x fineness, i.e. the powers of µ

# where µ^(4n) = 1

X = Scalar.roots_of_unity(group_order*4)

# print(powers_of_mu)

# Using self.fft_expand, move A, B, C into coset extended Lagrange basis

A = self.fft_expand(self.A)

B = self.fft_expand(self.B)

C = self.fft_expand(self.C)

# Expand public inputs polynomial PI into coset extended Lagrange

PI = self.fft_expand(self.PI)

# Expand selector polynomials pk.QL, pk.QR, pk.QM, pk.QO, pk.QC

# into the coset extended Lagrange basis

QL = self.fft_expand(self.pk.QL)

QR = self.fft_expand(self.pk.QR)

QM = self.fft_expand(self.pk.QM)

QO = self.fft_expand(self.pk.QO)

QC = self.fft_expand(self.pk.QC)

# Expand permutation grand product polynomial Z into coset extended

# Lagrange basis

Z = self.fft_expand(self.Z)

# Expand shifted Z(ω) into coset extended Lagrange basis

Z_w = self.fft_expand(self.Z.shift(1))

# Expand permutation polynomials pk.S1, pk.S2, pk.S3 into coset

# extended Lagrange basis

S1 = self.fft_expand(self.pk.S1)

S2 = self.fft_expand(self.pk.S2)

S3 = self.fft_expand(self.pk.S3)

# Compute Z_H = X^N - 1, also in evaluation form in the coset

Z_H = Z_H_monomial.fft()

X_eval = X_coeffs.fft()

X = self.fft_expand(X_eval)

one_eval = one_coeff.fft()

one = self.fft_expand(one_eval)

# Compute L0, the Lagrange basis polynomial that evaluates to 1 at x = 1 = ω^0

# and 0 at other roots of unity

# Expand L0 into the coset extended Lagrange basis

L0 = self.fft_expand(

)

gate_constraint = A * QL + B * QR + A * B * QM + C * QO + PI + QC

perm_constraint = Z * self.rlc(A, X)* self.rlc(B, X * Scalar(2)) * self.rlc(C, X* Scalar(3)) - Z_w *self.rlc(A, S1) * self.rlc(B, S2) *self.rlc(C, S3)

edge_constraint = (Z - one) * L0

perm_constraint * self.alpha

QUOT_big = (gate_constraint + perm_constraint * self.alpha + edge_constraint * (self.alpha ** 2) )/Z_H

# Sanity check: QUOT has degree < 3n

assert (

)

print("Generated the quotient polynomial")

# Split up T into T1, T2 and T3 (needed because T has degree 3n, so is

# too big for the trusted setup)

T = self.expanded_evals_to_coeffs(QUOT_big)

T1 = Polynomial(T1_coeff, Basis.MONOMIAL).fft()

T2 = Polynomial(T2_coeff, Basis.MONOMIAL).fft()

T3 = Polynomial(T3_coeff, Basis.MONOMIAL).fft()

# Sanity check that we've computed T1, T2, T3 correctly

fft_cofactor = self.fft_cofactor

assert (

T1.barycentric_eval(fft_cofactor)

+ T2.barycentric_eval(fft_cofactor) * fft_cofactor**group_order

+ T3.barycentric_eval(fft_cofactor) * fft_cofactor ** (group_order * 2)

print("Generated T1, T2, T3 polynomials")

# Compute commitments t_lo_1, t_mid_1, t_hi_1 to T1, T2, T3 polynomials

t_lo_1 = setup.commit(T1)

t_mid_1 = setup.commit(T2)

t_hi_1 = setup.commit(T3)

# Return t_lo_1, t_mid_1, t_hi_1

self.A = A

self.B = B

self.C = C

self.T1 = T1

self.T2 = T2

self.T3 = T3

self.T = T

self.pk.S1 = S1

self.pk.S2 = S2

self.pk.S3 = S3

self.QL = QL

self.QR = QR

self.QM = QM

self.QO = QO

self.PI = PI

self.QC = QC

self.Z = Z

self.Z_w = Z_w

self.Z_H = Z_H

self.L0 = L0

code:round4.py

# Compute evaluations to be used in constructing the linearization polynomial.

# Compute a_eval = A(zeta)

a_eval = self.A.barycentric_eval(self.zeta)

# Compute b_eval = B(zeta)

b_eval = self.B.barycentric_eval(self.zeta)

# Compute c_eval = C(zeta)

c_eval = self.C.barycentric_eval(self.zeta)

# Compute s1_eval = pk.S1(zeta)

s1_eval = self.pk.S1.barycentric_eval(self.zeta)

# Compute s2_eval = pk.S2(zeta)

s2_eval = self.pk.S2.barycentric_eval(self.zeta)

# Compute z_shifted_eval = Z(zeta * ω)

z_shifted_eval = self.Z.barycentric_eval(self.zeta * self.omega)

self.a_eval = a_eval

self.b_eval = b_eval

self.c_eval = c_eval

self.s1_eval = s1_eval

self.s2_eval = s2_eval

self.z_shifted_eval = z_shifted_eval