[bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 3071 bytes --]

Recently there have been some tapscript proposals, SIGHASH_ANYPREVOUT and
OP_CHECKOUTPUTHASHVERIFY, that aim to enable particular new features for
Bitcoin via new Script operations.  However, I think that these proposals
miss the mark when it comes to how they approach Bitcoin Script and
language features.

Bitcoin Script appears designed to be a flexible programmable system that
provides generic features to be composed to achieve various purposes.
Thus, when we design new language features for Script, we should be
striving, as much as possible, to similarly build general purpose tools
which can in turn be used for a variety of purposes.

I feel the SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY proposals fail
to achieve these design goals.  They are both are designed with very narrow
applications in mind, while also going out of their way to extend the
semantic domain of the interpretation of Bitcoin operations in new ways
that complicate their specification.  In the case of SIGHASH_ANYPREVOUT,
the semantic domain is extended by adding new counters to track the use of
various v0 and v2 signature types.  In the case of
OP_CHECKOUTPUTHASHVERIFY, it employs a new context-sensitive operation that
peeks at the value of surrounding opcodes.

Instead, I propose that, for the time being, we simply implement OP_CAT and
OP_CHECKSIGFROMSTACKVERIFY.  OP_CAT pops two byte arrays off the stack and
pushes their concatenation back onto the stack.  OP_CHECKSIGFROMSTACKVERIFY
pops a signature, message, and pubkey off the stack and performs a
bip-schnorr verification on the SHA256 hash of the message.

In concert, these two operations enable:

* Oracle signature verification, including discrete log contracts.
* Amortized secure multiparty computations (see "Amortizing Secure
Computation with Penalties" by Kumaresan and Bentov).
* Transaction introspection including:
+ Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply by
the nature of the construction.
+ Decide if a transaction has exactly one input or not. (etc.)
+ Weak covenants, which can verify output scripts to see if they are among
a set of predefined values or verify the output hash.

and presumably more applications as well.

For better or for worse, without an OP_PUBKEYTWEEK operation available, the
more interesting recursive-covenants remain largely out of reach, with the
exception of a recursive covenant that is only able to send back to its own
address, possibly abusing its own TXO value as a state variable.

All this is accomplished by two straightforward opcodes whose semantics are
pure computational operations on stack values.  The only semantic
side-effect is that OP_CHECKSIGFROMSTACKVERIFY would count towards the
existing 'sigops_passed' count.  Moreover, I feel that adding these
operations does not preclude adding more specialized opcodes in the future
as an optimization for whatever popular constructions come up, once we know
what those are.

I feel that this style of generic building blocks truly embodies what is
meant by "programmable money".

[-- Attachment #2: Type: text/html, Size: 3638 bytes --]

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[ZmnSCPxj]

Good morning Russell,

While I am sympathetic to this argument from first principles, as I understand it, it requires that provided witness inputs will become larger, compared to "shortcuts" like `SIGHASH_ANYPREVOUT` and `OP_CHECKOUTPUTSHASHVERIFY`.

For instance, to simulate `SIGHASH_ANYPREVOUT` with `OP_CAT` and `OP_CHECKSIGFROMSTACK`, I would effectively split the unsigned transaction into its "inputs" and "outputs" part, concat them and use `OP_CHECKSIGFROMSTACK` on the chaperone signature, and also use a normal `OP_CHECKSIGVERIFY` on that same chaperone signature, then dup the "outputs" part and use `OP_CHECKSIGFROMSTACK` on the "any prevout"/"noinput" signature.
I would effectively give the transaction to itself as part of the witness, and further, I would also have to very carefully write the script (admittedly the writing of the template could be done once, but it would require far more review than simple usages of the "limited" operations like `SIGHASH_ANYPREVOUT`).
So my witness stack would contain two signatures, and a duplicate of the transaction itself, plus a very much complicated script, whereas use of `SIGHASH_ANYPREVOUT` just requires two signatures and a script not much longer than pre-Schnorr multisig scripts.


It seems to me desirable, to try to reduce bandwidth consumption on the Bitcoin blockchain, including witness data.
Indeed, I had thought the whole exercise of putting `OP_CHECKSIGFROMSTACK` in a federated sidechain (Elements/Liquid) was to try to identify common patterns of usage for that opcode, and *then* to propose those common patterns as specific "optimized" opcodes as a sort of "jet" for Bitcoin itself (but not `OP_CHECKSIGFROMSTACK` itself).

Regards,
ZmnSCPxj


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Thursday, May 23, 2019 5:01 AM, Russell O'Connor via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> Recently there have been some tapscript proposals, SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY, that aim to enable particular new features for Bitcoin via new Script operations.  However, I think that these proposals miss the mark when it comes to how they approach Bitcoin Script and language features.
>
> Bitcoin Script appears designed to be a flexible programmable system that provides generic features to be composed to achieve various purposes.  Thus, when we design new language features for Script, we should be striving, as much as possible, to similarly build general purpose tools which can in turn be used for a variety of purposes.
>
> I feel the SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY proposals fail to achieve these design goals.  They are both are designed with very narrow applications in mind, while also going out of their way to extend the semantic domain of the interpretation of Bitcoin operations in new ways that complicate their specification.  In the case of SIGHASH_ANYPREVOUT, the semantic domain is extended by adding new counters to track the use of various v0 and v2 signature types.  In the case of OP_CHECKOUTPUTHASHVERIFY, it employs a new context-sensitive operation that peeks at the value of surrounding opcodes.
>
> Instead, I propose that, for the time being, we simply implement OP_CAT and OP_CHECKSIGFROMSTACKVERIFY.  OP_CAT pops two byte arrays off the stack and pushes their concatenation back onto the stack.  OP_CHECKSIGFROMSTACKVERIFY pops a signature, message, and pubkey off the stack and performs a bip-schnorr verification on the SHA256 hash of the message.
>
> In concert, these two operations enable:
>
> * Oracle signature verification, including discrete log contracts.
> * Amortized secure multiparty computations (see "Amortizing Secure Computation with Penalties" by Kumaresan and Bentov).
> * Transaction introspection including:
> + Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply by the nature of the construction.
> + Decide if a transaction has exactly one input or not. (etc.)
> + Weak covenants, which can verify output scripts to see if they are among a set of predefined values or verify the output hash.
>
> and presumably more applications as well.
>
> For better or for worse, without an OP_PUBKEYTWEEK operation available, the more interesting recursive-covenants remain largely out of reach, with the exception of a recursive covenant that is only able to send back to its own address, possibly abusing its own TXO value as a state variable.
>
> All this is accomplished by two straightforward opcodes whose semantics are pure computational operations on stack values.  The only semantic side-effect is that OP_CHECKSIGFROMSTACKVERIFY would count towards the existing 'sigops_passed' count.  Moreover, I feel that adding these operations does not preclude adding more specialized opcodes in the future as an optimization for whatever popular constructions come up, once we know what those are.
>
> I feel that this style of generic building blocks truly embodies what is meant by "programmable money".

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 3534 bytes --]

Hello ZmnSCPxj,

I agree that adding OP_CHECKSIGFROMSTACK doesn't preclude adding shortcuts
such as `SIGHASH_ANYPREVOUT` and `OP_CHECKOUTPUTSHASHVERIFY`, and I agree
we ought to support such operations directly, especially if we see
widespread use of these constructions in practice.

I think it is desirable to add OP_CHECKSIGFROMSTACK for its direct purposes
of enabling oracle verification and discreet log contracts.  Moreover, it
would be better decide if we do or do not want to do this first, because
whether or not we chose to implement a general OP_CHECKSIGFROMSTACK will
influence the design of these other proposals.

For example, if we choose to deploy OP_CHECKSIGFROMSTACK, then the design
of OP_CHECKOUTPUTSHASHVERIFY ought to be simplified to OP_PUSHOUTPUTHASH
and OP_PUSHNUMINPUTS (etc.) because the proposal would no longer be
extending the expressiveness of Bitcoin Script.  And while
OP_CHECKSIGFROMSTACK doesn't directly address whether SIGHASH_ANYPREVOUT
should be with or without a chaperone (as the simulated version with
OP_CHECKSIGFROMSTACK is necessarily chaperoned), we might get an
opportunity to learn if users are willing to take advantage of the
chaperone, or whether they rather bypass it by using a short well-known
pubkey: (e.g.
0x0200000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63)
and/or similar short signatures if we deploy OP_CHECKSIGFROMSTACK first.

Since most of the "scary" recursive convents are not available with
OP_CHECKSIGFROMSTACK within taproot (without further extensions), the
OP_CHECKSIGFROMSTACK proposal now has quite different consequences than
before.

On Thu, May 23, 2019 at 12:59 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Russell,
>
> While I am sympathetic to this argument from first principles, as I
> understand it, it requires that provided witness inputs will become larger,
> compared to "shortcuts" like `SIGHASH_ANYPREVOUT` and
> `OP_CHECKOUTPUTSHASHVERIFY`.
>
> For instance, to simulate `SIGHASH_ANYPREVOUT` with `OP_CAT` and
> `OP_CHECKSIGFROMSTACK`, I would effectively split the unsigned transaction
> into its "inputs" and "outputs" part, concat them and use
> `OP_CHECKSIGFROMSTACK` on the chaperone signature, and also use a normal
> `OP_CHECKSIGVERIFY` on that same chaperone signature, then dup the
> "outputs" part and use `OP_CHECKSIGFROMSTACK` on the "any
> prevout"/"noinput" signature.
> I would effectively give the transaction to itself as part of the witness,
> and further, I would also have to very carefully write the script
> (admittedly the writing of the template could be done once, but it would
> require far more review than simple usages of the "limited" operations like
> `SIGHASH_ANYPREVOUT`).
> So my witness stack would contain two signatures, and a duplicate of the
> transaction itself, plus a very much complicated script, whereas use of
> `SIGHASH_ANYPREVOUT` just requires two signatures and a script not much
> longer than pre-Schnorr multisig scripts.
>
>
> It seems to me desirable, to try to reduce bandwidth consumption on the
> Bitcoin blockchain, including witness data.
> Indeed, I had thought the whole exercise of putting `OP_CHECKSIGFROMSTACK`
> in a federated sidechain (Elements/Liquid) was to try to identify common
> patterns of usage for that opcode, and *then* to propose those common
> patterns as specific "optimized" opcodes as a sort of "jet" for Bitcoin
> itself (but not `OP_CHECKSIGFROMSTACK` itself).
>
> Regards,
> ZmnSCPxj
>
>
> Sent with ProtonMail Secure Email.
>

[-- Attachment #2: Type: text/html, Size: 4064 bytes --]

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Jimmy Song]

[-- Attachment #1: Type: text/plain, Size: 4196 bytes --]

Hi Russell,

This is probably a dumb question, but I'd like to get some clarity on your
proposal.

OP_CHECKSIGFROMSTACKVERIFY would pop off a signature, message and pubkey.
Presumably, the message would then have to get constructed as part of the
Script execution. What would such a message look like? What, in other
words, would you be signing and would that be similar to what signatures
sign now? Would it be a single blob that incorporates all the input/output
information in some hashed manner (like BIP143)? Or would you need separate
signatures for different parts of the transaction? Or is it something more
complicated like aggregating multiple signatures over different parts of
the transaction?

Best,

Jimmy

On Thu, May 23, 2019 at 8:35 AM Russell O'Connor via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Recently there have been some tapscript proposals, SIGHASH_ANYPREVOUT and
> OP_CHECKOUTPUTHASHVERIFY, that aim to enable particular new features for
> Bitcoin via new Script operations.  However, I think that these proposals
> miss the mark when it comes to how they approach Bitcoin Script and
> language features.
>
> Bitcoin Script appears designed to be a flexible programmable system that
> provides generic features to be composed to achieve various purposes.
> Thus, when we design new language features for Script, we should be
> striving, as much as possible, to similarly build general purpose tools
> which can in turn be used for a variety of purposes.
>
> I feel the SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY proposals fail
> to achieve these design goals.  They are both are designed with very narrow
> applications in mind, while also going out of their way to extend the
> semantic domain of the interpretation of Bitcoin operations in new ways
> that complicate their specification.  In the case of SIGHASH_ANYPREVOUT,
> the semantic domain is extended by adding new counters to track the use of
> various v0 and v2 signature types.  In the case of
> OP_CHECKOUTPUTHASHVERIFY, it employs a new context-sensitive operation that
> peeks at the value of surrounding opcodes.
>
> Instead, I propose that, for the time being, we simply implement OP_CAT
> and OP_CHECKSIGFROMSTACKVERIFY.  OP_CAT pops two byte arrays off the stack
> and pushes their concatenation back onto the stack.
> OP_CHECKSIGFROMSTACKVERIFY pops a signature, message, and pubkey off the
> stack and performs a bip-schnorr verification on the SHA256 hash of the
> message.
>
> In concert, these two operations enable:
>
> * Oracle signature verification, including discrete log contracts.
> * Amortized secure multiparty computations (see "Amortizing Secure
> Computation with Penalties" by Kumaresan and Bentov).
> * Transaction introspection including:
> + Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply
> by the nature of the construction.
> + Decide if a transaction has exactly one input or not. (etc.)
> + Weak covenants, which can verify output scripts to see if they are among
> a set of predefined values or verify the output hash.
>
> and presumably more applications as well.
>
> For better or for worse, without an OP_PUBKEYTWEEK operation available,
> the more interesting recursive-covenants remain largely out of reach, with
> the exception of a recursive covenant that is only able to send back to its
> own address, possibly abusing its own TXO value as a state variable.
>
> All this is accomplished by two straightforward opcodes whose semantics
> are pure computational operations on stack values.  The only semantic
> side-effect is that OP_CHECKSIGFROMSTACKVERIFY would count towards the
> existing 'sigops_passed' count.  Moreover, I feel that adding these
> operations does not preclude adding more specialized opcodes in the future
> as an optimization for whatever popular constructions come up, once we know
> what those are.
>
> I feel that this style of generic building blocks truly embodies what is
> meant by "programmable money".
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 5306 bytes --]

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 5519 bytes --]

Hi Jimmy,

The message could really be anything.  For example, in discreet log
contracts, AFAIU, you might have a specific public key from a trusted third
party (the Oracle) that is signs the closing price of corn in BTC on
2019-05-23 with a particular nonce dedicated to that product-date pair, in
which case the message would be the price expressed in binary.  In the case
of amortized secure multiparty computations, the message is protocol
specific binary data that consists of a counter (or counters), concatenated
with shares of secret data that is used to construct the result of the
multiparty computation.  In the case of transaction reflection, the message
would be a duplicate copy of the tapscript signed transaction data (about
244 bytes of data plus a 64 byte prefix).

As you note, the message is likely to constructed from a value computed
from a mix of witness and committed data, though the message might be pure
witness data, as in the discreet log contract example.  In that the
discreet log contract example, you'd probably duplicate the integer value
and do further processing (e.g. compare it to some other committed value).

On Thu, May 23, 2019 at 1:36 PM Jimmy Song <jaejoon@gmail.com> wrote:

> Hi Russell,
>
> This is probably a dumb question, but I'd like to get some clarity on your
> proposal.
>
> OP_CHECKSIGFROMSTACKVERIFY would pop off a signature, message and pubkey.
> Presumably, the message would then have to get constructed as part of the
> Script execution. What would such a message look like? What, in other
> words, would you be signing and would that be similar to what signatures
> sign now? Would it be a single blob that incorporates all the input/output
> information in some hashed manner (like BIP143)? Or would you need separate
> signatures for different parts of the transaction? Or is it something more
> complicated like aggregating multiple signatures over different parts of
> the transaction?
>
> Best,
>
> Jimmy
>
> On Thu, May 23, 2019 at 8:35 AM Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Recently there have been some tapscript proposals, SIGHASH_ANYPREVOUT and
>> OP_CHECKOUTPUTHASHVERIFY, that aim to enable particular new features for
>> Bitcoin via new Script operations.  However, I think that these proposals
>> miss the mark when it comes to how they approach Bitcoin Script and
>> language features.
>>
>> Bitcoin Script appears designed to be a flexible programmable system that
>> provides generic features to be composed to achieve various purposes.
>> Thus, when we design new language features for Script, we should be
>> striving, as much as possible, to similarly build general purpose tools
>> which can in turn be used for a variety of purposes.
>>
>> I feel the SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY proposals fail
>> to achieve these design goals.  They are both are designed with very narrow
>> applications in mind, while also going out of their way to extend the
>> semantic domain of the interpretation of Bitcoin operations in new ways
>> that complicate their specification.  In the case of SIGHASH_ANYPREVOUT,
>> the semantic domain is extended by adding new counters to track the use of
>> various v0 and v2 signature types.  In the case of
>> OP_CHECKOUTPUTHASHVERIFY, it employs a new context-sensitive operation that
>> peeks at the value of surrounding opcodes.
>>
>> Instead, I propose that, for the time being, we simply implement OP_CAT
>> and OP_CHECKSIGFROMSTACKVERIFY.  OP_CAT pops two byte arrays off the stack
>> and pushes their concatenation back onto the stack.
>> OP_CHECKSIGFROMSTACKVERIFY pops a signature, message, and pubkey off the
>> stack and performs a bip-schnorr verification on the SHA256 hash of the
>> message.
>>
>> In concert, these two operations enable:
>>
>> * Oracle signature verification, including discrete log contracts.
>> * Amortized secure multiparty computations (see "Amortizing Secure
>> Computation with Penalties" by Kumaresan and Bentov).
>> * Transaction introspection including:
>> + Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply
>> by the nature of the construction.
>> + Decide if a transaction has exactly one input or not. (etc.)
>> + Weak covenants, which can verify output scripts to see if they are
>> among a set of predefined values or verify the output hash.
>>
>> and presumably more applications as well.
>>
>> For better or for worse, without an OP_PUBKEYTWEEK operation available,
>> the more interesting recursive-covenants remain largely out of reach, with
>> the exception of a recursive covenant that is only able to send back to its
>> own address, possibly abusing its own TXO value as a state variable.
>>
>> All this is accomplished by two straightforward opcodes whose semantics
>> are pure computational operations on stack values.  The only semantic
>> side-effect is that OP_CHECKSIGFROMSTACKVERIFY would count towards the
>> existing 'sigops_passed' count.  Moreover, I feel that adding these
>> operations does not preclude adding more specialized opcodes in the future
>> as an optimization for whatever popular constructions come up, once we know
>> what those are.
>>
>> I feel that this style of generic building blocks truly embodies what is
>> meant by "programmable money".
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

[-- Attachment #2: Type: text/html, Size: 7021 bytes --]

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[ZmnSCPxj]

Good morning Jimmy,

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Friday, May 24, 2019 1:36 AM, Jimmy Song via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Russell,
>
> This is probably a dumb question, but I'd like to get some clarity on your proposal.
>
> OP_CHECKSIGFROMSTACKVERIFY would pop off a signature, message and pubkey. Presumably, the message would then have to get constructed as part of the Script execution. What would such a message look like? What, in other words, would you be signing and would that be similar to what signatures sign now? Would it be a single blob that incorporates all the input/output information in some hashed manner (like BIP143)? Or would you need separate signatures for different parts of the transaction? Or is it something more complicated like aggregating multiple signatures over different parts of the transaction?

In order to use `OP_CHECKSIGFROMSTACK` work to allow transaction introspection, the message to be signed would be the equivalent of the sighash digest using `SIGHASH_ALL`.

As a general pattern, if you want a SCRIPT that imposes some rule on some field in the sighash digest of the transaction:

1.  You would require that the transaction be split into three parts, with those parts provided in the witness stack.
    One would be "data before the field", then "the field", then "data after the field".
2.  In addition, you would require a signature for the transaction in addition to the transaction parts above.
3.  You would ensure that "data before the field" is the correct size, so that you know "the field" is at the correct location in the transaction.
    Alternately you might need to also introspect some other fields in order to ensure other details like number of inputs, number of outputs, value of inputs etc. etc. are what you expect.
4.  You would check that the given signature is `SIGHASH_ALL` (most easily by checking its size --- proposed Schnorr signatures have a fixed size, and the lack of an extra sighash flags byte means `SIGHASH_ALL` by default, so if the signature is exactly the fixed Schnorr signature size, it is `SIGHASH_ALL`).
5.  You would use normal `OP_CHECKSIGVERIFY` to ensure that the signature signs the actual transaction.
6.  You would concatenate the supposed parts of the transaction together and use `OP_CHECKSIGFROMSTACKVERIFY` to ensure that the signature *also* is valid for that.
    Since you know the signature is valid for the transaction itself, if it *also* is valid for this, then the concatenation of the input "data before the field", "the field", and "data after the field" is exactly the same sighash digest as the actual transaction, and thus is accurate to the transaction.
7.  Finally, you would actually validate the field you want to impose some rule on.

`SIGHASH_ALL` is suggested since it allows you to introspect all fields, but also because ensuring that the signature is indeed a `SIGHASH_ALL` signature is easier (just do the size check).
Alternately you can use some other flag, but you would require the signature on the stack to be flagless and concat the flag yourself before using `OP_CHECKSIGVERIFY`.

This mechanism is very general and allows SCRIPT to introspect *any* field of the transactions.
Indeed, one can argue that `OP_CHECKLOCKTIMEVERIFY` and `OP_CHECKSEQUENCEVERIFY` are both superfluous in a system with `OP_CAT` and `OP_CHECKSIGFROMSTACK`.
OF course, these operations are significantly more optimized since they do not require that you quine the transaction.

Regards,
ZmnSCPxj


>
> Best,
>
> Jimmy
>
> On Thu, May 23, 2019 at 8:35 AM Russell O'Connor via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> > Recently there have been some tapscript proposals, SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY, that aim to enable particular new features for Bitcoin via new Script operations.  However, I think that these proposals miss the mark when it comes to how they approach Bitcoin Script and language features.
> >
> > Bitcoin Script appears designed to be a flexible programmable system that provides generic features to be composed to achieve various purposes.  Thus, when we design new language features for Script, we should be striving, as much as possible, to similarly build general purpose tools which can in turn be used for a variety of purposes.
> >
> > I feel the SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY proposals fail to achieve these design goals.  They are both are designed with very narrow applications in mind, while also going out of their way to extend the semantic domain of the interpretation of Bitcoin operations in new ways that complicate their specification.  In the case of SIGHASH_ANYPREVOUT, the semantic domain is extended by adding new counters to track the use of various v0 and v2 signature types.  In the case of OP_CHECKOUTPUTHASHVERIFY, it employs a new context-sensitive operation that peeks at the value of surrounding opcodes.
> >
> > Instead, I propose that, for the time being, we simply implement OP_CAT and OP_CHECKSIGFROMSTACKVERIFY.  OP_CAT pops two byte arrays off the stack and pushes their concatenation back onto the stack.  OP_CHECKSIGFROMSTACKVERIFY pops a signature, message, and pubkey off the stack and performs a bip-schnorr verification on the SHA256 hash of the message.
> >
> > In concert, these two operations enable:
> >
> > * Oracle signature verification, including discrete log contracts.
> > * Amortized secure multiparty computations (see "Amortizing Secure Computation with Penalties" by Kumaresan and Bentov).
> > * Transaction introspection including:
> > + Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply by the nature of the construction.
> > + Decide if a transaction has exactly one input or not. (etc.)
> > + Weak covenants, which can verify output scripts to see if they are among a set of predefined values or verify the output hash.
> >
> > and presumably more applications as well.
> >
> > For better or for worse, without an OP_PUBKEYTWEEK operation available, the more interesting recursive-covenants remain largely out of reach, with the exception of a recursive covenant that is only able to send back to its own address, possibly abusing its own TXO value as a state variable.
> >
> > All this is accomplished by two straightforward opcodes whose semantics are pure computational operations on stack values.  The only semantic side-effect is that OP_CHECKSIGFROMSTACKVERIFY would count towards the existing 'sigops_passed' count.  Moreover, I feel that adding these operations does not preclude adding more specialized opcodes in the future as an optimization for whatever popular constructions come up, once we know what those are.
> >
> > I feel that this style of generic building blocks truly embodies what is meant by "programmable money".
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[ZmnSCPxj]

> For better or for worse, without an OP_PUBKEYTWEEK operation available, the more interesting recursive-covenants remain largely out of reach, with the exception of a recursive covenant that is only able to send back to its own address, possibly abusing its own TXO value as a state variable.

After some thinking, I may have devised a way to achieve the more interesting Turing-complete system (where each "loop through" requires paying a fee to miners, akin to Ethereum Gas, and thus a good way to build new footguns) even without `OP_PUBKEYTWEAK`.

I observe the following:

1.  `OP_CHECKSIGFROMSTACK` can introspect into the transaction *doing the spend* by giving the transaction (minus witness) as part of the witness (i.e. quining).
2.  The above can be leveraged to introspect into the transaction *being spent* by giving that transaction *being spent* (minus witness) as part of the witness stack.
    This is because the transaction *doing the spend* commits to the transaction *being spent* by referring to its txid.
    We can concatenate the bits of the previous transaction and confirm that it is indeed the transaction *being spent* by hashing and comparing that to the txid in the input of the transaction *doing the spend*.
3.  The transaction *being spent* can contain an `OP_RETURN` output that contains the previous state (or a commitment to the previous state if it is too large to fit in an `OP_RETURN`, again requiring that the previous state be given as part of the witness).
    Since it can be introspected, a script can acquire a "previous state" data.
4.  The transaction *doing the spend* can also contain an `OP_RETURN` with the next state (or commitment to next state).
5.  The rest of the script can then determine if the transition from "previous state" to "next state" is valid.
6.  The script can impose that the same script is paid to by introspecting the transaction *being spent* to get at a commitment to itself.

The above seems enough to create a potentially unbound loop, bound only by the amount of money you are willing to spend on fees operating that loop.
The "state" would be the memory of your virtual machine, and the SCRIPT validates the execution of one iteration of the interpreter loop, and that would be enough to create a Turing-complete system within Bitcoin.
With MAST, you can compress branches not taken, reducing the number of operations you have to expose at each iteration.

I admit *creating* this by hand will probably be very difficult, but that should be doable with an army of lower-level cognition agents.
(disclaimer: I am not an AI with an army of lower-level cognition agents and I can completely and totally pass the Turing test)


Regards,
ZmnSCPxj

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 411 bytes --]

On Wed, May 22, 2019 at 5:01 PM Russell O'Connor <roconnor@blockstream.io>
wrote:

> In concert, these two operations enable:
>
> * Oracle signature verification, including discrete log contracts.
>

Jonas informs me that I've misunderstood how discreet log contracts work.
The DLC signatures are not directly checked by Script and do not rely on
CHECKSIGFROMSTACK.  I apologize for my hasty literature review.

[-- Attachment #2: Type: text/html, Size: 850 bytes --]

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 1847 bytes --]

Hi Russell,

Thanks for this detailed comparison. The COSHV BIP does include a brief
comparison to OP_CHECKSIGFROMSTACKVERIFY and ANYPREVOUT, but this is more
detailed.


I think that the power from CHECKSIGFROMSTACKVERIFY is awesome. It's
clearly one of the more flexible options available and would enable a
multitude of new use cases.

When I originally presented my work on congestion control at Jan 2017
BPASE, I also discussed it as an option for covenants. Unfortunately I
think it may be on the edge of too powerful -- there are a lot of use cases
and implications from having a potentially recursive covenant. If you see
my response to Matt in the OP_COSHV BIP thread I classify it as enabling a
non-computationally enumerable set of restrictions.

I think also from a developer point of view working with OP_COSHV is much
much simpler (maybe this can be abstracted) which will lead to increased
adoption. OP_COSHV also uses less per-block bandwidth which also makes it
preferable for a measure intended to decongest blocks. Do you know the
exact byte cost for OP_CHECKSIGFROMSTACK? OP_COSHV scripts, with templating
changes to taproot, can be a single byte. OP_COSHV also has less potential
to have a negative interaction with future opcodes we may want like
OP_PUBKEYTWEAK. While we're getting to an exact spec for the features we
want in Bitcoin scripting, it's hard to sign on to OP_CHECKSIGFROMSTACK
unless there's an exact specification which makes us confident we're
hitting all the points.

If the main complaint about OP_COSHV is that it peeks at surrounding data,
it's also possible to implement it more closely to a multi-byte pushdata
opcode or do the template optimization.

Lastly, as I have previously noted, OP_LEFT is probably safer to implement
than OP_CAT and should be more efficient for OP_CHECKSIGFROMSTACK scripts.

[-- Attachment #2: Type: text/html, Size: 3507 bytes --]

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 3843 bytes --]

In order of escalating scope of amendments to OP_COSHV, I suggest

1) Peeking at surrounding data surrounding data should definitely be
replaced by a pushdata-like op-code that uses the subsequent 32-bytes
directly.  The OP_SUCCESSx upgrade path specifically allows for this, and
avoids complicating the semantics Bitcoin Script.
2) Furthermore, the number-of-input-verification and the
outputhash-verification operations ought to be split into different opcodes
as they are logically unrelated.
3) Better still, we should instead implement the transaction reflection
operations of OP_PUSHOUTPUTHASH and OP_NUMINPUTS that puts the outputhash
and number of inputs respectively onto the stack.  Recursive covenants
appear to be effectively impossible without either an OP_TWEEKPUBKEY or an
OP_PUSHSCRIPTPUBKEY so the effort your proposal goes through to guard
against placing an arbitrary outputhash onto the stack appears to be wasted
effort to me.
4) If we anticipate adding OP_CHECKSIGFROMSTACKVERIFY, then we should most
definitely prefer (3) instead of OP_COSHV, if we still feel the need to do
anything at all.  It is probably best to have both
OP_CHECKSIGFROMSTACKVERIFY and transaction reflection operations of
OP_PUSHOUTPUTHASH and OP_NUMINPUTS but I think I would be fine with just
OP_CHECKSIGFROMSTACKVERIFY as well.

On the other hand, if we are serious about preferring less per-block
bandwidth over reusable primitive opcodes for programming, then we should
instead abandon the RISC-style Bitcoin Script and instead add an
alternative CISC-style taproot leaf type that directly provides (a
conjunction of) the various popular common policies: channel opening,
channel factories, coinjoins, hashlocks, timelocks, congestion control
etc.  Segwit v0 already implements this CISC-style for the single most
popular policy: single signature verification.

On Fri, May 24, 2019 at 4:51 PM Jeremy <jlrubin@mit.edu> wrote:

> Hi Russell,
>
> Thanks for this detailed comparison. The COSHV BIP does include a brief
> comparison to OP_CHECKSIGFROMSTACKVERIFY and ANYPREVOUT, but this is more
> detailed.
>
>
> I think that the power from CHECKSIGFROMSTACKVERIFY is awesome. It's
> clearly one of the more flexible options available and would enable a
> multitude of new use cases.
>
> When I originally presented my work on congestion control at Jan 2017
> BPASE, I also discussed it as an option for covenants. Unfortunately I
> think it may be on the edge of too powerful -- there are a lot of use cases
> and implications from having a potentially recursive covenant. If you see
> my response to Matt in the OP_COSHV BIP thread I classify it as enabling a
> non-computationally enumerable set of restrictions.
>
> I think also from a developer point of view working with OP_COSHV is much
> much simpler (maybe this can be abstracted) which will lead to increased
> adoption. OP_COSHV also uses less per-block bandwidth which also makes it
> preferable for a measure intended to decongest blocks. Do you know the
> exact byte cost for OP_CHECKSIGFROMSTACK? OP_COSHV scripts, with templating
> changes to taproot, can be a single byte. OP_COSHV also has less potential
> to have a negative interaction with future opcodes we may want like
> OP_PUBKEYTWEAK. While we're getting to an exact spec for the features we
> want in Bitcoin scripting, it's hard to sign on to OP_CHECKSIGFROMSTACK
> unless there's an exact specification which makes us confident we're
> hitting all the points.
>
> If the main complaint about OP_COSHV is that it peeks at surrounding data,
> it's also possible to implement it more closely to a multi-byte pushdata
> opcode or do the template optimization.
>
> Lastly, as I have previously noted, OP_LEFT is probably safer to implement
> than OP_CAT and should be more efficient for OP_CHECKSIGFROMSTACK scripts.
>
>

[-- Attachment #2: Type: text/html, Size: 5545 bytes --]

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 4939 bytes --]

What do you think about having it be OP_CHECK_TXID_TEMPLATE_DATA where the
hash checked is the TXID of the transaction with the inputs set to 0000...
(maybe appended to the fee paid)?

This allows for a variable number of inputs to be allowed (e.g., one, two,
etc). This also fixes potential bugs around TXID malleability for lightning
like setups (Greg and I discussed in wizards about version malleability).

Allowing multiple inputs is great for structuring more complex contracts
with multiple nodes paying into the same covenantted transaction.

Also I personally prefer a RISC+CISC approach -- we should enable the
common paths easily as they are known (didn't you come up with jets?) and
improve security for API users, but also piecemeal enable features in
script to allow for experimentation or custom contracts.
--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>


On Fri, May 24, 2019 at 4:15 PM Russell O'Connor <roconnor@blockstream.io>
wrote:

> In order of escalating scope of amendments to OP_COSHV, I suggest
>
> 1) Peeking at surrounding data surrounding data should definitely be
> replaced by a pushdata-like op-code that uses the subsequent 32-bytes
> directly.  The OP_SUCCESSx upgrade path specifically allows for this, and
> avoids complicating the semantics Bitcoin Script.
> 2) Furthermore, the number-of-input-verification and the
> outputhash-verification operations ought to be split into different opcodes
> as they are logically unrelated.
> 3) Better still, we should instead implement the transaction reflection
> operations of OP_PUSHOUTPUTHASH and OP_NUMINPUTS that puts the outputhash
> and number of inputs respectively onto the stack.  Recursive covenants
> appear to be effectively impossible without either an OP_TWEEKPUBKEY or an
> OP_PUSHSCRIPTPUBKEY so the effort your proposal goes through to guard
> against placing an arbitrary outputhash onto the stack appears to be wasted
> effort to me.
> 4) If we anticipate adding OP_CHECKSIGFROMSTACKVERIFY, then we should most
> definitely prefer (3) instead of OP_COSHV, if we still feel the need to do
> anything at all.  It is probably best to have both
> OP_CHECKSIGFROMSTACKVERIFY and transaction reflection operations of
> OP_PUSHOUTPUTHASH and OP_NUMINPUTS but I think I would be fine with just
> OP_CHECKSIGFROMSTACKVERIFY as well.
>
> On the other hand, if we are serious about preferring less per-block
> bandwidth over reusable primitive opcodes for programming, then we should
> instead abandon the RISC-style Bitcoin Script and instead add an
> alternative CISC-style taproot leaf type that directly provides (a
> conjunction of) the various popular common policies: channel opening,
> channel factories, coinjoins, hashlocks, timelocks, congestion control
> etc.  Segwit v0 already implements this CISC-style for the single most
> popular policy: single signature verification.
>
> On Fri, May 24, 2019 at 4:51 PM Jeremy <jlrubin@mit.edu> wrote:
>
>> Hi Russell,
>>
>> Thanks for this detailed comparison. The COSHV BIP does include a brief
>> comparison to OP_CHECKSIGFROMSTACKVERIFY and ANYPREVOUT, but this is more
>> detailed.
>>
>>
>> I think that the power from CHECKSIGFROMSTACKVERIFY is awesome. It's
>> clearly one of the more flexible options available and would enable a
>> multitude of new use cases.
>>
>> When I originally presented my work on congestion control at Jan 2017
>> BPASE, I also discussed it as an option for covenants. Unfortunately I
>> think it may be on the edge of too powerful -- there are a lot of use cases
>> and implications from having a potentially recursive covenant. If you see
>> my response to Matt in the OP_COSHV BIP thread I classify it as enabling a
>> non-computationally enumerable set of restrictions.
>>
>> I think also from a developer point of view working with OP_COSHV is much
>> much simpler (maybe this can be abstracted) which will lead to increased
>> adoption. OP_COSHV also uses less per-block bandwidth which also makes it
>> preferable for a measure intended to decongest blocks. Do you know the
>> exact byte cost for OP_CHECKSIGFROMSTACK? OP_COSHV scripts, with templating
>> changes to taproot, can be a single byte. OP_COSHV also has less potential
>> to have a negative interaction with future opcodes we may want like
>> OP_PUBKEYTWEAK. While we're getting to an exact spec for the features we
>> want in Bitcoin scripting, it's hard to sign on to OP_CHECKSIGFROMSTACK
>> unless there's an exact specification which makes us confident we're
>> hitting all the points.
>>
>> If the main complaint about OP_COSHV is that it peeks at surrounding
>> data, it's also possible to implement it more closely to a multi-byte
>> pushdata opcode or do the template optimization.
>>
>> Lastly, as I have previously noted, OP_LEFT is probably safer to
>> implement than OP_CAT and should be more efficient for OP_CHECKSIGFROMSTACK
>> scripts.
>>
>>

[-- Attachment #2: Type: text/html, Size: 7782 bytes --]

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 5627 bytes --]

Allowing multiple inputs is certainly better than the 1 restriction COSHV.

However, I agree on your preference for a RISC+CISC approach.  Which is why
instead of COSHV or CHECK_TXID_TEMPLACE_DATA we should do the more RISC-y
thing and begin adding transaction reflection primitives, starting with
OP_NUMINPUTS and OP_PUSHOUTPUTSHASH.  Nothing bad will happen by pushing
the OUTPUTSHASH onto the stack, and we won't even get recursive covenants
with just these transaction reflection primitives in tapscript.

On Fri, May 24, 2019 at 9:08 PM Jeremy <jlrubin@mit.edu> wrote:

> What do you think about having it be OP_CHECK_TXID_TEMPLATE_DATA where the
> hash checked is the TXID of the transaction with the inputs set to 0000...
> (maybe appended to the fee paid)?
>
> This allows for a variable number of inputs to be allowed (e.g., one, two,
> etc). This also fixes potential bugs around TXID malleability for lightning
> like setups (Greg and I discussed in wizards about version malleability).
>
> Allowing multiple inputs is great for structuring more complex contracts
> with multiple nodes paying into the same covenantted transaction.
>
> Also I personally prefer a RISC+CISC approach -- we should enable the
> common paths easily as they are known (didn't you come up with jets?) and
> improve security for API users, but also piecemeal enable features in
> script to allow for experimentation or custom contracts.
> --
> @JeremyRubin <https://twitter.com/JeremyRubin>
> <https://twitter.com/JeremyRubin>
>
>
> On Fri, May 24, 2019 at 4:15 PM Russell O'Connor <roconnor@blockstream.io>
> wrote:
>
>> In order of escalating scope of amendments to OP_COSHV, I suggest
>>
>> 1) Peeking at surrounding data surrounding data should definitely be
>> replaced by a pushdata-like op-code that uses the subsequent 32-bytes
>> directly.  The OP_SUCCESSx upgrade path specifically allows for this, and
>> avoids complicating the semantics Bitcoin Script.
>> 2) Furthermore, the number-of-input-verification and the
>> outputhash-verification operations ought to be split into different opcodes
>> as they are logically unrelated.
>> 3) Better still, we should instead implement the transaction reflection
>> operations of OP_PUSHOUTPUTHASH and OP_NUMINPUTS that puts the outputhash
>> and number of inputs respectively onto the stack.  Recursive covenants
>> appear to be effectively impossible without either an OP_TWEEKPUBKEY or an
>> OP_PUSHSCRIPTPUBKEY so the effort your proposal goes through to guard
>> against placing an arbitrary outputhash onto the stack appears to be wasted
>> effort to me.
>> 4) If we anticipate adding OP_CHECKSIGFROMSTACKVERIFY, then we should
>> most definitely prefer (3) instead of OP_COSHV, if we still feel the need
>> to do anything at all.  It is probably best to have both
>> OP_CHECKSIGFROMSTACKVERIFY and transaction reflection operations of
>> OP_PUSHOUTPUTHASH and OP_NUMINPUTS but I think I would be fine with just
>> OP_CHECKSIGFROMSTACKVERIFY as well.
>>
>> On the other hand, if we are serious about preferring less per-block
>> bandwidth over reusable primitive opcodes for programming, then we should
>> instead abandon the RISC-style Bitcoin Script and instead add an
>> alternative CISC-style taproot leaf type that directly provides (a
>> conjunction of) the various popular common policies: channel opening,
>> channel factories, coinjoins, hashlocks, timelocks, congestion control
>> etc.  Segwit v0 already implements this CISC-style for the single most
>> popular policy: single signature verification.
>>
>> On Fri, May 24, 2019 at 4:51 PM Jeremy <jlrubin@mit.edu> wrote:
>>
>>> Hi Russell,
>>>
>>> Thanks for this detailed comparison. The COSHV BIP does include a brief
>>> comparison to OP_CHECKSIGFROMSTACKVERIFY and ANYPREVOUT, but this is more
>>> detailed.
>>>
>>>
>>> I think that the power from CHECKSIGFROMSTACKVERIFY is awesome. It's
>>> clearly one of the more flexible options available and would enable a
>>> multitude of new use cases.
>>>
>>> When I originally presented my work on congestion control at Jan 2017
>>> BPASE, I also discussed it as an option for covenants. Unfortunately I
>>> think it may be on the edge of too powerful -- there are a lot of use cases
>>> and implications from having a potentially recursive covenant. If you see
>>> my response to Matt in the OP_COSHV BIP thread I classify it as enabling a
>>> non-computationally enumerable set of restrictions.
>>>
>>> I think also from a developer point of view working with OP_COSHV is
>>> much much simpler (maybe this can be abstracted) which will lead to
>>> increased adoption. OP_COSHV also uses less per-block bandwidth which also
>>> makes it preferable for a measure intended to decongest blocks. Do you know
>>> the exact byte cost for OP_CHECKSIGFROMSTACK? OP_COSHV scripts, with
>>> templating changes to taproot, can be a single byte. OP_COSHV also has less
>>> potential to have a negative interaction with future opcodes we may want
>>> like OP_PUBKEYTWEAK. While we're getting to an exact spec for the features
>>> we want in Bitcoin scripting, it's hard to sign on to OP_CHECKSIGFROMSTACK
>>> unless there's an exact specification which makes us confident we're
>>> hitting all the points.
>>>
>>> If the main complaint about OP_COSHV is that it peeks at surrounding
>>> data, it's also possible to implement it more closely to a multi-byte
>>> pushdata opcode or do the template optimization.
>>>
>>> Lastly, as I have previously noted, OP_LEFT is probably safer to
>>> implement than OP_CAT and should be more efficient for OP_CHECKSIGFROMSTACK
>>> scripts.
>>>
>>>

[-- Attachment #2: Type: text/html, Size: 8591 bytes --]

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Anthony Towns]

On Wed, May 22, 2019 at 05:01:21PM -0400, Russell O'Connor via bitcoin-dev wrote:
> Bitcoin Script appears designed to be a flexible programmable system that
> provides generic features to be composed to achieve various purposes.

Counterpoint: haven't the flexibly designed parts of script mostly been
a failure -- requiring opcodes to be disabled due to DoS vectors or
consensus bugs, and mostly not being useful in practice where they're
still enabled in BTC or on other chains where they have been re-enabled
(eg, Liquid and BCH)?

> Instead, I propose that, for the time being, we simply implement OP_CAT and
> OP_CHECKSIGFROMSTACKVERIFY.

FWIW, I'd like to see CAT enabled, though I'm less convinced about a
CHECKSIG that takes the message from the stack. I think CAT's plausibly
useful in practice, but a sig against data from the stack seems more
useful in theory than in practice. Has it actually seen use on BCH or
Liquid, eg?  (Also, I think BCH's name for that opcode makes more sense
than Elements' -- all the CHECKSIG opcodes pull a sig from the stack,
after all)

> * Transaction introspection including:
> + Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply by the
> nature of the construction.

I think simulating an ANYPREVOUT sig with a data signature means checking:

    S1 P CHECKSIG -- to check S1 is a signature for the tx

    S1 H_TapSighash(XAB) P CHECKDATASIG
         -- to pull out the tx data "X", "A", "B")

    S2 H_TapSighash(XCB) Q CHECKDATASIG
         -- for the ANYPREVOUT sig, with A changed to C to
	    avoid committing to prevout info

    X SIZE 42 EQUALVERIFY
    B SIZE 47 EQUALVERIFY
         -- to make sure only C is replaced from "XCB"

So to get all those conditions checked, I think you could do:

   P 2DUP TOALT TOALT CHECKSIGVERIFY
   SIZE 42 EQUALVERIFY
   "TapSighash" SHA256 DUP CAT SWAP CAT TOALT
   SIZE 47 EQUALVERIFY TUCK
   CAT FROMALT TUCK SWAP CAT SHA256 FROMALT SWAP FROMALT
   CHECKDATASIGVERIFY
   SWAP TOALT SWAP CAT FROMALT CAT SHA256 Q CHECKDATASIG
   
Where the stack elements are, from top to bottom:

   S1: (65B) signature by P of tx
   X:  (42B) start of TapSighash spec
   B:  (47B) end of TapSighash spec (amount, nSequence, tapleaf_hash,
             key_version, codesep_pos)
   A:  (73B) middle of TapSighash spec dropped for ANYPREVOUT (spend_type,
             scriptPubKey and outpoint)
   C:   (1B) alternate middle (different spend_type)
   S2: (64B) signature of "XCB" by key Q

So 298B for the witness data, and 119B or so for the script (if I've not
made mistakes), versus "P CHECKSIGVERIFY Q CHECKSIG" and S2 and S1 on
the stack, for 132B of witness data and 70B of script, or half that if
the chaperone requirement is removed.

I think you'd need to complicate it a bit further to do the
ANYPREVOUTANYSCRIPT variant, where you retain the commitment to
amount/nseq but drop the commitment to tapleaf_hash.

> I feel that this style of generic building blocks truly embodies what is meant
> by "programmable money".

For practical purposes, this doesn't seem like a great level of
abstraction to me. It's certainly better at "permissionless innovation"
though.

You could make these constructions a little bit simpler by having a
"CHECK_SIG_MSG_VERIFY" opcode that accepts [sig msg key], and does "sig
key CHECKSIGVERIFY" but also checks the the provided msg was what was
passed into bip-schnorr.

Cheers,
aj

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[ZmnSCPxj]

Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Monday, May 27, 2019 3:21 PM, Anthony Towns via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Wed, May 22, 2019 at 05:01:21PM -0400, Russell O'Connor via bitcoin-dev wrote:
>
> > Bitcoin Script appears designed to be a flexible programmable system that
> > provides generic features to be composed to achieve various purposes.
>
> Counterpoint: haven't the flexibly designed parts of script mostly been
> a failure -- requiring opcodes to be disabled due to DoS vectors or
> consensus bugs, and mostly not being useful in practice where they're
> still enabled in BTC or on other chains where they have been re-enabled
> (eg, Liquid and BCH)?

One could argue that manually programming directly with `OP_CHECKSIGFROMSTACK` is difficult enough that we should really be using some compiler that (say) translates Simplicity to SCRIPT that uses `OP_CHECKSIGFROMSTACK` to implement transaction introspection.
So the lack of such use may point more to a lack of tools than a lack of actual use.

This extends in particular to "lack of abstraction"; the abstraction might be better served by implementing a pure functional language that is compiled down to `OP_CHECKSIGFROMSTACK` somehow, with the pure functional language implementing loops using the technique I described (keep current state in a separate `OP_RETURN` output, reuse the same `scriptPubKey` but modify the `OP_RETURN` output (i.e. code is `const`, data is `mutable`)).

But that still requires that we have at least a proof-of-existence in the form of some compiler that targets (say) Liquid/Elements SCRIPT and leverages `OP_CHECKSIGFROMSTACK` appropriately.

I believe Russell has expressed some interest in my Smart Contracts Unchained technique to implement Simplicity on top of Bitcoin by using a semi-trusted user-selected federation to enforce Simplicity execution.
If implemented as such, it may be possible to then show that actual use would be enabled if it is possible to run this on Bitcoin.
(I respect that Blockstream employees have to eat and thus made Liquid, but for example I myself would not be interested in putting any coins in Liquid, as its federation is not selected by me; I would be more willing to use a Simplicity or `OP_CHECKSIGFROMSTACK` implementation on top of Smart Contracts Unchained as at least I can select the federation to include my own hardware, and allow anyone I might want to form such contracts with to also select federation members to include my own hardware.)
(Of course Liquid is built on Elements and Elements is open-source and in theory I could just replace its federation with my own, but having to start a new blockchain for every federation-set seems wasteful compared to Smart Contracts Unchained; Elements does have the advantage of already actually existing whereas no Smart Contracts Unchained exists at all.)

Regards,
ZmnSCPxj

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 6848 bytes --]

On Mon, May 27, 2019 at 3:21 AM Anthony Towns <aj@erisian.com.au> wrote:

> On Wed, May 22, 2019 at 05:01:21PM -0400, Russell O'Connor via bitcoin-dev
> wrote:
> > Bitcoin Script appears designed to be a flexible programmable system that
> > provides generic features to be composed to achieve various purposes.
>
> Counterpoint: haven't the flexibly designed parts of script mostly been
> a failure -- requiring opcodes to be disabled due to DoS vectors or
> consensus bugs, and mostly not being useful in practice where they're
> still enabled in BTC or on other chains where they have been re-enabled
> (eg, Liquid and BCH)?
>

You may have a point.  However, I'm still inclined to think that problem is
that you want some subset of concatenation, arithmetic, CHECKDATASIG,
transaction reflection and/or covenants in order to create particularly
useful programs.

A while ago, I was designing a moderately sophisticated Script for Elements
Alpha to see if I could implement a toy game, but ultimately I was thwarted
due to the fact that Elements Alpha didn't support multiplication.
I did briefly consider using repeated additions and nested if statements to
implement multiplication since I was expecting my numbers to be 11 or less,
but ultimately I decided to just continue my work on an alternative to
Script rather than trying to work around the missing multiplication.


> > Instead, I propose that, for the time being, we simply implement OP_CAT
> and
> > OP_CHECKSIGFROMSTACKVERIFY.
>
> FWIW, I'd like to see CAT enabled, though I'm less convinced about a
> CHECKSIG that takes the message from the stack. I think CAT's plausibly
> useful in practice, but a sig against data from the stack seems more
> useful in theory than in practice. Has it actually seen use on BCH or
> Liquid, eg?  (Also, I think BCH's name for that opcode makes more sense
> than Elements' -- all the CHECKSIG opcodes pull a sig from the stack,
> after all)
>
> > * Transaction introspection including:
> > + Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply
> by the
> > nature of the construction.
>
> I think simulating an ANYPREVOUT sig with a data signature means checking:
>
>     S1 P CHECKSIG -- to check S1 is a signature for the tx
>
>     S1 H_TapSighash(XAB) P CHECKDATASIG
>          -- to pull out the tx data "X", "A", "B")
>
>     S2 H_TapSighash(XCB) Q CHECKDATASIG
>          -- for the ANYPREVOUT sig, with A changed to C to
>             avoid committing to prevout info
>
>     X SIZE 42 EQUALVERIFY
>     B SIZE 47 EQUALVERIFY
>          -- to make sure only C is replaced from "XCB"
>
> So to get all those conditions checked, I think you could do:
>
>    P 2DUP TOALT TOALT CHECKSIGVERIFY
>    SIZE 42 EQUALVERIFY
>    "TapSighash" SHA256 DUP CAT SWAP CAT TOALT
>    SIZE 47 EQUALVERIFY TUCK
>    CAT FROMALT TUCK SWAP CAT SHA256 FROMALT SWAP FROMALT
>    CHECKDATASIGVERIFY
>    SWAP TOALT SWAP CAT FROMALT CAT SHA256 Q CHECKDATASIG
>
> Where the stack elements are, from top to bottom:
>
>    S1: (65B) signature by P of tx
>    X:  (42B) start of TapSighash spec
>    B:  (47B) end of TapSighash spec (amount, nSequence, tapleaf_hash,
>              key_version, codesep_pos)
>    A:  (73B) middle of TapSighash spec dropped for ANYPREVOUT (spend_type,
>              scriptPubKey and outpoint)
>    C:   (1B) alternate middle (different spend_type)
>    S2: (64B) signature of "XCB" by key Q
>
> So 298B for the witness data, and 119B or so for the script (if I've not
> made mistakes), versus "P CHECKSIGVERIFY Q CHECKSIG" and S2 and S1 on
> the stack, for 132B of witness data and 70B of script, or half that if
> the chaperone requirement is removed.
>

I haven't checked your details but the above looks about correct to me.

So what I was thinking is that we could add CHECKDATASIG first, and then
people could get started on actually using ANYPREVOUT in practice and we
can take our time to debate the merits of the chaperone vs non-chaperone,
and possibly learn something about actual use before making a decision.
There is no doubt that using ANYPREVOUT directly uses less weight, but they
seem close enough to that it the simulation is usable, though perhaps far
enough apart that we would want to eventually add ANYPREVOUT.  However, do
keep in mind that our goal is not to minimize the weight of specific
redemption policies.  The weight of implementing any particular redemption
policy in Script is somewhat arbitrary to begin with anyways, being
dependent on the choices made for the Script language operations and its
encoding.  Again, if our goal were to minimize weight for specific
redemption policies we should abandon SCRIPT and directly use a language
similar to Miniscript, and/or just directly implement an enumeration of
policies.

However, my proposal CHECKSIGFROMSTACK (aka CHECKDATASIG) proposal was
based on my argument that CHECKDATASIG covenant abilities wouldn't be
controversial since it was limited to self-recursion and had less than
64-bits of state space.  But ZmnSCPxj has shown that my conclusions were
hasty and that self-recursion has access to arbitrarily large amounts of
state space.  In light of this, it would appear that self-recursive
covenants is nearly as powerful as arbitrary recursive covenants, and
therefore is nearly as controversial.

So, while I do think that we should add support for recursive covenants to
Bitcoin, we probably not ready to add it yet given the controversy around
the far more innocent ANYPREVOUT.  I do think it would be useful to add
support for CAT and CHECKDATASIG in order to implement MPC with penalties,
but perhaps we should support that via a HASH_tapdata digest function
rather than SHA256, in order to avoid any accidental covenants.  Of course
doing so would no longer count as "an alternative" proposal to ANYPREVOUT
or COSHV, and simply "an additional" proposal.


> I think you'd need to complicate it a bit further to do the
> ANYPREVOUTANYSCRIPT variant, where you retain the commitment to
> amount/nseq but drop the commitment to tapleaf_hash.
>
> > I feel that this style of generic building blocks truly embodies what is
> meant
> > by "programmable money".
>
> For practical purposes, this doesn't seem like a great level of
> abstraction to me. It's certainly better at "permissionless innovation"
> though.
>
> You could make these constructions a little bit simpler by having a
> "CHECK_SIG_MSG_VERIFY" opcode that accepts [sig msg key], and does "sig
> key CHECKSIGVERIFY" but also checks the the provided msg was what was
> passed into bip-schnorr.
>

The whole point is to keep the functionality simple and let users program
what they want.  What we don't want to do is tailor an opcode for the
specific use case we have in mind, because that just comes at the expense
of all the use cases we don't have in mind.

[-- Attachment #2: Type: text/html, Size: 8166 bytes --]

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

[Tamas Blummer]

[-- Attachment #1.1: Type: text/plain, Size: 7345 bytes --]

ZmnSCPxj already observed in [1] that these ops would enable introspection of any field of the transactions and make both `OP_CHECKLOCKTIMEVERIFY` and `OP_CHECKSEQUENCEVERIFY` superfluous.
There is much more to this as enumerated in generic terms by Russel O’Connor below and I would like to add a concrete example.

We could implement oracle less difficulty contracts without the need the of a CISC type OP_WORKVERIFY but instead through resurrection/extension of OP_CAT, OP_GREATERTHANOREQUAL and introduction of a new RISC opcode OP_CHECKBLOCKATHEIGHT[3] suggested by Luke Dashjr. Thanks for the pointer to Nathan Cook [4]

Technically we could resurrect and add them without burning more than one OP_NOP by redefining it as a prefix (OP_EXTENSION), such as:

OP_EXTENSION OP_CAT would become a two byte opcode pointing to a resurrected implementation of OP_CAT.

This could be soft forked in.

A concrete oracle less difficulty contract could look like:
It is an european digital call option on target difficulty after maturity and 10 blocks notice period. I gave you reasons while having these would increase bitcoin's security in [2]

IF
	<maturity as block height + 10> CHECKLOCKTIMEVERIFY DROP
      <speculator’s key> CHECKSIGVERIFY
ELSE
	OP_DUP  <maturity as block height - 1> OP_CHECKBLOCKATHEIGHT OP_LESSTHANEQUAL OP_VERIFY
	OP_SWAP OP_CAT  OP_CAT  OP_HASH256 <contracted target> OP_LESSTHANEQUAL OP_VERIFY
	<miner’s key> CHECKSIGVERIFY
ENDIF

insurance premium could be collected by the seller of the insurance after maturity + 10 blocks if target difficulty was not reached

<speculator’s signature>

miner would get back its insurance premium plus collateral of the seller if target difficulty was not reached at maturity. Miner has 10 blocks time after maturity to claim with:

<maturity block header after prevhash> <maturity block version> <prevhash>

The stack would be in second case processed as:

1: after pushes
<maturity block prevhash>
<maturity block version>
<maturity block block header after prevhash>

2: after OP_DUP:
<maturity block prevhash>
<maturity block prevhash>
<maturity block version>
<maturity block block header after prevhash>

3: after push
<maturity as block height - 1>
<maturity block prevhash>
<maturity block prevhash>
<maturity block version>
<maturity block block header after prevhash>

4: after OP_CHECKBLOCKATHEIGHT OP_VERIFY is successful proving that prevhash is the block at maturity block height - 1
<maturity block prevhash>
<maturity block version>
<maturity block block header after prevhash>

5: after OP_SWAP
<block version>
<maturity block prevhash>
<block header after prevhash>

6: after OP_CAT
<maturity block version concatenated with maturity prevhash>
<maturity block block header after maturity prevhash>

7: after OP_CAT
<complete block header>

8: after OP_HASH256
<block hash computed for header>

9: after push
<contracted target>
<block hash computed for header>

10: after OP_GREATERTHANOREQUAL OP_VERIFY proves that contracted target was reached

Tamas Blummer


[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016966.html <https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016966.html>
[2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/017019.html <https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/017019.html>
[3] https://github.com/luke-jr/bips/blob/bip-cbah/bip-cbah.mediawiki <https://github.com/luke-jr/bips/blob/bip-cbah/bip-cbah.mediawiki>
[4] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016954.html <https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016954.html>
[5] https://github.com/bitcoin/bitcoin/blob/master/src/script/script.h <https://github.com/bitcoin/bitcoin/blob/master/src/script/script.h>
> On May 22, 2019, at 23:01, Russell O'Connor via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> Recently there have been some tapscript proposals, SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY, that aim to enable particular new features for Bitcoin via new Script operations.  However, I think that these proposals miss the mark when it comes to how they approach Bitcoin Script and language features.
> 
> Bitcoin Script appears designed to be a flexible programmable system that provides generic features to be composed to achieve various purposes.  Thus, when we design new language features for Script, we should be striving, as much as possible, to similarly build general purpose tools which can in turn be used for a variety of purposes.
> 
> I feel the SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY proposals fail to achieve these design goals.  They are both are designed with very narrow applications in mind, while also going out of their way to extend the semantic domain of the interpretation of Bitcoin operations in new ways that complicate their specification.  In the case of SIGHASH_ANYPREVOUT, the semantic domain is extended by adding new counters to track the use of various v0 and v2 signature types.  In the case of OP_CHECKOUTPUTHASHVERIFY, it employs a new context-sensitive operation that peeks at the value of surrounding opcodes.
> 
> Instead, I propose that, for the time being, we simply implement OP_CAT and OP_CHECKSIGFROMSTACKVERIFY.  OP_CAT pops two byte arrays off the stack and pushes their concatenation back onto the stack.  OP_CHECKSIGFROMSTACKVERIFY pops a signature, message, and pubkey off the stack and performs a bip-schnorr verification on the SHA256 hash of the message.
> 
> In concert, these two operations enable:
> 
> * Oracle signature verification, including discrete log contracts.
> * Amortized secure multiparty computations (see "Amortizing Secure Computation with Penalties" by Kumaresan and Bentov).
> * Transaction introspection including:
> + <> Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply by the nature of the construction.
> + <> Decide if a transaction has exactly one input or not. (etc.)
> + Weak covenants, which can verify output scripts to see if they are among a set of predefined values or verify the output hash.
> 
> and presumably more applications as well.
> 
> For better or for worse, without an OP_PUBKEYTWEEK operation available, the more interesting recursive-covenants remain largely out of reach, with the exception of a recursive covenant that is only able to send back to its own address, possibly abusing its own TXO value as a state variable.
> 
> All this is accomplished by two straightforward opcodes whose semantics are pure computational operations on stack values.  The only semantic side-effect is that OP_CHECKSIGFROMSTACKVERIFY would count towards the existing 'sigops_passed' count.  Moreover, I feel that adding these operations does not preclude adding more specialized opcodes in the future as an optimization for whatever popular constructions come up, once we know what those are.
> 
> I feel that this style of generic building blocks truly embodies what is meant by "programmable money".
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[-- Attachment #1.2: Type: text/html, Size: 10332 bytes --]

[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 488 bytes --]