diff options
| author | ZmnSCPxj <ZmnSCPxj@protonmail.com> | 2018-05-23 02:15:03 -0400 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2018-05-23 06:15:10 +0000 |
| commit | fab0fa81ceb47eeddef986aa3fa2831fd3af3de6 (patch) | |
| tree | df12fd827cc984bd9dcf99e5435c47c46ca5ece9 /28 | |
| parent | 4327822bdf5de07fa356189420911a7cd8de9ea5 (diff) | |
| download | pi-bitcoindev-fab0fa81ceb47eeddef986aa3fa2831fd3af3de6.tar.gz pi-bitcoindev-fab0fa81ceb47eeddef986aa3fa2831fd3af3de6.zip | |
Re: [bitcoin-dev] Should Graftroot be optional?
Diffstat (limited to '28')
| -rw-r--r-- | 28/1f054fc6125ac68e87e7047ce136417035f846 | 173 |
1 files changed, 173 insertions, 0 deletions
diff --git a/28/1f054fc6125ac68e87e7047ce136417035f846 b/28/1f054fc6125ac68e87e7047ce136417035f846 new file mode 100644 index 000000000..b4b5ddc62 --- /dev/null +++ b/28/1f054fc6125ac68e87e7047ce136417035f846 @@ -0,0 +1,173 @@ +Return-Path: <ZmnSCPxj@protonmail.com> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 7AF2284B + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 23 May 2018 06:15:10 +0000 (UTC) +X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 +Received: from mail-1857040130.protonmail.ch (mail-1857040130.protonmail.ch + [185.70.40.130]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6C555180 + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 23 May 2018 06:15:09 +0000 (UTC) +Date: Wed, 23 May 2018 02:15:03 -0400 +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; + s=default; t=1527056107; + bh=jPXRp/BNrqpd2kjBvr5BykANNsflUnwyG3UREyyv6BY=; + h=Date:To:From:Reply-To:Subject:In-Reply-To:References:Feedback-ID: + From; + b=PQjjz1LPbdSYw1kaxnFyVxxADYMzyqxF8EEgu6Sa6YP9OPT4Mqxkhd4Map2eRM3gf + qriFfSEB2XcY9YGZdVHuztkH4qwVDKkQWGmAY4DmW25/vSELCJ9br/Tj4jB/nkGKZO + TbduTwpmQzTilQROmMqwNDHAs3sNS4NoOYfP/m58= +To: Pieter Wuille <pieter.wuille@gmail.com>, + Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +From: ZmnSCPxj <ZmnSCPxj@protonmail.com> +Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com> +Message-ID: <D3Cs5IbxxGQ_EvtMsOnbyOJGiGScqJN-fWeT82tGoOTN5zcLGZOvpMLZAoSwgQzOEUgEyUcSvHkWw26FiAqAUJGtMST9BmEkZC8nYsrnyPI=@protonmail.com> +In-Reply-To: <CAPg+sBgKY-nmL=x+LVubtB0fFBAwd-1CDHT7zhidX8p9DLSGyg@mail.gmail.com> +References: <CAPg+sBgKY-nmL=x+LVubtB0fFBAwd-1CDHT7zhidX8p9DLSGyg@mail.gmail.com> +Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail +MIME-Version: 1.0 +Content-Type: text/plain; charset=UTF-8 +Content-Transfer-Encoding: quoted-printable +X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED, + DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, FROM_LOCAL_NOVOWEL, + 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 +X-Mailman-Approved-At: Wed, 23 May 2018 12:21:32 +0000 +Subject: Re: [bitcoin-dev] Should Graftroot be optional? +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, 23 May 2018 06:15:10 -0000 + +Good morning Pieter and list, + +It seems to me, naively, that it would be better to make Graftroot optional= +, and to somehow combine Taproot and Graftroot. + +So I propose that the Taproot equation be modified to the below: + + Q =3D P + H(P, g, S) * G + +Where `g` is the "Graftroot flag", i.e. 0 if disable Graftroot, and 1 if en= +able Graftroot. + +A Graftroot spend would need to reveal P and the Taproot script S, then sig= +n the Graftroot script using P (rather than Q). + +If an output wants to use Graftroot but not Taproot, then it uses Q =3D P += + H(P, 1, {OP_FALSE}) * G, meaning the Taproot script can never succeed. Th= +en Graftroot scripts need to be signed using P. + +A simple wallet software (or hardware) that only cares about spending using= + keys `Q =3D q * G` it controls does not have to worry about accidentally s= +igning a Graftroot script, since Q is not used to sign Graftroot scripts an= +d it would be "impossible" to derive a P + H(P, 1, S) * G from Q (using the= + same argument that it is "impossible" to derive a P + H(P, S) * G from Q i= +n Taproot). + +In a multisignature setting, it would not be possible (I think) to generate= + a single private key p1 + H(P1 + P2, 1, {<p1*G> OP_CHECKSIG}) that can be = +used to kick out P2, since that would be signature cancellation attack by a= +nother path. + +This increases the cost of Graftroot by one point P and a Taproot script (w= +hich could be just `OP_FALSE` if Taproot is not desired). In addition, if = +both Taproot and Graftroot are used, then using any Graftroot branch will r= +eveal the existence of a Taproot script. Similarly, using the Taproot bran= +ch reveals whether or not we also had some (hidden) Graftroot branch. + +-- + +Now the above has the massive privacy loss where using Taproot reveals whet= +her or not you intended to use Graftroot too, and using Graftroot reveals w= +hether or not you intended to use Taproot. + +So now let us consider the equation below instead: + + Q =3D P + H(P, H(sign(P, g)), H(S)) * G + +A Taproot spend reveals P, H(sign(P,g)), and S, and the witness that makes = +S succeed. + +A Graftroot spend reveals P, sign(P, 1), H(S), and sign(P, Sg), and the wit= +ness that makes Sg succeed. + +If we want to use Graftroot but not Taproot, then we can agree on the scrip= +t S =3D `push(random 256-bit) OP_FALSE`, which can never be made to succeed= +. On spending using Taproot, we reveal H(S) but not the S. Nobody can now= + distinguish between this and a Graftroot+Taproot spent using Graftroot. W= +e only need to store H(S), not the original S (but we do need to verify tha= +t the original S follows the correct template above). + +If we want to use Taproot but not Graftroot, then we can agree to do a `sig= +n(P, 0)`, which definitely cannot be used to perform a Graftroot spend. Th= +e act of signing requires a random nonce to be generated, hence making the = +signature itself random. On spending using Graftroot, we reveal H(sign(P, = +0)) but not the signature itself. Nobody can now distinguish between this = +and a Graftroot+Taproot spent using Taproot. We only need to store H(sign(= +P, 0)), not the original signature (but we do need to verify(P, sign(P, 0))= +). Some other way of obfuscating the flag can be done, such as H(g, random= +), with the parties to the contract agreeing on the random obfuscation (but= + I am unsure of the safety of that). + +In effect, instead of the Taproot contract S, we use as contract a one-leve= +l Merkle tree, with one branch being an enable/disable of Graftroot and the= + other branch being an ordinary Script. + +Note that even if we are fooled into signing a message sign(P, 1), as long = +as we made sure that the output paid to a Q =3D P + H(P, H(sign(p, 0)), H(S= +)) * G in the first place, it cannot be used after-the-fact to make a non-G= +raftroot output a Graftroot output. + +Simple wallets that use Q =3D q * G need not worry whether signing arbitrar= +y messages with that key might suddenly make their outputs spendable as Gra= +ftroot. + +This increases Taproot spends by a hash. + +This increases Graftroot spends by a point, a signature, and a hash. + +-- + +I am not a mathematician and the above could be complete bunk. + +-- + +The above also does not actually answer the question. + +Many users of Bitcoin have been depending on the ability to sign arbitrary = +messages using a public key that is also used to protect funds. The use is= + common enough that people are asking for it for SegWit addresses: https://= +lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015818.html + +Now it might be possible that a valid Script can be shown as an ordinary AS= +CII text file containing some benign-looking message. For example a messag= +e starting with "L" is OP_PUSHDATA1 (76), the next character encodes a leng= +th. So "LA" means 65 bytes of data, and the succeeding 65 bytes can be an = +arbitrary message (e.g. "LARGE AMOUNTS OF WEALTH ARE SAFE TO STORE IN BITCO= +IN, DONCHA KNOW?\n"). Someone might challenge some fund owner to prove the= +ir control of some UTXO by signing such a message. Unbeknownst to the sign= +er, the message is actually also a valid Script (`OP_PUSHDATA1(65 random by= +tes)`) that lets the challenger trivially acquire access to the funds via G= +raftroot. + +Thus I think this is a valid concern and we should indeed make Graftroot be= + optional, and also ensure that the simple-signing case will not be a vulne= +rability for ordinary wallets, while keeping the property that use of Tapro= +ot and Graftroot is invisible if the onchain spend does not involve Taproot= +/Graftroot. + +Regards, +ZmnSCPxj + |