lip-0062.md

LIP: 0062
Title: Use pre-hashing for signatures
Author: Maxime Gagnebin <[email protected]>
Discussions-To: https://research.lisk.com/t/use-pre-hashing-for-signatures/329
Status: Active
Type: Standards Track
Created: 2022-02-11
Updated: 2024-01-04
Requires: 0037

Abstract

This LIP introduces pre-hashing for signatures in Lisk, this includes transactions, block headers and certificate signatures. This allows signing to be performed on memory limited devices such as hardware wallets. Additionally, it replaces a signature scheme for some offchain signatures that use double pre-hashing by single pre-hashing.

Copyright

This LIP is licensed under the Creative Commons Zero 1.0 Universal.

Motivation

Introducing memory efficient signing allows all objects used in the Lisk protocol to be signed on devices with limited memory. Most of the current transactions have a small size and can be signed on existing devices. However, new transactions implemented in the interoperability module, or transactions implemented in decentralized applications are likely to be too large to be signed directly on such devices. This argument was overlooked in the past which led to the pre-hashing step being removed in LIP 0008.

With the current proposal, signatures are computed against the hash of the message to be signed and hence always computed for a byte string of small constant size.

Lisk Elements currently contains another Ed25519 signature scheme that uses double pre-hashing. This scheme is only used for non-protocol related offchain signatures. More precisely the sign message feature in Lisk Desktop is using it, and it is implemented in Lisk Commander without a concrete use case. The usage of double pre-hashing next to single pre-hashing yields a small risk for collisions. Notice that the existing double pre-hashing signature scheme prepends the tag TAG = 0x15 + b"Lisk Signed Message:\n" and the length of the message to the message prior to hashing. If one finds messages m1 and m2, a message tag MST according to LIP 0037 and a chain ID chainID such that

sha256(TAG + len(m1) + m1) = MST + chainID + m2

then hashing and signing the left side with Ed25519 would result in a signature for m1 under the double pre-hashing scheme. Hashing and signing the right side with Ed25519 would result in a signature for m2 under the single pre-hashing scheme. Hence, if an attacker finds such a collision and convinces a user to sign m2 with the single pre-hashing scheme, then the attacker has also a signature of the user for m1 for the double pre-hashing scheme. Therefore, we want to replace the double pre-hashing scheme with a single pre-hashing scheme.

Rationale

Choice of Hash Function

Hashing before signing is a common practice and different protocols use different hash functions for this task. For the Lisk protocol, the natural choice of hash function is SHA-256. This function is used in multiple other parts of the protocol and hence it makes sense to not expose the protocol to another hash function.

Introduction of another hash function to the Lisk protocol was suggested in LIP 0010, but was later withdrawn as SHA-256 is widely used and can be considered secure.

On Removing Pre-hashing in LIP 0008

LIP 0008 removed the pre-hashing step from the Lisk signing protocol. This was mainly done as this step was deemed unnecessary and removing it could improve the theoretical security of the signing process. However this is not reflected by a practical improvement in protocol security as the SHA-256 hash function is considered collision resistant and secure. This hash function is used in several critical parts of many applications, including Lisk, and any future findings that SHA-256 is insecure would require changing the protocol throughout.

Signing Non-Protocol Messages

When signing a message with the sign message feature in Lisk Desktop, then the message is typically independet of any chain. Hence, no chain ID needs to be added to the message prior to hashing or signing. Therefore, we add an extra signing function for this use case that works the same as the regular Ed25519 signature scheme with single pre-hashing but omits a chain ID. This function should be used in Lisk Desktop for the sign message feature. The double pre-hashing scheme used in Lisk Commander should simply be removed without replacement as there is no use case for it.

Specification

Signing and Verifying with Ed25519

The Ed25519 signature for a binary message message and a secret key sk is generated by signEd25519(sk, tag, chainID, message) as defined below. tag must be the correct message tag for message as defined in LIP 0037, and chainID the correct chain ID for the chain. The resulting signature signature in combination with the message message and the matching public key pk is verified by verifyEd25519(pk, tag, chainID, message, signature).

def signEd25519(sk: bytes, tag: bytes, chainID: bytes, message: bytes) -> bytes:
    taggedMessage = tag + chainID + message
    hashedMessage = sha256(taggedMessage)
    return Sign(sk, hashedMessage)

def verifyEd25519(pk: bytes, tag: bytes, chainID: bytes, message: bytes, signature: bytes) -> bool:
    taggedMessage = tag + chainID + message
    hashedMessage = sha256(taggedMessage)
    return Verify(pk, hashedMessage, signature)

Here, Sign and Verify are the signing and verifying functions as specified in RFC 8032.

The signEd25519 and verifyEd25519 functions defined in LIP 0037 are superseded by the functions defined in this LIP.

Signing Non-Protocol Messages with Ed25519

A non-protocol related message message can be signed by the function signNonProtocolEd25519. The resulting signature can be verified by verifyNonProtocolEd25519. This scheme should be used for the sign message feature in Lisk Desktop. Note that the tag MESSAGE_TAG_NON_PROTOCOL_MESSAGE is defined in LIP 0037.

def signNonProtocolEd25519(sk: bytes, message: bytes) -> bytes:
    taggedMessage = MESSAGE_TAG_NON_PROTOCOL_MESSAGE + message
    hashedMessage = sha256(taggedMessage)
    return Sign(sk, hashedMessage)

def verifyNonProtocolEd25519(pk: bytes, message: bytes, signature: bytes) -> bool:
    taggedMessage = MESSAGE_TAG_NON_PROTOCOL_MESSAGE + message
    hashedMessage = sha256(taggedMessage)
    return Verify(pk, hashedMessage, signature)

Signing and Verifying with BLS

def signBLS(sk: bytes, tag: bytes, chainID: bytes, message: bytes) -> bytes:
    taggedMessage = tag + chainID + message
    hashedMessage = sha256(taggedMessage)
    return CoreSign(sk, hashedMessage)

def verifyBLS(pk: bytes, tag: bytes, chainID: bytes, message: bytes, signature: bytes) -> bool:
    taggedMessage = tag + chainID + message
    hashedMessage = sha256(taggedMessage)
    return CoreVerify(pk, hashedMessage, signature) == VALID

def verifyAggSig(keysList: list[bytes], aggregationBits: bytes, signature: bytes, tag: bytes, chainID: bytes, message: bytes) -> bool:
    taggedMessage = tagMessage(tag, chainID, message)
    hashedMessage = sha256(taggedMessage)
    keys = []
    if len(aggregationBits) != ceiling(len(keysList), 8):
        return False
    # ensure that the bits not corresponding to a key in keysList are all zero
    if len(keysList) % 8 != 0 and not (aggregationBits[-1]  >> (len(keysList) % 8) == 0):
        return False
    for i in range(8 * len(aggregationBits)):
        # if i-th bit of aggregationBits == 1
        if (aggregationBits[i // 8] >> (i % 8)) & 1:
            keys.append(keysList[i])
    return FastAggregateVerify(keys, hashedMessage, signature) == VALID

def verifyWeightedAggSig(keysList: list[bytes], aggregationBits: bytes, signature: bytes, tag: bytes, chainID: bytes, weights: list[int], threshold: int, message: bytes) -> bool:
    taggedMessage = tagMessage(tag, chainID, message)
    hashedMessage = sha256(taggedMessage)
    keys = []
    weightSum = 0
    if len(aggregationBits) != ceiling(len(keysList), 8):
        return False
    # ensure that the bits not corresponding to a key in keysList are all zero
    if len(keysList) % 8 != 0 and not (aggregationBits[-1]  >> (len(keysList) % 8) == 0):
        return False
    for i in range(8 * len(aggregationBits)):
        # if i-th bit of aggregationBits == 1
        if (aggregationBits[i // 8] >> (i % 8)) & 1:
            keys.append(keysList[i])
            weightSum += weights[i]
    if weightSum < threshold:
        return False
    return FastAggregateVerify(keys, hashedMessage, signature) == VALID

Here, we use the auxiliary function ceiling defined by

def ceiling(x: int, y: int) -> int:
    if y == 0:
        raise Exception('Cannot divide by 0.')
    return (x+y-1) // y

For the BLS signature scheme used in Lisk, CoreSign and CoreVerify are the signing and verifying functions, while FastAggregateVerify is the function used to verify aggregated BLS signatures as specified in BLS Signatures draft-irtf-cfrg-bls-signature-04.

The signBLS, verifyBLS, verifyAggSig, and verifyWeightedAggSig functions defined in LIP 0038 are superseded by the functions defined in this LIP.

Reference Implementation

Create signBLS, verifyBLS, createAggSig, verifyAggSig and verifyWeightedAggSig function

Backwards Compatibility

This LIP results in a hard fork as nodes following the proposed protocol will reject signatures according to the previous protocol, and nodes following the previous protocol will reject signatures according to the proposed protocol.

Appendix

Test Vectors

The following tests supersede the corresponding tests given in LIP 0038.

signBLS

sk = 0x263dbd792f5b1be47ed85f8938c0f29586af0d3ac7b977f21c278fe1462040e3
tag = b"LSK_TX_"
chainID = 0x00000000
message = 0xbeaf
assert signBLS(sk, tag, chainID, message) == 0x80c3da661b5bb80bb841367255f7b087b969c075661895b7ac8b74b72360be54693b3485eff7d816924517a21ef1c3a30a8f9402572d5a63a7ff2f71ca6929a8c3d7f75fd72edd1aa478ecc09966a133e829600f0111a1e40bbe35db61e8c689

verifyBLS

pk = 0xa491d1b0ecd9bb917989f0e74f0dea0422eac4a873e5e2644f368dffb9a6e20fd6e10c1b77654d067c0618f6e5a7f79a
tag = b"LSK_TX_"
chainID = 0x00000000
message = 0xbeaf
sig = 0x80c3da661b5bb80bb841367255f7b087b969c075661895b7ac8b74b72360be54693b3485eff7d816924517a21ef1c3a30a8f9402572d5a63a7ff2f71ca6929a8c3d7f75fd72edd1aa478ecc09966a133e829600f0111a1e40bbe35db61e8c689
assert verifyBLS(pk, tag, chainID, message, sig)

verifyAggSig

We use the following list of keys for the test below:

KEYS_LIST = [
  0x9998f02d85e3851a430333350ed6cc1c0afbd72ee52cf8ad2f23d394f3937bfdc92e056dce713b9d45dac7b106d82883,
  0xa491d1b0ecd9bb917989f0e74f0dea0422eac4a873e5e2644f368dffb9a6e20fd6e10c1b77654d067c0618f6e5a7f79a,
  0x8f116ba0b305fb734405dd0968e255ad06a34d0cacfeece4c320502824da4a2ff90a978bfcffa1206ecae27f62bac645,
  0xb301803f8b5ac4a1133581fc676dfedc60d891dd5fa99028805e5ea5b08d3491af75d0707adab3b70c6a6a580217bf81,
  0xb53d21a4cfd562c469cc81514d4ce5a6b577d8403d32a394dc265dd190b47fa9f829fdd7963afdf972e5e77854051f6f,
  0xa6b6a639f7fa0b64ad3a93be965e9cc34e1d9d0f0427c14c38fc80934a937c5fa745a3cb285f64d4d1c06d0825504488,
  0xa4aa20eedb651b7855ee38ce16f59a263346fc383dd9603ac219aaed166ebfe09d460ebbbb7ea89e71c70d48e06efd1a,
  0x95324a8c4a890e8c1e83c96c6c639254937c9c9cee789556606744b07e98292e292c8c150efd9506b0b5547fea3fdf9f,
  0xa424801164381bbfc0b20c1807ce43a12bb012e47deb11b2a3a273dd82ca9fa6364e2f2b8d6c89bc576da89a04d5118f
]

aggregationBits = 0x4001
signature = 0xb379644423397a99dedea08df6698ef15cb170a93d16ba3d96dbf65ae54b397362333561487b22a105e7e0d471802d5600391d8097154bd86656d323cb62975d0b768c8bec9b1193b482e0210d55dd81a5c36ae1595f3b98f72e66f0d71ffef4
tag = b"LSK_CE_"
chainID = 0x00000000
message = 0xbeaf
verifyAggSig(KEYS_LIST, aggregationBits, signature, tag, chainID, message) == True