A few days back I posted about this problem, where I thought I had to choose between security and easy synchonization between blockchain clients.
Turns out, using the libsodium key derivation function crypto_kdf_derive_from_key I don't. We can have our cake and eat it.
Using this function in the right way will require a bit of refactoring, but in the end we shall get the best of both worlds.
As the libsodium documentation tells us:
The crypto_kdf API can derive up to 2^64 keys from a single master key and context, and individual subkeys can have an arbitrary length between 128 (16 bytes) and 512 bits (64 bytes)
We can work with this. With a tiny constraint for our template parameters. Let's look at the function in question:
int crypto_kdf_derive_from_key(unsigned char *subkey, size_t subkey_len,
uint64_t subkey_id,
const char ctx[crypto_kdf_CONTEXTBYTES],
const unsigned char key[crypto_kdf_KEYBYTES]);
If we can create a unique 64 bit number for each WOTS chain in each subkey in each one-time key in each single merkle-tree multi-use signing key within a multi-tree signing key, then we can use a single high-entropy seed that will work on all multi-tree levels during the entire lifetime of our root key.
Why again is this a big deal? If we have a setup like this, and the blockchain remembers the last full signature info used by an entity with a given pubkey, then if we have multiple clients talking to the blockchain using the same key (for example key-chain installed on your laptop, key-chain installed on your desktop, and a Python script running on your NAS, then if for one client the time has come to generate a new transaction singing level key and/or intermediate level key, that client can just do that, and all other clients will be able to regenerate the new key from the shared common seed and information provided by the blockchain.
So how can we use the 64 bits at our disposal?
- Multi-tree level-id: 7 bits. Normally a multi-tree setup will have no more than a handfull of levels. We can not fully predict though that there won't be any use-cases for more than a handful. We pick a relatively high value of 7 bits, or 128 possible levels.
- One-time-key id: 16 bits. Our library supports merkle trees of up to 16 levels. That means we also need 16 bits to encode the specific one-time key id.
- Subkey-id: 40 bits. Depending on the wotsbits and hashlen parameter, a one time signing key can in theory consist of a single up to 128 subkeys. The larger values, that would arise if wotsbits is set close to the minimum of 4 bits per subkey, and the hash length is set close to the maximum of 512 bits. We set the number of bits to annotate a subkey to 40. This means that many combinations of smaller numbers for wotsbits and larger numbers for hashlen shall no longer be possible. This is the price we are paying for secure and easy synchonization.
- Dual-wots-chain direction: *1 bit. As we are using a dual wots chain, we need one bit to designate the specific direction of the chain our derived seed will be for.
By choosing these numbers of bits, everything adds up to the 64 bit unique number that the libsodium crypto_kdf_derive_from_key function supports.
This small refactor is giving us a tiny delay in implementation, but it will absolutely be worth it. Please note though that the synchronization we achieve will come at a bit of a user experience price. Let's discuss.
Today, with ECDSA key, if you for example do a query against a #FlureeDB blockchain based graph database, if do a post on the #HIVE blockchain, this signature would be close to instant. Even if you don't have a wallet installed, but simply log into one of the HIVE frontends with your posting key.
With hash-based signatures, things are a little different. Just like with ECDSA, the hash-based key will have a HIVE posting key or a FlureeDB signing key, or whatever blockchain will end up using the hash based signatures provided by spq-sigs, and this private key will be short-ish like the keys you are used to using. This short-ish key however, as you may have gathered from the above descriptions, not only will this seed private key end up getting converted to a large-ish private key, this large-ish private key is converted to a public key and merkle-tree needed for signing. The operation for converting the private key into a public key is a time-consuming conversion that can take many seconds up to many minutes depending on the number of wotsbits chosen and the chosen merkle height for the signing key.
Once a signing key has its public key and Merkle tree available, signing will be quick, that is, until the transaction signing key gets exhausted and a new transaction signing key needs to be generated, and importantly, converted to a public key so it can be used for signing. This means that you could do maybe a few thousand transactions that take a few dozen milliseconds, and then the next one takes half a minute. And once every few million transactions, a transaction takes a whole minute.
Now add in synchronization, and what happens? Instead of that one in a few thousand transactions taking half a minute on just one client, it will end up taking half a minute on each client because of synchronization.
And in the case of systems like HIVE, when used without a wallet, you should look at the web login as a brand-new client at every login. So with hash-based signatures without a wallet, signing in could easily take a minute or more as multiple keys are getting restored from the shared seed.
That sucks, right? So why go through all the trouble of this spq-sigs project? Well, the answer to that question is Quantum Computing. Between two years from now and 15 years from now (I wish I could be more specific, but this really seems to be the certainty in current projections, at least it was a few months back the last time I consulted people I consider highly knowledgeable on the subject), we can expect the largest existing quantum computer at that time to be able to take an ECDSA public key, either directly available or extracted from an ECDSA signature, and convert it to the matching ECDSA private key. On a blockchain like HIVE, or on a database blockchain such as FlureeDB, both systems that use key-reuse by design, this is a huge problem.
So couldn't we work around these delays? Well, yes and no. Each public key will need to be generated at least once, so the non-synchronization operations will be slow once in a while whatever we do. But them, they may be pre-calculated so that the user hardly ever notices. And as for synchronization operations, the client creating the new key might publish the matching public key on the blockchain, signed with the newly created signing key. Both these solutions though fall outside of the scope of the projection for the Minimal Viable Product version for spq-sigs. The first one might eventually end up in the libraries, the second one might be more suitable for blockchain specific code that doesn't belong in the spq-sigs libraries.
So what's the path when one client wants to sign a transaction and there are no more one-time signing keys left in the transaction signing key?
- Client A creates a new random salt.
- Client A takes the common private seed
- Client A calculates the big private key for the new transaction signing key using the scheme described above.
- Client A calculates the big public key
- Client A calculates the compact public key
- Client A uses the new key to sign the transaction (index 0)
- Client A used the intermediate key to sign the new compact public key.
- Both signatures get sent together as signature to the transaction.
- The blockchain stores the last signature made (at each level) under the pubkey of the root key for this multi-tree signing key.
Now when client B wants to sign a transaction:
- Client B uses the pubkey of the root key for this multi-tree signing key to request the last signatures at each level.
- Client B discovers it doesn't have the newest transaction signing key.
- Client B takes the salt from the signatures.
- Client A takes the common private seed
- Client A calculates the big private key for the new transaction signing key using the scheme described above.
- Client A calculates the big public key
- Client A calculates the compact public key
- Client A uses the new key to sign the transaction (index 1)
- The signed transaction is sent to the blockchain.
I hope this post both clarifies the solution I am aiming to take to inter-client synchronization and that it takes away the confusion about this project, as expressed by @ahmadmangazap here
This new choice is going to create a bit of a delay, but I'm pretty sure now the result will be the better for it.