Skip to content

Instantly share code, notes, and snippets.

@tarassh

tarassh/R1CS-QAP.ipynb

Last active September 2, 2023 14:02
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tarassh/4f0bfb102fd2fa2496917cd64575a70e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tarassh/4f0bfb102fd2fa2496917cd64575a70e to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
R1CS-QAP.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Evaluate\n",
"\n",
"$ 5x^{3} - 4x^{2}y^{2} + 13xy^{2} + x^{2} -10y = out $\n",
"\n",
"$ v_1 = xx $\n",
"\n",
"$ v_2 = yy $\n",
"\n",
"$ v_3 = 5xv_1 $\n",
"\n",
"$ v_4 = 4v_1v_2 $\n",
"\n",
"$ out -v_3 + v_4 - v_1 + 10y = 13xv_2 $\n",
"\n",
"$ w = \\begin{bmatrix}\n",
"1 & out & x & y & v_1 & v_2 & v_3 & v_4\n",
"\\end{bmatrix} $\n",
"\n",
"\n",
"\n",
"$ A = \\begin{bmatrix}\n",
"1 & out & x & y & v_1 & v_2 & v_3 & v_4 \\\\\n",
"0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n",
"0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n",
"0 & 0 & 5 & 0 & 0 & 0 & 0 & 0 \\\\\n",
"0 & 0 & 0 & 0 & 4 & 0 & 0 & 0 \\\\\n",
"0 & 0 & 13 & 0 & 0 & 0 & 0 & 0 \\\\\n",
"\\end{bmatrix} $\n",
"\n",
"\n",
"$ B = \\begin{bmatrix}\n",
"1 & out & x & y & v_1 & v_2 & v_3 & v_4 \\\\\n",
"0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n",
"0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n",
"0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n",
"0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
"0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
"\\end{bmatrix} $\n",
"\n",
"\n",
"$ C = \\begin{bmatrix}\n",
"1 & out & x & y & v_1 & v_2 & v_3 & v_4 \\\\\n",
"0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n",
"0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
"0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n",
"0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n",
"0 & 1 & 0 & 10 & -1 & 0 & -1 & 1 \\\\\n",
"\\end{bmatrix} $\n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"w = [ 1 104 2 3 4 9 40 144]\n",
"Aw = [ 2 3 10 16 26]\n",
"Bw = [2 3 4 9 9]\n",
"Aw * Bw = [ 4 9 40 144 234]\n",
"Cw = [ 4 9 40 144 234]\n"
]
}
],
"source": [
"import galois\n",
"import numpy as np\n",
"\n",
"p = 71\n",
"p = 21888242871839275222246405745257275088548364400416034343698204186575808495617\n",
"F71 = galois.GF(p)\n",
"\n",
"x = F71(2)\n",
"y = F71(3)\n",
"\n",
"v1 = x * x\n",
"v2 = y * y\n",
"v3 = 5 * x * v1\n",
"v4 = 4 * v1 * v2\n",
"out = 5*x**3 - 4*x**2*y**2 + 13*x*y**2 + x**2 - 10*y\n",
"\n",
"w = F71([1, out, x, y, v1, v2, v3, v4])\n",
"\n",
"print(\"w =\", w)\n",
"\n",
"A = F71([[0, 0, 1, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 1, 0, 0, 0, 0],\n",
" [0, 0, 5, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 4, 0, 0, 0],\n",
" [0, 0, 13, 0, 0, 0, 0, 0]])\n",
"\n",
"B = F71([[0, 0, 1, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 1, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 1, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 1, 0, 0],\n",
" [0, 0, 0, 0, 0, 1, 0, 0]])\n",
"\n",
"C = F71([[0, 0, 0, 0, 1, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 1, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 1, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 1],\n",
" [0, 1, 0, 10, F71(p - 1), 0, F71(p - 1), 1]])\n",
"\n",
"Aw = np.dot(A, w)\n",
"Bw = np.dot(B, w)\n",
"Cw = np.dot(C, w)\n",
"\n",
"print(\"Aw =\", Aw)\n",
"print(\"Bw =\", Bw)\n",
"\n",
"AwBw = np.multiply(Aw, Bw)\n",
"\n",
"print(\"Aw * Bw =\", AwBw)\n",
"\n",
"print(\"Cw = \", Cw)\n",
"\n",
"assert np.all(AwBw == Cw)\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"L\n",
"[[ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]\n",
" [ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]\n",
" [ 68\n",
" 21888242871839275222246405745257275088548364400416034343698204186575808495486\n",
" 18240202393199396018538671454381062573790303667013361953081836822146507079764\n",
" 21888242871839275222246405745257275088548364400416034343698204186575808495596\n",
" 3648040478639879203707734290876212514758060733402672390616367364429301415938]\n",
" [21888242871839275222246405745257275088548364400416034343698204186575808495607\n",
" 3648040478639879203707734290876212514758060733402672390616367364429301415954\n",
" 18240202393199396018538671454381062573790303667013361953081836822146507079671\n",
" 18240202393199396018538671454381062573790303667013361953081836822146507079683\n",
" 3648040478639879203707734290876212514758060733402672390616367364429301415936]\n",
" [21888242871839275222246405745257275088548364400416034343698204186575808495597\n",
" 7296080957279758407415468581752425029516121466805344781232734728858602831913\n",
" 7296080957279758407415468581752425029516121466805344781232734728858602831845\n",
" 14592161914559516814830937163504850059032242933610689562465469457717205663752\n",
" 14592161914559516814830937163504850059032242933610689562465469457717205663744]\n",
" [ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]\n",
" [ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]\n",
" [ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]]\n",
"\n",
"R\n",
"[[ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]\n",
" [ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]\n",
" [ 5\n",
" 9120101196599698009269335727190531286895151833506680976540918411073253539834\n",
" 912010119659969800926933572719053128689515183350668097654091841107325353987\n",
" 12768141675239577212977070018066743801653212566909353367157285775502554955776\n",
" 20976232752179305421319472172538221959858849217065366246044112345468483141633]\n",
" [21888242871839275222246405745257275088548364400416034343698204186575808495607\n",
" 3648040478639879203707734290876212514758060733402672390616367364429301415954\n",
" 18240202393199396018538671454381062573790303667013361953081836822146507079671\n",
" 18240202393199396018538671454381062573790303667013361953081836822146507079683\n",
" 3648040478639879203707734290876212514758060733402672390616367364429301415936]\n",
" [ 10\n",
" 10944121435919637611123202872628637544274182200208017171849102093287904247789\n",
" 16416182153879456416684804308942956316411273300312025757773653139931856371725\n",
" 21888242871839275222246405745257275088548364400416034343698204186575808495614\n",
" 16416182153879456416684804308942956316411273300312025757773653139931856371713]\n",
" [21888242871839275222246405745257275088548364400416034343698204186575808495613\n",
" 20064222632519335620392538599819168831169334033714698148390020504361157787657\n",
" 8208091076939728208342402154471478158205636650156012878886826569965928185851\n",
" 12768141675239577212977070018066743801653212566909353367157285775502554955778\n",
" 2736030358979909402780800718157159386068545550052004292962275523321976061952]\n",
" [ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]\n",
" [ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]]\n",
"\n",
"O\n",
"[[ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]\n",
" [ 1\n",
" 1824020239319939601853867145438106257379030366701336195308183682214650707966\n",
" 11856131555579607412050136445347690672963697383558685269503193934395229601794\n",
" 9120101196599698009269335727190531286895151833506680976540918411073253539840\n",
" 20976232752179305421319472172538221959858849217065366246044112345468483141633]\n",
" [ 0\n",
" 0\n",
" 0\n",
" 0\n",
" 0]\n",
" [ 10\n",
" 18240202393199396018538671454381062573790303667013361953081836822146507079660\n",
" 9120101196599698009269335727190531286895151833506680976540918411073253539855\n",
" 3648040478639879203707734290876212514758060733402672390616367364429301415932\n",
" 12768141675239577212977070018066743801653212566909353367157285775502554955777]\n",
" [ 4\n",
" 7296080957279758407415468581752425029516121466805344781232734728858602831868\n",
" 10944121435919637611123202872628637544274182200208017171849102093287904247810\n",
" 3648040478639879203707734290876212514758060733402672390616367364429301415936\n",
" 0]\n",
" [21888242871839275222246405745257275088548364400416034343698204186575808495607\n",
" 3648040478639879203707734290876212514758060733402672390616367364429301415954\n",
" 18240202393199396018538671454381062573790303667013361953081836822146507079671\n",
" 18240202393199396018538671454381062573790303667013361953081836822146507079683\n",
" 3648040478639879203707734290876212514758060733402672390616367364429301415936]\n",
" [ 9\n",
" 9120101196599698009269335727190531286895151833506680976540918411073253539823\n",
" 4560050598299849004634667863595265643447575916753340488270459205536626769931\n",
" 12768141675239577212977070018066743801653212566909353367157285775502554955774\n",
" 17328192273539426217611737881662009445100788483662693855427744981039181725697]\n",
" [21888242871839275222246405745257275088548364400416034343698204186575808495613\n",
" 20064222632519335620392538599819168831169334033714698148390020504361157787657\n",
" 8208091076939728208342402154471478158205636650156012878886826569965928185851\n",
" 12768141675239577212977070018066743801653212566909353367157285775502554955778\n",
" 2736030358979909402780800718157159386068545550052004292962275523321976061952]]\n",
"\n"
]
}
],
"source": [
"mtxs = [A, B, C]\n",
"poly_m = []\n",
"\n",
"for m in mtxs:\n",
" poly_list = []\n",
" for i in range(0, m.shape[1]):\n",
" points_x = F71(np.zeros(m.shape[0], dtype=int))\n",
" points_y = F71(np.zeros(m.shape[0], dtype=int))\n",
" for j in range(0, m.shape[0]):\n",
" points_x[j] = F71(j+1)\n",
" points_y[j] = m[j][i]\n",
"\n",
" poly = galois.lagrange_poly(points_x, points_y)\n",
" coef = poly.coefficients()[::-1]\n",
" if len(coef) < m.shape[0]:\n",
" coef = np.append(coef, np.zeros(m.shape[0] - len(coef), dtype=int))\n",
" poly_list.append(coef)\n",
" \n",
" poly_m.append(F71(poly_list))\n",
"\n",
"L = poly_m[0]\n",
"R = poly_m[1]\n",
"O = poly_m[2]\n",
"\n",
"print(f'''L\n",
"{L}\n",
"''')\n",
"\n",
"print(f'''R\n",
"{R}\n",
"''')\n",
"\n",
"print(f'''O\n",
"{O}\n",
"''')\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Ls = 10944121435919637611123202872628637544274182200208017171849102093287904247809x^4 + 3648040478639879203707734290876212514758060733402672390616367364429301415930x^3 + 10944121435919637611123202872628637544274182200208017171849102093287904247836x^2 + 18240202393199396018538671454381062573790303667013361953081836822146507079635x + 26\n",
"Rs = 11856131555579607412050136445347690672963697383558685269503193934395229601792x^4 + 20064222632519335620392538599819168831169334033714698148390020504361157787655x^3 + 20976232752179305421319472172538221959858849217065366246044112345468483141610x^2 + 12768141675239577212977070018066743801653212566909353367157285775502554955812x + 21888242871839275222246405745257275088548364400416034343698204186575808495601\n",
"Os = 12768141675239577212977070018066743801653212566909353367157285775502554955771x^4 + 7296080957279758407415468581752425029516121466805344781232734728858602831936x^3 + 9120101196599698009269335727190531286895151833506680976540918411073253539611x^2 + 14592161914559516814830937163504850059032242933610689562465469457717205664076x + 21888242871839275222246405745257275088548364400416034343698204186575808495461\n",
"T = x^5 + 21888242871839275222246405745257275088548364400416034343698204186575808495602x^4 + 85x^3 + 21888242871839275222246405745257275088548364400416034343698204186575808495392x^2 + 274x + 21888242871839275222246405745257275088548364400416034343698204186575808495497\n",
"T(1) = 0\n",
"T(2) = 0\n",
"T(3) = 0\n",
"T(4) = 0\n",
"T(5) = 0\n",
"----------\n",
"T(6) = 120\n",
"H = 5928065777789803706025068222673845336481848691779342634751596967197614800896x^3 + 14896165287779506748473248354411201101928747994727578928350166738086314115075x^2 + 1672018552709944635032711549984930735930777836142891512365835042030096482298x + 18240202393199396018538671454381062573790303667013361953081836822146507079683\n",
"rem = 0\n"
]
}
],
"source": [
"Ls = galois.Poly((w @ L)[::-1])\n",
"Rs = galois.Poly((w @ R)[::-1])\n",
"Os = galois.Poly((w @ O)[::-1])\n",
"\n",
"print(\"Ls = \", Ls)\n",
"print(\"Rs = \", Rs)\n",
"print(\"Os = \", Os)\n",
"\n",
"T = galois.Poly(F71([1, p-1]))\n",
"for i in range(2, A.shape[0] + 1):\n",
" T *= galois.Poly(F71([1, p-i]))\n",
"\n",
"print(\"T = \", T)\n",
"for i in range(1, A.shape[0] + 2):\n",
" print(f\"T({i}) = \", T(i))\n",
" if i == A.shape[0]:\n",
" print(\"-\"*10)\n",
"\n",
"H = (Ls * Rs - Os) // T\n",
"rem = (Ls * Rs - Os) % T\n",
"\n",
"print(\"H = \", H)\n",
"print(\"rem = \", rem)\n",
"\n",
"assert rem == 0"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"l = 1151\n",
"r = 21888242871839275222246405745257275088548364400416034343698204186575808494326\n",
"o = 21888242871839275222246405745257275088548364400416034343698204186575808483666\n",
"t = 15120\n",
"h = 10640118062699647677480891681722286501377677139091127805964404812918795796383\n"
]
}
],
"source": [
"tau = 10\n",
"\n",
"l = Ls(tau)\n",
"r = Rs(tau)\n",
"o = Os(tau)\n",
"t = T(tau)\n",
"h = H(tau)\n",
"\n",
"print(\"l = \", l)\n",
"print(\"r = \", r)\n",
"print(\"o = \", o)\n",
"print(\"t = \", t)\n",
"print(\"h = \", h)\n",
"\n",
"assert l * r - o == t * h"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"tau = 10\n",
"\n",
"Evaluation of Ls(tau)\n",
"P = 10944121435919637611123202872628637544274182200208017171849102093287904247809x^4 + 3648040478639879203707734290876212514758060733402672390616367364429301415930x^3 + 10944121435919637611123202872628637544274182200208017171849102093287904247836x^2 + 18240202393199396018538671454381062573790303667013361953081836822146507079635x + 26\n",
"P(10) = 1151\n",
"\n",
"Evaluation of Rs(tau)\n",
"P = 11856131555579607412050136445347690672963697383558685269503193934395229601792x^4 + 20064222632519335620392538599819168831169334033714698148390020504361157787655x^3 + 20976232752179305421319472172538221959858849217065366246044112345468483141610x^2 + 12768141675239577212977070018066743801653212566909353367157285775502554955812x + 21888242871839275222246405745257275088548364400416034343698204186575808495601\n",
"P(10) = 21888242871839275222246405745257275088548364400416034343698204186575808494326\n",
"\n",
"Evaluation of Os(tau)\n",
"P = 12768141675239577212977070018066743801653212566909353367157285775502554955771x^4 + 7296080957279758407415468581752425029516121466805344781232734728858602831936x^3 + 9120101196599698009269335727190531286895151833506680976540918411073253539611x^2 + 14592161914559516814830937163504850059032242933610689562465469457717205664076x + 21888242871839275222246405745257275088548364400416034343698204186575808495461\n",
"P(10) = 21888242871839275222246405745257275088548364400416034343698204186575808483666\n",
"\n",
"Evaluation of H(T(tau)*tau)\n",
"P = 5928065777789803706025068222673845336481848691779342634751596967197614800896x^3 + 14896165287779506748473248354411201101928747994727578928350166738086314115075x^2 + 1672018552709944635032711549984930735930777836142891512365835042030096482298x + 18240202393199396018538671454381062573790303667013361953081836822146507079683\n",
"P(10 * 15120) = 18240202393199396018538671454381062573790303667013361953081835886023564000933\n",
"\n",
"pairing(B, A) == pairing(G2, C) # A * B == C\n"
]
}
],
"source": [
"from py_ecc.optimized_bn128 import multiply, G1, G2, add, pairing\n",
"\n",
"def evaluate(poly, tau, t, use_G1 = True):\n",
" G = G1 if use_G1 else G2\n",
"\n",
" raw_eval = int(poly( (tau * t) % p ))\n",
" print(\"P = \", poly)\n",
" if t != 1:\n",
" print(f\"P({tau} * {t}) = \", raw_eval)\n",
" else:\n",
" print(f\"P({tau}) = \", raw_eval)\n",
"\n",
" coeficients = poly.coefficients()\n",
" \n",
" polys = []\n",
" degree = len(coeficients) - 1\n",
" for c in coeficients:\n",
" point = multiply(G, (pow(tau, degree, p) * t) % p)\n",
" polys.append(multiply(point, int(c)))\n",
" degree -= 1\n",
"\n",
" res = polys[0]\n",
" for i in range(1, len(polys)):\n",
" res = add(res, polys[i])\n",
"\n",
" return res\n",
"\n",
"print(f\"\"\"\n",
"tau = {tau}\"\"\")\n",
"\n",
"print(\"\"\"\n",
"Evaluation of Ls(tau)\"\"\")\n",
"A = evaluate(Ls, tau, 1, use_G1=True)\n",
"print(\"\"\"\n",
"Evaluation of Rs(tau)\"\"\")\n",
"B = evaluate(Rs, tau, 1, use_G1=False)\n",
"print(\"\"\"\n",
"Evaluation of Os(tau)\"\"\")\n",
"C1 = evaluate(Os, tau, 1, use_G1=True)\n",
"print(\"\"\"\n",
"Evaluation of H(T(tau)*tau)\"\"\")\n",
"C2 = evaluate(H, tau, int(t), use_G1=True)\n",
"\n",
"C = add(C1, C2)\n",
"\n",
"print(\"\"\"\n",
"pairing(B, A) == pairing(G2, C) # A * B == C\"\"\")\n",
"assert pairing(B, A) == pairing(G2, C)\n",
"\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"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.4"
},
"orig_nbformat": 4
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment