Re: [bitcoin-dev] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

[Russell O'Connor via bitcoin-dev]

Bitcoin Core is somewhat outside my core competence, but the various
OP_PUSHDATA are already multi-byte opcodes and GetOp already has a data
return parameter that is suitable for returning the payload of an immediate
32-byte data variant of OP_SECURETHEBAG.  All that I expect is needed is to
ensure that nowhere else is using a non-empty data-field as a proxy for a
non-empty push operation and fixing any such occurrences if they exist.
(AFAIKT there are only a handful of calls to GetOp).

It is probably worth updating the tapscript implementation to better
prepare it for new uses of OP_SUCCESSx.  Parsing should halt when an
OP_SUCCESSx is encountered, by having GetScriptOp advance the pc to end
after encountering such a code (decoding Script is no longer meaningful
after an OP_SUCCESS is encountered).  However, that means that GetScriptOp
needs to know what version of script it is expected to be parsing.  This
could be done by sending down some versioning flags, possibly by adding a
versioning field to CScript that can be initialized @
https://github.com/sipa/bitcoin/blob/7ddc7027b2cbdd11416809400c588e585a8b44ed/src/script/interpreter.cpp#L1679
or some other mechanism (and at the same time perhaps having GetSigOpCount
return 0 for tapscript, since counting sigops is not really meaningful in
tapscript). There are probably other reasonable approaches too (e.g your
option 2 below).  I could write some code to illustrate what I'm thinking
if you feel that would be helpful and I do think such changes around
OP_SUCCESS should be implemented regardless of whether we move forward with
OP_SECURETHEBAG or not.

It is probably worth doing this properly the first time around if we are
going to do it at all.

P.S. OP_RESERVED1 has been renamed to OP_SUCCESS137 in bip-tapscript.


>
> On Mon, Jun 24, 2019 at 6:47 PM Jeremy  wrote:

> I agree in principal, but I think that's just a bit of 'how things are'
> versus how they should be.
>
> I disagree that we get composability semantics because of OP_IF. E.g., the
> script "OP_IF  " and "OP_END" are two scripts that separately are
> invalid as parsed, but together are valid. OP_IF already imposes some
> lookahead functionality... but as I understand it, it may be feasible to
> get rid of OP_IF for tapscripts anyways. Also in this bucket are P2SH and
> segwit, which I think breaks this because the concat of two p2sh scripts or
> segwit scripts is not the same as them severally.
>
> I also think that the OP_SECURETHEBAG use of pushdata is a backwards
> compatible hack: we can always later redefine the parser to parse
> OP_SECURETHEBAG as the 34 byte opcode, recapturing the purity of the
> semantics. We can also fix it to not use an extra byte in a future tapleaf
> version.
>

> In any case, I don't disagree with figuring out what patching the parser
> to handle multibyte opcodes would look like. If that sort of upgrade-path
> were readily available when I wrote this, it's how I would have done it.
> There are two approaches I looked at mostly:
>
> 1) Adding flags to GetOp to change how it parses
>   a) Most of the same code paths used for new and old script
>   b) Higher risk of breaking something in old script style/downstream
>   c) Cleans up only one issue (multibyte opcodes) leaves other warts in
> place
>   d) less bikesheddable design (mostly same as old script)
>   e) code not increased in size
> 2) Adding a completely new interpreter for Tapscript
>   a) Fork the existing interpreter code
>   b) For all places where scripts are run, switch based on if it is
> tapscript or not
>   c) Can clean up various semantics, can even do fancier things like
> huffman encode opcodes to less than a byte
>   d) Can clearly separate parsing the script from executing it
>   e) Can improve versioning techniques
>   f) Low risk of breaking something in old script style/downstream
>   g) Increases amount of code substantially
>   h) Bikesheddable design (everything is on the table).
>   i) probably a better general mechanism for future changes to script
> parsing, less consensus risk
>   j) More compatible with templated script as well.
>
> If not clear, I think that 2 is probably a better approach, but I'm
> worried that 2.h means this would take a much longer time to implement.
>
> 2 can be segmented into two components:
>
> 1) the architecture of script parser versioning
> 2) the actual new script version
>
> I think that component 1 can be relatively non controversial, thankfully,
> using tapleaf versions (the architecture question is more around code
> structure). A proof of concept of this would be to have a fork that uses
> two independent, but identical, script parsers.
>
> Part two of this plan would be to modify one of the versions
> substantially. I'm not sure what exists on the laundry list, but I think it
> would be possible to pick a few worthwhile cleanups. E.g.:
>
> 1) Multibyte opcodes
> 2) Templated scripts
> 3) Huffman Encoding opcodes
> 4) OP_IF handling (maybe 

Re: [bitcoin-dev] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

[Jeremy via bitcoin-dev]

I agree in principal, but I think that's just a bit of 'how things are'
versus how they should be.

I disagree that we get composability semantics because of OP_IF. E.g., the
script "OP_IF  " and "OP_END" are two scripts that separately are
invalid as parsed, but together are valid. OP_IF already imposes some
lookahead functionality... but as I understand it, it may be feasible to
get rid of OP_IF for tapscripts anyways. Also in this bucket are P2SH and
segwit, which I think breaks this because the concat of two p2sh scripts or
segwit scripts is not the same as them severally.

I also think that the OP_SECURETHEBAG use of pushdata is a backwards
compatible hack: we can always later redefine the parser to parse
OP_SECURETHEBAG as the 34 byte opcode, recapturing the purity of the
semantics. We can also fix it to not use an extra byte in a future tapleaf
version.



In any case, I don't disagree with figuring out what patching the parser to
handle multibyte opcodes would look like. If that sort of upgrade-path were
readily available when I wrote this, it's how I would have done it. There
are two approaches I looked at mostly:

1) Adding flags to GetOp to change how it parses
  a) Most of the same code paths used for new and old script
  b) Higher risk of breaking something in old script style/downstream
  c) Cleans up only one issue (multibyte opcodes) leaves other warts in
place
  d) less bikesheddable design (mostly same as old script)
  e) code not increased in size
2) Adding a completely new interpreter for Tapscript
  a) Fork the existing interpreter code
  b) For all places where scripts are run, switch based on if it is
tapscript or not
  c) Can clean up various semantics, can even do fancier things like
huffman encode opcodes to less than a byte
  d) Can clearly separate parsing the script from executing it
  e) Can improve versioning techniques
  f) Low risk of breaking something in old script style/downstream
  g) Increases amount of code substantially
  h) Bikesheddable design (everything is on the table).
  i) probably a better general mechanism for future changes to script
parsing, less consensus risk
  j) More compatible with templated script as well.

If not clear, I think that 2 is probably a better approach, but I'm worried
that 2.h means this would take a much longer time to implement.

2 can be segmented into two components:

1) the architecture of script parser versioning
2) the actual new script version

I think that component 1 can be relatively non controversial, thankfully,
using tapleaf versions (the architecture question is more around code
structure). A proof of concept of this would be to have a fork that uses
two independent, but identical, script parsers.

Part two of this plan would be to modify one of the versions substantially.
I'm not sure what exists on the laundry list, but I think it would be
possible to pick a few worthwhile cleanups. E.g.:

1) Multibyte opcodes
2) Templated scripts
3) Huffman Encoding opcodes
4) OP_IF handling (maybe just get rid of it in favor of conditional Verify
semantics)

And make it clear that because we can add future script versions fairly
easily, this is a sufficient step.


Does that seem in line with your understanding of how this might be done?
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

[Russell O'Connor via bitcoin-dev]

I suspect that your conjecture is true.  And given that it is plausible
that we would want to add an opcode to tweak public keys, it seems like a
reason design to avoid accidental covenants.
(That said, I strongly prefer that the SECURETHEBAG data be the 32-bytes
immediately following the opcode rather than a OP_PUSHDATA, and I'd be
willing to help code this up (see below)).

On Mon, Jun 24, 2019 at 2:07 PM Jeremy  wrote:

> Do you think the following hypothesis is more or less true:
>
> H: There is no set of pure extensions* to script E such that enabling E
> and OP_SECURETHEBAG as proposed enables recursive covenants, but E alone
> does not enable recursive covenants?
>
> * Of course there are things that specifically are specifically designed
> to switch on if OP_SECURETHEBAG, so pure means normal things like OP_CAT
> that are a function of the arguments on the stack or hashed txn data.
>
> This is the main draw of the design I proposed, it should be highly
> improbable or impossible to accidentally introduce more behavior than
> intended with a new opcode.
>
> I think that given that H is not true for the stack reading version of the
> opcode, we should avoid doing it unless strongly motivated, so as to permit
> more flexibility for which opcodes we can add in the future without
> introducing recursion unless it is explicitly intended.
>

On Sat, Jun 1, 2019 at 12:47 PM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> A particularly useful topic of discussion is how best to eliminate the
> PUSHDATA and treat OP_SECURETHEBAG like a pushdata directly. I thought
> about how the interpreter works and is implemented and couldn't come up
> with something noninvasive.
>

We shouldn't be using the complexity of the changes to the Bitcoin Core a
measure of the complexity of a proposal.  That is looking the issue from
the wrong side.  If we measure the complexity of Script proposals by how
hard it is to change Bitcoin Core, what will happen is more and more of the
incidental details of Bitcoin Core's implementation will be pulled into the
semantics of Script (e.g. the fact that surrounding opcode values are
readily available in Bitcoin Core's particular implementation of its Script
interpreter).  Instead we should use the complexity of how hard it is to
reason about the new Script semantics.

The peeking semantics of OP_SECURETHEBAG is particularly awful because it
more-or-less breaks the fact that Bitcoin Script can be decomposed into
individual units of "opcodes" whose semantics and be individually
described, and it harms the composability of Bitcoin Script where you can
divide the script between any opcodes and the semantics of the
concatenation of those two scripts is simply the composition of the
semantics of the two halves.  (For those interested in formal semantics,
what we have here is a monoid homomorphism from list of opcodes (syntax) to
stack transformation functions (with side-effects) under (Kleisli)
composition (semantics).) Being able to decompose a Bitcoin Script this way
and reasoning about components is how one would reason about Bitcoin Script
in practice.  (Technically the structure is more involved than a list of
opcodes due to OP_IF, and instead you get a railroad diagram
).

Putting the 32 bytes of data required by OP_SECURETHEBAG immediately after
the opcode, like how OP_PUSHDATA* works, is a superior design choice.  It
lets us treat the opcodes and its immediate data as an atomic unit when
reasoning about Script and removes the need to define what happens when
OP_SECURETHEBAG is not followed by an OP_PUSDATA.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

[Jeremy via bitcoin-dev]

Do you think the following hypothesis is more or less true:

H: There is no set of pure extensions* to script E such that enabling E and
OP_SECURETHEBAG as proposed enables recursive covenants, but E alone does
not enable recursive covenants?

* Of course there are things that specifically are specifically designed to
switch on if OP_SECURETHEBAG, so pure means normal things like OP_CAT that
are a function of the arguments on the stack or hashed txn data.

This is the main draw of the design I proposed, it should be highly
improbable or impossible to accidentally introduce more behavior than
intended with a new opcode.

I think that given that H is not true for the stack reading version of the
opcode, we should avoid doing it unless strongly motivated, so as to permit
more flexibility for which opcodes we can add in the future without
introducing recursion unless it is explicitly intended.



On Mon, Jun 24, 2019, 7:35 AM Russell O'Connor 
wrote:

> OP_SECURETHEBAG doesn't include the script being executed (i.e the
> scriptPubKey specified in the output that is redeemed by this input) in its
> hash like ordinary signatures do
> .
> Of course, this ScriptPubKey is indirectly committed to through the input's
> prevoutpoint.  However Script isn't able to reconstruct this script being
> executed from the prevoutpoint in tapscript without an implementation of
> public key tweeking in Bitcoin Script.
>
> On Sun, Jun 23, 2019 at 2:41 AM Jeremy Rubin 
> wrote:
>
>> Can you clarify this comment?
>>
>> We do in fact commit to the script and scriptsig itself (not the witness
>> stack) in OP_SECURETHEBAG (unless I'm missing what you meant)?
>>
>> On Thu, Jun 20, 2019, 10:59 AM Russell O'Connor via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>> Just to be clear, while OP_CHECKTXDIGESTVERIFY would enable this style
>>> of covenants if it pulled data from the stack, the OP_SECURETHEBAG
>>> probably cannot create covenants even if it were to pull the data from the
>>> stack unless some OP_TWEEKPUBKEY operation is added to Script because the
>>> "commitment of the script itself" isn't part of the OP_SECURETHEBAG.
>>>
>>> So with regards to OP_SECURETHEBAG, I am also "not really seeing any
>>> reason to complicate the spec to ensure the digest is precommitted as part
>>> of the opcode."
>>>
>>> On Thu, Jun 6, 2019 at 3:33 AM ZmnSCPxj via bitcoin-dev <
>>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>>
 Good morning aj,


 Sent with ProtonMail Secure Email.

 ‐‐‐ Original Message ‐‐‐
 On Wednesday, June 5, 2019 5:30 PM, Anthony Towns via bitcoin-dev <
 bitcoin-dev@lists.linuxfoundation.org> wrote:

 > On Fri, May 31, 2019 at 10:35:45PM -0700, Jeremy via bitcoin-dev
 wrote:
 >
 > > OP_CHECKOUTPUTSHASHVERIFY is retracted in favor of OP_SECURETHEBAG*.
 >
 > I think you could generalise that slightly and make it fit in
 > with the existing opcode naming by calling it something like
 > "OP_CHECKTXDIGESTVERIFY" and pull a 33-byte value from the stack,
 > consisting of a sha256 hash and a sighash-byte, and adding a new
 sighash
 > value corresponding to the set of info you want to include in the
 hash,
 > which I think sounds a bit like "SIGHASH_EXACTLY_ONE_INPUT |
 SIGHASH_ALL"
 >
 > FWIW, I'm not really seeing any reason to complicate the spec to
 ensure
 > the digest is precommitted as part of the opcode.
 >

 I believe in combination with `OP_LEFT` and `OP_CAT` this allows
 Turing-complete smart contracts, in much the same way as
 `OP_CHECKSIGFROMSTACK`?

 Pass in the spent transaction (serialised for txid) and the spending
 transaction (serialised for sighash) as part of the witness of the spending
 transaction.

 Script verifies that the spending transaction witness value is indeed
 the spending transaction by `OP_SHA256  OP_SWAP OP_CAT
 OP_CHECKTXDIGESTVERIFY`.
 Script verifies the spent transaction witness value is indeed the spent
 transaction by hashing it, then splitting up the hash with `OP_LEFT` into
 bytes, and comparing the bytes to the bytes in the input of the spending
 transaction witness value (txid being the bytes in reversed order).

 Then the Script can extract a commitment of itself by extracting the
 output of the spent transaction.
 This lets the Script check that the spending transaction also pays to
 the same script.

 The Script can then access a state value, for example from an
 `OP_RETURN` output of the spent transaction, and enforce that a correct
 next-state is used in the spending transaction.
 If the state is too large to fit in a standard `OP_RETURN`, then the
 current state can be passed in as a witness and validated against a hash
 commitment in an `OP_RETURN` 

Re: [bitcoin-dev] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

[Russell O'Connor via bitcoin-dev]

OP_SECURETHEBAG doesn't include the script being executed (i.e the
scriptPubKey specified in the output that is redeemed by this input) in its
hash like ordinary signatures do
.
Of course, this ScriptPubKey is indirectly committed to through the input's
prevoutpoint.  However Script isn't able to reconstruct this script being
executed from the prevoutpoint in tapscript without an implementation of
public key tweeking in Bitcoin Script.

On Sun, Jun 23, 2019 at 2:41 AM Jeremy Rubin 
wrote:

> Can you clarify this comment?
>
> We do in fact commit to the script and scriptsig itself (not the witness
> stack) in OP_SECURETHEBAG (unless I'm missing what you meant)?
>
> On Thu, Jun 20, 2019, 10:59 AM Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Just to be clear, while OP_CHECKTXDIGESTVERIFY would enable this style
>> of covenants if it pulled data from the stack, the OP_SECURETHEBAG
>> probably cannot create covenants even if it were to pull the data from the
>> stack unless some OP_TWEEKPUBKEY operation is added to Script because the
>> "commitment of the script itself" isn't part of the OP_SECURETHEBAG.
>>
>> So with regards to OP_SECURETHEBAG, I am also "not really seeing any
>> reason to complicate the spec to ensure the digest is precommitted as part
>> of the opcode."
>>
>> On Thu, Jun 6, 2019 at 3:33 AM ZmnSCPxj via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>> Good morning aj,
>>>
>>>
>>> Sent with ProtonMail Secure Email.
>>>
>>> ‐‐‐ Original Message ‐‐‐
>>> On Wednesday, June 5, 2019 5:30 PM, Anthony Towns via bitcoin-dev <
>>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>>
>>> > On Fri, May 31, 2019 at 10:35:45PM -0700, Jeremy via bitcoin-dev wrote:
>>> >
>>> > > OP_CHECKOUTPUTSHASHVERIFY is retracted in favor of OP_SECURETHEBAG*.
>>> >
>>> > I think you could generalise that slightly and make it fit in
>>> > with the existing opcode naming by calling it something like
>>> > "OP_CHECKTXDIGESTVERIFY" and pull a 33-byte value from the stack,
>>> > consisting of a sha256 hash and a sighash-byte, and adding a new
>>> sighash
>>> > value corresponding to the set of info you want to include in the hash,
>>> > which I think sounds a bit like "SIGHASH_EXACTLY_ONE_INPUT |
>>> SIGHASH_ALL"
>>> >
>>> > FWIW, I'm not really seeing any reason to complicate the spec to ensure
>>> > the digest is precommitted as part of the opcode.
>>> >
>>>
>>> I believe in combination with `OP_LEFT` and `OP_CAT` this allows
>>> Turing-complete smart contracts, in much the same way as
>>> `OP_CHECKSIGFROMSTACK`?
>>>
>>> Pass in the spent transaction (serialised for txid) and the spending
>>> transaction (serialised for sighash) as part of the witness of the spending
>>> transaction.
>>>
>>> Script verifies that the spending transaction witness value is indeed
>>> the spending transaction by `OP_SHA256  OP_SWAP OP_CAT
>>> OP_CHECKTXDIGESTVERIFY`.
>>> Script verifies the spent transaction witness value is indeed the spent
>>> transaction by hashing it, then splitting up the hash with `OP_LEFT` into
>>> bytes, and comparing the bytes to the bytes in the input of the spending
>>> transaction witness value (txid being the bytes in reversed order).
>>>
>>> Then the Script can extract a commitment of itself by extracting the
>>> output of the spent transaction.
>>> This lets the Script check that the spending transaction also pays to
>>> the same script.
>>>
>>> The Script can then access a state value, for example from an
>>> `OP_RETURN` output of the spent transaction, and enforce that a correct
>>> next-state is used in the spending transaction.
>>> If the state is too large to fit in a standard `OP_RETURN`, then the
>>> current state can be passed in as a witness and validated against a hash
>>> commitment in an `OP_RETURN` output.
>>>
>>> I believe this is the primary reason against not pulling data from the
>>> stack.
>>>
>>> Regards,
>>> ZmnSCPxj
>>> ___
>>> 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
>>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev