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$
$\endgroup$
11
-
$\begingroup$ Maybe the inventors of Bitcoin didn't know it? $\endgroup$– SEJPMCommented Dec 30, 2016 at 17:23
-
$\begingroup$ It's error prone, inflexible and produces big signatures. $\endgroup$– CodesInChaosCommented Dec 30, 2016 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$– otusCommented Dec 30, 2016 at 17:36
-
2$\begingroup$ Good question! Especially as we are now making the transition to post-quantum crypto algorithms. $\endgroup$– user27950Commented Dec 31, 2016 at 6:08
-
2$\begingroup$ @MaiaVictor, could you ask that as a new question? $\endgroup$– otusCommented Dec 31, 2016 at 7:48
|
Show 6 more comments
3 Answers
$\begingroup$
$\endgroup$
4
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$ Commented Oct 2, 2017 at 20:01
-
$\begingroup$ @CodesInChaos none which comes close to compare to ECDSA though. $\endgroup$ Commented Oct 3, 2017 at 15:55
-
1$\begingroup$ @CodesInChaos What are the smallest ones? $\endgroup$– CoryGCommented Dec 18, 2017 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$– ponchoCommented Feb 8, 2021 at 16:38
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
The Capitalisk (https://capitalisk.com/) blockchain uses the Lamport OTS Scheme in conjunction with the Merkle Signature Scheme (MSS) to produce signatures. MSS provides some degree of key reuse which is useful for signing multiple transactions concurrently.
Here are some pros and cons of using Lamport OTS with MSS in this way:
Pros:
- Simple and easy to understand scheme.
- Fast signature creation.
- Fast signature verification.
- Quantum resistant.
- Changing public keys allows the user to change their account passphrase; this provides additional security and peace of mind.
Cons:
- Large signature sizes (which are typically 30KB with classic Lamport OTS and 15KB with simplified Lamport OTS).
- It's a stateful signature scheme; this means that the public key needs to be changed every N signatures to prevent key reuse beyond the number which is allowed by the MSS hash tree (depends on the tree size). Having to handle a changing key state tends to add complexity to the code.
- Because a public key leaf in the MSS tree cannot be reused, it makes it cumbersome (and risky) for a user to sign off-chain messages to prove ownership of an account (I.e. it's relatively easy to keep track of which private key index was last used on-chain, but it's harder to keep track of it off-chain).
Note also that with Lamport OTS, the blockchain cannot be forked as effectively (e.g. to make a new clone blockchain with the same account balances) because keys cannot be reused. If someone tried to move their funds on the forked chain, they would end up revealing additional hash preimages from one of their OTS private keys on the main chain; this would make their tokens on the main chain less secure. Note that this could also be seen as a positive since it would act as a deterrent from forking the main blockchain.
For the blockchain use case, there are trade-offs which can be made to reduce the usage of storage space.
