public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed

* [bitcoin-dev] Should Graftroot be optional?
@ 2018-05-22 18:17 Pieter Wuille
  2018-05-23  6:15 ` ZmnSCPxj
                   ` (3 more replies)
  0 siblings, 4 replies; 21+ messages in thread
From: Pieter Wuille @ 2018-05-22 18:17 UTC (permalink / raw)
  To: 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


^ permalink raw reply	[flat|nested] 21+ messages in thread

• * Re: [bitcoin-dev] Should Graftroot be optional?
    2018-05-22 18:17 [bitcoin-dev] Should Graftroot be optional? Pieter Wuille
  @ 2018-05-23  6:15 ` ZmnSCPxj
    2018-05-23 13:50 ` Andrew Poelstra
                     ` (2 subsequent siblings)
    3 siblings, 0 replies; 21+ messages in thread
  From: ZmnSCPxj @ 2018-05-23  6:15 UTC (permalink / raw)
    To: Pieter Wuille, Bitcoin Protocol Discussion
  
  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, {<p1*G> 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 signer, the message is actually also a valid Script (`OP_PUSHDATA1(65 random bytes)`) that lets the challenger trivially acquire access to the funds via Graftroot.
  
  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 vulnerability for ordinary wallets, while keeping the property that use of Taproot and Graftroot is invisible if the onchain spend does not involve Taproot/Graftroot.
  
  Regards,
  ZmnSCPxj
  
  
  ^ permalink raw reply	[flat|nested] 21+ messages in thread

• * Re: [bitcoin-dev] Should Graftroot be optional?
    2018-05-22 18:17 [bitcoin-dev] Should Graftroot be optional? Pieter Wuille
    2018-05-23  6:15 ` ZmnSCPxj
  @ 2018-05-23 13:50 ` Andrew Poelstra
    2018-05-23 17:52   ` Andrew Poelstra
    2018-05-23 22:06 ` Natanael
    2018-05-24  1:58 ` Pieter Wuille
    3 siblings, 1 reply; 21+ messages in thread
  From: Andrew Poelstra @ 2018-05-23 13:50 UTC (permalink / raw)
    To: Pieter Wuille, Bitcoin Protocol Discussion
  
  [-- Attachment #1: Type: text/plain, Size: 1776 bytes --]
  
  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
  
  
  [-- Attachment #2: signature.asc --]
  [-- Type: application/pgp-signature, Size: 455 bytes --]
  
  ^ permalink raw reply	[flat|nested] 21+ messages in thread

• • * Re: [bitcoin-dev] Should Graftroot be optional?
      2018-05-23 13:50 ` Andrew Poelstra
    @ 2018-05-23 17:52   ` Andrew Poelstra
      2018-05-25  9:46     ` Johnson Lau
      0 siblings, 1 reply; 21+ messages in thread
    From: Andrew Poelstra @ 2018-05-23 17:52 UTC (permalink / raw)
      To: Bitcoin Protocol Discussion
    
    [-- Attachment #1: Type: text/plain, Size: 3112 bytes --]
    
    On Wed, May 23, 2018 at 01:50:13PM +0000, 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&rep=rep1&type=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
    
    
    [-- Attachment #2: signature.asc --]
    [-- Type: application/pgp-signature, Size: 455 bytes --]
    
    ^ permalink raw reply	[flat|nested] 21+ messages in thread

  • • * Re: [bitcoin-dev] Should Graftroot be optional?
        2018-05-23 17:52   ` Andrew Poelstra
      @ 2018-05-25  9:46     ` Johnson Lau
        0 siblings, 0 replies; 21+ messages in thread
      From: Johnson Lau @ 2018-05-25  9:46 UTC (permalink / raw)
        To: Andrew Poelstra, 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 <bitcoin-dev@lists•linuxfoundation.org> wrote:
      > 
      > On Wed, May 23, 2018 at 01:50:13PM +0000, 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&rep=rep1&type=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
      
      
      
      
      ^ permalink raw reply	[flat|nested] 21+ messages in thread

• * Re: [bitcoin-dev] Should Graftroot be optional?
    2018-05-22 18:17 [bitcoin-dev] Should Graftroot be optional? Pieter Wuille
    2018-05-23  6:15 ` ZmnSCPxj
    2018-05-23 13:50 ` Andrew Poelstra
  @ 2018-05-23 22:06 ` Natanael
    2018-05-23 23:45   ` Gregory Maxwell
    2018-05-24  1:58 ` Pieter Wuille
    3 siblings, 1 reply; 21+ messages in thread
  From: Natanael @ 2018-05-23 22:06 UTC (permalink / raw)
    To: Pieter Wuille, Bitcoin Dev
  
  [-- Attachment #1: Type: text/plain, Size: 1694 bytes --]
  
  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.
  
  >
  
  [-- Attachment #2: Type: text/html, Size: 2738 bytes --]
  
  ^ permalink raw reply	[flat|nested] 21+ messages in thread

• • * Re: [bitcoin-dev] Should Graftroot be optional?
      2018-05-23 22:06 ` Natanael
    @ 2018-05-23 23:45   ` Gregory Maxwell
      2018-05-24  9:32     ` Natanael
      0 siblings, 1 reply; 21+ messages in thread
    From: Gregory Maxwell @ 2018-05-23 23:45 UTC (permalink / raw)
      To: Natanael, Bitcoin Protocol Discussion
    
    On Wed, May 23, 2018 at 10:06 PM, Natanael via bitcoin-dev
    <bitcoin-dev@lists•linuxfoundation.org> 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.
    
    
    ^ permalink raw reply	[flat|nested] 21+ messages in thread

  • • * Re: [bitcoin-dev] Should Graftroot be optional?
        2018-05-23 23:45   ` Gregory Maxwell
      @ 2018-05-24  9:32     ` Natanael
        0 siblings, 0 replies; 21+ messages in thread
      From: Natanael @ 2018-05-24  9:32 UTC (permalink / raw)
        To: Gregory Maxwell; +Cc: Bitcoin Dev
      
      [-- Attachment #1: Type: text/plain, Size: 1309 bytes --]
      
      Den tor 24 maj 2018 01:45Gregory Maxwell <greg@xiph•org> 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.
      
      >
      
      [-- Attachment #2: Type: text/html, Size: 1884 bytes --]
      
      ^ permalink raw reply	[flat|nested] 21+ messages in thread

• * Re: [bitcoin-dev] Should Graftroot be optional?
    2018-05-22 18:17 [bitcoin-dev] Should Graftroot be optional? Pieter Wuille
                     ` (2 preceding siblings ...)
    2018-05-23 22:06 ` Natanael
  @ 2018-05-24  1:58 ` Pieter Wuille
    2018-05-24  2:08   ` Gregory Maxwell
    3 siblings, 1 reply; 21+ messages in thread
  From: Pieter Wuille @ 2018-05-24  1:58 UTC (permalink / raw)
    To: Bitcoin Dev
  
  On Tue, May 22, 2018 at 11:17 AM, Pieter Wuille <pieter.wuille@gmail•com> 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
  
  
  ^ permalink raw reply	[flat|nested] 21+ messages in thread

• • * Re: [bitcoin-dev] Should Graftroot be optional?
      2018-05-24  1:58 ` Pieter Wuille
    @ 2018-05-24  2:08   ` Gregory Maxwell
      2018-05-24  9:44     ` Natanael
      2018-05-25 10:14     ` Johnson Lau
      0 siblings, 2 replies; 21+ messages in thread
    From: Gregory Maxwell @ 2018-05-24  2:08 UTC (permalink / raw)
      To: Pieter Wuille, Bitcoin Protocol Discussion
    
    On Thu, May 24, 2018 at 1:58 AM, Pieter Wuille via bitcoin-dev
    <bitcoin-dev@lists•linuxfoundation.org> 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.
    
    
    ^ permalink raw reply	[flat|nested] 21+ messages in thread

  • • * Re: [bitcoin-dev] Should Graftroot be optional?
        2018-05-24  2:08   ` Gregory Maxwell
      @ 2018-05-24  9:44     ` Natanael
        2018-05-24 12:39       ` Andrew Poelstra
        2018-05-25 10:14     ` Johnson Lau
        1 sibling, 1 reply; 21+ messages in thread
      From: Natanael @ 2018-05-24  9:44 UTC (permalink / raw)
        To: Gregory Maxwell, Bitcoin Dev
      
      [-- Attachment #1: Type: text/plain, Size: 1706 bytes --]
      
      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.
      
      >
      
      [-- Attachment #2: Type: text/html, Size: 2405 bytes --]
      
      ^ permalink raw reply	[flat|nested] 21+ messages in thread

    • • * Re: [bitcoin-dev] Should Graftroot be optional?
          2018-05-24  9:44     ` Natanael
        @ 2018-05-24 12:39       ` Andrew Poelstra
          0 siblings, 0 replies; 21+ messages in thread
        From: Andrew Poelstra @ 2018-05-24 12:39 UTC (permalink / raw)
          To: Natanael, Bitcoin Protocol Discussion
        
        [-- Attachment #1: Type: text/plain, Size: 1848 bytes --]
        
        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
        
        
        [-- Attachment #2: signature.asc --]
        [-- Type: application/pgp-signature, Size: 455 bytes --]
        
        ^ permalink raw reply	[flat|nested] 21+ messages in thread

    • * Re: [bitcoin-dev] Should Graftroot be optional?
        2018-05-24  2:08   ` Gregory Maxwell
        2018-05-24  9:44     ` Natanael
      @ 2018-05-25 10:14     ` Johnson Lau
        2018-06-01  0:25       ` Pieter Wuille
        1 sibling, 1 reply; 21+ messages in thread
      From: Johnson Lau @ 2018-05-25 10:14 UTC (permalink / raw)
        To: Gregory Maxwell, bitcoin-dev
      
      
      
      > On 24 May 2018, at 10:08 AM, Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
      > 
      > On Thu, May 24, 2018 at 1:58 AM, Pieter Wuille via bitcoin-dev
      > <bitcoin-dev@lists•linuxfoundation.org> 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.
      
      
      ^ permalink raw reply	[flat|nested] 21+ messages in thread

    • • * Re: [bitcoin-dev] Should Graftroot be optional?
          2018-05-25 10:14     ` Johnson Lau
        @ 2018-06-01  0:25       ` Pieter Wuille
          2018-06-06 12:48         ` Tim Ruffing
          2018-06-27  7:29         ` Anthony Towns
          0 siblings, 2 replies; 21+ messages in thread
        From: Pieter Wuille @ 2018-06-01  0:25 UTC (permalink / raw)
          To: Johnson Lau; +Cc: bitcoin-dev
        
        On Fri, May 25, 2018 at 3:14 AM, Johnson Lau <jl2012@xbt•hk> 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
        
        
        ^ permalink raw reply	[flat|nested] 21+ messages in thread

      • • * Re: [bitcoin-dev] Should Graftroot be optional?
            2018-06-01  0:25       ` Pieter Wuille
          @ 2018-06-06 12:48         ` Tim Ruffing
            2018-06-06 17:04           ` Pieter Wuille
            2018-06-27  7:29         ` Anthony Towns
            1 sibling, 1 reply; 21+ messages in thread
          From: Tim Ruffing @ 2018-06-06 12:48 UTC (permalink / raw)
            To: 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
          
          
          
          
          ^ permalink raw reply	[flat|nested] 21+ messages in thread

        • • * Re: [bitcoin-dev] Should Graftroot be optional?
              2018-06-06 12:48         ` Tim Ruffing
            @ 2018-06-06 17:04           ` Pieter Wuille
              2018-06-06 21:25             ` Tim Ruffing
              0 siblings, 1 reply; 21+ messages in thread
            From: Pieter Wuille @ 2018-06-06 17:04 UTC (permalink / raw)
              To: Tim Ruffing, Bitcoin Protocol Discussion
            
            On Wed, Jun 6, 2018 at 5:48 AM, Tim Ruffing via bitcoin-dev
            <bitcoin-dev@lists•linuxfoundation.org> 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
            
            
            ^ permalink raw reply	[flat|nested] 21+ messages in thread

          • • * Re: [bitcoin-dev] Should Graftroot be optional?
                2018-06-06 17:04           ` Pieter Wuille
              @ 2018-06-06 21:25             ` Tim Ruffing
                2018-06-20 12:12               ` ZmnSCPxj
                0 siblings, 1 reply; 21+ messages in thread
              From: Tim Ruffing @ 2018-06-06 21:25 UTC (permalink / raw)
                To: Pieter Wuille, Bitcoin Protocol Discussion
              
              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
              > <bitcoin-dev@lists•linuxfoundation.org> 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,
              > 
              
              
              ^ permalink raw reply	[flat|nested] 21+ messages in thread

            • • * Re: [bitcoin-dev] Should Graftroot be optional?
                  2018-06-06 21:25             ` Tim Ruffing
                @ 2018-06-20 12:12               ` ZmnSCPxj
                  2018-06-20 14:30                 ` Gregory Maxwell
                  0 siblings, 1 reply; 21+ messages in thread
                From: ZmnSCPxj @ 2018-06-20 12:12 UTC (permalink / raw)
                  To: 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 <hash> OP_EQUALVERIFY <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 (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 reduces code reuse, though.
                
                Regards,
                ZmnSCPxj
                
                
                
                ^ permalink raw reply	[flat|nested] 21+ messages in thread

              • • * Re: [bitcoin-dev] Should Graftroot be optional?
                    2018-06-20 12:12               ` ZmnSCPxj
                  @ 2018-06-20 14:30                 ` Gregory Maxwell
                    2018-06-21  7:09                   ` ZmnSCPxj
                    0 siblings, 1 reply; 21+ messages in thread
                  From: Gregory Maxwell @ 2018-06-20 14:30 UTC (permalink / raw)
                    To: ZmnSCPxj, Bitcoin Protocol Discussion
                  
                  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.
                  
                  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.
                  
                  
                  ^ permalink raw reply	[flat|nested] 21+ messages in thread

                • • * Re: [bitcoin-dev] Should Graftroot be optional?
                      2018-06-20 14:30                 ` Gregory Maxwell
                    @ 2018-06-21  7:09                   ` ZmnSCPxj
                      0 siblings, 0 replies; 21+ messages in thread
                    From: ZmnSCPxj @ 2018-06-21  7:09 UTC (permalink / raw)
                      To: Gregory Maxwell; +Cc: Bitcoin Protocol Discussion
                    
                    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
                    
                    
                    
                    ^ permalink raw reply	[flat|nested] 21+ messages in thread

        • * Re: [bitcoin-dev] Should Graftroot be optional?
            2018-06-01  0:25       ` Pieter Wuille
            2018-06-06 12:48         ` Tim Ruffing
          @ 2018-06-27  7:29         ` Anthony Towns
            1 sibling, 0 replies; 21+ messages in thread
          From: Anthony Towns @ 2018-06-27  7:29 UTC (permalink / raw)
            To: Pieter Wuille, Bitcoin Protocol Discussion
          
          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, "", 0xffffffff)]
               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
          
          
          
          ^ permalink raw reply	[flat|nested] 21+ messages in thread

end of thread, other threads:[~2018-06-27  7:29 UTC | newest]

Thread overview: 21+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-05-22 18:17 [bitcoin-dev] Should Graftroot be optional? Pieter Wuille
2018-05-23  6:15 ` ZmnSCPxj
2018-05-23 13:50 ` Andrew Poelstra
2018-05-23 17:52   ` Andrew Poelstra
2018-05-25  9:46     ` Johnson Lau
2018-05-23 22:06 ` Natanael
2018-05-23 23:45   ` Gregory Maxwell
2018-05-24  9:32     ` Natanael
2018-05-24  1:58 ` Pieter Wuille
2018-05-24  2:08   ` Gregory Maxwell
2018-05-24  9:44     ` Natanael
2018-05-24 12:39       ` Andrew Poelstra
2018-05-25 10:14     ` Johnson Lau
2018-06-01  0:25       ` Pieter Wuille
2018-06-06 12:48         ` Tim Ruffing
2018-06-06 17:04           ` Pieter Wuille
2018-06-06 21:25             ` Tim Ruffing
2018-06-20 12:12               ` ZmnSCPxj
2018-06-20 14:30                 ` Gregory Maxwell
2018-06-21  7:09                   ` ZmnSCPxj
2018-06-27  7:29         ` Anthony Towns

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox