Skip to content

Instantly share code, notes, and snippets.

@cds-amal

cds-amal/.prettierrc.json

Created October 12, 2023 02:21
Show Gist options
  • Save cds-amal/1eb0b06667b0662567894fa4c9967905 to your computer and use it in GitHub Desktop.
Save cds-amal/1eb0b06667b0662567894fa4c9967905 to your computer and use it in GitHub Desktop.
Download ZIP
Created using remix-ide: Realtime Ethereum Contract Compiler and Runtime. Load this file by pasting this gists URL or ID at https://remix.ethereum.org/#version=soljson-v0.8.21+commit.d9974bed.js&optimize=false&runs=200&gist=
Raw
.prettierrc.json
{
"overrides": [
{
"files": "*.sol",
"options": {
"printWidth": 80,
"tabWidth": 4,
"useTabs": false,
"singleQuote": false,
"bracketSpacing": false
}
},
{
"files": "*.yml",
"options": {}
},
{
"files": "*.yaml",
"options": {}
},
{
"files": "*.toml",
"options": {}
},
{
"files": "*.json",
"options": {}
},
{
"files": "*.js",
"options": {}
},
{
"files": "*.ts",
"options": {}
}
]
}
Raw
week3.sol
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.21;
/// @title Zero Knowledge Proofs and Elliptic Curve Operations
/// @dev This contract implements certain elliptic curve operations and verifies cryptographic assertions.
contract ZK {
/// @dev Struct to represent an elliptic curve point.
struct ECPoint {
uint256 x;
uint256 y;
}
// Elliptic curve order.
uint256 order =
21888242871839275222246405745257275088548364400416034343698204186575808495617;
// Generator point G for the elliptic curve.
ECPoint G = ECPoint(1, 2);
/// @notice Adds two elliptic curve points.
/// @dev This function utilizes a precompiled contract at address 6 for the addition operation.
/// @param x1 X coordinate of the first point.
/// @param y1 Y coordinate of the first point.
/// @param x2 X coordinate of the second point.
/// @param y2 Y coordinate of the second point.
/// @return x X coordinate of the resulting point.
/// @return y Y coordinate of the resulting point.
function add(
uint256 x1,
uint256 y1,
uint256 x2,
uint256 y2
) public view returns (uint256 x, uint256 y) {
(bool ok, bytes memory result) = address(6).staticcall(
abi.encode(x1, y1, x2, y2)
);
require(ok, "add failed");
(x, y) = abi.decode(result, (uint256, uint256));
}
/// @notice Multiplies an elliptic curve point by a scalar.
/// @dev Uses a precompiled contract at address 7 for the multiplication operation.
/// @param scalar Scalar to multiply.
/// @param x1 X coordinate of the point.
/// @param y1 Y coordinate of the point.
/// @return x X coordinate of the resulting point.
/// @return y Y coordinate of the resulting point.
function mul(
uint256 scalar,
uint256 x1,
uint256 y1
) public view returns (uint256 x, uint256 y) {
(bool ok, bytes memory result) = address(7).staticcall(
abi.encode(x1, y1, scalar)
);
require(ok, "mul failed");
(x, y) = abi.decode(result, (uint256, uint256));
}
/// @dev Modular euclidean inverse of a number (mod p).
/// @param _x The number.
/// @param _pp The modulus.
/// @return q such that x*q = 1 (mod _pp).
function invMod(uint256 _x, uint256 _pp) internal pure returns (uint256) {
require(_x != 0 && _x != _pp && _pp != 0, "Invalid number");
uint256 q = 0;
uint256 newT = 1;
uint256 r = _pp;
uint256 t;
while (_x != 0) {
t = r / _x;
(q, newT) = (newT, addmod(q, (_pp - mulmod(t, newT, _pp)), _pp));
(r, _x) = (_x, r - t * _x);
}
return q;
}
/// @notice Validates if the elliptic curve addition of A and B corresponds to the rational number (num/den) when encoded in EC.
/// @param A First ECPoint.
/// @param B Second ECPoint.
/// @param num Numerator of the rational number.
/// @param den Denominator of the rational number.
/// @return verified True if the addition is valid, False otherwise.
function rationalAdd(
ECPoint memory A,
ECPoint memory B,
uint256 num,
uint256 den
) public view returns (bool verified) {
require(den != 0, "Denominator cannot be zero.");
// Calculate SUM = A + B
(uint256 SUMx, uint256 SUMy) = add(A.x, A.y, B.x, B.y);
// Convert the fraction num/den into an elliptic curve scalar multiplication.
uint256 scalar = mulmod(num, invMod(den, order), order);
(uint256 ECx, uint256 ECy) = mul(scalar, G.x, G.y);
verified = SUMx == ECx && SUMy == ECy;
}
/// @notice Validates if the matrix-vector product of `matrix` and `s` equals `o`.
/// @dev This function verifies the mathematical claim: matrix * s = o.
/// @param matrix Input matrix (flattened).
/// @param n Dimension of the matrix (nxn).
/// @param s Vector of ECPoints.
/// @param o Output vector (flattened).
/// @return verified True if the multiplication is valid, False otherwise.
function matmul_nbyn(
uint256[] memory matrix,
uint256 n,
ECPoint[] memory s,
uint256[] memory o
) public view returns (bool verified) {
require(matrix.length == n * n, "Matrix must be nxn");
require(o.length == n, "Matrix o should have n rows");
require(s.length == n, "Matrix s should have n rows.");
// Convert output scalars to their respective elliptic curve points.
ECPoint[] memory oPoints = new ECPoint[](o.length);
for (uint256 i = 0; i < o.length; i++) {
(uint256 pointX, uint256 pointY) = mul(o[i], G.x, G.y);
oPoints[i] = ECPoint(pointX, pointY);
}
ECPoint[] memory LHS = new ECPoint[](n);
for (uint256 i = 0; i < n**2; i += n) {
ECPoint[] memory accumulator = new ECPoint[](n);
// Scale the secret s by matrix values and store the result in accumulator.
for (uint256 j = 0; j < n; j++) {
(uint256 pointX, uint256 pointY) = mul(
matrix[j + i],
s[j].x,
s[j].y
);
accumulator[j] = ECPoint(pointX, pointY);
}
// Sum the scaled points in accumulator.
for (uint256 j = 0; j < n - 1; j++) {
(uint256 pointX, uint256 pointY) = add(
accumulator[j].x,
accumulator[j].y,
accumulator[j + 1].x,
accumulator[j + 1].y
);
accumulator[j + 1] = ECPoint(pointX, pointY);
}
LHS[i / n] = accumulator[n - 1];
}
for (uint256 i = 0; i < n; i++) {
if (LHS[i].x != oPoints[i].x || LHS[i].y != oPoints[i].y) {
return false;
}
}
return true;
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation 1/2 + 5/2 = 3/1
/// @dev The encoded elliptic curve points are derived from a specific curve
/// and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_one() public view returns (bool verified) {
ECPoint memory A = ECPoint(
10296210423881459776936787717049993391325552021605413991699412493845789633013,
16532533273964472383651167452754510965928658867757334670578445799571582196663
);
ECPoint memory B = ECPoint(
19032580475487806326057692075690361508625732333378927815997075982203596960703,
8731032473663224878408972807329716494736032188868213550913069617079965841757
);
return rationalAdd(A, B, 3, 1);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation 1/3 + 5/17 = 32/51
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_two() public view returns (bool verified) {
ECPoint memory A = ECPoint(
7882810270164319787005206832833610930431987920385435807716318376542052354560,
19432520343525233641062008984286830060574134258521690491420158809041132350596
);
ECPoint memory B = ECPoint(
1893605303548843236882693821488675454783355617924500803013052618837200072572,
297461610705396111198119190839735034439455529249955383133560737578468227923
);
return rationalAdd(A, B, 32, 51);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation: 14/81 + 100/17 = 8338/1377
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_14_81_100_17() public view returns (bool verified) {
// A + B = 8338/1377
ECPoint memory A = ZK.ECPoint(
6059911476566527530965034239846524990122245330194263914997526761532744231634,
13721567033381639103532740557447468494218343450727175543297520612075613285377
);
ECPoint memory B = ZK.ECPoint(
4537249267589406030402847773814443841095083767307214120027556859519700027635,
6555720194087405344443149354826472850823519691072213332671381160431053399053
);
verified = rationalAdd(A, B, 8338, 1377);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation: 27/87 + 14/55 = 2703/4785
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_27_87_14_55() public view returns (bool verified) {
// A + B = 2703/4785
ECPoint memory A = ZK.ECPoint(
19506447420044045799738838424700441161832083772081351318916203522001267888613,
13552163381824493875666862200703346962554769797562306859593383669399287958649
);
ECPoint memory B = ZK.ECPoint(
7904048952042424441180231335445154640772627221331527895114122319982232676644,
17999938464806390763215342179888442486254233558160274216338732141118370195263
);
verified = rationalAdd(A, B, 2703, 4785);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation: 24/101 + 13/84 = 3329/8484
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_24_101_13_84() public view returns (bool verified) {
// A + B = 3329/8484
ECPoint memory A = ZK.ECPoint(
21609611267819821097091407000833023013192116078526648682867104421353930967431,
14529147639020501668550656139784823440832093301758074861625878182518001705657
);
ECPoint memory B = ZK.ECPoint(
7905155136823485094344507662240796203906926223682905920845903297534434074870,
2950829865125047916469224800372691564946336798778976227848873848295736232479
);
verified = rationalAdd(A, B, 3329, 8484);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation: 7/7 + 30/64 = 658/448
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_7_7_30_64() public view returns (bool verified) {
// A + B = 658/448
ECPoint memory A = ZK.ECPoint(
1,
2
);
ECPoint memory B = ZK.ECPoint(
6290573467617727943666945771656006331323632615229368448662383123234933475026,
20979258315477581076918926805956021952855555508084809620272731353922196922188
);
verified = rationalAdd(A, B, 658, 448);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation: 11/79 + 53/7 = 4264/553
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_11_79_53_7() public view returns (bool verified) {
// A + B = 4264/553
ECPoint memory A = ZK.ECPoint(
8362541657398135634540148761367920273569033095276227688401806706951201962375,
18433587928520100464422842790707154047177700099010224210722540832535850376378
);
ECPoint memory B = ZK.ECPoint(
10476292557783178437740410430168169270874664726668692482550266441745375161247,
18465187058176758168705744906343708473721253587687112266608882778235466886538
);
verified = rationalAdd(A, B, 4264, 553);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation: 13/86 + 68/49 = 6485/4214
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_13_86_68_49() public view returns (bool verified) {
// A + B = 6485/4214
ECPoint memory A = ZK.ECPoint(
12630986734578811993799424168723045271278741809440737135672535403119446541470,
18063859613043377093247949619054987340491130148923828879145532733640531612330
);
ECPoint memory B = ZK.ECPoint(
2283060633015625117634273520139343045689179458025601797864842493439685135801,
15701445441307023696149768046883106829485200356718836509347319588956280773306
);
verified = rationalAdd(A, B, 6485, 4214);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation: 37/81 + 26/84 = 5214/6804
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_37_81_26_84() public view returns (bool verified) {
// A + B = 5214/6804
ECPoint memory A = ZK.ECPoint(
19951603733433961496675715127630436059204237421274097671357808927640927846112,
6230076022101806558277044623917608620776347164197501624215047813456547850535
);
ECPoint memory B = ZK.ECPoint(
14585486571397039593525108031117943608519994646974680392129131930348955505107,
9369756825339163595612523385711357274564697896488153169532810310866939945179
);
verified = rationalAdd(A, B, 5214, 6804);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation: 84/97 + 65/32 = 8993/3104
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_84_97_65_32() public view returns (bool verified) {
// A + B = 8993/3104
ECPoint memory A = ZK.ECPoint(
8941109698046494605596484783200629557898840538734920808403471741111129590268,
12476610269693618132425205323292054474805813335449939607937572979039313272687
);
ECPoint memory B = ZK.ECPoint(
5305294276663965794067337324983783366091462831452956553734441430091000723677,
843293992195325853095536449023587003921257041681131535740037591620276791484
);
verified = rationalAdd(A, B, 8993, 3104);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation: 76/39 + 39/31 = 3877/1209
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_76_39_39_31() public view returns (bool verified) {
// A + B = 3877/1209
ECPoint memory A = ZK.ECPoint(
14871560297043422046186124474194517992615602038525591354149856945501275840685,
10592191340856067051696093585991754998529041418188784331140133614417675873860
);
ECPoint memory B = ZK.ECPoint(
2992266688199039183823129421968662314872963098560700596314924747237781000924,
1400958684477096704160721966209407938352288493906284349834258314805522551774
);
verified = rationalAdd(A, B, 3877, 1209);
}
/// @notice Tests the rational addition of two elliptic curve encoded fractions.
/// In this case, we test the equation: 10/99 + 29/1 = 2881/99
/// @dev As before, the encoded elliptic curve points are derived from a specific
/// curve and must be decoded to get the real fractions.
/// @return verified Boolean result indicating if the addition is verified.
function test_10_99_29_1() public view returns (bool verified) {
// A + B = 2881/99
ECPoint memory A = ZK.ECPoint(
8418298297718117570748310012132820603669919637140583374585161137578423288439,
5951373021126777117951475101189663126522187083601053471974901732227791249677
);
ECPoint memory B = ZK.ECPoint(
9961482077405933653703920413004101065199760487639777914203301284159532567165,
5862436715964027487145075334372980905100234227901145792980374837265196864691
);
verified = rationalAdd(A, B, 2881, 99);
}
/// @notice Tests matrix-vector multiplication with elliptic curve encoded vectors.
/// We're verifying the claim: I know a secret, S, such that M x S = R.
/// Specifically, we're checking the equation using the matrices:
/// M = | 1 1 1 | S = | EC1 |
/// | 2 2 2 | | EC2 |
/// | 3 3 3 | | EC3 |
/// And the resulting vector R = | 4 |
/// | 8 |
/// | 12|
/// @dev The matrix and vectors are represented in terms of their encoded elliptic curve points.
/// The function leverages the matmul_nbyn function to perform the matrix multiplication.
/// @return verified Boolean result indicating if the matrix-vector multiplication is verified.
function test_matrix_multiply() public view returns (bool verified) {
uint256 n = 3;
uint256[] memory matrix = new uint256[](9);
matrix[0] = 1;
matrix[1] = 1;
matrix[2] = 1;
matrix[3] = 2;
matrix[4] = 2;
matrix[5] = 2;
matrix[6] = 3;
matrix[7] = 3;
matrix[8] = 3;
ECPoint[] memory secret = new ECPoint[](3);
secret[0] = ECPoint(1, 2);
secret[1] = ECPoint(
1368015179489954701390400359078579693043519447331113978918064868415326638035,
9918110051302171585080402603319702774565515993150576347155970296011118125764
);
secret[2] = ECPoint(1, 2);
uint256[] memory output = new uint256[](3);
output[0] = 4;
output[1] = 8;
output[2] = 12;
return matmul_nbyn(matrix, n, secret, output);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment