Progress on "Simple Post-Quantum Signatures" libraries (C++ spq-sigs lib)

Its been almost three weeks since my last progress report on the Simple Post-Quantum Signatures libraries. In my last progress report I showed a working C++ implementation for single-tree post-quantum signatures.

Now, three weeks later, after slow progress because of limited time resources, I've reached the next milestone with working multi-tree signatures.

Multi-tree signatures are larger than single-tree signatures. Next to that, the time it takes to sign a message can vary as signing might require the generation of a new signing key tree, and occasionally an intermediate key tree. Multi-tree signing keys though, allow for larger numbers of signatures to be made before exhausting the primary key. So while for systems with limited key-reuse single-tree signatures might be the best option, in systems like the #HIVE blockchain based blogging platform, or the FlureeDB blockchain based graph database, where a signing key is fundamentally tied to a user account, and key-replacement isn't a frequent operation, multi-tree signatures are the way to go.

So how do multi-tree hash based signatures work? Lets discuss quadruple tree signatures.
In our example we define four levels, each with a 16 signature key.

1. The users root signing key
2. The long term intermediate signing key
3. The short-term intermediate signing key
4. The message signing key

The user's root signing key can sign 16 different long term intermediate signing keys. Each long term intermediate signing key can sign 16 short term intermediate signing keys. Each short term intermediate signing key can sign 16 message signing keys. And finally, each message signing key can sign 16 messages.

So in the end, one user root signing key can in our case sign a total of 65536 messages. But note, the receiver needs to, at least at one point in time, have seen a total of four signatures in order to know the message signature was valid and done by the user.

1. The message signed by the message signing key
2. The pubkey of the message signing key, signed by the short-term intermediate signing key
3. The pubkey of the short-term intermediate signing key, signed by the long term intermediate signing key
4. The pubkey of the long term intermediate signing key, signed by the user's root signing key

We'll be using some validator side caching and signer side data reduction for the keys to not send all four of these signatures in the future, but that, together with actual serialization of the multi tree signatures, and the implementation of key serialization and wallets, is something for future milestones. For now, the only place where the future bleeds through a tiny bit is the API.

So let's look at the API for multi-tree signatures that we have now. Multi tree signatures are implemented in two sets of variadic templates right now. This allows you as a user to define
your multi-tree signatures of any dimensions you see fit. Note though that other than merkle tree height, the other signing key parameters such as the hash length and the number of WOTS bits to use for WOTS compression is set to the same values for all trees in the multi-tree setup.

Let's define our types. We need one type definition for a multi tree signing key and one for a multi tree signature validator.

#include "spq_sigs.hpp"
constexpr unsigned char hashlen=24;
constexpr unsigned char wotsbits=12;
constexpr unsigned char merkleheight1=4;
constexpr unsigned char merkleheight2=4;
constexpr unsigned char merkleheight3=4;
constexpr unsigned char merkleheight4=4;
typedef spqsigs::multi_signing_key<hashlen, wotsbits, merkleheight1, merkleheight2, merkleheight3, merkleheight4> signing_key;
typedef spqsigs::multi_signature<hashlen, wotsbits, merkleheight1, merkleheight2, merkleheight3, merkleheight4> verifyable_signature;

Note that where before, the signing key would return a single string, the signature, the multi tree signing key will return a more complex structure. In the end you won't have to worry about this, as serialisation will take care of that, but for now, we have this complex return value. But lets use auto anyway to not get drowned in details.

std::sting msg("nobler in the mind to suffer");
auto skey = signing_key();
auto signature = skey.sign_message(msg);

The actual message signature is available through signature.first, and the respective pubkey signatures through signature.second[0].second through signature.second[2].second, but please forget about this for now, as serialization will soon take away the need for developers to concern themselves with those details.

So how about validation? For that we need to first create a little annoying little vector that really is only there right now because once we get data reduced serialization, this vector will become the interface for inserting validator side knowledge into the signature validator.

std::vector<std::string> cached;
cached.push_back("");
cached.push_back("");
cached.push_back("");
cached.push_back(skey.pubkey());

Now that we have our dummy cache vector, we can instantiate a validator and validate the signature.

auto sign = verifyable_signature(signature, cached);
bool validated = sign.validate(msg);

What's next?

Now that we have multi-tree signatures, the next up is multi-tree signature serialization and reduced size signatures. When we have these, and have them thoroughly tested, we will be ready for the final step towards the Minimal Viable Product, the implementation of a wallet from the multi tree signing key, using key serialization and encryption of the serialized private bits.

Again, it will be awhile before the next milestone as the spare time I can spend on this project is limited at this time, but I'll continue working on the project, so bare with me, and if you feel this project deserves more attention, pleas upvote my progress reports, send some $HIVE to @croupierbot in support of this project, or be the first to support this project on Patreon.