Date: Mon, 15 Mar 2021 14:24:01 -1000
From: "David A. Harding" <dave@dtrt.org>
To: Luke Dashjr <luke@dashjr.org>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20210316002401.zlfbc3y2s7vbrh35@ganymede>
References: <202103152148.15477.luke@dashjr.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
 protocol="application/pgp-signature"; boundary="qhw546z5jk5oahgs"
Content-Disposition: inline
In-Reply-To: <202103152148.15477.luke@dashjr.org>
User-Agent: NeoMutt/20180716
Subject: Re: [bitcoin-dev] PSA: Taproot loss of quantum protections
Precedence: list


--qhw546z5jk5oahgs
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

On Mon, Mar 15, 2021 at 09:48:15PM +0000, Luke Dashjr via bitcoin-dev wrote:
> Note that in all circumstances, Bitcoin is endangered when QC becomes
> a reality [...] it could very well become an unrecoverable situation
> if QC go online prior to having a full quantum-safe solution.

The main concern seems to be someone developing, in secret, a quantum
computer with enough capacity to compromise millions of keys and then
deciding to use the most powerful and (probably) expensive computer ever
developed to steal coins that will almost immediately lose most or all
of their value.

That's certainly a threat we should consider, but like other "movie
plot" threats, I think we should weigh its unlikeliness in comparison
to the people who are losing smaller amounts of money on a regular basis
right now because we don't already have taproot---people who don't use
multisig, or contracts with threshold reduction timeout clauses, or
certain types of covenants because the contingencies these types of
scripts protect against come at too great a cost in fees for the typical
case where no contingencies are needed.

We have many ideas about how to mitigate the risk of effective quantum
computing attacks, from emergency protection to long-term solutions, so
it seems to me that the real risk in the movie plot scenario comes
entirely from *secret advances* in quantum computing.  Other similar
risks for Bitcoin exist, such as secret discoveries about how to
compromise the hash functions Bitcoin depends on.  One way to help
control those risks is to pay a public bounty to anyone who provably and
publicly discloses the secret advance (ideally while allowing the leaker
to remain anonymous).  Several years ago, Peter Todd created a series of
Bitcoin addresses that does exactly that.[1]

For example, if you pay 35Snmmy3uhaer2gTboc81ayCip4m9DT4ko, then
anyone[2] who can prove a collision attack against Bitcoin's primary
hash function, SHA256, will be able to claim the bitcoins you and other
people sent to that address.  Their claim of the funds will publicly
demonstrate that someone can create a SHA256 collision, which is an
attack we currently believe to be impractical.  This system was
demonstrated to work about four years ago[3] when the collision bounty
for the much weaker SHA1 function was claimed.[4]

We can already create an output script with a Nothing Up My Sleeve
(NUMS) point that would provide a trustless bounty to anyone proving the
capability to steal any P2PK-style output with secp256k1's 128-bit
security.  I curious about whether anyone informed about ECC and QC
knows how to create output scripts with lower difficulty that could be
used to measure the progress of QC-based EC key cracking.  E.g.,
NUMS-based ECDSA- or taproot-compatible scripts with a security strength
equivalent to 80, 96, and 112 bit security.

That way the people and businesses concerned about QC advances could
send a few BTC to those addresses to create a QC early warning system
that would allow us to continue confidently working on EC-based
protocols for now but also objectively alert us to when we need to shift
to working on post-QC protocols for the future.

Thank you,

-Dave

[1] https://bitcointalk.org/index.php?topic=293382.0

[2] Anyone claiming the reward may need to mine their own transaction to
    protect it against rewriting.  In the worst case, they may need to
    mine at a depth of several blocks or share their reward with miners
    to prevent sniping reorgs.

[3] https://blockstream.info/tx/8d31992805518fd62daa3bdd2a5c4fd2cd3054c9b3dca1d78055e9528cff6adc

[4] To the best of my knowledge, nothing in Bitcoin ever depended
    significantly on SHA1, and especially not on SHA1 collision
    resistance, which was known to be weak even in 2009 when Nakamoto
    first published the Bitcoin software.

--qhw546z5jk5oahgs
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQIzBAEBCgAdFiEEgxUkqkMp0LnoXjCr2dtBqWwiadMFAmBP+qEACgkQ2dtBqWwi
adOOGg//ckjfCJ/YDyhdwNBs0ai2UBvzAhA0dMDH0Oto79zG7b96Jzy6Tg+RxOtx
6G8fI42+j/IVbdur92lvxSgtEnelH31eURwE4kKd47rxws6kCyojieeIjOX1PXPv
XVylC2HKxDKUIAorkClQZcj1hxILwIsGoe/QPRzH/z4OyMBiikmsaTdMmNN/6usn
paHYahgqZZSOFkPmnSlnhbyqs+poerGcvW9V2eQ35e5AiFOd0sJ4mLJlP+USP8hG
nmipnl/uNZNBKqdG7b2k/8BMbBEjZvUrOEzICKduOhv1LDO7PhfI7XjEJZbikyd8
rbE1FBu6GOy+/sjQz2uE3JbPFdJuaoaOcm/dMQkszM5DgSta5SL3NQ78mFCRWT9G
QpXbzQqsADkFlMnJRta2u9QwacYrlpUfb5eMoaCtaOz1iuDg59qlBHbuWdO4m2dN
W1qfbuVvYfRhyFoz6dhrnFUEoHoCOmAAKTq9PgcHZXiEz3nKvXtGuW19PNm7KMRy
FOshO6B0591YSfVd/OQfvmgknQMNz6qb0UZOlCw/ZzvGpUIUz6dzauRLoQfAWjYe
Len8V4gtX6aDfbE/MhYRdSqO3rgiiXvQOo/5nkvrGByD0jZzz2c2iVFTeDJnNpeG
wedDydCUFJrbiGcXQEUDrwx7ewsXVvIuJcPmhaxvJJdkr5ZDjC4=
=ieJ0
-----END PGP SIGNATURE-----

--qhw546z5jk5oahgs--