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: May 1, 2024 20:02 UTC

In a detailed discussion on the security implications and technical nuances of a proposed cryptographic scheme, several key points are raised regarding its viability and safety.

Initially, there's an agreement that once a transaction is broadcasted by an entity, say Alice, the possibility of double-spending that output is negated unless she compromises on security. This leads to a suggestion that unforgeability should be defined under the EU-CMA (Existential Unforgeability under Chosen Message Attack) model with a single signature constraint to enhance security measures.

Furthermore, the conversation touches upon mechanisms to adjust transaction fees without altering the signature hash, suggesting the use of SIGHASH flag options like "anyone can pay" or Child Pays For Parent (CPFP) as viable strategies. However, there's skepticism about the assumptions made regarding ECDSA (Elliptic Curve Digital Signature Algorithm) signatures within the discussed scheme. It's emphasized that expecting the scheme to be secure without a solid proof of security or at least some justification for its assumptions is unreasonable. The discussion also critiques the level of security provided, highlighting that 64 bits of security is insufficient, while noting that even 80 bits—equivalent to the collision resistance level of P2SH (Pay to Script Hash)—is probably too low for contemporary standards.

A significant concern raised is the ease with which the scheme could potentially be broken due to its reliance on certain signature properties. Specifically, it's pointed out that storage and look-up operations for this scheme are overly simplistic and do not require advanced techniques such as rainbow tables. Instead, once a 20 byte r-value is precomputed, it could be exploited across the board, significantly undermining the scheme's integrity. To put the computational effort into perspective, grinding such an r-value to achieve a 50% success rate in breaking these signatures would require 2^96 ECDSA queries, equating to the computational cost of mining over a quintillion Bitcoin blocks, thereby suggesting that investing resources in mining would be more profitable than attempting to exploit the scheme's vulnerabilities through r-value grinding.