Allow Runestone tags to be placed in witness / taproot annex

[joshdoman]

I've been thinking about basic improvements that can be made to the Runestone scripting language, which I expect will become more important over time as the number of even tags expands and it becomes more common for large Runestones to be made.

First and foremost, I think ord should consider adding an even tag, which indicates that additional tags are in a taproot or P2WSH witness envelope.

There are two problems with requiring a Runestone to be placed in an OP_RETURN as it stands today:

1. If the Runestone exceeds approximately 133 bytes, it becomes more cost effective to inscribe some data in a witness envelope to benefit from the witness discount (like the details of an etching).
2. If the Runestone exceeds 80 bytes, the transaction can't pass Bitcoin Core mempool standardness rules. It could still be submitted to a private mempool, but this can be expensive, making 80 bytes effectively the limit. ord already has a number of runestone_size test cases that exceed 80 bytes if a new tag is added, and one test already exceeds the limit.

Bitcoin Core recently introduced support for ephemeral anchors and package relay, which would make it quite easy for users to submit a package of commit and reveal transactions, where the Runestone is in the witness of the latter.

Potential Cost Savings

For maximum efficiency, I'd recommend the data be allowed to be put in a taproot witness envelope or a P2WSH envelope, with a pointer to the tx envelope number. The latter would cut out the 33 byte control block in the witness, which is unnecessary if you only need a single script path. You could even remove the signature if you don't require an OP_RETURN and don't mind others placing tags there. If something like OP_CTV eventually gets implemented, you could specify that there's no OP_RETURN or that the OP_RETURN contains nothing.

By my calculation, in a purely taproot package of transactions with 2 signatures, the Runestone would need to be ~177 bytes for this to make sense. To move a Runestone to a witness, you need 3 additional pieces of data:

1. An even Witness tag that indicates that Runestone tags are in a witness envelope (the tag followed by the envelope index, ~2vb)
2. A witness envelope (3 vb)
3. The equivalent of a transaction spending to a taproot output and spending from a taproot output using a script path with a single signature (128 vb).
   3a. For reference, a script path spend with a single signature has 68 bytes of additional witness data, or 17 vb, vs a taproot key path spend (1 byte for script length, 34 bytes for the script, and 33 bytes for the control block.
   3b. Meanwhile, a 1-input-1-output taproot key path spend is 111 vb.

Adding them up, you have 133 vb of additional data. This would imply that the Runestone itself would need to be ~177 bytes of data before it becomes cost effective to move it to the witness (133 + 177 / 4 = 177). If you want, you could save 7vb by using a P2WSH commitment output, which would get rid of the control block, but add 1 vb for the ECDSA signature. This would imply you'd add 126 vb of additional data and need 168 bytes of tag-related data before it makes sense to put it in a witness envelope.

The real cost savings come when you remove the need for a signature. With a P2WSH commitment output, you would need nothing but the witness envelope, getting rid of the signature and the script altogether. This would save 105 bytes of witness data, or 26.25 vb, reducing the amount of additional data to 100 vb, which would require 133 bytes of tag-related data to breakeven.

This would be ideal for use cases where you don't need a Runestone in the OP_RETURN of the reveal transaction, and you don't care if there is one. This could include messages authorizing an asset to be released from a vault, or the details of an etching, which was made in the commitment transaction.

Use Cases for Large Runestones

This could provide meaningful cost savings, especially in etchings with many tags, or with tags that reference large values. If fee rates rise significantly, cost efficient tagging could mitigate the impact on use cases that require frequent etchings, like an event organizer creating multiple classes of tickets for multiple recurring events, and use cases where there may be a lower willingness to etch, like a commemorative airdrop to attendees of an event, which may or may not be transferable.

In particular, I think this could be particularly useful for #4218 by making it more cost effective for rune holders to vote on governance proposals. Users could sign messages offchain, proving they own a UTXO through a virtual deterministic self-spend no-fee transaction that includes the message they want to sign. Only the signatures and unlocking scripts authorizing the virtual transaction and the message itself would need to be placed in the envelope.

Signatures could then be aggregated and broadcast all at once in a transaction. There could even be a tip to the broadcaster, in the form of a rune, or in the case of a vault sending out an asset, it could be paid for by the recipient. With a way to sign arbitrary messages proving ownership of any UTXO, the possibilities become endless.

A more near-term compelling argument, though, is to ensure users can get transactions relayed and included in blocks, even if the runestone exceeds 80 bytes. If core devs saw that users were doing this, there would be a stronger case for changing relay policies and lifting the OP_RETURN limit.

Concluding Thoughts

Even if this isn't a pressing issue now, it could become one, especially if ord starts adding new tags, which make it hard for certain transactions to get relayed. Many new types of features can then be safely added to ord, like transfiguration / vaulting, unvaulting, changes to vault governance, freezing, dynamic minting, etc.

@casey How would you feel about adding this to the roadmap? It doesn't need to be added imminently, and perhaps it shouldn't be until users complain, but it might be good to start thinking about. At a protocol level, I don't think it would be too difficult to do.

The biggest challenge I see is implementing this safely. If marketplaces and wallets don't upgrade their version of ord, users might buy a rune in one wallet or marketplace that isn't supported elsewhere. To mitigate this, ord might require runes to opt in by adding the Witness tag in the etching. Additionally, ord could apply this retroactively to all runes etched with a turbo flag, allowing the feature to be used for runes immediately while encouraging new runes to be made explicitly compatible, even if some wallets don’t yet support it.

[casey]

Here's my thinking:

• Regarding the 80 byte OP_RETURN standardness limit, I actually do not think that this is something we should work around. Many miners already accept nonstandard transactions, and Peter Todd's Libre Relay fork of Bitcoin Core can be used to submit oversize OP_RETURNs without needing to send them to a specific miner. It is in the rational self-interest of miners to accept transactions with oversize OP_RETURNS, and I think eventually, Bitcoin Core will lift the standardness limit, so we just shouldn't worry about it.

• The space savings is nice, but it comes at the cost of a high degree of protocol complexity. Additionally, there is little demand for this at the moment. I myself made one transaction with a really large runestone which had to be submitted directly to a miner, and I think that there are a few others, but they are rare.

• If we put data anywhere, this should ideally go in the taproot signature annex. The signature annex is covered by signatures, so doesn't require a commit/reveal, and receives the witness discount. Attempts to standardize a format for unstructured data in the annex have kind of stalled out. (See Store inscriptions in taproot signature annex #2405.) But in this case I think we should just wait. If you wanted to champion carving out a standardness exception for unstructured annex data, I think that would be a worthy cause, and would allow this to come closer to being actionable.

So I think I would change this issue to "allow edicts to be placed in the taproot signature annex", since edicts are what winds up being large. A runestone would have a new flag (there is a flags field which is an even tag, and if there are unrecognized flags, it is treated as an unknown even field) which indicates that edicts are present in the signature annex. It then looks for a signature annex with edicts and processes the transaction accordingly.

And I think a prerequisite for that would to be worth doing would be the ability to construct a transaction with a signature annex with unstructured data, which can be broadcast and mined without needing to collude with a miner. I think if Libre Relay supported it, that would be good enough.

[joshdoman]

And I think a prerequisite for that would to be worth doing would be the ability to construct a transaction with a signature annex with unstructured data, which can be broadcast and mined without needing to collude with a miner. I think if Libre Relay supported it, that would be good enough.

I think the proposal to put data in the taproot annex is a fantastic one. I had no idea such a thing even existed, until you mentioned it.

What will it take for Core Devs to preemptively soft-fork in functionality for arbitrary data to be safely placed in the annex? I really like the TLV proposal you suggested in #4229 , but it seems to me that there is little incentive on Core's part, or on the part of regular users, to build this functionality. Might it make sense for ord devs to create a BIP or implement your proposal? Anyone can be a Core dev, technically, if they can create a PR.

That being said, many people, rightfully or not, hate the idea of 1s and 0s existing onchain which they do not consider meaningful, and which they do not value. Never mind the fact that data in the taproot annex could meaningfully reduce congestion, and thereby reduce fees. People still tend to despise non-bitcoin data existing onchain.

This suggests to me that nothing short of a "hack," where some developer goes ahead and builds a metaprotocol that uses the annex, or that could use the annex, is the only way to force the issue. I don't like the idea of force, so that developer will never be me, but I would hope that this would not be necessary. I just struggle to see a path right now, given how contentious soft forks can be, where this happens without such a "hack."

I think this was part of my motivation for #4229 . If a unified protocol gets built, where data can live, for instance, in an OP_RETURN OR within a taproot annex, the protocol could go live, and the problem would be made front-and-center, even if users aren't actively submitting transactions with data in the annex. The fact that they could might be enough to place the issue front and center for discussion, with minimal risk to Bitcoin or the protocol if the annex is later divided up in an incompatible way. Because the OP_RETURN remains a fallback.

Anyway, I digress.

Thank you for the feedback. As you say, the question of putting Runestone data in the witness can be addressed later, when users start to complain.

[petertodd]

If you wanted to champion carving out a standardness exception for unstructured annex data, I think that would be a worthy cause, and would allow this to come closer to being actionable.

FYI, this is something I'd be happy to add to Libre Relay if someone wants to pay for my time. I'd suggest that the exception be for any annex data that starts with the byte 0xFF, to allow for future soft-forks to also use annex data for consensus reasons by starting the annex data with a different (lower) tag byte. I'm sure we could get MARA at least to mine such transactions.

Technically speaking this shouldn't be a difficult thing to add to Core. Although it'll likely take a non-trival amount of work to implement proper tests for it (Core is very well tested!).

[joshdoman]

FYI, this is something I'd be happy to add to Libre Relay if someone wants to pay for my time. I'd suggest that the exception be for any annex data that starts with the byte 0xFF, to allow for future soft-forks to also use annex data for consensus reasons by starting the annex data with a different (lower) tag byte. I'm sure we could get MARA at least to mine such transactions.

@petertodd Interesting. A byte flag makes a lot of sense. One question: Do you think there's a scenario where it makes sense for consensus-critical and non-consensus-critical data to live in the annex?

For context, @casey suggested that data be placed in the annex using type-length-value encoding (TLV). I thought that was an interesting idea because it could conceivably be used to let consensus-critical data live alongside non-consensus-critical data in the annex. That would let users take advantage of a future soft fork while still being able to place metaprotocol data in the same annex.

[petertodd]

Do you think there's a scenario where it makes sense for consensus-critical and non-consensus-critical data to live in the annex?

There definitely could be. For example my OP_Expire proposal would probably be implemented via an expiration field in the annex, and you can probably come up with some auction protocol or something like that where expiration would be useful as well as annex data at the same time.

TLV encoding might be a good idea. But the thing is, if the consensus tags are limited to 256 in total (perfectly reasonable!), the last tag, 0xFF, can be reserved for "ignore everything else" --- you don't need to actually specify the length in that case.

[joshdoman]

@casey I thought of another reason for why it could make sense to place Runestone tags in the taproot annex, beyond cost savings.

I think it would make it possible for users to create sub-balance rune sell offers in a single PSBT transaction. This isn't possible today. With the sighash flags allowed under current consensus rules, users can only sign either a single output or they must sign all outputs. Since users can only split their balance via an OP_RETURN output under the current runes protocol, it is impossible to create a sub-balance rune sell offer without creating two transactions.

If, however, Runestone tags could be placed in the annex, a user could sign an input using SIGHASH_SINGLE | ANYONECANPAY, and the tags in the annex could split their balance, assigning some to the signed UTXO and leaving the rest to be purchased by the buyer.

This would be a meaningful UX improvement and would reduce the onchain footprint and cost of making offers. Designing this would require some thought, though. For example, should Runestone tags in the annex be processed before tags in the OP_RETURN? You may also need a special type of edict that assigns runes to the UTXO signed by the input. Will leave this and other details for future discussion.

[casey]

@joshdoman I think I've had a similar thought, and I think you're right.

@petertodd One thing that would be nice about a TLV encoding is that different non-consensus metaprotocols and future consensus transaction metadata could all coexist in the same annex.

It's really unfortunate that efforts to define a TLV format for the taproot annex kind of stalled out.

I think it's probably too ambitious for us to define a TLV format, not least of which because whatever we come up with, it's not certain that a future soft fork giving meaning to the annex would use the same thing, so probably best to just define something reasonable.

@petertodd I think maybe first byte is 0x00 to indicate that the rest of the data has no consensus meaning might be slightly cleaner, since it doesn't assume that there are at most 255 structured tag, structured tags just start at 0x01. What do you think?

How much do you think it would cost for you to add it to libre relay?

[petertodd]

@casey

One thing that would be nice about a TLV encoding is that different non-consensus metaprotocols and future consensus transaction metadata could all coexist in the same annex.

In the scheme I proposed above they certainly can co-exist. It's just that any TLV encoding for consensus would be entirely separate from however other applications choose to use the annex. Of course, that does mean that future applications who want to simultanously use the annex for consensus and non-consensus uses would need to be upgraded to take the consensus encoding into account. But we have no way to control how that gets defined now, so might as well do something extremely simple.

I think maybe first byte is 0x00 to indicate that the rest of the data has no consensus meaning might be slightly cleaner, since it doesn't assume that there are at most 255 structured tag, structured tags just start at 0x01. What do you think?

Having more than 255 consensus meaningful tags seems absurd. I just can't see any way that we'd ever need that many given the limited number of features that could possibly be added to Bitcoin.

How much do you think it would cost for you to add it to libre relay?

Rough guess this is ~10 hours of work all in. So let's say $1500

[joshdoman]

In the scheme I proposed above they certainly can co-exist. It's just that any TLV encoding for consensus would be entirely separate from however other applications choose to use the annex. Of course, that does mean that future applications who want to simultanously use the annex for consensus and non-consensus uses would need to be upgraded to take the consensus encoding into account.

I think that makes sense. The need for a second protocol upgrade is unfortunate but probably the most realistic outcome.

@petertodd Before we implement, I'd like to throw out another alternative. If 255 tags is way more than we'll ever need for consensus, I imagine that 128 tags is more than enough as well.

If so, would it make sense to define tags that start with a leading bit of 1 as non-consensus, and leave the first 128 tags for Core?

This would be slightly more byte efficient, because non-consensus protocols could use the remaining 7 bits for application-specific data (ex: protocol flags, basic TLV, etc.)

This would imply that tags at or above 0x80 are "ignore everything else."

[petertodd]

@joshdoman Yes, that'd be similar to the Lightning wire protocol's "it's ok to be odd" rule for tags.

That said, note that I didn't actually propose a TLV scheme; I haven't said anything about length! Rather, I proposed a forwards-compatible way to mark the rest of the annex data as non-consensus. Applications could then use it in any way they wanted, be it their own TLV scheme, or something totally different.

If we really want multiple arbitrary applications to share annex space --- eg in a coinjoin --- it isn't going to be easy... we'll need something more like randomly chosen 128-bit UUIDs to avoid collisions. And it'd be quite hard to define efficient schemes where there's no risk of security issues from different data having different meanings. Much easier to just stick to "consensus meanings" and a single non-consensus meaning for annex space.

[casey]

In the scheme I proposed above they certainly can co-exist.

I meant multiple non-consensus uses of the annex.

Having more than 255 consensus meaningful tags seems absurd.

I agree, however I think it's still a weak argument in favor of 0x00. Also, in almost every varint encoding that a future structured annex encoding might use, 0x00 is the representation of the integer 0, whereas 0xFF is often not a valid integer by itself, which makes future consensus logic easier. I.e., you just have to decode the next varint, and if it's 0 you stop.

we'll need something more like randomly chosen 128-bit UUIDs to avoid collisions

In practice, I think much smaller identifiers would probably work, since people would intentionally choose identifiers to avoid collisions.

@joostjager wrote a PR for making unstructured annexes standard. It has some good bits, mainly that all inputs must commit to an annex for the transaction to be standard, and that a standard annex may either be empty (so all inputs can commit to an annex for minimum cost) or start with 0x00 indicating an unstructured annex. There's also a size limitation, but that defeats the purpose of using the witness for us, since we'd want it both for inscriptions and runes.

[petertodd]

I meant multiple non-consensus uses of the annex.

Sure, you can do that with that I'm proposing too. Those uses just need to come up with their own protocol if they want to interoperate with each other.

There's a lot of things that would like to put data in annexes. As you know, Lightning channels could make good use of this for backing up or publishing certain types of data. Those use-cases probably aren't going to care about whatever we come up with.

I agree, however I think it's still a weak argument in favor of 0x00. Also, in almost every varint encoding that a future structured annex encoding might use, 0x00 is the representation of the integer 0, whereas 0xFF is often not a valid integer by itself, which makes future consensus logic easier. I.e., you just have to decode the next varint, and if it's 0 you stop.

Fair enough. Let's do 0x00. That'd be compatible with delta encoding too, modulo the minor limitation that it would make the 0x00 tag invalid.

@joostjager wrote a bitcoin/bitcoin#27926 for making unstructured annexes standard. It has some good bits, mainly that all inputs must commit to an annex for the transaction to be standard, and that a standard annex may either be empty (so all inputs can commit to an annex for minimum cost) or start with 0x00 indicating an unstructured annex. There's also a size limitation, but that defeats the purpose of using the witness for us, since we'd want it both for inscriptions and runes.

Requiring all inputs to commit to the annex (if non-empty) is a decent idea. But we probably want an exception for keyless outputs at least (bc1pfeessrawgf).

[casey]

@petertodd Sounds good! I just followed up via email to nail down the details.

[joshdoman]

@casey I think there's another fairly interesting use case for the annex: expiring sell offers.

If Runestone tags were allowed in the annex, you could create a PSBT sell offer that transfers all runes in an input to the output signed with SINGLE|ANYONECANPAY, but only after a specific block height.

The implication is that anyone can buy those runes if they can get the transaction mined before the sell offer expires. It's potentially risky, especially if sellers collude with miners to exclude the transaction until expiry, but buyers could price in this risk and avoid offers with imminent expirations.

What's nice about this approach is that you can get most of the benefits of @petertodd's OP_Expire proposal without the need for a soft fork.

There are multiple ways to implement timelocked / expiring edicts, but I leave those details for another time.