Select SageMath Kernel First#
F193.<a> = GF(193)
Fp=F193
var_names = ['X' + str(i) for i in range(100)] + ['X']
R = PolynomialRing(QQ, var_names)
R.inject_variables()
global_vars = R.gens()
Defining X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, X23, X24, X25, X26, X27, X28, X29, X30, X31, X32, X33, X34, X35, X36, X37, X38, X39, X40, X41, X42, X43, X44, X45, X46, X47, X48, X49, X50, X51, X52, X53, X54, X55, X56, X57, X58, X59, X60, X61, X62, X63, X64, X65, X66, X67, X68, X69, X70, X71, X72, X73, X74, X75, X76, X77, X78, X79, X80, X81, X82, X83, X84, X85, X86, X87, X88, X89, X90, X91, X92, X93, X94, X95, X96, X97, X98, X99, X
class MLE:
def __init__(self, poly):
self.vars = global_vars
self.mle = None
# if type of poly is list, then it's a list of evals
if isinstance(poly, list):
if len(poly) == 0:
self.k = 0
return
self.k = log(len(poly), 2)
self.from_evals(poly)
else:
self.k = len(poly.variables())
self.mle = poly
def __repr__(self):
return str(self.mle)
# fallback to mle's method
def __getattr__(self, name):
return getattr(self.mle, name)
# eval means f(0,0,...,0) = evals[0]
# f(0,0,...,1) = evals[1]
# ...
# f(1,1,...,1) = evals[2^k-1]
# f(X0, X1) = (1-X0)(1-X1)evals[0] + X0(1-X1)evals[1] + (1-X0)X1*evals[2] + X0X1*evals[3]
def from_evals(self, evals):
vars = self.vars[:len(evals)]
bit_len = self.k
mle_poly = 0
for i in range(len(evals)):
mask = MLE.get_bit_mask(i, bit_len)
prods = prod([var if enabled else (1-var) for var, enabled in zip(self.vars, mask)])
mle_poly += evals[i] * prods
self.mle = mle_poly
return self
def get_evals(self):
vars = self.vars[:2**self.k]
evals = []
k = self.k
if k == 0:
return [self.mle]
for i in range(2**k):
mask = self.get_bit_mask(i, k)
mle_tmp = self.mle
for j in range(k):
mle_tmp = mle_tmp.subs({vars[j]: mask[j]})
evals.append(mle_tmp)
return evals
def get_coeffs(self):
coeffs = []
vars = self.vars[:2**self.k]
k = self.k
if k == 0:
return [self.mle]
for i in range(2**k):
mask = self.get_bit_mask(i, k)
monomial = R(prod([var if bit else 1 for var, bit in zip(vars, mask)]))
coeff = self.mle.monomial_coefficient(monomial)
coeffs.append(coeff)
return coeffs
def from_coeffs(self, coeffs):
self.k = log(len(coeffs), 2)
self.mle = 0
vars = self.vars[:2**self.k]
k = self.k
for i in range(2**k):
mask = self.get_bit_mask(i, k)
monomial = R(prod([var if bit else 1 for var, bit in zip(vars, mask)]))
coeff = coeffs[i]
self.mle += coeff * monomial
return self
@staticmethod
def get_bit_mask(num, bits):
mask = []
for i in range(bits):
mask.append(num & 1)
num >>= 1
return mask
@staticmethod
def evals_to_univar(evals):
uni_poly = 0
for i in range(len(evals)):
uni_poly += evals[i] * X^i
return uni_poly
def extend(self, n):
k = self.k
evals = self.get_evals()
# extend evals to n
for i in range(n - k):
evals = evals + evals
return MLE(evals)
def to_uni(self):
evals = self.get_evals()
return MLE.evals_to_univar(evals)
ZeroMorph#
While KZG is a powerful commitment scheme, it’s limited to univariate polynomials. However, for techniques like sumcheck, we require multivariate polynomials (hereafter referred to as MLE - Multilinear Extension).
KZG proves the existence of: q(X) = (f(X) - f(a)) / (X - a)
In MLE, we have a similar quotient theorem. For example: f(X0, X1, X2) = (X0-a)*q0 + (X1-b)*q1(X0) + (X2-c)*q2(X0, X1)
To leverage the power of KZG for MLE, we need to find a way to treat the MLE as a univariate polynomial. This requires a proper mapping from MLE to a univariate form.
ZeroMorph provides this crucial mapping.
Before delving into the specifics of this mapping, let’s first examine how MLE encodes values.
The following image demonstrates MLE encoding of 8 numbers on a 3D cube.
mle_evals = [1, 1, 2, 3, 5, 8, 13, 21]
vertices = [
([0,0,0], mle_evals[0]), ([0,0,1], mle_evals[1]), ([0,1,0], mle_evals[2]), ([0,1,1], mle_evals[3]),
([1,0,0], mle_evals[4]), ([1,0,1], mle_evals[5]), ([1,1,0], mle_evals[6]), ([1,1,1], mle_evals[7])
]
g = Graphics()
for x in [0,1]:
for y in [0,1]:
g += line3d([(x,y,0), (x,y,1)], color='black')
for x in [0,1]:
for z in [0,1]:
g += line3d([(x,0,z), (x,1,z)], color='black')
for y in [0,1]:
for z in [0,1]:
g += line3d([(0,y,z), (1,y,z)], color='black')
for (x,y,z), value in vertices:
g += text3d(f"({x},{y},{z})={value}", (x,y,z), fontsize=15)
note = "This 3D cube visualization represents a multilinear extension, with each vertex storing the corresponding function value."
text_position = (0.5, 0.5, -0.5)
g += text3d(note, text_position, fontsize=15)
show(g, aspect_ratio=(1, 1, 1), ticks=[[0,2,1], [0,2,1], [0,2,1]], frame=False)
This cube shows the MLE evaluation form. Then we convert it into coefficient form and map it into the Uni-Variate polynomial.
mle = MLE(mle_evals)
print(f"mle: {mle}")
print(f"mle evals: {mle.get_evals()}")
print(f"U(mle): {mle.to_uni()}")
mle: 4*X0*X1*X2 + X0*X1 + 3*X0*X2 + 7*X1*X2 + X1 + 4*X2 + 1
mle evals: [1, 1, 2, 3, 5, 8, 13, 21]
U(mle): 21*X^7 + 13*X^6 + 8*X^5 + 5*X^4 + 3*X^3 + 2*X^2 + X + 1
Then we commit this polynomial. The quotient polynomial also applies the same procedure.
point = [1, 2, 3]
q2, r2 = mle.quo_rem((X2-point[2]))
print(f"q2: {q2}")
print(f"r2: {r2}")
q1, r1 = r2.quo_rem((X1-point[1]))
print(f"q1: {q1}")
print(f"r1: {r1}")
q0, r0 = r1.quo_rem((X0-point[0]))
print(f"q0: {q0}")
print(f"r0: {r0}")
v = r0
# check if mle - v == q0*(X0-point[0]) + q1*(X1-point[1]) + q2*(X2-point[2])
print(f"mle - v: {mle - v}")
print(f"sigma((Xk-uk)*qi): {q0*(X0-point[0]) + q1*(X1-point[1]) + q2*(X2-point[2])}")
q2_uni = MLE(q2).to_uni()
q1_uni = MLE(q1).to_uni()
q0_uni = MLE(q0).to_uni()
print(f"q2_uni: {q2_uni}")
print(f"q1_uni: {q1_uni}")
print(f"q0_uni: {q0_uni}")
q2: 4*X0*X1 + 3*X0 + 7*X1 + 4
r2: 13*X0*X1 + 9*X0 + 22*X1 + 13
q1: 13*X0 + 22
r1: 35*X0 + 57
q0: 35
r0: 92
mle - v: 4*X0*X1*X2 + X0*X1 + 3*X0*X2 + 7*X1*X2 + X1 + 4*X2 - 91
sigma((Xk-uk)*qi): 4*X0*X1*X2 + X0*X1 + 3*X0*X2 + 7*X1*X2 + X1 + 4*X2 - 91
q2_uni: 18*X^3 + 11*X^2 + 7*X + 4
q1_uni: 35*X + 22
q0_uni: 35
Verifier’s Equation Check#
The verifier needs to check if the equation holds using the Commitments of \({U}(mle)\), \({U}(q_0)\), \({U}(q_1)\), \({U}(q_2)\), and the plain point, v.
Equation Transformation#
Let’s transform the equation: \({U}(mle - v) = {U}(q_0 \cdot (X_0 - point[0]) + q_1 \cdot (X_1 - point[1]) + q_2 \cdot (X_2 - point[2]))\)
\({U}(mle) - {U}(v) = {U}(q_0X_0 - q_0 \cdot point[0] + q_1X_1 - q_1 \cdot point[1] + q_2X_2 - q_2 \cdot point[2])\)
\(\quad = {U}(q_0X_0) - {U}(q_0 \cdot point[0]) + {U}(q_1X_1) - {U}(q_1 \cdot point[1]) + {U}(q_2X_2) - {U}(q_2 \cdot point[2])\)
Challenge: Aligning the Dimension of U(MLE) without the Original MLE#
We face a significant challenge in this process: we need to find a method to increase the dimension of \({U}(q)\), but the verifier only has access to \({U}(q)\), not the original \( q\) itself. This limitation requires us to develop a approach to upscale the dimension while working solely with the committed values.
ZeroMorph’s U Mapping#
ZeroMorph’s U mapping defines all dimensions in F[X] 2^n. We need to extend any lower degree items from k-dim to the n-dim vector space.
Example: \({U}(q_0X_0)\)#
Let’s examine what’s happening with \({U}(q_0X_0)\):
It means a 0-dim \(q_0\) multiplies a variable, making it 1-dim
When \(X_0=0\), \({U}(q_0 \cdot 0) = 0\)
When \(X_0=1\), \({U}(q_0 \cdot 1) = {U}(q_0)\) This appears to be zero-padding before \(q_0\) on 1-dim.
Extending to Higher Dimensions#
To fulfill the space requirements, we need to extend the 1-dimensional representation into a 3-dimensional one.
Consider the following scenario:
The 1-dimensional representation is augmented with two additional variables that do not affect the outcome.
Regardless of the values chosen for X1 and X2, only X0 has an impact on the result.
To achieve this extension, we can:
Replicate the 1-dimensional representation to create a 2-dimensional structure.
Subsequently, expand the 2-dimensional structure into a 3-dimensional representation.
This approach allows us to maintain the integrity of the original information while extending it to the required higher-dimensional space.
# To explain the expansion of the k-dim mle to n-dim mle by using evals
# We can use a 1D example to explain
# the evals is [0, 35] which lying on the 1D line
mle_evals = [0, 35]
vertices = [
([0,0,0], mle_evals[0]), ([1,0,0], mle_evals[1]),
]
g = Graphics()
for x in [0,1]:
g += line3d([(0,0,0), (1,0,0)], color='black')
for (x,y,z), value in vertices:
g += text3d(f"({x})={value}", (x,y,z), fontsize=15)
note = "This line visualization represents a multilinear extension, with each vertex storing the corresponding function value."
text_position = (0.5, 0.5, -0.5) # x和y居中，z在立方体下方
g += text3d(note, text_position, fontsize=15)
show(g, aspect_ratio=(1, 1, 1), ticks=[[0,2,1], [0,2,1], [0,2,1]], frame=False)
# Then expand the 1D mle to 2D mle, copy the 1D evals to next dimension
vertices = [
([0,0,0], mle_evals[0]), ([1,0,0], mle_evals[1]),
([0,1,0], mle_evals[0]), ([1,1,0], mle_evals[1]),
]
g = Graphics()
for x in [0,1]:
for y in [0,1]:
g += line3d([(1-x,y,0), (x,y,0)], color='black')
for x in [0,1]:
for y in [0,1]:
g += line3d([(x,1-y,0), (x,y,0)], color='red', linestyle='dotted')
for (x,y,z), value in vertices:
g += text3d(f"({x},{y})={value}", (x,y,z), fontsize=15)
note = "The second line is the copy of the first line, now it's a 2D plane"
text_position = (0.5, 0.5, -0.5) # x和y居中，z在立方体下方
g += text3d(note, text_position, fontsize=15)
show(g, aspect_ratio=(1, 1, 1), ticks=[[0,2,1], [0,2,1], [0,2,1]], frame=False)
# Then expand the 2D plane to 3D cube by copying the 2D plane to next dimension
vertices = [
([0,0,0], mle_evals[0]), ([1,0,0], mle_evals[1]),
([0,1,0], mle_evals[0]), ([1,1,0], mle_evals[1]),
([0,0,1], mle_evals[0]), ([1,0,1], mle_evals[1]),
([0,1,1], mle_evals[0]), ([1,1,1], mle_evals[1]),
]
g = Graphics()
for x in [0,1]:
for y in [0,1]:
g += line3d([(x,y,0), (x,y,1)], color='red')
for x in [0,1]:
for z in [0,1]:
g += line3d([(x,0,z), (x,1,z)], color='black')
for y in [0,1]:
for z in [0,1]:
g += line3d([(0,y,z), (1,y,z)], color='black')
for (x,y,z), value in vertices:
g += text3d(f"({x},{y},{z})={value}", (x,y,z), fontsize=15)
note = "The top plane is the copy of the bottom plane, now it's a 3D cube"
text_position = (0.5, 0.5, -0.5) # x和y居中，z在立方体下方
g += text3d(note, text_position, fontsize=15)
show(g, aspect_ratio=(1, 1, 1), ticks=[[0,2,1], [0,2,1], [0,2,1]], frame=False)
Let’s examine \(q_0\). The verifier has the commitment of \(U(q_0)\), but how can they obtain \(U(q_0X_0)\) independently?
\(U(q_0)\) is a 0-dimensional number. Multiplying it by \(X_0\) is equivalent to padding \(U(q_0)\) with a leading zero.
At this point, the verifier has \([0, U(q_0)]\).
Now, let’s extend this to 3 dimensions: \([0, U(q_0), 0, U(q_0), 0, U(q_0), 0, U(q_0)]\) Notice the pattern? It’s constructed through padding and duplication. We’ll call this the period function \(\Phi(X)\).
This function transforms \(0 + U(q_0)X\) into \(0 + U(q_0)X + 0 + U(q_0)X^3 + 0 + U(q_0)X^5 + 0 + U(q_0)X^7\) We can rewrite this equation as: \((0 + U(q_0)X) (1 + X^2 + X^4 + X^6)\)
The \(U(q_0)X\) term causes a right shift for \(U(q_0)\), resulting in a leading zero padding. For a k-dimensional polynomial, this shift would be represented by \(X^{2^k}\).
We call this expression \((1 + X^2 + X^4 + X^6)\) the period function, denoted as \(\Phi(X)\).
def Phi(x, k, n):
result = 0
x = x^(2^(k))
for i in range(2**(n-k)):
result = result + x^(i)
return result
q0X0 = MLE(q0*X0)
q0X0_uni = q0X0.to_uni()
print(f"U(q0X0)_k: {q0X0_uni}")
q0X0_ext_3_uni = q0X0.extend(3).to_uni()
print(f"U(q0X0)_n: {q0X0_ext_3_uni}")
print(f"U(q0X0)_n/U(q0)_k: {q0X0_ext_3_uni/q0_uni}")
print(f"Phi(X, 1, 3): {Phi(X, 1, 3)}")
print(f"Shift(X) * Phi(X, 1, 3): {X * Phi(X, 1, 3)}")
q1X1 = MLE(q1*X1)
q1X1_uni = q1X1.to_uni()
print(f"U(q1X1)_k: {q1X1_uni}")
q1X1_ext_3_uni = q1X1.extend(3).to_uni()
print(f"U(q1X1)_n: {q1X1_ext_3_uni}")
print(f"U(q1X1)_n/U(q1)_k: {q1X1_ext_3_uni/q1_uni}")
print(f"Phi(X, 2, 3): {Phi(X, 2, 3)}")
print(f"Shift(X^2) * Phi(X, 2, 3): {X^2 * Phi(X, 2, 3)}")
U(q0X0)_k: 35*X
U(q0X0)_n: 35*X^7 + 35*X^5 + 35*X^3 + 35*X
U(q0X0)_n/U(q0)_k: X^7 + X^5 + X^3 + X
Phi(X, 1, 3): X^6 + X^4 + X^2 + 1
Shift(X) * Phi(X, 1, 3): X^7 + X^5 + X^3 + X
U(q1X1)_k: 35*X^3 + 22*X^2
U(q1X1)_n: 35*X^7 + 22*X^6 + 35*X^3 + 22*X^2
U(q1X1)_n/U(q1)_k: X^6 + X^2
Phi(X, 2, 3): X^4 + 1
Shift(X^2) * Phi(X, 2, 3): X^6 + X^2
The verifier can now construct the transformation by applying a shift of \(X^d\) and duplicating with \(Phi(X)\) on \(U(q)\).
This process mirrors the padding and duplication performed on the original Multi-Linear Extension (MLE). As a result, the verifier can recover the original extension by applying the shift with \(X^d\) and \(Phi(X)\) on \(U(q)\), which is equivalent to the original MLE.
With this understanding of the mapping from MLE to Univariate Polynomial and how the verifier can construct the dimension extension without knowing the original MLE, we can now proceed to apply the Kate-Zaverucha-Goldberg (KZG) commitment scheme to it.