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=

.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": {}
        }
    ]
}

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);
    }
}