Introducing the Strata bridge

Update! This post was updated on December 9, 2024 to better reflect the collaborative nature of research leading to the Strata bridge.

Alpen Labs is developing a bitcoin bridge to its platform, Strata. Strata is a programmable layer that ensures parity with bitcoin: 1 BTC on Strata is backed by 1 BTC on bitcoin, and withdrawals can be done with minimal trust assumptions.

The Strata bridge uses design approaches from the BitVM2 paper by Robin Linus and collaborators, but includes many optimizations and other tricks that use cutting-edge research to ensure a robust and efficient product. Alpen is a participant in the BitVM Alliance, an informal group of researchers and developers working to improve on the original BitVM2 bridge design, coordinate on implementation, and bring safe bridges to production. The collaboration with the Alliance and broader open-source community in the BitVM repository provides a core foundation for the Strata bridge. We’re thrilled at the opportunity to contribute to this work, and are grateful to Alliance participants for curating many ideas and inspiring much research through collaboration.

In this post, we’ll show how the Strata bridge works, how it relates to other designs, and why it’s useful and important for the ecosystem. You don’t need advanced knowledge about bitcoin or other bridge concepts, but we do assume familiarity with basic digital asset concepts (like a blockchain and a transaction).

Background

Blockchains as state machines

Blockchains are replicated state machines. Block producers create new blocks and relay these to the blockchain network. Full nodes in the blockchain network locally execute a deterministic state transition function (STF) and update to the new state accordingly.

STF(current_state, block) = new_state

A block contains an ordered set of transactions along with some header metadata. The STF is a deterministic program that checks validity of a proposed block and transitions the current state to a new state.

In bitcoin, the state is the UTXO set: a collection of unspent transaction outputs that are valid. A state transition results from transactions consuming existing UTXOs and generating new ones. In Ethereum the state is the Merkle Patricia Trie: a key-value store that maps account addresses to their respective account states.

If there are multiple competing branches of the blockchain — each constructed with valid STFs — a node will use a deterministic fork choice rule (FCR) to determine the canonical chain. This is essential for ensuring global consensus across the network on a consistent latest state.

In bitcoin, the FCR ensures that the chain with the most cumulative work is the canonical chain at any given time. In Ethereum 2.0, the FCR is based on the total stake or attestations supporting the chain.

Sovereign rollups

A sovereign rollup is a blockchain that uses another blockchain ("base layer") for data availability and consensus. In contrast to a smart contract rollup, whose STF and FCR is defined by a smart contract on the base layer, the STF and FCR of a sovereign rollup is defined by the rollup’s full node and is verified client-side.

Rollup block producers put block data on the base layer, which allows nodes to verify the rollup’s STF and FCR to get global consensus on the latest state of the rollup. Note that the rollup nodes must also verify the base layer’s STF and FCR to get global consensus on the latest state of the rollup.

This allows sovereign rollups to inherit the double-spend security of the base layer: rollup blocks can be reorg-ed if and only if the base layer is re-orged.

Sovereign validity rollups also post validity proofs (e.g. SNARKs) — cryptographic signatures that attest to the correctness of the STF program and rollup FCR program execution — on the base layer. Thus, rollup nodes only need to verify the validity proof to transition to the latest canonical state. 

Strata is a type of sovereign validity rollup: sequencers post validity proofs on bitcoin, which are verified by Strata nodes, including the Strata bridge. Sequencers currently relay the full Strata blocks offchain to full nodes, and include only the validity proof, withdrawal data, and block commitments on Bitcoin, so it could be more accurately categorized as a validium chain.

Bitcoin Rollup Bridge

To deposit an asset from bitcoin to Strata (or generally, any one chain to another) without relying on an honest majority of trusted parties, a contract on Strata must be able to execute light node functions. Namely the contract must validate the STF and FCR of bitcoin.

This is because Strata must verify that the assets are locked in deposit contract on the canonical bitcoin chain before it mints those assets on its chain, which requires knowing the latest state of bitcoin.

Since Strata is an expressive EVM layer, it is relatively simple to build this light client contract. We will shift our focus to the other functionality of a bridge: withdrawals.

To withdraw an asset from Strata back to bitcoin, a withdrawal contract on bitcoin must be able to execute Strata’s light node functions. This requires being able to verify the STF and FCR of Strata and of bitcoin.

If a bitcoin script can verify a SNARK, then it can verify the STF and FCR of Strata and STF of bitcoin. How can we verify a SNARK in Bitcoin?

Even if this SNARK were verifiable and valid, script must verify that the proof was valid over the current canonical bitcoin chain and not a valid private fork with much lower work. Bitcoin scripts have limited block introspection and statefulness, so how do we verify the SNARK proof is valid over the canonical bitcoin chain? 

Our bridge protocol described in this document focuses on solutions to exactly these core questions. These solutions allow trust-minimized withdrawals from Strata to bitcoin with 1-of-N liveness assumption during withdrawals.

The design for the Strata bridge is based heavily on BitVM2, which comes from a preprint by Robin Linus and collaborators. BitVM2 proposes one general way to verify arbitrary computation on the bitcoin blockchain in an optimistic way. It then uses this idea to describe a way to build a trust-minimized bitcoin-compatible bridge to a generic sidesystem. In particular, unlike many other designs that restrict the ability to challenge a misbehaving entity, the BitVM2 design enables anyone to do so. 

Alpen has further improved on and simplified the BitVM2 bridge design to build the Strata bridge. We’ll first describe how the Strata bridge works, and later look at how it differs from BitVM2, as well as ongoing research work in this area.

Strata bridge

Strata bridge operations are conducted by operators who generate special bitcoin transactions and perform certain operations to enable counterparties to use the bridge. These operators control bridge deposit addresses, and will later handle corresponding withdrawals. There are security and liveness tradeoffs relating to the number of operators, and the number can affect efficiency as well. There are also challengers and disprovers, which we describe later, who can help to prevent misbehavior; these can be anyone on the bitcoin network.

We’ll use the term functional to describe an entity, like an operator or challenger or disprover, that follows the protocol rules and processes. The term faulty will refer to an entity that does not. This could occur if the entity is malicious, malfunctioning, or coerced.

User counterparties

When Alice wants to access wrapped funds on Strata from the bitcoin chain, she makes a deposit to the bridge address arranged by the operators, in a deposit transaction. This deposit output is structured only to be spendable if later conditions are met. At this point, Strata can launch into action, minting corresponding wrapped funds to Alice that she can use there. At some point, the wrapped funds end up in the hands of Bob, who wants to withdraw them to the bitcoin chain.

Once Bob burns his wrapped funds on Strata, he doesn’t directly claim Alice’s deposit on the bitcoin chain. After all, the bitcoin network didn’t know in advance that Bob would end up with the funds, so Alice’s deposit conditions couldn’t account for this. Instead, a bridge operator fronts its own funds to him in a withdrawal transaction, minus an agreed-upon fee that the operator keeps as compensation. (This fee is separate from any bitcoin transaction fees that go to miners, who are not directly involved in bridge operations.)

Claiming a deposit

At this point, the operator needs to claim Alice’s deposit to make up for the funds it fronted to Bob. The operator does this by executing a series of transactions that allow it to verifiably assert that the requirements for its claim are met.

The first step is to make a kick-off transaction, which references collateral that the operator has previously staked. This collateral ensures that if the operator is faulty in its claim, it will lose this value permanently. We’ll discuss this collateral in more detail later!

Next, the operator makes a claim transaction, which references the withdrawal. At the same time, it makes an optimistic payout transaction that would provide the operator Alice’s deposit and its collateral back. This payout transaction is locked for a period of time against certain conditions, and allows for anyone on the bitcoin network to check the validity of the claim:

• Did Bob own and burn the Strata funds to make the withdrawal balance to bitcoin?
• Did the operator front Bob his requested withdrawal properly?

Provided nobody challenges the operator’s claim, the optimistic payout transaction is unlocked and the operator receives Alice’s deposit and its staked collateral back. This is the happy path! Bob got his withdrawal, the operator got Alice’s deposit, and Bob paid the operator for its work.

Here’s a broad overview of the process for a single deposit. Note that in practice, the Strata bridge is built to handle multiple deposits and claims happening simultaneously, meaning that payouts don’t need to come from the original corresponding deposit. This diagram shows a simplified version without this parallelism.

Challenging a claim

But what happens if the operator’s claim is invalid? It certainly seems to have an incentive to lie and wrongly claim a deposit. During the optimistic payout lock period, anyone who deems the claim invalid can generate a challenge transaction. This includes a fee (which could be crowdfunded) that the challenger must provide to the operator. The fee discourages false challenges against a functional operator, and covers the cost of the operator’s required response to the challenge.

When a challenge is issued, the operator must respond with a set of assertion transactions that provides partial proof of the terms of its claim: the Strata burn, the fronted withdrawal, and a few other components. It turns out that this is where the real meat of the bridge design starts, so we’ll discuss it in more detail later.

Another lock period begins, during which anyone on the network can check the operator’s assertion. If the assertion is valid (meaning the operator was functional), the operator posts a payout transaction that provides it with both Alice’s initial deposit and the operator’s own collateral. This is similar to the earlier optimistic payout transaction, but differs in structure for reasons we’ll explain later.

It’s possible for the operator’s assertion to be invalid, since it provides only partial proof of the claim validity for efficiency reasons. If this happens, any disprover (including the original claim challenger) can post a disproving transaction that includes verifiable evidence of the inaccuracy. This transaction takes the operator’s staked collateral, burning part of it and providing the remainder to the disprover as a reward for reporting the fault.

Enforcing logic

The claim process involves a lot of logic. Certain transactions must occur in specific orders, transactions must reason about specific common data, and different “paths” mean that some transactions must not occur if others do.

This brings up three crucial questions.

• How can the ordering and logical paths between these transactions be enforced by the bitcoin network using consensus rules?
• How can we be sure that each of these highly-structured transactions has the correct form and conditions for spending?
• How can we pass verifiable state between transactions?

If we can’t ensure these questions have satisfying answers, we can’t be sure that the bridge is guaranteed to work properly since the counterparties, operator, and challenger might be faulty.

To solve these, the Strata bridge uses several simple but clever ideas in conjunction: emulated covenants, connector outputs, and one-time signatures. We’ll describe each of these.

Emulated covenants

Bitcoin’s script satisfiability rules and structure do not permit transaction introspection. That is, consensus cannot enforce any existing state or restrictions on how the transaction can spend outputs, apart from the requirements of a script to unlock a spend at all. The term of art for these output restrictions is covenants. Covenants have important use cases: a common example is a vault, where funds can only be withdrawn in a two-stage process that mitigates the risk of stolen keys.

There are several proposals for different ways to add covenants to bitcoin. Unfortunately, they are not available for use outside of testing environments without a consensus soft fork.

The Strata bridge design implicitly requires covenants. Placing requirements on certain outputs can enforce effective links between transactions, while simultaneously ensuring that those transactions (like claims and assertions and payouts) have the structure required by the overall bridge design protocol.

In the absence of covenant support by the bitcoin consensus rules, we emulate them using multisignatures (in conjunction with connector outputs, described next). When setting up the bridge for a deposit, the operators generate the structured transactions referenced above, and collectively sign them (using MuSig2, a Schnorr multisignature scheme). Because the pre-signed transactions can define output requirements, the effect is effectively covenants, albeit with a bit of trust.

Why does trust come into play? As long as at least one of the operators is functional, all of the pre-signed transactions that could possibly be needed for any bridge operation will be prepared as expected. All we need is for one functional operator to refuse to sign any noncompliant transaction provided by its fellow operators. This is so-called “1-of-N” trust, which is close to minimal.

It’s worth noting that if consensus support for covenants were to be added to bitcoin in the future, they could be used directly in the bridge design without the need for multisignature emulation, and may enable significant simplification of transaction structure, lock periods, and operator requirements.

Connector outputs

In conjunction with emulated covenants that allow links between structured transactions, we need a way to enforce more complex logic ensuring that once a transaction “path” is taken during bridge operations, certain transactions off the path cannot occur.

The approach taken is elegant and simple. If we have two exclusive paths leading from a common transaction, we ensure that the common transaction generates an output that would be spent by transactions on both paths. Since bitcoin consensus rules prohibit double spending of outputs, only one path can be taken by posting its transaction. These outputs are sometimes called connector outputs since their purpose is to connect transactions together for logical path enforcement.

Notice that this approach doesn’t work alone; after all, how do we make such that a connector output actually appears in the common transaction and on both paths? This is where emulated covenants become useful, since they ensure this structure is in place.

A useful aspect of connector outputs is their value. For some paths, we might want to bring bitcoin value, such as operator collateral, along to be used later in the path. For other paths, value transfer may not be required, as the purpose of the connector is solely to carry information. In those cases, the connector output can have zero value.

One-time signatures

We need to be able to pass state between transactions in a way that’s verifiable. Doing so in general is challenging since bitcoin has extremely limited means to perform chain introspection.

The solution used by the Strata bridge is to use Winternitz one-time signatures in a specific way. These kinds of signatures allow a signer to use a signing key on a message to produce a signature. Verifiers can use a corresponding verification key to check the signature against the message. Winternitz signatures are constructed using hash functions, which makes them easy to work with in bitcoin script.

These signatures have a limitation, in that it’s only safe to use your signing key a single time on a single message. This is fine in practice, since each deposit-and-withdrawal instance uses fresh keys that are only ever used once. When setting up a Strata bridge instance with structured transactions that need a common value passed around, the transactions have identical verification keys hard coded. The common value is signed and included in the transactions along with the signature, and verification can be performed using script consensus rules.

Overall, this lets us reason about values between transactions using bitcoin consensus rules in ways that are otherwise not possible! This technique is used in the Strata bridge challenge processes in several places, where a challenger or disprover can reference state from an earlier transaction.

Optimistic process

Being able to enforce transaction logic and establish transaction paths with known state is beneficial for bridging because operator claims are optimistic. An optimistic claim means there’s a “happy” path where the operator is functional and not challenged, and an “unhappy” path where the operator is (likely) faulty and a challenger appears.

Because deposit value and operator collateral need to move between exactly one of these paths, we need to be able to rigorously enforce this logic and use state information to determine how to traverse transaction paths. Hence emulated covenants, connector outputs, and one-time signatures!

Reusable operator collateral

We noted earlier that an operator claim needs to reference collateral that it has previously staked, with the intent that if the operator is faulty, the collateral can be slashed as punishment. It’s not possible for the operator to stake collateral when it processes a claim, since transaction pre-signing means this collateral would need to be available at deposit time, increasing the amount of capital that each operator would need to keep staked.

The Strata bridge design addresses this through the use of stake chains. A stake chain is a pre-signed set of transactions that lock operator stake, but do not specifically tie it to only a single deposit over time. Instead, each “link” transaction in the chain allows the operator to use the stake for a different deposit. However, it’s important that the stake not be allowed to be used for multiple claims at the same time. Otherwise, if the stake were slashed in one claim, it couldn’t be slashed in any other! If an operator wishes to process multiple claims in parallel, it can open multiple stake chains instead.

When an operator chooses to use its stake in a claim, it “plays forward” the stake chain to the appropriate link for the corresponding deposit. This link is constructed such that if the claim is challenged and successfully disproved due to operator fault, the stake is slashed and the stake chain is broken: the stake can’t be used again!

There are subtleties in this design resulting from the complexity and duration of the claim process. For example, an operator might try to begin a claim process and then play the stake chain forward at the same time, hoping to get away with a false claim that can’t be slashed. The Strata bridge design addresses these kinds of attacks by ensuring that a special burn transaction can be used to slash the stake and break the chain if it’s discovered that the operator is trying to do this. The burn transaction also uses connector outputs associated with the claim’s payout, blocking the operator from receiving a withdrawal. In fact, burn transactions even come in sets, helping to mitigate against certain kinds of advanced censorship attacks from powerful adversaries.

The effect of the careful stake chain design is that operators have flexibility in the use of their staked collateral, while ensuring that faulty behavior can’t result in unsafe situations where any given collateral is in use for multiple claims at the same time.

Reasoning about chains

An important part of the challenge process is using the bitcoin consensus rules to reason about chain behavior. This reasoning needs to happen about both the bitcoin chain and Strata. On the bitcoin chain, the bridge needs to assess the status of the withdrawal transaction that the operator uses to front Bob’s funds. On Strata, the bridge needs to assess the validity of Bob’s burn.

Even though the bridge transactions occur on the bitcoin chain, consensus rules don’t permit “introspection” into transactions in a useful way. This means the use of “vanilla” bitcoin scripting operations won’t work for this.

The situation is further complicated since the bitcoin chain has no inherent knowledge of Strata state on its own, nor of how Strata executes its transactions. It’s a separate system!

Bitcoin chain fork selection

Part of the operator’s claim process is to assert that it made a valid withdrawal transaction that fulfills Bob's withdrawal request. Because the bitcoin chain can fork, either temporarily due to normal mining and network propagation behavior or maliciously by faulty miners, an operator may have an incentive to collude with miners, produce its withdrawal transaction on a malicious fork and reference this transaction on the main chain in its claim; this would allow the operator to receive Alice’s deposit without providing Bob’s withdrawal!

To show the existence of the necessary transactions for valid claim processing, an operator provides a chain segment consisting of a series of blocks that it claims are on the main bitcoin chain. The Strata bridge design needs to ensure that this segment is effectively anchored: it must be tied to the main chain at its “oldest” point, and must be as close to the main chain tip as possible at its “newest” point. The design uses two techniques to accomplish this.

To keep the end of a segment as close to the main chain tip as possible, the bridge design requires that the operator’s claim must commit to the main chain’s timestamp and block height at the time. These commitments are used in claim processing transactions to enforce time locks that incentivize the operator against claiming faulty values that are too far in the past or future. This diagram shows a simplified version of the process.

The Strata bridge mitigates the issue at the start of the segment using checkpoint anchor blocks. As part of the deposit process, operators agree on a recent block they see on the main chain, which they include when preparing the deposit transaction; this is the anchor block. They also collectively reveal a group key that can be used later. When an operator makes a claim, it commits to the most recent checkpoint, the anchor block of which must also be used in its chain segment. This prevents the operator from producing a private fork of the bitcoin chain that starts too far back in time. If this were allowed, the operator could use the bitcoin difficulty adjustment algorithm to produce its chain more easily than would be expected.

There is, however, a risk that the operator is faulty, and commits to an old checkpoint. If the operator does this, a disprover can produce a chain disproving transaction, which reveals the operator group key from a more recent checkpoint. Because the operators only reveal a new group key when they reach a checkpoint and select a new anchor block, this transaction asserts that the operator was faulty and committed to an old checkpoint. The operator’s collateral is slashed, with part of it going to the disprover as a reward for reporting the fault.

We think this is a useful solution, so let’s go through how it works in more detail in case you’re interested in seeing the cryptographic plumbing.

Group key setup and deposit

Suppose we have $N$ operator-signers comprising the bridge pre-signing group.

At genesis time, the signers agree on a series of $M$ periodic block heights into the future, called checkpoints. The future blocks on the main chain at these checkpoints will be called anchor blocks, each of which corresponds uniquely to a checkpoint $1 \leq j \leq M$. For each $j$, each signer $1 \leq i \leq N$ selects a Schnorr signing key $y_{i,j}$, and computes the corresponding verification key $Y_{i,j} := y_{i,j} G$. We discuss later how each signer should choose its signing keys.

The signers use MuSig2-style key aggregation to compute, for each checkpoint $j$, a group verification key:

$$ Y_j := \sum_{i=1}^N c_{i,j} Y_{i,j} $$

Note that the corresponding group signing key is similarly aggregated:

$$ y_j := \sum_{i=1}^N c_{i,j} y_{i,j} $$

Here we define each weighting coefficient using a suitable cryptographic hash function $\text{H}$:

$$ c_{i,j} := \text{H}\left( N, M, \{ Y_{i,j} \}_{i,j=1}^{N,M}, i, j \right) $$

That is, each $Y_j = y_j G$. The set of group verification keys $\{ Y_j \}_{j=1}^N$ is hard coded and known to all bridge participants, but individual and group signing keys are not (yet) revealed.

When it’s time for the signers to prepare a set of pre-signed bridge transactions for a new deposit, they collectively compute the group signing key $y_j$ corresponding to the next unused group verification key $Y_j$. They examine their view of the main chain and identify the block hash $H_j$ of the anchor block whose height corresponds to checkpoint $j$. The signers embed $y_j$ and $H_j$ into the pre-signed deposit transaction once they agree on these values.

Withdrawal and challenge

When an operator wishes to process a withdrawal, its kickoff-to-claim transaction process includes a bit commitment to the checkpoint $j$ corresponding to the most recent deposit transaction it claims is pre-signed by the signing group. The chain of blocks referenced in the witness of the operator’s produced SNARK proof must include the anchor block from this deposit, whose hash is embedded in the deposit transaction. Note that this is not necessarily the deposit corresponding to the operator’s claim!

This asserts that the operator’s claimed chain includes a block known by the signers to be part of the main chain. However, the operator may be faulty such that the signers have since revealed an anchor block hash corresponding to a more recent checkpoint. If this happens, any disprover can produce a chain disproving transaction.

This transaction contains the operator’s stake as a connector. If the transaction is accepted, some fixed portion of this stake is burned, with the rest going to the disprover as a reward for reporting the fault.

In order to ensure that a valid chain chain disproving transaction asserts the existence of a more recent checkpoint, the spending conditions for this transaction open the operator’s committed index, and require a signature using the next available group signing key.

If the opened checkpoint is $j$, the script effectively requires the following:

• If $j = 1$, there is a signature using group signing key $y_2$
• If $j = 2$, there is a signature using group signing key $y_3$
• …
• For checkpoint $1 \leq j < M$, there is a signature using group signing key $y_{j+1}$

The existence of such a group signing key in a deposit transaction ensures that such a signature can be made by any disprover.

We note a subtlety that can arise with this construction. Suppose that multiple checkpoints pass between deposit transactions. This means that there may exist group signing keys that are not revealed, which in turn means that an honest disprover may not be able to produce a valid chain disproving transaction against a faulty operator.

This situation can be resolved in one of two ways.

Option 1: checkpoint lookback

The first approach uses a lookback technique.

In this approach, signers can select their individual signing keys in one of two ways, for $1 \leq i \leq N$ and $1 \leq j \leq M$:

• The signing key $y_{i,j}$ is sampled uniformly at random
• The signing key $y_{i,j}$ is computed using a key derivation function against a single 32-byte secret seed $x_i$ sampled uniformly at random and diversified using $j$, such that $y_{i,j} = \text{KDF}(x_i, j)$

These requirements ensure that it is not possible for any entity (other than the signer) to compute a signing key $y_{i,j}$ that has not yet been revealed in a pre-signed deposit transaction.

Suppose the checkpoint used in the last deposit is $j_\text{old}$, and that the most recent checkpoint (which the signers must use for a new pre-signed deposit) is $j_\text{new} > j_\text{old}$.

The signers compute and embed into the pre-signed deposit transaction the following:

• The set $\{ y_j \}_{j=j_\text{old}+1}^{j_\text{new}}$ of group signing keys for all intermediate checkpoints
• The hash $H_{j_\text{new}}$ of the most recent anchor block

This ensures that an honest disprover can always satisfy the script requirement of the chain disproving transaction given a faulty operator.

Note that this design is optimistic, in that it minimizes the amount of data embedded in the deposit transaction.

Option 2: chained signing keys

The second approach makes different tradeoffs, and relies on operators selecting their individual signing keys in a specific way.

Each signer $1 \leq i \leq N$ first samples a 32-byte secret seed $x_i$ uniformly at random, and sets $y_{i,M} := \text{KDF}(x_i)$ using a key derivation function. For each $M > j \geq 1$, it recursively sets $y_{i,j} := \text{KDF}(y_{i,j+1})$.

This effectively forms a hash chain, where arrows indicate key derivation:

$$ y_{i,1} \leftarrow y_{i,2} \leftarrow \cdots \leftarrow y_{i,M} \leftarrow x_i $$

Suppose the checkpoint used in the last deposit is $j_\text{old}$, and that the most recent checkpoint (which the signers must use for a new pre-signed deposit) is $j_\text{new} > j_\text{old}$.

The signers embed into the pre-signed deposit transaction the following:

• The set $\{ y_{i,j_\text{new}} \}_{i=1}^N$ of all individual signing keys for the most recent checkpoint
• The hash $H_{j_\text{new}}$ of the most recent anchor block

This ensures that an honest disprover can always “play forward” the hash chain for each $y_{i,j}$ in order to compute the group signing key $y_j$ that it needs to satisfy the script requirement of the chain disproving transaction, but cannot compute any $y_{i,j}$ that has not yet been revealed.

Note that unlike the checkpoint lookback approach, this approach is not optimistic, as it always requires that a set of $N$ individual signing keys be embedded. However, it may simplify signing operations.

Proof verification in script

The Strata bridge uses a technique that allows for the assertion and verification of arbitrary computation using bitcoin’s scripting functionality. While this can be done very generally, for a bridge design we need to verify two particular aspects of chain behavior:

• That the bitcoin main chain contains the operator’s peg out transaction
• That the Strata state is valid and contains Bob’s wrapped fund burn

Because these are complex conditions, the strategy is to generate a succinct (SNARK) proof of them. The idea is that this type of proof is small and computationally easy to verify, though it may require more work to generate. Fortunately, these kinds of proofs exist already! The most common construction is Groth16, named after the paper (by Jens Groth) in which it was introduced. A Groth16 proof can be constructed for essentially any conditions that can be represented mathematically.

Here, the operator uses its anchor block data as part of the proof construction. Specifically, it shows that it can provide a series of bitcoin blocks that includes the anchor block and meets the bitcoin block difficulty target. It also provides information about the Strata state, and shows that the burn transaction is part of this state.

Even though the resulting Groth16 proof is small and quick to verify, the verification process must be represented using bitcoin’s limited scripting functionality. This is possible, but not as a single script due to consensus rules that limit how complex a script can be.

To get around this, the proof verification process is broken down into a series of subprograms that chain together to give the entire verification: at the end, the proof is either accepted (meaning the required bitcoin and sidesystem conditions are met), or it is rejected (meaning the operator was faulty).

These subprograms are effectively executed optimistically as part of the bridge’s overall optimistic structure. The operator only needs to provide initial proof information at the start of its claim process. If a challenger performs the proof verification locally itself and deems the proof invalid, the operator is forced to provide state information about each subprogram in its assertion. The challenger then only needs to execute one failing subprogram in bitcoin script; because the subprograms are small, this can be done efficiently. The use of one-time signature state maintenance ensures that this subprogram information can be passed between transactions to allow these checks to happen correctly.

As part of this subprogram splitting, the design uses bitcoin’s Taproot functionality as part of assertions. Taproot allows for an output to be spent if one of a set of possible conditions is met. The use of Taproot helps to make transactions more efficient. When generating such an output in a transaction, the set of spending conditions is encoded into a Merkle tree, and only the tree’s root is included in the transaction. When the output is later spent, the spending transaction includes the particular spending condition used, in addition to a Merkle path leading to the required root. The “unused” spending conditions do not appear at all!

In our case, the set of possible conditions encodes a possible failure of one of the proof verification subprograms. This means that if the challenger can identify a subprogram that was not executed correctly as part of verification, it presents this failure in its disproving transaction; the transaction is only accepted if the subprogram fails. Notably, this means that only one subprogram’s script must appear in response to a faulty operator assertion; the full program is never required to be on chain.

Tying it together

The Strata bridge design, like its inspiration BitVM2, takes several important and useful constructions and connects them in careful ways. We’ve introduced these components:

• Covenants emulated by multisignatures, which allow us to control which transactions are allowed to be part of bridge operations
• Connector outputs, which let us build logical paths of transactions for “happy” and “unhappy” paths that depend on operator and challenger honesty
• One-time signatures, which provide a way to pass a common state between transactions
• Script-based proof verification, which lets us perform complex and arbitrary computations using subprograms that can be built using bitcoin’s scripting functionality

Of course, there’s still a lot of heavy lifting to be done! One-time signature operations need to be encoded into bitcoin script efficiently, as they are performed often on many different values. The details of the Groth16 proof about bitcoin and sidesystem state are complex to formalize mathematically. And the Groth16 verification subprograms need to be designed as efficiently as possible to ensure that each can be executed in a single script in a manner that is compatible with the overall proof verification steps.

Differences from BitVM2

Alpen’s design for the Strata bridge, while heavily based on the BitVM2 design described above, has several changes and optimizations intended to improve performance, simplify the design, and reduce costs imposed by use of the bitcoin chain. These changes are the result of ongoing work and collaboration by researchers at Alpen and elsewhere.

Superblocks

As discussed, the Strata bridge uses anchor blocks to force operators to “keep up” with the main chain and mitigate private fork attacks. The BitVM2 design proposes alternate ideas that have much more significant tradeoffs and impose risk.

The most prominent of the alternate approaches uses superblocks. The superblock of a given chain segment is the block with the lowest hash (and therefore highest difficulty) in that period. Statistically, a malicious miner is unlikely to produce a “better” superblock in a reasonable time period than the main bitcoin chain. Otherwise, it is likely that its fork will contain greater accumulated difficulty and be accepted as the main chain.

To use this idea in the BitVM2 claim process, an operator must commit to a starting block height simultaneously with the kick-off transaction. During an ensuing “measurement” period, it monitors the bitcoin chain to determine the superblock, which it commits to as part of its claim. If the operator fails to perform this commitment, or does not submit its claim promptly at the end of the measurement period, a challenger can submit a transaction that forfeits the operator’s staked collateral, burning a portion of it and providing the remainder to the challenger as a reward for reporting this failure. This restricts the amount of time available to a faulty operator (and its mining colluders) to mine maliciously.

While a functional operator will correctly identify the main chain’s superblock, a faulty operator may substitute another block, like the superblock of a malicious fork. If this happens, a challenger can submit a special disproving transaction where it provides verifiable proof of the existence of a fork containing a block in the same period with higher difficulty, alleging this as the main chain’s superblock. A valid proof means the chain disproving transaction is accepted and burns part of the faulty operator’s staked collateral, providing the rest to the challenger as a reward for reporting the fault.

However, this approach is flawed. When disputing an operator’s provided superblock, it is possible for a faulty disprover to provide a superior superblock that is not anchored to the expected chain. This allows for such a disprover to produce a claimed superblock in advance if it possesses enough computational power and can predict the time of a future claim. The anchor block design used in the Strata bridge does not have this issue.

Simplified block height management

In the BitVM2 design, the operator commits to a starting block height in a start time transaction such that if it does not, a challenger can cancel the claim. This start time is necessary to establish the beginning of the operator’s superblock measurement period.

There is a flaw in this design where a faulty operator can commit to a starting block height in the past, giving it the ability to maliciously attempt to mine its own private fork in advance.

In conjunction with avoiding the use of superblocks, the Strata bridge design removes the start time transaction, instead requiring the operator to commit to the start time in its claim transaction. To ensure that the operator makes a timely claim, an invalidation transaction can be used by a challenger in case the operator has not properly selected a starting block height.

Simplified disproving

In the BitVM2 design, there are two mechanisms by which a challenger can disprove an assertion by a faulty operator.

The first mechanism is using a disproving transaction, which can be made if a challenger identifies that the claim proof provided by an operator in its assertion transaction is invalid. The challenger provides specific subprogram information that renders the proof invalid.

The second mechanism uses a chain disproving transaction, which can be made if the challenger identifies that the superblock claimed by an operator does not match the challenger’s view of the bitcoin chain. The challenger provides an alternate superblock and proves it is superior to the operator’s.

Because the Strata bridge does not require or use superblocks, it modifies the BitVM2 chain disproving transaction to function with anchor blocks instead.

Multi-stage assertions

The BitVM2 design specifies a single assertion transaction by an operator, in which the operator presents verifiable proof of its claim. This proof consists of Groth16 verifier subprogram information that is stored as common state using one-time signatures. This subprogram information can be used later by a challenger who wishes to produce a disproving transaction showing that at least one subprogram was executed incorrectly, signaling an invalid proof.

In practice, it is not feasible to fit this information into a single transaction due to bitcoin scripting and transaction limits. To overcome this, the Strata bridge design splits up the subprogram information between multiple assertion transactions, using connector outputs to manage the logic. The effect is identical to the “idealized” single assertion transaction presented in the original BitVM2 design, but the change is necessary to account for these limits.

Capital efficiency

The BitVM2 design specifies that each deposit must have associated with it a particular operator collateral. Because the withdrawing operator for a deposit is not known in advance, the result is that each operator must stake collateral for each deposit for which it wishes to be considered for later withdrawal.

As noted earlier, the Strata bridge mitigates this through the use of stake chains, which require an operator to stake only the collateral it needs for a single deposit. If the operator wishes to be considered for processing multiple withdrawals in parallel, it can simply establish multiple stake chains.

Ongoing research

BitVM2 has rapidly developed into a practical technology, but it is still far from mature. It continues to rapidly change and improve, and it will likely continue to do so for the foreseeable future. Many of these optimizations come from the similarly rapidly-improving field of applied SNARK research. Surprisingly, the problems of verifying SNARKs on bitcoin and designing SNARKs in the first place are quite similar.

More fundamentally, there are other approaches than BitVM2 to verifying SNARKs on bitcoin. For example, techniques based on cutting-edge theoretical cryptography like witness encryption and functional encryption would be very compelling. These approaches would dramatically simplify the design of the bridge, and even if not practical may nevertheless yield interesting hybrid approaches.

Improvements to BitVM2 verifier

BitVM2 allows verifying arbitrary computation on bitcoin, not performing arbitrary computation. This distinction may seem subtle, but it has profound implications on the sort of optimizations that are possible. It is also the same distinction that enables many interesting techniques in the design of SNARK protocols themselves. SNARKs verify computation, which enables the prover to non-deterministically pass hints to the proof. For example, rather than computing an inverse, in a SNARK one typically “witnesses” the inverse and checks that it is correct.

In BitVM2, we typically think of a computation as a linear sequence of discrete steps, each represented as a bitcoin script. The output of one step is fed as the input to the next, which limits the “width” of circuits one can conveniently express in BitVM2. A promising class of improvements to BitVM2 that alleviates this limitation comes from memory checking protocols.  In a memory checking protocol, a prover convinces a verifier that a sequence of reads and writes to a memory are correct. Remarkably, this does not require actually materializing the memory in bitcoin script. For BitVM2, this would allow chunks to arbitrarily pass data even in ways that depend on the witness to the computation. This would allow, for example, precomputing a cache of elliptic curve linear combinations to accelerate scalar multiplications. The particular values read from this cache depend on the scalar, so in order to use this technique with BitVM2, we would need to pass the entire cache between chunks. A memory checking protocol avoids this entirely, as each chunk only needs to witness the portion of the cache that it uses.

Alternative approaches

Beyond BitVM2, there are many interesting new cryptographic techniques that could also solve the problem of SNARK verification on bitcoin. These approaches have very different tradeoffs and have the potential to dramatically simplify the bridge design overall. Unfortunately, the most compelling of these techniques, based on functional encryption (FE) and/or indistinguishability obfuscation (iO), are not known to be practical.

A functional encryption scheme consists of four algorithms: setup, key generation, encrypt, and decrypt. Setup generates a pair of keys consisting of a secret and a public key. Key generation takes a function and secret key as inputs, and outputs a decryption key. Encrypt takes a message and public key as inputs, and outputs an encrypted message. Decrypt takes a decryption key and encrypted message as inputs, and outputs the corresponding function applied to the message. Running the decrypt algorithm reveals no more information about the message than the result of applying the function. We can use this to build non-interactive signature oracles (with certain restrictions). These oracles can verify some conditions, and only if they are met, output a signed bitcoin transaction. This allows adding arbitrary smart contracting functionality to bitcoin, as well as constructing more robust and simpler bridges. Research into these technologies is ongoing, as is research into how they can be applied to bitcoin.

‍