Announcing the QRL: Quantum Resistant Ledger

Inca

Moderator
Staff member
Aug 28, 2015
517
1,679
Hi,

Some of you may know me from posting here and on bitcointalk in recent years. I am huge bitcoin fan and believe that in the coming years a supranational scalable cryptocurrency will emerge as the payment medium for the internet. Hopefully this will be bitcoin :). I have some current concerns about bitcoin scaling and also over the longer term the security of bitcoin against a non-linear quantum computing advance by an adversary. (ECDSA is vulnerable to quantum computing.) I think it would be valuable to experiment with some quantum resistant signature schemes in the context of a blockchain ledger now rather than reacting to future events and a lot of fun to implement them.

I have created a python-based blockchain ledger project which utilises quantum resistant one-time hash-based cryptographic signatures instead of ECDSA as part of a merkle tree signature scheme(MSS). The protocol currently supports Lamport-Diffie(LDOTS) and Winternitz one-time signatures(WOTS) with protocol-level disabling of public key re-use. In the current version the merkle tree signature scheme allows each address to sign a finite number of transactions (~200 computationally easily enough). Using such a signature scheme increases transaction sizes quite a lot (~5kb for WOTS-MSS, larger for LDOTS-MSS) and necessitates the blockchain to record 'state' (store the used public key) to prevent transaction replay attempts.
Transactions and blocks are transmitted between nodes in JSON. The asynchronous node functions are handled by twisted-internet in the node. The 'state' of the chain is maintained in a levelDB.
Currently the node runs with mining disabled. Interaction with the node is through a local telnet session (telnet localhost 2000) allowing a number of wallet, node and mining and blockchain searching functions to be accessed.

The project is in alpha stage with a prototype, proof-of-concept, pre-testnet node to be found at:

http://github.com/surg0r/QRL

The subreddit http://www.reddit.com/r/qrl was gifted to me by a friendly person.

But I will use this thread to update the forum with progress as the codebase and project develops.

So far I have a local node and two linux vps boxes providing a testnet, with a network which mines for blocks (using a placeholder sha256 POW function) , processes transactions and allows basic wallet functions, blockchain searching functionality etc..

Outstanding major code updates todo include:
- improved node block handling to follow longest chain and reorg if required.
- switch currency unit handling from float to big integer.
- fully implement human readable string substitution for addresses (partially coded)
- recode the place holder POW algorithm to function properly, implement on the fly difficulty adjustment
- implement block reward, emission algorithm and tx fee handling..

Future aims:
- create a formal release which is stable for testnet purposes.
- implement XMSS scheme to enable unlimited tx signs with each address

Anyone who wants to get involved let me know..

Inca/pete
 
Last edited:

freetrader

Moderator
Staff member
Dec 16, 2015
2,806
6,088
Excellent work!

Although this may not be the "great fun" part, would you consider writing it up as a whitepaper?
I think this could really help people understand and get behind it.
 
  • Like
Reactions: Inca

Inca

Moderator
Staff member
Aug 28, 2015
517
1,679
White paper is a good idea, freetrader. I think I will make a start on that after a few more updates to the node codebase. :)
 
  • Like
Reactions: freetrader

Inca

Moderator
Staff member
Aug 28, 2015
517
1,679
Update:

1) Made contact with some post-quantum phd's who will hopefully advise/vet on the crypto requirements for the project.
2) Decided to implement winternitz OTS+ and some form of extensible MSS scheme..although most urgent coding task is to fully implement difficulty/block reward for mining purposes and to improve block handling logic of the node..then cryptography upgrade and white paper.
3) http://oxt.me shows that around ~50% of all bitcoins are currently in addresses with exposed public keys which are vulnerable to quantum computing theft - far higher than I suspected..

For those interested, the existing cryptography at the heart of the project uses a binary hash merkle tree with one-time signature (OTS) keypairs as the base leaves. The 'Q' address is simply a hash of the merkle tree root value with a four byte double hash checksum appended.
Because the MSS tree uses precomputed OTS keypairs it becomes very difficult to grow much bigger than 256 keypairs without computation time becoming an issue (time for both keypairs generation and calculating merkle tree authentication proofs).

There are a few schemes in existence to allow extension of the above basic merkle tree signature scheme (MSS). Instead of pre-computing a massive merkle tree above a huge number of random pre-computed OTS keypairs (say 2^8), a smaller merkle tree can be created say 2^4 and the 16 base OTS keypairs can be used to sign further merkle trees.

For example a 2^4 merkle tree can be used to certify another 2^4 tree which is computed initially. This allows 16 signatures to be used immediately from the 1st leaf. Once these are used up another merkle tree 2^4 can be generated and the root signed from the 2nd leaf of the base of the first tree. It is also possible to chain trees together to massively increase the signing capacity using schemes like XMMS or SPHINCS.

The drawback as far as i can tell of chaining numerous trees together is that the signature size grows as a result..
 
  • Like
Reactions: freetrader

Inca

Moderator
Staff member
Aug 28, 2015
517
1,679
So the project isn't dead. It has been quietly beavering away. It is a small group but we are working feverishly on a private alpha testnet using a custom proof-of-stake algorithm, again relying upon the security of cryptographic hash functions rather than conventional digital signature schemes.

An updated white paper, github repo and a link for volunteers or potential early investors is on http://theqrl.org.

I wrote a little blog post about it on medium: https://medium.com/@surg0r/blockchain-is-here-to-stay-but-for-how-long-536336a02b03#.d2saz4leg.

I expect us to have another few weeks of private tinkering before we go public with a testnet. It has taken a lot longer than I expected - creating a algorithm was easy, creating a good one much more difficult (iteration 5 now) especially which can scale upwards to allow 100's of stakers whilst not be easily gameable.

In any case we are not far off a fully fledged launch of a the world's first blockchain which has 0 reliance upon conventional signature schemes and is completely resistant against classical and quantum computing attack.

Exciting times. Anyone who wants to join the developer slack just PM me.

Pete
 

Inca

Moderator
Staff member
Aug 28, 2015
517
1,679
Alpha testnet up with node count in double digits. Nodes in Japan, US, UK, Netherlands and New Zealand.

No network panics just yet.