diff options
| author | Natanael <natanael.l@gmail.com> | 2018-01-24 13:51:45 +0100 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2018-01-24 12:51:49 +0000 |
| commit | 34ab1adf18f3f2aeb2a5dbbe16339914efcd544b (patch) | |
| tree | 4346d94975538b5add2698fb069258bb2d840fe7 | |
| parent | e8e950f616e2d5c49eda2f82dd03ef902a3eebec (diff) | |
| download | pi-bitcoindev-34ab1adf18f3f2aeb2a5dbbe16339914efcd544b.tar.gz pi-bitcoindev-34ab1adf18f3f2aeb2a5dbbe16339914efcd544b.zip | |
Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting
| -rw-r--r-- | a4/14e9cd434a2e9a855ba73bda4e556c6d1454d5 | 295 |
1 files changed, 295 insertions, 0 deletions
diff --git a/a4/14e9cd434a2e9a855ba73bda4e556c6d1454d5 b/a4/14e9cd434a2e9a855ba73bda4e556c6d1454d5 new file mode 100644 index 000000000..647e7b59f --- /dev/null +++ b/a4/14e9cd434a2e9a855ba73bda4e556c6d1454d5 @@ -0,0 +1,295 @@ +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 "Gregory Maxwell via bitcoin-dev&qu= +ot; <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"= +_blank">bitcoin-dev@lists.linuxfounda<wbr>tion.org</a>>:<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 <<a href=3D"mailto:aj@erisian= +.com.au" target=3D"_blank">aj@erisian.com.au</a>> wrote:<br> +> Hmm, at least people can choose not to reuse addresses currently --<br= +> +> if everyone were using taproot and that didn'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'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">>=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'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= + "practical" 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'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't find a source for this estimate. I'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's still on the orde= +r of ~15 minutes for 2^40 cycles. Since we don't even have a proper gen= +eral purpose QC yet, nor one with usable amounts of qubits, we don'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's nearly ideal, then Bitcoin'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'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're safe against QC:s.=C2= +=A0</span><br></div><div dir=3D"auto"><br></div><div dir=3D"auto">Sidenote:= + There'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'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'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-- + |