Date: Wed, 23 May 2018 02:15:03 -0400
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
Subject: Re: [bitcoin-dev] Should Graftroot be optional?
Precedence: list

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