The Lamport signature scheme is faster, less complex and considerably safer than ECDSA. It's only downside - being only usable once - isn't really a downside when signing transactions, since you could just include your next public key whenever signing it. Why isn't, thus, the Lamport signature scheme used in crypto currencies such as Bitcoin?

  • $\begingroup$ Maybe the inventors of Bitcoin didn't know it? $\endgroup$
    – SEJPM
    Dec 30 '16 at 17:23
  • $\begingroup$ It's error prone, inflexible and produces big signatures. $\endgroup$ Dec 30 '16 at 17:32
  • 3
    $\begingroup$ Big signatures are probably the main reason – the blockchain of bitcoin is huge as is. I don't have a reference, however. $\endgroup$
    – otus
    Dec 30 '16 at 17:36
  • 2
    $\begingroup$ Good question! Especially as we are now making the transition to post-quantum crypto algorithms. $\endgroup$
    – user27950
    Dec 31 '16 at 6:08
  • 2
    $\begingroup$ @MaiaVictor, could you ask that as a new question? $\endgroup$
    – otus
    Dec 31 '16 at 7:48

The major issue will be size difference. The size of ECDSA in bitcoin is much less than the Lamport Signature.

For ECDSA in bitcoin

  • The public key is only 33 Bytes (1 byte for prefix, and 32 bytes for 256-bit integer x)
  • Signature is at maximum 73 bytes

Whereas in Lamport Signature

  • The public key is 512 numbers of 256-bit (total of 16KB)
  • The Signature is 256 number of 256-bit (total of 8KB)

The size of Lamport public key and signature together is 231 times (106 bytes vs 24KB) more than the ECDSA public key and signature.

The public key and signature form part of each bitcoin transaction and are stored in block chain. So use of Lamport Signature will need 231 times more storage than ECDSA. As of 1 Oct 2017, the Blockchain size is approximately 135GB. Had it been the Lamport Signature, this would have been in TeraBytes. This would have resulted in higher storage and bandwidth requirement, less number of transactions in one block(which may create backlog, as one block is committed in 10 minutes) and more time in blockchain propagation to other nodes.

Moreover, In bitcoin each transaction is charged a network fee based upon transaction size(in terms of bytes, not in terms of amount). At the moment, the network fee rate is 178, 149, 120 satoshi / byte for high, medium and low priority respectively.

  • $\begingroup$ There are significantly smaller one-time signatures than those. $\endgroup$ Oct 2 '17 at 20:01
  • $\begingroup$ @CodesInChaos none which comes close to compare to ECDSA though. $\endgroup$
    – MaiaVictor
    Oct 3 '17 at 15:55
  • 1
    $\begingroup$ @CodesInChaos What are the smallest ones? $\endgroup$
    – CoryG
    Dec 18 '17 at 4:07
  • $\begingroup$ @CoryG you could use a Winternitz scheme, rather than a Lamport one - that would reduce the size of a signature significantly (e.g. to circa 300 bytes with $w=256$ and 128 bit hashes for 128 bit security), and the public key to ECDSA sizes. That said, the signature size is still much larger than ECDSA... $\endgroup$
    – poncho
    Feb 8 at 16:38

I know this question is really old, but you should look into IOTA (iota.org), they use Winternitz one time signature instead of ECDSA. There's also a paper about Winternitz OTS here: http://eprint.iacr.org/2011/191.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.