BTC Scaling Proof of Concept: Implementing a Bridge Contract on BTC Supporting OP_CAT

Source: Starknet Chinese Community

Featured Quick View

• In-depth exploration of building a demo bridge contract on Bitcoin to lay the foundation for Starknet's production-level bridge

• Implementing four smart contracts: deposit and withdrawal aggregator, bridge, and withdrawal extender

• Efficiently batch deposit and withdrawal requests using recursive contracts and Merkle trees while maintaining the integrity and security of user accounts

Introduction

In this article, we take a deep dive into how sCrypt builds a demo bridge contract on Bitcoin. This proof-of-concept implementation aims to lay the foundation for a production-level bridge for the Starknet Layer 2 (L2) network. The design of the bridge allows multiple deposit or withdrawal request transactions to be merged into a root transaction and incorporated into the main bridge contract, updating its state, which consists of a set of accounts organized in a Merkle tree.

Because the bridge contract script is very complex, we at sCrypt leveraged the sCrypt Domain-Specific Language (DSL) to write its implementation.

Overview

The bridge consists of a recursive contract Bitcoin script. In this context, “contract” means that the locking script is able to impose conditions on spending transactions, and “recursive” means that the above rules are strong enough to implement persistent logic and state on-chain (a basic requirement for any on-chain smart contract).

The script exists in a chain of transactions, each of which imposes constraints on the structure of subsequent transactions, which unlock the outputs of the current transaction. Every time a new transaction is added to this chain, it represents an update to the bridge state. Therefore, the end of the chain holds the current bridge state.

The contract state — specifically, its hash — is stored in a non-spendable OP_RETURN output. Although we will not spend this UTXO, its data can be inspected when executing the contract script. Specifically, the state holds the root hash of a Merkle tree containing the account data, as shown below:

This Merkle tree holds data for a fixed set of account slots. The leaf nodes contain the hash of the respective account data, which includes the address and balance. To represent empty account slots, these slots are marked with zero bytes.

Every update of the bridge causes the account tree to change. To facilitate this update, we rely on Merkle proofs, whose verification is very efficient in Bitcoin Script. The update mainly consists of two steps. First, we verify a Merkle proof to prove that the Merkle tree contains the current state of a specific account. Then, after calculating the new state of the account, we use the same auxiliary nodes in the aforementioned Merkle proof to derive the new root hash.

An update can be either a deposit or a withdrawal. The bridge can perform batches of these updates in a single transaction.

Deposit

Our goal is to allow users to submit deposit or withdrawal requests independently. To do this, users create separate transactions paying to the deposit or withdrawal aggregation contract respectively. The contract aggregates these requests into a merkle tree. The root hash of this tree can be merged into the main bridge contract, which then processes each deposit or withdrawal.

In the deposit transaction, in addition to hashing the deposit data and building the merkle tree, the contract also ensures that the deposit satoshis locked in the contract outputs are accumulated to the root of the tree in the correct way. The aggregation contract ensures that only the correct on-chain smart contract can use these funds. (Of course, in a production environment, we will also allow users to cancel their deposit transactions).

The design of this tree structure is due to the limitations of the contract script construction, that is, transactions with too many inputs and outputs are not allowed. The tree structure allows us to scale to potentially arbitrary throughput.

Withdrawal Requests

The aggregation of withdrawal requests is similar to deposits, but there are a few differences. First, we need a way to authenticate so that users can withdraw funds from their accounts. This is different from deposits, where anyone can deposit money into any account, similar to how Bitcoin addresses are used. Authentication is done at the leaf node level of the aggregation tree. The withdrawal request aggregation contract checks that the withdrawal address matches the P2WPKH address of the first input in the leaf transaction.

This ensures that the owner of the address approves the withdrawal because they have signed the transaction requesting the withdrawal. Another subtle difference compared to deposit aggregation is that we also hash the intermediate accumulated amounts and pass them up the tree. This is because we need this data when scaling withdrawals, which we will explain in detail later.

The astute reader may notice a potential problem with this withdrawal request authentication model. What if the operator decides to cheat and create a root transaction for an aggregation tree whose data was forged locally via an unauthenticated fake withdrawal request? We need an efficient way to verify that the root transaction is derived from a valid leaf transaction.

To solve this problem, we perform what is called a "genesis check". Essentially, we have the aggregation contract check its previous transaction and the previous two transactions, its "ancestor transactions". The contract verifies that these transactions contain the same contract script and perform the same checks. In this way, we implement an inductive transaction history check. Since the previous two transactions perform the same checks as the current contract, we can confirm that the "ancestors" of these transactions also performed the same checks, all the way back to the leaf node (i.e. the genesis transaction).

Of course, we perform validation on both branches of the tree. So, each aggregation node transaction checks a maximum of six transactions in total.

Withdrawal Extension

Now let's move on to the final part of the solution: the withdrawal extension. After processing a batch of withdrawal requests, the main bridge contract enforces an output that pays the total withdrawal amount to the extension contract. We can think of this contract as the reverse process of what the withdrawal request aggregation contract does. It starts at the root node of the withdrawal tree and expands it into two branches, each containing the corresponding withdrawal amount that should be paid to that branch. This process continues all the way to the leaf nodes of the withdrawal tree. The leaf transaction enforces a simple payment output that pays the account owner's address the amount they requested to withdraw.

Implementation

To implement our bridge contract, we developed four sCrypt smart contracts, each handling a different aspect of the system. In this section, we will briefly outline the functionality of each contract.

Deposit Aggregator Contract

The Deposit Aggregator contract aggregates individual deposits into a Merkle tree, which is then merged into the main bridge contract. This aggregation enables batch deposit processing, reducing the number of transactions that need to be processed individually by the bridge. In addition, it allows users to submit deposits independently, which can be processed later by the operator.

The contract construction function has two parameters:

• operator: the public key of the bridge operator, which has the right to aggregate deposits.

• bridgeSPK: The script public key (SPK) of the main bridge contract, ensuring that aggregated deposits are merged correctly.

The core functionality of the deposit aggregator is encapsulated in the "aggregate" method. This method performs the following steps:

Verify sighash preimage and operator signatures: Ensures that the transaction is authorized by the bridge operator and that the sighash preimage is well-formed and belongs to the transaction being executed. Learn more about sighash preimage verification in this article.

Construct and verify predecessor transaction IDs: Checks that the aggregated predecessor transaction is valid and correctly referenced.

Merkle tree aggregation: Verify that the deposit data passed as the witness hash matches the state stored in the preceding transaction. Amount Verification: Confirm that the amount in the previous output matches the specified deposit amount to ensure that the funds are calculated correctly in the aggregation.

State update: Calculate a new hash by concatenating the hash of the previous transaction and update the state in the OP_RETURN output.

Reentrancy attack prevention: Enforce strict output scripts and amounts to prevent unauthorized modifications or double spending.

Once deposits are aggregated, they must be merged into the main bridge contract. This process is handled by the "finalize" method, which includes the following steps:

Verify predecessor transactions: Similar to the "aggregate" method, verify predecessor transactions to ensure the integrity of the merged data.

Integration with the bridge contract: Check that the aggregated deposits are correctly merged into the main bridge contract by referencing the bridge's transaction ID and script public key.

The full source code of the deposit aggregation contract can be viewed on GitHub.

Withdrawal Aggregator Contract

WithdrawalAggregatorThe contract is designed to aggregate individual withdrawal requests into a Merkle tree, similar to how deposit aggregators process deposits. However, withdrawal operations require additional authentication to ensure that only legitimate account owners can withdraw funds from their accounts.

The core functionality of the withdrawal aggregator is encapsulated in the "aggregate" method, which performs the following steps:

Build and verify predecessor transaction ID: This process verifies that the aggregated predecessor transaction is valid and correctly referenced.

Proof of Ownership Verification: Verifying the Proof of Ownership transaction ensures that only the legitimate owner can withdraw funds from the account.

• Proof of Ownership Transaction: A transaction that proves control of a withdrawal address. The contract checks whether the address in the withdrawal request matches the address in the proof-of-ownership transaction.

Genesis check through "ancestor transactions": Similar to the deposit aggregator, the contract performs an inductive check by verifying ancestor transactions. This ensures the integrity of the transaction history and prevents operators from inserting unauthorized withdrawal requests.

Amount verification and total amount calculation: This method calculates the total amount to be withdrawn by adding the amounts of the withdrawal request or the previous aggregation.

Status update: Calculate a new hash value that contains the hash value of the previous transaction and the sum of the withdrawal amount. This hash is stored in the OP_RETURN output to update the state.

Reentrancy Prevention and Output Enforcement: Ensure that outputs are strictly defined to prevent unauthorized modification or reentrancy attacks.

The full source code of the withdrawal aggregation contract can be viewed on GitHub.

Bridge Contract

The Bridge contract is the core component of our system and is the main contract that maintains the bridge state, including accounts and their balances organized in a Merkle tree. It handles deposit and withdrawal operations by integrating with the aggregator contract we discussed earlier.

The contract construction function has two parameters:

• operator: The public key of the bridge operator, who has the authority to update the bridge state.

• expanderSPK: The script public key (SPK) of the WithdrawalExpander contract, used during the withdrawal process.

The deposit method is responsible for processing the aggregated deposit transaction and updating the account balance accordingly.

The steps performed by the deposit method include:

Process deposits and update accounts:

• Traverse the deposits and use the "applyDeposit" method to apply each deposit to the corresponding account.

Update bridge state and outputs:

• After processing the deposit, compute the new account Merkle root.

The withdraw method processes the aggregated withdrawal transaction, updates the account balance, and prepares the allocated funds via the withdrawal extender.

The steps performed by the withdraw method include:

Process the withdrawal request and update the account:

• Iterate over the withdrawal requests and apply each withdrawal to the corresponding account using the "applyDeposit" method.

Update the bridge state and outputs:

• After processing the withdrawal, calculate the new account Merkle root.

• Create a new state hash value representing the updated bridge state.

• Construct the contract output to subtract the total withdrawal amount from the bridge balance.

• Create an extended output for the withdrawal extender contract containing the total withdrawal amount.

• Ensure that the output conforms to the expected format to maintain data integrity.

Full source code is available on GitHub.

Withdrawal Expander Contract

The Withdrawal Expander is the final component of our bridge system, responsible for distributing the aggregated withdrawal amounts back to individual users based on their withdrawal requests. It reverses the aggregation process performed by the Withdrawal Aggregator and expands the aggregated withdrawal data back to a single user's payment.

The core functionality of the Withdrawal Expander is encapsulated in the "expand" method. The method accepts aggregated withdrawal data and recursively expands it into individual withdrawal transactions, paying the corresponding amount to the user.

Expand to leaf nodes: If the method expands to a leaf node (single withdrawal), it verifies the withdrawal data and builds an output that pays directly to the user's address.

Further expansion: If the method has not yet reached the leaf node layer, it continues to expand, splitting the aggregated data into two branches and creating outputs for consumption by further expanded transactions. In this proof-of-concept implementation, we developed a bridge contract to Bitcoin with OP_CAT support using the sCrypt embedded domain-specific language (DSL). The bridge leverages recursive contracts and Merkle trees to efficiently batch deposit and withdrawal requests while maintaining the integrity and security of user accounts. By designing and implementing four smart contracts, DepositAggregator, WithdrawalAggregator, Bridge, and WithdrawalExpander, we provide a way to manage stateful interactions on Bitcoin, facilitating interoperability with layer-2 networks like Starknet. This work provides the technical foundation for building production-grade bridges, potentially enhancing scalability and functionality in the Bitcoin ecosystem.

All code implementations and end-to-end tests are available on GitHub.

[End of full text]

Original link: https://starkware.co/blog/implementing-a-bridge-covenant-on-op-cat-bitcoin/

Mirror: https://mirror.xyz/starknet-zh.eth/zFbhQB7gfmSTV4CcTv5MRqJBUnKuwMLTNOgZ6jUgDK8