bitcoin
BIP-360: QuBit - Pay to Quantum Resistant Hash
This spent several months gathering feedback from the mailing list and from other advisors. This is hopefully polished enough to submit upstream.
Let me know if you have any questions or feedback, and of course feel free to submit suggestions.
Thank you for your time.
@cryptoquick Can you begin to write up the sections currently marked as TBD, along with a backwards compatibility section (to describe incompatibilities, severity, and suggest mitigations, where applicable/relevant)? We've begun to reserve a range of BIP numbers for this topic, pending continued progress here.
@cryptoquick ping for an update here. Have you seen https://groups.google.com/g/bitcoindev/c/p8xz08YTvkw / https://github.com/chucrut/bips/blob/master/bip-xxxx.md? It may be interesting to review each other and possibly collaborate.
I’m wondering whether introducing four different signature schemes at once may be a bit too ambitious.
SPHINCS and Crystals-DILITHIUM are approved by NIST. Antoine Riard specifically requested the inclusion of SPHINCS on the mailing list, and the alternative proposal implements Crystals-DILITHIUM. FALCON is likely to be approved as as a FIPS standard as well, but it's not yet official. SQIsign is very attractive for its small public key and signature sizes, but it is only just recently under review.
Just a note: The content of the BIP should be nearing its final state. Feel free to leave feedback while I work on the test vectors, it'll take me a while since I'm also making changes to rust-bitcoin in order to support P2QRH and transaction attestation, but I don't expect any major changes from my side at this point.
Hey @cryptoquick, just wanted to mention a few quick things:
- While I would consider test vectors and reference implementation necessary for a proposal to move to the "Proposed" status, their lack would not necessarily prevent something to be considered for getting a number and be merged as draft.
- I have a formatting request: Having lines with over 1000 characters makes it really hard to see what changed between pushes and to give review suggestions. May I suggest that you break the lines in text blocks at e.g. 120 characters?
As an example from my own draft, it’s just much easier to see what exactly was changed when the lines are shorter:
- This PR is currently marked as "draft", please click "ready for review" if/when you want editors to take a look. :)
I want to propose an alternative design. Instead of supporting multiple different signature algorithms in the same output and then inferring algorithm based on public key length. Flag signature algorithm based on address prefix, e.g. addresses that start with bc1f only accept FALCON-1024 public keys and signatures.
- This makes it straightforward to add new post-quantum signature algorithms and lets you streamline this design by only needing to support one post-quantum signature algorithm.
- This avoids using length as a signaling mechanism. Currently length works, but what if two algorithms have the same length public key? Do we lengthen one?
- Supporting multiple signature algorithms in the same output is likely to increase complexity for other protocols. Say a payment channel where the two parties are using different signature algorithms. I don't see this as a strong reason not to do this, but I think the BIP needs a justification for this additional complexity.
Is the reason you are doing multisig outside of script, because of the stack element limitations of some these bigger signatures? Are there any issues with the values on the attestation stack being larger than 520?
Sorry for coming late with this important PR, we have just shared 3 proposed pqc algorithms that guarantee elimination of quantum computer risk.
https://delvingbitcoin.org/t/implemented-post-quantum-cryptography-pqc-feature-into-bitcoin-core/1320
Sorry for coming late with this important PR, we have just shared 3 proposed pqc algorithms that guarantee elimination of quantum computer risk.
https://delvingbitcoin.org/t/implemented-post-quantum-cryptography-pqc-feature-into-bitcoin-core/1320
That's a great start! I see from your documentation here you're intending to use the same PQC signature algorithms we've selected, which is validating of the approach recommended for this BIP.
I want to propose an alternative design. Instead of supporting multiple different signature algorithms in the same output and then inferring algorithm based on public key length. Flag signature algorithm based on address prefix, e.g. addresses that start with
bc1fonly accept FALCON-1024 public keys and signatures.
The problem with that approach is that there's only so many OP_NUMs to prefix the address type with for each signature type. If new signature algorithms were added, I would imagine they would be added in batches, so that bc1f would indicate a superset of multiple algorithms.
- This makes it straightforward to add new post-quantum signature algorithms and lets you streamline this design by only needing to support one post-quantum signature algorithm.
- This avoids using length as a signaling mechanism. Currently length works, but what if two algorithms have the same length public key? Do we lengthen one?
Yes, we would lengthen one.
- Supporting multiple signature algorithms in the same output is likely to increase complexity for other protocols. Say a payment channel where the two parties are using different signature algorithms. I don't see this as a strong reason not to do this, but I think the BIP needs a justification for this additional complexity.
In the case of a payment channel, it's a 2-of-2 multisig agreed to by both parties. If either party finds the signature algorithms proposed unacceptable, the channel simply won't be funded.
Is the reason you are doing multisig outside of script, because of the stack element limitations of some these bigger signatures? Are there any issues with the values on the attestation stack being larger than 520?
Partly for that reason, and also, because I want this to use stricter validation rules than all that script expresses.
Hi, Sorry for the ping, This is too complicated for me. Is there no way to simplify or generalize this?
Hi, Sorry for the ping, This is too complicated for me. Is there no way to simplify or generalize this?
Perhaps a good summary is this:
In this BIP we suggest a new address format beginning with bc1r that introduces the capability for users to generate addresses that can receive payments signed using quantum-resistant keys and signatures.
It really is that simple, but there are the details for why this needs to happen and how it should happen and this tries to cover those in a comprehensive enough manner, or at least, as comprehensive as we can be without test vectors.
@jonatack Why did you re-add the draft designation? From what I understand, @murchandamus recommended that be changed: https://github.com/bitcoin/bips/pull/1670#issuecomment-2523737288
@jonatack Why did you re-add the draft designation? From what I understand, @murchandamus recommended that be changed: #1670 (comment)
I see. The PR title doesn't refer to the GitHub status of "draft, not ready for review", only that it is a BIP draft as yet without a number -- once there is a number, then the title becomes "BIP <number>: ..." instead. I unified a few titles yesterday to make it easier for me to follow the various PRs.
Are there any remaining obstacles keeping this from getting a BIP number?
I have a range of numbers in mind for QC resistance BIPs to run by the other editors and am re-reviewing here.
Sorry for being late, but was any thought been given to the feasibility of cryptographic multisig for the algorithms named?
Raccoon has a few threshold signature protocols which can drop in with the originally defined Raccoon (so long as parameters are mutual).
https://eprint.iacr.org/2024/1291 https://eprint.iacr.org/2024/184 https://eprint.iacr.org/2024/496
This would avoid the on-chain cost of several signatures and provide indistinguishability.
@kayabaNerve This BIP supports multisig. Maybe threshold signatures can be added once they're more mature.
I'm aware of the on-chain multisig possible with this proposal, which would have non-trivial scalability limits.
Raccoon was one of the PQ signature algorithms submitted to the NIST competition for additional schemes, alongside SQIsign. It isn't explicitly/inherently a threshold signature and just has threshold signature schemes available. I'd question if it is too immature given the (currently rather) unique benefits provided.
@murchandamus @vostrnad Thank you for taking the time to review. I realize this is a long BIP and there's a lot to go over, but I think it's important as the first quantum BIP to go into the problem in detail. In that way it's similar to BIP-52.
Regardless, I've made updates to satisfy your recommendations the best I can, here's a diff for your convenience: https://github.com/bitcoin/bips/pull/1670/commits/0fdd8c3edc9e563bcf5a7cb0cc93e6f428b948d8
For context, I also intend to introduce a QuBit activation BIP, and a P2TRH BIP separate from QuBit. Additionally, I realize that there's some sections here that are underspecified. That will come with test vectors and an implementation, which I'm working towards.
the main problem that I see is decryptor wallets, as well as a master private key and a master public key, curves allow us to use something like this, but post-quantum algorithms do not provide such an opportunity (in current implementations)
if use clasic logic with key pool , we simple get key pairs and use them
but how are we going to associate a key obtained from master keys with post quantum keys?
@mraksoll4 All PQC algos will of course need to be compatible with BIP-32 HD wallet-style key derivation. There are definitely PQC libraries out there that just assume you'll never want to bring your own entropy, and so they don't provide a field or argument to provide that, but the intention behind the implementation of this BIP is that there will be a custom PQC library for bitcoin specifically that will implement things like this. So, your concern, while valid, is an implementation detail, and doesn't really have much bearing on the BIP itself.
@mraksoll4 All PQC algos will of course need to be compatible with BIP-32 HD wallet-style key derivation. There are definitely PQC libraries out there that just assume you'll never want to bring your own entropy, and so they don't provide a field or argument to provide that, but the intention behind the implementation of this BIP is that there will be a custom PQC library for bitcoin specifically that will implement things like this. So, your concern, while valid, is an implementation detail, and doesn't really have much bearing on the BIP itself.
Well, we have no problems with private keys, and also with generating from a seed, I have already implemented for experiments on the liboqs library the use of my own seed for falcon and dilithium to obtain a pair of keys, as well as obtaining a public key from a private one.
There are also no problems with multi-signature, the signature itself can be merged.
but we have a problem with obtaining public keys from the master public key ; due to the design of post quantum algorithms, we do not have the ability to obtain public keys from other public keys through predictable mathematical operations as in ecdsa.
although perhaps I don’t fully understand how we get the master public key.
how start you can see at base examle .
https://github.com/open-quantum-safe/liboqs/pull/2031
first we need to solve the problem of key hierarchy, or we will have to forget about generating public keys without cration the private key, although for example in Falcon you don't need the entire private key but only part of it to reconstruct the public key
/*
* This function reconstructs the public key from a given private key.
* It decodes the private key components (f and g) from the secret key
* and uses them to regenerate the corresponding public key (h).
* The generated public key is then encoded into the provided pk array.
*
* public (pk): The output buffer where the public key will be stored (must be at least PQCLEAN_FALCON512_CLEAN_CRYPTO_PUBLICKEYBYTES in size).
* private (sk): The input secret key (private key) in byte array format (must be PQCLEAN_FALCON512_CLEAN_CRYPTO_SECRETKEYBYTES in size).
* Return value: 0 on success, -1 on error.
*/
int
PQCLEAN_FALCON1024_CLEAN_crypto_sign_pubkey_from_privkey(
uint8_t *pk, const uint8_t *sk) {
union {
uint8_t b[FALCON_KEYGEN_TEMP_10];
uint64_t dummy_u64;
fpr dummy_fpr;
} tmp;
int8_t f[1024], g[1024], F[1024];
uint16_t h[1024];
size_t u, v;
/*
* Decode the private key.
*/
if (sk[0] != 0x50 + 10) {
return -1;
}
u = 1;
v = PQCLEAN_FALCON1024_CLEAN_trim_i8_decode(
f, 10, PQCLEAN_FALCON1024_CLEAN_max_fg_bits[10],
sk + u, PQCLEAN_FALCON1024_CLEAN_CRYPTO_SECRETKEYBYTES - u);
if (v == 0) {
return -1;
}
u += v;
v = PQCLEAN_FALCON1024_CLEAN_trim_i8_decode(
g, 10, PQCLEAN_FALCON1024_CLEAN_max_fg_bits[10],
sk + u, PQCLEAN_FALCON1024_CLEAN_CRYPTO_SECRETKEYBYTES - u);
if (v == 0) {
return -1;
}
/*
* Reconstruct the public key using f and g by calling the compute_public function.
*/
if (!PQCLEAN_FALCON1024_CLEAN_compute_public(h, f, g, 10, tmp.b)) {
return -1;
}
/*
* Encode public key.
*/
pk[0] = 0x00 + 10;
v = PQCLEAN_FALCON1024_CLEAN_modq_encode(
pk + 1, PQCLEAN_FALCON1024_CLEAN_CRYPTO_PUBLICKEYBYTES - 1,
h, 10);
if (v != PQCLEAN_FALCON1024_CLEAN_CRYPTO_PUBLICKEYBYTES - 1) {
return -1;
}
return 0;
}
Have you read the mail list discussion at https://groups.google.com/g/bitcoindev/c/8O857bRSVV8? It might be good to weigh in there if you're inclined.
I did write a response in the mailing list many months ago, but it never showed up. Not sure what happened. I really don't want to repeat my analysis... It was a good amount of work that was lost.
And is it not in your send folder?
I composed it in the Google GUI ... Last I checked there wasn't a way to check back on it.
If you sent it from there, it should be in your "Sent" or "Drafts" folder, unless you deleted it.