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

["Russell O'Connor" <roconnor@blockstream.io>]

[-- 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 --]