Re: [bitcoindev] P2QRH / BIP-360 Update

[Ian Quantum <ianquantum2027@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 11028 bytes --]

FALCON+ is more likely to get NIST approval. They struggled to get the
algorithm over "80 bits of security" even with a significant set of
improvements. I don't know if this affects the aggregation features, it
would take significant research. The dramatic security improvements of
FALCON+ only cost 5% and 0 bytes additional overhead.
https://eprint.iacr.org/2024/1769.pdf

SECP256k1 had significant reductions to it's security over the last 16
years but none of the attacks detailed by Bernstein directly impact the
security as implemented into Bitcoin. (Mitigations and non-interactive
signing, salt and hash were excellent design choices.)

I would suggest delaying FALCON or FALCON+ until standardized. There are
significant weaknesses but no full break. The brittleness of the random
numbers, exposure to inverse function and a lot "weaker than expected"
parameters would suggest caution. Once standardized I would suggest rapid
implementation but not until then.

NTRU Prime is a favored alternate candidate of mine, as communicated
previously. Cryptographers suspect that NIST has again inserted PQC
backdoors following the last 3 public key standards being standardized with
very suspicious parameters. (P224, P256, P384)

I hope we can get some momentum around protecting Bitcoin. 1-6 million
(depending on estimate) BTC have known public keys and while most could
transfer to p2pkh the creation of quantum safe addresses is a strong
signal. The implementation of post quantum cryptography is also required by
many government agencies around the world, including the White House.
Ian Smith
Migrate to Quantum Safety before 2027

On Mon, Feb 24, 2025, 12:53 AM Hunter Beast <hunter@surmount.systems> wrote:

> Hi Jonas,
>
> On Selective Disclosure,
>
> I think we're going to need to add simple multisig semantics to the
> attestation due to its lack of script capability. Would that help? Separate
> multisig semantics like quorum and total would be needed for each class of
> key, so that even if Schnorr signatures can be broken (or one or two of the
> other PQC signatures even), they don't count towards the quorum of the
> other signature types.
>
> On Attestation structure,
>
> What prevents arbitrary data being hashed and then included in the
> attestation is, each signature public key pair must be able to verify the
> transaction message in order to be considered a valid transaction. In other
> words, each public key and signature pair is validated against the
> transaction message upon transaction verification.
>
> On Multisignature 256-bit security,
>
> To be honest, I've read this a couple of times and I will admit I don't
> understand this attack. Can you provide more details on how it works, and
> how it might be possible to mitigate?
>
> On General comments,
>
> I agree with the worst-case transaction verification concern. I'll need to
> put some work into detailing NIST I variants and their signature
> verification times, and then computing worst-case scenarios for different
> discount constants.
>
> On 128-bit security... Yes, I'm coming to realize that too. It's been a
> common point of feedback.
>
> On adding three schemes, there are a couple of advantages of this. First,
> wallets can automatically decide how many signatures to add based on the
> amount being spent. This then acts as a sort of MEV opportunity for miners,
> because the higher the value of the transaction, the more signatures might
> be included, which increases fee revenue. Also, it addresses Matt's concern
> about security assumptions. There's a strong desire for SLH-DSA support,
> even though it's so large. However, from a practicality standpoint
> (thinking of plebs), it will make sense to include the smaller ML-DSA and
> FN-DSA also. While it does increase complexity, I believe that a
> libbitcoinpqc library, as mentioned in the BIP, will serve as a useful
> analogue to libsecp256k1. It's also worth noting that in my position at
> Anduro, I have resources to put into building such a library. Hopefully
> this can help meet the expectation of a well specified and implemented
> consensus level library.
>
> On signature aggregation, yes, I'm excited to see those developments in
> FN-DSA, and maybe we can see that filter into SLH-DSA as well. Hopefully
> those improvements will be ready once the time comes to activate.
>
>
>
> On Friday, February 21, 2025 at 3:18:35 AM UTC-7 Jonas Nick wrote:
>
>> Hi Hunter,
>>
>> Thanks for your work on BIP 360. I think now is a good time to develop
>> and
>> discuss concrete PQ proposals. I have a few questions and comments
>> regarding
>> some aspects of the proposal:
>>
>> Selective disclosure
>> ---
>>
>> From, the output contains a root of a Merkle tree of public key hashes
>> and
>> spending from this output requires revealing the public keys and their
>> corresponding valid signatures. More concretely, if the user creates root
>>
>> R = MerkleRoot([hash(public_key_falcon_1024),
>> hash(public_key_secp256k1)]),
>>
>> they can spend from R by revealing both public keys and corresponding
>> signatures.
>>
>> The BIP also mentions that the public keys can be selectively disclosed:
>>
>> > When spending, if a public key hash is provided in the attestation with
>> an
>> > empty signature, that hash will be used directly in the merkle tree
>> computation
>> > rather than hashing the full public key.
>>
>> What prevents an quantum adversary, upon observing a spend from R, from
>> breaking
>> public_key_secp256k1 and then spending from R by providing
>>
>> [
>> hash(public_key_falcon_1024),
>> empty string,
>> public_key_secp256k1,
>> a secp256k1 signature forgery
>> ]?
>>
>>
>> Attestation structure
>> ---
>>
>> The BIP proposes to an attestation structure alongside the witness which
>> is
>> supposed to contain BIP 360 public keys and signatures (instead having
>> them in
>> the witness). The purpose of this structure is to assign a higher weight
>> discount than the witness. The "Rationale" and "Output Mechanics"
>> sections the
>> BIP describe that, since the attestation structure only contains public
>> keys and
>> signatures, storage of arbitrary data ("inscriptions") is prevented.
>>
>> Leaving aside that there may be creative ways to embed arbitrary data in
>> public
>> keys and signatures as well, selective disclosure of the Merkle tree
>> appears to
>> allow embedding arbitrary data. For instance, a user can create root
>>
>> R = MerkleRoot(data, hash(public_key_secp256k1)]),
>>
>> where data is an arbitrary 256-bit string. What prevents the user from
>> pretending that data is the hash of a public key and providing
>>
>> [
>> data,
>> empty string,
>> public_key_secp256k1,
>> a secp256k1 signature forgery
>> ]
>>
>> in the attestation structure to spend from R?
>>
>>
>> Multi-signature 256-bit security
>> ---
>>
>> The BIP briefly discusses multi-signature scenarios in the script
>> validation
>> section, but the details seem incomplete. From what I can infer, the
>> current
>> specification fails to achieve the claimed 256-bit security.
>>
>> The potential attack would work as follows:
>> 1. The victim provides their public key pk to the adversary.
>> 2. The adversary finds two public keys pk' and pk'' such that
>> MerkleRoot(MultiSig[pk, pk']) = MerkleRoot([pk''])
>> 3. The adversary convinces the victim to send coins to
>> MerkleRoot(MultiSig[pk,
>> pk']) and then steals the coins by opening the Merkle tree root to [pk'']
>> and
>> providing a signature for pk''.
>>
>> Since the Merkle root is the 256-bit output of SHA256, the adversary can
>> find
>> this collision with about 2^128 operations.
>>
>> If I remember correctly, this attack was discussed on the mailing list in
>> the
>> context of segwit and it's the reason why P2WSH (unlike P2PKH) requires
>> 256-bit
>> hashes.
>>
>>
>> General comments
>> ---
>>
>> I think one of the main questions that the BIP does not currently address
>> is how
>> it affects the worst-case validation cost of a block.
>>
>> Regarding your question:
>> > But if the intention was for 256 bits of security, should level V
>> security be
>> > the default?
>>
>> I don't know what Satoshi's intentions were, but the secp256k1
>> specification
>> clearly indicates 128-bit "strength" ([0], Table 1). I believe that's
>> fairly
>> well known in the technical Bitcoin space.
>>
>> I am not quite convinced that adding three PQ schemes to the Bitcoin
>> consensus
>> protocol is a great solution to the problem of not being sure which exact
>> scheme
>> to pick. Offloading this decision to users does not really solve this
>> problem.
>> Moreover, this adds massive complexity and new cryptographic assumptions
>> to the
>> protocol. Remember that one of the main motivations behind libsecp256k1,
>> was
>> that general purpose cryptographic libraries are not well suited for
>> consensus
>> systems. So all new cryptographic schemes added to the consensus protocol
>> need
>> to be exceptionally well specified and implemented. That said, it makes a
>> lot of
>> sense to design a hybrid scheme that also provides security against a
>> classic
>> attacker through an established signature scheme (as BIP 360 proposes).
>>
>> Lastly, I agree that non-interactive aggregation of PQ schemes might be
>> promising, as it could mitigate about signature size and verification
>> cost if
>> aggregation is applied on the transaction level. Recently, there has been
>> progress on the security of aggregating hash-based signatures [1] and
>> Falcon
>> [2].
>>
>> [0] https://www.secg.org/sec2-v2.pdf
>> [1] https://eprint.iacr.org/2025/055
>> [2] https://eprint.iacr.org/2024/311 (Unfortunately, this only beats
>> trivial
>> aggregation (concatenation of signatures) when the number of signatures
>> is
>> greater than about 110)
>>
>> Jonas
>>
>> --
> You received this message because you are subscribed to the Google Groups
> "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5-9570-31967ee339ecn%40googlegroups.com
> <https://groups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5-9570-31967ee339ecn%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CA%2B7C%2BcYY_97y_QsSON5U3y7v4a0usGaGmcD%2Br%3D8Y05p5Cwmp5w%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 12745 bytes --]