Some ideas for a Quantum-Resistance roadmap for HIVE

HIVE is amazing for many reasons. A great community, an amazing blogging platform, zero transaction costs enabled by a POS based resource credits system, etc, etc. Many reasons to be positive about both the platform and the coin. There remains however one important source of concern: Quantum Computing

HIVE uses ECDSA for signing transactions, what, for now, is basically the standard way to do signing on a blockchain. But be aware of the for now part. Quantum Computing is advancing slowly but steadily, and in some instances even with some major leaps. In the foreseeable future. More than a few years, but less than a decade, we can expect the for now part to kick us in the teeth if we don't act before that. So what's the problem? Once a quantum computer is constructed, somewhere in this decade, most likely, that has more than a certain threshold of so-called qubits, that a quantum computer should be able to calculate an ECDSA private-key using a signed ECDSA.

For some blockchains that is a non-urgent problem because private keys are rarely reused, and all funds bound to a private key in an USO get spent the moment the USO gets spent. In those chains a signature sitting on the chain isn't a problem because no funds are bound to it anymore.

HIVE is not such a chain. In HIVE, the re-use of private keys is fundamental to its current design. As such, HIVE is really vulnerable to Quantum Computing. In this post I want to look at a few first steps we could take in order to try and make HIVE Quantum Computing safe before the time left to fix this problem becomes too short.

Hash based signing

While there are many blockchains where ECDSA key-reuse is rare and as such the biggest and most direct threat factor posed by Quantum Computing is minimal, there is currently only one bockchain that can be considered fully and fundamentally Quantum Resistant, and that is QRL. What makes QRL fully quantum resistance? The fact that QRL never used ECDSA signatures. Instead QRL uses one flavour of so called Hash-Based signatures: XMSS (EXtended Merkle Signature Scheme). Don't get too cought up in XMSS imideately. There are other similar options such as LMS (Leighton-Micali Signatures).

We could go and do a deep dive into the details of hash based signing and talk about Merkel-trees and other important details, but let's leave that subject for a different post. For now let's focus on a few attributes that make hash based signatures different from ECDSA signatures.

An XMSS/LMS private key is a multi-use resource

For ECDSA you can look at a private key in two ways. If not considering Quantum Resistance, an ECDSA private key is an inexhaustible resource. You can sign as many transactions as you like, and without a Quantum Computer of considerable size, you will never run out of this resource.
When you do take QC into account the picture changes quite a bit, and an ECDSA private key becomes a single use resource that is depleted as soon as you used it once.

An XMSS/LMS private key is different. Depending on how you dimension it, a private key can be used a few dozen times, a few hundred times, or many thousands of times. The more transactions you wish to sign with a single private key before this resource is depleted, the larger for example the signatures get, and there are other considerations as well. We could probably do a post on optimal parameters for a HIVE XMSS/LMS keys and signatures, and I probably will do just that someday. Just not now. For now, just remember that a hash based signing key is a resource that depletes with use.

Signature size

Depending on the number of transactions you want to be able to sign before having to replace your signing key, a signature with a hash-based signature will be quite a bit bigger up to a whole lot bigger than an ECDSA signature. We can probably, for HIVE dimention it to be just a few hundred bytes in size. What compared to a 64 byte signature for ECDSA is already quite a bit bigger.

A draft roadmap

The below roadmap draft is just that, a draft. It likely is by no means complete, but hopefully it is something that can act as a basis to start a discussion from. Some of the below steps might be candidates for proposals in the HIVE proposal system and as such might find funding. Others, especially the design part, likely will need to be done without any prospects of earnings, but that shouldn't matter, considering we are working on the long term value of all of our holdings.

1. Design a base signing structure
   • choose key hierarchy.
   • pick hash-based signature primitives.
   • pick hash-based signature parameters.
2. Write a signing and signature validation libraries for HIVE relevant languages
   • C++
   • JavaScript
   • Python
   • Others ?
3. Add API to HIVE for setting and updating hash-based signing pubkeys.
4. Update existing signed transaction API to accept hash-based signing-key signed transactions.
5. Design and build market-separation strategies and extra coins.
6. Set and hard-code dates for specific market separation events.

Let's keep 3 to 6 for a future post and start with looking at the first two steps.

Step 1: Design a base signing structure

Given that, as discussed above, hash based signing is done with keys that are an exhaustible resource, and that choices made have major impact on things like the size of signatures, dimensioning the keys just right becomes an essential part of the migration path.

Currently HIVE has a key hierarchy with the following keys:

• Owner key
• Active key
• Posting key
• Memo key

I don't think the Memo-key is ever actually used, so we might just want to skip discussing that for now. Consider we need a hash based signing equivalent of the other three keys. While it may be tempting to use the new quantum resistant owner key as the key we use to replace depleted active and posting keys with, we must realize that there are scenarios where the owner key itself gets used for numerous transactions, and we don't want to risk depleting an owner key and locking ourselves out. We should also consider the numerous users today that have lost their owner key, and have been using their HIVE account with just their active and posting key. If we require the owner key for a user to migrate to hash-based signing, this could put up a barrier to adaptation that we don't want to introduce.

So instead we propose the following key hierarchy

• Post Quantum Revival Key
• Post Quantum Live Keys
  • Post Quantum Owner Key
  • Post Quantum Active Key
  • Post Quantum Posting Key

The idea is that the Revival key can be set once (or in special conditions, twice) using an ECDSA signing key. This could either (preferably) be the Owner key, or in the case that the user has lost her owner key, using the Active key.

The strategy would be that if the Revival Key is created with the Active key, it can't be used to create a Post Quantum Active Key. If the Revival Key is created with the Active key, a timer should be started. Within the time window defined for this, the Owner key may still be used to overwrite the Revival key and clear the Live keys. The idea is to find a balance between:

• The risk of lack of adaptation by users without an owner key.
• The risk of privilege escalation with an active key.
• The risk of a quantum computing based security incident.

We could for example pick 3 months as time window for overruling the active key activated Post Quantum Revival Key with a owner key activated Post Quantum Revival Key. After those 3 months, the owner key will be rendered useless as to attenuate the risk of quantum computing based security incident.

Once the Quantum Revival Key is set, it could be used to set the Post Quantum Live Keys.
Once a Live Key is (almost) exhausted, the Quantum Revival Key can be used to set a replacement Live Key at that level of access.

Again, the above is just a draft that needs work and discussion.

There are signature primitives we need to consider. Do we want to use standard SHA256 hashing as primitive, or do we maybe want to use alternatives such as BLAKE2? And once we have picked the primitives and decided on things like LMS vs XMSS vs our own derivative from one of these options (for example a non-standard-compliant version of LMS that uses BLAKE2 rather than SHA256), we will need to pick parameters like tree height and friends. This is something for another post, and again, input is highly welcomed.

Step 2: Write a signing and signature validation libraries for HIVE relevant languages

Once we have decided on the base signing structure above, we can start implementing. Today C++, JavaScript and Python are the dominant languages of the platform. It would seem like a good idea to simultaneously work on three libraries for the main three languages. A library that implements key management, signing and signature validations according to the signing structure step above.

Please weigh in !!!

At the moment, it feels a bit that I'm either the only one on HIVE who is seeing the urgency of quantum resistance for HIVE, or the only one on HIVE who feelks (s)he has anything constructive to say regarding a possible roadmap towards making HIVE post-quantum ready. If you, like me, are concerned about the future of HIVE in the light of Quantum Computing, please at least join the Quantum Resistance HIVE community, and if you can, write your own blog posts on this topic.

I have a feeling HIVE is sleeping and we need to wake it up. We need to do this together as a community, so please weigh in, comment on this post, join the Quantum Resistance HIVE community and post your own HIVE quantum resistance blog posts.