Date: Tue, 22 Aug 2023 10:04:38 -0700
From: Brandon Black <freedom@reardencode.com>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <ZOTqppwATA9HyfND@console>
Mail-Followup-To: bitcoin-dev@lists.linuxfoundation.org
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Subject: [bitcoin-dev] Combined CTV+APO to minimal TXHASH+CSFS
Precedence: list

Hi list,

https://gist.github.com/reardencode/2aa98700b720174598d21989dd46e781

I'm seeking feedback on this proposal to provide the functionality
requested by those advocating for bip118 and bip119 in a combined way
that retains the low risk associated with each of those separate
proposals. At least part of the reason for creating this is similar to
my reason for creating bips PR#1472, and my covenant comparo
spreadsheet, i.e. to help further the discussion of these proposals and
make more clear the similarities and differences between them.

https://github.com/bitcoin/bips/pull/1472
https://docs.google.com/spreadsheets/d/1YL5ttNb6-SHS6-C8-1tHwao1_19zNQ-31YWPAHDZgfo/edit

It's become clear to me that in large part the separation between
advocates of these two proposals stems from a lack of full understanding
of their properties. My hope is that this work helps to clarify our
thinking about them individually and together, and potentially move
toward consensus on a path toward enabling better lightning, vaults, and
likely other amazing ways to use bitcoin in the future.

-----------------------

# Abstract

This proposal is an alternative to [bip119][] and [bip118][], providing the
functionality of both proposals with no additional overhead in [many
cases](#compared-to-non-tapscript-ctv), while clearing certain objections to
both, and opening clear upgrade paths.

This is, in essence, an initially constrained version of Russel O'Connor's
[OP_TXHASH+OP_CSFS proposal][].

We define three new Tapscript-only opcodes. Replacing `OP_SUCCESS80`,
`OP_SUCCESS187`, and `OP_SUCCESS188` with `OP_TXHASH`, `OP_CHECKSIGFROMSTACK`,
and `OP_CHECKSIGFROMSTACKVERIFY` respectively.

# Summary

For `OP_TXHASH`, we define exactly 5 methods of hashing the transaction depending
on a minimally encoded numeric argument popped from the stack:

argument | behavior
-------- | -----------------
   0     | as in [bip119][]
   1     | as in [bip118][] with sighash flag `0x41`
   2     | as in [bip118][] with sighash flag `0xc1`
   3     | as in [bip118][] with sighash flag `0x43`
   4     | as in [bip118][] with sighash flag `0xc3`

`OP_CHECKSIGFROMSTACK(VERIFY)` is defined similarly to the [implementation in
the Elements project][OP_CHECKSIGFROMSTACK in elements], but does not
internally SHA256 hash the data argument. As [bip340][] defines signatures on
arbitrary length messages, and these `OP_CHECKSIGFROMSTACK(VERIFY)` are
defined only in Tapscript, the internal hashing is unnecessarily restrictive.
Users may wish to use pre-hashed values as in this proposal, or non-SHA256
hashes available in script.

# Motivation

Much ink has been spilled on the discussion of what is next for bitcoin scipt
development. The two proposals nearest to consensus are [bip118][] and
[bip119][], but the proponents of each disagree about the relative priority
and the merrits of the other. Here, we'll briefly outline some of the
objections to each and demonstrate how this proposal reduces those objections.
We will not discuss the concerns about the introduction of covenants or
recursive covenants generally.

## [CTV][bip119] Objections

* Not general enough
* Inefficient when otherwise validating the hash (e.g. when combined with
  `OP_CHECKSIGFROMSTACK`)
* Uses `OP_NOPx` extension semantics even though `OP_SUCCESSx` is available

## [APO][bip118] Objections

* Not general enough
* Accidentally enables inefficient, hard to use covenants
* Uses new Tapscript key version to avoid accidents

## Solutions

* By providing the behavior of both [bip118][] and [bip119][], this proposal
  is more general than either of those proposals. It also provides explicit
  upgrade hooks for further generality (e.g. to
  [full OP_TXHASH][OP_TXHASH+OP_CSFS proposal]).
* By splitting the hashing from the validation of [bip119], the hash can be
  used in ways other than `OP_EQUALVERIFY`.
* We use `OP_SUCCESSx` upgrade semantics.
* We explicitly enable some of the sighash-based covenants accidentally
  enabled by [bip118][].
* By using new signature checking opcodes, we do not require the safety of a
  new Tapscript key version.

# Specification

## `OP_TXHASH`

When validating Tapscript, the behavior of `OP_SUCCESS80` is modified as
follows:
* If there is not at least one item on the stack, fail[^1].
* If the top item on the stack is not a minimally encoded `OP_0`, `OP_1`, or
  `OP_2`; succeed immediately[^2].
* Pop the top item from the stack, and name it `hash_mode`
* If `hash_mode` is 0:
    * Hash the transaction as defined in [bip119][]
    * Push the resulting hash to the stack
* If `hash_mode` is 1:
    * Hash the transaction as defined in [bip118][] using `sighash_type=0x41`
    * Push the resulting hash to the stack
* If `hash_mode` is 2:
    * Hash the transaction as defined in [bip118][] using `sighash_type=0xc1`
    * Push the resulting hash to the stack
* If `hash_mode` is 3:
    * Hash the transaction as defined in [bip118][] using `sighash_type=0x43`
    * Push the resulting hash to the stack
* If `hash_mode` is 4:
    * Hash the transaction as defined in [bip118][] using `sighash_type=0xc3`
    * Push the resulting hash to the stack

## `OP_CHECKSIGFROMSTACK(VERIFY)`

When validating Tapscript, the behavior of `OP_SUCCESS187` and `OP_SUCCESS188`
are modified as follows:
* If there are not at least 3 items on the stack, fail[^1].
* If the top-minus-0 stack item's length is not 32, succeed immediately[^2].
* If the top-minus-2 stack item's length is not 64, fail[^3].
* Pop the top 3 stack items as `pubkey`, `msg`, and `sig` respectively.
* Let `result` equal the result of verifying `sig` against `msg` and `pubkey` according to [bip340][].
* Push `true` if `result` otherwise `false` to the stack.
* If validating `OP_CHECKSIGFROMSTACKVERIFY`
    * Pop the top item from the stack as `check`.
    * If `check` is not `true`, fail.

# Discussion

### How does the efficiency compare to [bip118][]?

`SIGHASH_ANYPREVOUT`:
```
<64-byte signature>||<1-byte sighash type> <33-byte pubkey> OP_CHECKSIG(VERIFY)
with pushes: 64+1+1 + 33+1 + 1 = 101 witness bytes (25.25vBytes)
```

This proposal:
```
<64-byte signature> <1-byte argument> OP_TXHASH <32-byte pubkey> OP_CHECKSIGFROMSTACK(VERIFY)
with pushes: 64+1 + 1 + 1 + 32+1 + 1 = 101 witness bytes (25.25vBytes)
```

### How does the efficiency compare to [bip119][]?

#### Both in Tapscript

`OP_CHECKTEMPLATEVERIFY` alone:
```
<32-byte hash> OP_CHECKTEMPLATEVERIFY OP_DROP OP_TRUE
with pushes: 32+1 + 1 + 1 + 1 = 36 witness bytes (9vBytes)
```

`OP_CHECKTEMPLATEVERIFY` with a subsequent check:
```
<32-byte hash> OP_CHECKTEMPLATEVERIFY OP_DROP <...>
with pushes: 32+1 + 1 + 1 = 35 witness bytes (8.75vBytes)
```

This proposal:
```
<1-byte argument> OP_TXHASH <32-byte hash> OP_EQUAL(VERIFY)
with pushes: 1 + 1 + 32+1 + 1 = 36 witness bytes (9 vBytes)
```

#### Compared to non-Tapscript CTV

Bare `OP_CHECKTEMPLATEVERIFY`:
```
Lock: <32-byte hash> OP_CHECKTEMPLATEVERIFY OP_DROP OP_TRUE
with pushes: 32+1 + 1 + 1 + 1 = 36 bytes (36vBytes)

Unlock: <empty>

Total: 36 + 0 = 36vBytes
```

Witness v0 CTV:
```
Lock: OP_0 <32-byte hash>
with pushes: 1 + 32+1 = 34 bytes (34 vBytes)

Unlock:
<36-byte witness script>
with sizes: 36+1 = 37 witness bytes (9.25vBytes)

Total: 34 + 9.25 = 43.25vBytes
```

This proposal:
```
Lock: OP_1 <32-byte pubkey>
with pushes: 1 + 32+1 = 34 bytes (34 vBytes)

Unlock:
<36-byte leaf script> <33-byte control block>
with sizes: 36+1 + 33+1 = 71 witness bytes (17.75vBytes)

Total: 34 + 17.75 = 51.75vBytes
```

Compared to bare CTV, this proposal is 15.75vBytes more costly. If CTV use
cases gain popularity, a separate upgrade for bare CTV may be warranted,
either as specified in [bip119][], as its own witness version, or some
alternative.

Bearing in mind the risks mentioned in [bip119][], fee sensitive users can add
`OP_RIPEMD160` to save 2.75 vBytes when using `OP_TXHASH` with
`OP_EQUAL(VERIFY)`. This brings the excess cost relative to bare CTV down to
13vBytes.

### Why not include modes for [bip118][] sighash_types 0x42 and 0xc2?[^4]

Possibly due to a lack of imagination, we are unable to see a use for signing
none of the inputs and none of the outputs (or a single input script and none
of the outputs).

### Can this be used in ln-symmetry?

Yes, this is fully compatible with ln-symmetry. It uses a different script,
but has the same size and behavior as [bip118][] for this purpose.

### Can this be used in PTLCs?

Yes, this is fully compatible with PTLCs. It uses a different script, but has
the same size and behavior as [bip118][] for this purpose.

### Can this be used with OP_VAULT?

Yes, this is fully compatible with OP_VAULT. It uses a different script, but
has the same size and behavior as [bip119][] for this purpose.

# What is hashed?

| field \ mode                        | CTV(0) | APO/ALL(1) | APOAS/ALL(2) | APO/SINGLE(3) | APOAS/SINGLE(4) |
| ----------------------------------- | ------ | ---------- | ------------ | ------------- | --------------- |
| hash_type                           |        | x          | x            | x             | x               |
| version/locktime                    | x      | x          | x            | x             | x               |
| this input UTXO                     |        |            |              |               |                 |
| other input UTXOs                   |        |            |              |               |                 |
| this script pubkey/amount           |        | x          |              | x             |                 |
| other script pubkeys/amounts        |        |            |              |               |                 |
| this script sig                     | x      |            |              |               |                 |
| other script sig                    | x      |            |              |               |                 |
| the number of inputs                | x      |            |              |               |                 |
| this input sequence                 | x      | x          | x            | x             | x               |
| other input sequences               | x      |            |              |               |                 |
| this input spend type/annex         |        | x          | x            | x             | x               |
| other input spend types/annexes     |        |            |              |               |                 |
| corresponding output script/amount  | x      | x          | x            | x             | x               |
| other output scripts/amounts        | x      | x          | x            |               |                 |
| the number of outputs               | x      |            |              |               |                 |

# Notes

[^1]: We fail on invalid stack lengths to ensure that attackers cannot skip
  validation.
[^2]: We succeed on unspecified txhash modes or pubkey lengths to allow future
  extensions.
[^3]: We fail on invalid signature lengths _after_ the pubkey length check,
  thus allowing only 64-byte signatures for 32-byte keys, but allowing future
  key types to potentially also have different signature lengths.
[^4]: As far as we know there is no use for sighash types other than those
  defined in [bip118][] with this proposal, as the other types either reduce
  to `OP_CHECKSIG(VERIFY)` or create infinite hash loops.

[bip118]: https://github.com/bitcoin/bips/blob/master/bip-0118.mediawiki
[bip119]: https://github.com/bitcoin/bips/blob/master/bip-0119.mediawiki
[bip340]: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
[OP_TXHASH+OP_CSFS proposal]: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-January/019813.html
[OP_CHECKSIGFROMSTACK in elements]: https://github.com/ElementsProject/elements/blob/f08447909101bfbbcaf89e382f55c87b2086198a/src/script/interpreter.cpp#L1399
[proposed ln-symmetry scripts]: https://github.com/instagibbs/bolts/blob/eltoo_draft/XX-eltoo-transactions.md

-----------------------

Best,

--Brandon