Ethereum ecrecover compatibility with Secp256k1PrehashedKeccak256

[CedarMist]

Ethereum compatibility for the signing algorithms is very important for Sapphire.

This consists of:

• Converting signatures to an Ethereum compatible v, r, and s parameters
• Converting a generated P256k1 public key to an Ethereum address

To be acceptable there must be an example which performs a round-trip using ecrecover to verify a signature & public key generated by the Sapphire signing precompiles.

The signature format returned by Sapphire is 70 bytes DER encoded, see:

• https://github.com/oasisprotocol/oasis-sdk/blob/ca630e7d48986bd102d7aa477a48f8966a3d1d23/runtime-sdk/src/crypto/signature/secp256k1.rs#L136
• https://bitcoin.stackexchange.com/questions/58853/how-do-you-figure-out-the-r-and-s-out-of-a-signature-using-python

[CedarMist]

Converting compressed public key to ethereum address costs approx 5k gas with the following snippet, and a method to extract R &S params from DER encoded signature.

// SPDX-License-Identifier: Apache-2.0

pragma solidity ^0.8.0;

library EthereumUtils {
    uint256 constant k256_p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f;

    // (p+1)//4
    uint256 constant k256_p_plus_1_over_4 = 0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c;

    address constant PRECOMPILE_BIGMODEXP = address(0x5);

    function expmod(uint256 base, uint256 exponent, uint256 modulus)
        internal view
        returns (uint256 out)
    {
        (bool success, bytes memory result) = PRECOMPILE_BIGMODEXP.staticcall(abi.encodePacked(
            uint256(0x20),  // length of base
            uint256(0x20),  // length of exponent
            uint256(0x20),  // length of modulus
            base,
            exponent,
            modulus
        ));

        require( success );

        out = uint256(bytes32(result));
    }

    function k256_derive_y(uint8 _prefix, uint256 x)
        internal view
        returns (uint256 y)
    {
        require(_prefix == 0x02 || _prefix == 0x03);

        // x^3 + ax + b, where a=0, b=7
        y = addmod(
            mulmod(x, mulmod(x, x, k256_p), k256_p),
            7,
            k256_p
        );

        // find square root of quadratic residue
        y = expmod(y, k256_p_plus_1_over_4, k256_p);

        // negate y if indicated by sign bit
        if( (y + _prefix) % 2 != 0 )
        {
            y = k256_p - y;
        }
    }

    function k256_decompress(bytes memory pk)
        internal view
        returns (uint256 x, uint256 y)
    {
        require( pk.length == 33 );
        assembly {
            // skip 32 byte length prefix, plus one byte sign byte prefix
            x := mload(add(pk, 33))
        }
        y = k256_derive_y(uint8(pk[0]), x);
    }

    function ethereum_address(uint256 x, uint256 y)
        internal pure
        returns (address)
    {
        bytes32 digest = keccak256(abi.encodePacked(x, y));

        return address(uint160((uint256(digest)<<96) >> 96));
    }

    function k256_signature_der_split(bytes memory der)
        internal pure
        returns (bytes32 r, bytes32 s)
    {
        require( der.length == 70 );
        require( der[0] == 0x30 );
        require( der[1] == 0x44 );
        require( der[2] == 0x02 );
        require( der[3] == 0x20 );
        require( der[0x20+4] == 0x02 );
        require( der[0x20+5] == 0x20 );
        assembly {
            r := mload(add(der, 36))    // skip 32 bytes `der` length prefix
            s := mload(add(der, 70))
        }
        // Example of DER encoded signature
        // 0x3044022061676dce86847b7d79cc3740b71a651a3fef1edbb5b1d3b69c873ecca18fec31022074ca0050787a6980376e9d4f1bfc557bc3c67e6d565397cc862480d06c54ad63
        // 30
        // 44
        // 02
        // 20
        // 61676dce86847b7d79cc3740b71a651a3fef1edbb5b1d3b69c873ecca18fec31 = R
        // 02
        // 20
        // 74ca0050787a6980376e9d4f1bfc557bc3c67e6d565397cc862480d06c54ad63 = S
    }
}

[CedarMist]

Turns out ASN.1 DER encoding is a little derpier than I expected, the variable length nature means field elements have their leading zeros removed and thus DER encoded signatures for k256 can be anywhere between 8 and 72 bytes. Sometimes it adds a leading zero too... presumably because the high bit is set to distinguish it from a signed value?

So, high probability of either R or S being 32-33 bytes, but also chances of them being 31 bytes or (with significantly decreasing probability) 30, 29 bytes etc. An example of a DER encoded signature of length 68 bytes:

0x3042022062fa7911022e734f7a40b6b545a2fc47923144ccffb9e2116cc8081d05c9ac56021e226163d65cde79b1e62c010f998890f25f1dc69db714b4a18a810ce32752

Which has 32 byte r and 30 byte s parameter

This means the k256_signature_der_split needs to handle variable lengths correctly otherwise it may fail intermittently with simpler checks, and so will be slightly more complex than the code above.

The good news is I've tested generate & verify signatures end to end through ecrecover with derived ethereum address from the public key and it works, so no blockers.