BIP: alonzocoeus-quantumsafe Title: Quantum Safe Transactions Author: Alonzo Coeus <alonzo.coeus@mail.com> Status: Draft Type: Standards Track Created: 2016-04-17
In this BIP describes 4 new opcodes for quantum proofing the bitcoin system.
The bitcoin protocol using escada for transactions is not quantum secure and this may allow coins held by a bitcoin user to be stolen. So I plan to introduce a new set of OPCODES for quantum proof transactions.
The 4 new OP_CODES are CheckSig's using a lamport signature inspired algorithm they will replace NOP4 to NOP7.
- OP_LAMPORTCHECKSIG
- OP_LAMPORTCHECKSIGVERIFY
- OP_LAMPORTCHECKMULTISIG
- OP_LAMPORTCHECKMULTISIGVERIFY
The signature algorithm we use will be a version of lamport using hash ladders suggested by karlgluck here but we will use RIPEMD-160. We will use merkle trees to allow you to sign multiple times without endangering your bitcoin's.
To compress the private key we will use a Ripemd-160 Hash as a pseudo random generator. We will use a 512-bit seed for creating the private key but in main use users will use the 512-bit seed but you could use any size want. To create the keys we run the seed through a for loop and concatenate it with the loop index and hash it this gives us is our 160-bit will be a part of our private key for the signatures.
The hash ladder we will use lowers key size by 30% using 8-bit chunk sizes. It divides the document hash into chunks which should be around 8-bit's. Your public keys for each chunk would be a pair of 160-bit hashes of 160-bit numbers hashed 162 times.
To allow multiple use signatures we will create a merkle tree with the branches being the hash of the public key for the entire document. These hashes will have the size of 160 bit's the merkle witness is the path on the merkle tree to cryptographically prove that this key set belongs to the batch of keys. The structure of this witness will be shown bellow
[publickey1, publickeyhash2, nodehash12, ...]
The first public key is what is used for checking the signature is correct but the rest is for proving the public key belongs to a roothash.
To verify that this truly does belong to a roothash you would hash the public key the first element in the array this would be put in a variable (let’s call it tempverifyhash). Then you would hash the concatenated string of tempverifyhash and publickeyhash2 then set that to tempverifyhash. You do this in a loop until there is no value left in the array if this is equal to the roothash this public key is valid.
now you can verify the signature with the public key (if the public key was genuine).
I have started work on an implementation of this at https://github.com/Alonzo-Coeus/bitcoin/
I added 2 new files in crypto/
- lamport.h
- lamport.cpp
Also I have added 4 new Opcodes in the script interpreter
This BIP must not be implemented until segwit is added and lightning is in use for most tx's. Otherwise this will have a negative effect on scaling for bitcoin. This is mostly just a safe gaurd for when quantum computers are main stream
A normal transaction using this OPCODE would be.
ScriptPubKey: {root public key} OP_LAMPORTCHECKSIGVERIFY ScriptSig: {sig} {merkle_witness}
[1] karlgluck's lamport variant
This document has been put in the public domain.