ZK-Bootcamp - Homework 5 - BN128

    !python -m pip install py-ecc

    from py_ecc.bn128 import G1, add, multiply, curve_order

Problem 1: Rational numbers

Claim: “I know two rational numbers that add up to num/den”

Proof: ([A], [B], num, den)

Here, num is the numerator of the rational number and den is the denominator.

    class ECPoint:
        def __init__(self, x, y):
            self.x = x
            self.y = y
    
    def rational_add(A: ECPoint, B: ECPoint, num: int, den: int) -> bool:
        """
        Return True if the prover knows two numbers that add up to num/den.
        """
        # To prove a + b = num/den, the prover must know a and b such that:
        # a + b = num.den^-1
        # We prove this by checking
        # F(a + b) = F(a).F(b)
        # F(num.den^-1) = F(a).F(b)
        den_inv = pow(den, -1, curve_order)
        num_den_inv = num * den_inv
        F_num_den_inv = multiply(G1, num_den_inv)
        F_a_and_F_b = add((A.x, A.y), (B.x, B.y))
        return F_num_den_inv == F_a_and_F_b 
    
    def get_EC_point(a: int) -> ECPoint:
        """
        Convert an integer to an ECPoint on the BN-128 curve.
        """
        x, y = multiply(G1, a)
        return ECPoint(x, y)

    # Equation a + b = num / den
    # Solution 1: 5 + 10 = 45 / 3
    a = 5
    b = 10
    num = 45
    den = 3
    A = get_EC_point(a)
    B = get_EC_point(b)
    assert rational_add(A, B, num, den) == True
    
    # Solution 2: 2 + 3 = 5 / 1
    a = 2
    b = 3
    num = 5
    den = 1
    A = get_EC_point(a)
    B = get_EC_point(b)
    assert rational_add(A, B, num, den) == True
    
    # Invalid solution: 4 + 9 = 3 / 2
    a = 4
    b = 9
    num = 3
    den = 2
    A = get_EC_point(a)
    B = get_EC_point(b)
    assert rational_add(A, B, num, den) == False

Problem 2: Matrix Multiplication

There is no claim statement here, just execute the math.

Your code should implement matrix multiplication of an n x n matrix (M) of int and a n x 1 vector of points (s). It validates the claim that matrix Ms = o where o is a n x 1 matrix of uint256.

You will need to multiply o by the generator so that both sides have the same type.

Example

\begin{bmatrix}1 & 2 & 3\4 & 5 & 6\7 & 8 & 9\end{bmatrix}\begin{bmatrix}P\Q\R\end{bmatrix}=\begin{bmatrix}P+2Q+3R\4P+5Q+6R\7P + 8Q + 9R\end{bmatrix}\stackrel{?}{=}\begin{bmatrix}o_1G\o_2G\o_3G\end{bmatrix}

    def matmul(matrix, n, s, o):
        """
        matrix: matrix of size n x n
        n: size of the matrix
        s: list of n EC points (tuples: (x, y))
        o: list of n integers
        Returns True if Ms == o*G1 elementwise
        """
        for i in range(n): # looping through rows of the matrix
            expected_o = multiply(G1, o[i]) 
            found_o = multiply(G1, 0)  # Initialize found_o as the identity element
            for j in range(n): # looping through columns of the matrix
                matrix_element = matrix[i][j]
                point = s[j]
                scaled_point = multiply((point.x, point.y), matrix_element)
                found_o = add(found_o, scaled_point)
            if found_o != expected_o:
                return False
                
        return True

    matrix = [[1,2,3], [4,5,6], [7,8,9]]
    n = 3
    s = [get_EC_point(2), get_EC_point(3), get_EC_point(4)]
    o = [20, 47, 74] 
    
    assert matmul(matrix, n, s, o) == True
    
    o = [20, 47, 75]  # This should fail as its not a solution
    assert matmul(matrix, n, s, o) == False

Spoorthi Satheesha

ZK-Bootcamp - Homework 5 - BN128

Problem 1: Rational numbers

Problem 2: Matrix Multiplication