Bitcoin Forum
October 14, 2024, 10:05:27 PM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Lamport signature in script 2.0?  (Read 1696 times)
jl2012 (OP)
Legendary
*
Offline Offline

Activity: 1792
Merit: 1111


View Profile
July 26, 2013, 04:27:19 AM
 #1

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.

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3 (Bitcoin ONLY)
LRDGENPLYrcTRssGoZrsCT1hngaH3BVkM4 (LTC)
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
metacoin
Sr. Member
****
Offline Offline

Activity: 437
Merit: 260


balance


View Profile WWW
April 11, 2014, 04:36:19 AM
 #2

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

pin.org
TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1104


View Profile
April 11, 2014, 12:21:17 PM
Last edit: April 11, 2014, 12:43:55 PM by TierNolan
 #3

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.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
xeroc
Sr. Member
****
Offline Offline

Activity: 345
Merit: 250



View Profile
April 11, 2014, 01:01:41 PM
 #4

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
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!