Last active
September 2, 2023 14:02
-
-
Save tarassh/4f0bfb102fd2fa2496917cd64575a70e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"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