From: Antoine Riard <antoine.riard@gmail•com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: [bitcoindev] Re: Proposing a P2QRH BIP towards a quantum resistant soft fork
Date: Sun, 16 Jun 2024 18:07:46 -0700 (PDT) [thread overview]
Message-ID: <87b4e402-39d8-46b0-8269-4f81fa501627n@googlegroups.com> (raw)
In-Reply-To: <d78f5dc4-a72d-4da4-8a24-105963155e4dn@googlegroups.com>
[-- Attachment #1.1: Type: text/plain, Size: 6408 bytes --]
Hi Hunter Beast,
I think any post-quantum upgrade signature algorithm upgrade proposal would
grandly benefit to have
Shor's based practical attacks far more defined in the Bitcoin context. As
soon you start to talk about
quantum computers there is no such thing as a "quantum computer" though a
wide array of architectures
based on a range of technologies to encode qubits on nanoscale physical
properties.
This is not certain that any Shor's algorithm variant works smoothly
independently of the quantum computer
architecture considered (e.g gate frequency, gate infidelity, cooling
energy consumption) and I think it's
an interesting open game-theory problem if you can concentrate a sufficiant
amount of energy before any
coin owner moves them in consequence (e.g seeing a quantum break in the
mempool and reacting with a counter-spend).
In my opinion, one of the last time the subject was addressed on the
mailing list, the description of the state of
the quantum computer field was not realistic and get into risk
characterization hyperbole talking about
"super-exponential rate" (when indeed there is no empirical
realization that distinct theoretical advance on
quantum capabilities can be combined with each other) [1].
On your proposal, there is an immediate observation which comes to mind,
namely why not using one of the algorithm
(dilthium, sphincs+, falcon) which has been through the 3 rounds of NIST
cryptanalysis. Apart of the signature size,
which sounds to be smaller, in a network of full-nodes any PQ signature
algorithm should have reasonable verification
performances.
Lastly, there is a practical defensive technique that can be implemented
today by coin owners to protect in face of
hyptothetical quantum adversaries. Namely setting spending scripts to
request an artificially inflated witness stack,
as the cost has to be burden by the spender. I think one can easily do that
with OP_DUP and OP_GREATERTHAN and a bit
of stack shuffling. While the efficiency of this technique is limited by
the max consensus size of the script stack
(`MAX_STACK_SIZE`) and the max consensus size of stack element
(`MAX_SCRIPT_ELEMENT_SIZE`), this adds an additional
"scarce coins" pre-requirement on the quantum adversarise to succeed.
Shor's algorithm is only defined under the
classic ressources of computational complexity, time and space.
Best,
Antoine
[1] https://freicoin.substack.com/p/why-im-against-taproot
Le vendredi 14 juin 2024 à 15:30:54 UTC+1, Hunter Beast a écrit :
> Good points. I like your suggestion for a SPHINCS+, just due to how mature
> it is in comparison to SQIsign. It's already in its third round and has
> several standards-compliant implementations, and it has an actual
> specification rather than just a research paper. One thing to consider is
> that NIST-I round 3 signatures are 982 bytes in size, according to what I
> was able to find in the documents hosted by the SPHINCS website.
>
> https://web.archive.org/web/20230711000109if_/http://sphincs.org/data/sphincs+-round3-submission-nist.zip
>
> One way to handle this is to introduce this as a separate address type
> than SQIsign. That won't require OP_CAT, and I do want to keep this soft
> fork limited in scope. If SQIsign does become significantly broken, in this
> hopefully far future scenario, I might be supportive of an increase in the
> witness discount.
>
> Also, I've made some additional changes based on your feedback on X. You
> can review them here if you so wish:
>
> https://github.com/cryptoquick/bips/pull/5/files?short_path=917a32a#diff-917a32a71b69bf62d7c85dfb13d520a0340a30a2889b015b82d36411ed45e754
>
> On Friday, June 14, 2024 at 8:15:29 AM UTC-6 Pierre-Luc Dallaire-Demers
> wrote:
>
>> SQIsign is blockchain friendly but also very new, I would recommend
>> adding a hash-based backup key in case an attack on SQIsign is found in the
>> future (recall that SIDH broke over the span of a weekend
>> https://eprint.iacr.org/2022/975.pdf).
>> Backup keys can be added in the form of a Merkle tree where one branch
>> would contain the SQIsign public key and the other the public key of the
>> recovery hash-based scheme. For most transactions it would only add one bit
>> to specify the SQIsign branch.
>> The hash-based method could be Sphincs+, which is standardized by NIST
>> but requires adding extra code, or Lamport, which is not standardized but
>> can be verified on-chain with OP-CAT.
>>
>> On Sunday, June 9, 2024 at 12:07:16 p.m. UTC-4 Hunter Beast wrote:
>>
>>> The motivation for this BIP is to provide a concrete proposal for adding
>>> quantum resistance to Bitcoin. We will need to pick a signature algorithm,
>>> implement it, and have it ready in event of quantum emergency. There will
>>> be time to adopt it. Importantly, this first step is a more substantive
>>> answer to those with concerns beyond, "quantum computers may pose a threat,
>>> but we likely don't have to worry about that for a long time". Bitcoin
>>> development and activation is slow, so it's important that those with low
>>> time preference start discussing this as a serious possibility sooner
>>> rather than later.
>>>
>>> This is meant to be the first in a series of BIPs regarding a
>>> hypothetical "QuBit" soft fork. The BIP is intended to propose concrete
>>> solutions, even if they're early and incomplete, so that Bitcoin developers
>>> are aware of the existence of these solutions and their potential.
>>>
>>> This is just a rough draft and not the finished BIP. I'd like to
>>> validate the approach and hear if I should continue working on it, whether
>>> serious changes are needed, or if this truly isn't a worthwhile endeavor
>>> right now.
>>>
>>> The BIP can be found here:
>>> https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki
>>>
>>> Thank you for your time.
>>>
>>>
--
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 on the web visit https://groups.google.com/d/msgid/bitcoindev/87b4e402-39d8-46b0-8269-4f81fa501627n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 14060 bytes --]
next prev parent reply other threads:[~2024-06-17 1:24 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-06-08 21:04 [bitcoindev] " Hunter Beast
2024-06-14 13:51 ` [bitcoindev] " Pierre-Luc Dallaire-Demers
2024-06-14 14:28 ` Hunter Beast
2024-06-17 1:07 ` Antoine Riard [this message]
2024-06-17 20:27 ` hunter
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87b4e402-39d8-46b0-8269-4f81fa501627n@googlegroups.com \
--to=antoine.riard@gmail$(echo .)com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox