Lamport signature in script 2.0?

[jl2012]

Is there any chance to support Lamport signature in the future? Comparing with traditional private key cryptography, Lamport signature is much more easy to implement. It is also QC hard. There are 2 major problems for Lamport signature: one-time-use only and large size.

The one-time-use only problem can be improved by using a merklelized public key (http://en.wikipedia.org/wiki/Lamport_signature#Public_key_for_multiple_messages).

For sig size, it's actually not that big. Using Hash160, the public key will consume 800bytes, and the signature will consume 400bytes, so the total will be 1.2kB (a few more bytes if merklelized public key is used). A transaction like this: http://blockchain.info/tx/8e17ed76cf51a9adcbb284365c2aff6bf28f7fa8259286dd1a93ec1cd47a81ca already takes 1.5kB. However, using the  CHECKSIG 2.0 I proposed at https://bitcointalk.org/index.php?topic=258931.0, it is possible to sign multiple inputs with only one signature. Therefore, using Lamport signature would not be a big problem.

[metacoin]

I'd like to further discussion on this thread, considering the news regarding dangers of re-using the ECDSA algorithm with the same private key. I think it is worthwhile from an experimentation and research standpoint to implement new and different CHECKSIG opcodes, perhaps on the testnet or an alt-coin.

In addition, using a Hash Ladder algorithm it is possible to further reduce the size of Lamport signatures through a clever method of hashing the public key.  https://gist.github.com/karlgluck/8412807

[TierNolan]

In addition, using a Hash Ladder algorithm it is possible to further reduce the size of Lamport signatures through a clever method of hashing the public key.  https://gist.github.com/karlgluck/8412807

That is pretty interesting.  It trades CPU for signature length.

I think he has messed up his table though.

A 256 bit hash combined with a 16 bit chunk should be 1024 bytes rather than 2048 bytes.  It makes it look like eventually a larger chunk makes things worse.  I think the later rows should be 512 hash lengths?

The CPU cost is exponential and the smallest possible signature would be 2X the hash size.

What would be cool would be a method that requires more CPU to sign but less to verify.

[xeroc]

There was a project called L-coin which wanted to use Lamport signatures in combination with multisig. However I haven't heard from them in a while

http://l-coin.org