1
\$\begingroup\$

This is my first smart contract, and it isn't finished yet, but the remaining bits are complicated enough that I'd like to make sure I'm on the right track first. My concerns are:

  • At line 117, is the missing division an actual division or a modular multiplicative inverse? (BigNumber provides neither; the bn_div method is just for verifying a division.) I'm not clear on what the universe of discourse is for the elliptic curve.
  • Should any other operations be modular that aren't?
  • I've already moved the square-root function and a coprimality test off-chain (hence the 7th through 10th parameters to submitPrime). Any other parts that can easily be moved off-chain and verified?
  • The part of ellipticCurveCheck that I've written so far doesn't use B at all. Should it?
  • All the BigNumber method names are qualified with the library name, which makes the code kind of unwieldy. Does Solidity have an equivalent of Java's import static that I can use instead? Googling doesn't turn anything up.

NB: BigNumber is my personal fork, updated to work with Solidity 0.5.x and with the tests run 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);
        }
    }

    function donate() payable {}
}
```
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.