As you may know, my dhf-proposal to make my post-quantum hash-based-signatures project for HIVE failed to gather the support needed to get funding. As a result, I had to trim down the project quite a bit, and had to shift away from a quick 3 month project towards a longer running development effort.
While the original proposal had a generic layer and a HIVE specific layer, and included a data engineering phase for finding out the ideal parameters that HIVE should use.
In the new revised setup, there is no HIVE specific high level library anymore. That doesn't mean I've given up on making my work usable for HIVE. It just means that HIVE has now become an equal citizen to any other blockchain that may want to use the spq-sigs project for implementing simple post-quantum signatures. It also means someone else will need to be doing the data engineering part for fitting spq-sigs into whatever blockchain wants to use it.
To summarize, the changes to the project are as follows:
- I will be working on the project when I have time, no allocated time slots unless I find an alternative source of project funding.
- No more HIVE layer
- No more HIVE data-engineering phase for finding out the ideal low-level parameters for hash-based signatures.
- Multi-tree will be moved in to the now generic library (used to be planned for the HIVE layer)
- Encrypted wallet will be moved in to the now generic library (used to be planned for the HIVE layer)
- The language support priorities have been shifted around.
- Now using libsodium
While the first Python proof of concept implementation of the project used hashlib, my recent experience with libsodium. I am planning to redo the Python implementation using the Python language bindings for libsodium as well. The reason for this is that libsodium, next to blake2b, that we use for the hash based signatures, also has argon2, xsalsa20 and poly1305, that are perfect candidates for implementing encrypted wallets with. So nw, the new plan is to use libsodium as cryptographic basis. First write an initial version of the full library in C, and then port this library to other languages that have libsodium bindings. While I'll be working on the C library for a bit, I'll share the language porting roadmap as I invission it now.
- C++
- Python
- Rust
- JavaScript
- Clojure
- Elixir
- Ruby
- Php
Not sure how far down the list I'll eventually end up coming. If I continue working without any funding, chances are I won't get further than two up to four languages. If I do acquire funding for my project, I might end up reshuffling my language priorities to accommodate sponsors.
single-tree hash-based signatures.
The core feature the spq-sigs library builds around are single-tree hash-based signatures.
I won't make this too extensive, as I did other blog posts on this, but a quick walkthrough of the spq-sigs hash-based signatures algoritm. We start at the bottom of the image with a seed. We consider the seed, for all practical purposes to be your secret key. In the image the small purple circle is our seed. From the seed we derive a large private key for each one-time signing operation. This WOTS private key is at the bottom of a collection of double WOTS chains. In the image the orange dots represent a signature for the octal number 3751.
The sender calculates the orange circle hashes from the WOTS private key and the 3751 digest using salted hashing operations. The receiver can than calculate the grey 2 circle using the orange dots and the 3751 digest.
At the top of the algoritm is a merkle tree. The sensder includes the red dots as a header with the signature. Using the 2 result combined with the red dots, the receiver can calculate the green dot. This green dot is the merkle root and the public key, so if the calculation by the receiver matches the pubkey, the signature is found to be valid.
progress
So how far are we right now? There is a Python proof of concept implementation here, and I'm currently working on a non-POC C++ implementation. Just the single-tree implementation for now.
To use the code right now (what you shouldn't do yet except for educational purposes), you start off by including the single-file header-only include file. Secondly, you create a typedef with the desired signing key parameters.
Here we define a signing key type that can sign 1024 messages, uses 24 byte long hashes as primitive, and uses 4096 high dual WOTS chains to encode 12 bits at a time.
#include
constexpr unsigned char hashlen=24;
constexpr unsigned char wotsbits=12;
constexpr unsigned char merkleheight=10;
constexpr bool do_threads=true;
typedef spqsigs::signing_key<hashlen, wotsbits, merkleheight, do_threads > signing_key;
typedef spqsigs::signature<hashlen, wotsbits, merkleheight> verifyable_signature;
Once we have the typedef, we can instantiate a signing key.
auto skey = signing_key();
For now, this signing key is usefull only for demo and educational purposes as we don't have a wallet yet, or any way to implement serialization and deserialization. That feature will come after we have implemented the multi-tree signing keys that ate projected to become the foundation of our wallet implementation. The reason why we will need multi-tree signing keys is that public key calculation becomes problematic as the tree hight grows towards values compatible with life-long key usage on a chain like HIVE. We need to chop up the tree into multiple layered smaller ones for things to remain practical.
But let's continue with usage. Once we have our signing key instantiated, we can use it to sign messages with.
std::string msg("This is just a test.");
std::string signature = skey.sign_message(msg);
We actually need a tiny bit more code, as our signing key could get exhausted. If it does, the library will throw an exception.
try {
std::string signature = skey.sign_message(msg);
} catch (const spqsigs::signingkey_exhausted&) {
std::cerr << "Signing Key exhausted" << std::endl;
}
Now, once we have a signature, we can check if its valid.
auto sign = verifyable_signature(signature);
std::string msg("This is just a test.");
if (sign.validate(msg)) {
std::cout << "OK" << std::endl;
} else {
std::cerr << " Oops, invalid signature." << std::endl;
}
Now for the real milestone. A little program.
This program generates a signing key, creates the maximum of 1024 signatures for the key, and then one more.
The result is long, and ratther repetative, so here is the start and the end of the output from our little test program.
We see our signatures end up being 1058 bytes long, and that is just for a single tree signature. The first 1024 signatures all validate succesfully, then the final one triggers an exception because the key is exhausted.
What's next?
I'll (slowly) continue working on this project, first focusing on C++ for a while, implemeting the following:
- Implement multi-tree signing keys and signatures.
- Private key serialization and de-serialization.
- Private key password protection (use libsodium).
- Intermediate signature caching.
- Add multi-threading.
- Work on const-correctness.
- Document usage.
- Add a sample project with cmake and stuff.
After that I'll move on to Python, then come back to C++ for a bit.
- Test signing/validation cross language compatability and fix if needed.
- Test serialization/deserialization python/c++ cross-compatibility.
Help and funding?
For now I'm not allocating set time slots to the project, so progress will be slow and/or busty. If you want to support the project, please consider:
Non-financial
- Doing the port for your favourite (libsodium supported) language.
- Doing a code review
- Doing a cryptographic analysis of the C++ implementation
Financial:
- My brand-new Patreon page
- Donating $HIVE/$HBD to @croupierbot.
- Donating other crypto currency to the project.
- Upvoting my project progress posts on HIVE.
If I either get the funding for allocating fixed time slots to the project, or I get other people to work with me on this project once the initial C++ reference implementation is far enough along, we can make this project the success it deserves to be, so please consider contributing in any way you feel you can.
The day that quantum computers will be able to reconstruct ECDSA signing keys from signatures is coming closer and closer.