Skip to content

Instantly share code, notes, and snippets.

@AdamISZ
Created April 26, 2022 07:27
Show Gist options
  • Save AdamISZ/8be8d1358ecaac86b631dee30ffb2d4a to your computer and use it in GitHub Desktop.
Save AdamISZ/8be8d1358ecaac86b631dee30ffb2d4a to your computer and use it in GitHub Desktop.
Square root scaling for polynomial commitments
#!usr/bin/env python
""" Implementation example of https://eprint.iacr.org/2016/263.pdf
Bootle et al. Section 3, polynomial evaluation protocol which scales
in the square root of the degree.
*Not* zero knowledge form.
"""
import jmbitcoin as btc
import struct
import hashlib
import random
# This first chunk of code is just to find NUMS base points
# needed to form vector Pedersen commitments
Gs = []
def getbase(i):
"""Return a base for a vector commitment construction
at index i by hashing G for NUMS.
Basically just copied this from the old PoDLE code.
"""
nums_point = None
seed = btc.getG(True) + struct.pack(b'B', i)
for counter in range(256):
seed_c = seed + struct.pack(b'B', counter)
hashed_seed = hashlib.sha256(seed_c).digest()
#Every x-coord on the curve has two y-values, encoded
#in compressed form with 02/03 parity byte. We just
#choose the former.
claimed_point = b"\x02" + hashed_seed
try:
nums_point = btc.CPubKey(claimed_point)
# CPubKey does not throw ValueError or otherwise
# on invalid initialization data; it must be inspected:
assert nums_point.is_fullyvalid()
return nums_point
except:
continue
assert False, "It seems inconceivable, doesn't it?" # pragma: no cover
for i in range(256):
Gs.append(getbase(i))
def vec_comm(vec, rand=False):
""" Takes a list `vec` of scalar values as integers,
and forms a commitment v_0 G_0 + v_1 G_1 + ...
TODO: commitment should add randomness but not done here yet,
note thought that we are not attempting ZK.
TODO: ensure amounts in range
"""
return btc.add_pubkeys([btc.multiply(vec[i].to_bytes(32, byteorder="big"),
Gs[i]) for i in range(len(vec))])
if __name__ == "__main__":
degree = int(input("For our polynomial, choose an integer degree (d) which is one less than a number with two similar size factors: "))
m = int(input("Now choose the first factor of d+1: "))
if m >= degree or (degree + 1)% m:
print("Invalid factor.")
exit(0)
n = int((degree + 1)/ m)
# note d = mn - 1, -1 for the x^0 term
# First steps are for the prover, he needs to construct a
# set of m commitments C_0, C_1, ..., C_(m-1) to the rows
# of the coefficient matrix as per Bootle 16
# prover knows this set of coefficients:
coeff_vector = []
randcoeff = input("Do you want coefficients generated randomly(type 'r') or input them manually('m')?: ") == "r"
for i in range(degree+1):
if randcoeff:
coeff_vector.append(random.randint(1, 20))
else:
coeff_vector.append(int(input("Enter integer: ")))
poly_string = "We (the prover) now have a full polynomial: "
for i in range(degree+1):
poly_string += str(coeff_vector[i]) + "x^" + str(i) + " + "
print(poly_string[:-3])
input("Any key to continue")
# they are arranged into a matrix based on \Sigma(i=0,m-1)\Sigma(j=0,n-1)t_(i,j)x^(i*n+j)
# we do it row by row:
row_comms = []
for i in range(m):
# think of each row as a chunk/slice of the whole list, of length n; and there are m of them.
row_comms.append(vec_comm([coeff_vector[x] for x in range(i*n, i*n + n)]))
print("Prover publishes the following {} row commitments:".format(m))
for i in range(m):
print("{}".format(row_comms[i]))
print("Note that he would only publish this once for any number of protocol runs.\n")
# verifier challenges by asking for output for a given input:
input_val = int(input("Enter an integer x value as input to the polynomial:"))
# prover calculates the actual polynomial value at the input given by the verifier,
# and claims it:
final_val = sum([coeff_vector[i]*(input_val**i) for i in range(len(coeff_vector))])
print("Prover claims output for {} is {}".format(input_val, final_val))
# Now for the compact proof. the verifier can already compute the commitment
# \Sigma_(i=0,m-1) x^ni * C_i, which should be the same as C(tbar) (using the notation of the paper),
# and demand a valid opening.
commit_given_x = btc.add_pubkeys([btc.multiply((input_val**(n*i)).to_bytes(
32, byteorder="big"), row_comms[i]) for i in range(m)])
print("Verifier can calculate the commitment (sum: x^ni * C_i):")
print(commit_given_x)
# prover constructs the valid opening; this is the only part that must
# be sent over the wire, after the initial setup of input value and claimed output value.
openings = []
for i in range(n):
val = 0
for j in range(m):
val += coeff_vector[j*n + i]*(input_val**(j*n))
openings.append(val)
print("Prover gives the opening for that commitment: {}".format(openings))
print("This is the only data that the prover needs to send to the verifier; {} scalar values.\n".format(n))
# if the commitment to the vector `openings` is the same as the commitment above,
# it validates. Notice this is very simple because we are not using randomness.
if commit_given_x == vec_comm(openings):
print("The commitment was opened correctly")
else:
print("Commitments didn't match.")
# Final step: for the verifier to be convinced that the output value is correct, he
# multiplies this new row vector by the column vector of powers of x.
check_final_value = sum([(input_val**x)*openings[x] for x in range(n)])
if check_final_value == final_val:
print("Value of output was correct.")
else:
print("Value of output was wrong, expected {}, got {}".format(final_val, check_final_value))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment