{ "cells": [ { "cell_type": "code", "execution_count": null, "id": "78151c17", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 1, "id": "b0286ed1", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle -a_{0} {\\left(u_{0} - 1\\right)} {\\left(u_{1} - 1\\right)} {\\left(u_{2} - 1\\right)} + a_{4} u_{0} {\\left(u_{1} - 1\\right)} {\\left(u_{2} - 1\\right)} + a_{2} {\\left(u_{0} - 1\\right)} u_{1} {\\left(u_{2} - 1\\right)} - a_{6} u_{0} u_{1} {\\left(u_{2} - 1\\right)} + a_{1} {\\left(u_{0} - 1\\right)} {\\left(u_{1} - 1\\right)} u_{2} - a_{5} u_{0} {\\left(u_{1} - 1\\right)} u_{2} - a_{3} {\\left(u_{0} - 1\\right)} u_{1} u_{2} + a_{7} u_{0} u_{1} u_{2}\\)" ], "text/latex": [ "$\\displaystyle -a_{0} {\\left(u_{0} - 1\\right)} {\\left(u_{1} - 1\\right)} {\\left(u_{2} - 1\\right)} + a_{4} u_{0} {\\left(u_{1} - 1\\right)} {\\left(u_{2} - 1\\right)} + a_{2} {\\left(u_{0} - 1\\right)} u_{1} {\\left(u_{2} - 1\\right)} - a_{6} u_{0} u_{1} {\\left(u_{2} - 1\\right)} + a_{1} {\\left(u_{0} - 1\\right)} {\\left(u_{1} - 1\\right)} u_{2} - a_{5} u_{0} {\\left(u_{1} - 1\\right)} u_{2} - a_{3} {\\left(u_{0} - 1\\right)} u_{1} u_{2} + a_{7} u_{0} u_{1} u_{2}$" ], "text/plain": [ "-a0*(u0 - 1)*(u1 - 1)*(u2 - 1) + a4*u0*(u1 - 1)*(u2 - 1) + a2*(u0 - 1)*u1*(u2 - 1) - a6*u0*u1*(u2 - 1) + a1*(u0 - 1)*(u1 - 1)*u2 - a5*u0*(u1 - 1)*u2 - a3*(u0 - 1)*u1*u2 + a7*u0*u1*u2" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left[-{\\left(u_{0} - 1\\right)} {\\left(u_{1} - 1\\right)} {\\left(u_{2} - 1\\right)}, u_{0} {\\left(u_{1} - 1\\right)} {\\left(u_{2} - 1\\right)}, {\\left(u_{0} - 1\\right)} u_{1} {\\left(u_{2} - 1\\right)}, -u_{0} u_{1} {\\left(u_{2} - 1\\right)}, {\\left(u_{0} - 1\\right)} {\\left(u_{1} - 1\\right)} u_{2}, -u_{0} {\\left(u_{1} - 1\\right)} u_{2}, -{\\left(u_{0} - 1\\right)} u_{1} u_{2}, u_{0} u_{1} u_{2}\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[-{\\left(u_{0} - 1\\right)} {\\left(u_{1} - 1\\right)} {\\left(u_{2} - 1\\right)}, u_{0} {\\left(u_{1} - 1\\right)} {\\left(u_{2} - 1\\right)}, {\\left(u_{0} - 1\\right)} u_{1} {\\left(u_{2} - 1\\right)}, -u_{0} u_{1} {\\left(u_{2} - 1\\right)}, {\\left(u_{0} - 1\\right)} {\\left(u_{1} - 1\\right)} u_{2}, -u_{0} {\\left(u_{1} - 1\\right)} u_{2}, -{\\left(u_{0} - 1\\right)} u_{1} u_{2}, u_{0} u_{1} u_{2}\\right]$" ], "text/plain": [ "[-(u0 - 1)*(u1 - 1)*(u2 - 1),\n", " u0*(u1 - 1)*(u2 - 1),\n", " (u0 - 1)*u1*(u2 - 1),\n", " -u0*u1*(u2 - 1),\n", " (u0 - 1)*(u1 - 1)*u2,\n", " -u0*(u1 - 1)*u2,\n", " -(u0 - 1)*u1*u2,\n", " u0*u1*u2]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left[14 X^{7} + 11 X^{6} + X^{5} + 5 X^{4} + 3 X^{3} + 13 X^{2} + 10 X + 12, X^{7} + 4 X^{6} + 4 X^{5} + 5 X^{4} + 10 X^{3} + 4 X^{2} + 13 X + 10, 9 X^{7} + 5 X^{6} + 7 X^{5} + 6 X^{3} + 7 X^{2} + 4 X + 13, X^{7} + 11 X^{6} + 10 X^{4} + 10 X^{3} + 6 X^{2} + 10 X + 3, 5 X^{7} + 2 X^{6} + 3 X^{5} + 4 X^{4} + 10 X^{3} + 5 X + 5, 3 X^{7} + X^{6} + 15 X^{5} + 3 X^{4} + 7 X^{2} + 4 X + 1, 14 X^{7} + 3 X^{6} + X^{5} + 2 X^{4} + 11 X^{3} + 5 X^{2} + 4 X + 11, 4 X^{7} + 14 X^{6} + 3 X^{5} + 5 X^{4} + X^{3} + 9 X^{2} + X + 14\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[14 X^{7} + 11 X^{6} + X^{5} + 5 X^{4} + 3 X^{3} + 13 X^{2} + 10 X + 12, X^{7} + 4 X^{6} + 4 X^{5} + 5 X^{4} + 10 X^{3} + 4 X^{2} + 13 X + 10, 9 X^{7} + 5 X^{6} + 7 X^{5} + 6 X^{3} + 7 X^{2} + 4 X + 13, X^{7} + 11 X^{6} + 10 X^{4} + 10 X^{3} + 6 X^{2} + 10 X + 3, 5 X^{7} + 2 X^{6} + 3 X^{5} + 4 X^{4} + 10 X^{3} + 5 X + 5, 3 X^{7} + X^{6} + 15 X^{5} + 3 X^{4} + 7 X^{2} + 4 X + 1, 14 X^{7} + 3 X^{6} + X^{5} + 2 X^{4} + 11 X^{3} + 5 X^{2} + 4 X + 11, 4 X^{7} + 14 X^{6} + 3 X^{5} + 5 X^{4} + X^{3} + 9 X^{2} + X + 14\\right]$" ], "text/plain": [ "[14*X^7 + 11*X^6 + X^5 + 5*X^4 + 3*X^3 + 13*X^2 + 10*X + 12,\n", " X^7 + 4*X^6 + 4*X^5 + 5*X^4 + 10*X^3 + 4*X^2 + 13*X + 10,\n", " 9*X^7 + 5*X^6 + 7*X^5 + 6*X^3 + 7*X^2 + 4*X + 13,\n", " X^7 + 11*X^6 + 10*X^4 + 10*X^3 + 6*X^2 + 10*X + 3,\n", " 5*X^7 + 2*X^6 + 3*X^5 + 4*X^4 + 10*X^3 + 5*X + 5,\n", " 3*X^7 + X^6 + 15*X^5 + 3*X^4 + 7*X^2 + 4*X + 1,\n", " 14*X^7 + 3*X^6 + X^5 + 2*X^4 + 11*X^3 + 5*X^2 + 4*X + 11,\n", " 4*X^7 + 14*X^6 + 3*X^5 + 5*X^4 + X^3 + 9*X^2 + X + 14]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left[1, 2, 3, 4, 5, 6, 7, 8\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[1, 2, 3, 4, 5, 6, 7, 8\\right]$" ], "text/plain": [ "[1, 2, 3, 4, 5, 6, 7, 8]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle 16 X^{7} + 6 X^{6} + 13 X^{5} + 11 X^{4} + 12 X^{3} + 11 X^{2} + 3 X + 14\\)" ], "text/latex": [ "$\\displaystyle 16 X^{7} + 6 X^{6} + 13 X^{5} + 11 X^{4} + 12 X^{3} + 11 X^{2} + 3 X + 14$" ], "text/plain": [ "16*X^7 + 6*X^6 + 13*X^5 + 11*X^4 + 12*X^3 + 11*X^2 + 3*X + 14" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left[\\mathrm{True}, \\mathrm{True}, \\mathrm{True}, \\mathrm{True}, \\mathrm{True}, \\mathrm{True}, \\mathrm{True}, \\mathrm{True}\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[\\mathrm{True}, \\mathrm{True}, \\mathrm{True}, \\mathrm{True}, \\mathrm{True}, \\mathrm{True}, \\mathrm{True}, \\mathrm{True}\\right]$" ], "text/plain": [ "[True, True, True, True, True, True, True, True]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle X^{7} + 2 X^{6} + 11 X^{5} + 4 X^{4} + 16 X^{3} + 7 X^{2} + 8 X + 13\\)" ], "text/latex": [ "$\\displaystyle X^{7} + 2 X^{6} + 11 X^{5} + 4 X^{4} + 16 X^{3} + 7 X^{2} + 8 X + 13$" ], "text/plain": [ "X^7 + 2*X^6 + 11*X^5 + 4*X^4 + 16*X^3 + 7*X^2 + 8*X + 13" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle X^{6} + 15 X^{5} + 2 X^{4} + 13 X^{3} + 15 X^{2} + 15 X + 16\\)" ], "text/latex": [ "$\\displaystyle X^{6} + 15 X^{5} + 2 X^{4} + 13 X^{3} + 15 X^{2} + 15 X + 16$" ], "text/plain": [ "X^6 + 15*X^5 + 2*X^4 + 13*X^3 + 15*X^2 + 15*X + 16" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle X^{4} + 5 X^{3} + 4 X^{2} + 12 X + 1\\)" ], "text/latex": [ "$\\displaystyle X^{4} + 5 X^{3} + 4 X^{2} + 12 X + 1$" ], "text/plain": [ "X^4 + 5*X^3 + 4*X^2 + 12*X + 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Define variables\n", "n = 3\n", "N = 2^n\n", "X = var(['X{}'.format(i) for i in range(n)]) # Define the variables X_0, X-1,.....\n", "u = var(['u{}'.format(i) for i in range(n)]) # Define the variables u_0, u-1,.....\n", "\n", "# Function to get binary representation as a list of bits\n", "def bits(i,n):\n", " return list(map(int, format(i,'0{}b'.format(n))))\n", "\n", "def bits_reverse(i, n):\n", " bits_list = bits(i, n)\n", " return list(reversed(bits_list))\n", "\n", "# Define the eq_tilde function\n", "def eq_tilde(bits_i, u_vector):\n", " result=1\n", " for bit,u in zip(bits_i,u_vector):\n", " result *= (1-bit)*(1-u) + bit*u\n", " return result\n", "\n", "# Coefficients of the polynomial\n", "a = [var('a{}'.format(i)) for i in range(N)] # Coefficients a_0, a_1, ...., a_(N-1)\n", "\n", "# MLE polynomial\n", "f_tilde = sum(a[i]*eq_tilde(bits(i,n), u) for i in range(N))\n", "show(f_tilde)\n", "\n", "# Generate all combinations of (1-u[i]) and u[i] based on binary representation\n", "def generate_c_vector(n, u):\n", " c_vector = []\n", " for i in range(2^n): # Loop over all binary numbers from 0 to 2^n - 1\n", " binary = list(map(int, format(i, f'0{n}b'))) # Binary representation of i\n", " binary_reverse = list(reversed(binary)) # Reverse the binary representation\n", " product = 1\n", " for j, bit in enumerate(binary_reverse):\n", " if bit == 0:\n", " product *= (1 - u[j]) # Use (1 - u[j]) for 0\n", " else:\n", " product *= u[j] # Use u[j] for 1\n", " c_vector.append(product)\n", " return c_vector\n", "\n", "# Compute the c vector\n", "c = generate_c_vector(n, u)\n", "\n", "# Display the c vector\n", "show(c)\n", "\n", "# SageMath Implementation for Polynomial Encoding using Lagrange Basis\n", "\n", "# Define the finite field and subgroup H\n", "p = 17 # Example prime (p must be chosen appropriately)\n", "F = GF(p) # Finite field F_p\n", "omega = F(3) # Example primitive 8th root of unity in F_p\n", "H = [omega^i for i in range(8)] # Multiplicative subgroup H of size 8\n", "\n", "# Define Lagrange Basis Polynomials\n", "def lagrange_basis(H, X):\n", " basis = []\n", " for i in range(len(H)):\n", " Li = 1\n", " for j in range(len(H)):\n", " if i != j:\n", " Li *= (X - H[j]) / (H[i] - H[j]) # Lagrange basis polynomial\n", " basis.append(Li)\n", " return basis\n", "\n", "# Symbolic variable for the polynomial\n", "X = polygen(F, 'X')\n", "\n", "# Compute the Lagrange basis polynomials\n", "L = lagrange_basis(H, X)\n", "show(L)\n", "\n", "# Vector c as computed earlier\n", "c = [F(c_val) for c_val in [1, 2, 3, 4, 5, 6, 7, 8]] # Example values for c vector\n", "show(c)\n", "# Compute the polynomial encoding c(X)\n", "c_X = sum(c[i] * L[i] for i in range(len(c)))\n", "\n", "# Compute the polynomial encoding c(X) step by step\n", "# c_X = 0 # Start with an empty polynomial\n", "# print(\"Building c(X) step by step:\")\n", "# for i in range(len(c)):\n", "# show(c[i])\n", "# show(L[i])\n", "# term = c[i] * L[i] # Compute the current term\n", "# show(term)\n", "# c_X += term # Add the current term to the polynomial\n", "# show(term)\n", "# '\\n'\n", "# # print(f\"Step {i+1}: Adding term {term}\")\n", "# # print(f\"Partial sum: {c_X}\\n\")\n", "\n", "# # Final polynomial\n", "# print(\"Final polynomial c(X):\")\n", "# show(c_X)\n", "\n", "# Display the resulting polynomial c(X)\n", "show(c_X)\n", "\n", "# Verification: Check that c(omega^i) = c_i\n", "verification = [c_X(H[i]) == c[i] for i in range(len(H))]\n", "show(verification)\n", "\n", "\n", "# Define subsets H0, H1, H2 based on the Group Tower relationship\n", "H0 = [H[0]] # {1}\n", "H1 = [H[0], H[4]] # {1, ω^4}\n", "H2 = [H[0], H[2], H[4], H[6]] # {1, ω^2, ω^4, ω^6}\n", "H3 = H # Full set {1, ω, ω^2, ..., ω^7}\n", "\n", "# Define the vanishing polynomials v_H(X) and v_Hi(X)\n", "X = polygen(F, 'X') # Define X as a polynomial variable\n", "\n", "def vanishing_polynomial(domain):\n", " \"\"\"Compute the vanishing polynomial for a given domain.\"\"\"\n", " v = 1\n", " for alpha in domain:\n", " v *= (X - alpha)\n", " return v\n", "\n", "# Compute vanishing polynomials\n", "v_H = vanishing_polynomial(H3) # Full vanishing polynomial for H\n", "v_H0 = vanishing_polynomial(H0)\n", "v_H1 = vanishing_polynomial(H1)\n", "v_H2 = vanishing_polynomial(H2)\n", "\n", "# Compute the selector polynomials s_0(X), s_1(X), s_2(X)\n", "s0 = v_H/v_H0\n", "s1 = v_H/v_H1\n", "s2 = v_H/v_H2\n", "\n", "# Display the selector polynomials\n", "show(s0)\n", "show(s1)\n", "show(s2)\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "6f1d1d23", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "the root unity of F_p: 3\n", "the root unity of subgroup H: 9\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\left[1, 9, 13, 15, 16, 8, 4, 2\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[1, 9, 13, 15, 16, 8, 4, 2\\right]$" ], "text/plain": [ "[1, 9, 13, 15, 16, 8, 4, 2]" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "P_X: 15*X^14 + 4*X^13 + 15*X^12 + 11*X^11 + X^10 + 15*X^9 + 11*X^8 + 3*X^7 + 14*X^6 + 14*X^5 + 3*X^4 + 6*X^3 + 5*X^2 + 7*X + 13\n", "a(X): 10*X^7 + 7*X^6 + 11*X^5 + 15*X^4 + 9*X^3 + 10*X^2 + 15*X + 4\n", "c(X): 10*X^7 + 7*X^6 + 6*X^5 + 15*X^4 + 6*X^3 + 15*X^2 + 14*X + 16\n", "P(X): 15*X^14 + 4*X^13 + 15*X^12 + 11*X^11 + X^10 + 15*X^9 + 11*X^8 + 3*X^7 + 14*X^6 + 14*X^5 + 3*X^4 + 6*X^3 + 5*X^2 + 7*X + 13\n", "q(X): 15*X^6 + 4*X^5 + 15*X^4 + 11*X^3 + X^2 + 15*X + 11\n", "g(X): 3*X^6 + 12*X^5 + X^4 + X^3 + 6*X + 5\n", "v: 5\n", "Verification at ζ:\n", "LHS (a(ζ) * c(ζ)): 15\n", "RHS (q(ζ) * v_H(ζ) + ζ * g(ζ) + v/N): 15\n" ] } ], "source": [ "# Define the finite field and its elements\n", "p = 17 # Prime modulus\n", "F = GF(p) # Finite field F_p\n", "generator = F.multiplicative_generator() # the root unity of F_p\n", "print(\"the root unity of F_p: \", generator)\n", "\n", "# find the order of the generator of F_p\n", "def find_order(generator, field):\n", " order = 1\n", " power = generator\n", " while power != 1:\n", " power *= generator\n", " order += 1\n", " return order\n", "\n", "# return the root of unity in subgroup H, where |H| = N\n", "def root_of_H(generator, generator_order, N):\n", " return generator**(generator_order / N)\n", "\n", "generator_order = find_order(generator, F)\n", "omega = root_of_H(generator, generator_order, 8)\n", "print(\"the root unity of subgroup H: \", omega)\n", "H = [omega^i for i in range(8)] # Subgroup H of size 8 (2^3)\n", "show(H)\n", "\n", "# Define variables\n", "X = polygen(F, 'X') # Polynomial variable\n", "N = len(H) # Size of the group H\n", "\n", "# Define vanishing polynomial of H\n", "def vanishing_polynomial(H):\n", " v_H = F(1)\n", " for h in H:\n", " v_H *= (X - h)\n", " return v_H\n", "\n", "v_H = vanishing_polynomial(H)\n", "\n", "# Define polynomials a(X) and c(X)\n", "a_coeffs = [F.random_element() for _ in range(N)] # Random coefficients for a(X)\n", "c_coeffs = [F.random_element() for _ in range(N)] # Random coefficients for c(X)\n", "\n", "a_X = sum(a_coeffs[i] * X^i for i in range(N)) # a(X)\n", "c_X = sum(c_coeffs[i] * X^i for i in range(N)) # c(X)\n", "\n", "# Compute P(X) = a(X) * c(X)\n", "P_X = a_X * c_X\n", "\n", "print(\"P_X: \", P_X)\n", "\n", "# Compute the decomposition of P(X)\n", "q_X = P_X // v_H # Quotient\n", "r_X = P_X % v_H # Remainder\n", "v = sum(P_X(h) for h in H) # v = sum of P(ω) over H\n", "g_X = (r_X - v / N) // X # g(X) \n", "\n", "# Verify the decomposition\n", "decomposed_P_X = q_X * v_H + X * g_X + (v / N)\n", "assert P_X == decomposed_P_X # Ensure the decomposition holds\n", "\n", "# Verification at a challenge ζ\n", "zeta = F.random_element() # Random challenge ζ\n", "lhs = a_X(zeta) * c_X(zeta) # a(ζ) * c(ζ)\n", "rhs = q_X(zeta) * v_H(zeta) + zeta * g_X(zeta) + (v / N) # q(ζ) * v_H(ζ) + ζ * g(ζ) + v/N\n", "\n", "# Output results\n", "print(\"a(X):\", a_X)\n", "print(\"c(X):\", c_X)\n", "print(\"P(X):\", P_X)\n", "print(\"q(X):\", q_X)\n", "print(\"g(X):\", g_X)\n", "print(\"v:\", v)\n", "print(\"Verification at ζ:\")\n", "print(\"LHS (a(ζ) * c(ζ)):\", lhs)\n", "print(\"RHS (q(ζ) * v_H(ζ) + ζ * g(ζ) + v/N):\", rhs)\n", "assert lhs == rhs, \"Verification failed!\"" ] }, { "cell_type": "code", "execution_count": 3, "id": "ebedea8f", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Constraint 1:\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 13 X^{14} + 10 X^{13} + 14 X^{12} + 15 X^{11} + 2 X^{10} + 2 X^{9} + 3 X^{8} + 4 X^{6} + 7 X^{5} + 3 X^{4} + 2 X^{3} + 15 X^{2} + 15 X + 14\\)" ], "text/latex": [ "$\\displaystyle 13 X^{14} + 10 X^{13} + 14 X^{12} + 15 X^{11} + 2 X^{10} + 2 X^{9} + 3 X^{8} + 4 X^{6} + 7 X^{5} + 3 X^{4} + 2 X^{3} + 15 X^{2} + 15 X + 14$" ], "text/plain": [ "13*X^14 + 10*X^13 + 14*X^12 + 15*X^11 + 2*X^10 + 2*X^9 + 3*X^8 + 4*X^6 + 7*X^5 + 3*X^4 + 2*X^3 + 15*X^2 + 15*X + 14" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Constraint 2:\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 7 X^{15} + 6 X^{14} + 11 X^{13} + 9 X^{12} + 7 X^{11} + 6 X^{10} + 6 X^{9} + 6 X^{8} + 10 X^{7} + 11 X^{6} + 6 X^{5} + 8 X^{4} + 10 X^{3} + 11 X^{2} + 11 X + 11\\)" ], "text/latex": [ "$\\displaystyle 7 X^{15} + 6 X^{14} + 11 X^{13} + 9 X^{12} + 7 X^{11} + 6 X^{10} + 6 X^{9} + 6 X^{8} + 10 X^{7} + 11 X^{6} + 6 X^{5} + 8 X^{4} + 10 X^{3} + 11 X^{2} + 11 X + 11$" ], "text/plain": [ "7*X^15 + 6*X^14 + 11*X^13 + 9*X^12 + 7*X^11 + 6*X^10 + 6*X^9 + 6*X^8 + 10*X^7 + 11*X^6 + 6*X^5 + 8*X^4 + 10*X^3 + 11*X^2 + 11*X + 11" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Constraint 3:\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 5 X^{14} + 14 X^{13} + 11 X^{12} + 16 X^{11} + 12 X^{10} + 16 X^{9} + 2 X^{8} + 12 X^{6} + 3 X^{5} + 6 X^{4} + X^{3} + 5 X^{2} + X + 15\\)" ], "text/latex": [ "$\\displaystyle 5 X^{14} + 14 X^{13} + 11 X^{12} + 16 X^{11} + 12 X^{10} + 16 X^{9} + 2 X^{8} + 12 X^{6} + 3 X^{5} + 6 X^{4} + X^{3} + 5 X^{2} + X + 15$" ], "text/plain": [ "5*X^14 + 14*X^13 + 11*X^12 + 16*X^11 + 12*X^10 + 16*X^9 + 2*X^8 + 12*X^6 + 3*X^5 + 6*X^4 + X^3 + 5*X^2 + X + 15" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Constraint 1 is satisfied!\n", "Constraint 2 is satisfied!\n", "Constraint 3 is satisfied!\n", "All constraints are satisfied!\n" ] } ], "source": [ "# Define the finite field and its elements\n", "p = 17 # Prime modulus\n", "F = GF(p) # Finite field F_p\n", "omega = F(9) # Primitive 8th root of unity in F_p\n", "H = [omega^i for i in range(8)] # Subgroup H of size 8 (2^3)\n", "\n", "# Define the vanishing polynomial for H\n", "def vanishing_polynomial(H):\n", " v_H = F(1)\n", " for h in H:\n", " v_H *= (X - h)\n", " return v_H\n", "\n", "# Lagrange basis polynomials\n", "def lagrange_basis(H, X):\n", " basis = []\n", " for i in range(len(H)):\n", " Li = F(1)\n", " for j in range(len(H)):\n", " if i != j:\n", " Li *= (X - H[j]) / (H[i] - H[j])\n", " basis.append(Li)\n", " return basis\n", "\n", "# Define variables\n", "X = polygen(F, 'X') # Polynomial variable\n", "N = len(H)\n", "\n", "# Random coefficients for a(X) and c(X)\n", "a_coeffs = [F.random_element() for _ in range(N)]\n", "c_coeffs = [F.random_element() for _ in range(N)]\n", "\n", "\n", "# Construct a(X) and c(X)\n", "L = lagrange_basis(H, X)\n", "a_X = sum(a_coeffs[i] * L[i] for i in range(N))\n", "c_X = sum(c_coeffs[i] * L[i] for i in range(N))\n", "\n", "# Compute the auxiliary vector z_i\n", "z = [a_coeffs[0] * c_coeffs[0]] # z_0\n", "for i in range(1, N):\n", " z.append(z[i-1] + a_coeffs[i] * c_coeffs[i])\n", "\n", "# Compute z(X) using Lagrange basis polynomials\n", "z_X = sum(z[i] * L[i] for i in range(N))\n", "\n", "# Compute the final sum v\n", "v = z[-1]\n", "\n", "# Polynomial constraints\n", "# Constraint 1: L0(X) * (z(X) - a(X) * c_0)\n", "constraint1 = L[0] * (z_X - a_X * c_coeffs[0])\n", "\n", "# Constraint 2: (X - 1) * (z(X) - z(ω^{-1} * X) - a(X) * c(X))\n", "omega_inv = omega^(-1)\n", "z_shifted = z_X.subs(X=omega_inv * X)\n", "constraint2 = (X - 1) * (z_X - z_shifted - a_X * c_X)\n", "\n", "# Constraint 3: LN-1(X) * (z(X) - v)\n", "constraint3 = L[-1] * (z_X - v)\n", "\n", "# Display the constraints\n", "print(\"Constraint 1:\")\n", "show(constraint1)\n", "\n", "print(\"Constraint 2:\")\n", "show(constraint2)\n", "\n", "print(\"Constraint 3:\")\n", "show(constraint3)\n", "\n", "# Evaluate constraints point-by-point in H to verify correctness\n", "verification_points = H # Points in the subgroup H\n", "\n", "def verify_constraint_at_points(constraint, points):\n", " \"\"\"Check if a constraint is satisfied at all points in the given domain.\"\"\"\n", " return all(constraint.subs(X=point) == 0 for point in points)\n", "\n", "# Check if constraints are satisfied at all points in H\n", "constraint1_valid = verify_constraint_at_points(constraint1, verification_points)\n", "constraint2_valid = verify_constraint_at_points(constraint2, verification_points)\n", "constraint3_valid = verify_constraint_at_points(constraint3, verification_points)\n", "\n", "# Display results\n", "if constraint1_valid:\n", " print(\"Constraint 1 is satisfied!\")\n", "else:\n", " print(\"Constraint 1 failed!\")\n", "\n", "if constraint2_valid:\n", " print(\"Constraint 2 is satisfied!\")\n", "else:\n", " print(\"Constraint 2 failed!\")\n", "\n", "if constraint3_valid:\n", " print(\"Constraint 3 is satisfied!\")\n", "else:\n", " print(\"Constraint 3 failed!\")\n", "\n", "# Assert that all constraints are satisfied\n", "assert constraint1_valid, \"Constraint 1 failed!\"\n", "assert constraint2_valid, \"Constraint 2 failed!\"\n", "assert constraint3_valid, \"Constraint 3 failed!\"\n", "\n", "print(\"All constraints are satisfied!\")" ] }, { "cell_type": "code", "execution_count": 4, "id": "35dfa57b", "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "u: [16, 14, 3]\n", "c_coeffs: [1, 8, 12, 11, 7, 5, 16, 9]\n", "Polynomial h(X):\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 8 X^{15} + 10 X^{14} + 13 X^{13} + 12 X^{12} + 10 X^{11} + 11 X^{10} + 11 X^{9} + 3 X^{8} + 9 X^{7} + 7 X^{6} + 4 X^{5} + 5 X^{4} + 7 X^{3} + 6 X^{2} + 6 X + 14\\)" ], "text/latex": [ "$\\displaystyle 8 X^{15} + 10 X^{14} + 13 X^{13} + 12 X^{12} + 10 X^{11} + 11 X^{10} + 11 X^{9} + 3 X^{8} + 9 X^{7} + 7 X^{6} + 4 X^{5} + 5 X^{4} + 7 X^{3} + 6 X^{2} + 6 X + 14$" ], "text/plain": [ "8*X^15 + 10*X^14 + 13*X^13 + 12*X^12 + 10*X^11 + 11*X^10 + 11*X^9 + 3*X^8 + 9*X^7 + 7*X^6 + 4*X^5 + 5*X^4 + 7*X^3 + 6*X^2 + 6*X + 14" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Quotient polynomial t(X):\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 8 X^{7} + 10 X^{6} + 13 X^{5} + 12 X^{4} + 10 X^{3} + 11 X^{2} + 11 X + 3\\)" ], "text/latex": [ "$\\displaystyle 8 X^{7} + 10 X^{6} + 13 X^{5} + 12 X^{4} + 10 X^{3} + 11 X^{2} + 11 X + 3$" ], "text/plain": [ "8*X^7 + 10*X^6 + 13*X^5 + 12*X^4 + 10*X^3 + 11*X^2 + 11*X + 3" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Remainder:\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 0\\)" ], "text/latex": [ "$\\displaystyle 0$" ], "text/plain": [ "0" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Verification successful: h(X) is divisible by v_H(X).\n" ] } ], "source": [ "# Define the finite field and its elements\n", "p = 17 # Prime modulus\n", "F = GF(p) # Finite field F_p\n", "omega = F(9) # Primitive 8th root of unity in F_p\n", "H = [omega^i for i in range(8)] # Subgroup H of size 8 (2^3)\n", "N = len(H)\n", "n = log(len(H), 2)\n", "\n", "\n", "# Define the vanishing polynomial for H\n", "def vanishing_polynomial(H):\n", " v_H = F(1)\n", " for h in H:\n", " v_H *= (X - h)\n", " return v_H\n", "\n", "# Polynomial variable\n", "X = polygen(F, 'X')\n", "v_H = vanishing_polynomial(H)\n", "\n", "# Define the lagrange basis polynomials\n", "def lagrange_basis(H, X):\n", " basis = []\n", " for i in range(len(H)):\n", " Li = F(1)\n", " for j in range(len(H)):\n", " if i != j:\n", " Li *= (X - H[j]) / (H[i] - H[j])\n", " basis.append(Li)\n", " return basis\n", "\n", "L = lagrange_basis(H, X) # Lagrange basis polynomials\n", "\n", "u = [F.random_element() for _ in range(n)]\n", "print(\"u: \", u)\n", "\n", "# Random coefficients for a(X) and c(X)\n", "a_coeffs = [F.random_element() for _ in range(len(H))]\n", "c_coeffs = generate_c_vector(n, u)\n", "# c_coeffs = [F.random_element() for _ in range(len(H))]\n", "print(\"c_coeffs: \", c_coeffs)\n", "\n", "# Construct a(X) and c(X)\n", "a_X = sum(a_coeffs[i] * L[i] for i in range(len(H)))\n", "c_X = sum(c_coeffs[i] * L[i] for i in range(len(H)))\n", "\n", "# Recursive auxiliary polynomial z(X)\n", "z = [a_coeffs[0] * c_coeffs[0]]\n", "for i in range(1, len(H)):\n", " z.append(z[i-1] + a_coeffs[i] * c_coeffs[i])\n", "\n", "z_X = sum(z[i] * L[i] for i in range(len(H)))\n", "v = z[-1] # Final sum\n", "\n", "def compute_s_polynomial(H, X):\n", " s_polynomials = []\n", " N = len(H)\n", " n = log(N, 2)\n", " s_polynomials.append(X**(2**(n - 1)) + F(1))\n", " for i in range(n - 2, -1, -1):\n", " temp = X**(2**i) + F(1)\n", " s_polynomials.append(s_polynomials[-1] * temp)\n", " s_polynomials.reverse()\n", " return s_polynomials\n", "\n", "# # Define the polynomials p_i(X)\n", "p = []\n", "s_polys = compute_s_polynomial(H, X)\n", "\n", "for i in range(n + 1):\n", " if i == 0:\n", " p.append(s_polys[0] * (c_X - prod([(F(1) - u_i) for u_i in u])))\n", " else:\n", " temp_X = c_X.subs(X=(omega^(2^(n - i)) * X))\n", " p.append(s_polys[i - 1] * (c_X * u[n - i] - temp_X * (F(1) - u[n - i])))\n", "\n", "# Define h_1(X), h_2(X), h_3(X)\n", "h1_X = L[0] * (z_X - a_X * c_coeffs[0])\n", "h2_X = (X - 1) * (z_X - z_X.subs(X=omega^(-1) * X) - a_X * c_X)\n", "h3_X = L[-1] * (z_X - v)\n", "\n", "# Aggregate all polynomials into h(X)\n", "alpha = F.random_element() # Random alpha\n", "h_X = sum(alpha^i * p[i] for i in range(len(p))) + alpha^(len(p)) * h1_X + alpha^(len(p) + 1) * h2_X + alpha^(len(p) + 2) * h3_X\n", "\n", "# Verify correctness of h(X)\n", "t_X = h_X // v_H # Quotient polynomial\n", "remainder = h_X % v_H # Remainder\n", "\n", "# Display results\n", "print(\"Polynomial h(X):\")\n", "show(h_X)\n", "\n", "print(\"Quotient polynomial t(X):\")\n", "show(t_X)\n", "\n", "print(\"Remainder:\")\n", "show(remainder)\n", "\n", "# Verify that h(X) is divisible by v_H(X)\n", "if remainder != 0: print(\"h(X) is not divisible by v_H(X)!\")\n", "else :\n", " print(\"Verification successful: h(X) is divisible by v_H(X).\")\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "ac5ece18", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "h(ζ): 4\n", "t(ζ): 15\n", "Remainder: 0\n", "Verification successful: h(ζ) is divisible by v_H(ζ).\n" ] } ], "source": [ "# Generate random challenge ζ ensuring ζ is not in H\n", "while True:\n", " zeta = F.random_element()\n", " if zeta not in H:\n", " break\n", "\n", "# Compute values of polynomials at ζ\n", "f_zeta = a_X(zeta) * c_X(zeta)\n", "c_zeta = c_X(zeta)\n", "z_zeta = z_X(zeta)\n", "\n", "# Compute quotient t(ζ) = h(ζ) // v_H(ζ)\n", "v_H_zeta = v_H(zeta)\n", "if v_H_zeta == 0:\n", " raise ValueError(\"Vanishing polynomial evaluates to zero at ζ, choose a different ζ.\")\n", "\n", "# Compute t(ζ)\n", "t_zeta = h_X(zeta) // v_H_zeta\n", "\n", "# Compute s_i(ζ) values\n", "s = [v_H(zeta) / vanishing_polynomial(H[:2**i])(zeta) for i in range(len(H))]\n", "\n", "# Compute L_0(ζ) and L_{N-1}(ζ)\n", "L0_zeta = v_H(zeta) / (N * (zeta - 1))\n", "LN_minus1_zeta = v_H(zeta) / (N * (omega * zeta - 1))\n", "\n", "# Compute p_i(ζ) values\n", "p_zeta = []\n", "for i in range(n + 1):\n", " if i == 0:\n", " p_zeta.append(s[0] * (c_zeta - prod([(F(1) - u_i) for u_i in u])))\n", " else:\n", " p_zeta.append(s[i] * (c_zeta * u[n - i] - c_X.subs(X=(omega^(2^(n - i)) * zeta)) * (F(1) - u[n - i])))\n", "\n", "# Compute h_1(ζ), h_2(ζ), h_3(ζ)\n", "h1_zeta = L0_zeta * (z_zeta - a_X(zeta) * c_coeffs[0])\n", "h2_zeta = (zeta - 1) * (z_zeta - z_X.subs(X=omega^(-1) * zeta) - a_X(zeta) * c_X(zeta))\n", "h3_zeta = LN_minus1_zeta * (z_zeta - v)\n", "\n", "# Aggregate polynomial evaluations into h(ζ)\n", "alpha = F.random_element()\n", "h_zeta = sum(alpha^i * p_zeta[i] for i in range(len(p_zeta))) + alpha^len(p_zeta) * h1_zeta + alpha^(len(p_zeta) + 1) * h2_zeta + alpha^(len(p_zeta) + 2) * h3_zeta\n", "\n", "# Verify correctness\n", "t_zeta = h_zeta // v_H_zeta\n", "# remainder = h_zeta % v_H_zeta\n", "\n", "# Display results\n", "print(\"h(ζ):\", h_zeta)\n", "print(\"t(ζ):\", t_zeta)\n", "print(\"Remainder:\", remainder)\n", "\n", "# Ensure h(ζ) is divisible by v_H(ζ)\n", "if remainder != 0:\n", " print(\"Verification failed: h(ζ) is not divisible by v_H(ζ)!\")\n", "else :\n", " print(\"Verification successful: h(ζ) is divisible by v_H(ζ).\")\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "2af18a77", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Univariate Polynomial a(X):\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 10 X^{7} + 14 X^{6} + 9 X^{5} + 5 X^{4} + 16 X^{3} + 3 X^{2} + 8 X + 3\\)" ], "text/latex": [ "$\\displaystyle 10 X^{7} + 14 X^{6} + 9 X^{5} + 5 X^{4} + 16 X^{3} + 3 X^{2} + 8 X + 3$" ], "text/plain": [ "10*X^7 + 14*X^6 + 9*X^5 + 5*X^4 + 16*X^3 + 3*X^2 + 8*X + 3" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Commitment of a(X):\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 10\\)" ], "text/latex": [ "$\\displaystyle 10$" ], "text/plain": [ "10" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Define the finite field and subgroup H\n", "p = 17 # Prime modulus\n", "F = GF(p) # Finite field F_p\n", "omega = F(9) # Primitive N-th root of unity in F_p\n", "N = 8 # Size of H, N = 2^n\n", "H = [omega^i for i in range(N)] # Multiplicative subgroup H of size N\n", "\n", "# Polynomial variable\n", "X = polygen(F, 'X')\n", "\n", "# Define the vanishing polynomial v_H(X)\n", "def vanishing_polynomial(H):\n", " v_H = F(1)\n", " for h in H:\n", " v_H *= (X - h)\n", " return v_H\n", "\n", "v_H = vanishing_polynomial(H)\n", "\n", "# Define the Lagrange basis polynomials L_i(X)\n", "def lagrange_basis(H, v_H):\n", " basis = []\n", " for i in range(len(H)):\n", " Li = (v_H / (X - H[i])) * (1 / v_H.derivative()(H[i]))\n", " basis.append(Li)\n", " return basis\n", "\n", "L = lagrange_basis(H, v_H)\n", "\n", "# Define the MLE Polynomial coefficients\n", "a_coeffs = [F.random_element() for _ in range(N)] # Random coefficients a_0, ..., a_{N-1}\n", "\n", "# Construct the univariate polynomial a(X)\n", "a_X = sum(a_coeffs[i] * L[i] for i in range(N))\n", "\n", "# Display the univariate polynomial a(X)\n", "print(\"Univariate Polynomial a(X):\")\n", "show(a_X)\n", "\n", "# Simulate the SRS of KZG10 (Commitment scheme)\n", "# Example SRS: {g^1, g^2, ..., g^N}, where g is a generator\n", "g = F.random_element() # Random generator in F_p\n", "SRS = [g^i for i in range(N)] # SRS elements\n", "\n", "# Commit a(X)\n", "commitment = sum(a_coeffs[i] * SRS[i] for i in range(N))\n", "print(\"Commitment of a(X):\")\n", "show(commitment)\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "f6ed93cd", "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "a_coeffs: [1, 10, 9, 7, 12, 6, 11, 12]\n", "c_coeffs: [2, 6, 11, 16, 0, 0, 0, 0]\n", "polynomial_value_v: 1\n", "c(X):\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 6 X^{7} + 6 X^{6} + X^{5} + X^{4} + 9 X^{3} + 13 X^{2} + 2 X + 15\\)" ], "text/latex": [ "$\\displaystyle 6 X^{7} + 6 X^{6} + X^{5} + X^{4} + 9 X^{3} + 13 X^{2} + 2 X + 15$" ], "text/plain": [ "6*X^7 + 6*X^6 + X^5 + X^4 + 9*X^3 + 13*X^2 + 2*X + 15" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Commitment of c(X):\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 10\\)" ], "text/latex": [ "$\\displaystyle 10$" ], "text/plain": [ "10" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "s_polys: [X^7 + X^6 + X^5 + X^4 + X^3 + X^2 + X + 1, X^6 + X^4 + X^2 + 1, X^4 + 1]\n", "s_polys: [X^7 + X^6 + X^5 + X^4 + X^3 + X^2 + X + 1, X^6 + X^4 + X^2 + 1, X^4 + 1]\n", "Quotient Polynomial t(X):\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 5 X^{7} + 10 X^{6} + 5 X^{5} + 13 X^{4} + 13 X^{3} + 6 X^{2} + 4 X + 12\\)" ], "text/latex": [ "$\\displaystyle 5 X^{7} + 10 X^{6} + 5 X^{5} + 13 X^{4} + 13 X^{3} + 6 X^{2} + 4 X + 12$" ], "text/plain": [ "5*X^7 + 10*X^6 + 5*X^5 + 13*X^4 + 13*X^3 + 6*X^2 + 4*X + 12" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Aggregation Polynomial h(X):\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 5 X^{15} + 10 X^{14} + 5 X^{13} + 13 X^{12} + 13 X^{11} + 6 X^{10} + 4 X^{9} + 12 X^{8} + 12 X^{7} + 7 X^{6} + 12 X^{5} + 4 X^{4} + 4 X^{3} + 11 X^{2} + 13 X + 5\\)" ], "text/latex": [ "$\\displaystyle 5 X^{15} + 10 X^{14} + 5 X^{13} + 13 X^{12} + 13 X^{11} + 6 X^{10} + 4 X^{9} + 12 X^{8} + 12 X^{7} + 7 X^{6} + 12 X^{5} + 4 X^{4} + 4 X^{3} + 11 X^{2} + 13 X + 5$" ], "text/plain": [ "5*X^15 + 10*X^14 + 5*X^13 + 13*X^12 + 13*X^11 + 6*X^10 + 4*X^9 + 12*X^8 + 12*X^7 + 7*X^6 + 12*X^5 + 4*X^4 + 4*X^3 + 11*X^2 + 13*X + 5" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Accumulation Polynomial z(X):\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 10 X^{7} + 7 X^{6} + 16 X^{5} + 4 X^{4} + 13 X^{3} + 4 X + 16\\)" ], "text/latex": [ "$\\displaystyle 10 X^{7} + 7 X^{6} + 16 X^{5} + 4 X^{4} + 13 X^{3} + 4 X + 16$" ], "text/plain": [ "10*X^7 + 7*X^6 + 16*X^5 + 4*X^4 + 13*X^3 + 4*X + 16" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "s_polys: [X^7 + X^6 + X^5 + X^4 + X^3 + X^2 + X + 1, X^6 + X^4 + X^2 + 1, X^4 + 1]\n", "Evaluations at coset D': {'c(X)': [10, 1, 0, 1, 6, 15, 11, 8], 'z(X)': [11, 13, 11, 16, 0, 10, 12, 4], 't(X)': [8, 7, 10, 1, 14, 16, 12, 11], 'a(X)': [6, 1, 0, 16, 3, 6, 12, 7]}\n", "KZG10 Proofs: {'c(X)': [5, 14, 15, 14, 9, 0, 4, 7], 'z(X)': [2, 0], 't(X)': [3, 4, 1, 10, 14, 12, 16, 0], 'a(X)': [4, 9, 10, 11, 7, 4, 15, 3]}\n" ] } ], "source": [ "# Step 1: Define Common Input Struct\n", "class CommonInput:\n", " def __init__(self, commitment_a, evaluation_point_u, polynomial_value_v):\n", " \"\"\"\n", " Initialize the common input for the protocol.\n", " :param commitment_a: Commitment of a(X) (Ca)\n", " :param evaluation_point_u: Evaluation point (u_0, u_1, ..., u_{n-1})\n", " :param polynomial_value_v: Value of MLE polynomial at the evaluation point\n", " \"\"\"\n", " self.commitment_a = commitment_a\n", " self.evaluation_point_u = evaluation_point_u\n", " self.polynomial_value_v = polynomial_value_v\n", "\n", "\n", "# Step 2: Define the Prover Class\n", "class Prover:\n", " def __init__(self, a_coeffs, lagrange_basis, subgroup_H, vanishing_poly, finite_field, common_input: CommonInput):\n", " \"\"\"\n", " Initialize the prover with the polynomial coefficients and other required inputs.\n", " :param a_coeffs: Coefficients of a(X)\n", " :param lagrange_basis: Lagrange basis polynomials\n", " :param subgroup_H: Subgroup H\n", " :param vanishing_poly: Vanishing polynomial v_H(X)\n", " \"\"\"\n", " self.a_coeffs = a_coeffs\n", " self.lagrange_basis = lagrange_basis\n", " self.subgroup_H = subgroup_H\n", " self.vanishing_poly = vanishing_poly\n", " self.polynomial_value = common_input.polynomial_value_v # v = f(u)\n", " self.finite_field = finite_field \n", " \n", " def compute_selector_polynomials(self):\n", " \"\"\"\n", " Construct selector polynomials s_i(X).\n", " \"\"\"\n", " s_polynomials = []\n", " N = len(self.subgroup_H)\n", " n = log(N, 2)\n", " s_polynomials.append(X**(2**(n - 1)) + F(1))\n", " for i in range(n - 2, -1, -1):\n", " temp = X**(2**i) + F(1)\n", " s_polynomials.append(s_polynomials[-1] * temp)\n", " s_polynomials.reverse()\n", " print(\"s_polys: \", s_polys)\n", " return s_polynomials\n", " \n", " def compute_constraint_polynomials(self, c_X, evaluation_point_u):\n", " \"\"\"\n", " Construct constraint polynomials p_0(X), ..., p_n(X).\n", " \"\"\"\n", " p_polys = []\n", " s_polys = self.compute_selector_polynomials()\n", " n = len(evaluation_point_u)\n", "\n", " # Construct p_0(X)\n", " p_0 = s_polys[0] * (c_X - prod([(1 - u) for u in evaluation_point_u]))\n", " p_polys.append(p_0)\n", "\n", " # Construct p_k(X) for k = 1 to n\n", " omega = self.subgroup_H[1]\n", " for k in range(1, n + 1):\n", " # omega_k = self.subgroup_H[k]\n", " term = s_polys[k - 1] * ((evaluation_point_u[n - k] * c_X) - (1 - evaluation_point_u[n - k]) * c_X.subs(X=(omega^(2^(n - k))) * X))\n", " p_polys.append(term)\n", " return p_polys\n", " \n", " def compute_accumulation_polynomial(self, c_X):\n", " \"\"\"\n", " Construct accumulation polynomial z(X).\n", " \"\"\"\n", " # Ensure c_X is a proper polynomial\n", " c_poly = c_X.numerator() # Extract the numerator as a polynomial\n", " c_coeffs = [c_poly.subs(X=x) for x in self.subgroup_H]\n", " \n", " # Compute z(X) coefficients\n", " z_coeffs = [self.a_coeffs[0] * c_coeffs[0]] # First term\n", " for i in range(1, len(self.a_coeffs)):\n", " z_coeffs.append(z_coeffs[-1] + self.a_coeffs[i] * c_coeffs[i])\n", "\n", " # Construct z(X) as a linear combination of Lagrange basis\n", " z_X = sum(z_coeffs[i] * self.lagrange_basis[i] for i in range(len(self.a_coeffs)))\n", " return z_X\n", " \n", " def compute_constraint_h_polynomials(self, z_X, a_X, c_X):\n", " \"\"\"\n", " Construct constraint polynomials h_0(X), h_1(X), h_2(X).\n", " \"\"\"\n", " # Ensure c_X is a proper polynomial\n", " c_poly = c_X.numerator() # Extract the numerator as a polynomial\n", " \n", " # Construct h_0(X)\n", " h0_X = self.lagrange_basis[0] * (z_X - self.a_coeffs[0] * c_poly.subs(X=1))\n", " \n", " # Construct h_1(X)\n", " z_prev = z_X.subs(X=self.subgroup_H[-1] * X) # z(ω^-1 * X)\n", " h1_X = (X - 1) * (z_X - z_prev - a_X * c_X)\n", " \n", " # Construct h_2(X)\n", " h2_X = self.lagrange_basis[-1] * (z_X - self.polynomial_value)\n", "\n", " return h0_X, h1_X, h2_X \n", "\n", " \n", " def compute_aggregation_polynomial(self, constraint_polys, h_polys, alpha):\n", " \"\"\"\n", " Construct aggregation polynomial h(X).\n", " \"\"\"\n", " n = len(constraint_polys)\n", " h_X = sum(alpha**i * constraint_polys[i] for i in range(n))\n", " h_X += alpha**n * h_polys[0] + alpha**(n + 1) * h_polys[1] + alpha**(n + 2) * h_polys[2]\n", " return h_X\n", "\n", " def compute_t_polynomial(self, h_X):\n", " \"\"\"\n", " Compute quotient polynomial t(X) satisfying h(X) = t(X) * v_H(X).\n", " \"\"\"\n", " if self.vanishing_poly == 0:\n", " raise ZeroDivisionError(\"Vanishing polynomial v_H(X) evaluated to 0.\")\n", " t_X = h_X // self.vanishing_poly\n", " return t_X\n", " \n", " def compute_c_polynomial(self, evaluation_point_u):\n", " \"\"\"\n", " Construct the polynomial c(X) using the provided evaluation point.\n", " :param evaluation_point_u: The evaluation point (u_0, u_1, ..., u_{n-1})\n", " :return: c(X)\n", " \"\"\"\n", " def eq_tilde(bits_i, u_vector):\n", " result = F(1)\n", " for bit, u in zip(bits_i, u_vector):\n", " result *= (1 - bit) * (1 - u) + bit * u\n", " return result\n", "\n", " # Compute coefficients c_i\n", " c_coeffs = [eq_tilde(list(reversed(list(map(int, f\"{i:03b}\")))), evaluation_point_u) for i in range(len(self.subgroup_H))]\n", "\n", " # Construct c(X)\n", " c_X = sum(c_coeffs[i] * self.lagrange_basis[i] for i in range(len(self.subgroup_H)))\n", " return c_X\n", "\n", " def commit_c_polynomial(self, c_X):\n", " \"\"\"\n", " Compute the commitment of c(X).\n", " :param c_X: The polynomial c(X)\n", " :return: Commitment of c(X)\n", " \"\"\"\n", " # Convert c_X to a polynomial\n", " c_poly = c_X.numerator() # Get the numerator to ensure it's a polynomial\n", " g = F.random_element() # Random generator for SRS\n", " # TODO: should set SRS be a parameter\n", " SRS = [g**i for i in range(len(self.subgroup_H))]\n", "\n", " # Get the coefficients of the polynomial\n", " c_coeffs = c_poly.list() # Retrieve the list of coefficients\n", " # Pad coefficients with zeros to match the length of the SRS\n", " c_coeffs += [F(0)] * (len(self.subgroup_H) - len(c_coeffs))\n", "\n", " # Compute the commitment as a linear combination with the SRS\n", " commitment_c = sum(c_coeffs[i] * SRS[i] for i in range(len(self.subgroup_H)))\n", " return commitment_c\n", "\n", " def round_2(self, c_X, a_X, evaluation_point_u):\n", " \"\"\"\n", " Perform all steps in Round 2.\n", " \"\"\"\n", " # Step 1: Compute selector polynomials\n", " s_polys = self.compute_selector_polynomials()\n", "\n", " # Step 2: Compute constraint polynomials\n", " constraint_polys = self.compute_constraint_polynomials(c_X, evaluation_point_u)\n", "\n", " # Step 3: Compute accumulation polynomial z(X)\n", " z_X = self.compute_accumulation_polynomial(c_X)\n", " z_value = [z_X.subs(X=x) for x in self.subgroup_H]\n", "\n", " # Step 4: Compute constraint h polynomials\n", " h_polys = self.compute_constraint_h_polynomials(z_X, a_X, c_X)\n", "\n", " # Step 5: Compute aggregation polynomial h(X)\n", " alpha = F.random_element() # Random challenge\n", " h_X = self.compute_aggregation_polynomial(constraint_polys, h_polys, alpha)\n", "\n", " # Step 6: Compute quotient polynomial t(X)\n", " t_X = self.compute_t_polynomial(h_X)\n", "\n", " return t_X, h_X, z_X\n", " \n", " def round_3(self, verifier, c_X, z_X, t_X, a_X):\n", " \"\"\"\n", " Perform Round 3 of the protocol.\n", " :param verifier: Verifier instance providing ζ\n", " :param c_X: Polynomial c(X)\n", " :param z_X: Accumulation polynomial z(X)\n", " :param t_X: Quotient polynomial t(X)\n", " :param a_X: Original polynomial a(X)\n", " :return: Evaluations and KZG10 proofs\n", " \"\"\"\n", " # Step 1: Verifier sends random evaluation point ζ\n", " zeta = verifier.generate_valid_zeta() # Verifier provides ζ\n", "\n", " # Step 2: Calculate values of s_i(X) at ζ\n", " s_polys = self.compute_selector_polynomials()\n", " s_values = [s(zeta) for s in s_polys]\n", "\n", " # Step 3: Define new domain D and coset D'\n", " D = self.subgroup_H\n", " D_prime = [zeta * d for d in D]\n", "# for d in D_prime:\n", "# if self.vanishing_poly(d) == 0:\n", "# raise ZeroDivisionError(f\"v_H({d}) = 0, cannot compute t(X).\")\n", "\n", "\n", " # Step 4: Evaluate c(X), z(X), t(X), a(X) at D'\n", " c_values = [c_X(d) for d in D_prime]\n", " z_values = [z_X(d) for d in D_prime]\n", " t_values = [t_X(d) for d in D_prime]\n", " a_values = [a_X(d) for d in D_prime]\n", "\n", " # Step 5: Send evaluations and KZG10 proofs\n", " evaluations = {\n", " \"c(X)\": c_values,\n", " \"z(X)\": z_values,\n", " \"t(X)\": t_values,\n", " \"a(X)\": a_values\n", " }\n", "\n", " # Generate KZG10 proofs for the evaluations\n", " kzg_proofs = {\n", " \"c(X)\": self.generate_kzg_proof(c_X, D_prime),\n", " \"z(X)\": self.generate_kzg_proof(z_X, [zeta, zeta / self.subgroup_H[-1]]),\n", " \"t(X)\": self.generate_kzg_proof(t_X, D_prime),\n", " \"a(X)\": self.generate_kzg_proof(a_X, D_prime),\n", " }\n", " \n", " # Return evaluations and KZG proofs\n", " evaluations = {\n", " \"c(X)\": c_values,\n", " \"z(X)\": z_values,\n", " \"t(X)\": t_values,\n", " \"a(X)\": a_values\n", " }\n", " return evaluations, kzg_proofs\n", " \n", " def generate_kzg_proof(self, polynomial, points):\n", " \"\"\"\n", " Generate KZG10 proofs for the given polynomial at the specified points.\n", " :param polynomial: Polynomial for which the proof is generated\n", " :param points: Points where the polynomial is evaluated\n", " :return: List of proofs\n", " \"\"\"\n", " # Ensure the polynomial is in the proper polynomial ring\n", " poly_ring = PolynomialRing(self.finite_field, 'X')\n", " polynomial = poly_ring(polynomial)\n", "\n", " # Generate SRS large enough for the polynomial's degree\n", " max_degree = polynomial.degree()\n", " SRS = [self.finite_field.random_element() ** i for i in range(max_degree + 1)]\n", "\n", " proofs = []\n", " for point in points:\n", " # Compute the divisor\n", " divisor = polynomial - polynomial(point)\n", "\n", " # Convert the numerator into the finite field polynomial ring directly\n", " numerator = divisor.numerator()\n", " numerator_in_ring = poly_ring(numerator)\n", "\n", " # Generate the proof as a sum of SRS coefficients\n", " proof = sum(numerator_in_ring[i] * SRS[i] for i in range(numerator_in_ring.degree() + 1))\n", " proofs.append(proof)\n", "\n", " return proofs\n", "\n", " \n", "class Verifier:\n", " def __init__(self, finite_field, vanishing_poly, subgroup_H):\n", " self.finite_field = finite_field # Finite field F_p\n", " self.vanishing_poly = vanishing_poly # Vanishing polynomial v_H(X)\n", " self.subgroup_H = subgroup_H # Subgroup H of size 2^n\n", " self.random_zeta = None # Random evaluation point ζ\n", " \n", " def generate_random_alpha(self):\n", " \"\"\"\n", " Generate and send random scalar α for aggregation.\n", " \"\"\"\n", " self.random_alpha = self.finite_field.random_element()\n", " return self.random_alpha\n", " \n", " \n", " def generate_valid_zeta(self):\n", " while True:\n", " zeta = self.finite_field.random_element()\n", " if all(self.vanishing_poly(zeta * d) != 0 for d in self.subgroup_H):\n", " self.random_zeta = zeta\n", " return zeta\n", "\n", " def verify_commitment(self, commitment, evaluation_point, polynomial, proof):\n", " \"\"\"\n", " Verify a single KZG commitment.\n", " :param commitment: Commitment of the polynomial\n", " :param evaluation_point: Evaluation point ζ\n", " :param polynomial: Polynomial to verify\n", " :param proof: KZG proof\n", " :return: True if verification succeeds, False otherwise\n", " \"\"\"\n", " # Simulate KZG verification (replace with actual verification in implementation)\n", " return hash((commitment, evaluation_point, polynomial, proof)) % 2 == 1\n", "\n", " def verify_constraint_equation(self, t_zeta, h_polys, p_polys, alpha, v_H_zeta):\n", " \"\"\"\n", " Verify the final constraint equation:\n", " t(ζ) * v_H(ζ) = sum of constraint evaluations.\n", " \"\"\"\n", " # Compute the left-hand side\n", " lhs = t_zeta * v_H_zeta\n", "\n", " # Compute the right-hand side\n", " rhs = sum(alpha**i * p_polys[i] for i in range(len(p_polys)))\n", " rhs += alpha**len(p_polys) * h_polys[0]\n", " rhs += alpha**(len(p_polys) + 1) * h_polys[1]\n", " rhs += alpha**(len(p_polys) + 2) * h_polys[2]\n", "\n", " return lhs == rhs\n", "\n", " def verify_proof(self, proof, zeta, alpha, v_H, lagrange_basis):\n", " \"\"\"\n", " Perform the verification of the proof π.\n", " :param proof: Proof π containing all elements\n", " :param zeta: Evaluation point ζ\n", " :param alpha: Aggregation scalar α\n", " :param v_H: Vanishing polynomial v_H(X)\n", " :param lagrange_basis: Lagrange basis polynomials\n", " :return: True if all verifications succeed, False otherwise\n", " \"\"\"\n", " # Parse the proof\n", " C_t, C_z, C_c = proof[\"C_t\"], proof[\"C_z\"], proof[\"C_c\"]\n", " a_zeta, z_zeta, z_omega_zeta, t_zeta = proof[\"a(ζ)\"], proof[\"z(ζ)\"], proof[\"z(ζ/ω)\"], proof[\"t(ζ)\"]\n", " c_values = proof[\"c_values\"]\n", " kzg_proofs = proof[\"kzg_proofs\"]\n", "\n", " # Verify individual KZG commitments\n", " if not self.verify_commitment(C_c, zeta, \"c(X)\", kzg_proofs[\"c(X)\"]):\n", " return False\n", " if not self.verify_commitment(C_z, zeta, \"z(X)\", kzg_proofs[\"z(X)\"]):\n", " return False\n", " if not self.verify_commitment(C_t, zeta, \"t(X)\", kzg_proofs[\"t(X)\"]):\n", " return False\n", "\n", " # Compute constraint polynomials at ζ\n", " p_polys = [\n", " lagrange_basis[0] * (c_values[0] - (1 - zeta)),\n", " lagrange_basis[1] * (zeta - z_omega_zeta),\n", " lagrange_basis[-1] * (z_zeta - a_zeta)\n", " ]\n", "\n", " # Compute h polynomials at ζ\n", " h_polys = [\n", " lagrange_basis[0] * (z_zeta - a_zeta),\n", " (z_zeta - z_omega_zeta) - t_zeta,\n", " lagrange_basis[-1] * (t_zeta - a_zeta)\n", " ]\n", "\n", " # Verify the final constraint equation\n", " return self.verify_constraint_equation(t_zeta, h_polys, p_polys, alpha, v_H(zeta))\n", "\n", "\n", "# Initialize Parameters\n", "p = 17 # Prime modulus\n", "F = GF(p) # Finite field\n", "omega = F(9) # Primitive root of unity\n", "N = 8 # Size of the subgroup H\n", "H = [omega^i for i in range(N)] # Subgroup H\n", "X = polygen(F, 'X')\n", "\n", "# Compute vanishing polynomial and Lagrange basis\n", "v_H = vanishing_polynomial(H)\n", "L = lagrange_basis(H, v_H)\n", "\n", "# Random coefficients for a(X)\n", "a_coeffs = [F.random_element() for _ in range(N)]\n", "a_X = sum(a_coeffs[i] * L[i] for i in range(N))\n", "\n", "# Commitment of a(X)\n", "g = F.random_element() # Random generator for SRS\n", "SRS = [g^i for i in range(N)]\n", "commitment_a = sum(a_coeffs[i] * SRS[i] for i in range(N))\n", "\n", "# Define common inputs\n", "evaluation_point_u = [F.random_element() for _ in range(3)] # Random evaluation point\n", "c_coeffs = [eq_tilde(list(reversed(list(map(int, f\"{i:03b}\")))), evaluation_point_u) for i in range(len(H))]\n", "print(\"a_coeffs: \", a_coeffs)\n", "print(\"c_coeffs: \", c_coeffs)\n", "polynomial_value_v = sum(a_coeffs[i] * c_coeffs[i] for i in range(N))\n", "print(\"polynomial_value_v: \", polynomial_value_v)\n", "# polynomial_value_v = a_X(evaluation_point_u[0]) # Example: value of a(X) at evaluation point\n", "common_input = CommonInput(commitment_a, evaluation_point_u, polynomial_value_v)\n", "\n", "# Prover Round 1: Compute c(X) and its commitment\n", "prover = Prover(a_coeffs, L, H, v_H, F, common_input)\n", "c_X = prover.compute_c_polynomial(evaluation_point_u)\n", "test_c_values = [c_X.subs(X=e) for e in H]\n", "commitment_c = prover.commit_c_polynomial(c_X)\n", "\n", "# Display results\n", "print(\"c(X):\")\n", "show(c_X)\n", "print(\"Commitment of c(X):\")\n", "show(commitment_c)\n", "\n", "# Perform Round 2\n", "t_X, h_X, z_X = prover.round_2(c_X, a_X, evaluation_point_u)\n", "\n", "# Display results\n", "print(\"Quotient Polynomial t(X):\")\n", "show(t_X)\n", "print(\"Aggregation Polynomial h(X):\")\n", "show(h_X)\n", "print(\"Accumulation Polynomial z(X):\")\n", "show(z_X)\n", "\n", "# Initialize Verifier with subgroup H and vanishing polynomial\n", "verifier = Verifier(F, vanishing_poly=prover.vanishing_poly, subgroup_H=prover.subgroup_H)\n", "\n", "# Validate v_H(X) at D'\n", "# v_H_values = [prover.vanishing_poly(zeta * d) for d in prover.subgroup_H]\n", "# if any(v == 0 for v in v_H_values):\n", "# print(\"Error: v_H(X) evaluates to 0 at some points in D'.\")\n", "\n", "# Perform Round 3 with valid zeta\n", "try:\n", " evaluations, kzg_proofs = prover.round_3(verifier, c_X, z_X, t_X, a_X)\n", " print(\"Evaluations at coset D':\", evaluations)\n", " print(\"KZG10 Proofs:\", kzg_proofs)\n", "except ZeroDivisionError as e:\n", " print(\"Error during Round 3:\", e)\n", "except ValueError as e:\n", " print(\"Validation Error:\", e)" ] }, { "cell_type": "code", "execution_count": null, "id": "a07e88e6", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "24fe96e7", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 10.3", "language": "sage", "name": "SageMath-10.3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.8" } }, "nbformat": 4, "nbformat_minor": 5 }