Update BIP 118 for taproot, rename to ANYPREVOUT #943

Lots of updates to BIP 118 in light of taproot. cc @cdecker

Gave it a quick read and didn't spot anything objectionable. One micro-nit.

I suggest that you get a new BIP number for ANYPREVOUT and add "not recommended for implementation" to bip118 (including reasoning, please ;-).

The two approaches are conceptually distinct and it's worth keeping the other idea around for historical purposes, even if it's not pursued going forward. BIP118 as a segwit version has been around for over 3 years now.

Please just give us one or the other! We're dying out here! ;-)

The two approaches are conceptually distinct and it's worth keeping the other idea around for historical purposes

Concept ACK for updating. The original BIP118 proposal will remain available via git history, so no information is lost by updating it. Noinput as its own separate segwit version never had any traction AFAICT---I think almost everyone has wanted this to be either a part of a larger soft fork or an add-on soft fork.

That was the rationale for proposing an update instead of leaving noinput lingering. noinput alone was lacking the details to make it work within taproot, and the update adds all the necessary details to make the proposal compatible with taproot. Given the timing of the taproot and the noinput proposal we tried to make the two independent by not adding any dependencies between them.

With taproot making good progress, and the shrinking probability of a raw noinput proposal without taproot integration making progress, it is desirable imho to replace the raw proposal with the integrated one.

poke @ajtowns @cdecker

It might be worth adding a section about recommendations for wallet devs on how to handle if funds are received to an address that has BIP 118 pub key, I would expect that they should immediately spend it to another address if they already given out a SIGHASH_ANYPREVOUTANYSCRIPT signature and do not want the newly received funds spendable by the parties with the signature.

It might be worth adding a section about recommendations for wallet devs on how to handle if funds are received to an address that has BIP 118 pub key, I would expect that they should immediately spend it to another address if they already given out a SIGHASH_ANYPREVOUTANYSCRIPT signature and do not want the newly received funds spendable by the parties with the signature.

Our usual approach to this is "if you don't know how to handle ANYPREVOUT scripts you should not signal support for BIP118", and the wallets sending to you should never use BIP118". Having consumer wallets that do not require BIP118 support handle it is undesirable, and imho any guidance on how to handle them might give the contrary impression.

What is the status here? Can we merge it?

I just want to say that it is horribly confusing to have a standards document be completely rewritten to describe a totally different idea. This is a very atypical thing to do. If it's a new approach, please make a new BIP.

It's not really new, it just adds the details for Taproot and addresses some concerns that have been raised during the discussion regarding replay-attacks. IMHO this is exactly the goal of updates to the BIPs.

Indeed, it's not like it was even Proposed yet, just a Draft.

I'll soon have a bit more time to dig into BIP 118, and I have spoken with a number of people willing to join a review club to work through the proposal. If anybody is interested in joining a public discussion we can set something up :-)

But don't want to distract from the Taproot effort, which deserves all the attention it can get, and is the basis for anyprevout.

I think now is a good time to revive public discussion efforts?

Rebased, removed "draft" marker on PR, so should be okay for ACKs and eventual merge

There's a lot of style changes mixed in with contextual changes so it's hard to determine what is a style fix vs what is new content. It would be helpful if commit number 1 was a pure style tweak followed by the actual changes in subsequent commit(s).

There's a lot of style changes mixed in with contextual changes so it's hard to determine what is a style fix vs what is new content.

It's pretty much entirely new content, I don't think there's much you can extract as just a style fix?

Is there a current reference implementation?

Trying to figure out presently if the BIP is trying to imply a tap leaf with 0x01 CHECKSIG has the effect of being equivalent to <0x01 || internal key> checksig or not (it seems implied by the bip language but not explicit enough imo).

Is there a current reference implementation?

There's a reference implementation at https://github.com/ajtowns/bitcoin/tree/202101-anyprevout but it's not current both in that it's missing at least the change to have ANYPREVOUTANYSCRIPT not commit to the amount, is some months out of date, and may be buggy.

Trying to figure out presently if the BIP is trying to imply a tap leaf with 0x01 CHECKSIG has the effect of being equivalent to <0x01 || internal key> checksig or not (it seems implied by the bip language but not explicit enough imo).

I'm not sure what's unclear about:

To convert a 1-byte BIP 118 public key for use with BIP 340, simply use the 32-byte taproot internal key, p, as defined in BIP 341. To convert a 33-byte BIP 118 public key for use with BIP 340, simply remove the 0x01 prefix and use the remaining 32 bytes.

If your internal key is G, ie, "79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798" then doing either 210179BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798AC (push the 32-byte key prefixed by 0x01, then CHECKSIG) or 51AC (OP_1 and CHECKSIG) will result in a checksig operation against "G" as the BIP118 public key.

I'm not in love with the 0x01 to mean an anyprevout key based on the internal PK.

I think that this sort of mechanism is more generally useful (e.g., I imagine the script USE_INTERNAL CHECKSIGVERIFY SHA256 <H> EQUAL could be useful without APO because bip341 commits to the spend script).

I also think that 0x01 makes it so that there is a public key which is "computable" using script math, which is kind of weird (or at least merits consideration)? I mean I suppose <something> sha256 also is a 32 byte value, but conceivably finding d. dG == sha256(x) is hard?

I think that this sort of mechanism is more generally useful (e.g., I imagine the script USE_INTERNAL CHECKSIGVERIFY SHA256 <H> EQUAL could be useful without APO because bip341 commits to the spend script).

You could define the single-byte pubkey "0x81" (ie the value OP_1NEGATE pushes onto the stack) to be treated as the internal public key with the bip342 signature digest and get that sort of behaviour. The key and/or signature needs to encode what digest is going to be used however; but if you're happy for the signature to encode the digest, then just using the APO capable OP_1 with a non-ANYPREVOUT signature works.

I also think that 0x01 makes it so that there is a public key which is "computable" using script math, which is kind of weird (or at least merits consideration)? I mean I suppose <something> sha256 also is a 32 byte value, but conceivably finding d. dG == sha256(x) is hard?

CAT would also make public keys "computable" in this sense, except moreso since there would actually be multiple keys you could compute. But you can already write scripts that simply accept the pubkey as an input which is more flexible, and already in use since that's how P2PKH works.

@cdecker Think this is mergable? Even if not perfect, it can continue to be revised...

In general, one thing that strikes me is that when anyprevout is used for eltoo you're generally doing a script like:

IF
    10 CSV DROP
    1::musigkey(As,Bs) CHECKSIG
ELSE
    <S+1> CLTV DROP
   1::musigkey(Au,Bu) CHECKSIG
ENDIF

This means that you're overloading the CLTV clause, which means it's impossible to use Eltoo and use a absolute lock time, it also means you have to use fewer than a billion sequences, and if you pick a random # to mask how many payments you've done / pick random gaps let's say that reduces your numbers in half. That may be enough, but is still relatively limited. There is also the issue that multiple inputs cannot be combined into a transaction if they have signed on different locktimes.

Since Eltoo is the primary motivation for ANYPREVOUT, it's worth making sure we have all the parts we'd need bundled together to see it be successful.

A few options come to mind that might be desirable in order to better serve the eltoo usecase

1. Define a new CSV type (e.g. define (1<<31 && 1<<30) as being dedicated to eltoo sequences). This has the benefit of giving a per input sequence, but the drawback of using a CSV bit. Because there's only 1 CSV per input, this technique cannot be used with a sequence tag.
2. CSFS -- it would be possible to take a signature from stack for an arbitrary higher number, e.g.:

IF
    10 CSV DROP
    1::musigkey(As,Bs) CHECKSIG
ELSE
    DUP musigkey(Aseq, BSeq) CSFSV <S+1> GTE VERIFY
   1::musigkey(Au,Bu) CHECKSIG
ENDIF

Then, posession of a higher signed sequence would allow for the use of the update path. However, the downside is that there would be no guarantee that the new state provided for update would be higher than the past one without a more advanced covenant. 3) Sequenced Signature: It could be set up such that ANYPREVOUT keys are tagged with a N byte sequence (instead of 1), and a part of the process of signature verification includes hashing a sequence on the signature itself.

E.g.

IF
    10 CSV DROP
    1::musigkey(As,Bs) CHECKSIG
ELSE
   <N>::musigkey(Au,Bu) CHECKSIG
ENDIF

To satisfy this clause, a signature <N+1>::S would be required. When validating the signature S, the APO digest would have to include the value <N+1>. It is non cryptographically checked that N+1 > N. 5) Similar to 3, but look at more values off the stack. This is also OK, but violates the principle of not making opcodes take variable numbers of things off the stack. Verify semantics on the extra data fields could ameliorate this concern, and it might make sense to do it that way. 4) Something in the Annex: It would also be possible to define a new generic place for lock times in the annex (to permit dual height/time relative/absolute, all per input. The pro of this approach is that it would be solving an outstanding problem for script that we want to solve anyways, the downside is that the Annex is totally undefined presently so it's unclear that this is an appropriate use for it. 5) Do Nothing :)

Overall I'm somewhat partial to option 3 as it seems to be closest to making ANYPREVOUT more precisely designed to support Eltoo. It would also be possible to make it such that if the tag N=1, then the behavior is identical to the proposal currently.

It occurs to me this might be the wrong venue to discuss the above as this is larger change outside the changes to the BIP outstanding, so I will move discussion to the mailing list.

@cdecker Think this is mergable? Even if not perfect, it can continue to be revised...

I think it is excellent, let's ship it 🤓 We can do fine-tuning and corrections in separate PRs, agreed