📖 This EIP is in the review stage. It is subject to changes and feedback is appreciated.

EIP-2098: Compact Signature Representation Source

AuthorRichard Moore, Nick Johnson
Discussions-Tohttps://github.com/ethereum/EIPs/issues/2440
StatusReview
TypeInformational
Created2019-03-14
Requires 2

Table of Contents

Simple Summary

This proposal describes a compact representation of an Ethereum Signature.

Abstract

The secp256k1 curve permits the computation of the public key of signed digest when coupled with a signature, which is used implicitly to establish the origin of a transaction from an Externally Owned Account as well as on-chain in EVM contracts for example, in meta-transactions and multi-sig contracts.

Currently signatures require 65 bytes to represent, which when aligned to 256-bit words, requires 96 bytes (with 31 zero bytes injected). The yParity in RLP-encoded transactions also require (on average) 1.5 bytes. With compact signatures, this can be reduced to 64 bytes, which remains 64 bytes when word-aligned, and in the case of RLP-encoded transactions saves the 1.5 bytes required for the yParity.

Motivation

The motivations for a compact representation are to simplify handling transactions in client code, reduce gas costs and reduce transaction sizes.

Specification

A secp256k1 signature is made up of 3 parameters, r, s and yParity. The r represents the x component on the curve (from which the y can be computed), and the s represents the challenge solution for signing by a private key. Due to the symmetric nature of an elliptic curve, a yParity is required, which indicates which of the 2 possible solutions was intended, by indicating its parity (odd-ness).

Two key observations are required to create a compact representation.

First, the yParity parameter is always either 0 or 1 (canonically the values used have been 27 and 28, as these values didn’t collide with other binary prefixes used in Bitcoin).

Second, the top bit of the s parameters is always 0, due to the use of canonical signatures which flip the solution parity to prevent negative values, which was introduced as a constraint in Homestead.

So, we can hijack the top bit in the s parameter to store the value of yParity, resulting in:

[256-bit r value][1-bit yParity value][255-bit s value]

Example Implementation In Python 

# Assume yParity is 0 or 1, normalized from the canonical 27 or 28
def to_compact(r, s, yParity):
    return {
        "r": r,
        "yParityAndS": (yParity << 255) | s
    }

def to_canonical(r, yParityAndS):
    return {
        "r": r,
        "s": yParityAndS & ((1 << 255) - 1),
        "yParity": (yParityAndS >> 255)
    }

Rationale

The compact representation proposed is simple to both compose and decompose in clients and in Solidity, so that it can be easily (and intuitively) supported, while reducing transaction sizes and gas costs.

Backwards Compatibility

The Compact Representation does not collide with canonical signature as it uses 2 parameters (r, yParityAndS) and is 64 bytes long while canonical signatures involve 3 separate parameters (r, s, yParity) and are 65 bytes long.

Test Vectors 

Private Key: 0x1234567890123456789012345678901234567890123456789012345678901234
Message: "Hello World"
Signature:
  r:  0x68a020a209d3d56c46f38cc50a33f704f4a9a10a59377f8dd762ac66910e9b90
  s:  0x7e865ad05c4035ab5792787d4a0297a43617ae897930a6fe4d822b8faea52064
  v:  27
Compact Signature:
  r:           0x68a020a209d3d56c46f38cc50a33f704f4a9a10a59377f8dd762ac66910e9b90
  yParityAndS: 0x7e865ad05c4035ab5792787d4a0297a43617ae897930a6fe4d822b8faea52064

Private Key: 0x1234567890123456789012345678901234567890123456789012345678901234
Message: "It's a small(er) world"
Signature:
  r:  0x9328da16089fcba9bececa81663203989f2df5fe1faa6291a45381c81bd17f76
  s:  0x139c6d6b623b42da56557e5e734a43dc83345ddfadec52cbe24d0cc64f550793
  v:  28
Compact Signature:
  r:           0x9328da16089fcba9bececa81663203989f2df5fe1faa6291a45381c81bd17f76
  yParityAndS: 0x939c6d6b623b42da56557e5e734a43dc83345ddfadec52cbe24d0cc64f550793

Gas Analysis

Solidity

// See: https://ropsten.etherscan.io/address/0xce826fbc499e3723df5668ea90a4bc51aeca13b8

pragma solidity 0.5.6;

contract TestCompact {
    address _lastAddr;
    
    function recover(bytes32 hash, uint8 v, bytes32 r, bytes32 s) public returns (address) {
         _lastAddr = ecrecover(hash, v, r, s);
    }

    function recoverCompact(bytes32 hash, bytes32 r, bytes32 vs) public returns (address) {
        bytes32 s = vs & 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff;
        uint8 v = 27 + uint8(uint256(vs) >> 255);
        _lastAddr = ecrecover(hash, v, r, s);
    }
    
    function lastAddr() public view returns (address) {
        return _lastAddr;
    }
}

JavaScript

let address = "0xcE826fbC499e3723DF5668Ea90a4BC51AeCa13b8";
let abi = [
  'function recover(bytes32 hash, uint8 v, bytes32 r, bytes32 s) public returns (address)',
  'function recoverCompact(bytes32 hash, bytes32 r, bytes32 vs) public returns (address)',
  'function lastAddr() public view returns (address)'
];
let wallet = Wallet.fromMnemonic("relief cousin sorry cabin burst frog slush flavor pitch tragic hip disagree").connect(provider);

let hash = "0x6ac9e083f46825a57816e023ae641ee45ac9b82cc2c370c10ec1ef4c835fa182";
let sig = wallet.signingKey.signDigest(hash)

let contract = new Contract(address, abi, wallet);
(async function() {
    let tx, receipt;

    console.log("Canonical:");
    tx = await contract.recover(hash, sig.v, sig.r, sig.s);
    console.log("  Hash:    ", tx.hash);
    console.log("  Data:    ", tx.data);
    console.log("  Length:  ", utils.hexDataLength(tx.data));  
    receipt = await tx.wait();
    console.log("  Gas Used:", receipt.gasUsed.toString());

    console.log("Compact:");
    tx = await contract.recoverCompact(hash, sig.r, sig._vs);
    console.log("  Hash:    ", tx.hash);
    console.log("  Data:    ", tx.data);
    console.log("  Length:  ", utils.hexDataLength(tx.data));
    receipt = await tx.wait();
    console.log("  Gas Used:", receipt.gasUsed.toString());
})();

Result

/home/ricmoo> ethers --network ropsten run test.js 
Canonical:
  Hash:     0x3280985011d2f25e76141681e865216e796cf065880eb9dd1f8221f3243028d2
  Data:     0xc2bf17b06ac9e083f46825a57816e023ae641ee45ac9b82cc2c370c10ec1ef4c835fa182000000000000000000000000000000000000000000000000000000000000001be95b1a8633ee7ff851f68cf4303030b1e2596d686cafd9803cef74919a9139291c492d05696da754cf342bec961d00d9f7dfac3ab90b1e9352177c7b9bfa2a5d
  Length:   132
  Gas Used: 37541
Compact:
  Hash:     0x513bd8bd8710a84903235ca60591fc60f2f3db524d14cc1b6874edc628512176
  Data:     0x1230abb66ac9e083f46825a57816e023ae641ee45ac9b82cc2c370c10ec1ef4c835fa182e95b1a8633ee7ff851f68cf4303030b1e2596d686cafd9803cef74919a9139291c492d05696da754cf342bec961d00d9f7dfac3ab90b1e9352177c7b9bfa2a5d
  Length:   100
  Gas Used: 37329

Implementations

The ethers.js library supports this in v5 as an unofficial property of split signatures (i.e. sig._vs), but should be considered an internal property that may change at discretion of the community and any changes to this EIP.

Acknowledgments

Copyright and related rights waived via CC0.

Citation

Please cite this document as:

Richard Moore, Nick Johnson, "EIP-2098: Compact Signature Representation," Ethereum Improvement Proposals, no. 2098, March 2019. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2098.