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 30, 2024 20:43 UTC

The proposed redesign focuses on optimizing the scheme used in cryptographic operations, particularly in reducing the number of opcodes required for validating signatures.

By altering the traditional method where each ECDSA signature's length is signed individually, the new approach suggests having a single Lamport (or WOTS) signature to sign a vector indicating the positions of ECDSA signatures of a specific shorter length. This adjustment significantly decreases opcode usage as it eliminates the need to check every signature length individually and allows for the omission of unchecked signatures, streamlining the process.

Alice benefits from this system because she can determine the placement of these shorter ECDSA signatures post-generation, leveraging a combinatorial advantage. Specifically, if the total number of signatures is denoted by N and the count of shorter signatures by M, Alice's advantage is quantified as the combination of N taken M at a time. For example, with both N and M equal to 10, Alice would need to exert a computational effort equivalent to 2^(8*10), assuming the probability of generating a 58-byte ECDSA signature is 1/256 or 1/(2^8). However, if N increases to 40 while M remains 10, her required effort dramatically reduces, factoring in the combination of 40 taken 10 at a time.

To achieve an 80-bit security level, it's determined that exactly 10 low-length ECDSA signatures are needed. The flexibility of this model allows for adjusting the number of total signatures (N) to reduce Alice's computational load without compromising security. For instance, setting N to 46 ensures Alice's workload does not exceed 2^32, optimizing both security and efficiency. This balance reduces operational costs while maintaining robust security standards, representing a significant improvement over existing methods.