bitcoin-dev

Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

Original Postby Ethan Heilman

Posted on: April 29, 2024 00:30 UTC

In a groundbreaking discussion at the MIT DCI, an innovative approach was developed to implement Lamport signatures for Bitcoin transactions without the need for OP_CAT, a feature not currently available in Bitcoin's scripting language.

This new scheme allows for the signing of spending transactions directly, diverging from previous methods that sign arbitrary data or utilize different script functionalities such as tapscript. The foundation of this method lies in utilizing the variable length of ECDSA signatures in Bitcoin, where the signature size can act as a proxy for the transaction hash, facilitated by the observation that the length of the 's-value' in an ECDSA signature is influenced by the transaction hash for a fixed nonce and signing key.

The security of this novel scheme hinges on a specific setting of the nonce, k, to the multiplicative inverse of 2, which results in a significantly short 'r' value. This peculiar setup enables the identical 'r' values across multiple signatures to be validated based on their lengths using a simple size comparison operation within Bitcoin's scripting language. However, this method introduces a unique challenge; it requires a large number of signatures to achieve cryptographic security, with discussions suggesting around 1000 signatures might be needed to secure a transaction adequately.

Lamport signatures play a crucial role in this scheme by allowing the signing of the ECDSA signature lengths instead of the transaction hashes directly. This method significantly complicates an attacker's ability to forge a transaction, as they would need to generate a matching set of signature sizes in the correct order, a feat that becomes exponentially difficult with each additional signature required by the protocol.

Despite its innovative approach, the scheme has identified weaknesses, such as susceptibility to tuning attacks, where attackers could manipulate the signature length through different SIG_HASH flags, and mix and match attacks exploiting small variations in 'r' value lengths. Proposed improvements aim to mitigate these issues by increasing the diversity of signed ECDSA signature lengths and employing techniques like Winternitz One Time signatures to compress the length of signatures further, thereby enhancing overall security.

This exploratory work has sparked interest and feedback from several experts in the field, including contributions and critiques aimed at refining the approach. It represents a significant step toward leveraging existing Bitcoin script capabilities to implement more advanced cryptographic schemes, albeit with the caveat that its current form is more suited to academic exploration rather than practical application. The discussion reflects ongoing efforts to expand Bitcoin's utility through creative scripting and highlights the collaborative nature of innovation within the cryptocurrency space.