Bitcoin Forum
December 13, 2017, 10:04:25 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Lamport signature in script 2.0?  (Read 1619 times)
jl2012
Legendary
*
Offline Offline

Activity: 1750


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
1513159465
Hero Member
*
Offline Offline

Posts: 1513159465

View Profile Personal Message (Offline)

Ignore
1513159465
Reply with quote  #2

1513159465
Report to moderator
1513159465
Hero Member
*
Offline Offline

Posts: 1513159465

View Profile Personal Message (Offline)

Ignore
1513159465
Reply with quote  #2

1513159465
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1513159465
Hero Member
*
Offline Offline

Posts: 1513159465

View Profile Personal Message (Offline)

Ignore
1513159465
Reply with quote  #2

1513159465
Report to moderator
1513159465
Hero Member
*
Offline Offline

Posts: 1513159465

View Profile Personal Message (Offline)

Ignore
1513159465
Reply with quote  #2

1513159465
Report to moderator
metacoin
Sr. Member
****
Offline Offline

Activity: 359


live free


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

⚜ Florin block explorer: http://florincoin.info
TierNolan
Legendary
*
Offline Offline

Activity: 1148


View Profile
April 11, 2014, 12:21:17 PM
 #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



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:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!