[bitcoin-dev] CTV through SIGHASH flags

[bitcoin-dev] CTV through SIGHASH flags

[Bob McElrath]

We propose that OP_CHECKTEMPLATEVERIFY should behave more like CHECKSIG,
including a flags byte that specify what is hashed. This unifies the ways a
SigHash is computed, differing only in the final checksig which is omitted in
favor of chacking the hash directly. Having two paths to create a signature hash
introduces extra complexity, especially as concerns potential future SIGHASH
flag upgrades.

CTV omits inputs as part of its semantics, so CTV-type functionality using
CHECKSIG is also achievable if some form of NOINPUT flag is also deployed. With
NOINPUT alone, a standard CHECKSIG can be used to implement a covenant -- though
it uses an unnecessarily large number of bytes just to check a 32-byte hash.
Therefore, any pitfalls CTV intends to evade can be evaded by using a CHECKSIG,
if NOINPUT is deployed in some form, adding new flexibility.  Beyond what's
possible with NOINPUT/ANYPREVOUT, CTV additionally commits to: 

»·······1. Number of inputs
»·······2. Number of outputs
»·······3. Index of input

The justification given for committing to the number of inputs and outputs is
that "it makes CTV hashes easier to compute with script", however doing so would
require OP_CAT. It's noted that both of these are actually redundant
commitments. Since the constexpr requirement was removed, if OP_CAT were
enabled, this commitment to the input index could be evaded by computing the CTV
hash within the script, modifying the input index using data taken from the
witness. Therefore committing to the input index is a sender-specified-policy
choice, and not an anti-footgun measure for the redeemer. As such, it's
appropriate to consider committing to the input index using a flag instead.

I believe the above may be possible *without* a new opcode and simply with a
sighash flag. That is, consider a flag SIGHASH_NOSIG which behaves as follows:
The stack is expected to contain <hash> <flags>, where the hash to be checked is
<hash> and is in the place where you'd normally put a pubkey. The byte <flags>
is the second thing on the stack. This is intended to be an empty "signature"
with the flags byte appended (which must contain SIGHASH_NOSIG to succeed).

There are probably reasons this might not work as a flag that I haven't
discovered yet. Alternatively CTV might be considered to be an alternative type
of CHECKSIG operator and might be renamed to CHECKSIGHASH, appending flag bytes
to the hash to be checked.

The flags discussed above, NOINPUT, NOSIG, INPUTINDEX are all really
sender-policy choices, while SIGHASH flags are redeemer-choice as they usually
occur in the witness. There's really no way currently for an output to specify
that the redeemer must use a particular set of flags. One way to achieve this is
to put the CHECKSIG(HASH) including its flags into the redeemScript -- which is
functionally what CTV does (or a CHECKSIG in a redeemScript using NOINPUT).
This is committed to in outputs and therefore specifies sender policies, however
the redeemScript is specified by the receiver.  Perhaps an anti-footgun measure
would be to require that certain SIGHASH flags like these MUST be committed to
in the output, by the sender.

CSV (CHECKSEQUENCEVERIFY) is an example that redemption policies are committed
to in the output by the sender via the sequence_no field, and then checked with
an opcode OP_CSV to enable relative timelocks. It's probably possible to add new
flags to the sequence_no field, and check the new semantics with CSV instead of
an entiely new opcode.

As user policy choices, NOINPUT might be considered "MAY" conditions. A user MAY
use NOINPUT on an output, but let's not require it.  Covenants on the other
hand, are a MUST condition. The CTV proposal imposes "MUST" conditions on the
existence of the covenant itself, as well as the number of inputs and outputs,
to prevent txid malleability so that such transactions can be used in offline
protocols. Txid non-malleability can be achieved by enforcing that the output
must be spent using SIGHASH_ALL instead of committing to the number of inputs
separately with a new opcode. The MUST condition also helps with sighash caching
for batch validation.

INPUTINDEX is required in a CTV/CHECKSIGHASH world because of the half-spend
problem. Normally outputs are spent uniquely as long as different addresses are
used on the outputs. A transaction with the same address appearing twice would
also have a half-spend problem. Anyone signing the first output and giving that
PSBT to another person can allow them to spend the second input. Therefore one
might even want INPUTINDEX for non-covenant transactions, though making a tx
with the same address twice seems like a silly idea to me.

Therefore, assuming a CSV-type mechanism can be devised using sequence_no, CTV
is equivalent to a flag in sequence_no that is logically
MUST|ALL|NOSIG|INPUTINDEX and a redeemScript of <hash> <flags>.

Lightning-like use cases might put sequence_no flags that are logically
MAY|ALL|NOINPUT.

The other mechanism for sender policy is scriptPubKey, which is heavily
restricted by isStandard, but might be another place to specify flags like the
above.

Thoughts? 

Does this idea address any of the NOINPUT footguns? (which I'm not up on) 
Is there a reason this cannot be done with sequence_no and OP_CSV?
Is there a reason that a separate opcode (CTV) is different/better than this
approach?

--
Cheers, Bob McElrath

"For every complex problem, there is a solution that is simple, neat, and wrong."
    -- H. L. Mencken 

Re: [bitcoin-dev] CTV through SIGHASH flags

[Jeremy]

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

I think these ideas shows healthy review of how OP_CTV is specified against
alternatives, but I think most of the ideas presented are ill advised.

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


On Sat, Feb 1, 2020 at 2:15 PM Bob McElrath via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> We propose that OP_CHECKTEMPLATEVERIFY should behave more like CHECKSIG,
> including a flags byte that specify what is hashed. This unifies the ways a
> SigHash is computed, differing only in the final checksig which is omitted
> in
> favor of chacking the hash directly. Having two paths to create a
> signature hash
> introduces extra complexity, especially as concerns potential future
> SIGHASH
> flag upgrades.

<snip>

> I believe the above may be possible *without* a new opcode and simply with
> a
> sighash flag. That is, consider a flag SIGHASH_NOSIG which behaves as
> follows:
> The stack is expected to contain <hash> <flags>, where the hash to be
> checked is
> <hash> and is in the place where you'd normally put a pubkey. The byte
> <flags>
> is the second thing on the stack. This is intended to be an empty
> "signature"
> with the flags byte appended (which must contain SIGHASH_NOSIG to succeed).
>


I've previously brought this up in IRC
http://gnusha.org/bitcoin-wizards/2019-11-28.log


AFAIK, using an actual CheckSig SIGHASH Flag as is is a bad idea because
then you need to include an encoding valid signature and pubkey that map
onto the hash to check. This is not just extra 11 extra bytes of data (33
bytes PubKey + 9 bytes Signature + 2 push -32 bytes - 1 byte push), it's
also a very awkward API. I don't think you can soft-fork around these
encoding rules. But you're right that it's possible to add this as a
SIGHASH flag. I don't think doing CTV as a sighash flag is worth
considering further.

I get your point that CTV is kind of a signature hash, and that we might
want to not have a separate path. This ignores, however, that the current
SIGHASH code-path is kind of garbage and literally no one likes it and it
has been the source of nasty issues previously. Thus I posit that a
separate path creates less complexity, as we don't need to worry about
accidentally introducing a weird interaction with other sighash flags.




> CTV omits inputs as part of its semantics, so CTV-type functionality using
> CHECKSIG is also achievable if some form of NOINPUT flag is also deployed.
> With
> NOINPUT alone, a standard CHECKSIG can be used to implement a covenant --
> though
> it uses an unnecessarily large number of bytes just to check a 32-byte
> hash.
> Therefore, any pitfalls CTV intends to evade can be evaded by using a
> CHECKSIG,
> if NOINPUT is deployed in some form, adding new flexibility.  Beyond what's
> possible with NOINPUT/ANYPREVOUT, CTV additionally commits to:
>
> »·······1. Number of inputs
> »·······2. Number of outputs
> »·······3. Index of input
>

NOINPUT as specified here
https://github.com/ajtowns/bips/blob/bip-anyprevout/bip-anyprevout.mediawiki
(is this the latest?) isn't a great surrogate for CTV because CTV commits
to the input index which prevents half-spend. This also encumbers, as
proposed, an additional chaperone signature to fix it to a specific output.

This adds a lot of complexity and space to using CTV. Maybe NOINPUT could
make changes to special-case CTV, but then we're back to CTV again.



>
> The justification given for committing to the number of inputs and outputs
> is
> that "it makes CTV hashes easier to compute with script", however doing so
> would
> require OP_CAT. It's noted that both of these are actually redundant
> commitments. Since the constexpr requirement was removed, if OP_CAT were
> enabled, this commitment to the input index could be evaded by computing
> the CTV
> hash within the script, modifying the input index using data taken from the
> witness. Therefore committing to the input index is a
> sender-specified-policy
> choice, and not an anti-footgun measure for the redeemer. As such, it's
> appropriate to consider committing to the input index using a flag instead.
>
> This is incorrect almost entirely.

1. There is a semantic difference between the *commitment* being strictly
redundant, which has more to do with malleation, and being redundant from a
feature perspective. I could maybe do a better job here of expanding what
"easier" means here -- there are actually some scripts which are quite
difficult to write/impossible without this. I've described this a couple
places outside of the BIP, but essentially it allows you to pin the number
of inputs/outputs separately from the hashes themselves. So if you're
trying to build the template in script, you might want to allow the
Sequences to be set to any value, and pass them via a hash. But then from a
hash you can't check the validity of the length. An external length
commitment lets you do this, but without it you would have to pass in the
sequences directly.
2. The constexpr requirement was implemented in a soft-fork re-moveable
manner specifically so that if we wanted OP_CAT, we could add it without
also introducing constructing CTVs on the stack. Similarly, it would be
possible to specify with OP_CAT as a soft-fork removeable rule that if
OP_CAT executes before an OP_CTV, the script is invalid. The constexpr rule
was removed on the sentiment that if we introduce OP_CAT, we almost surely
intend to introduce it for OP_CTV (or related) use cases.
3. Committing to the input-index is not a *sender* policy choice. It's a
receiver policy choice. I tell a Payer my invoice/address, and they emit a
transaction matching it. From an address containing a CTV, I as the
receiver set the input_index. I don't see how this is related to the
anti-footgun-ness
4. You write as if OP_CTV + OP_CAT allows the input index to stripped
*unconditionally*. That's wrong. It's an opt in if you write a script
taking it as a parameter. You can't evade it in general use.
5. The "anti-footgun" measure is that it precludes reused-keys being spent
in the same transaction. Were you to opt out of the mechanism (via OP_CAT
input_index), then you opt out of the reuse protection. (This only matters
if there is more than one input to begin with).
6. Committing to it via a flag is strictly less flexible, because I can do
a lot more with OP_CAT than with a flag. For instance, I can do
<input_index> <min> <max> OP_WITHIN OP_VERIFY to ensure that it falls
within a certain range of inputs.
7. A flag is also an extra byte somewhere or uses a sighash bit.
8. Enabling a flag right away enables a big footgun right off the bat. I
think it's bad for use safety.
9. Rather than add flags, if you wanted to add this, I would suggest
reserving max input_index to specify a don't care value. Then you always
check a given CTV against the don't care value and the specified value.
Hashing the don't care value can be done in the PreComputedTxData. But I
don't think it's worth special casing or making available today because of
8.



> There are probably reasons this might not work as a flag that I haven't
> discovered yet. Alternatively CTV might be considered to be an alternative
> type
> of CHECKSIG operator and might be renamed to CHECKSIGHASH, appending flag
> bytes
> to the hash to be checked.
>

Sure -- happy to go down the renaming path again. Keep in mind that CTV
currently only applies rules when the argument is 32-bytes. Future
soft-forkers are welcome to define a rule for a 33byte 1st argument that
treats it as a pubkey and has CHECKSIG semantics, and looks for another
argument.



>
> The flags discussed above, NOINPUT, NOSIG, INPUTINDEX are all really
> sender-policy choices, while SIGHASH flags are redeemer-choice as they
> usually
> occur in the witness. There's really no way currently for an output to
> specify
> that the redeemer must use a particular set of flags. One way to achieve
> this is
> to put the CHECKSIG(HASH) including its flags into the redeemScript --
> which is
> functionally what CTV does (or a CHECKSIG in a redeemScript using NOINPUT).
> This is committed to in outputs and therefore specifies sender policies,
> however
> the redeemScript is specified by the receiver.  Perhaps an anti-footgun
> measure
> would be to require that certain SIGHASH flags like these MUST be
> committed to
> in the output, by the sender.
>
>
I think this "sender/redeemer" framework is a bit bunk. Ultimately all
redeemers are senders, and you aren't forcing a choice on someone. You
could be on to something though, but I think in general Bitcoin has gone
the way of opaque addresses so that people can't encumber arbitrary
policies on your coins. Maybe it swings the other way...



> CSV (CHECKSEQUENCEVERIFY) is an example that redemption policies are
> committed
> to in the output by the sender via the sequence_no field, and then checked
> with
> an opcode OP_CSV to enable relative timelocks. It's probably possible to
> add new
> flags to the sequence_no field, and check the new semantics with CSV
> instead of
> an entiely new opcode.
>


The sender commits to them, but legally, if you add a contract that I
didn't agree to as receipt (e.g., in segwit address -- which the script is
hashed) I won't even know I got paid. So the way Bitcoin works today, these
are receiver set policies.

One way to think of CTV is it's precise the opcode that lets you "wrap"
someone's known address in arbitrary new scripts. E.g., if you gave me an
address X, but I need to (for whatever reason) add an additional 1 month
CSV.

So i just get the txn:

A:
    sequence 1mo
    1 input
    1 output: pay X 1 coin

then take the STH(A), and create B


B:
    ... inputs
    1 output pay `STH(A) CTV` 1 coin

I can also add other things, like secondary signers/alternatives

`IF {some checksig program} STH(A) CTV ELSE {multisig program} ENDIF



> As user policy choices, NOINPUT might be considered "MAY" conditions. A
> user MAY
> use NOINPUT on an output, but let's not require it.  Covenants on the other
> hand, are a MUST condition. The CTV proposal imposes "MUST" conditions on
> the
> existence of the covenant itself, as well as the number of inputs and
> outputs,
> to prevent txid malleability so that such transactions can be used in
> offline
> protocols. Txid non-malleability can be achieved by enforcing that the
> output
> must be spent using SIGHASH_ALL instead of committing to the number of
> inputs
> separately with a new opcode. The MUST condition also helps with sighash
> caching
> for batch validation.
>

ANYPREVOUT/ANYSCRIPT are actually weirder than that, because once it has
been used that key is permanently "burned". Hence ANYPREVOUT has such
pubkeys be explicity tagged as ANYPREVOUT compatible. So a user kind of has
to pre-decide if they want to have ANYPREVOUT semantics or not.
And in this case, key-reuse is relatively unsafe (as you need to track what
else you've signed) so I think what you're suggesting is not robust.

These "MUST" conditions sound nice, but they don't actually help with
validity caching because we want to be able to compute this information
before we've fetched the outputs from the database so we can't know what to
cache yet. Contextless things are things you can precompute not knowing
input scripts.

Again, I don't think this sender/redeemer framework is super useful but I
admire the attempt.



>
> INPUTINDEX is required in a CTV/CHECKSIGHASH world because of the
> half-spend
> problem. Normally outputs are spent uniquely as long as different
> addresses are
> used on the outputs. A transaction with the same address appearing twice
> would
> also have a half-spend problem. Anyone signing the first output and giving
> that
> PSBT to another person can allow them to spend the second input. Therefore
> one
> might even want INPUTINDEX for non-covenant transactions, though making a
> tx
> with the same address twice seems like a silly idea to me.
>

I'm confused. Transactions don't have addresses. What are you talking about?

Input indexes accomplish two goals.

One, they eliminate third-party malleability of input order (which would
muck with sighash singles too).
Two, they prevent half-spend.

Signatures today commit to this in the signature hash (the field is nIn,
which is confusing because nIn might also look like vin.size()).

So the half spend problem doesn't exist today...

>
> Therefore, assuming a CSV-type mechanism can be devised using sequence_no,
> CTV
> is equivalent to a flag in sequence_no that is logically
> MUST|ALL|NOSIG|INPUTINDEX and a redeemScript of <hash> <flags>.
>
> Lightning-like use cases might put sequence_no flags that are logically
> MAY|ALL|NOINPUT.
>
> The other mechanism for sender policy is scriptPubKey, which is heavily
> restricted by isStandard, but might be another place to specify flags like
> the
> above.
>
> Thoughts?
>
>

So OP_CAT already lets you do this kind of stuff with the SIGHASHes rather
than a new special-purpose verifier. Just pass the signature separately
from the flags, and cat them togehther for the checker but just look at the
flags for your new thing. Then check that the flags are exactly what you
wanted. If you don't want OP_CAT, you can also add OP_SUBSTRVERIFY wherein
you verify that a provided substr was inside another string. Then you pass
in the witness the full string you want, as well as sub-bits you want to
check properties on (like the flags).

It's not clear to me that we want this kind of stuff though. OP_CAT
requires very careful review because it has very surprising functional
consequences across the board.



> Does this idea address any of the NOINPUT footguns? (which I'm not up on)
> Is there a reason this cannot be done with sequence_no and OP_CSV?
>

ANYPREVOUT already precludes these by using a separate key type and
chaperone signatures.  I think a flag for MUST NOT ANYPREVOUT would maybe
help with making it safer. But this is a complete sidebar from CTV. This
exists already by generating a non-anyprevout capable key though...



> Is there a reason that a separate opcode (CTV) is different/better than
> this
> approach?
>
>
I'll let the email above serve as the answer to your question.

I don't think there's anything gained by expressing CTV as a sighash type
today, especially since a future soft fork (when we've taking the time to
deeply rethink sighash flags, like bitmask sighash flags proposed for
elements) can make CTV (as specified today) a valid hash in this new
language and use the OP_NOP4 with a non 32-byte argument as the new
CheckSig operator anyways.







But now I'll pose a different question: why shouldn't we compute the
sighash entirely as a type of Bitcoin Script? SIGHASH_FLAGS are essentially
a tiny, crappy, language for putting together a message digest. You can
think of SIGHASH_FLAGS as being like optimized "jets" for known programs.
For custom programs, you can construct the digest pattern you want in
script. This is essentially what the bitmask sighash flags proposal is. I
think you're going to waste a lot of mental-cycles trying to cram in all
this logic into flags. As this stuff gets more complicated, you should just
write an actual language for dealing with sighashes and go from there.

Now why don't we want this sighash language? Quadratic hashing. If every
output commits to some different complex thing, we end up doing a lot of
rehashing. Flags are actually kind of bad because a few different flags can
trigger a lot of rehashing. But the way flags are *today* is relatively OK
because we can cache the important parts so validation is cheap.

The more complicated you plan gets, the less context free validation we can
do.

CTV is fully compatible with context free validation optimizations,
trivially. It's not clear if your other stuff is, I suspect not.

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