Efficient elliptic curve point addition and multiplication in scrypt

We propose a novel and effective method , Used to calculate point addition and scalar multiplication on elliptic curve in bitcoin script . For points add , We will surpass 1MB Script size reduced to ~400 byte .

Elliptic Curve

Point addition

For each i, Each point P_i By two coordinates (x_i, y_j) Express . For calculation P₃ = P₁ + P₂, We use the following formula

Add some formula

If P₁ != P₂,

otherwise

A simple implementation requires computing the reciprocal of the modulus , Apply extended Euclidean algorithm . However , This will cause the script size to be too large , Because the exact number of cycles in the algorithm is unknown in advance , And must use a large conservative upper limit .

Efficient solutions

We don't just add points , But by passing the expected point in the unlock script P₃ To solve this problem . We only verify in the script P₃ = P₁ + P₂. To avoid modulo reciprocal in verification , We convert the formula into the following equivalent form .

When P₁ != P₂

When P₁ == P₂

And P₃ equally ,λ It is also pre calculated under the chain , And pass... In the unlock script , As shown below . This produces a very compact script , The size is only ~400B.

    static function isSumHelper(Point p1, Point p2, int lambda, Point p) : bool {
    
        // check lambda is indeed gradient
        bool lambdaOK = (p1 == p2) ?
            (2 * lambda * p1.y - 3 * p1.x * p1.x) % P == 0 :
            (lambda * (p2.x - p1.x) - (p2.y - p1.y)) % P == 0;
        // also check p = p1 + p2
        return lambdaOK && (lambda * lambda - p1.x - p2.x - p.x) % P == 0 && 
            (lambda * (p1.x - p.x) - p1.y - p.y) % P == 0;
    }

    // return true if lambda is the gradient of the line between p1 and p2
    // and p = p1 + p2 
    static function isSum(Point p1, Point p2, int lambda, Point p) : bool {
    
        // special handling of point ZERO
        bool ret = p1 == ZERO ? p2 == p : (p2 == ZERO ? p1 == p : (p1.x == p2.x && (p1.y + p2.y) % P == 0) ? p == ZERO : true);

        return ret && isSumHelper(p1, p2, lambda, p);
    }

Point plus verification ## Dot multiplication

x * P = (x0 + x1 * 2 + x2 * 4 + x3 * 8 + … + x255 * 2²⁵⁵) * P
= x0 * P + x1 * (2P) + x2 * (4P) + x3 * (8P) + … + x255 * (2²⁵⁵P)

x0, x1, x2, …, x255 It's scalar x The bit of "s" means , From least significant bit to most significant bit . We calculate in advance 2P, 4P, 8P, …, 2²⁵⁵P Chain them down and pass them to the unlock script , These are verified in the locking script , As shown in the following paragraph 21-24 Line .

 // return true iff p * x == r
    static function isMul(Point p, int x, Point r, Point[EC.N] pMultiples, Point[EC.N] qs, int[EC.N1] lambdas1, int[EC.N1] lambdas2) : bool {
    

        // validate pMultiples = [p, 2p, 4p, 8p, ...]
        loop (N) : i {
    
            require(i == 0 ? pMultiples[i] == p : isSum(pMultiples[i - 1], pMultiples[i - 1], lambdas1[i - 1], pMultiples[i]));
        }

        // // x * p = x0 * p + x1 *(2p) + x2 * (4p) + x3 * (8p) + ...
        // // xi is the i-th bit of x
        Point P0 = ZERO;
        loop (N) : i {
    
            Point P = x % 2 ? pMultiples[i] : ZERO;

            // right shift by 1
            x /= 2;

            if (i == 0) {
    
                P0 = P;
            } else if (i == 1) {
    
                // first
                require(isSum(P0, P, lambdas2[i - 1], qs[i - 1]));
            } else {
    
                // rest
                require(isSum(qs[i - 1], P, lambdas2[i - 1], i < N1 ? qs[i] : r));
            }
        }

        return true;
    }

Dot multiplication verification

thank

This article is based on Craig Wright and Owen Vaughan The job of , As well as from nChain Of Enrique Larraia and Owen Vaughan Valuable feedback from .