Proposal: Design and early-development libraries for (QR) hash-based signatures

in Quantum Resistance10 months ago (edited)

Design and early-development libraries for (QR) hash-based signatures

Proposal Type: Opensource
Principals: @croupierbot (Rob Meijer, aka @pibara, aka @mattockfs )

Budget

The proposal for this first stage is to work one block of at least four and at most six hours each week for a weekly budget of 490 $HBD per week (70 $HBD/day) for the duration of 13 weeks.

If completion of the milestone ends up early, the remaining time will be spent on making the two libraries production ready. If completion ends up late, additional weeks of work will be added without a request for payment in order to complete the proposed milestones.

hold/convert/sell

I see other proposals define how the earned funds are to either be converted or sold. Not sure why this is, but out of apparent convention I will do the same. I intend to split my earnings in three equal parts:

  • 1/3th: sell to pay bills with
  • 1/3th: convert and power-up
  • 1/3th: set aside (unconverted) for funding :
    • Proposal creation fees for any post-quantum proposals coming out of the community (preferably not just mine)
    • Editing and artwork for my next (fiction) publication.

Expected completion date by milestone

  • Determine current ECDSA-key-usage statistics: week 2
  • Research appropriate hash-based-signature algorithms and parameters: week 4.
  • API design: Week 6
  • First interoperable proof-of-concept version of the C++ and the Python library: week 13

Progress reporting: By milestone

Project Summary

This project is meant to be a first step on a much larger roadmap towards making HIVE post-quantum ready in time for the cryptocalypse.

This one-man 3 months project is meant to get the post-quantum ball rolling for HIVE. The aim is to research, design and write two interoperable and API-similar libraries (C++ and Python) that implement:

  • Management of stateful private keys dimensioned appropriately for typical usage and sufficiently for outlier usage.
  • Hash-based signatures dimensioned for HIVE transaction signing.
  • Validation of hash-based signatures.

The goal of this first project is to create these libraries at least up to two interoperable proof of concept libraries that have the potential to, in later versions, become part of a set of three production quality libraries meant to be used by core ecosystem HIVE components.

Post-completion ?

After completion of this time-boxed project, the door should be open to subsequent project proposals for completing the libraries, adding a fully interoperable JavaScript library to the mix. These libraries could then, as step 3, be used in development efforts on the actual HIVE blockchain (C++), the Python BEEM and LightHive libraries, and JavaScript parts of the HIVE ecosystem such as KeyChain.

It is important to note that adding hash-based signatures is an important part of the post-quantum equation. Things like market-separation between funds held-by or earned-by migrated accounts and larger non-migrated accounts will eventualy need a lot of attention too, and there are other concerns. Please join the above-mentioned community and weigh in, in tackling those challenges, maybe eventually translating them into proposals as well.

Project description

As discussed in the (still very much underpopulated) Hive Quantum Resistance Community, it is likely that because of developments in Quantum Computing, ECDSA, the core signing algorithm for transactions on the HIVE blockchain will become dangerously obsolete before the end of this decade, in the most pessimistic scenarios even round and about the second half of this decade.

Other than several other blockchains that use ECDSA, signing keys in HIVE are designed to be re-used, making a move away from ECDSA towards quantum resistance slightly more urgent for HIVE than it is for these other blockchains.

As the HIVE ecosystem runs mostly under C++, JavaScript and Python, a first step is the creation of fully interoperable libraries for quantum-resistant hash-based signatures, fine-tuned to the needs of the HIVE blockchain and its ecosystem.

Benefits

The benefits of this proposal compared to a proposal that would try to fix the post-quantum challenge as a (series of) HIVE blockchain proposals first, is that by trying to build a set of two (eventually three) libraries targeting core ecosystem languages, we build solid interoperability in from day-one. Quantum resistance might not be a problem that needs to be solved in one or two years, but there is a lot of work to do to get things right, and this project could help kick-start work on this multifaceted problem.

What happens if the proposal becomes unfunded?

It being a one-man project, and while having been primary architect on many security and cryptography using project, and being a senior developer with years of experience in security and forensics qualifies me to run it as such, I do have limited time resources for doing unpaid work. Without funding, this 3-month project might turn out to become an 18-month project easy, and if, like for another library I worked on, the dev community gives me little to no pull, the project might end up abandoned. So in short: The project might still happen, but take a lot longer, or it might get abandoned.

At one point in time, maybe not in 18 months, but still, time will end up becoming short on achieving quantum resistance in time for HIVE. I thus hope people voting for this are able to grasp the role this project might end up playing as a kick-starting catalyst for getting the post-quantum ball rolling for HIVE. While this project only aims to (at-least) provide two proof of concept libraries, it is I think a modest yet important step towards a post-quantum ready HIVE ecosystem.

Team

For this first stage proposal, unfortunately the team is just one person, me. That is @pibara (aka @croupierbot, aka @mattockfs). I'm a data-engineer, system architect and software developer with a focus on information security, computer forensics and cryptography. I'm also a self published author of speculative fiction, but that may not be all that relevant to my credentials in regard to this proposal, except for the fact that I wrote about a quantum blockchain heist in my (HIVE-first published) mythpunk novel Ragnarok Conspiracy.

I've been primary architect and core-team developer on multiple information security and computer forensics projects. 15 years of extensive experience with C++. 8 years with Python, 2 with JavaScript (JavaScript is not my strong point, hence not in this proposal).

I've been doing data-engineering since 2000. Information security since 1994 and cryptography related projects since 2003. I wrote the proof of concept least authority file-system MinorFs in 2008, designed the Rumpelstiltskin Tree-graph sparsecap algorithm., was core architect on the Open Computer Forensics Architecture and CarvFs that later was merged, conceptually, with MinorFs to create the capability-secure proof of concept computer forensics file-system MattockFS.

As for my experience with HIVE. I used to be relatively active in development in the STEEM days. I wrote the asyncio Python STEEM libraries asyncsteem plus some tutorials, and later the aplha relaese of the txjsonrpcque library. I ran the @croupierbot that allowed STEEM users to run an indisputably fair draw contest, and ran the @pibarabot that posted daily reports and visualizations of the flag wars of these days.

While, in this first stage project, I'm a one man team, I hope that for future following projects I can team up with some more junior developers and hopefully a senior JavaScript developer for the JavaScript version of the proposed library.

Voting

If you would like to vote for this proposal, please use one of the followint:

  • Direct link to the proposal on peakd
  • The hive.blog proposal overview . Search the page for QR to find this proposal.

repos

I will be working from four github repos. Two for Python and two for C++. For both, using one repo for generic stuff that might be useful for non-HIVE projects, and the other one as HIVE layer on top of that.

Python

  • Low level: pyspqsigs There is some actual working code there right now.
  • Hive specific: pypqhive Nothing to see there yet.

C++

  • Low level: spq-sigs Some ugly half-done code there.
  • Hive specific: pqhivepp Nothing there yet.

image.png

Sort:  

I can't seem to find the proposal, doesn't seem to be a good search mechanism on the peaks proposal site. I went scrolling looking, but just didn't come up yet!

How exactly is elliptic curve vulnerable to quantum computing? What does this proposal do to address it? Will the solution require a pitchfork?

Eliptic curve cryptography is vulnerable to a modifief version of the shor algorithm

https://arxiv.org/abs/quant-ph/0301141

That means that once a few thousand qubit quantum computer exists, having either a public ECDSA key or an ECDSA signed transaction, deriving the signing key in a reasonable amount of time becomes practical.

The solution is multifaceted, but the signatures part of it involes a combination of a largish private key that is statefull, a one time signature algorithm such as WOTS or WOTS+, and merkle trees.

LMS is a candidate. So is XMSS, and there are others. Currently looking into an XMSS-like posibility using BLAKE or BLAKE2 as core hashing algorithm.

Please note that offering quantum-secure signatures is not enough to fix the problem by itself. We will also need separation strategies and tech to effectively separate both the market and the liquidity of upgraded vs vulnerable key holdings. That part isn't part in any way of the current proposal, that just aims for a first step on the signatures part of things.

Suppose there is a reasonable solution, ahead of any action taken against Hive. What do we do about blocks prior to the solution? Do we pull all of the transactions out and re-sign them into a whole new chain? Do we leave them in place and only use the new signing from then on?

Good question, and something that might eventually need attention, together with market/liquidity isolation. A question though that should I think, if it is relevant, be mostly relevant for brand new nodes that need to sync the whole chain from zero.

As stated, my proposal above is just a small first step on the hash-based quantum-resistant signatures part of things. I think we need a roadmap and people like you who know to ask the right questions to come to that roadmap.

Maybe you could look into the new node aspect in a blog post and post it in the (still fetal sized) community ?

I suppose having a separate balance that uses quantum-resistant keys would be a good first step. Those keys would be preferred after that. Whereas the legacy (non-quantum-resistant) keys would be less preferred, for a time. Then, once adequate adoption is achieved, the legacy keys would be fully discouraged.

Then, after enough time has elapsed, the legacy keys would only be used for replays, perhaps at that point, using quantum-resistant checkpoints during the replay.

Might be a very dumb question, but couldn't we just use quantum computers to create new cryptography that is quantum proof?

Even if the first quantum computer ends up hacking the chain before hive devs have access to one and learn new cryptography, wouldn't we just be able to go back to the state hive was in before the hack?

A scenario like the 2016 Ethereum split might end up being an option for reverting some specific fund transfers, but then, even if an alternative crypto patch would be instantly available to start things up again, if everyone has a private key that needs to be replaced at that moment in time, key replacement itself will become the new attack factor.

The IMO best solution is to offer a migration path to users while we can still trust the old keys (because powerful enough quantum computers aren't there yet). Not everyone will do this in time, if at all, so there is then a second problem. If your account is safe, but that of 40% of all HIVE holdings isn't, that 40% could disrupt the market to such an extent that you could lose most of the value of your holdings even if you have yourself migrated. As such, as a second part of being post-quantum ready (not covered by this proposal), we will need to look into measures that could allow for market separation between funds in accounts that have upgraded to post quantum ready signing keys, and funds held by accounts that still will only have ECDSA siging keys at the time that a QC attack becomes a realistic threat.