Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY

[Jeremy via bitcoin-dev]

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 



On Thu, Nov 28, 2019 at 6:33 AM Russell O'Connor 
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 

Re: [bitcoin-dev] Signing CHECKSIG position in Tapscript

[Anthony Towns via bitcoin-dev]

On Wed, Nov 27, 2019 at 04:29:32PM -0500, Russell O'Connor via bitcoin-dev 
wrote:
> The current tapscript proposal requires a signature on the last executed
> CODESEPRATOR position.  I'd like to propose an amendment whereby instead of
> signing the last executed CODESEPRATOR position, we simply always sign the
> position of the CHECKSIG (or other signing opcode) being executed.

FWIW, there's discussion of this at
http://www.erisian.com.au/taproot-bip-review/log-2019-11-28.html#l-65

> However, unless CODESEPARATOR is explicitly used, there is no protection
> against these sorts of attacks when there are multiple participants that have
> signing conditions within a single UTXO (or rather within a single tapleaf in
> the tapscript case).

(You already know this, but:)

With taproot key path spending, the only other conditions that can be
placed on a transaction are nSequence, nLockTime, and the annex, all of
which are committed to via the signature; so I think this concern only
applies to taproot script path spending.

The proposed sighashes for taproot script path spending all commit to
the script being used, so you can't reuse the signature in a different
leaf of the merkle tree of scripts for the UTXO, only in a separate
execution path within the script you're already looking at.

> So for example, if Alice and Bob are engaged in some kind of multi-party
> protocol, and Alice wants to pre-sign a transaction redeeming a UTXO but
> subject to the condition that a certain hash-preimage is revealed, she might
> verify the Script template shows that the code path to her public key enforces
> that the hash pre-image is revealed (using a toolkit like miniscript can aid 
> in
> this), and she might make her signature feeling secure that it, if her
> signature is used, the required preimage must be revealed on the blockchain. 
> But perhaps Bob has masquated Alice's pubkey as his own, and maybe he has
> inserted a copy of Alice's pubkey into a different path of the Script
> template.
>
> Now Alice's signature can be copied and used in this alternate path,
> allowing the UTXO to be redeemed under circumstances that Alice didn't believe
> she was authorizing.  In general, to protect herself, Alice needs to inspect
> the Script to see if her pubkey occurs in any other branch.  Given that her
> pubkey, in principle, could be derived from a computation rather that pushed
> directly into the stack, it is arguably infeasible for Alice to perform the
> required check in general.

First, it seems like a bad idea for Alice to have put funds behind a
script she doesn't understand in the first place. There's plenty of
scripts that are analysable, so just not using ones that are too hard to
analyse sure seems like an option.

Second, if there are many branches in the script, it's probably more
efficient to do them via different branches in the merkle tree, which
at least for this purpose would make them easier to analyse as well
(since you can analyse them independently).

Third, if you are doing something crazy complex where a particular key
could appear in different CHECKSIG operators and they should have
independent signatures, that seems like you're at the level of
complexity where learning about CODESEPARATOR is a reasonable thing to
do.

I think CODESEPARATOR is a better solution to this problem anyway. In
particular, consider a "leaf path root OP_MERKLEPATHVERIFY" opcode,
and a script that says "anyone in group A can spend if the preimage for
X is revelaed, anyone in group B can spend unconditionally":

 IF HASH160 x EQUALVERIFY groupa ELSE groupb ENDIF
 MERKLEPATHVERIFY CHECKSIG

spendable by

 siga keya path preimagex 1

or

 sigb keyb path 0

With your proposed semantics, if my pubkey is in both groups, my signature
will sign for position 10, and still be valid on either path, even if
the signature commits to the CHECKSIG position.

I could fix my script either by having two CHECKSIG opcodes (one for
each branch) and also duplicating the MERKLEPATHVERIFY; or I could
add a CODESEPARATOR in either IF branch.

(Or I could just not reuse the exact same pubkey across groups; or I could
have two separate scripts: "HASH160 x EQUALVERIFY groupa MERKLEPATHVERIFY
CHECKSIG" and "groupb MERKLEPATHVERIFY CHECKSIG")

> I believe that it would be safer, and less surprising to users, to always sign
> the CHECKSIG position by default.

> As a side benefit, we get to eliminate CODESEPARATOR, removing a fairly 
> awkward
> opcode from this script version.

As it stands, ANYPREVOUTANYSCRIPT proposes to not sign the script code
(allowing the signature to be reused in different scripts) but does
continue signing the CODESEPARATOR position, allowing you to optionally
restrict how flexibly you can reuse signatures. That seems like a better
tradeoff than having ANYPREVOUTANYSCRIPT signatures commit to the CHECKSIG
position which would make it a fair bit harder to design scripts that
can share signatures, or not having any way to restrict