Re: [bitcoin-dev] Should Graftroot be optional?

[Anthony Towns via bitcoin-dev]

On Thu, May 31, 2018 at 05:25:04PM -0700, Pieter Wuille via bitcoin-dev wrote:
> The best argument for why Graftroot does not need to be optional I
> think was how Greg put it: "since the signer(s) could have signed an
> arbitrary transaction instead, being able to delegate is strictly less
> powerful.".

This seems persuasive to me. I think you could implement graftroot in
a way that makes this explicit:

 * A graftroot input has >=2 items on the witness stack, a signature,
   a script (S), and possibly witness elements for the script. The
   signature has a SIGHASH_GRAFTROOT bit set.

 * To validate the signature, a virtual transaction is constructed:

 nVersion = 1
 locktime = 0
 inputs = [(txhash, txoutidx, 0, "", 0x)]
 outputs = [(txvalue, len(S), S)]
 locktime = 0

   The signature is then checked against the virtual transaction.

 * If the signature is valid, the virtual transaction is discarded, and
   the script and witness elements are checked against the original tx.

I think this approach (or one like it) would make it clear that
graftroot is a simple optimisation, rather than changing the security
parameters. Some caveats:

 * You'd presumably want to disallow signatures with SIGHASH_GRAFTROOT
   from being used in signatures in scripts, so as not to end up having
   to support recursive graftroot.

 * Checking the script/witness against the original transaction instead
   of the virtual one cheats a bit, but something like it is necessary
   to ensure locktime/csv checks in the script S behave sanely. You
   could have the virtual transaction be treated as being confirmed in
   the same block as the original transaction instead though, I think.

 * You would need to use SIGHASH_NOINPUT (or similar) in conjuction
   to allow graftroot delegation prior to constructing the tx (otherwise
   the signature would be committing to txhash/txoutidx). BIP118 would
   still commit to txvalue, but would otherwise work fine, I think.

Cheers,
aj

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[ZmnSCPxj via bitcoin-dev]

Good morning Greg,


> On Wed, Jun 20, 2018 at 12:12 PM, ZmnSCPxj via bitcoin-dev
> 
> bitcoin-dev@lists.linuxfoundation.org wrote:
> 
> > This has the advantage that the Graftroot signature commits to a single 
> > outpoint and cannot be used to spend all outpoints that happen to pay to 
> > the same `P` public key.
> 
> If it isn't possible to make a graftroot signature independent of the
> 
> outpoint then the functionality is greatly reduced to the point of
> 
> largely mooting it-- because you could no longer prepare the grafts
> 
> before the coins to be spent existed, and meaning you must stay online
> 
> and sign new grafts as coins show up. In my view graft's two main
> 
> gains are being able to delegate before coins exist and making the
> 
> conditional transfer atomic (e.g. compared to just pre-signing a
> 
> transaction). Making outpoint binding optional, so that you could
> 
> choose to either sign for particular outputs or in a blanket way would
> 
> be a lot more useful.
> 

Perhaps `SIGHASH_NOINPUT` can do this? One can argue that the option to not 
commit a signature to refer to a specific outpoint is orthogonal to the option 
to Graftroot, so having a separate flag for that makes sense.

The proposal could then be:

1. Define a transaction `nVersion` reserved for Graftroot. Transactions with 
that `nVersion` are disallowed in blocks.
2. If a next-SegWit-version P2WPKH (or P2WPK) is spent, and the top witness 
stack item is a signature with `SIGHASH_GRAFTROOT` flag, then this is a 
Graftroot spend.
3. The signature signs an imaginary 1-input 1-output tx, with the input copied 
from the spending tx, the output value being the entire output being spent, and 
the output `scriptPubKey` being the Graftroot script (second to top witness 
stack). The imaginary tx has the Graftroot-reserved `nVersion`.
4. The Graftroot signature has its other flags `SIGHASH_NOINPUT` evaluated also 
when verifying it signs the imaginary tx.
5. The Graftroot signature and the Graftroot script are popped and the script 
executed in the context of the original Graftroot-spending tx.


This lets users select whether committing to a specific outpoint is needed or 
not, independently of Graftroot.

Regards,
ZmnSCPxj

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Gregory Maxwell via bitcoin-dev]

On Wed, Jun 20, 2018 at 12:12 PM, ZmnSCPxj via bitcoin-dev
 wrote:
> This has the advantage that the Graftroot signature commits to a single 
> outpoint and cannot be used to spend all outpoints that happen to pay to the 
> same `P` public key.

If it isn't possible to make a graftroot signature independent of the
outpoint then the functionality is _greatly_ reduced to the point of
largely mooting it-- because you could no longer prepare the grafts
before the coins to be spent existed, and meaning you must stay online
and sign new grafts as coins show up. In my view graft's two main
gains are being able to delegate before coins exist and making the
conditional transfer atomic (e.g. compared to just pre-signing a
transaction).  Making outpoint binding optional, so that you could
choose to either sign for particular outputs or in a blanket way would
be a lot more useful.

Though I had assumed outpoint binding could best be achieved by
checking the outpoint in the graft-script-- this is general for
whatever kinds of arbitrary graft conditions you might want to specify
(e.g. locktimes, value checks, or conditions on subsequent outputs)...
but perhaps binding a particular outpoint is enough of a special case
that it's worth avoiding the overhead of expressing a match condition
in the script, since that would probably end up blowing 36 bytes for
the match condition in the witness when instead it could just be
covered by the signature, and people should probably prefer to do
output binding grafts whenever its reasonably possible.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[ZmnSCPxj via bitcoin-dev]

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 outpoint 
that pays to `P`, and a single output whose `scriptPubKey` is the Graftroot 
`script` and contains the entire value of the outpoint, and `sighash()` is the 
standard SegWit transaction digest algorithm used for signing (and is affected 
by other flags in the signature).

This has the advantage that the Graftroot signature commits to a single 
outpoint and cannot be used to spend all outpoints that happen to pay to the 
same `P` public key.

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

Let us consider a simple CoinSwap protocol.  Let us focus on one half of the 
procedure, which is a simple ZKCP, i.e. Alice pays Bob for a hash preimage, 
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 public 
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 
transaction) on the agreed timeout, spending the above txid outpoint to the 
Alice return address, and provides its half of the signature to P signing the 
timeout backoff transaction to Alice.

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

5.  Alice then signs a Graftroot to the script `{ OP_HASH  OP_EQUALVERIFY 
 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 (one 
that is not encumbered by `nLockTime`), spending the funding txid outpoint to 
the Bob destination address, and provides its half of the signature to P 
signing this transaction.  This completes Alice participation in the protocol 
(it has now received the preimage).

8.  Bob completes the signature to the destination transaction and broadcasts 
it to the blockchain layer.

If Alice or Bob stalls at step 5 or earlier then the transaction does not occur 
(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 claim 
its funds as long as the timeout is not reached.

Now if Graftroot signature is "actually" just a standard signature of a 
transaction that is elided from the blockchain, however, it means that this 
elided transaction can be immanentized on the blockchain with the specified 
script.  Even if this transaction has e.g. no fee then Bob could collude with 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 the 
timeout backoff transaction.  Then Bob forever controls the UTXO and Alice 
cannot back out of the transaction, so even if the knowledge of the preimage 
ceases to be interesting, Alice has already paid Bob and Bob can provide 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 
specific 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 
transaction 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 `sighash()` 
algorithm, e.g. it could just be the outpoint being spent and the script to be 
executed, i.e. `sign(P, concat(txid, outnum, script))`.  This 

Re: [bitcoin-dev] Should Graftroot be optional?

[Tim Ruffing via bitcoin-dev]

What you're saying makes sense.

By the way, an even stronger reason why you shouldn't be able to
"repurpose" just a Graftroot signature as a transaction: You may want
to reveal to others that you've delegated. But if an observer sees the
delegation (literally the Graftroot signature), this observer could
send the Graftroot signature to the network (and lock out the other
delegates and the initial owner). So you would need to keep the
signature itself secret, otherwise we can't call this delegation.

So it may sense to consider the idea of an implicit transaction for the
case when one really solves the delegated script (as you mentioned) but
only in this case.

Tim


On Wed, 2018-06-06 at 10:04 -0700, Pieter Wuille wrote:
> On Wed, Jun 6, 2018 at 5:48 AM, Tim Ruffing via bitcoin-dev
>  wrote:
> > On Thu, 2018-05-31 at 17:25 -0700, Pieter Wuille via bitcoin-dev
> > wrote:
> > > The best argument for why Graftroot does not need to be optional
> > > I
> > > think was how Greg put it: "since the signer(s) could have signed
> > > an
> > > arbitrary transaction instead, being able to delegate is strictly
> > > less
> > > powerful.".
> 
> ...
> 
> > So
> > I think Graftroot delegation is not "strictly less powerful" than
> > just
> > using a normal transaction: Graftroot enables to delegate in a way
> > such
> > that the delegation itself cannot be fixed in the chain. I think
> > this
> > is not possible currently. (Okay, you can just pass around the
> > secret
> > keys but has other problems obviously).
> > 
> > Does this have practical implications?
> > I don't see any but maybe this helps someone to identify an
> > undesirable
> > implication.
> 
> Interesting point; I don't see any relevant implications to this
> either, but it's indeed good to point out this as a distinction.
> 
> > One way to be on the safe side and probably make Greg's argument go
> > through is to just define the semantics such that (*) is allowed,
> > i.e.,
> > call g-sig a "Graftroot transaction" and give it transaction
> > semantics.
> > This provides a new perspective on Graftroot: Then Graftroot does
> > not
> > introduce new semantics but (*) is just an optimized version of
> > (**)
> > that uses fewer bytes and may be better for privacy.
> 
> So you're saying: the Graftroot signature data could be made
> identical
> to the signature hash of an implicit 1-input-1-output transaction
> spending the coin and creating a new output with the delegated script
> as sPK, and the same amount.
> 
> I like that idea, but I don't think it can be *exactly* that. If it's
> possible to take a Graftroot signature and instead construct a
> transaction with it, you have inherently introduced a malleability.
> The created outpoint will be different in both cases (different
> txid),
> meaning that a chain of dependent unconfirmed transactions may be
> broken by giving one participant the ability to choose between
> Graftroot delegation or actual spending.
> 
> Two points here: (1) the implicit transaction would be 0 fee (unless
> we somehow assign a portion of the fee to the delegation itself for
> purposes of sighash computing), and (2) this sounds very similar to
> the issue SIGHASH_NOINPUT is intended to solve. About that...
> 
> > Interestingly Andrew's blind-sig example and Johnson's fix (g-sig
> > signs
> > the outpoint) are just a special case. If g-sig has transaction
> > semantics, it must sign the outpoint (and other stuff).
> 
> You're right when you're comparing with existing transaction sighash
> semantics, but not when SIGHASH_NOINPUT would exist. If that were the
> case, the only real difference is your point above of not being able
> to commit the implicit transaction separately. In other words, we're
> back to something Johnson pointed out earlier: some of the perceived
> problems with Graftroot are also issues with SIGHASH_NOINPUT.
> 
> I wonder if we can make this explicit: Graftroot spending becomes a
> special sighash flag (which possibly is only allowed at the top
> level)
> - it builds an implicit transaction which moves all the coins to a
> newly provided script, computes the sighash of that transaction
> (taking all of the Graftroot signature's sighash flags into account -
> including potentially SIGHASH_NOINPUT), and requires a signature with
> that. The delegated script is then evaluated in the context of that
> implicit transaction.
> 
> However, in order to avoid the malleability issue I think the actual
> signature should still be different - possibly by simply passing
> through the Graftroot sighash flag into the sighash being computed.
> 
> Cheers,
> 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Pieter Wuille via bitcoin-dev]

On Wed, Jun 6, 2018 at 5:48 AM, Tim Ruffing via bitcoin-dev
 wrote:
> On Thu, 2018-05-31 at 17:25 -0700, Pieter Wuille via bitcoin-dev wrote:
>> The best argument for why Graftroot does not need to be optional I
>> think was how Greg put it: "since the signer(s) could have signed an
>> arbitrary transaction instead, being able to delegate is strictly
>> less
>> powerful.".

...

> So
> I think Graftroot delegation is not "strictly less powerful" than just
> using a normal transaction: Graftroot enables to delegate in a way such
> that the delegation itself cannot be fixed in the chain. I think this
> is not possible currently. (Okay, you can just pass around the secret
> keys but has other problems obviously).
>
> Does this have practical implications?
> I don't see any but maybe this helps someone to identify an undesirable
> implication.

Interesting point; I don't see any relevant implications to this
either, but it's indeed good to point out this as a distinction.

> One way to be on the safe side and probably make Greg's argument go
> through is to just define the semantics such that (*) is allowed, i.e.,
> call g-sig a "Graftroot transaction" and give it transaction semantics.
> This provides a new perspective on Graftroot: Then Graftroot does not
> introduce new semantics but (*) is just an optimized version of (**)
> that uses fewer bytes and may be better for privacy.

So you're saying: the Graftroot signature data could be made identical
to the signature hash of an implicit 1-input-1-output transaction
spending the coin and creating a new output with the delegated script
as sPK, and the same amount.

I like that idea, but I don't think it can be *exactly* that. If it's
possible to take a Graftroot signature and instead construct a
transaction with it, you have inherently introduced a malleability.
The created outpoint will be different in both cases (different txid),
meaning that a chain of dependent unconfirmed transactions may be
broken by giving one participant the ability to choose between
Graftroot delegation or actual spending.

Two points here: (1) the implicit transaction would be 0 fee (unless
we somehow assign a portion of the fee to the delegation itself for
purposes of sighash computing), and (2) this sounds very similar to
the issue SIGHASH_NOINPUT is intended to solve. About that...

> Interestingly Andrew's blind-sig example and Johnson's fix (g-sig signs
> the outpoint) are just a special case. If g-sig has transaction
> semantics, it must sign the outpoint (and other stuff).

You're right when you're comparing with existing transaction sighash
semantics, but not when SIGHASH_NOINPUT would exist. If that were the
case, the only real difference is your point above of not being able
to commit the implicit transaction separately. In other words, we're
back to something Johnson pointed out earlier: some of the perceived
problems with Graftroot are also issues with SIGHASH_NOINPUT.

I wonder if we can make this explicit: Graftroot spending becomes a
special sighash flag (which possibly is only allowed at the top level)
- it builds an implicit transaction which moves all the coins to a
newly provided script, computes the sighash of that transaction
(taking all of the Graftroot signature's sighash flags into account -
including potentially SIGHASH_NOINPUT), and requires a signature with
that. The delegated script is then evaluated in the context of that
implicit transaction.

However, in order to avoid the malleability issue I think the actual
signature should still be different - possibly by simply passing
through the Graftroot sighash flag into the sighash being computed.

Cheers,

-- 
Pieter
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Tim Ruffing via bitcoin-dev]

I haven't read the original Graftroot thread, so maybe all of this has
b
een discussed already or is just wrong... Please correct me if this
is
the case.

On Thu, 2018-05-31 at 17:25 -0700, Pieter Wuille via bitcoin-dev wrote:
> The best argument for why Graftroot does not need to be optional I
> think was how Greg put it: "since the signer(s) could have signed an
> arbitrary transaction instead, being able to delegate is strictly
> less
> powerful.".

I'm trying to get a more abstract view of the problem. One issue with
Greg's argument is the following:

If g-script is a script (containing a public key) that allows for
Graftroot spending, then the following "flow" of coins is valid: 

  g-script --g-sig--> script1 ---tx2---> script2

Here, g-sig is a Graftroot signature on script1 and tx2 is a
transaction that fulfills script1 and sends to script2. In other words,
the only transaction involved here is tx2; it provides g-sig, script1,
and a solution for tx1, and it spends to script2.

Now Greg's argument (as I understand it) is that this can be already
done without Grafroot with two transactions, namely a normal
transaction tx1 that spends g-script normally and tx2 that spends tx1
to script1.

  g-script ---tx1---> script1 ---tx2---> script2.

So far, so good. A difference however is that g-sig *alone* can't be
committed to the chain but tx1 alone can be committed to the chain.
That means

  g-script --g-sig--> script1 (*)

is "incomplete" but

  g-script ---tx1---> script1 (**)

is a perfectly valid transaction that can be committed to the chain. So
I think Graftroot delegation is not "strictly less powerful" than just
using a normal transaction: Graftroot enables to delegate in a way such
that the delegation itself cannot be fixed in the chain. I think this
is not possible currently. (Okay, you can just pass around the secret
keys but has other problems obviously).

Does this have practical implications?
I don't see any but maybe this helps someone to identify an undesirable
implication.

One way to be on the safe side and probably make Greg's argument go
through is to just define the semantics such that (*) is allowed, i.e.,
call g-sig a "Graftroot transaction" and give it transaction semantics.
This provides a new perspective on Graftroot: Then Graftroot does not
introduce new semantics but (*) is just an optimized version of (**)
that uses fewer bytes and may be better for privacy. 

Interestingly Andrew's blind-sig example and Johnson's fix (g-sig signs
the outpoint) are just a special case. If g-sig has transaction
semantics, it must sign the outpoint (and other stuff).

Now you can say that this is not really useful: if g-sig is essentially
a full transaction that can committed to the blockchain, then it needs
to specify inputs, outputs etc. So all the optimizations are lost and
those were the reason we want to introduce Grafroot in the first place.

But one observation here is that g-sig only needs to be a full
transaction if it's used standalone as in (*). If we want to have 

  g-script --g-sig--> script1 ---tx2---> script2

(and this should be the common case) then just the bare signature  and
script1 suffices, as in the Graftroot proposal. In some sense, inputs
and outputs of the Graftroot transaction are just implicit in this
case.

Another way to look at this that instead of providing a transaction
with g-sig, script1, and a solution for script1, you can also choose to
provide a transaction with only g-sig and script1 (and don't solve
script1), which then just sends to script1.

I'm not saying that it's worth the hassle to add this possibility
without being aware of a problem that arises if we don't add it -- but
maybe my thoughts provide another perspective on the issue.

Best,
Tim


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Pieter Wuille via bitcoin-dev]

On Fri, May 25, 2018 at 3:14 AM, Johnson Lau  wrote:
> A graftroot design like this is a strict subset of existing signature 
> checking rules. If this is dangerous, the existing signature checking rules 
> must be dangerous.

While you may be right in this situation, I'm not sure that conclusion
follows from your argument. Whether or not a construction is safe does
not just depend on the consensus rules, but also on how it is used.
Otherwise you could as well argue that since OP_TRUE is possible right
now which is obviously insecure, nothing more dangerous can be
accomplished through any soft fork.

The best argument for why Graftroot does not need to be optional I
think was how Greg put it: "since the signer(s) could have signed an
arbitrary transaction instead, being able to delegate is strictly less
powerful.".

Cheers,

-- 
Pieter
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Johnson Lau via bitcoin-dev]

> On 24 May 2018, at 10:08 AM, Gregory Maxwell via bitcoin-dev 
>  wrote:
> 
> On Thu, May 24, 2018 at 1:58 AM, Pieter Wuille via bitcoin-dev
>  wrote:
>> Thanks everyone who commented so far, but let me clarify the context
>> of this question first a bit more to avoid getting into the weeds too
>> much.
> 
> since the signer(s) could have signed an arbitrary
> transaction instead, being able to delegate is strictly less powerful.
> 


Actually, we could introduce graftroot-like delegation to all existing and new 
P2PK and P2PKH UTXOs with a softfork:

1. Define SIGHASH_GRAFTROOT = 0x40. New rules apply if (nHashType & 
SIGHASH_GRAFTROOT)

2. The third stack item MUST be at least 64 bytes, with 32-byte R and 32-byte 
S, followed by a script of arbitrary size. It MUST be a valid signature for the 
script with the original public key.

3. The remaining stack items MUST solve the script

Conceptually this could be extended to arbitrary output types, not just P2PK 
and P2PKH. But it might be too complicated to describe here.

(We can’t do this in P2WPKH and P2WSH due to the implicit CLEANSTACK rules. But 
nothing could stop us to do it by introducing another witness structure (which 
is invisible to current nodes) and store the extra graftroot signatures and 
scripts)

A graftroot design like this is a strict subset of existing signature checking 
rules. If this is dangerous, the existing signature checking rules must be 
dangerous. This also doesn’t have any problem with blind signature, since the 
first signature will always sign the outpoint, with or without ANYONECANPAY. 
(As I pointed out in my reply to Andrew, his concern applies only to 
SIGHASH_NOINPUT, not graftroot)


==

With the example above, I believe there is no reason to make graftroot 
optional, at the expense of block space and/or reduced privacy. Any potential 
problem (e.g. interaction with blind signature) could be fixed by a proper 
rules design.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Johnson Lau via bitcoin-dev]

While you have rescind your concern, I’d like to point out that it’s strictly a 
problem of SIGHASH_NOINPUT, not graftroot (or script delegation in general).

For example, we could modify graftroot. Instead of signing the (script), we 
require it to sign (outpoint | script). That means a graftroot signature would 
never be valid for more than one UTXO.

> On 24 May 2018, at 1:52 AM, Andrew Poelstra via bitcoin-dev 
>  wrote:
> 
> On Wed, May 23, 2018 at 01:50:13PM +, Andrew Poelstra via bitcoin-dev 
> wrote:
>> 
>> Graftroot also break blind signature schemes. Consider a protocol such as [1]
>> where some party has a bunch of UTXOs all controlled (in part) by the same
>> key X. This party produces blind signatures on receipt of new funds, and can
>> only verify the number of signatures he produces, not anything about what he
>> is signing.
>> 
>> BTW, the same concern holds for SIGHASH_NOINPUT, which I'd also like to be
>> disable-able. Maybe we should extend one of ZmnSCPxj's suggestions to include
>> a free "flags" byte or two in the witness?
>> 
>> (I also had the same concern about signature aggregation. It seems like it's
>> pretty hard to preserve the "one signature = at most one input" invariant of
>> Bitcoin, but I think it's important that it is preserved, at least for
>> outputs that need it.)
>> 
>> Or maybe, since it appears it will require a space hit to support optional
>> graftroot anyway, we should simply not include it in a proposal for Taproot,
>> since there would be no opportunity cost (in blockchain efficiency) to doing
>> it later.
>> 
>> [1] https://github.com/apoelstra/scriptless-scripts/pull/1 
>> 
> 
> On further thought, I rescind this concern (ditto for SIGHASH_NOINPUT) (but
> not for aggregate sigs, they still interact badly with blind signatures).
> 
> As long as graftroot (and NOINPUT) sigs commit to the public key, it is
> possible for a server to have unique keys for every output, even while
> retaining the same private key, and thereby ensure that "one sig can spend
> only one output" holds. To do this, suppose the server has a BIP32 xpubkey
> (xG, cc). A blind signer using the private key x can be made to sign not
> only for xG, but also for any publicly-derived child keys of (xG, cc).
> 
> Here is a simple scheme that does this:
> 
>  1. Signer provides a nonce R = kG
> 
>  2. Challenger computes bip32 tweak h, chooses blinders alpha and beta,
> and computes:
> R' = R + alpha*G + beta*P
> e  = H(P + hG || R' || tx)
> e' = e + beta
> and sends e' to the signer.
> 
>  3. Signer replies with s = k + xe' (= k + beta*x + (x + h)e - he)
> 
>  4. Challenger unblinds this as s' = s + alpha + he
> 
> (This blind signature scheme is vulnerable to Wagner's attack, though see
> Schnorr 2004 [1] for mitigations that are perfectly compatible with this
> modified BIP32ish scheme.)
> 
> I'm unsure whether key-prefixing is _actually_ necessary for this, but it
> makes the security argument much clearer since the messagehash contains
> some data which can be made unique per-utxo and is committed in the chain.
> 
> 
> Andrew
> 
> 
> [1] 
> http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8ECEF929559865FD68D1D873555D18FE?doi=10.1.1.68.9836=rep1=pdf
> 
> 
> -- 
> Andrew Poelstra
> Mathematics Department, Blockstream
> Email: apoelstra at wpsoftware.net
> Web:   https://www.wpsoftware.net/andrew
> 
> "A goose alone, I suppose, can know the loneliness of geese
> who can never find their peace,
> whether north or south or west or east"
>   --Joanna Newsom
> 
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Andrew Poelstra via bitcoin-dev]

On Thu, May 24, 2018 at 11:44:16AM +0200, Natanael via bitcoin-dev wrote:
> 
> As stated above by Wuille this seems to not be a concern for typical P2SH
> uses, but my argument here is simply that in many cases, not all
> stakeholders in a transaction will hold one of the private keys required to
> sign. And such stakeholders would want a guarantee that the original script
> is followed as promised.
>

In this case, even mandatory graftroot would not allow the signing stakeholders
to take the coins. The reason is that if there are _any_ non-signing script
conditions that must be followed, then to use Taproot the top-level public key
needs to be unusable, e.g. by being a NUMS point. In that case the public key
would also be unusable for Graftroot.

Another way to see this is -- in any context where Graftroot seems dangerous,
there needs to be a reason why the ability to just create transactions is not
dangerous. In your example it seems that the signing parties can just take
the coins with or without Graftroot, so the problem is not in Graftroot but
in the way that the example is set up.
 
> I'm not concerned by the ability to move funds to an address with the new
> rules that you'd otherwise graftroot in, only that you can provide a
> transparent guarantee that you ALSO follow the original script as promised.
> What happens *after* you have followed the original script is unrelated,
> IMHO.
>

To do this in Taproot you need to disable the top-level key, which will also
disable Graftroot. 

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Natanael via bitcoin-dev]

Den tor 24 maj 2018 04:08Gregory Maxwell via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> skrev:

>
> My understanding of the question is this:
>
> Are there any useful applications which would be impeded if a signing
> party who could authorize an arbitrary transaction spending a coin had
> the option to instead sign a delegation to a new script?
>
> The reason this question is interesting to ask is because the obvious
> answer is "no":  since the signer(s) could have signed an arbitrary
> transaction instead, being able to delegate is strictly less powerful.
> Moreover, absent graftroot they could always "delegate" non-atomically
> by spending the coin with the output being the delegated script that
> they would have graftrooted instead.
>
> Sometimes obvious answers have non-obvious counter examples, e.g.
> Andrews points related to blindsigning are worth keeping in mind.
>

As stated above by Wuille this seems to not be a concern for typical P2SH
uses, but my argument here is simply that in many cases, not all
stakeholders in a transaction will hold one of the private keys required to
sign. And such stakeholders would want a guarantee that the original script
is followed as promised.

I agree that such flags typically wouldn't have a meaningful effect for
funds from non-P2SH addresses, since the entire transaction / script could
be replaced by the very same keyholders.

I'm not concerned by the ability to move funds to an address with the new
rules that you'd otherwise graftroot in, only that you can provide a
transparent guarantee that you ALSO follow the original script as promised.
What happens *after* you have followed the original script is unrelated,
IMHO.

>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Natanael via bitcoin-dev]

Den tor 24 maj 2018 01:45Gregory Maxwell  skrev:

> I am having a bit of difficulty understanding your example.
>
> If graftroot were possible it would mean that the funds were paid to a
> public key.  That holder(s) of the corresponding private key could
> sign without constraint, and so the accoutability you're expecting
> wouldn't exist there regardless of graftroot.
>
> I think maybe your example is only making the case that it should be
> possible to send funds constrained by a script without a public key
> ever existing at all.  If so, I agree-- but that wasn't the question
> here as I understood it.
>

I have to admit I not an expert on this field, so some of my concerns might
not be relevant. However, I think Wuille understood my points and his reply
answered my concerns quite well. I'm only asking for the optional ability
to prove you're not using these constructions (because some uses requires
committing to an immutable script), and that already seems to exist. So for
the future implementations I only ask that this ability is preserved.

I think such a proof don't need to be public (making such a proof in
private is probably often better), although optionally it might be. A
private contract wouldn't publish these details, while a public commitment
would do so.

>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Gregory Maxwell via bitcoin-dev]

On Thu, May 24, 2018 at 1:58 AM, Pieter Wuille via bitcoin-dev
 wrote:
> Thanks everyone who commented so far, but let me clarify the context
> of this question first a bit more to avoid getting into the weeds too
> much.

My understanding of the question is this:

Are there any useful applications which would be impeded if a signing
party who could authorize an arbitrary transaction spending a coin had
the option to instead sign a delegation to a new script?

The reason this question is interesting to ask is because the obvious
answer is "no":  since the signer(s) could have signed an arbitrary
transaction instead, being able to delegate is strictly less powerful.
Moreover, absent graftroot they could always "delegate" non-atomically
by spending the coin with the output being the delegated script that
they would have graftrooted instead.

Sometimes obvious answers have non-obvious counter examples, e.g.
Andrews points related to blindsigning are worth keeping in mind.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Pieter Wuille via bitcoin-dev]

On Tue, May 22, 2018 at 11:17 AM, Pieter Wuille  wrote:
> Hello all,
>
> Given the recent discussions about Taproot [1] and Graftroot [2], I
> was wondering if a practical deployment needs a way to explicitly
> enable or disable the Graftroot spending path. I have no strong
> reasons why this would be necessary, but I'd like to hear other
> people's thoughts.

Thanks everyone who commented so far, but let me clarify the context
of this question first a bit more to avoid getting into the weeds too
much.

If it turns out to be necessary to explicitly commit to permitting
Graftroot spending, there are a number of approaches:
* Use a different witness version (or other marker directly in the
scriptPubKey) to enable Graftroot.
* Signal the permission to spend through Graftroot inside the Taproot
script as suggested by ZmnSCPxj.
* Make "Spend through Graftroot" a special script (possibly indirectly
with a Merkle tree in Taproot).
* Implement Graftroot as an opcode/feature inside the scripting
language (which may be more generically useful as a delegation
mechanism).
* Postpone Graftroot.

All of these are worse in either efficiency or privacy than always
permitting Graftroot spends directly. Because of that, I think we
should first focus on reasons why a lack of commitment to enabling
Graftroot may result in it being incompatible with certain use cases,
or other reasons why it could interfere with applications adopting
such outputs.

@Natanael: all of these concerns only apply to a new hypothetical
Taproot/Graftroot output type, which combines pay-to-pubkey and
pay-to-script in a single scriptPubKey that just contains a public
key. It doesn't apply to existing P2SH like constructions.

Also, the concern of making Graftroot optional does not apply to
Taproot, as the Taproot spending path's script is committed to (using
scriptPubKey = P + H(P,script)*G), allowing the script to be
explicitly chosen to be a non-spendable script, which the author could
prove is the case (without revealing it to the entire world).

It is also always possible to create a "script only" Taproot output
(without key that can unconditionally spend), by picking a pubkey that
is provably unspendable (hashing onto a curve point, in particular),
or through pubkey recovery.

Cheers,

-- 
Pieter
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Gregory Maxwell via bitcoin-dev]

On Wed, May 23, 2018 at 10:06 PM, Natanael via bitcoin-dev
 wrote:
> Consider for example a P2SH address for some fund, where you create a
> transaction in advance. Even if the parties involved in signing the
> transaction would agree (collude), the original intent of this particular
> P2SH address may be to hold the fund accountable by enforcing some given
> rules by script. To be able to circumvent the rules could break the purpose
> of the fund.

I am having a bit of difficulty understanding your example.

If graftroot were possible it would mean that the funds were paid to a
public key.  That holder(s) of the corresponding private key could
sign without constraint, and so the accoutability you're expecting
wouldn't exist there regardless of graftroot.

I think maybe your example is only making the case that it should be
possible to send funds constrained by a script without a public key
ever existing at all.  If so, I agree-- but that wasn't the question
here as I understood it.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Natanael via bitcoin-dev]

Den tis 22 maj 2018 20:18Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> skrev:

> Hello all,
>
> Given the recent discussions about Taproot [1] and Graftroot [2], I
> was wondering if a practical deployment needs a way to explicitly
> enable or disable the Graftroot spending path. I have no strong
> reasons why this would be necessary, but I'd like to hear other
> people's thoughts.
>

I'm definitely in favor of the suggestion of requiring a flag to allow the
usage of these in a transaction, so that you get to choose in advance if
the script will be static or "editable".

Consider for example a P2SH address for some fund, where you create a
transaction in advance. Even if the parties involved in signing the
transaction would agree (collude), the original intent of this particular
P2SH address may be to hold the fund accountable by enforcing some given
rules by script. To be able to circumvent the rules could break the purpose
of the fund.

The name of the scheme escapes me, but this could include a variety of
proof-requiring committed transactions, like say a transaction that will
pay out if you can provide a proof satisfying some conditions such as
embedding the solution to a given problem. This fund would only be supposed
to pay out of the published conditions are met (which may include an expiry
date).

To then use taproot / graftroot to withdraw the funds despite this
possibility not showing in the published script could be problematic.

I'm simultaneously in favor of being able to have scripts where the usage
of taproot / graftroot isn't visible in advance, but it must simultaneously
be possible to prove a transaction ISN'T using it.

>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Andrew Poelstra via bitcoin-dev]

On Wed, May 23, 2018 at 01:50:13PM +, Andrew Poelstra via bitcoin-dev wrote:
> 
> Graftroot also break blind signature schemes. Consider a protocol such as [1]
> where some party has a bunch of UTXOs all controlled (in part) by the same
> key X. This party produces blind signatures on receipt of new funds, and can
> only verify the number of signatures he produces, not anything about what he
> is signing.
> 
> BTW, the same concern holds for SIGHASH_NOINPUT, which I'd also like to be
> disable-able. Maybe we should extend one of ZmnSCPxj's suggestions to include
> a free "flags" byte or two in the witness?
> 
> (I also had the same concern about signature aggregation. It seems like it's
> pretty hard to preserve the "one signature = at most one input" invariant of
> Bitcoin, but I think it's important that it is preserved, at least for
> outputs that need it.)
> 
> Or maybe, since it appears it will require a space hit to support optional
> graftroot anyway, we should simply not include it in a proposal for Taproot,
> since there would be no opportunity cost (in blockchain efficiency) to doing
> it later.
> 
> [1] https://github.com/apoelstra/scriptless-scripts/pull/1 
>

On further thought, I rescind this concern (ditto for SIGHASH_NOINPUT) (but
not for aggregate sigs, they still interact badly with blind signatures).

As long as graftroot (and NOINPUT) sigs commit to the public key, it is
possible for a server to have unique keys for every output, even while
retaining the same private key, and thereby ensure that "one sig can spend
only one output" holds. To do this, suppose the server has a BIP32 xpubkey
(xG, cc). A blind signer using the private key x can be made to sign not
only for xG, but also for any publicly-derived child keys of (xG, cc).

Here is a simple scheme that does this:

  1. Signer provides a nonce R = kG

  2. Challenger computes bip32 tweak h, chooses blinders alpha and beta,
 and computes:
 R' = R + alpha*G + beta*P
 e  = H(P + hG || R' || tx)
 e' = e + beta
 and sends e' to the signer.

  3. Signer replies with s = k + xe' (= k + beta*x + (x + h)e - he)

  4. Challenger unblinds this as s' = s + alpha + he

(This blind signature scheme is vulnerable to Wagner's attack, though see
Schnorr 2004 [1] for mitigations that are perfectly compatible with this
modified BIP32ish scheme.)

I'm unsure whether key-prefixing is _actually_ necessary for this, but it
makes the security argument much clearer since the messagehash contains
some data which can be made unique per-utxo and is committed in the chain.


Andrew


[1] 
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8ECEF929559865FD68D1D873555D18FE?doi=10.1.1.68.9836=rep1=pdf


-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[Andrew Poelstra via bitcoin-dev]

On Tue, May 22, 2018 at 11:17:42AM -0700, Pieter Wuille via bitcoin-dev wrote:
> 
> Given the recent discussions about Taproot [1] and Graftroot [2], I
> was wondering if a practical deployment needs a way to explicitly
> enable or disable the Graftroot spending path. I have no strong
> reasons why this would be necessary, but I'd like to hear other
> people's thoughts.
>

Graftroot also break blind signature schemes. Consider a protocol such as [1]
where some party has a bunch of UTXOs all controlled (in part) by the same
key X. This party produces blind signatures on receipt of new funds, and can
only verify the number of signatures he produces, not anything about what he
is signing.

BTW, the same concern holds for SIGHASH_NOINPUT, which I'd also like to be
disable-able. Maybe we should extend one of ZmnSCPxj's suggestions to include
a free "flags" byte or two in the witness?

(I also had the same concern about signature aggregation. It seems like it's
pretty hard to preserve the "one signature = at most one input" invariant of
Bitcoin, but I think it's important that it is preserved, at least for
outputs that need it.)

Or maybe, since it appears it will require a space hit to support optional
graftroot anyway, we should simply not include it in a proposal for Taproot,
since there would be no opportunity cost (in blockchain efficiency) to doing
it later.

[1] https://github.com/apoelstra/scriptless-scripts/pull/1 

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Should Graftroot be optional?

[ZmnSCPxj via bitcoin-dev]

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 = P + H(P, g, S) * G

Where `g` is the "Graftroot flag", i.e. 0 if disable Graftroot, and 1 if enable 
Graftroot.

A Graftroot spend would need to reveal P and the Taproot script S, then sign 
the Graftroot script using P (rather than Q).

If an output wants to use Graftroot but not Taproot, then it uses Q = P + H(P, 
1, {OP_FALSE}) * G, meaning the Taproot script can never succeed.  Then 
Graftroot scripts need to be signed using P.

A simple wallet software (or hardware) that only cares about spending using 
keys `Q = q * G` it controls does not have to worry about accidentally signing 
a Graftroot script, since Q is not used to sign Graftroot scripts and 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 in 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 another path.

This increases the cost of Graftroot by one point P and a Taproot script (which 
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 reveal the 
existence of a Taproot script.  Similarly, using the Taproot branch reveals 
whether or not we also had some (hidden) Graftroot branch.

--

Now the above has the massive privacy loss where using Taproot reveals whether 
or not you intended to use Graftroot too, and using Graftroot reveals whether 
or not you intended to use Taproot.

So now let us consider the equation below instead:

Q = 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 witness 
that makes Sg succeed.

If we want to use Graftroot but not Taproot, then we can agree on the script S 
= `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.  We 
only need to store H(S), not the original S (but we do need to verify that the 
original S follows the correct template above).

If we want to use Taproot but not Graftroot, then we can agree to do a `sign(P, 
0)`, which definitely cannot be used to perform a Graftroot spend.  The 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-level 
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 = 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-Graftroot 
output a Graftroot output.

Simple wallets that use Q = q * G need not worry whether signing arbitrary 
messages with that key might suddenly make their outputs spendable as Graftroot.

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 ASCII 
text file containing some benign-looking message.  For example a message 
starting with "L" is OP_PUSHDATA1 (76), the next character encodes a length.  
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 BITCOIN, DONCHA 
KNOW?\n").  Someone might challenge some fund owner to prove their control of 
some UTXO by signing such a message.  Unbeknownst to the 

[bitcoin-dev] Should Graftroot be optional?

[Pieter Wuille via bitcoin-dev]

Hello all,

Given the recent discussions about Taproot [1] and Graftroot [2], I
was wondering if a practical deployment needs a way to explicitly
enable or disable the Graftroot spending path. I have no strong
reasons why this would be necessary, but I'd like to hear other
people's thoughts.

As a refresher, the idea is that a script type could exists which
looks like a pubkey Q, but can be spent either:
* By signing the spending transaction directly using Q (key spending)
* By proving Q was derived as Q = P + H(P,S)*G, with a script S and
its inputs (Taproot script spending).
* By signing a script S using Q, and providing S's inputs (Graftroot
script spending).

Overall, these constructions let us create combined
pay-to-pubkey-or-script outputs that are indistinguishable, and don't
even reveal a script spending path existed in the first place when the
key spending path is used. The two approaches ((T)aproot and
(G)raftroot) for the script spending path have different trade-offs:
* T outputs can be derived noninteractively from key and scripts; G
outputs need an interaction phase where the key owner(s) sign off on
the potential script spending paths.
* T lets you prove what all the different spending paths are.
* T without any other technology only needs to reveal an additional
point when spending a single script; G needs half-aggregated
signatures [3] to achieve the same, which complicates design (see
[4]).
* G is more compact when dealing with many spending paths (O(1) in the
number of spending paths), while T spends need to be combined with
Merkle branches to deal with large number of spends (and even then is
still O(log n)).
* G spending paths can be added after the output is created; T
requires them be fixed at output creation time.

My question is whether it is safe to always permit both types of
script spending paths, or an explicit commitment to whether Graftroot
is permitted is necessary. In theory, it seems that this shouldn't be
needed: the key owners are always capable of spending the funds
anyway, so them choosing to delegate to others shouldn't enable
anything that isn't
possible by the key owners already.

There are a few concerns, however:

* Accidentally (participating in) signing a script may have more broad
consequences. Without Graftroot, that effect is limited to a single
transaction with specific inputs and outputs, and only as long as all
those inputs are unspent. A similar but weaker concern exists for
SIGHASH_NOINPUT.

* In a multisignature setting (where the top level key is an aggregate
of multiple participants), the above translates to the ability for a
(threshold satsisfying) subset of participants being able to (possibly
permanently) remove others from the set of signers (rather than for a
single output).

* In a situation where private keys are stored in an HSM, without
Graftroot an attacker needs access to the device and convince it to
sign for every output he wants to steal (assuming the HSM prevents
leaking private keys). With Graftroot, the HSM may be tricked into
signing a script that does not include itself. Arguably, in a
Graftroot setting such an HSM would need a degree of protection
similar to not leaking private keys applied to not signing scripts,
but this may be less obvious.

Overall, none of these are convincing points, but they do make me
uncomfortable about the effect the Graftroot spending path may have on
some use cases. Given that Taproot/Graftroot's primary advantage is
increasing fungibility by making all outputs look identical, it seems
good to discuss potential reasons such outputs couldn't or wouldn't be
adopted in certain applications.

  [1] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html
  [2] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html
  [3] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014308.html
  [4] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html

Cheers,

-- 
Pieter
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev