Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 7AF2284B for ; 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 ; 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 , Bitcoin Protocol Discussion From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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, { 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