BorromeanRing.sol

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;

import "https://github.com/witnet/elliptic-curve-solidity/blob/master/contracts/EllipticCurve.sol";

library BorromeanRing {

    // Secp256k1 curve constants
    uint256 public constant GX = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798;
    uint256 public constant GY = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8;
    uint256 public constant AA = 0;
    uint256 public constant BB = 7;
    uint256 public constant PP = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F;

    struct Signature {
        uint256 e0;
        bytes[][] P;
        uint256[][] s;
    }

    function validate(bytes calldata m, Signature calldata sig) internal pure returns (bool) {
        uint256 M = uint256(keccak256(abi.encode(m, sig.P))) % PP;
        bytes[] memory last_Rs = new bytes[](sig.P.length);

        for (uint8 i = 0; i < sig.P.length; i++) {
            uint256 e = sig.e0;
            for (uint8 j = 0; j < sig.P[i].length; j++) {
                // Decode and validate P
                (uint256 Px, uint256 Py) = abi.decode(sig.P[i][j], (uint256, uint256));
                require(EllipticCurve.isOnCurve(Px, Py, AA, BB, PP));

                // R = sG + eP
                (uint256 sGx, uint256 sGy) = EllipticCurve.ecMul(sig.s[i][j], GX, GY, AA, PP);
                (uint256 ePx, uint256 ePy) = EllipticCurve.ecMul(e, Px, Py, AA, PP);
                (uint256 Rx, uint256 Ry) = EllipticCurve.ecAdd(sGx, sGy, ePx, ePy, AA, PP);
                bytes memory R = abi.encode(Rx, Ry);

                if (i + 1 == sig.P.length) {
                    last_Rs[i] = R;
                }
                else {
                    // e = H(M, R, i, j)
                    e = uint256(keccak256(abi.encode(M, R, i, j))) % PP;
                }                
            }
        }

        // e'0 == e0 ?
        return sig.e0 == (uint256(keccak256(abi.encode(last_Rs))) % PP);
    }
}