Date: Wed, 20 Jun 2018 08:12:28 -0400
To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <7nh2F_OPfoHDxrXVG8Dlu51iJ4nnlLFo962B7gI1cN3nyLupsjjlZF9-2nO525E5ENlhMSXprJWkHty8AAxe7W7FRZZpv00C0BptZZcvzK8=@protonmail.com>
In-Reply-To: <01976660b06809ea27af7db4bbceb08220ea2568.camel@timruffing.de>
References: <CAPg+sBgKY-nmL=x+LVubtB0fFBAwd-1CDHT7zhidX8p9DLSGyg@mail.gmail.com>
	<CAPg+sBh4CESPV_5TpPn0H3Zpv2Ump_0txxS63W_S2f3Lxezq1A@mail.gmail.com>
	<CAAS2fgRXYtTyqqQp8Ehs_q_KsT7usA+vYSmngStnndd1rWNVNw@mail.gmail.com>
	<D996F4E8-ACC6-4A49-B841-0F3285344DF6@xbt.hk>
	<CAPg+sBgEUV5KNFi1L4MhR-3KAX9gbQKdzWneaEzF+QsKSXYu8A@mail.gmail.com>
	<f5c0012e55242d85ec2cc740cc8d081ef5da9145.camel@timruffing.de>
	<CAPg+sBhYkQdjDcKvxUiGZCs220N0dqRMYoweCbOB2dgzD9UpzA@mail.gmail.com>
	<01976660b06809ea27af7db4bbceb08220ea2568.camel@timruffing.de>
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 Tim and all,

My understanding is that the idea now being discussed by Pieter and Tim is =
that the Graftroot signature is not `sign(P, script)` but instead `sign(P, =
sighash(tx))`, where `tx` is an "ordinary" transaction that spends the outp=
oint that pays to `P`, and a single output whose `scriptPubKey` is the Graf=
troot `script` and contains the entire value of the outpoint, and `sighash(=
)` is the standard SegWit transaction digest algorithm used for signing (an=
d is affected by other flags in the signature).

This has the advantage that the Graftroot signature commits to a single out=
point and cannot be used to spend all outpoints that happen to pay to the s=
ame `P` public key.

However I believe the ability to "immanentize" a Graftroot signature as a s=
ignature for a 1-input 1-output transaction is unsafe (so a Graftroot signa=
ture should probably not be "the same" as a signature for a 1-input 1-outpu=
t transaction like the above).

Let us consider a simple CoinSwap protocol.  Let us focus on one half of th=
e procedure, which is a simple ZKCP, i.e. Alice pays Bob for a hash preimag=
e, with a timeout imposed so that Bob needs to provide the preimage, within=
 a specified time.

1.  Alice and Bob generate a shared public key P which requires k_a (Alice =
secret key) and k_b (Bob secret key) to sign.

2.  Alice creates but does not sign a funding transaction that pays to publ=
ic key P and gives its txid to Bob.  Alice also provides a standard P2WPKH =
return address that Alice controls.

3.  Bob creates a `nLockTime`-encumbered transaction (the timeout backoff t=
ransaction) on the agreed timeout, spending the above txid outpoint to the =
Alice return address, and provides its half of the signature to P signing t=
he timeout backoff transaction to Alice.

4.  Alice keeps the above signature (verifying it is to the correct `nLockT=
ime` and Alice return address), then signs and broadcasts the funding trans=
action.  Both wait for the funding transaction to confirm deeply.

5.  Alice then signs a Graftroot to the script `{ OP_HASH <hash> OP_EQUALVE=
RIFY <P_b> OP_CHECKSIG }` and gives its half of the signature to P signing =
the Graftroot to Bob.  Bob keeps this signature.

6.  Bob provides the preimage to the hash directly to Alice and a standard =
P2WPKH destination address that Bob controls.

7.  Alice then signs a direct spend of the funding transaction outpoint (on=
e that is not encumbered by `nLockTime`), spending the funding txid outpoin=
t to the Bob destination address, and provides its half of the signature to=
 P signing this transaction.  This completes Alice participation in the pro=
tocol (it has now received the preimage).

8.  Bob completes the signature to the destination transaction and broadcas=
ts it to the blockchain layer.

If Alice or Bob stalls at step 5 or earlier then the transaction does not o=
ccur (Alice does not learn the preimage, Bob gets no money).

If Bob stalls at step 6, Alice can use the timeout backoff.

If Alice stalls at step 7, Bob can use the Graftroot signed at step 5 to cl=
aim its funds as long as the timeout is not reached.

Now if Graftroot signature is "actually" just a standard signature of a tra=
nsaction that is elided from the blockchain, however, it means that this el=
ided transaction can be immanentized on the blockchain with the specified s=
cript.  Even if this transaction has e.g. no fee then Bob could collude wit=
h a miner via sidefees to get the (valid) transaction onchain.

So Bob could take the signature made at 5 to create a transaction spending =
to the specified script, and prevent Alice from claiming the funds using th=
e timeout backoff transaction.  Then Bob forever controls the UTXO and Alic=
e cannot back out of the transaction, so even if the knowledge of the preim=
age ceases to be interesting, Alice has already paid Bob and Bob can provid=
e the preimage at its leisure rather than constrained by the timeout.

Thus we should somehow disallow immanentizing the Graftroot signature.

An idea is that the Graftroot signature should sign a transaction with a sp=
ecific special `nVersion`, that is then soft-forked to be invalid onchain (=
i.e. the `nVersion` is reserved for Graftroot and it is invalid for a trans=
action onchain to use that `nVersion`).  So the Graftroot signature can be =
used as a Graftroot spend, but not as a immanentized signature on an actual=
 onchain transaction that could disable the timeout backoff transaction.

Utilities that can sign an arbitrary message using your private keys could =
check if the first four bytes match the Graftroot `nVersion` and refuse to =
sign such messages to prevent inadvertently giving a Graftroot signature.

Alternatively, we note that the "transaction" signed by Graftroot will not =
be referred to onchain anyway, and we could use a completely different `sig=
hash()` algorithm, e.g. it could just be the outpoint being spent and the s=
cript to be executed, i.e. `sign(P, concat(txid, outnum, script))`.  This r=
educes code reuse, though.

Regards,
ZmnSCPxj