Square root scaling for polynomial commitments

sqrt_commit.py

#!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))