ECDSA signature verification in crypt

We use sCrypt The language implements ECDSA Signature verification algorithm . It can verify whether any message is signed by the private key corresponding to the given public key , and OP_CHECKSIG The signature can only be verified if the message is a currently spent transaction ¹. It's amazing , There is no need to introduce any new opcodes . And in the BCH On , Additional opcodes need to be introduced OP_DATASIGVERIFY（ also called OP_CHECKDATASIG）） Complete the same function .

Elliptic curve digital signature algorithm (ECDSA)

ECDSA It is an algorithm used for signature generation and verification in bitcoin . The validation algorithms are listed below .

Realization

As shown below , We have implemented the algorithm , Use the elliptic curve library we released earlier .

First , We need to start with DER Format encoded signature extraction r and s component . Because they are big end codes , We must convert to Small end coding , This is where the data Script / sCrypt How to code in .

In search of r and s after , We just need to run the standard ECDSA Verification algorithm .

import "ec.scrypt";
import "util.scrypt";

struct RSPair {
    
    int r;
    int s;
}

// ECDSA signatures verification for secp256k1, for arbitrary message @msg
contract ECDSA {
    
    public function verify(Sig sig, PubKey pubKey, bytes msg, int invS, Point P, int lambda, Point U1, PointMulAux u1Aux, Point U2, PointMulAux u2Aux) {
    

        // extract (r, s) from sig
        RSPair rs = parseDERSig(sig);
        int r = rs.r;
        int s = rs.s;
        // within range
        require(r >= 1 && r < EC.n);
        require(s >= 1 && s < EC.n);

        // verify invS
        require((s * invS) % EC.n == 1);
        
        int e = unpack(sha256(msg));
        int u1 = (e * invS) % EC.n;
        int u2 = (r * invS) % EC.n;

        // U1 = u1 * G
        require(EC.isMul(EC.G, u1, U1, u1Aux));

        Point Q = pubKey2Point(pubKey);
        // U2 = u2 * Q
        require(EC.isMul(Q, u2, U2, u2Aux));

        // P == U1 + U2
        require(EC.isSum(U1, U2, lambda, P));
        // cannot be identify
        require(P != EC.ZERO);

        require((P.x - r) % EC.n == 0);
    }

    // parse signature in DER format to get (r, s) pair
    static function parseDERSig(Sig sig) : RSPair {
    
        int rLen = unpack(sig[3 : 4]);
        int r = fromBESigned(sig[4 : 4 + rLen]);

        int sLen = unpack(sig[6 + rLen : 7 + rLen]);
        int s = fromBESigned(sig[7 + rLen : 7 + rLen + sLen]);

        return {
     r , s };
    }

    // r & s are signed big endian
    static function fromBESigned(bytes b) : int {
    
        // convert big-endian to little-endian: either 32 or 33 bytes
        bytes bLE = len(b) == 32 ? reverseBytes(b, 32) : reverseBytes(b, 33);
        return unpack(bLE);
    }

    // convert public key to a point, assuming it's uncompressed
    static function pubKey2Point(PubKey pubKey) : Point {
    
        require(pubKey[: 1] == b'04');
        return {
     unpack(pubKey[1 : 33]), unpack(pubKey[33 : 65]) };
    }
}

ECDSA contract

[1] More precisely , It's for sighash Verify the signature .