Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY

[Jeremy <jlrubin@mit.edu>]

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

Thanks for the feedback Russell, now and early. It deeply informed the
version I'm proposing here.

I weighed carefully when selecting this design that I thought it would be
an acceptable tradeoff after our discussion, but I recognize this isn't
exactly what you had argued for.

First off, with respect to the 'global state' issue, I figured it was
reasonable with this choice of constexpr rule given that a reasonable tail
recursive parser might look something like:

parse (code : rest) stack alt_stack just_pushed =
    match code with
        OP_PUSH => parse rest (x:stack) alt_stack True
        OP_DUP => parse rest (x:stack) alt_stack False
        // ...

So we're only adding one parameter which is a bool, and we only need to
ever set it to an exact value based on the current code path, no
complicated rules. I'm sensitive to the complexity added when formally
modeling script, but I think because it is only ever a literal, you could
re-write it as co-recursive:

parse_non_constexpr (code : rest) stack alt_stack =
    match code with
        OP_PUSH => parse_constexpr rest (x:stack) alt_stack
        OP_DUP => parse_non_constexpr rest (x:stack) alt_stack
        // ...

parse_constexpr (code : rest) stack alt_stack  =
    match code with
        OP_CTV => ...
        _ => parese_non_constexpr (code : rest) stack alt_stack


If I recall, this should help a bit with the proof automatability as it's
easier in the case by case breakdown to see the unconditional code paths.


In terms of upgrade-ability, one of the other reasons I liked this design
is that if we do enable OP_CTV for non-constexpr arguments, the issue
basically goes away and the OP becomes "pure" without any state tracking.
(I think the switching on argument size is much less a concern because we
already use similar upgrade mechanisms elsewhere, and it doesn't add
parsing context).


It's also possible, as I think *should be done* for tooling to treat an
unbalanced OP_CTV as a parsing error. This will always produce
consensus-valid scripts! However by keeping the consensus rules more
relaxed we keep our upgrade-ability paths open for OP_CTV, which as I
understand from speaking with other users is quite desirable.


Best (and happy thanksgiving to those celebrating),

Jeremy

--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>


On Thu, Nov 28, 2019 at 6:33 AM Russell O'Connor <roconnor@blockstream.io>
wrote:

> Thanks for this work Jeremy.
>
> I know we've discussed this before, but I'll restate my concerns with
> adding a new "global" state variable to the Script interpreter for tracking
> whether the previous opcode was a push-data operation or not.  While it
> isn't so hard to implement this in Bitcoin Core's Script interpreter,
> adding a new global state variable adds that much more complexity to anyone
> trying to formally model Script semantics.  Perhaps one can argue that
> there is already (non-stack) state in Script, e.g. to deal with
> CODESEPARATOR, so why not add more?  But I'd argue that we should avoid
> making bad problems worse.
>
> If we instead make the CHECKTEMPLATEVERIFY operation fail if it isn't
> preceded by (or alternatively followed by) an appropriate sized
> (canonical?) PUSHDATA constant, even in an unexecuted IF branch, then we
> can model the Script semantics by considering the
> PUSHDATA-CHECKTEMPLATEVERIFY pair as a single operation.  This allows
> implementations to consider improper use of CHECKTEMPLATEVERIFY as a
> parsing error (just as today unbalanced IF-ENDIF pairs can be modeled as a
> parsing error, even though that isn't how it is implemented in Bitcoin
> Core).
>
> I admit we would lose your soft-fork upgrade path to reading values off
> the stack; however, in my opinion, this is a reasonable tradeoff.  When we
> are ready to add programmable covenants to Script, we'll do so by adding
> CAT and operations to push transaction data right onto the stack, rather
> than posting a preimage to this template hash.
>
> Pleased to announce refinements to the BIP draft for
>> OP_CHECKTEMPLATEVERIFY (replaces previous OP_SECURETHEBAG BIP). Primarily:
>>
>> 1) Changed the name to something more fitting and acceptable to the
>> community
>> 2) Changed the opcode specification to use the argument off of the stack
>> with a primitive constexpr/literal tracker rather than script lookahead
>> 3) Permits future soft-fork updates to loosen or remove "constexpr"
>> restrictions
>> 4) More detailed comparison to alternatives in the BIP, and why
>> OP_CHECKTEMPLATEVERIFY should be favored even if a future technique may
>> make it semi-redundant.
>>
>> Please see:
>> BIP: https://github.com/JeremyRubin/bips/blob/ctv/bip-ctv.mediawiki
>> Reference Implementation:
>> https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify
>>
>> I believe this addresses all outstanding feedback on the design of this
>> opcode, unless there are any new concerns with these changes.
>>
>> I'm also planning to host a review workshop in Q1 2020, most likely in
>> San Francisco. Please fill out the form here
>> https://forms.gle/pkevHNj2pXH9MGee9 if you're interested in
>> participating (even if you can't physically attend).
>>
>> And as a "but wait, there's more":
>>
>> 1) RPC functions are under preliminary development, to aid in testing and
>> evaluation of OP_CHECKTEMPLATEVERIFY. The new command `sendmanycompacted`
>> shows one way to use OP_CHECKTEMPLATEVERIFY. See:
>> https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-rpcs.
>> `sendmanycompacted` is still under early design. Standard practices for
>> using OP_CHECKTEMPLATEVERIFY & wallet behaviors may be codified into a
>> separate BIP. This work generalizes even if an alternative strategy is used
>> to achieve the scalability techniques of OP_CHECKTEMPLATEVERIFY.
>> 2) Also under development are improvements to the mempool which will, in
>> conjunction with improvements like package relay, help make it safe to lift
>> some of the mempool's restrictions on longchains specifically for
>> OP_CHECKTEMPLATEVERIFY output trees. See: https://github.com/bitcoin/bitcoin/pull/17268
>> This work offers an improvement irrespective of OP_CHECKTEMPLATEVERIFY's
>> fate.
>>
>>
>> Neither of these are blockers for proceeding with the BIP, as they are
>> ergonomics and usability improvements needed once/if the BIP is activated.
>>
>> See prior mailing list discussions here:
>>
>> *
>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016934.html
>> *
>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/016997.html
>>
>> Thanks to the many developers who have provided feedback on iterations of
>> this design.
>>
>> Best,
>>
>> Jeremy
>>
>> --
>> @JeremyRubin <https://twitter.com/JeremyRubin>
>>
>

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