Tag: original

This is my first smart contract, and it's not finished yet, but the remaining parts are so complicated that I want to make sure I'm on the right track first. My concerns are:

• Is the missing division at line 117 an actual division or a modular multiplicative inverse? (BigNumber does not offer either bn_div Method is only for check I'm not sure what the discourse universe is for the elliptic curve.
• Should other operations be modular that are not modular?
• I've already moved the square root function and a coprimacy test out of the chain (hence the 7th through 10th parameters) submitPrime). Are there any other parts that can be easily removed from the chain and checked?
• The part of ellipticCurveCheck that I have written so far, does not use B at all. Should it?
• All BigNumber method names are qualified with the library name, which makes the code unwieldy. Does Solidity have an equivalent to Java? import static that I can use instead? Googling brings nothing to light.

NB: BigNumber is my personal fork, updated to work with Solidity 0.5.x and with tests running against 0.5.8.

pragma experimental ABIEncoderV2;
pragma solidity >=0.5.11 <0.6;

import "https://raw.githubusercontent.com/Pr0methean/solidity-BigNumber/2bddf04709f0e1ed649b37b5533264cef8c5cbfe/contracts/BigNumber.sol";
contract PrimeNumberBounty {
    BigNumber.instance ZERO = BigNumber._new(hex"00",false,false); 
    BigNumber.instance ONE = BigNumber._new(hex"01",false,false); 
    BigNumber.instance TWO = BigNumber._new(hex"02",false,false);
    BigNumber.instance THREE = BigNumber._new(hex"03",false,false);
    BigNumber.instance FOUR = BigNumber._new(hex"04",false,false); 
    BigNumber.instance TWENTY_SEVEN = BigNumber._new(hex"1B",false,false); 
    BigNumber.instance BOUNTY_THRESHOLD = BigNumber._new(hex"010000000000000000000000000000000000000000000000000000000000000000",false,false);
    mapping(bytes => BigNumber.instance) knownPrimes;
    uint256 constant public bountyAmount = 1e12 wei;
    address payable owner;

    constructor(bytes32) public {
        owner = msg.sender;
        knownPrimes(TWO.val) = TWO;
    }

    function selfDestruct() public {
        require(msg.sender == owner, 'Only the owner can call this');
        selfdestruct(owner);
    }

    function square(BigNumber.instance memory input) private view returns (BigNumber.instance memory) {
        return BigNumber.bn_mul(input, input);
    }

    function cube(BigNumber.instance memory input) private view returns (BigNumber.instance memory) {
        return BigNumber.bn_mul(square(input), input);
    }

    function mapContains(
            mapping(bytes => BigNumber.instance) storage haystack,
            BigNumber.instance memory needle)
            private view returns (bool) {
        return BigNumber.cmp(needle, haystack(needle.val), true) == 0;
    }

    function verifySquareRoot(BigNumber.instance memory input, BigNumber.instance memory sqrt) view private {
        require(BigNumber.cmp(square(sqrt), input, false) <= 0, 'Square root too high');
        BigNumber.instance memory sqrtPlusOne = BigNumber.prepare_add(sqrt, ONE);
        BigNumber.instance memory nextSquare = BigNumber.bn_mul(sqrtPlusOne, sqrtPlusOne);
        require(BigNumber.cmp(input, nextSquare, false) < 0, 'Square root too low');
    }

    /**
     * Assert that prime and 4A^3 + 27B^2 are coprime, using certificate method from
     * https://math.stackexchange.com/questions/2163034/proving-a-coprime-certificate-of-x-y.
     * Do not inline (causes a "Stack too deep" error).
     */
    function verifyCoprimality(
            BigNumber.instance memory prime,
            BigNumber.instance memory A,
            BigNumber.instance memory B,
            BigNumber.instance memory coprimeCertX,
            BigNumber.instance memory coprimeCertY) private view {
        require (BigNumber.cmp(ONE,
                BigNumber.prepare_add(
                        BigNumber.bn_mul(coprimeCertX, prime),
                        BigNumber.bn_mul(coprimeCertY, BigNumber.prepare_add(
                                BigNumber.bn_mul(FOUR, cube(A)),
                                BigNumber.bn_mul(TWENTY_SEVEN, square(B))))),
                true) == 0, 'Coprimality certificate verification failed');
    }

    /**
     * assert q > 2*prime^(1/4) + prime^(1/2) + 1
     * TODO: Does rounding the roots *before* adding affect this bounds check?
     */
    function boundsCheckQ(
            BigNumber.instance memory q,
            BigNumber.instance memory sqrtPrime,
            BigNumber.instance memory fourthRootPrime) private view {
        require (BigNumber.cmp(q,
                BigNumber.prepare_add(ONE, BigNumber.prepare_add(sqrtPrime, BigNumber.bn_mul(fourthRootPrime, TWO))), false)
                > 0, 'Requires q > 2 * ⁴√(prime) + √(prime) + 1');                
    }

    /**
     * assert My² = Mx³ + AMx + B
     */
    function verifyPointOnCurve(
            BigNumber.instance memory Mx,
            BigNumber.instance memory My,
            BigNumber.instance memory A,
            BigNumber.instance memory B) private view {
        BigNumber.instance memory expectedMySquared = BigNumber.prepare_add(B,
                BigNumber.bn_mul(Mx, BigNumber.prepare_add(A, square(Mx))));
        require (BigNumber.cmp(square(My), expectedMySquared, false) == 0, 'Requires My² = Mx³ + AMx + B');                
    }

    /**
     * Only works for curves with no term in y, xy or x²
     * 
     * Based on https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html (a1 = a2 = a3 = 0)
     */
    function ellipticCurvePointAdd(
            BigNumber.instance memory x1,
            BigNumber.instance memory y1,
            BigNumber.instance memory x2,
            BigNumber.instance memory y2,
            BigNumber.instance memory A) private view returns (BigNumber.instance memory x3, BigNumber.instance memory y3) {
        BigNumber.instance memory run = BigNumber.prepare_sub(x2, x1);
        BigNumber.instance memory rise;
        BigNumber.instance memory slope;
        if (BigNumber.cmp(ZERO, run, false) == 0) {
            require (BigNumber.cmp(y2, y1, false) == 0, 'Attempt to add two points with same x and different y in elliptic curve');
            run = BigNumber.bn_mul(y1, TWO);
            rise = BigNumber.prepare_add(A, BigNumber.bn_mul(square(x1), THREE));
        } else {
            rise = BigNumber.prepare_sub(y2, y1);
        }
        require(BigNumber.cmp(BigNumber.bn_mod(rise, run), ZERO, false) == 0, 'Elliptic curve cannot be computed in integer arithmetic');
        // TODO: Need on-chain division to set slope = rise / run!
        x3 = BigNumber.prepare_sub(BigNumber.prepare_sub(square(slope), x1), x2);
        y3 = BigNumber.prepare_sub(BigNumber.bn_mul(slope, BigNumber.prepare_sub(x1, x3)), y1);
    }

    function ellipticCurveCheck(
            BigNumber.instance memory Mx,
            BigNumber.instance memory My,
            BigNumber.instance memory A,
            BigNumber.instance memory B,
            BigNumber.instance memory q) private view returns (bool) {
        // Then M = (Mx, My) is a non-identity point on the elliptic curve y^2 = x^3 + Ax + B.
        // Let kM be M added to itself k times using
        // standard elliptic-curve addition. Then, if qM is the identity element I, then n is prime.
        BigNumber.instance memory qMx;
        BigNumber.instance memory qMy;
        BigNumber.instance memory Nx = Mx;
        BigNumber.instance memory Ny = My;
        BigNumber.instance memory remainingQ = q;
        while (BigNumber.cmp(remainingQ, ZERO, false) != 0) {
            if (BigNumber.is_odd(remainingQ) != 0) {
                (qMx, qMy) = ellipticCurvePointAdd(qMx, qMy, Nx, Ny, A);
            }
            remainingQ = BigNumber.right_shift(remainingQ, 1);
            (Nx, Ny) = ellipticCurvePointAdd(Nx, Ny, Nx, Ny, A);
        }
        // TODO: Determine if qMx, qMy is an identity element
        return false;
    }

    /**
     * Use this method to submit an Atkin–Goldwasser–Kilian–Morain certificate to be verified and added to the list.
     * A bounty of bountyAmount is paid to the sender if the prime is new to the list and sufficiently large. This type of
     * certificate uses an elliptic curve of the form y² = x³ + Ax + B.
     * 
     * Some additional off-chain-calculated parameters are required,
     * to limit the gas cost of verification. coprimeCertX and coprimeCertY are such that
     * coprimeCertX * prime + coprimeCertY * (4*A*A*A + 27*B*B) == 1.
     * 
     * @param prime the prime number to add to the list
     * @param Mx the x-coordinate of the certifying point
     * @param My the y-coordinate of the certifying point
     * @param A the elliptic curve's coefficient in x
     * @param B the elliptic curve's constant term
     * @param q a previously-submitted prime, or 2 for bootstrapping
     * @param sqrtPrime the square root of prime, rounded down
     * @param fourthRootPrime the fourth root of prime, rounded down
     * @param coprimeCertX term in the prime for the coprimality certificate
     * @param coprimeCertY term in 4A³ + 27B² for the coprimality certificate
     */
    function submitPrime(
            BigNumber.instance memory prime,
            BigNumber.instance memory Mx,
            BigNumber.instance memory My,
            BigNumber.instance memory A,
            BigNumber.instance memory B,
            BigNumber.instance memory q,
            BigNumber.instance memory sqrtPrime,
            BigNumber.instance memory fourthRootPrime,
            BigNumber.instance memory coprimeCertX,
            BigNumber.instance memory coprimeCertY) public {
        require (!prime.neg && !Mx.neg && !My.neg && !A.neg && !B.neg && !q.neg && !sqrtPrime.neg && !fourthRootPrime.neg,
            'Inputs prime,Mx,My,A,B,q must be non-negative');
        require (BigNumber.cmp(Mx, prime, false) < 0, 'Mx must be less than the prime');
        require (BigNumber.cmp(My, prime, false) < 0, 'My must be less than the prime');
        require (BigNumber.cmp(A, prime, false) < 0, 'A must be less than the prime');
        require (BigNumber.cmp(B, prime, false) < 0, 'B must be less than the prime');
        require (BigNumber.is_odd(prime) != 0, 'Not odd, and 2 is already claimed; therefore not prime');
        require (mapContains(knownPrimes, q), 'Submit a primality certificate for q first');
        require (!mapContains(knownPrimes, prime), 'Already claimed');
        verifySquareRoot(prime, sqrtPrime);
        verifySquareRoot(sqrtPrime, fourthRootPrime);
        verifyCoprimality(prime, A, B, coprimeCertX, coprimeCertY);
        boundsCheckQ(q, sqrtPrime, fourthRootPrime);
        verifyPointOnCurve(Mx, My, A, B);
        require (ellipticCurveCheck(Mx, My, A, B, q), 'Elliptic-curve test failed');
        knownPrimes(prime.val) = prime;
        if (BigNumber.cmp(prime, BOUNTY_THRESHOLD, false) > 0) {
            msg.sender.transfer(bountyAmount);
        }
    }
}
```