Input needed: Simple Post-Quantum Signatures; derived or random sub-tree seeds/salts

While I realize most of the people following my blog, and most of the community that I post this blog post in might not be so deep into crypto to be able to help me out, I hope there is going to be at least one of you with sufficient insights into digital signatures, secure hashes, and designed-for-hey-reuse blockchains such #hive to be able to help me pick the right path.

As you may know, I am making (slowish) progress with the C++ implementation of spq-sigs. I recently posted about working multi-tree signatures, and since then got signature serialization and de-serialization working and made a small start at signing key serialization.

It's with the practical use of multi-tree signing keys, and what different use cases and expectations from the library mean for the implementation, that I need some desperate input. Let me try to explain.

When you as a user, for example of the HIVE blockchain, first create or import a hash-based signing key that works with the multi-tree concept, you will have what in fact is a tiny stack of secret keys, with for each one other than the root key, a signed public key. If the multi-tree signing key is a three tree key, this means you have the following:

  1. A root key
  2. An intermediate key signed by your root key
  3. A transaction signing key signed by your intermediate key.

This is all fine so for, but remember signing something with a hash based signing key depletes the key, so after a number of transactions, the transaction signing key gets depleted, and you need to replace your transaction signing key by a new one. So you create a new key, sign it with your intermediate key, and you are good to go. Or are you?

Everything will be nice and dandy if you only use your signing key from one computer. But what if you use two computers? What if you talk to the blockchain with your account from three, four or even more different computers, all holding a copy of your wallet?

Well, in that case there may be a problem. Once a new transaction signing key is created, that key, as things are implemented right now, will exist only on that one computer. So now, when any of the other computers needs to sign a transaction, all it can do is create its own transaction signing key with the intermediate signing key. That will work, for a while, until the initial intermediate key gets exhausted too, and the different computers will need to do the same thing once more, but now creating new and distinct intermediate keys.

While this may all work quite reasonable, there might be reasons why this wouldn't be ideal. For one, usage may not be similar between the different computers, leaving corners of the key space unused while others get exhausted. The blockchain may need to keep more state for wallets to be able to prevent copies of the signing key from using an already used part of a signing key and hurting the confidentiality and security of the signing key.

An option might be to use a single tree master key that isn't used for anything but the creation of multi-tree keys meant for specific clients. There are some security advantages to this as it could allow revocation of sorts on the chain, and for me as developer of the library this would be a great option as I would have to do absolutely nothing. The problem wouldn't be a library problem but a chain architecture problem.

Another option would be to opt for new tree creation from a common seed. Instead of picking a fully random seed and a fully random salt for creating a new transaction signing key, resulting in different client computers ending up with different sub keys, each client will be able to reproduce the exact same new sub key.

This however would mean less lifetime entropy in a signing key lifetime. As the salt is public anyway, we could still make the salt fully random, but the seed for the new key would have to be something like a secure salted hash of our new salt, the common shared seed, and maybe the signing index of the signature of this key that we are going to make.

So my question: What do you guys think?

  1. The extra chain-side state is not a problem and neither is sparse and diverse use of the signing space, keep things as they are now.
  2. Assume the on-chain implementation will use a single-tree master key. Not a library problem.
  3. Go for single-seed derived reproducible sub-key creation. Fix it in the library, even if that means less entropy and thus the potential need for larger hashing primitives and thus larger signatures.
  4. All three options are missing the point, you know a better option and are going to tell me.

Looking forward to your insights.

P.s, if you don't have a HIVE account and can give me feedback, drop me a message on Twitter

H2
H3
H4
3 columns
2 columns
1 column
1 Comment
Ecency