path: root/a4/14e9cd434a2e9a855ba73bda4e556c6d1454d5

Return-Path: <natanael.l@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 72DCF10B6
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 24 Jan 2018 12:51:49 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f51.google.com (mail-wm0-f51.google.com [74.125.82.51])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 06973360
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 24 Jan 2018 12:51:47 +0000 (UTC)
Received: by mail-wm0-f51.google.com with SMTP id g1so8267540wmg.2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 24 Jan 2018 04:51:47 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to
	:cc; bh=9/7XxFk1qoeinzkl5nuLtc0nRu8aFj6zKcLGeGl4xjQ=;
	b=kWATUFz24ZGKQEMHkW7zX7XGGPHThUk4bGVv/MQLhFJFk4BWVRnsNMP4jrdD/dd0tr
	Qj3/Abw2lRfHZaaVyTvx+ejjrw5XYp4Yz18Q9RRS/gIdyHqU2Xt5rIHgmKmVUYyGWzHM
	vGXFfhRdskwjDtvvNsYzLM0F6GH/g7SJboAG8AVVH2KxudANy5XKOAtuHZOJR0d4vJRd
	HSE+BrsoVv4IY5mjwdh01GyuKhX0RC8KnfNtO9+WpUf+HzdsQo45/9fJoRoV2/q5S4BC
	/afFNDKdHY84Cc4Edb/vmFdjMkpRL+9q1UhArJ4McTAi5n95LpKqnARhUr2JaFb1vuK7
	R1Yg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to:cc;
	bh=9/7XxFk1qoeinzkl5nuLtc0nRu8aFj6zKcLGeGl4xjQ=;
	b=hOTW8/3EOxP1UVUvXpQIgikeqYrx9ngGjlCA+5SFuw2PL/OjLCMnzkA7yfRFqEmuN2
	JaYT60cIuBli7dyV+SZdiC3xMiqAHKN9jeNaX98n9Osp0m9eSUxQ+2A9XWgyCMk2VvFM
	+tadzeUQQ4II0y83xVv9byrRPCLb6v/DtitS3iK7bK7giaqqTQ1BZ1nQi2LONiaP7yKw
	/saxDAFhPxmuf/gQW155+6pbIGzDECLJ57EH08ZrHC0DbRFknNpVIs0hLXrtGh55v3oW
	R4w/8DsJb6vWp17fFJ+Wf2x3DGuKm6z0VmoAjUTXam2OFQGGT00UC8Hi6E1az0PRoL9l
	1ATg==
X-Gm-Message-State: AKwxytdmVNfABP5P9Gv8eQ7YF1/m7Heb1b9Ns9V8jPXxeVu1UC4Y0R7u
	qNggO9fsMA9Zgrt1x/N6yAcvH7Lg89n5ubxAm8M=
X-Google-Smtp-Source: AH8x2245s+F7AE9goincpH5f++Au9v1pCnfc/Uk9FWNan3VwbdgKcc3dKCZ1HTiTy/s7pIuHTKP2RgjHseA82h6r5lU=
X-Received: by 10.80.212.154 with SMTP id s26mr23518336edi.268.1516798306550; 
	Wed, 24 Jan 2018 04:51:46 -0800 (PST)
MIME-Version: 1.0
Received: by 10.80.169.103 with HTTP; Wed, 24 Jan 2018 04:51:45 -0800 (PST)
Received: by 10.80.169.103 with HTTP; Wed, 24 Jan 2018 04:51:45 -0800 (PST)
In-Reply-To: <CAAS2fgTNcCB2mfvCBhC_AhgxX=g8feYguGHN_VPWW0EoOOxMyA@mail.gmail.com>
References: <CAAS2fgTXg5kk6TyUM9dS=tf5N0_Z-GKVmzMLwTW1HxUgrqdo+Q@mail.gmail.com>
	<20180123064419.GA1296@erisian.com.au>
	<CAAS2fgSy8qg71M6ZOr=xj=W6y2Jbz8hwygZOUYv-Brkt0JwVaQ@mail.gmail.com>
	<20180123222229.GA3801@erisian.com.au>
	<CAAS2fgTNcCB2mfvCBhC_AhgxX=g8feYguGHN_VPWW0EoOOxMyA@mail.gmail.com>
From: Natanael <natanael.l@gmail.com>
Date: Wed, 24 Jan 2018 13:51:45 +0100
Message-ID: <CAAt2M1-oh=_Ro6+Srit0XYburK_abQgJiW0Jx=nmNyeToA2rSA@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>,
	Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="94eb2c1af00c420a0d0563852003"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
	RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Wed, 24 Jan 2018 12:51:49 -0000

--94eb2c1af00c420a0d0563852003
Content-Type: text/plain; charset="UTF-8"

Den 23 jan. 2018 23:45 skrev "Gregory Maxwell via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org>:

On Tue, Jan 23, 2018 at 10:22 PM, Anthony Towns <aj@erisian.com.au> wrote:
> Hmm, at least people can choose not to reuse addresses currently --
> if everyone were using taproot and that didn't involve hashing the key,

Can you show me a model of quantum computation that is conjectured to
be able to solve the discrete log problem but which would take longer
than fractions of a second to do so? Quantum computation has to occur
within the coherence lifetime of the system.


Quantum computers works like randomized black boxes, you run them in many
cycles with a certain probability of getting the right answer.

The trick to them is that they bias the probabilities of their qubits to
read out the correct answer *more often than at random*, for many classes
of problems. You (likely) won't get the correct answer immediately.

https://en.wikipedia.org/wiki/Quantum_computing

Quoting Wikipedia:

> An algorithm is composed of a fixed sequence of quantum logic gates and a
problem is encoded by setting the initial values of the qubits, similar to
how a classical computer works. The calculation usually ends with a
measurement, collapsing the system of qubits into one of the 2 n
{\displaystyle 2^{n}} 2^{n} pure states, where each qubit is zero or one,
decomposing into a classical state. The outcome can therefore be at most n
{\displaystyle n} n classical bits of information (or, if the algorithm did
not end with a measurement, the result is an unobserved quantum state).
Quantum algorithms are often probabilistic, in that they provide the
correct solution only with a certain known probability.

A non programmed QC is essentially an RNG driven by quantum effects. You
just get random bits.

A programmed one will need to run the and program over and over until you
can derive the correct answer from one of its outputs. How fast this goes
depends on the problem and the algorithm.

Most people here have heard of Grover's algorithm, it would crack a
symmetric 256 bit key in approximately 2^128 QC cycles - completely
impractical. Shor's algorithm is the dangerous one for ECC since it cracks
current keys at "practical" speeds.

https://eprint.iacr.org/2017/598 - resource estimates, in terms of size of
the QC. Does not address implementation speed.

I can't seem to find specific details, but I remember having seen estimates
of around 2^40 cycles in practical implementations for 256 bit ECC (this
assumes use error correction schemes, QC machines with small some
imperfections, and more). Unfortunately I can't find a source for this
estimate. I've seen lower estimates too, but they seem entirely
theoretical.

Read-out time for QC:s is indeed insignificant, in terms of measuring the
state of the qubits after a complete cycle.

Programming time, time to prepared for readout, reset, reprogramming, etc,
that will all take a little longer. In particular with more qubits
involved, since they all need to be in superposition and be coherent at
some point. Also, you still have to parse all the different outputs (on a
classical computer) to find your answer among them.
Very very optimistic cycle speeds are in the GHz range, and then that's
still on the order of ~15 minutes for 2^40 cycles. Since we don't even have
a proper general purpose QC yet, nor one with usable amounts of qubits, we
don't even know if we can make them run at a cycle per second, or per
minute...

However if somebody *does* build a fast QC that's nearly ideal, then
Bitcoin's typical use of ECC would be in immediate danger. The most
optimistic QC plausible would indeed be able to crack keys in under a
minute. But my own wild guess is that for the next few decades none will be
faster than a runtime measured in weeks for cracking keys.

---

Sidenote, I'm strongly in favor of implementing early support for the
Fawkes scheme mentioned previously.

We could even patch it on top of classical transactions - you can only
break ECC with a known public key, so just commit to the signed transaction
into the blockchain before publishing it. Then afterwards you publish the
transaction itself, with a reference to the commitment. That transaction
can then be assumed legit simply because there was no room to crack the key
before the commitment, and the transaction matches the commitment.

Never reuse keys, and you're safe against QC:s.

Sidenote: There's a risk here with interception, insertion of a new
commitment and getting the new transaction into the blockchain first.
However, I would suggest a mining policy here were two known conflicting
transactions with commitments are resolved such that the one with the
oldest commitment wins. How to address detection of conflicting
transactions with commitments older than confirmed transactions isn't
obvious. Some of these may be fully intentional by the original owner, such
as a regretted transaction.

Another sidenote: HD wallets with hash based hardened derivation should
also be safe in various circumstances, near completely safe in the case
where they're defined such that knowing an individual private key, which is
not the root key,  is not enough to derive any other in your wallet.
HD schemes that only prevent derivation of parent keypairs in the tree
would require that you never use a key derived from another already used or
published public key.

--94eb2c1af00c420a0d0563852003
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div><div class=3D"gmail_extra"><br><div class=3D"gmail_q=
uote">Den 23 jan. 2018 23:45 skrev &quot;Gregory Maxwell via bitcoin-dev&qu=
ot; &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"=
_blank">bitcoin-dev@lists.linuxfounda<wbr>tion.org</a>&gt;:<br type=3D"attr=
ibution"><blockquote class=3D"m_3610986213815081737m_7259154457222964248quo=
te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"=
><div class=3D"m_3610986213815081737m_7259154457222964248quoted-text">On Tu=
e, Jan 23, 2018 at 10:22 PM, Anthony Towns &lt;<a href=3D"mailto:aj@erisian=
.com.au" target=3D"_blank">aj@erisian.com.au</a>&gt; wrote:<br>
&gt; Hmm, at least people can choose not to reuse addresses currently --<br=
>
&gt; if everyone were using taproot and that didn&#39;t involve hashing the=
 key,<br>
<br>
</div>Can you show me a model of quantum computation that is conjectured to=
<br>
be able to solve the discrete log problem but which would take longer<br>
than fractions of a second to do so? Quantum computation has to occur<br>
within the coherence lifetime of the system.</blockquote></div></div></div>=
<div dir=3D"auto"><br></div><div dir=3D"auto">Quantum computers works like =
randomized black boxes, you run them in many cycles with a certain probabil=
ity of getting the right answer.</div><div dir=3D"auto"><br></div><div dir=
=3D"auto">The trick to them is that they bias the probabilities of their qu=
bits to read out the correct answer *more often than at random*, for many c=
lasses of problems. You (likely) won&#39;t get the correct answer immediate=
ly.=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto"><a href=3D"htt=
ps://en.wikipedia.org/wiki/Quantum_computing" target=3D"_blank">https://en.=
wikipedia.org/wiki/<wbr>Quantum_computing</a><br></div><div dir=3D"auto"><b=
r></div><div dir=3D"auto">Quoting Wikipedia:=C2=A0</div><div dir=3D"auto"><=
br></div><div dir=3D"auto">&gt;=C2=A0An algorithm is composed of a fixed se=
quence of quantum logic gates and a problem is encoded by setting the initi=
al values of the qubits, similar to how a classical computer works. The cal=
culation usually ends with a measurement, collapsing the system of qubits i=
nto one of the 2 n {\displaystyle 2^{n}} 2^{n} pure states, where each qubi=
t is zero or one, decomposing into a classical state. The outcome can there=
fore be at most n {\displaystyle n} n classical bits of information (or, if=
 the algorithm did not end with a measurement, the result is an unobserved =
quantum state). Quantum algorithms are often probabilistic, in that they pr=
ovide the correct solution only with a certain known probability.</div><div=
 dir=3D"auto"><br></div><div dir=3D"auto">A non programmed QC is essentiall=
y an RNG driven by quantum effects. You just get random bits.=C2=A0</div><d=
iv dir=3D"auto"><br></div><div dir=3D"auto">A programmed one will need to r=
un the and program over and over until you can derive the correct answer fr=
om one of its outputs. How fast this goes depends on the problem and the al=
gorithm.=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">Most peop=
le here have heard of Grover&#39;s algorithm, it would crack a symmetric 25=
6 bit key in approximately 2^128 QC cycles - completely impractical. Shor&#=
39;s algorithm is the dangerous one for ECC since it cracks current keys at=
 &quot;practical&quot; speeds.=C2=A0</div><div dir=3D"auto"><a href=3D"http=
s://eprint.iacr.org/2017/598" style=3D"font-family:sans-serif"><br>https://=
eprint.iacr.org/2017/<wbr>598</a><span style=3D"font-family:sans-serif">=C2=
=A0- resource estimates, in terms of size of the QC. Does not address imple=
mentation speed.=C2=A0</span><br></div><div dir=3D"auto"><span style=3D"fon=
t-family:sans-serif"><br></span></div><div dir=3D"auto">I can&#39;t seem to=
 find specific details, but I remember having seen estimates of around 2^40=
 cycles in practical implementations for 256 bit ECC (this assumes use erro=
r correction schemes, QC machines with small some imperfections, and more).=
 Unfortunately I can&#39;t find a source for this estimate. I&#39;ve seen l=
ower estimates too, but they seem entirely theoretical.=C2=A0</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">Read-out time for QC:s is indeed insi=
gnificant, in terms of measuring the state of the qubits after a complete c=
ycle.=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">Programming =
time, time to prepared for readout, reset, reprogramming, etc, that will al=
l take a little longer. In particular with more qubits involved, since they=
 all need to be in superposition and be coherent at some point. Also, you s=
till have to parse all the different outputs (on a classical computer) to f=
ind your answer among them.=C2=A0</div><div dir=3D"auto">Very very optimist=
ic cycle speeds are in the GHz range, and then that&#39;s still on the orde=
r of ~15 minutes for 2^40 cycles. Since we don&#39;t even have a proper gen=
eral purpose QC yet, nor one with usable amounts of qubits, we don&#39;t ev=
en know if we can make them run at a cycle per second, or per minute...=C2=
=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">However if somebody =
*does* build a fast QC that&#39;s nearly ideal, then Bitcoin&#39;s typical =
use of ECC would be in immediate danger. The most optimistic QC plausible w=
ould indeed be able to crack keys in under a minute. But my own wild guess =
is that for the next few decades none will be faster than a runtime measure=
d in weeks for cracking keys.=C2=A0</div><div dir=3D"auto"><br></div><div d=
ir=3D"auto">---</div><div dir=3D"auto"><br></div><div dir=3D"auto">Sidenote=
, I&#39;m strongly in favor of implementing early support for the Fawkes sc=
heme mentioned previously.=C2=A0</div><div dir=3D"auto"><br></div><div dir=
=3D"auto">We could even patch it on top of classical transactions - you can=
 only break ECC with a known public key, so just commit to the signed trans=
action into the blockchain before publishing it. Then afterwards you publis=
h the transaction itself, with a reference to the commitment. That transact=
ion can then be assumed legit simply because there was no room to crack the=
 key before the commitment, and the transaction matches the commitment.=C2=
=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto"><span style=3D"font-=
family:sans-serif">Never reuse keys, and you&#39;re safe against QC:s.=C2=
=A0</span><br></div><div dir=3D"auto"><br></div><div dir=3D"auto">Sidenote:=
 There&#39;s a risk here with interception, insertion of a new commitment a=
nd getting the new transaction into the blockchain first. However, I would =
suggest a mining policy here were two known conflicting transactions with c=
ommitments are resolved such that the one with the oldest commitment wins. =
How to address detection of conflicting transactions with commitments older=
 than confirmed transactions isn&#39;t obvious. Some of these may be fully =
intentional by the original owner, such as a regretted transaction.</div><d=
iv dir=3D"auto"><br></div><div dir=3D"auto">Another sidenote: HD wallets wi=
th hash based hardened derivation should also be safe in various circumstan=
ces, near completely safe in the case where they&#39;re defined such that k=
nowing an individual private key, which is not the root key,=C2=A0 is not e=
nough to derive any other in your wallet.=C2=A0</div><div dir=3D"auto">HD s=
chemes that only prevent derivation of parent keypairs in the tree would re=
quire that you never use a key derived from another already used or publish=
ed public key.=C2=A0</div><div dir=3D"auto"></div></div>

--94eb2c1af00c420a0d0563852003--