Stacks transaction replay on Bitcoin reorg

[obycode]

We have open issues for the miner (#4313) and signer (#4913) to implement this behavior. From the issue:

Under Nakamoto, sortitions with a valid winner on the Bitcoin blockchain will yield a TenureChange that allows a new miner to produce blocks that the signers will sign, but a Bitcoin reorg can force the Stacks blockchain to reorganize because a Bitcoin block with a valid sortition can be orphaned itself, meaning that the orphaned tenures are now invalid. This ticket is to add a feature to the default Miner binary to have the miner replay transactions that were orphaned by a Bitcoin reorg to be included within the next tenure.

This ticket does not encompass including any kind of analysis on the validity of transactions, only prioritizing the replay of the transactions that were previously confirmed by a now invalid tenure.

I'm opening this discussion to provide a place for Stacks core developers and Stacks application builders to discuss:

• What are end goals of this feature?
• What requirements does your app have?

We need to clarify these points, and clarify the limitations of what is possible, before beginning any design or implementation, in the hopes of avoiding (1) building something that doesn't solve anyone's problems and (2) building something that is more complicated than necessary.

[jcnelson]

I 100% agree that altering consensus rules like this needs to come from a place of understanding which parties want this and which stakeholders are affected. That said, I'll limit this to summarizing what I've shared elsewhere about what is and is not possible.

Today, Stacks inherits the security budget of Bitcoin. A Bitcoin fork will orphan the Stacks tenures anchored to the orphaned Bitcoin blocks. This was stated in SIP-015 and found to be acceptable via its activation.

SIP-015 described a direction of future development whereby Stackers and miners could make an effort to preserve Stacks transactions across Bitcoin forks. Transactions in orphaned tenures could be re-mined in the same relative order on the now-canonical Bitcoin fork. Transactions which remain valid on the new Bitcoin fork would become part of the new tenures, before any other Stacks transactions get mined. Achieving this is possible since the Stackers (and their nodes) which signed off on the orphaned tenures will retain copies of them, and will thus be able to (1) publish them for miners to discover, and (2) require miners to attempt to re-mine them in the same order in the blocks they produce as a condition of accepting their block proposals.

What transactions can be re-mined? SIP-015 calls for re-mining Stacks transactions that are causally independent of orphaned Bitcoin state, since it won't matter which Bitcoin fork their tenure is in. But what about the causally-dependent Stacks transactions?

Stacks transactions can be causally dependent on Bitcoin state in an arbitrary number of ways. Not only are they made causally-dependent by employing get-burn-block-info?, burn-block-height, or other Clarity built-ins during their execution that provides data from the Bitcoin chain, but also they are made causally-dependent if any prior causally-dependent transaction creates or alters state that the given transaction depends on. Any attempt to identify causally-dependent transactions would require Stacks to implement a form of taint-tracking, whereby causally-dependent transactions become tainted by either directly accessing Bitcoin state via a Clarity built-in, or by accessing state created by tainted transactions. Implementing the recommendation in SIP-015 would be tantamount to associating each chain state record with the tenure in which it was created, and requiring miners to replay orphaned transactions whose accessed state remains linked to a canonical tenure (i.e. are untainted by the orphaned Bitcoin blocks).

Before you read the next paragraphs, remember I'm only talking about what's possible. I am NOT advocating for actually doing this without some very compelling, very publicly-discussed reasons.

This is not the limit of what is possible, however, when it comes to preserving Stacks chain history across a Bitcoin fork. Today, signers already maintain a linearized history of accepted block proposals, and with it, a linearized history of observed Bitcoin blocks. With this information, it is possible to maintain a linearized history of Stacks transactions that "passes through" orphaned Bitcoin blocks, such that tenure N+1's parent may be anchored to a sibling of tenure N+1's Bitcoin block, instead of an ancestor Bitcoin block.

For example, suppose Bitcoin blocks B, B+1, B+1', and B+2 are mined in that order, as observed by signers. Suppose B+2 is the child of B+1, and B+1' is an orphaned sibling of B+1, and both B+1 and B+1' are children of B. Finally, suppose each of these Bitcoin blocks have associated non-empty Stacks tenures.

Signers observe the linearized history of produced Bitcoin blocks as B, B+1', B+1, and B+2. In doing so, they retain copies of these Bitcoin blocks for posterity. Stacks nodes retain copies of all sibling Bitcoin blocks by fetching them from signers, so that all times, all Bitcoin blocks which have Stacks tenures are available to all Stacks nodes. In addition, Stacks nodes store and replicate the signer-given Bitcoin block production order, so the linearized tenure history is always available to all nodes.

When Bitcoin block B+1 is mined, the winning Stacks miner would build atop the tenure produced B+1' instead of B. In other words, the signers treat the tenure in B+1' as the canonical Stacks tip which must be built upon, even though B+1 is its canonical sibling. This is possible because signers (not Bitcoin) would now be deciding what the canonical ordering of tenures is, and that ordering is simply the observed arrival order.

When a Stacks node synchronizes blocks, it asks its Bitcoin node for not only the canonical Bitcoin blocks, but also its Stacks peers for any non-canonical Bitcoin blocks which have tenures. The synchronizing node validates each non-canonical Bitcoin block via the usual way (e.g. it checks the timestamp and chain work to assess that it is a plausible orphan). Its peers provide it with the linearized order of Bitcoin blocks in addition to the Stacks blocks themselves, so the synchronizing node can fetch, validate, and apply tenures in the right order and ultimately reach the Stacks chain tip.

What's possible with this alternative approach? Compared to SIP-015, this approach would mean that no Stacks transaction is ever tainted -- all Stacks blocks are causally consistent with the history Bitcoin blocks that produced their tenures. However, this approach would also mean that Stacks history is causally inconsistent with the canonical Bitcoin chain. For example, suppose Alice redeems her sBTC for BTC, and that BTC transaction was mined only in Bitcoin block B+1' but not B+1 (or B+2, or anywhere else in the canonical Bitcoin fork). The Stacks history would indicate that Alice's sBTC was redeemed, but Alice would not have her BTC. As another example, suppose Bob sends a Stacks-on-BTC stack-stx, which gets mined in B+1'. Then, Bob's STX are stacked in the Stacks history, but the record of his stack-stx is not present in the Bitcoin chain.

It's possible to use both the SIP-015 approach and this alternative approach on a case-by-case basis. The choice to even consider state in the blockchain as tainted can be made on a per-record basis. Some records could be treated as "taintable" at the discretion of the smart contract, in which case, the effects of their storage would only materialize on tenures which are part of the canonical Bitcoin chain. Other records would be treated as "untaintable," in which case, the effects of their storage would be preserved regardless.

This would allow us to surgically address the causal inconsistency problem with Alice's sBTC above, while preserving Bob's stack-stx in the canonical Stacks history. The code branch which destroys Alice's sBTC in reaction to the BTC redemption transaction getting mined in Bitcoin block B+1' would be marked taintable in the sBTC contract's code body, meaning that even though the redemption completed in B+1''s tenure, it would still be treated as pending in B+1's and B+2's tenures. This is because the chain state records produced in the redemption completion branch would be (1) marked as taintable in the DB at sBTC's discretion, and (2) associated with tenures that are not part of the canonical Bitcoin chain, meaning that the system could consider them as having not happened at all. We would treat writes from Stacks-on-BTC transactions like stack-stx as untaintable, so they materialize regardless of whether or not the Bitcoin block which contains them is ultimately orphaned.

---

While the above provides a sketch of what Stacks transactions (and associated chain state) can be preserved across Bitcoin forks (and how we might do this), it has insurmountable limits. Specifically, Stacks cannot control what Bitcoin miners do. In the sBTC example, Alice's peg-out fulfillment will never be considered finalized by 3rd parties until the Bitcoin block which contains it is sufficiently confirmed. There is nothing we can do about this, since Bitcoin can fork and we cannot prevent it. So, Alice is still going to wait for ~1 hour before Charlie will accept her BTC, and Charlie will insist on this. It also means that no matter what we do, the sBTC signers would need to identify the case where Alice's BTC redemption transaction gets orphaned, and re-submit the BTC redemption transaction. It would possibly be a different transaction altogether, from a different UTXO, since sBTC signers may have produced a different history of BTC transactions in the interim. So, some additional fork-awareness will be needed for sBTC regardless of what the Stacks blockchain does.

[aldur]

Thank you for opening this!

I think about the end goals of this feature from a product/UX perspective related to transaction finality.

To provide good UX, transactions should "finalise"¹ as soon as possible, ideally as soon as a new Bitcoin block gets mined.

Transaction replay could help in this direction. In the event of a Bitcoin fork, Stacks transactions that are now orphaned would be replayed -- possibly with higher priority -- and re-make their way into the canonical chain. For the sake of simplicity, we can also suppose they'd make it back within a single Bitcoin block/Stacks tenure.

Unfortunately, some replayed transactions might fail -- for instance, because they casually depend on the state of a Bitcoin fork that is now not-canonical.

This raises a problem: even with transaction replay, a Stacks transaction will be probabilistically final after enough Bitcoin blocks (e.g., the usual six).

Needless to say, this makes the UX suboptimal. Exchanges might need to play it safe and wait six Bitcoin blocks before allowing STX withdrawals, and so on.

Can we do better? I think we can, as follows.

As described in the SIP, transaction replay can guarantee that all transactions that remain valid across the Bitcoin fork will be re-mined (in the same order).

If users could tell in advance which transactions will remain valid across the Bitcoin fork, then they could:

1. Require 1 Bitcoin block to consider "final" any transactions that will remain valid across Bitcoin forks.
2. Require 6 Bitcoin blocks before considering any other transaction "final". This includes all transactions (transitively) casually dependent on Bitcoin state.

Such approach would optimise UX, allowing fast finality for the subset of transactions that can benefit from it. It also strikes a good trade-off between effort and impact (value to users), with respect to other solutions (e.g., modifying the consensus protocol to allow the replay of now-invalid transactions).

The problem of understanding whether a transaction will remain valid across Bitcoin blocks is non-trivial, but tractable (it might share the problem space with taint analysis in databases and similar).

If we can solve such problem, then we "productise" it by serving an API to users that, given a transaction (hash), tells the required number of Bitcoin blocks before finality. An upside of such strategy is that the API could be even developed outside stacks-core, similarly to how Hiro APIs now provide fine-grained fee estimate for transactions.

Footnotes

1. Loosely speaking, a Stacks transaction is final if, regardless of forks on Stacks or Bitcoin, it is there to stay within Stacks chain history. ↩