arXiv:2605.20952v1 [cs.DC] 20 May 2026
Ark: Offchain Transaction Batching in Bitcoin Pim Keer
Matteo Maffei
Marco Argentieri
TU Wien Vienna, Austria [email protected]
TU Wien Vienna, Austria [email protected]
Ark Labs Tallinn, Estonia [email protected]
Andrew Camilleri
Zeta Avarikioti
Ark Labs Tallinn, Estonia [email protected]
TU Wien, Common Prefix Vienna, Austria [email protected]
Abstract Bitcoin is the cryptocurrency with the largest market capitalisation, but its widespread adoption is fundamentally limited by the scalability constraints of its consensus algorithm, which requires every transaction to be confirmed onchain. To address this, several Layer-2 scalability solutions have been proposed to move payments offchain—most notably, the Lightning Network. However, their deployment remains hindered by cumbersome setup requirements: users must lock funds onchain to participate and engage in complex auxiliary protocols (e.g., for channel rebalancing, top-ups, and routing). Other solutions, like payment pools, sidechains and rollups, cannot be implemented in a non-custodial way on Bitcoin due to its limited scripting capabilities, or require all protocol participants to update the offchain state. In this work, we present Ark, the first Bitcoin-compatible commitchain. Ark enables offchain transactions of virtual UTXOs (VTXOs), through an untrusted operator who aggregates them into succinct onchain commitments. A distinctive feature of Ark is its ease of deployment: users can receive offchain payments without locking any funds beforehand and Ark state updates can be performed only requiring the users involved in that update. We formally define the Ark protocol and prove its security. During this process, we identified two attacks affecting the testnet implementation, which we responsibly disclosed and proposed fixes for, which have been now integrated into the mainnet implementation. Our experimental evaluation demonstrates that Ark can commit onchain to batches of arbitrarily many VTXOs with a constant-sized footprint of approximately 200 vB. Cooperative exits add one output per user, while unilateral exits require O (log 𝑛) transactions of roughly 150 vB per VTXO for a batch of 𝑛 VTXOs.
1
users must lock collateral onchain to initially fund their channels as well as to engage later on in complex auxiliary protocols (e.g., for channel rebalancing [9, 10, 53], channel top-ups, and payment routing [7, 47, 49]). These usability and liquidity challenges have hindered the widespread deployment of such protocols. In this work, we present Ark, the first Bitcoin-compatible commitchain. A distinctive strength of Ark lies in its open architecture. In contrast to payment channel solutions, users can receive and hold funds without issuing any onchain transaction, thereby lowering entry barriers. At the same time, funds deposited in Ark remain fully fungible: they can be transferred to anyone, Ark user or not, who may subsequently decide to use them within Ark or move them outside—for example, in order to make onchain Bitcoin payments or even to setup a Layer-2 protocol on top of Ark. This design eases onboarding, enhances interoperability, and mitigates liquidity fragmentation. At its core, Ark introduces the concept of virtual UTXOs (VTXOs), which serve as offchain counterparts of standard UTXOs. Ark allows users to transact offchain by drawing on shared liquidity managed by an operator. Each transaction updates the allocation of VTXOs, and the operator periodically commits state updates to the Bitcoin blockchain. Furthermore, Ark features unilateral exit: each user may decide to bring their VTXOs onchain without the operator’s collaboration, and without forcing any other Ark participant to exit. Additionally, Ark imposes minimal online requirements: only the operator must remain continuously online, while users need to connect periodically to refresh their VTXOs; a process that occurs entirely offchain. Finally, in the presence of a rational operator and an existentially honest signer committee, Ark enables fast finality: users willing to make these extra assumptions can opt in to spend their VTXOs immediately, without the risk of the transaction being reverted.
Introduction
The security and decentralisation guarantees of the Bitcoin consensus protocol [37] come at the expense of severely limited throughput of approximately 10 transactions per second, which is about three orders of magnitude lower than conventional credit card systems that can process around 10k transactions per second. To overcome this limitation, a variety of Layer-2 protocols have been proposed, most notably payment channel networks [2, 6, 11, 21, 22, 28, 44] and their extensions (such as payment channel hubs [25, 29, 45, 52], virtual channels [5, 12, 24, 25], and channel factories [16, 42]). However, these approaches share a fundamental drawback: they require a cumbersome and, most importantly, costly setup. Specifically,
1.1
Related work
The comparison between Ark and other Layer-2 protocols is summarised in Table 1 and discussed below. We omit custodial approaches like eCash [17, 18, 26]. Payment channel networks (PCN). PCNs, such as the Lightning Network [44], are networks of 2-party channels, i.e., 2-of-2 multisignature UTXOs, where parties can cooperate to instantly update their channel balances, and where any party can at any time close the channel unilaterally and claim its funds onchain after a dispute period, in which the counterparty should come online to prevent a malicious user from exiting with an old state. PCNs
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
therefore achieve fast finality, i.e., transactions are instant and nonrevertible, and unilateral exit, i.e., users can exit their funds without the collaboration of another party. Closing, as well as opening a channel, has an onchain cost and requires to lock funds, which can only be used within the network. Ark, on the other hand, is externally fungible: it allows users who are not onboarded to receive funds with no onchain footprint. Moreover, PCNs require routing algorithms to find a path with sufficient capacity in the network, rebalancing algorithms to reallocate funds among channels, and possibly onchain top-up transactions. Payment channel hubs [25, 29, 45, 52], virtual channels [5, 12, 24, 25] and state channels [4, 20, 35], which can track arbitrary state, suffer from similar limitations. Channel factories [16, 42] alleviate these issues by creating multiple channels at once, amongst which liquidity can be reallocated. However, one user leaving leads to other users being forced to leave as well. Statechains. Somsen [50] proposed statechains to instantly transfer ownership of a UTXO to arbitrary parties with no onchain activity, and thus achieve fast finality and external fungibility. The owner can claim funds unilaterally after a dispute period. Spark [51] allows splitting the UTXO amongst multiple owners. However, statechains are only secure assuming a trusted operator that cosigns each transfer and deletes its key after each state update, preventing collusion with previous owners. Ark similarly enables operator-assisted transfers, but the operator can be malicious: we just need to assume their rationality for fast finality. Payment pools. The most developed example is CoinPool [38]. It allows multiple users to share a single UTXO, make instant offchain transfers within this UTXO, and allows unilateral exit at any time by any user. Contrary to Ark, it assumes the introduction of several new Bitcoin opcodes (as of the current, post-Taproot, state of Bitcoin: it is thus not Bitcoin-compatible), and has a high interactivity requirement since each state update requires each user’s approval. Sidechains. Sidechains [13, 32, 39] are independent blockchains, able to process transactions to arbitrary users with faster block times (but not necessarily with fast finality), or richer smart contract functionality, running in parallel to the main blockchain, enabling the transfer of assets between them via a two-way peg mechanism. In Bitcoin, this approach has to be custodial, with users sending funds to a trusted committee, requiring its collaboration to exit again. BitVM [1, 34] could partially remove this trust. Regardless, sidechains reduce their security from that of Bitcoin to that of the sidechain’s consensus mechanism. Commit-chains. Here, an untrusted operator coordinates transactions between its participants (not externally fungible) and periodically commits the state to the blockchain. Most commit-chains [31, 43] assume an expressive blockchain to handle user exits and disputes and are thus not Bitcoin-compatible. Commit-chains achieve delayed finality, i.e., the payment is only finalised once the corresponding commitment is confirmed onchain, and survived the dispute period, during which participants should come online to contest any misbehaviour. Assuming a malicious operator, Ark also achieves delayed finality (whereas a rational operator enables fast finality). Clique [46] is a commit-chain handling simple payments on Bitcoin. Its original design requires a covenant functionality Bitcoin currently does not have, but could be modified to instead
use signatures from all users to update the state. In contrast, Ark only requires signatures of users involved in a transaction and the operator to perform a state update and is fully Bitcoin-compatible. Contrary to other commit-chains, both Clique and Ark operators fund the onchain commitment with their own liquidity. Rollups. Rollups [30, 41] offload computation offchain, but post all transaction data onchain. Just like commit-chains, rollups achieve unilateral exit and delayed finality, but are not externally fungible, and they are in general not Bitcoin-compatible. BitVM [1, 34] might in principle be leveraged to design Bitcoin-compatible rollups, but it is very expensive (e.g., dispute require 0.15 BTC in fees and more than 3MB in size). Ark instead focuses on reducing its onchain footprint, having only a small transaction onchain committing to a state update. In contrast to rollups, where the state can be derived from onchain data, each Ark user stores its local state. BitVM is moreover not entirely trustless, as it relies on a committee that is honest and live at setup for liveness and assumes existential honesty throughout the protocol execution for safety. Ark only requires such a committee for its opt-in fast finality mechanism. Table 1: Protocol comparison. Cols.: TA: trust assumptions; UE: unilateral exit; EF: external fungibility (no need for onchain interaction to receive funds); FF: fast finality (safely spend funds immediately, D = delayed until onchain commitment, ∗ under rational operator and 1-of-𝑛 honest committee, otherwise D for Ark); SU: parties required per state update (except unilateral exit) (op. = operator); OL: operator liquidity; BC: Bitcoin-compatible; OR: users should come online each: (DP = Dispute period, OC = Onchain commitment). TA
PCN Statechain Payment Pool Sidechain Commitchain Bitcoin Clique Rollup Ark
1.2
UE EF FF
SU channel ✓ ✓ parties Honest owner ✓ ✓ ✓ op. + op. ✓ Honest validators
✓
OL
0
OR
✓
DP
✓
DP
all
DP
validators
✓
BC
✓
D
op.
✓
D
all
✓ 0 Clique ✓ value 0
Never
OC OC
✓ D op. OC Rational op. + Batch VTXO op. only ✓ ✓ ✓ ∗ involved ✓ value lifetime for FF users
Our contributions
The contributions of this work can be summarised as follows: • We present Ark, the first Bitcoin-compatible commit-chain, featuring unilateral exit, opt-in fast finality, and an open architecture, allowing receivers to join without performing any onchain transaction, and funds to be spent within as well as outside Ark.
Ark: Offchain Transaction Batching in Bitcoin
• We formalise and prove the security of Ark (VTXO security, user balance security, atomicity, operator balance security, and fast finality balance security). In doing so, we identified two attacks on the original Ark protocol, as implemented on testnet: the hostage attack and spam attack. We solve these attacks by introducing reset transactions, which have been integrated into the mainnet implementation. • We conduct an experimental evaluation to demonstrate the performance and scalability gains. Specifically, we show that the onchain footprint for a commitment with arbitrarily many VTXOs is constant (197 vB) and for unilateral exit is logarithmic in the number 𝑛 of VTXOs per commitment (⌈log 𝑛⌉ · 150 + 107 vB), which is a reasonable price to pay to obtain the functionality of a commit-chain in Bitcoin. Finally, we show the time required to produce a commitment is linear in the number of users involved in the commitment. For example, it requires a mere 2.7 seconds for 200 users.
2 Model and Protocol Overview 2.1 Model and Notation System Model. Ark is a Bitcoin-native transaction batching protocol that lets an arbitrary set of users P = {𝑃1, 𝑃2, . . .} transact offchain with a minimal onchain footprint, using an untrusted Ark operator 𝑂. Users hold virtual balances (represented by VTXOs) and issue Ark requests, such as boarding (onramp), transactions, batch swaps, and exits (offramp). Users can moreover claim their funds onchain at any time. 𝑂 aggregates requests and batches them into onchain commitment transactions, which are approved by the involved users in signing sessions coordinated by 𝑂, and are predominantly funded by 𝑂. Blockchain and UTXO Model. We assume a robust public transaction ledger A (Bitcoin) that operates in the UTXO model. The ledger A consists of a sequence of transactions. Transactions and Script. In the UTXO model, each transaction tx maps a non-empty list of existing unspent transaction outputs (UTXOs) to a list of new UTXOs. A transaction is a tuple tx = (ins, wits, outs), where ins = [out1, . . . , out𝑛 ] references unspent outputs, wits = [𝑤 1, . . . , 𝑤𝑛 ] provides unlocking data (wit* ] are new outputs. Each output nesses), and outs = [out*1 , . . . , out𝑚 out = (value, lockScript) holds an amount out.value, locked by a locking script out.lockScript. A transaction is valid if every input is unspent, each script accepts its respective witness, i.e., out𝑖 .lockScript(𝑤𝑖 ) = True, and if no new coins are created, i.e., Í𝑛 Í𝑚 * 𝑖=1 out𝑖 .value ≥ 𝑗=1 out 𝑗 .value. The locking scripts are expressed in the stack-based Bitcoin scripting language. We use: (i) signature checks chkSig𝑝𝑘 that require a valid signature under 𝑝𝑘, (ii) 𝑝-of-𝑞 multisignature checks chkMulSig𝑝,𝑞;𝑝𝑘1 ,...,𝑝𝑘𝑛 , (iii) absolute timelocks absTlk(𝑇 ) and relative timelocks relTlk(𝑡). Taproot allows key-path spends with Schnorr signatures or script-path spends by revealing a single committed script together with a Merkle proof. We denote a Taproot output by Taproot(𝑝𝑘𝐼 ; scriptPath1, . . . , scriptPath𝑛 ), where 𝑝𝑘𝐼 is the internal key used together with the root of a Merkle tree built over the script paths to determine the “tweaked” public key, which is shown in the actual output script. This output can then be spent
by only providing a signature under the tweaked public key, or by providing the witness for a script path together with its Merkle inclusion proof. We set 𝑝𝑘𝐼 to False when the key path is disabled. Ledger Model. We adopt the blockchain (ledger) model of [27] to which parties can submit transactions. In this model, each participant of the blockchain protocol (miner) 𝑀 maintains a local view of the ledger L 𝑀 ; write L 𝑀 for L 𝑀 without the last 𝑘 blocks. −𝑘 We assume our ledger is robust with depth and wait parameters 𝑘, 𝑢, i.e., it satisfies the following properties (informally): with overwhelming probability, (i) if tx ∈ L 𝑀 for some honest 𝑀, it will −𝑘 be reported by the other honest miners at the same position in their ledger views (persistence), and (ii) if tx is given to all honest miners for 𝑢 consecutive communication rounds, each honest 𝑀 will report tx ∈ L 𝑀 (liveness). We use this interface to reason −𝑘 about confirmation and reorgs. We denote for any Ark party (user or 𝑂) 𝑄 by L𝑄 the local view of 𝑄, where 𝑄 shares the view of some miner 𝑀. Communication Model. Parties communicate over authenticated channels. The network is synchronous, i.e., all messages are delivered within a known time bound Δ (which is also the network model of Bitcoin itself). We assume 𝑂 is online, while users may be intermittently online. Users performing fast finality payments need to remain online until their funds are spent. Cryptographic and Script Assumptions. We assume standard cryptographic primitives, i.e., collision-resistant hash functions and EUF-CMA secure signature schemes. Taproot Schnorr signatures are used for key/script paths and for efficientÉ 𝑛-of-𝑛 multisignature via MuSig2 [40] (aggregate key denoted 𝑖 𝑝𝑘𝑖 , checked by chkSigÉ𝑖 𝑝𝑘𝑖 ). Finally, we remark that as script-level covenants are unavailable, spend restrictions can be emulated with 𝑛-of-𝑛 co-signing. Native support for stronger covenants in Bitcoin would reduce interactivity, when compared to emulation with multisignatures, but are not required for correctness. Threat Model. A PPT adversary may corrupt any subset of parties (including 𝑂), possibly adaptively and with full collusion. The adversary controls message scheduling (subject to the synchronous bound) and the mempool, but cannot break cryptography or the ledger’s security properties (but with negligible probability). We consider the adversary to be Byzantine, i.e., it may deviate from the protocol arbitrarily. We further provide an extension enabling fast finality, where we assume rationality of the operator, i.e., it can misbehave only if this leads to a financial gain, and existential honesty for (i.e., at least one being honest among) the signing committee.
2.2
Protocol Overview
We use three recurring objects: (i) VTXOs: offchain outputs with at least one collaborative spend path (requiring 𝑂’s signature) and at least one unilateral spend path (user only, after a relative timelock); (ii) batches: onchain outputs that compactly commit to a set of VTXOs by only being spendable before a certain time through presigned, offchain transactions creating these VTXOs; and (iii) connectors: onchain outputs that can only be spent to create multiple anchors, outputs that atomically bind offchain state updates (changes in the VTXO set) to a future onchain batch (cf. §3.3). Figure 1 illustrates the end-to-end flow; we summarise the components below and cross-reference the detailed sections.
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
• Onchain commitments, §3.1,§3.4. The operator 𝑂 broadcasts commitment transactions, typically funded by its own liquidity. These commitments contain batches that compactly commit to the newly created VTXOs. • Offchain transaction execution, §3.2. Users collaborate with 𝑂 to build offchain (virtual) transactions, spending existing VTXOs and creating new VTXOs. • Batch swapping, §3.3. Users exchange (offchain) old VTXOs for new ones in the next batch by forfeiting the old VTXOs (allowing 𝑂 to claim them if they go onchain). Connectors atomically bind the swap to the next commitment. • Boarding, §3.4. A user posts a boarding transaction whose output is spendable either jointly with 𝑂 or unilaterally after a timelock. Once confirmed, 𝑂 spends it in the next commitment, giving VTXOs to the user for offchain use. • Exiting, §3.4. To exit, the user forfeits their VTXOs and receives onchain outputs in the next commitment. If 𝑂 is unresponsive or adversarial, the user exits a VTXO unilaterally via the script path of the corresponding batch.
2.3
Security and Scalability Properties
We introduce the security and performance guarantees below, which we informally prove in §5. Formal statements and proofs are deferred to Appendix E. The Ark protocol maintains a set of unspent VTXOs, which we can see as offchain state. Intuitively, VTXO Security guarantees that any Ark state can be mapped to a corresponding Bitcoin state (i.e., a set of UTXOs). Ark Atomicity guarantees the transitions between Ark states either take place in full or not at all. • VTXO Security. An unexpired1 VTXO committed in an onchain batch can only be spent with a valid witness (safety). Any VTXO held by an honest user can be unilaterally redeemed onchain before batch expiry (liveness). • Ark Atomicity. For any Ark action (boarding, transaction, batch swap, exit), either all inputs are consumed and all outputs are created, or none is. From these two properties, we can derive balance security, for both the users and the operator. Under the additional assumptions of a rational operator and an existentially honest signer committee, users can moreover opt in to securely transact with fast finality, ensuring balance security even for VTXOs not committed in a batch. Finally, with respect to scalability, Ark’s onchain footprint is: (i) execution constant: the onchain commitment size is constant in the number of VTXOs; (ii) optimistic exit constant: with a responsive operator, a user exits with O (1) onchain transactions; and (iii) pessimistic exit logarithmic: in the worst case, a user exits a VTXO with O (log 𝑛) transactions, where 𝑛 is the batch’s VTXO population. With fast finality, all previous offchain transactions leading to the to-be-exited VTXO need to be posted as well.
3
The Ark Protocol
At the core of Ark is an operator 𝑂 with key pair (𝑠𝑘𝑂 , 𝑝𝑘𝑂 ) who facilitates transactions of virtual UTXOs called VTXOs. VTXOs are offchain outputs that can be spent without leaving an onchain footprint (§3.2). Each VTXO is locked by a Taproot script with two 1 Expired batches of VTXO can be claimed at once by 𝑂 .
paths: a collaborative spend with 𝑂, and a unilateral spend that requires no interaction with 𝑂. Definition 3.1 (Virtual UTXO / VTXO). A virtual UTXO or VTXO, with operator 𝑂, is a transaction output of the form vtxo := (value, vtxoLockScript) where vtxoLockScript is a Taproot locking script with: (i) an unspendable key path; (ii) at least one collaborative script path, requiring a signature of 𝑂; and (iii) at least one unilateral script path, not requiring 𝑂’s signature and delayed by a relative timelock 𝑡𝑢 (determined by 𝑂), ensuring that a VTXO appearing onchain can be spent collaboratively at least 𝑡𝑢 blocks before it becomes unilaterally spendable. A VTXO is called collaboratively or unilaterally spent if the corresponding path is used. The simplest VTXO is a single-signature output: an amount an Ark user Alice, with key pair (𝑠𝑘𝐴 , 𝑝𝑘𝐴 ), can spend via a signature under 𝑝𝑘𝐴 . Its locking script Taproot(False; chkSig𝑝𝑘𝑂 ⊕𝑝𝑘𝐴 , chkSig𝑝𝑘𝐴 ∧ relTlk(𝑡𝑢 )) requires a collaborative witness 𝑤𝑐𝑜𝑙𝑙𝑎𝑏 = 𝜎𝑂 ⊕𝐴 or a unilateral witness 𝑤𝑢𝑛𝑖𝑙𝑎𝑡 = 𝜎𝐴 . For simplicity, we assume in this section that VTXOs have a clear “owner” (e.g., Alice or Bob), who can spend them both collaboratively and unilaterally. However, VTXOs may include multiple complex script paths, generalising ownership to anyone providing a valid witness. This is assumed in the rest of the paper. Throughout the rest of this paper, we adopt two conventions. First, when vtxo = (value, vtxoLockScript) appears as an output in a (virtual) transaction, it represents a value value and a Taproot output script only2 showing the 32-byte tweaked public key committing to the key and script paths in vtxoLockScript. A blockchain observer only sees 𝑝𝑘𝑇 and cannot infer the spending paths. In other contexts (e.g., an Ark user sharing vtxo with 𝑂), both value and all spending paths are shared, allowing derivation of 𝑝𝑘𝑇 . Second, when requests create new VTXOs, these are initially just value–script pairs, not yet tied to a specific transaction. Context clarifies whether we refer to this pair or to a fully defined VTXO within a batch. We now describe Ark’s core functionality: transaction batching, which consolidates multiple VTXOs into a single onchain output called a batch. Users can execute transactions offchain by spending and creating VTXOs, and batch swapping to atomically exchange old VTXOs for fresh ones in a new batch. This process motivates the design of commitment transactions, the only onchain footprint. We then extend this structure to support Ark user entry and exit.
3.1
Transaction Batching
As the name suggests, VTXOs are meant to remain virtual. While they can be unilaterally converted into UTXOs via an exit path, this is ideally avoided: VTXO holders are instead expected to collaborate with 𝑂 to claim funds onchain (see §3.4). This allows us to design a structure that minimises onchain footprint while still permitting unilateral exits if needed. This structure, called a batch, is a transaction output predominantly funded by 𝑂 that can be spent either via a sweep path (returning funds to 𝑂) or an unroll path, which splits the onchain UTXO into offchain VTXOs via a virtual transaction tree (VTXT). This tree is made up of virtual transactions: 2 To be precise, the script reads OP_1 OP_PUSHBYTES_32 𝑝𝑘 . 𝑇
Ark: Offchain Transaction Batching in Bitcoin
Alice
UTXO
VTXO
Alice pays
Change
Bob virtually
output
Exit cooperatively
VTXO
UTXO
Boarding
Commitment transaction
Commitment transaction
...
Commitment transaction
Operator Batch(es) of VTXOs
Specifies
Specifies
Specifies
Batch(es) of VTXOs
Contains
Output
Batch(es) of VTXOs
Contains
Bob
Swap
Exit unilaterally
VTXO
VTXO
UTXO
Time
Figure 1: An example Ark protocol flow (solid boxes appear onchain, dashed boxes optimistically never appear onchain). Alice joins the Ark by submitting her onchain UTXO through a boarding procedure (§3.4). She receives a VTXO contained in a batch (§3.1), which is an output of a commitment transaction (§3.4) posted onchain by 𝑂. Alice can use this VTXO to transact offchain, e.g., by paying Bob. This happens via an ordinary (but offchain) Bitcoin transaction (§3.2), creating a payment VTXO for Bob and a change VTXO for Alice. Alice can exit the Ark cooperatively with 𝑂 (§3.4), turning her change VTXO into an onchain output in a new commitment transaction. Bob secures his new funds via a batch swap (§3.3) with 𝑂, exchanging the received VTXO for a new VTXO, which is again part of a batch output of an onchain commitment transaction. This mechanism ensures that if 𝑂 would no longer respond, Bob can claim his funds onchain unilaterally (§3.4). presigned Bitcoin transactions that optimistically never go onchain, specifying how the batch should be distributed amongst VTXOs. Definition 3.2 (Virtual transaction tree). A virtual transaction tree (VTXT) is a directed rooted tree, given by the ordered pair 𝐺 = (𝑉 , 𝐴), where 𝑉 is a set of virtual transactions (the nodes) with exactly one input, and 𝐴 is a set of ordered pairs of virtual transactions (the edges) such that, for every 𝑢 1, 𝑢 2 ∈ 𝑉 , we have (𝑢 1, 𝑢 2 ) ∈ 𝐴 if and only if 𝑢 2 .ins ⊇ 𝑢 1 .outs. There is also exactly one virtual transaction 𝑟 ∈ 𝑉 , called the root, such that there are no edges 𝑎 ∈ 𝐴 of the form (𝑢, 𝑟 ), where 𝑢 ∈ 𝑉 . For all other 𝑢 2 ∈ 𝑉 , there is exactly one 𝑢 1 ∈ 𝑉 such that (𝑢 1, 𝑢 2 ) ∈ 𝐴. Any 𝑠 ∈ 𝑉 for which there are no edges of the form (𝑠, 𝑢) in 𝐴 (for 𝑢 ∈ 𝑉 ) is called a leaf. For any 𝑢 ∈ 𝑉 , we define path(𝑢) as the sequence (𝑢 1, . . . , 𝑢 ℓ ), where 𝑢 1 is the root, 𝑢 ℓ = 𝑢, and (𝑢𝑖 , 𝑢𝑖+1 ) ∈ 𝐴 for each 𝑖 ∈ {1, . . . , ℓ − 1}. For any out ∈ 𝑢.outs, we interpret path(out) as path(𝑢). Definition 3.3 (Batch). A batch is a transaction output locked by a Taproot script with an unspendable key path and exactly two script paths: (i) a sweep path that allows 𝑂 to claim the entire output after a certain block height, called the batch expiry, and (ii) an unroll path that specifies spending according to a VTXT with root spending the full batch, each leaf a VTXO as its only output, and the remaining nodes virtual transactions that have batches as their only outputs. Remark 3.4. The VTXT structure needs to be enforced by a covenant, ensuring the batch can be spent only according to the VTXT before expiry. To preserve Bitcoin compatibility, this covenant can be emulated with an 𝑛-of-𝑛 multisignature (e.g., Musig2), where 𝑂 coordinates signing sessions with all VTXO holders. Either all holders sign every virtual transaction, or, as in Figure 2, each holder signs only along the path to their VTXO. The latter reduces the number of interactions without compromising safety, since every honest holder must approve
the transactions needed to redeem their VTXO, ensuring their batch funds cannot be spent otherwise. The purpose of batch expiry is explained in §3.4. For now, note that any VTXO holder who knows the virtual transaction path in the VTXT to their VTXO can broadcast it onchain and exit unilaterally. Figure 2 illustrates this: to redeem 𝑣 1 , 𝑃1 must publish the transactions with outputs (𝑣 1 + 𝑣 2, 𝑣 3 + 𝑣 4 ), (𝑣 1, 𝑣 2 ), and 𝑣 1 . Only 𝑃1 ’s VTXO appears onchain, but 𝑃1 must pay fees, which may make small VTXOs uneconomical to exit.
3.2
Ark transactions
As discussed earlier, VTXOs are intended to remain offchain, enabling the offchain execution of transactions via Ark transactions. These spend one or more VTXOs from a batch through the collaborative path, creating new VTXOs. To illustrate the Ark transaction mechanism, consider an Ark user Alice who wants to send amount 𝑝 to Bob. Alice holds a VTXO vtxo𝐴 with value 𝑎 > 𝑝 in a batch. She constructs an Ark transaction tx𝐴ark , a virtual transaction with inputs [vtxo𝑖𝑛,1, . . . , vtxo𝑖𝑛,𝑛 ], collaborative wit1 𝑛 nesses [𝑤𝑐𝑜𝑙𝑙𝑎𝑏 , . . . , 𝑤𝑐𝑜𝑙𝑙𝑎𝑏 ], and outputs [vtxo𝑜𝑢𝑡,1, . . . , vtxo𝑜𝑢𝑡,𝑚 ]. 1 In this example, 𝑛 = 1, vtxo𝑖𝑛,1 = vtxo𝐴 , 𝑤𝑐𝑜𝑙𝑙𝑎𝑏 = 𝜎𝑂 ⊕𝐴 , and the outputs may include: a VTXO vtxo𝐵 with amount 𝑝 spendable by Bob, a change VTXO for Alice, and possibly a fee VTXO to 𝑂. Alice signs tx𝐴ark and asks 𝑂 to co-sign. Once signed, she sends the transaction to Bob along with the VTXT path to vtxo𝐴 , enabling Bob to exit vtxo𝐵 unilaterally. In a way, Bob now holds his own VTXO, without needing prior funds in Ark or on Bitcoin. However, there is a critical issue: Bob must trust Alice not to double-spend vtxo𝐴 . She could unilaterally exit with it (forcing Bob to constantly monitor the chain and post tx𝐴ark if Alice ever exits
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
with vtxo𝐴 ) or collude with 𝑂 to create conflicting Ark transactions spending the same VTXO. Since Ark transactions are virtual, Alice and a (malicious) 𝑂 could theoretically spend the same VTXO arbitrarily many times. If Alice broadcasts vtxo𝐴 onchain, only one such transaction could be confirmed. Next, we explain how Bob can secure his funds by batch swapping vtxo𝐵 for a new VTXO.
3.3
Batch Swaps
To finalise Alice’s payment, Bob atomically swaps vtxo𝐵 for a new VTXO, a process we call batch swapping. Here, 𝑂 takes vtxo𝐵 and issues Bob a new VTXO vtxo𝐵 ′ in the next batch, which serves as onchain confirmation that Bob owns value 𝑏 (which may be smaller than 𝑝 to account for a fee 𝑂 may charge). This guarantees that either both transfers succeed or both fail, removing the need for Bob to monitor the chain or trust 𝑂 not to collude with Alice. For clarity we describe one-to-one VTXO swaps, though the protocol supports swapping multiple VTXOs into arbitrary new allocations. A batch swap starts with Bob requesting 𝑂 to swap vtxo𝐵 . 𝑂 builds a transaction tx𝑂 spending its own funds and producing outputs tx𝑂 .outs = [(𝑏, chkMulSig2,2;𝑝𝑘𝑂 ,𝑝𝑘𝐵 ), (𝜀, chkSig𝑝𝑘𝑂 )]. This is a basic commitment transaction (formally defined in §3.4). The first output is a batch containing one VTXO; the second is an anchor output with dust value 𝜀, essential for atomicity. 𝑂 also creates a virtual transaction txvirtual spending the first output of tx𝑂 and producing vtxo𝐵 ′ . 𝑂 signs txvirtual and shares it with Bob along with the anchor output. Bob then constructs and signs a forfeit transaction txforfeit spending both vtxo𝐵 and the anchor, sending all funds to 𝑂. The signature uses the SIGHASH_ALL flag3 and is only valid for this specific transaction spending the anchor. Thus, txforfeit is valid only if both tx𝑂 and vtxo𝐵 are onchain. 𝑂 can now safely broadcast tx𝑂 , as the anchor ensures atomicity. If Bob turns vtxo𝐵 into a UTXO, 𝑂 can claim 𝑏 via txforfeit . On the other hand, 𝑂 cannot claim vtxo𝐵 using txforfeit as long as tx𝑂 is not onchain. Bob has successfully swapped vtxo𝐵 for vtxo𝐵 ′ , which he can now unilaterally exit by posting txvirtual , regardless of whether Alice tries to unilaterally exit with or double-spend vtxo𝐴 . He no longer needs to monitor the blockchain for Alice turning vtxo𝐴 into a UTXO. If she does, it is now in 𝑂’s interest to broadcast tx𝐴ark and txforfeit to claim what are now its funds. This construction understandably seems cumbersome. However, its power becomes clear when realising we can process more than one VTXO in this way. Indeed, the first output of tx𝑂 is just a batch containing one VTXO (where the VTXT consists only of txvirtual ). We can increase the size of this batch, including other VTXOs that may also have been created through batch swaps. Finally, note that the current construction also locks 𝑂’s funds, since Bob’s signature is required. We show next how these funds are later released to 𝑂.
3.4
Definition 3.5 (Connector). A connector is a transaction output which is locked by a Taproot script connectorScript with an unspendable key path and a script path that specifies spending according to a VTXT where the root spends the full connector, and where each leaf of the VTXT has an anchor output as its only output. The remaining nodes of the VTXT are virtual transactions with a connector as their only output. Each output can be spent by a signature from 𝑂. A connector contains (multiple) anchor outputs serving as inputs to forfeit transactions, that can only be included onchain if the commitment containing that connector is included onchain. Unlike batches, the virtual transactions of a connector are signed solely by 𝑂. We now simply define a commitment transaction as follows. Definition 3.6 (Commitment transaction). A commitment transaction (or commitment) is a transaction with at least one batch or one connector output. A commitment may output multiple batches and connectors. Additionally, it may contain inputs and outputs related to users joining (boarding) and leaving (exiting) the Ark. Boarding. Consider a user Alice with some onchain funds locked in a UTXO out𝐴 . Alice can join, or board the Ark via a two-step process. First, Alice constructs, signs and broadcasts the boarding transaction txboard with input out𝐴 and output out𝐴* , where the locking script of the output out𝐴* can be written as Taproot(False; chkSig𝑝𝑘𝑂 ⊕𝑝𝑘𝐴 , chkSig𝑝𝑘𝐴 ∧ relTlk(𝑡𝑏 )). This is a Taproot script with an unspendable key path and two script paths. The first script path is a cooperative path, in which Alice and 𝑂 spend the funds together, and the second is an exit path, which lets Alice spend her funds after a timeout 𝑡𝑏 . Alice can now send a boarding request to 𝑂, who will first verify that out𝐴* cannot be spent without 𝑂 before the timeout (preventing a double-spend of the next commitment txcommit ), and then create one or more VTXOs for Alice in a batch of txcommit . In return, out𝐴* is added as an input to txcommit via its cooperative path. In case Alice would not want to board the Ark after all, she can either spend out𝐴* via the exit path after the timeout, or cooperate with 𝑂 to spend out𝐴* for a new UTXO that can be spent by Alice only. Exiting. Alice holds one or more VTXOs in confirmed batches and can exit either unilaterally or collaboratively. In the unilateral case, she simply broadcasts path(vtxo) for each owned vtxo, without interacting with 𝑂. In the collaborative case, Alice batch swaps her VTXOs, but instead of receiving new ones, 𝑂 includes a UTXO for her in the next commitment. As in §3.3, 𝑂 also obtains a signed forfeit transaction to prevent Alice from reusing old VTXOs. Constructing a fully signed commitment requires user coordination (see Figure A.1 and Appendix D). This process assumes responsive participants4 . Figure 2 illustrates: 𝑃1 boards via a boarding transaction; 𝑂 combines 𝑃1 ’s and its own funds into a commitment; 𝑃4 swaps a VTXO; and 𝑃5 exits. The batch then includes a VTXO for 𝑃1 , a new VTXO for 𝑃4 , a UTXO for 𝑃5 , and a connector allowing 𝑂 to reclaim 𝑃 4 ’s and 𝑃5 ’s old VTXOs if posted onchain.
Commitment transactions
The previously defined tx𝑂 offers a natural way to contain batches as its outputs. Moreover, the second output of tx𝑂 enables to swap VTXOs atomically. This second output is a so-called connector. 3 Bitcoin’s SIGHASH flags specify which parts of a spending transaction are covered by a signature. In particular, SIGHASH_ALL fixes all inputs and outputs.
3.5
Ark transactions revisited
The earlier testnet version of the Ark protocol is fully described by §3.1-§3.4. However, we found out two critical vulnerabilities in this protocol, which we call the hostage attack and spam attack. 4 If a user is offline, the transaction aborts but can be retried without that request.
Ark: Offchain Transaction Batching in Bitcoin
pkO , pk1
pkO ≥ Te pkO ≥ Te
v1 pkO , (pki )2i=1
txboard v1′
pk1 +tb pk1 , pkO pkO
O’s UTXOs
pkO , (pki )4i=1
P1
pkO ≥ Te pkO ≥ Te
v1 + v2 v3 + v4
pkO ≥ Te pk5
batch v5
O
v2
O
pkO , (pki )2i=1
v4
pk6 +tv
ε4 ε5
pkO , pk6
pkO pkO
...
pkO , pk2
...
P2
pkO , pk3
v3
pk3 +tv
P3
pkO , pk3
...
pkO , pk4
...
pk4 +tv
P4
pkO , pk4
pkO
pkO , pk1
pk2 +tv
...
P6
P1
v2
...
v4
txcommit
O
pk1 +tv
pkO , pk2
pkO ≥ Te pkO ≥ Te
v3
connector
From previous batch
O
O
P5
pkO
v1
O O v4
ε4 ε5
reset
tx
v4
pkO , pk4
pkO ≥ Te
O
pkO
v4 + ε4
pkO , pk4
v4
pk4 +tv
txforfeit pkO
O
P4 pkO
pkO , pk5
txforfeit v5 + ε5
pkO
O
From previous batch pkO , pk5
v5
pk5 +tv
P5
Figure 2: Transaction dependencies within the Ark protocol. UTXOs are represented by small rectangles enclosing a label, representing either the value or their function. (Multiple) UTXOs can be enclosed by a larger rectangle, which is a transaction. Multiple arrows may leave from a UTXO. Each arrow is labelled by a spending condition and may point to a transaction that spends the respective UTXO. Dashed transactions are virtual transactions and optimistically never appear onchain. We set 𝑇𝑒 = ℎ + 2𝑘 + 𝑡𝑒 , where ℎ is the block height txcommit got submitted by 𝑂 and 𝑡𝑒 the time in which a batch should expire. Moreover, recall that 𝑡𝑢 is the minimum delay for a unilateral VTXO exit compared to any collaborative exit, and 𝑡𝑏 the boarding transaction timeout period. Hostage attack. Recall from §3.3 that 𝑂 is responsible for broadcasting Ark and forfeit transactions when already spent or batch swapped VTXOs appear onchain. A problem arises when an Ark transaction includes inputs from multiple batches: at some point, some batches will have expired whereas others have not. 𝑂 wants to sweep expired batches, but doing so exposes it to users who try to unilaterally claim unexpired VTXOs. Normally, 𝑂 would broadcast the Ark transactions up to the batch swap in response, then the forfeit transaction to claim batch swapped output VTXOs. However, once a batch containing an input VTXO has been swept, the Ark transaction becomes invalid and cannot be included onchain. 𝑂 has
thus no way to claim this spent VTXO, resulting in a loss of funds. A malicious user could hold 𝑂’s funds hostage for prolonged periods of time by having Ark transactions with inputs from many different batches. For example, if a user has an Ark transaction spending from batches expiring at 𝑇1 and 𝑇2 > 𝑇1 , and an Ark transaction spending from batches expiring at 𝑇2 and 𝑇3 > 𝑇2 , then 𝑂 cannot sweep any batch until 𝑇3 . This attack can be prolonged as long as the operator processes Ark transactions spending from multiple batches. If the operator would not do so this would severely limit the Ark’s functionality.
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
Spam attack. Recall from §3.3 that a forfeit transaction is only signed for a VTXO that is batch swapped. Hence, a malicious user Mallory holding a VTXO vtxo𝑀 could, in theory, make a chain of Ark transactions to herself, each time spending the new VTXO in the next transaction, and batch swap or cooperatively exit the final VTXO vtxo𝑀 ′ . When the new commitment is confirmed, she could then exit vtxo𝑀 unilaterally. The operator now has to post all Ark transactions onchain, incurring onchain fees to finally broadcast the forfeit transaction that spends vtxo𝑀 ′ . As the potential Ark transaction fees will be significantly lower than the corresponding onchain fees, this spam attack could make it unprofitable for 𝑂 to broadcast the transaction chain up to the forfeit transaction, allowing Mallory to illegitimately claim both vtxo𝑀 and vtxo𝑀 ′ , essentially stealing vtxo𝑀 ′ .value from the operator. Reset transactions. To defend against these attacks, we introduce an additional virtual transaction, the reset transaction, which allows 𝑂 to claim spent VTXOs even if the corresponding Ark transaction became invalid after an earlier sweep. This transaction shifts the responsibility of posting the subsequent Ark transaction to users. Consider the setting of §3.2, where Alice sends an amount 𝑝 to Bob. In addition to constructing an Ark transaction as before, she also creates a reset transaction spending vtxo𝐴 collaboratively, producing one output with value 𝑝 and locking script Taproot(False; chkSig𝑝𝑘𝑂 ⊕𝑝𝑘𝐴 , chkSig𝑝𝑘𝑂 ∧ absTlk(𝑇𝑒 ))). Her Ark transaction then spends this output, giving 𝑝 to Bob. The reset output can thus be spent either jointly by Alice and 𝑂 or swept by 𝑂 once the batch expires. Alice first signs the Ark transaction and sends both the Ark and reset transactions to 𝑂, who verifies the scripts, signs both, and returns them. Alice then signs the reset transaction and passes it to 𝑂 5 . The overall back-and-forth is shown in Figure 3. The resulting transaction flow is also illustrated in Figure 2, where 𝑃3 sends 𝑃4 the amount 𝑣 4 , which 𝑃4 then batch swaps. If Alice wants to perform an Ark transaction with multiple inputs, she first constructs a reset transaction for each input VTXO, and builds an Ark transaction spending the outputs of all these reset transactions. This protects 𝑂 for the hostage attack: if VTXOs from different batches are spent by an Ark transaction, expired batches can safely be swept. Indeed, if an input VTXO appears onchain, 𝑂 can simply broadcast the corresponding reset transaction, claiming the funds at that batch’s expiry. The Ark transaction, which requires all input VTXOs and their corresponding reset transactions to be onchain, became invalid once the expired batches were swept. A receiver wishing to exit unilaterally with the outputs of the Ark transaction should thus do so before any of the batches holding an input to the Ark transaction expires. In case of a spam attack, where Mallory exited unilaterally with vtxo𝑀 , the operator will now simply broadcast the appropriate reset transaction, forcing Mallory to post the subsequent Ark transaction. The operator will always force Mallory to post the next Ark transaction, until eventually the operator can post the forfeit transaction. Mallory having to post all the Ark transactions to try to claim vtxo𝑀 should deter Mallory from trying to claim both vtxo𝑀 and vtxo𝑀 ′ . Note that this deters any rational attacker from mounting this attack. However, a Byzantine user could mount this 5 More precisely, both cooperatively produce the aggregated signatures for the Ark and reset transactions, in that order.
attack regardless. To protect against such attackers, 𝑂 could additionally limit the length of a chain of Ark transactions, forcing a batch swap at some point.
Alice
Operator
Construct txre with input vtxo𝐴 and output out with locking script Taproot(False; chkSig𝑝𝑘𝑂 ⊕𝑝𝑘𝐴 , chkSig𝑝𝑘𝑂 ∧ absTlk(𝑇𝑒 ) ) Construct txark with input
txre ,
out and output vtxo𝐵
txark ,
ark Sign 𝜎𝐴 = Sign𝑠𝑘𝐴 (txark )
ark 𝜎𝐴 ark Verify txark , txre and 𝜎𝐴 ark 𝜎𝑂
ark Sign 𝜎𝑂 = Sign𝑠𝑘𝑂 (txark )
ark Verify 𝜎𝑂 re 𝜎𝐴
re Sign 𝜎𝐴 = Sign𝑠𝑘𝐴 (txre )
re 𝜎𝑂 re Verify 𝜎𝑂
Alice
re Verify 𝜎𝐴 re re Sign 𝜎𝑂 = Sign𝑠𝑘𝑂 (tx )
Bob ark
tx
re
, tx , path(vtxo𝐴 ),
ark ark re re 𝜎𝐴 , 𝜎𝑂 , 𝜎𝐴 , 𝜎𝑂
Proceed with batch swap for vtxo𝐵
Figure 3: Alice sends funds to Bob via an Ark transaction. Upon receiving the signed Ark transaction txark and reset transaction txre (described in §3.2 and §3.5 respectively), Bob will request a batch swap as introduced in §3.3 and only consider the transaction finalised once the corresponding commitment transaction is confirmed onchain.
3.6
Offchain handover
As described in §3.4, unilateral exits involve broadcasting the whole virtual transaction path leading up to the to-be-exited VTXO. Onchain activity may thus spike if many Ark users unilaterally exit their VTXOs, for example when an operator stops responding and users must claim funds to prevent loss. Even if the operator remains active, facilitating collaborative exits can still create numerous onchain UTXOs when many users are involved. If some users wish to stay in an Ark, such exits require a subsequent onchain boarding transaction into a new Ark. To avoid this footprint, we introduce an offchain handover procedure, allowing a VTXO in an Ark with operator 𝑂 1 to move into an Ark with operator 𝑂 2 . If 𝑂 1 plans to shut down but stays online to process handovers, its users can migrate to 𝑂 2 ’s Ark entirely offchain, with the only onchain footprint being 𝑂 1 reimbursing 𝑂 2 for the transferred VTXOs. Consider a user Alice holding a VTXO vtxo𝐴 of value 𝑣 in a confirmed batch funded by 𝑂 1 . Suppose 𝑂 1 plans to shut down its Ark but remains cooperative to transfer Alice’s VTXO to an Ark run by 𝑂 2 . This transfer is effectively a batch swap with connector spendable by 𝑂 1 , and the new VTXO funded by 𝑂 2 .
Ark: Offchain Transaction Batching in Bitcoin
Alice requests a batch swap to 𝑂 2 , as in §3.3. 𝑂 2 includes a new VTXO for Alice and an anchor output in its commitment transaction, but this anchor is now spendable by 𝑂 1 . Instead of Alice and 𝑂 2 signing a forfeit transaction spending the anchor and giving vtxo𝐴 to 𝑂 2 , Alice and 𝑂 1 sign one giving it to 𝑂 1 . This two-operator batch swap ensures 𝑂 1 can claim vtxo𝐴 if Alice exits unilaterally. Since 𝑂 2 funds Alice’s new VTXO without being able to sweep vtxo𝐴 , 𝑂 1 must reimburse 𝑂 2 by amount 𝑣. This is conditional on 𝑂 2 ’s commitment being confirmed onchain. To enforce this atomicity, 𝑂 2 ’s commitment includes an anchor output out1→2 used as input to tx1→2 , where 𝑂 1 pays 𝑂 2 the amount 𝑣. Before signing this modified commitment, 𝑂 2 requests tx1→2 , signed by 𝑂 1 . If valid, 𝑂 2 can broadcast both transactions and safely claim 𝑣. Conversely, 𝑂 1 only pays if 𝑂 2 ’s commitment is confirmed onchain. This scheme scales to multiple VTXOs, where tx1→2 now pays the total amount 𝑂 2 needed to fund all the transferred VTXOs. For the users, the online requirement is the same as for a normal batch swap (some tasks are simply in collaboration with 𝑂 1 , and others with 𝑂 2 ). Additionally, we need 𝑂 1 to remain responsive and handle the extra overhead of signing off on tx1→2 and verifying 𝑂 2 ’s commitment.
4
Fast Finality
In §3.3 Bob must batch swap the VTXO received from Alice before treating the payment as final: ownership is only guaranteed once the corresponding commitment confirms onchain, since Alice could otherwise collude with 𝑂. This limits how quickly VTXOs can be spent again. If 𝑂 is honest, it will never cosign a conflicting spend of an already-spent VTXO, and Bob can therefore safely accept and respend new VTXOs without waiting for the next onchain commitment. Building on this observation, we introduce a mechanism that enforces this behaviour economically: a rational operator that double-signs stands to lose more than it can gain. Concretely, consider a set 𝑁 ff of Ark users who opt in to transact with fast finality, and assume the following additions to the model of §2: (A1) 𝑂 is rational, i.e., maximising profit, (A2) there is an online committee of 𝑛 signers, with at least one honest signer. The committee is fixed throughout the Ark’s lifetime and its identities are known to all Ark users 6 , (A3) users in 𝑁 ff form a broadcast network where messages are delivered within the known time bound Δ. (A4) it is known to the users in 𝑁 ff that they collectively hold a value 𝑣 in VTXOs. We stress that participation in the fast finality scheme is entirely opt-in. Users who are unwilling to accept assumptions (A1)–(A4) can continue using the Ark protocol as presented before, where transaction finality reduces to that of the underlying blockchain.
4.1
Protocol Overview
The fast finality protocol requires 𝑂 to lock a collateral of value 𝑐 > 𝑣 in a UTXO that can either be spent by 𝑂 alone after a timelock 𝑡𝑝 , or burned immediately (e.g., via OP_RETURN) by a transaction signed by 𝑂 and cosigned by the 𝑛-of-𝑛 committee. By (A2), at least one committee member is honest, meaning it deletes its signing 6We leave for future work how to assemble the committee, and how to implement other designs such as rotating committees (see §7).
key after producing the burn transaction and ensures that this transaction is publicly available. This guarantees that before 𝑡𝑝 , the collateral can only be destroyed—and only by someone who knows 𝑂’s private key. We show in §4.2 how Schnorr nonce reuse enables private key extraction whenever 𝑂 double-signs. The protocol works as follows. Each user in 𝑁 ff maintains a local record of all Ark transactions it has observed, which we call an Ark ledger. By the broadcast assumption (A3), every Ark transaction reaches all users in 𝑁 ff within Δ. When a user receives a new VTXO via an Ark transaction, it broadcasts the transaction to 𝑁 ff , waits 2Δ to ensure no conflicting transaction surfaces, and only then accepts the payment. If a conflict is detected, either via the broadcast network or by monitoring the chain, the user extracts 𝑂’s private key from the two conflicting signatures (which share a committed nonce) and burns the collateral. The full protocol is given in Protocol 1; all output scripts along a VTXO’s path are modified to embed fixed nonce commitments as detailed in §4.2. Definition 4.1 (Ark ledger). An Ark ledger A is a set of Ark transactions that (i) carry valid witnesses for all their VTXO inputs, and (ii) spend only VTXOs that are either created by other transactions in A or committed to in a confirmed, unswept batch output. Note that A is an unordered set: the broadcast network disseminates transactions but does not impose a total order on them. Remark 4.2. Fast finality Ark transactions may have multiple VTXO inputs and outputs. The notion of path(vtxo) from Definition 3.2 therefore generalises: unilaterally exiting vtxo may require posting not only the virtual transactions from the batch, but also every fast finality Ark transaction in the chain leading to vtxo, potentially spanning multiple batches. Each user must therefore store the full transaction history relevant to its VTXOs. Security intuition. We claim that any user in 𝑁 ff who follows Protocol 1 cannot be defrauded, as long as 𝑐 > 𝑣. The 2Δ waiting period ensures that no two honest users in 𝑁 ff accept conflicting payments: if a conflict exists, at least one recipient will observe it before finalising. A malicious user who attempts to exit onchain with a conflicting transaction will be detected by the honest recipient monitoring the chain, triggering collateral burning. Since the burned amount 𝑐 exceeds the maximum gain 𝑣 from any doublesign, a rational operator will refrain from misbehaving. The same logic applies if the operator attempts to collude with a subset of batch cosigners to restructure the batches from which a fast finality VTXO originates. Finally, because collaborative spends take priority over unilateral spends (which are delayed by 𝑡𝑢 ), an honest user monitoring the chain can always preempt a previous VTXO owner attempting to reclaim already-spent funds. Remark 4.3. Our presentation assumes a fixed set 𝑁 ff . In practice, 𝑂 can periodically publish 𝑁 ff , either onchain or at a publicly accessible location with an onchain commitment, specifying how to reach each participating user. The only power this grants 𝑂 is determining which users can safely accept fast finality payments; each honest user independently verifies its own membership. The design extends naturally to a dynamic 𝑁 ff , with 𝑂 publishing updated sets and adding collateral as needed.
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
Protocol 1 Fast finality protocol for an Ark user 𝑃1 . 1: Check that 𝑃 1
occurs in 𝑁 ff .
checks that the provided Schnorr signature under public key 𝑝𝑘 uses the committed nonce 𝑅 ∗ :
2: while 𝑃 1 holds vtxo not committed to in a confirmed batch do
OP_DUP OP_DUP 𝑝𝑘 OP_CHECKSIGVERIFY
Monitor the chain for transactions 4: conflicting with path(vtxo) 5: if such a tx* appears, conflicting with tx then 6: Extract 𝑂’s private key from tx and tx* and 7: burn the operator collateral 8: end if 9: end while 10: To spend vtxo in txark to 𝑃 2 : 11: Proceed as in Figure 3, with 𝑃 1 Alice and 𝑃 2 Bob, 12: except that 𝑃 2 does not request a batch swap. 13: When receiving a message 𝑝 = (txark , txre , path(vtxo)): 14: if 𝑃 1 is the payment recipient then 15: for all tx ∈ path(vtxo) do 16: Reject the payment if any out ∈ tx.ins has an incorrect 17: output script (see §4.2) 18: Reject the payment if the sender of tx is not in 𝑁 ff . 19: end for 20: Reject the payment if vtxo has an incorrect output script 21: (see §4.2) or if the sender is not in 𝑁 ff 22: Broadcast 𝑝 to 𝑁 ff 23: Wait 2Δ 24: end if 25: if 𝑝 does not conflict with 𝑃 1 ’s Ark ledger A or the chain then 26: Add txark and txre to A 27: if 𝑃 1 is the payment recipient then 28: Accept payment 29: end if 30: else 31: Extract 𝑂’s private key from the conflict and 32: burn the collateral 33: if 𝑃 1 is the payment recipient then 34: Reject payment 35: end if 36: end if
𝑅 ∗ ∥0032 OP_GREATERTHANEQUAL OP_SWAP
3:
4.2
Private key extraction
To burn the operator’s collateral, one must sign the burn transaction with the operator’s private key. We present a mechanism that reveals this key upon operator misbehaviour. Unlike key extraction schemes such as accountable assertions [48] or DAPS-based constructions [23], our mechanism is implementable in Bitcoin today. It exploits Schnorr signature nonce reuse: given two valid signatures 𝜎1,2 = (𝑅1,2, 𝑠 1,2 ) on distinct messages 𝑚 1 ≠ 𝑚 2 under the same key 𝑝𝑘, the secret key 𝑠𝑘 can be recovered whenever 𝑅1 = 𝑅2 (see Appendix C for details). We construct VTXOs so that their collaborative path requires 𝑂’s signature with a fixed nonce commitment 𝑅 ∗ embedded in the script. If 𝑂 ever cosigns two different transactions spending the same VTXO, the reused nonce reveals 𝑠𝑘, enabling anyone to burn the collateral. Concretely, the collaborative script additionally7 7 For now we would have to verify the user’s signature separately. Combining nonce commitments with key aggregation is left for future work.
𝑅 ∗ ∥FF32 OP_LESSTHANEQUAL OP_AND. An honest receiver accepts a fast finality payment only if the received Ark transaction and all its predecessors spend VTXOs whose collaborative paths commit to specific nonces, and the batch output(s) and VTXT transaction outputs leading to the original committed VTXOs include this script as well. If 𝑂 later doublesigns any output along the path, anyone holding both signatures can extract the private key and execute the burn transaction.
5
Security Analysis
This section argues informally why Ark satisfies the properties of §2.3. Formal definitions and proofs of the security properties are deferred to Appendix E. VTXO Security, Theorem E.7. (i) Safety. Any vtxo in a confirmed, unexpired batch cannot be spent without a valid witness, as long as one cosigner on path(vtxo) is honest. An honest cosigner never signs conflicting transactions, emulating a covenant: before expiry, a VTXO is either exited unilaterally or spent collaboratively with 𝑂, in which case it is only considered spent when there is a valid Ark or forfeit transaction, requiring a valid witness. (ii) Liveness. For any vtxo in a confirmed batch, if at least one cosigner on path(vtxo) is honest so that vtxo remains unspent, then anyone knowing path(vtxo) can broadcast it to exit unilaterally. This is safe up to 2𝑘 (blockchain depth parameter) blocks before batch expiry to ensure all transactions in the path confirm onchain. Ark Atomicity, Theorem E.12. For any action involving an honest party (user or operator), either the state changes exactly as intended or not at all. We show this by going through each honest Ark action and making sure honest participants can abort at any time upon detecting misbehaviour and only provide witnesses for transactions they approve, ruling out partial execution. Balance Security, Theorems E.10 and E.13. (For a user) A user’s balance consists of funds in boarding outputs and VTXOs that can be claimed without 𝑂’s help (formally defined in Appendix E). Applying VTXO Security ensures that an honest user, holding the necessary paths, can always reclaim these funds via unilateral exit. (For an operator) 𝑂 funds each commitment but eventually reclaims its inputs once the commitment expires. By atomicity, every coin spent by an honest operator corresponds to at least as much recoverable value in the sweep. Tracking all flows shows that after a phase of serving exits, all operator funds return. Fast Finality, Theorem E.18. Because of the broadcast network between honest users in 𝑁 ff , each double-spend to two honest users will be detected and rejected. The only way in which a doublespend can occur after an honest user finalised a payment is if the malicious sender tries to exit unilaterally with either a conflicting VTXO, or an already spent VTXO. In both cases, the honest user will detect this, and respectively burn the operator collateral, or spend the spent VTXO with the corresponding (collaboratively signed) Ark transaction. Because the operator has to fund the collateral,
Ark: Offchain Transaction Batching in Bitcoin
which exceeds the potential gains from double-signing, and since the operator is assumed rational, it will refrain from double-signing. Scalability. (i) Constant Updates. A batch can in principle commit to an arbitrarily large VTXT. Only the root of the tree appears onchain as part of the commitment transaction. The connector output can also contain arbitrarily many connectors. Note, however, that to confirm each successive VTXO spend, the new VTXO must appear in its own batch, requiring an additional onchain commitment. (ii) Constant optimistic exit. With a cooperating operator, a user can exit multiple VTXOs collaboratively as an additional output in a commitment transaction. (iii) Logarithmic pessimistic exit. A unilateral exit requires posting path(vtxo), which has length O (log 𝑛) in a VTXT with 𝑛 VTXOs as its leaves. If vtxo is an output in a (fast finality) Ark transaction, the unilateral exit costs increase. Indeed, all offchain Ark transactions need to be posted onchain as well in order for vtxo the transaction containing vtxo to be valid.
6
Onchain footprint. The experiment also produces the commitment transaction and the batch’s VTXT, from which we extract transaction sizes via PSBT9 data (see Appendix B). Examining path(vtxo) for any VTXO in the batch, we observe consistent sizes: 107 vB for the leaf transaction (P2TR10 VTXO output and one anchor11 ), and 150 vB for each intermediate virtual transaction (two P2TR outputs and one anchor11 ). With fast finality, each additional Ark transaction along the path incurs a comparable cost. The commitment transaction itself (comprising a change output, a batch output, and a connector output, all P2TR) is 197 vB. As a concrete example, at a fee rate of 6 sat/vB (1B = 108 sat), unilaterally exiting a VTXO from a batch of 𝑛 = 128 costs 6 · (⌈log 128⌉ · 150 + 107) = 6,942 sat (which is approx. $4.58 at the time of writing). Comparison with other protocols. Table 3 summarizes how Ark’s onchain costs compare to other Bitcoin offchain protocols across three dimensions: commitment size (where applicable), cooperative exit cost, and unilateral exit cost.
Implementation and Evaluation
We implemented the Ark protocol as an open-source mainnet system8 , incorporating the reset transaction scheme introduced in §3.5 to defend against the hostage and spam attacks. Using this implementation, we experimentally evaluate two aspects: the time required to construct a commitment transaction as a function of the number of users, and the onchain footprint of commitments and unilateral exits. Commitment construction time. We measure the time to finalize a commitment transaction when 𝑂 receives exactly one batch swap request from each of 𝑛 users, for 𝑛 ∈ {21, . . . , 27, 200}. Table 2 reports the duration of three phases: (BC) 𝑂 builds the commitment transaction (one batch, one connector) and distributes it to all users; (SS) all MuSig2 signing sessions for the virtual transactions in the batch’s VTXT are completed; and (FF) users construct and fully sign forfeit transactions with 𝑂. Signing the commitment transaction itself took 𝑂 on average 0.023 seconds. Table 2: Execution times 𝑡 in seconds per value of 𝑛 for each phase (with 𝑅 2 for linear regression 𝑡 = 𝑎 0 + 𝑎 1𝑛, and 𝑝-value for 𝐻 0 : 𝑎 1 = 0 against 𝐻 1 : 𝑎 1 ≠ 0). 𝑡 (𝑛) 2 4 8 16 32 64 128 200 𝑅 2 𝑝 BC 0.030 0.049 0.053 0.080 0.084 0.220 0.427 0.806 0.981 2.25e-6 SS 0.190 0.194 0.200 0.219 0.333 0.388 0.707 1.075 0.991 2.01e-7 FF 0.114 0.123 0.132 0.169 0.224 0.370 0.556 0.831 0.998 4.71e-9 All three phases grow linearly in 𝑛, consistent with the O (𝑛) complexity of MuSig2 [40]. At 𝑛 = 200, users must be online simultaneously for approximately 2.7 seconds. In practice, users submit requests over time and may go offline between rounds; 𝑂 collects pending requests and initiates the commitment protocol once its batching policy triggers, prompting the relevant users to reconnect. A key advantage of Ark is that only users involved in a given update need to participate, allowing 𝑂 to produce smaller, more frequent batches. We note that the experiment operates with minimal network delay; real-world latency would increase these times.
Table 3: Onchain cost comparison across Bitcoin offchain protocols. Here 𝑛 denotes the batch/clique size, ℎ the number of in-flight HTLCs (for a single channel), and 𝑑 the depth of the user’s UTXO in Spark. Protocol Commit. (vB) Coop. exit Unilat. exit (vB) Ark 197 +1 output ⌈log 𝑛⌉ · 150 + 107 — O (1) ℎ · 43 + 181 Lightning [33] Spark [51] — O (1) (𝑑 + 3) · 315 CoinPool O (1) O (1) O (1) O (1) +1 output O (log 𝑛) Bitcoin Clique For commitment transactions, only CoinPool and Bitcoin Clique have comparable constructions with a constant number of outputs. Lightning and Spark do not have commitments in the sense that their onchain footprints do not batch an arbitrary number of UTXOs. CoinPool achieves constant cooperative/unilateral exit cost, as the user spends a shared UTXO and creates only two outputs. Bitcoin Clique’s unilateral exit cost grows logarithmically in the clique size, analogous to Ark’s scaling in the batch size. Both Clique and Ark require one output in a commitment per cooperative exit. Lightning’s unilateral exit cost depends on in-flight HTLCs, while Spark’s cost scales linearly in the UTXO depth 𝑑. This is analogous to Ark with fast finality, although Ark transactions can be smaller in size. Moreover, Ark’s batch swap mechanism allows users to reset the path length, reducing exit to only the VTXT transactions.
7
Discussion, Limitations, and Future Work
Operator Centralisation. Ark relies on a single operator to coordinate offchain transactions, manage liquidity, and produce commitments. This introduces a centralisation risk at odds with Bitcoin’s decentralised ethos. While unilateral exit ensures users can always reclaim funds, the operator remains a single point of failure: if unavailable or adversarial, performance degrades and onchain costs rise. Future work could explore multi-operator designs via 9 Partially Signed Bitcoin Transaction format. 10 Pay To Taproot output.
8 https://github.com/ark4fish/ARK
11 For onchain fee management.
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
federation or cryptographic coordination, and examine how the operator’s roles (funding, signing, batching) might be distributed across multiple parties. Liquidity Requirements. The operator must commit upfront capital to fund each batch, recoverable only at batch expiry together with any fees collected. Future work should quantify liquidity needs under realistic market conditions and develop trustminimised mechanisms for external liquidity providers to fund commitments. This, together with appropriately designed fee structures, could position Ark liquidity provision as a Bitcoin-native, near risk-free return on capital, attracting sufficient supply. Collateral Requirements for Fast Finality. Beyond operational liquidity, the fast finality mechanism requires the operator to lock collateral exceeding the total value held by opt-in users, ensuring that double-signing is always unprofitable. The opportunity cost of this lock-up must be covered by fees, and its sustainability under varying adoption levels remains an open question. Future work should analyse fee mechanisms that make the collateral economically viable, and explore alternative deterrence approaches that reduce the required amount, for example by accounting for the operator’s loss of future revenue. Honest operator behaviour could also be enforced via TEEs, which may present an acceptable trust trade-off for fast finality users. Fast Finality Committee. The fast finality mechanism relies on a signer committee with at least one honest member to ensure that the operator’s collateral can only be burned, not redirected. This existential honesty assumption is not unique to Ark: it is the same trust model underlying BitVM2 [34] and is, to the best of our knowledge, inherent to any punishment mechanism on Bitcoin today in the absence of covenant opcodes. Native covenant support would remove the need for a committee entirely, as the burn condition could be enforced directly in script. Within the current design, open questions remain around committee selection (e.g., stake-weighted membership with penalties for liveness failures) and rotation. Since signers delete their keys after setup, modifying an existing committee is inherently difficult. A natural approach for Ark would be to align rotation with batch expiry: as VTXOs must be periodically refreshed regardless, a new committee can be introduced with each batch cycle without additional user overhead. Onchain Cost of Unilateral Exit. Unilateral exits require broadcasting O (log 𝑛) virtual transactions, and fast finality increases this cost further since all preceding Ark transactions must also appear onchain. Small VTXO holders may be priced out. Compared to rollups, which post all transaction data onchain by default, this is an improvement; compared to Lightning, whose exit cost per channel grows only with in-flight HTLCs, it is worse in absolute terms. However, the Ark operator is designed to remain continuously online (similar to a payment channel hub), making unilateral exits less frequent in practice. Future work should explore VTXT designs that reduce exit costs and evaluate policies limiting successive Ark spends before a mandatory batch swap. Miner Extractable Value (MEV). The operator controls request scheduling and VTXO grouping, granting sequencing power analogous to a rollup sequencer. However, Ark does not introduce new scripting capabilities: the operator cannot reorder or insert transactions with programmable side effects. Its influence is limited to
delaying or censoring requests, which is already possible in Bitcoin itself, and is mitigated by unilateral exit. Richer application logic built on top of Ark (e.g., via BitVM [1, 34]) could introduce application-level MEV, but this remains architecturally sandboxed: Ark handles VTXO transfers, while application semantics are enforced offchain via fraud proofs, and BitVM does not grant the operator additional control over execution order. Bank Run Scenario. As with other Layer-2 protocols, a worst-case scenario for Ark is a bank run in which many users exit simultaneously, producing a transaction surge proportional to the number of VTXOs in the affected batches. Given Bitcoin’s limited throughput, this may delay exits; users should therefore initiate unilateral exits well before batch expiry to avoid race conditions with operator sweeps. Future work should quantify how quickly a bank run can be resolved onchain as a function of the number of exiting VTXOs. We note, however, that this scenario can be avoided entirely when the operator remains cooperative: as shown in §3.6, users can migrate their VTXOs to a new Ark offchain, allowing a controlled wind-down with no unilateral exit footprint. Rational Security Analysis. Under a rational miner model [2], Ark becomes vulnerable to timelock bribing [36]: a colluding operator could pay miners to censor a user’s unilateral exit until batch expiry, then sweep the funds. Integrating bribe-resistant constructions [19, 54, 55] or deriving tighter time bounds under fine-grained rational models [8] are important future directions. More broadly, our analysis assumed the operator is simply present and showed that it cannot violate economic safety (unless miners are rational) and can only censor users into exiting onchain. This censoring power is particularly relevant for batch swaps, which must occur at least once per VTXO per expiry period. In practice, however, operators will be profit-driven entities whose operational and capital costs, including the opportunity cost of locked liquidity and the fees needed to attract external providers, must be covered by user fees. Future work should devise fee mechanisms that make operating an Ark profitable while incentivising responsive behaviour.
8
Conclusion
We presented Ark, the first Bitcoin-compatible commit-chain. Ark enables offchain transactions of virtual UTXOs through an untrusted operator who batches them into succinct onchain commitments. Unlike payment channel networks, Ark allows receivers to onboard entirely offchain and requires only the involved users, rather than all participants, to coordinate each state update. We formally defined the protocol, proved VTXO security, atomicity, and balance security for both users and the operator, and showed how an opt-in fast finality mechanism can eliminate the need to wait for onchain confirmation under a rational operator. Our security analysis uncovered two vulnerabilities in the original protocol, the hostage and spam attacks, which we resolved via the so-called reset transactions that are now integrated into an open-source mainnet implementation. Experimentally, we showed that Ark commits to arbitrarily many VTXOs with a constant 197 vB onchain footprint, achieves cooperative exits at constant cost, and bounds unilateral exit cost to ⌈log 𝑛⌉ · 150 + 107 vB for a batch of 𝑛 VTXOs, with commitment construction completing in 2.7 seconds for 200 users.
Ark: Offchain Transaction Batching in Bitcoin
Acknowledgements The original version of the Ark protocol was conceptualised by Burak [15]. Our work builds on his idea, which required covenants, making it Bitcoin-compatible. This research was partially funded by Ark Labs, by the European Research Council (ERC) under the European Union’s Horizon 2020 research (grant agreement 101141432BlockSec), by the Austrian Science Fund (FWF) through the SFB SpyCode project F8510-N and F8512-N, and by the WWTF through the projects 10.47379/ICT22045 and 10.47379/ICT25056. Finally, we thank Christos Stefo and Yuheng Wang for insightful discussions.
References [1] Lukas Aumayr, Zeta Avarikioti, Robin Linus, Matteo Maffei, Andrea Pelosi, Christos Stefo, and Alexei Zamyatin. 2024. BitVM: Quasi-Turing Complete Computation on Bitcoin. Cryptology ePrint Archive (2024). [2] Lukas Aumayr, Zeta Avarikioti, Matteo Maffei, and Subhra Mazumdar. 2024. Securing Lightning Channels against Rational Miners. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security (Salt Lake City, UT, USA) (CCS ’24). Association for Computing Machinery, New York, NY, USA, 393–407. doi:10.1145/3658644.3670373 [3] Lukas Aumayr, Zeta Avarikioti, Matteo Maffei, Giulia Scaffino, and Dionysis Zindros. 2024. Blink: An optimal proof of proof-of-work. Cryptology ePrint Archive (2024). [4] Lukas Aumayr, Oguzhan Ersoy, Andreas Erwig, Sebastian Faust, Kristina Hostáková, Matteo Maffei, Pedro Moreno-Sanchez, and Siavash Riahi. 2021. Generalized channels from limited blockchain scripts and adaptor signatures. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 635–664. [5] Lukas Aumayr, Matteo Maffei, Oğuzhan Ersoy, Andreas Erwig, Sebastian Faust, Siavash Riahi, Kristina Hostáková, and Pedro Moreno-Sanchez. 2021. Bitcoincompatible virtual channels. In 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 901–918. [6] Georgia Avarikioti, Eleftherios Kokoris Kogias, Roger Wattenhofer, and Dionysis Zindros. 2019. Brick: Asynchronous payment channels. arXiv preprint arXiv:1905.11360 (2019). [7] Zeta Avarikioti, Mahsa Bastankhah, Mohammad Ali Maddah-Ali, Krzysztof Pietrzak, Jakub Svoboda, and Michelle Yeo. 2024. Route Discovery in Private Payment Channel Networks. In Computer Security. ESORICS 2024 International Workshops - DPM, CBT, and CyberICPS, Bydgoszcz, Poland, September 16-20, 2024, Revised Selected Papers, Part I (Lecture Notes in Computer Science), Joaquín García-Alfaro, Ken Barker, Guillermo Navarro-Arribas, Cristina Pérez-Solà, Sergi Delgado-Segura, Sokratis K. Katsikas, Frédéric Cuppens, Costas Lambrinoudakis, Nora Cuppens-Boulahia, Marek Pawlicki, and Michal Choras (Eds.). Springer, 207–223. doi:10.1007/978-3-031-82349-7_15 [8] Zeta Avarikioti, Georg Fuchsbauer, Pim Keer, Matteo Maffei, and Fabian Regen. 2025. A Composable Game-Theoretic Framework for Blockchains. arXiv preprint arXiv:2504.18214 (2025). [9] Zeta Avarikioti, Krzysztof Pietrzak, Iosif Salem, Stefan Schmid, Samarth Tiwari, and Michelle Yeo. 2022. Hide & Seek: Privacy-Preserving Rebalancing on Payment Channel Networks. In Financial Cryptography and Data Security - 26th International Conference, FC 2022, Grenada, May 2-6, 2022, Revised Selected Papers (Lecture Notes in Computer Science), Ittay Eyal and Juan A. Garay (Eds.). Springer, 358–373. doi:10.1007/978-3-031-18283-9_17 [10] Zeta Avarikioti, Stefan Schmid, and Samarth Tiwari. 2024. Musketeer: IncentiveCompatible Rebalancing for Payment Channel Networks. In 6th Conference on Advances in Financial Technologies, AFT 2024, Vienna, Austria, September 2325, 2024 (LIPIcs), Rainer Böhme and Lucianna Kiffer (Eds.). Schloss Dagstuhl Leibniz-Zentrum für Informatik, 13:1–13:22. doi:10.4230/LIPICS.AFT.2024.13 [11] Zeta Avarikioti, Orfeas Stefanos Thyfronitis Litos, and Roger Wattenhofer. 2020. Cerberus Channels: Incentivizing Watchtowers for Bitcoin. In Financial Cryptography and Data Security: 24th International Conference, FC 2020 , Kota Kinabalu, Malaysia, February 10–14, 2020 Revised Selected Papers. Springer-Verlag, Berlin, Heidelberg, 346–366. doi:10.1007/978-3-030-51280-4_19 [12] Zeta Avarikioti, Yuheng Wang, and Yuyi Wang. 2025. Thunderdome: TimelockFree Rationally-Secure Virtual Channels. arXiv preprint arXiv:2501.14418 (2025). [13] Adam Back, Matt Corallo, Luke Dashjr, Mark Friedenbach, Gregory Maxwell, Andrew Miller, Andrew Poelstra, Jorge Timón, and Pieter Wuille. 2014. Enabling blockchain innovations with pegged sidechains. URL: http://www. opensciencereview. com/papers/123/enablingblockchain-innovations-with-pegged-sidechains 72 (2014), 201–224. [14] Bitcoin Optech. 2025. Cluster mempool. https://bitcoinops.org/en/topics/clustermempool/. accessed: 2025-09-21.
[15] Burak. 2023. Introducing Ark. https://brqgoo.medium.com/introducing-ark6f87ae45e272 [16] Conrad Burchert, Christian Decker, and Roger Wattenhofer. 2018. Scalable funding of bitcoin micropayment channel networks. Royal Society open science 5, 8 (2018), 180089. [17] Cashu. 2025. Cashu is Ecash for Bitcoin. https://docs.cashu.space/ [18] David Chaum. 1983. Blind signatures for untraceable payments. In Advances in Cryptology: Proceedings of Crypto 82. Springer, 199–203. [19] Hao Chung, Elisaweta Masserova, Elaine Shi, and Sri AravindaKrishnan Thyagarajan. 2022. Ponyta: Foundations of side-contract-resilient fair exchange. Cryptology ePrint Archive (2022). [20] Jeff Coleman. 2015. State Channels. https://www.jeffcoleman.ca/state-channels/ [21] Christian Decker, Rusty Russell, and Olaoluwa Osuntokun. 2018. eltoo: A simple layer2 protocol for bitcoin. White paper: https:// blockstream.com/ eltoo.pdf (2018). [22] Christian Decker and Roger Wattenhofer. 2015. A fast and scalable payment network with bitcoin duplex micropayment channels. In Stabilization, Safety, and Security of Distributed Systems: 17th International Symposium, SSS 2015, Edmonton, AB, Canada, August 18-21, 2015, Proceedings 17. Springer, 3–18. [23] Xinshu Dong, Orfeas Stefanos Thyfronitis Litos, Ertem Nusret Tas, David Tse, Robin Linus Woll, Lei Yang, and Mingchao Yu. 2024. Remote Staking with Economic Safety. arXiv preprint arXiv:2408.01896 (2024). [24] Stefan Dziembowski, Lisa Eckey, Sebastian Faust, Julia Hesse, and Kristina Hostáková. 2019. Multi-party virtual state channels. In Annual international conference on the theory and applications of cryptographic techniques. Springer, 625–656. [25] Stefan Dziembowski, Lisa Eckey, Sebastian Faust, and Daniel Malinowski. 2019. Perun: Virtual payment hubs over cryptocurrencies. In 2019 IEEE symposium on security and privacy (SP). IEEE, 106–123. [26] Fedimint. 2025. Fedimint. https://fedimint.org/docs/intro [27] Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. 2024. The Bitcoin Backbone Protocol: Analysis and Applications. J. ACM (apr 2024). doi:10.1145/3653445 [28] Mike Hearn and Jeremy Spillman. 2023. Contract. https://en.bitcoin.it/wiki/ Contract. accessed: 2025-09-20. [29] Ethan Heilman, Leen Alshenibr, Foteini Baldimtsi, Alessandra Scafuro, and Sharon Goldberg. 2017. Tumblebit: An untrusted bitcoin-compatible anonymous payment hub. In Network and distributed system security symposium. [30] Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S Matthew Weinberg, and Edward W Felten. 2018. Arbitrum: Scalable, private smart contracts. In 27th USENIX Security Symposium (USENIX Security 18). 1353–1370. [31] Rami Khalil, Alexei Zamyatin, Guillaume Felley, Pedro Moreno-Sanchez, and Arthur Gervais. 2018. Commit-chains: Secure, scalable off-chain payments. Cryptology ePrint Archive (2018). [32] Aggelos Kiayias and Dionysis Zindros. 2019. Proof-of-work sidechains. In International Conference on Financial Cryptography and Data Security. Springer, 21–34. [33] Lightning Network. 2023. BOLT #3. https://github.com/lightning/bolts/blob/ master/03-transactions.md. accessed: 2025-09-21. [34] Robin Linus, Lukas Aumayr, Zeta Avarikioti, Matteo Maffei, Andrea Pelosi, Orfeas Thyfronitis Litos, Christos Stefo, David Tse, and Alexei Zamyatin. 2025. Bridging Bitcoin to Second Layers via BitVM2. Cryptology ePrint Archive, Paper 2025/1158. https://eprint.iacr.org/2025/1158 [35] Andrew Miller, Iddo Bentov, Surya Bakshi, Ranjit Kumaresan, and Patrick McCorry. 2019. Sprites and state channels: Payment networks that go faster than lightning. In International conference on financial cryptography and data security. Springer, 508–526. [36] Tejaswi Nadahalli, Majid Khabbazian, and Roger Wattenhofer. 2021. Timelocked Bribing. In Financial Cryptography and Data Security: 25th International Conference, FC 2021, Virtual Event, March 1–5, 2021, Revised Selected Papers, Part I. Springer-Verlag, Berlin, Heidelberg, 53–72. doi:10.1007/978-3-662-64322-8_3 [37] Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. [38] Gleb Naumenko and Antoine Riard. [n. d.]. CoinPool: efficient off-chain payment pools for Bitcoin. https://coinpool.dev/v0.1.pdf [39] Jonas Nick, Andrew Poelstra, and Gregory Sanders. 2020. Liquid: A bitcoin sidechain. Liquid white paper. URL https://blockstream. com/assets/downloads/pdf/liquid-whitepaper. pdf (2020). [40] Jonas Nick, Tim Ruffing, and Yannick Seurin. 2020. MuSig2: Simple Two-Round Schnorr Multi-Signatures. Cryptology ePrint Archive, Paper 2020/1261. doi:10. 1007/978-3-030-84242-0_8 [41] Optimism. 2021. Optimistic Rollup Overview. https://github.com/ethereumoptimism/optimistic-specs/blob/0e9673af0f2cafd89ac7d6c0e5d8bed7c67b74ca/ overview.md [42] Alejandro Ranchal Pedrosa, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni. 2019. Scalable lightning factories for bitcoin. In Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing. 302–309. [43] Joseph Poon and Vitalik Buterin. 2017. Plasma: Scalable autonomous smart contracts. White paper (2017), 1–47. [44] Joseph Poon and Thaddeus Dryja. 2016. The bitcoin lightning network: Scalable off-chain instant payments.
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
[45] Xianrui Qin, Shimin Pan, Arash Mirzaei, Zhimei Sui, Oğuzhan Ersoy, Amin Sakzad, Muhammed F Esgin, Joseph K Liu, Jiangshan Yu, and Tsz Hon Yuen. 2023. Blindhub: Bitcoin-compatible privacy-preserving payment channel hubs supporting variable amounts. In 2023 IEEE symposium on security and privacy (SP). IEEE, 2462–2480. [46] Siavash Riahi and Orfeas Stefanos Thyfronitis Litos. 2024. Bitcoin Clique: Channel-free Off-chain Payments using Two-Shot Adaptor Signatures. Cryptology ePrint Archive, Paper 2024/025. https://eprint.iacr.org/2024/025 [47] Stefanie Roos, Pedro Moreno-Sanchez, Aniket Kate, and Ian Goldberg. 2018. Settling Payments Fast and Private: Efficient Decentralized Routing for PathBased Transactions. In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-21, 2018. The Internet Society. https://www.ndss-symposium.org/wp-content/uploads/2018/ 02/ndss2018_09-3_Roos_paper.pdf [48] Tim Ruffing, Aniket Kate, and Dominique Schröder. 2015. Liar, liar, coins on fire! Penalizing equivocation by loss of bitcoins. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 219–230. [49] Vibhaalakshmi Sivaraman, Shaileshh Bojja Venkatakrishnan, Kathleen Ruan, Parimarjan Negi, Lei Yang, Radhika Mittal, Giulia Fanti, and Mohammad Alizadeh. 2020. High Throughput Cryptocurrency Routing in Payment Channel Networks. In 17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020, Santa Clara, CA, USA, February 25-27, 2020, Ranjita Bhagwan and George Porter (Eds.). USENIX Association, 777–796. https://www.usenix.org/ conference/nsdi20/presentation/sivaraman [50] Ruben Somsen. 2018. Statechains: Off-chain Transfer of UTXO Ownership. [51] Spark. [n. d.]. Spark Documentation. https://docs.spark.money/ [52] Erkan Tairi, Pedro Moreno-Sanchez, and Matteo Maffei. 2021. A 2 l: Anonymous atomic locks for scalability in payment channel hubs. In 2021 IEEE symposium on security and privacy (SP). IEEE, 1834–1851. [53] Samarth Tiwari, Michelle Yeo, Zeta Avarikioti, Iosif Salem, Krzysztof Pietrzak, and Stefan Schmid. 2022. Wiser: Increasing Throughput in Payment Channel Networks with Transaction Aggregation. In Proceedings of the 4th ACM Conference on Advances in Financial Technologies, AFT 2022, Cambridge, MA, USA, September 19-21, 2022, Maurice Herlihy and Neha Narula (Eds.). ACM, 217–231. doi:10.1145/3558535.3559775 [54] Itay Tsabary, Matan Yechieli, Alex Manuskin, and Ittay Eyal. 2021. MAD-HTLC: because HTLC is crazy-cheap to attack. In 2021 IEEE symposium on security and privacy (SP). IEEE, 1230–1248. [55] Sarisht Wadhwa, Jannis Stoeter, Fan Zhang, and Kartik Nayak. 2022. He-htlc: Revisiting incentives in htlc. Cryptology ePrint Archive (2022). [56] Pieter Wuille, Jonas Nick, and Anthony Towns. 2020. Taproot: SegWit version 1 spending rules. https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki
A
Global Parameters, Notation and Commitment Transaction Construction Table A.1: Global parameters and Notation 𝑃, 𝑂 tx, out vtxo 𝑄
L𝑄 , L −𝑘 𝑡𝑏 𝑡𝑒
𝑡𝑢 𝜀 𝑘, 𝑢 L𝑄 (𝑟 ), 𝑄 L −𝑘 (𝑟 ) L1 ⪯ L2
Ark user and Ark operator Transaction, transaction output Virtual transaction output Local view of party 𝑄, with and without latest 𝑘 blocks, denote inclusion by tx ∈ L 𝑃 (or out ∈ L 𝑃 for unspent outputs) Boarding timeout: unilateral recovery delay for boarding funds Batch expiry time: minimum number of blocks before batch expires VTXO unilateral delay: minimum delay of a VTXO unilateral script path compared to any collaborative script path Dust-sized value of anchor outputs Ledger depth/wait parameters as defined in [27] Local view of party 𝑄 at round 𝑟 , with and without latest 𝑘 blocks, as in [27], used only in Appendix E, denote inclusion just as before L 1 is a prefix of L 2
B
Commitment transactions and VTXTs
As an example, let us look at the commitment transaction created by our experiment in §6 for 𝑛 = 2. The commitment transaction can be found on Mutinynet at: https://mutinynet.com/ by searching for the transaction ID 3fd6ddc344170c6ba90abb5a6ae7e4aaa1ca94c2 78de1501aba34fb7738740d3. One can see one large input, as well as one large change output, together with a batch output of 10000 sat and a connector output of 660 sat. The connector output consists of two dust value (330 sat) outputs. The batch commits to two VTXOs, one of 8000 sat and one of 2000 sat. Below, we share the transactions in PSBT format for conciseness. These can easily be decoded into JSON via a website such as https://chainquery.com/bitcoin-cli/decodepsbt: • VTXT Root, spending the batch output and having 2 P2TR outputs for the leaf transactions, and one anchor output: cHNidP 8BAJYDAAAAAdNAh3O3T6OrARXeeMKUyqGq5OdqWrsKqWsMF0TD3 dY/AAAAAAD/////A0AfAAAAAAAAIlEg1uuTP5t4SvcKMZtq4x3b 6J5dADh8hC4t+79wnvdQBkzQBwAAAAAAACJRIHaEDwnIyDSOyHF f/jLuenc2dJ1lRTh4LnlMw7wVjN5lAAAAAAAAAAAEUQJOcwAAAA AAARNAyBga5bp6IDKv35ReC9Nqn0lDvB6Km2uitFQC88HNBkRvr SBQotq8004h1E9+pNUVM9VO6mg8q74vRJDwvnHZewxjb3NpZ25l cgAAAAAhAlWozfpWDEPyugdJ95dGUrYTUFjZVaqhCezPp8QKtyU SDGNvc2lnbmVyAAAAASEChNDc7qODfpNp/P7KaCotiCExEw6RXc LIgJkm1HtwFO4MY29zaWduZXIAAAACIQKbjuy0+nlO9A5YxcUws NP7V/Tt56lculCTrhoZXbbWugZleHBpcnkDUztAAAAAAA== • Leaf 1, having the VTXO with value 8000 sat as output, together with an anchor: cHNidP8BAGsDAAAAAQdO2R6SLbqa1+KtulJ84a /0qnMC5t0XNkzacdHcdVSTAAAAAAD/////AkAfAAAAAAAAIlEg7 N6TSBPPzHXoOwvg7b5YxseoaDNxayBBQEmnhRvXLroAAAAAAAAA AARRAk5zAAAAAAABE0AYwVd0VW4mvU6RT1pdv+Nz1wAZ8nXmbxm sSooq2dj0VbHvmGe3sC7YzyXLEPhJ9PpLYnflBFMSSog/e/Cqy8 5pDGNvc2lnbmVyAAAAACECVajN+lYMQ/K6B0n3l0ZSthNQWNlVq qEJ7M+nxAq3JRIMY29zaWduZXIAAAABIQKE0Nzuo4N+k2n8/spo Ki2IITETDpFdwsiAmSbUe3AU7gZleHBpcnkDUztAAAAA • Leaf 2, having the VTXO with value 2000 sat as output, together with an anchor : cHNidP8BAGsDAAAAAQdO2R6SLbqa1+KtulJ84 a/0qnMC5t0XNkzacdHcdVSTAQAAAAD/////AtAHAAAAAAAAIlEg k4Bo7yqsimoNGhA5XrjZnY0HpJU6dY9coXomK4rSHi8AAAAAAAA AAARRAk5zAAAAAAABE0ASijnyUYyN6+A+ab+qpb7WUmz8ngKWaL pBqBiVcYUTCjuNwkERVqaOIVtsr/iETZ00kpEdae02Pvzwt+Jt7 ttiDGNvc2lnbmVyAAAAACECVajN+lYMQ/K6B0n3l0ZSthNQWNlV qqEJ7M+nxAq3JRIMY29zaWduZXIAAAABIQKbjuy0+nlO9A5YxcU wsNP7V/Tt56lculCTrhoZXbbWugZleHBpcnkDUztAAAAA
C
Schnorr Signatures and Nonce Reuse
We show that one can extract the private key from two Schnorr signatures of different messages under the same public key, using the same nonce. To this end, let us first recall the Schnorr signature scheme, which has been introduced to Bitcoin with the Taproot upgrade. Definition C.1 (Schnorr signatures scheme). Let 𝜆 be the security parameter. Consider the secp256k1 elliptic curve group 𝐸 with generator point 𝐺 with order 𝑞. The Schnorr signature scheme is defined as the triple (Gen, Sign, Vrfy), where
Ark: Offchain Transaction Batching in Bitcoin
• Gen(1𝜆 ) is the key generation algorithm, outputting a privatepublic key pair (𝑠𝑘, 𝑝𝑘), where 𝑠𝑘 ∈ Z𝑞 and 𝑝𝑘 = 𝑠𝑘𝐺, • Sign(𝑠𝑘, 𝑚) is the signing algorithm, outputting a signature 𝜎 = (𝑅, 𝑠) for a message 𝑚, where 𝑅 = 𝑟𝐺 for some randomly sampled 𝑟 ← Z𝑞 and 𝑠 = [𝑟 + 𝐻 (𝑅∥𝑝𝑘 ∥𝑚)𝑠𝑘 mod 𝑞], and • Vrfy(𝑝𝑘, 𝑚, 𝜎) is the verification algorithm, outputting 1 if 𝜎 is a valid signature of 𝑚 under 𝑝𝑘, and 0 otherwise. That is, Vrfy(𝑝𝑘, 𝑚, 𝜎) = 1 ⇐⇒ 𝑅 = 𝑠𝐺 − 𝐻 (𝑅∥𝑝𝑘 ∥𝑚)𝑝𝑘. One can retrieve the private key 𝑠𝑘 given two valid Schnorr signatures under 𝑝𝑘, denoted by (𝑅1, 𝑠 1 ) and (𝑅2, 𝑠 2 ), for messages 𝑚 1, 𝑚 2 (𝑚 1 ≠ 𝑚 2 ) whenever the nonce is reused, i.e., whenever 𝑅1 = 𝑅2 = 𝑟𝐺 for some 𝑟 ← Z𝑞 . Indeed, we have 𝑠1 − 𝑠2 = [𝑟 + 𝐻 (𝑅∥𝑝𝑘 ∥𝑚 1 )𝑠𝑘 − 𝑟 − 𝐻 (𝑅∥𝑝𝑘 ∥𝑚 2 )𝑠𝑘 mod 𝑞] = [(𝐻 (𝑅∥𝑝𝑘 ∥𝑚 1 ) − 𝐻 (𝑅∥𝑝𝑘 ∥𝑚 2 ))𝑠𝑘 mod 𝑞]. From this, we can retrieve the private key 𝑠1 − 𝑠2 𝑠𝑘 = mod 𝑞 . 𝐻 (𝑅∥𝑝𝑘 ∥𝑚 1 ) − 𝐻 (𝑅∥𝑝𝑘 ∥𝑚 2 ) We assume the denominator to be nonzero, as otherwise we would have found a collision of the hash function.
D
Detailed Protocol Specification
We start off by listing some conventions and simplifying assumptions: • We denote by batch(vtxo) the batch output containing vtxo. • A party 𝑃 can represents a single user or multiple users. We assume for simplicity that one entity communicates with the operator and can organise the users behind it to provide the necessary witnesses, and we assume that the view L 𝑃 of this entity is well-defined (for example that the multiple users represented by 𝑃 all agree on the state of the blockchain). • For any VTXO that has multiple spending conditions where different parties can provide witnesses satisfying one of these conditions, we assume that all these parties are aware of the state of this VTXO, i.e., whether for a given Ark state Σ = (𝐶, 𝐹, 𝑆), this VTXO is in 𝐶, 𝐹 , or 𝑆 (see Definition E.4. This is relevant for request routines (Routine 3, 5, 6, and 8), to ensure that honest users never make a request spending an already spent VTXO. Furthermore, recall that the lists vtxos and vtxos′ should be understood here as lists of tuples (value, vtxoLockScript), such that 𝑂 can read off all spending paths from vtxoLockScript. Of course, the locking script itself present in any transaction would only contain the tweaked public key committing to these spending paths. The protocol setup is minimal and presented in Routine 2. It only requires the Operator 𝑂 to let users know how they can create a boarding address, which boils down to 𝑂 sharing its public key 𝑝𝑘𝑂 and some other Ark-specific parameters, for example on a website. Apart from that, a number of empty lists are instantiated for the operator to keep track of user requests and VTXOs. Finally, 𝑂 defines a batching policy: a set of rules that specifies when and how 𝑂 should construct a commitment transaction. This policy may also be published. Users who want to board the Ark can now do so by sending a boarding request to the operator, as described in Routine 3. This
boarding request specifies a list of VTXOs which the user in question wants to add to the Ark. The Ark operator can now verify this boarding request, making sure that the UTXO specified in the request is not already spent, checking the locking script is of the correct form (in particular that there are no other spending paths), amongst others. This is specified in Routine 4. We can now also specify the other types of request users can make to the operator: batch swap requests (Routine 5), exit requests (Routine 6), Ark transaction requests (Routine 8), and their respective verification procedures (Routines 9, 10 and 11). For the Ark transaction, we also write out the procedure to send an Ark transaction to the receiver (Routine 12), and what checks the receiver should subsequently perform (Routine 13). Out of all of the received requests, the operator can select a number of them to construct a commitment, as detailed in Routine 14. The batch outputs of this transaction are specified by a batch template, which is a list of VTXTs (one for each batch output). How these VTXTs are constructed exactly is specified in the batching policy from Routine 2 and is up to the operator. It employs its own rules and optimisations to construct the VTXTs that go beyond this protocol specification. Of course, the VTXTs are constructed such that the obtained batch outputs satisfy Definition 3.3. Similarly, the connector outputs are specified by a connector template: a list of connector outputs, and a connector function 𝛾, mapping each VTXO that is being batch swapped or exited from to a leaf of one of the VTXTs in the connector template. The commitment produced by 𝑂 is still missing signatures. 𝑂 has to communicate with all the relevant parties, who will at least each individually check the commitment is valid (Routines 15, 16 and 19). Furthermore, parties who sent a boarding request or batch swap request should make sure their requested VTXOs are included in the batch template, and parties who sent a batch swap or exit request should find the anchor output in the connector template associated with their old VTXOs that are being swapped or exited. If every party convinced themselves that the commitment is correct, parties who sent a batch swap or exit request will produce forfeit transactions (Routine 17) that are only valid once the commitment holding the specific, corresponding anchor output is available onchain, and multiple signing sessions (Routine 7) will happen to produce witnesses for the commitment itself, and for the virtual transactions contained in the different batch outputs. All the steps to go from user requests to a fully signed commitment are gathered in Routine 23. At the end, the commitment can be broadcast, and the operator can update the various lists tracking VTXOs and open requests. This is specified in Routine 22. Finally, we specify the behaviour of honest parties, apart from how they should act when building commitment transactions. For the operator, this is done in Routine 24. For example, the operator has to monitor the chain for exited VTXOs and possibly respond by broadcasting the necessary reset and/or forfeit transactions. Other honest parties also have some tasks to perform, however not continuously. In Routine 25, we describe what a party wanting to spend a VTXO should do: first try to spend collaboratively, and if at some point this has still failed, exit unilaterally (Routine 20) and spend the created UTXO. In Routine 18, we give the steps the recipient of an Ark transaction should take.
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
Operator
Users ∀𝑖 ∈ 𝐼𝐵 : 𝑃𝑖 made boarding request 𝑟𝑖 = (𝑃𝑖 , out𝑖 ) ∀𝑖 ∈ 𝐼𝐸 : 𝑃𝑖 made exit request 𝑟𝑖 = (𝑃𝑖 , vtxo𝑖 ) ∀𝑖 ∈ 𝐼𝑆 : 𝑃𝑖 made batch swap request 𝑟𝑖 = (𝑃𝑖 , vtxo𝑖 ) 𝑂 receives over time all requests
Verify exit paths of out𝑖 𝑖 ∈𝐼 are invalid 𝐵
Construct a commitment transaction txcommit spending out𝑖 𝑖 ∈𝐼 and some funds of 𝑂, 𝐵
and with outputs a batch 𝛽, specified by a VTXT (𝑉 , 𝐴), a connector 𝛾 , with anchor outputs {𝜀𝑖 } 𝑖 ∈𝐼𝐸 ∪𝐼𝑆 , and UTXOs out𝑖 𝑖 ∈𝐼
𝐸
send txcommit
∀𝑖 ∈ 𝐼𝐵 :
and 𝛽 to 𝑃𝑖 𝑃𝑖 verifies txcommit and 𝛽 send txcommit
∀𝑖 ∈ 𝐼𝐸 :
and 𝛾 to 𝑃𝑖 𝑃𝑖 verifies txcommit and out𝑖 send txcommit
∀𝑖 ∈ 𝐼𝑆 :
𝛽, and 𝛾 to 𝑃𝑖 𝑃𝑖 verifies txcommit and 𝛽
∀vtx ∈ 𝑉 : Signing session for vtx, involving signers required by the design choice in Remark 3.4 After a successful session, everyone involved is capable of broadcasting a fully signed vtx onchain
∀𝑖 ∈ 𝐼𝐸 ∪ 𝐼𝑆 : 𝑃𝑖 constructs tx𝑖forfeit with vtxo𝑖 , 𝜀𝑖 as inputs and signs it, producing 𝜎𝑖𝐹 send tx𝑖forfeit , 𝜎𝑖𝐹
∀𝑖 ∈ 𝐼𝐵 : 𝑃𝑖 signs txcommit , producing 𝜎𝑖𝐶 send 𝜎𝑖𝐶 Broadcast txcommit with 𝐶 witnesses 𝜎𝑂 and {𝜎𝑖𝐶 }𝑖 ∈𝐼𝐵
Figure A.1: High-level construction of a commitment transaction from requests indexed by 𝐼𝐵 , 𝐼𝐸 , 𝐼𝑆 for boarding, exit, and batch swap request, respectively.
Ark: Offchain Transaction Batching in Bitcoin
Routine 2 Setup by Operator 𝑂 with public key 𝑝𝑘𝑂 . 1: 𝑂 publishes its public key 𝑝𝑘𝑂 , as well as the following Ark parameters:
• 𝑡𝑏 : Timeout period for boarding transaction output. • 𝑡𝑒 : Minimum amount of blocks that should pass before a batch expires. • 𝑡𝑢 : Minimum delay in VTXO unilateral script path. • 𝑡𝑟 : Time after which if the commitment transaction is still not included the operator will retry. 2: 𝑂 also instantiates the variables: • toBoard := [ ], the list of all boarding requests that have been verified by 𝑂 and can be added to a commitment transaction. • toBatchSwap := [ ], the list of all batch swap requests that have been verified by 𝑂 and can be added to a commitment transaction. • toExit := [ ], the list of all exit requests that have been verified by 𝑂 and can be added to a commitment transaction. • unconfirmed := [ ], the list of all VTXOs that are part of the batch output of a transaction which has not yet been confirmed onchain. • confirmedVTXO := [ ], the list of all VTXOs that are part of the batch output of a commitment transaction which has been confirmed onchain. • confirmedBatches := [ ], the list of all batch outputs that are part of a commitment transaction which has been confirmed onchain. • expired := [ ], the list all VTXOs that are part of a batch output of which the expiry timelock passed. • unconfirmedSpent := [ ], the list of all VTXOs that have been spent, either by an Ark transaction, or by a batch swap or exit in an unconfirmed commitment transaction. • spent := [ ], the list of all pairs (vtxo, tx) where vtxo could be spent onchain by a valid reset or forfeit transaction tx. • replaced := [ ], the list of all VTXOs that are part of the batch output of a transaction which has been double-spent or invalidated. • preSpent := [ ], the list of all VTXOs and boarding outputs spent in a yet unconfirmed boarding, batch swap, or exit request. • preConfirmed := [ ], the list of all VTXOs that are output from Ark transactions, but not yet batch swapped. • unconfirmedBoardings := [ ], unconfirmedBatchSwaps := [ ], and unconfirmedExits := [ ], the lists of all tuples of boarding, batch swap, and exit requests, respectively, with the fully signed, unconfirmed commitment transaction they have been processed in. • confirmedBoardings := [ ], confirmedBatchSwaps := [ ], confirmedExits := [ ], the lists of all tuples of boarding, batch swap, and exit requests, respectively, with the fully signed, confirmed commitment transaction they have been processed in. 3: Finally, 𝑂 specifies a batching policy. We abstract this policy away into a batching black box 𝛽, which deterministically maps a given state of the lists toBoard, toBatchSwap and toExit of available, verified requests to lists boardings, batchSwaps and exits of requests included in the commitment transaction, as well as templates batchTmp, connectorTmp and 𝛾 that specify how the VTXOs and anchor outputs will be arranged in batch and connector outputs of the commitment transaction. This policy may also include limits such as the maximum number of outputs per virtual transaction, or the maximum tree depth. Note that 𝛽 can also be a function of other external factors, such as the current time or onchain fees. For simplicity, we assume 𝑂 shares its lists toBoard, toBatchSwap and toExit with 𝛽, listens to 𝛽 and starts building a commitment transaction as soon as 𝛽 outputs a tuple of the form (boardings, batchSwaps, exits, batchTmp, connectorTmp, 𝛾). Routine 3 Boarding request to 𝑂 for VTXO list vtxos′ with cosigner set 𝑁 by a party 𝑃. Í Í Require: A list of UTXOs [out 𝑗 ] 𝑗 ∈ 𝐽 ⊆ L 𝑃−𝑘 for which 𝑗 ∈ 𝐽 out 𝑗 .value ≥ 𝑣 := vtxo′ ∈vtxos′ vtxo′ .value, and such that for each 𝑗 ∈ 𝐽 , 𝑃 can provide a witness 𝑤 𝑗 that allows out 𝑗 to be spent for the boarding transaction. 𝑃 should also know the operator public key 𝑝𝑘𝑂 . Finally, 𝑃 should have sets 𝑆𝐶 and 𝑆𝑈 of collaborative and unilateral script paths, as well as an internal public key 𝑝𝑘𝐼 that is a NUMS (Nothing Up My Sleeve) point (such as the one recommended in BIP 341 [56]), in order for the key path to be unspendable. 𝑃 should be able to provide witnesses for these script paths (collaborating with 𝑂 when needed). 1: 𝑃 constructs the boarding transaction tx𝑃board , with tx𝑃board .ins = [out 𝑗 ] 𝑗 ∈ 𝐽 , tx𝑃board .wits = 𝑤 𝑗 , and tx𝑃board .outs = out𝑃board , 𝑗 ∈𝐽 where out𝑃board .value = 𝑣 and out𝑃board .lockScript = Taproot False; 𝑆𝐶 , 𝑆𝑈 . 2: 𝑃 submits tx𝑃board to Π BTC . 3: Once tx𝑃board ∈ L 𝑃−𝑘 , 𝑃 sends to 𝑂 the boarding request
𝑟 = “boarding: ”, 𝑃, 𝑁 , out𝑃board, 𝑝𝑘𝐼 , 𝑆𝐶 , 𝑆𝑈 , vtxos′ .
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
Routine 4 verifyBoardingRequest(𝑟 ): Verify boarding request 𝑟 = “boarding: ”, 𝑃, 𝑁 , out, 𝑝𝑘𝐼 , 𝑆𝐶 , 𝑆𝑈 , vtxos′ . 1: 𝑂 checks that out ∈ L𝑂 and that out ∉ preSpent. −𝑘 2: 𝑂 checks that each script path in 𝑆𝐶 requires a signature from 𝑂, and that each script path in 𝑆𝑈 has a relative timelock of at least 𝑡𝑏 . 3: Given 𝑝𝑘 𝐼 , 𝑆𝐶 , 𝑆𝑈 , 𝑂 makes sure that the locking script of out indeed commits to the correct script paths and unspendable key path. 4: 𝑂 checks that out.value ≥ 5: for vtxo′ ∈ vtxos′ do
Í
′ vtxo′ ∈vtxos′ vtxo .value.
𝑂 checks that vtxo′ satisfies Definition 3.1. 7: end for 8: if all of the checks in Lines 1 - 7 are successful then 9: Add (𝑃, 𝑁 , out, vtxos′ ) to toBoard. 10: Add out to preSpent. 11: end if 6:
Routine 5 Batch swap request to 𝑂 of a VTXO list vtxos into a VTXO list vtxos′ with cosigner set 𝑁 by 𝑃. Require: VTXO lists vtxos ⊆ 𝐶 ∪ 𝐹 and vtxos′ such that for each vtxo ∈ vtxos, batch(vtxo) exists and is in L 𝑃−𝑘 , vtxo can be spent Í Í collaboratively by 𝑃 and the operator, and such that vtxo ∈vtxos vtxo.value ≥ vtxo′ ∈vtxos′ vtxo′ .value. 1: 𝑃 sends to 𝑂 the batch swap request 𝑟 = (“batch swap: ”, 𝑃, 𝑁 , vtxos, vtxos′ ). Routine 6 Exit request to 𝑂 of a VTXO list vtxos into a UTXO list utxos by 𝑃. Require: A VTXO list vtxos ⊆ 𝐶 ∪ 𝐹 such that for each vtxo ∈ vtxos, batch(vtxo) exists and is in L 𝑃−𝑘 , and 𝑃 is able to provide a witness Í Í to spend vtxo via a collaborative VTXO script path. Also, a UTXO list utxos such that vtxo ∈vtxos vtxo.value ≥ out ∈utxos out.value. 1: 𝑃 sends to 𝑂 the exit request 𝑟 = (“exit: ”, 𝑃, vtxos, utxos). Routine 7 musig(tx,𝑁 ): Perform a MuSig2 signing session with public key set 𝑁 for transaction tx. 1: The signers in 𝑁 perform a MuSig2 signing session, such that after successful completion every signer has the signature of tx under the
aggregate public key
É
𝑝𝑘 ∈𝑁 𝑝𝑘.
Routine 8 Ark transaction request to 𝑂 of a VTXO list vtxos ⊆ 𝐶 into a VTXO list vtxos′ by a party 𝑃. Require: A VTXO list vtxos such that for each vtxo ∈ vtxos, batch(vtxo) exists and is in L 𝑃−𝑘 , and 𝑃 is able to cooperate with the operator to provide a witness 𝑤 vtxo to spend vtxo via a collaborative VTXO script path 𝑠𝐶,vtxo . Also, a VTXO list vtxos′ , such that Í Í ′ vtxo ∈vtxos vtxo.value ≥ vtxo′ ∈vtxos′ vtxo .value. re re re , with tx𝑃,vtxo .ins = vtxos, tx𝑃,vtxo .wits = [∗] vtxo ∈vtxos , and 1: 𝑃 constructs for each vtxo ∈ vtxos a reset transaction tx𝑃,vtxo re re .value = vtxo.value and outre .lockScript = Taproot(False; 𝑠 tx𝑃,vtxo .outs = outre , with out 𝐶,vtxo , chkSig𝑝𝑘𝑂 ∧ vtxo vtxo vtxo absTlk 𝑇𝑒,vtxo )), where 𝑇𝑒,vtxo is the block height at which vtxo expires. the batch containing ark ark ′ 2: 𝑃 constructs an Ark transaction tx𝑃ark , with tx𝑃ark .ins = outre vtxo vtxo ∈vtxos , tx𝑃 .wits = [∗] vtxo ∈vtxos , and tx𝑃 .outs = vtxos . 3: 𝑃 sends to 𝑂 the Ark transaction request re ark ′ 𝑟 = “Ark: ”, 𝑃, tx𝑃,vtxo , tx , vtxos, vtxos . 𝑃 vtxo ∈vtxos
Ark: Offchain Transaction Batching in Bitcoin
Routine 9 verifyBatchSwapRequest(𝑟 ): Verify batch swap request 𝑟 = (“batch swap: ”, 𝑃, 𝑁 , vtxos, vtxos′ ). 1: for vtxo ∈ vtxos do
𝑂 checks that vtxo ∈ confirmedVTXO ∪ preConfirmed. 𝑂 checks that vtxo ∉ preSpent. 4: end for 5: for vtxo′ ∈ vtxos′ do 6: 𝑂 makes sure that vtxo′ satisfies Definition 3.1. 7: end for Í Í 8: 𝑂 checks that vtxo ∈vtxos vtxo.value ≥ vtxo′ ∈vtxos′ vtxo′ .value. 9: if all of the checks in Lines 1 - 8 are successful then 10: Add (𝑃, 𝑁 , vtxos, vtxos′ ) to toBatchSwap. 11: Add each vtxo ∈ vtxos to preSpent. 12: end if 2: 3:
Routine 10 verifyExitRequest(𝑟 ): Verify exit request 𝑟 = (“exit: ”, 𝑃, vtxos, utxos). 1: for vtxo ∈ vtxos do
𝑂 checks that vtxo ∈ confirmedVTXO ∪ preConfirmed 𝑂 checks that vtxo ∉ preSpent. 4: end for Í Í 5: 𝑂 checks that vtxo ∈vtxos vtxo.value ≥ out ∈utxos out.value. 6: if all of the checks in Lines 1 - 5 are successful then 7: Add (𝑃, ∅, vtxos, utxos) to toExit. 8: Add each vtxo ∈ vtxos to preSpent. 9: end if 2: 3:
Routine 11 verifyArkTxRequest(𝑟 ): Verify Ark transaction request 𝑟 = “Ark: ”, 𝑃, 𝑅, txark, vtxos, vtxos′ . 1: for vtxo ∈ vtxos do
𝑂 checks that vtxo ∈ confirmedVTXO and that vtxo ∉ preSpent. 𝑂 verifies that there is a txre ∈ 𝑅 that can claim vtxo at the corresponding batch’s expiry. ark for each input of txark . 4: 𝑂 cooperates with 𝑃 to produce a valid witness 𝑤 vtxo 5: end for 6: for vtxo′ ∈ vtxos′ do 7: 𝑂 makes sure that vtxo′ satisfies Definition 3.1. 8: end for Í Í 9: 𝑂 checks that vtxo ∈vtxos vtxo.value ≥ vtxo′ ∈vtxos′ vtxo′ .value. 10: if all of the checks in Lines 1 - 9 are successful then 11: Add each vtxo′ ∈ vtxos′ (as an output of tx) to preConfirmed. re for each tx ∈ 𝑅. 12: Cooperate with 𝑃 to create a witness 𝑤 tx 13: Add (vtxos, tx) to spent, where tx ∈ 𝑅 is the corresponding fully signed reset transaction. 14: end if 2: 3:
Routine 12 sendArkTx(𝑄,tx,vtxos′ ,paths): Send an Ark transaction tx to 𝑄 by 𝑃. Require: We assume tx is a fully signed Ark transaction, and that 𝑃 has knowledge of the set vtxos′ of actual locking scripts of tx that 𝑄 should verify, and path(vtxo) for each vtxo spent by tx (with the reset transaction txre vtxo ). 1: 𝑃 sends to 𝑄 the fully signed Ark transaction tx, as well as the sets vtxos′ of locking scripts of outputs of tx that 𝑄 should verify and paths := path(vtxo) : vtxo ∈ tx.ins . Routine 13 verifyArkTx(tx,vtxos′ ,paths): Verify a received Ark transaction tx with subset of output locking scripts vtxos′ and VTXT paths paths up to the transaction inputs by 𝑄. 1: 𝑄 checks that the locking scripts in vtxos′ are actually committed to by locking scripts of outputs of tx. 2: 𝑄 checks that if it were to submit all transactions in paths to Π BTC , tx would be a valid Bitcoin transaction.
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
Routine 14 commitmentTx(boardings, batchSwaps,exits,batchTmp, connectorTmp,𝛾): Construct commitment transaction with batch outputs according to batchTmp, connectors according to connectorTmp and 𝛾, processing the boarding requests in boardings, batch swap requests in batchSwaps, and exit requests in exits. Require: A list of verified boarding requests boardings ⊆ toBoard, a list of verified batch swap requests batchSwaps ⊆ toBatchSwap, a list of verified exit requests exits ⊆ toExit, a list of UTXOs [out 𝑗 ] 𝑗 ∈ 𝐽 ⊆ L𝑂 for which −𝑘 ∑︁ ∑︁ ∑︁ ∑︁ out 𝑗 .value ≥ vtxo.value − out.value (·,·,·,vtxos′ ) ∈boardings vtxo′ ∈vtxos′
𝑗 ∈𝐽
∑︁
+
∑︁
(·,·,out,·) ∈boardings
∑︁
′
vtxo .value +
(·,·,·,vtxos′ ) ∈batchSwaps vtxo′ ∈vtxos′
+
∑︁
∑︁
out.value +
(·,·,·,utxos) ∈exits out ∈utxos
|vtxos| · 𝜀
(·,·,vtxos,·) ∈batchSwaps
∑︁
|vtxos| · 𝜀,
(·,·,vtxos,·) ∈exits
(1) and such that for each 𝑗 ∈ 𝐽 , out 𝑗 can be spent by 𝑂 with a witness 𝑤 𝑗 for the commitment transaction. Also, the collection of outputs Ð Ð of the leaves of all VTXTs in batchTmp should exactly coincide with (·,·,·,vtxos′ ) ∈boardings vtxos′ ∪ (·,·,·,vtxos′ ) ∈batchSwaps vtxos′ , and Ð Ð connectorTmp should contain an anchor output for each VTXO in (·,·,vtxos,·) ∈batchSwaps vtxos ∪ (·,·,vtxos,·) ∈exits vtxos. For ease of notation, given a VTXT vtxt in batchTmp, we define a function 𝜈 vtxt which makes explicit for every tx ∈ vtxt the cosigners that should sign this tx (note that this is already present implicitly in batchTmp). 1: Define ℎ𝑂 as the current block height according to the operator. Ð 2: 𝑂 constructs the unsigned commitment transaction txcommit with txcommit .ins = [out 𝑗 ] 𝑗 ∈ 𝐽 ∪ (·,·,out,·) ∈boardings out, txcommit .wits = Ð [∗] 𝑗 ∈ 𝐽 ∪ (·,·,out,·) ∈boardings [∗] and txcommit .outs given by Ø Ø Ø outbatch outconnector ∪ utxos, vtxt ∪ vtxt vtxt∈batchTmp
vtxt∈connectorTmp
(·,·,·,utxos) ∈exits
where for each vtxt ∈ batchTmp, outbatch vtxt .value ≥
Í
txleaf ∈leaves(vtxt) tx
leaf .outs[0].value, where
outbatch vtxt .lockScript = Taproot False; chkSig𝑝𝑘𝑂 ∧ absTlk(ℎ𝑂 + 2𝑘 + 𝑡𝑒 ), chkSig𝑝𝑘𝑂 ⊕É𝑝𝑘 ∈𝜈 (root(vtxt) ) 𝑝𝑘 , vtxt
and where for each vtxt ∈ connectorTmp, outconnector .value ≥ |leaves(vtxt)| · 𝜀 and vtxt outconnector .lockScript = Taproot(False; chkSig𝑝𝑘𝑂 ). vtxt 3: Let signerTmp := [ ] 4: for vtxt = (𝑉 , 𝐴) ∈ batchTmp do
Let 𝑉 ′ := 𝜈 vtxt (tx) : tx ∈ 𝑉 . 6: Let 𝐴′ := (𝜈 vtxt (tx), 𝜈 vtxt (tx* )) ∈ 𝑉 ′ : (tx, tx* ) ∈ 𝐴 . 7: Add (𝑉 ′, 𝐴′ ) to signerTmp. 8: end for 9: return (txcommit , signerTmp). 5:
Ark: Offchain Transaction Batching in Bitcoin
Routine 15 verifyPath(𝑁 ,𝑡,txcommit ,vtxo,vtxt,st): Verify using signer tree st = (𝑉 ′, 𝐴′ ) that VTXT vtxt = (𝑉 , 𝐴) correctly includes vtxo and enables unilateral exit controlled by 𝑁 with expiry time 𝑡, and is properly included in txcommit . Require: We assume there is a unique bijection 𝜙𝑉 : 𝑉 → 𝑉 ′ and a unique bijection 𝜙𝐴 : 𝐴 → 𝐴′ such that 𝜙𝐴 ((𝑣 1, 𝑣 2 )) = (𝜙𝑉 (𝑣 1 ), 𝜙𝑉 (𝑣 2 )), otherwise, the routine trivially returns False. The operator public key 𝑝𝑘𝑂 should be known. 1: if ∃tx ∈ leaves(vtxt) : vtxo ∈ tx.outs. then 2: Write (tx1, . . . , txℓ ) := path(vtxo). 3: else 4: return False. 5: end if 6: Write tx0 := txcommit . 7: Check txℓ .outs = [vtxo]. 8: for 𝑖 = ℓ, . . . , 1 do 9: Check 𝜙𝑉 (tx𝑖 ) ⊇ 𝑁 . 10: Check ∃out ∈ tx𝑖 −1 .outs : tx𝑖 .ins = [out] and call it out* . Í 11: Check out* .value ≥ outi ∈tx .outs outi .value and: 𝑖
out* .lockScript = Taproot False; chkSig𝑝𝑘𝑂 ∧ absTlk(𝑡), chkSig𝑝𝑘𝑂 ⊕É𝑝𝑘 ∈𝜙 (tx ) 𝑝𝑘 . 𝑉
𝑖
12: end for 13: if all of the checks in Lines 1 - 12 are successful then
return (vtxt, out* ). 15: end if 14:
Routine 16 verifyConnector(vtxo,txcommit ,connectorTmp,𝛾): Verify using signer tree st = (𝑉 ′, 𝐴′ ) that VTXT vtxt = (𝑉 , 𝐴) correctly includes vtxo and enables unilateral exit controlled by 𝑁 with expiry time 𝑡, and is properly included in txcommit . 1: if ∃vtxt ∈ connectorTmp : ∃tx ∈ leaves(vtxt) : 𝛾 (vtxo) = tx then
Denote this vtxt by vtxt∗ and tx by tx* . Write (tx1, . . . , txℓ ) := path(tx* ), i.e. the path of tx* in vtxt∗ . 4: Write tx0 := txcommit . 5: for 𝑖 = ℓ, . . . , 1 do 6: Check ∃out ∈ tx𝑖 −1 .outs : tx𝑖 .ins = [out] and call it out* . Í 7: Check out* .value ≥ outi ∈tx .outs outi .value. 𝑖 8: end for 9: end if 10: if all of the checks in Lines 1 - 8 are successful then 11: return True. 12: end if 2:
3:
Routine 17 forfeitTx(vtxo,out): Forfeit transaction for vtxo using anchor output out by 𝑃. Require: It is assumed 𝑃 is able to cooperate with 𝑂 to produce a witness 𝑤 vtxo to spend vtxo via a collaborative VTXO script path, and that 𝑃 knows the operator public key 𝑝𝑘𝑂 . 1: 𝑃 constructs the transaction txforfeit , with txforfeit = [vtxo, out], txforfeit .wits = [∗, ∗], and txforfeit .outs = [(vtxo.value + out.value, chkSig𝑝𝑘𝑂 )]. 2: 𝑃 sends txforfeit to 𝑂. Routine 18 Tasks a party 𝑃 performs whenever receiving an Ark transaction. Require: Assume 𝑃 is the recipient of a sendArkTx(𝑃, tx, vtxos′, paths) operation, and that 𝑃 is able to provide a witness to a collaborative script path of all VTXOs vtxos𝑃′ ⊆ vtxos′ . 1: if verifyArkTx(tx, vtxos′ , paths) then 2: Follow Routine 25 for vtxos𝑃′ , with 𝑃 batch swapping or exiting collaboratively. 3: end if
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
Routine 19 verifyCommitTx(txcommit ,batchTmp,signerTmp,connectorTmp,𝛾): Verify commitment transaction txcommit with batch template batchTmp, signer template signerTmp, connector template connectorTmp and connector function 𝛾 by a party 𝑃. Require: 𝑃 is assumed to be involved in at least one request that is being processed by txcommit , either as witness provider or cosigner. We respectively write by boardings, batchSwaps, exits the sets of boarding, batch swap, and exit requests included in txcommit , for which 𝑃 either made the request, or has its public key in the cosigner set. 𝑃 should know the operator public key 𝑝𝑘𝑂 and the cosigner set 𝑁 of public keys. All checks below are performed by 𝑃. Í Í 1: Check that out ∈txcommit .ins out.value ≥ out ∈txcommit .outs out.value. 2: Let ℎ 𝑃 be the current block height according to 𝑃 and check that ℎ𝑂 + 2𝑘 + 𝑡𝑒 ≥ ℎ 𝑃 + 2𝑘 + 𝑡𝑒 . 3: Let 𝑅𝑃 := [ ]. 4: for (𝑃, 𝑁 , out, vtxos′ ) ∈ boardings do 5: Check that out ∈ txcommit .ins. 6: for vtxo′ ∈ vtxos′ do 7: Check ∃vtxt ∈ batchTmp : ∃tx ∈ leaves(vtxt) : vtxo′ ∈ tx.outs. 8: Denote vtxt by vtxt∗ and the corresponding tree in signerTmp by st∗ . 9: Let res := verifyPath(𝑃, 𝑁 , ℎ𝑂 + 2𝑘 + 𝑡𝑒 , txcommit, vtxo′, vtxt∗, st∗ ). 10: if res = (vtxt∗, out* ) for some out* ∈ txcommit .outs then 11: Add (vtxt∗, out* ) to 𝑅𝑃 . 12: else 13: return False 14: end if 15: end for 16: end for 17: for (𝑃, 𝑁 , vtxos, vtxos′ ) ∈ batchSwaps do 18: for vtxo ∈ vtxos do 19: verifyConnector(vtxo, txcommit, connectorTmp, 𝛾). 20: end for 21: for vtxo′ ∈ vtxos′ do 22: Check ∃vtxt ∈ batchTmp : ∃tx ∈ leaves(vtxt) : vtxo′ ∈ tx.outs. 23: Let vtxt∗ := vtxt and the corresponding tree in signerTmp be st∗ . 24: Let res := verifyPath(𝑃, 𝑁 , ℎ𝑂 + 2𝑘 + 𝑡𝑒 , txcommit, vtxo, vtxt∗, st∗ ). 25: if res = (vtxt∗, out* ) for some out* ∈ txcommit .outs then 26: Add (vtxt∗, out* ) to 𝑅𝑃 . 27: else 28: return False 29: end if 30: end for 31: end for 32: for (𝑃, 𝑁 , vtxos, utxos) ∈ exits do 33: for vtxo ∈ vtxos do 34: verifyConnector(vtxo, txcommit, connectorTmp, 𝛾). 35: end for 36: for out ∈ utxos do 37: Check that out ∈ txcommit .outs and add (out, out) to 𝑅𝑃 . 38: end for 39: end for 40: Check there are no (𝑥 1 , 𝑦 1 ), (𝑥 2 , 𝑦 2 ) ∈ 𝑅𝑃 for which 𝑥 1 = 𝑥 2 but 𝑦 1 ≠ 𝑦 2 . 41: Check any additional requirements announced by 𝑂 (such as maximum number of outputs per virtual transaction, maximum tree depth, or the presence of always spendable anchor outputs (𝜀, True)) by inspecting each VTXT in batchTmp. 42: if all of the checks in Lines 1 - 40 are successful then 43: return True. 44: end if
Ark: Offchain Transaction Batching in Bitcoin
Routine 20 unilateralExit(vtxo): Redeem a VTXO onchain via a unilateral exit by a party 𝑃. Require: A VTXO vtxo such that batch(vtxo) exists and is in L 𝑃−𝑘 . 𝑃 also needs to possess all, fully signed, virtual transactions in path(vtxo) as defined in Definition 3.2. 1: 𝑃 submits all transactions in path(vtxo) \ L 𝑃−𝑘 to Π BTC . Routine 21 sweep(out): Reclaim the remaining funds from an output out. Require: We assume out has a Taproot script path of the form chkSig𝑝𝑘𝑂 ∧ absTlk(𝑡) for some block height 𝑡. 1: if out is spent by some tx* ∈ L𝑂 then 2: for out* ∈ tx* .outs do 3: if out* has a Taproot script path chkSig𝑝𝑘𝑂 ∧ absTlk(𝑡) for some 𝑡 then 4: sweep(out* ). 5: end if 6: end for 7: else 8: Construct tx spending out with output (𝑣, chkSig𝑝𝑘𝑂 ), where 𝑣 ≤ out.value. 9: Submit tx to ΠBTC . 10: end if Routine 22 submitCommitTx(txcommit ,boardings, batchSwaps, exits, old, new): Update all the required request and VTXO lists after submitting a fully signed commitment transaction txcommit constructed from boardings, batchSwaps and exits, yielding spent and created VTXO sets old (paired with the corresponding forfeit transaction) and new. All operations are done by 𝑂. 1: Submit txcommit to Π BTC , denote by ℎ the block height at which this happens according to 𝑂. 2: Remove all VTXOs in old from confirmedVTXO and preConfirmed and add (txcommit , old) to unconfirmedSpent. 3: Add (txcommit , new) to unconfirmed. 4: Remove boardings from toBoard and add (txcommit , boardings) to unconfirmedBoardings. 5: Remove batchSwaps from toBatchSwap and add (txcommit , batchSwaps) to unconfirmedBatchSwaps. 6: Remove exits from toExit and add (txcommit , exits) to unconfirmedExits. 7: if txcommit ∈ L𝑂 then −𝑘
Remove (txcommit, old) from unconfirmedSpent. 9: Add all pairs of VTXOs and forfeit transactions in old to spent. 10: Remove (txcommit, new) from unconfirmed. 11: Add all VTXOs in new to confirmedVTXO. 12: Add all batch outputs of txcommit to confirmedBatches. 13: Remove (txcommit, boardings) from unconfirmedBoardings. 14: Remove (txcommit, batchSwaps) from unconfirmedBatchSwaps. 15: Remove (txcommit, exits) from unconfirmedExits. 16: Add (txcommit, boardings) to confirmedBoardings. 17: Add (txcommit, batchSwaps) to confirmedBatchSwaps. 18: Add (txcommit, exits) to confirmedExits. 19: else if txcommit has never been in L𝑂 by block height ℎ + 𝑡𝑟 then −𝑘 20: Remove (txcommit, old) from unconfirmedSpent. 21: Remove (txcommit, new) from unconfirmed. 22: Remove (txcommit, boardings) from unconfirmedBoardings. 23: Remove (txcommit, batchSwaps) from unconfirmedBatchSwaps. 24: Remove (txcommit, exits) from unconfirmedExits. 25: Add boardings to toBoard. 26: Add batchSwaps to toBatchSwap. 27: Add exits to toExit. 28: end if 8:
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
Routine 23 processRequests(boardings,batchSwaps,exits,batchTmp, connectorTmp,𝛾): Construct the corresponding commitment transaction according to Routine 14 and finalise it by gathering the required signatures. Require: It is assumed that the 𝑂 and all cosigners represented in the requests boardings, batchSwaps and exits can communicate with each other. For ease of notation, we refer to the cosigners by their public keys, and we denote by N the set of all cosigners involved in all the requests processed here, and we denote by P the set of all requesters who made requests processed here. 1: 𝑂 constructs (txcommit , signerTmp) := commitmentTx(boardings, batchSwaps, exits, batchTmp, connectorTmp, 𝛾). Ð 2: Let new := (·,·,·,vtxos′ ) ∈boardings∪batchSwaps vtxos′ be all to be created VTXOs. 3: Let old := [ ]. 4: for 𝑆 ∈ P ∪ N do 5: 𝑂 sends to 𝑆 the tuple (txcommit, batchTmp, signerTmp, connectorTmp, 𝛾). 6: if not verifyCommitTx(txcommit, batchTmp, signerTmp, connectorTmp, 𝛾) then 7: 𝑆 aborts. 8: end if 9: end for 10: Since verifyCommitTx(. . .) succeeded for everyone, there is for each vtxt = (𝑉 , 𝐴) ∈ batchTmp a corresponding tree st ∈ signerTmp with bijections 𝜙𝑉vtxt : 𝑉 → 𝑉 ′ and 𝜙𝐴vtxt : 𝐴 → 𝐴′ such that 𝜙𝐴vtxt ((𝑣 1, 𝑣 2 )) = (𝜙𝑉vtxt (𝑣 1 ), 𝜙𝑉vtxt (𝑣 2 )). 11: for vtxt := (𝑉 , 𝐴) ∈ batchTmp do 12: for tx ∈ 𝑉 do 13: musig(tx, 𝜙𝑉vtxt (tx) ∪ 𝑂). 14: end for 15: end for 16: for (𝑃, 𝑁 , out, vtxos′ ) ∈ boardings do 17: musig(txcommit, 𝑃 ∪ {𝑂 }). 18: end for 19: for (𝑃, 𝑁 , vtxos, vtxos′ ) ∈ batchSwaps do 20: for vtxo ∈ vtxos do 21: forfeitTx(vtxo, 𝛾 (vtxo)) yielding txforfeit . vtxo forfeit 22: 𝑂 checks that txvtxo has: • inputs spending vtxo and 𝛾 (vtxo). • one output sending all the funds to 𝑂. 23: 𝑃 and 𝑂 cooperate to provide a collaborative witness to spend vtxo. 24: 𝑂 adds (vtxo, txforfeit ) to old, with txforfeit now fully signed. vtxo vtxo 25: end for 26: end for 27: for (𝑃, ∅, vtxos, utxos) ∈ exits do 28: for vtxo ∈ vtxos do 29: forfeitTx(vtxo, 𝛾 (vtxo)) yielding txforfeit . vtxo 30: 𝑂 checks that txforfeit has: vtxo • inputs spending vtxo and 𝛾 (vtxo). • one output sending all the funds to 𝑂. 31: 𝑃 and 𝑂 cooperate to provide a collaborative witness to spend vtxo. 32: 𝑂 adds (vtxo, txforfeit ) to old, with txforfeit now fully signed. vtxo vtxo forfeit 33: 𝑂 adds (vtxo, txvtxo ) to old. 34: end for 35: end for 36: Once 𝑂 received a forfeit transaction for every vtxo spent in a batch swap or exit request, 𝑂 provides the witnesses [𝑤 𝑗 ] 𝑗 ∈ 𝐽 for the outputs [out 𝑗 ] 𝑗 ∈ 𝐽 . 37: submitCommitTx(txcommit , boardings, batchSwaps, exits, old, new).
Ark: Offchain Transaction Batching in Bitcoin
Routine 24 Tasks an operator performs continuously. 1: while True do
if 𝑂 receives a request 𝑟 = (“boarding: ”, 𝑃, 𝑁 , out, 𝑝𝑘𝐼 , 𝑆𝐶 , 𝑆𝑈 , vtxos′ ) then 3: verifyBoardingRequest(𝑟 ). 4: end if 5: if 𝑂 receives a request 𝑟 = (“Ark: ”, 𝑃, tx, vtxos, vtxos′ ) then 6: verifyArkTxRequest(𝑟 ). 7: end if 8: if 𝑂 receives a request 𝑟 = (“batch swap: ”, 𝑃, 𝑁 , vtxos, vtxos′ ) then 9: verifyBatchSwapRequest(𝑟 ). 10: end if 11: if 𝑂 receives a request 𝑟 = (“exit: ”, 𝑃, 𝑁 , vtxos, utxos) then 12: verifyExitRequest(𝑟 ). 13: end if 14: if 𝛽 outputs (boardings, batchSwaps, exits, batchTmp, connectorTmp, 𝛾) then 15: processRequests(boardings, batchSwaps, exits, batchTmp, connectorTmp, 𝛾). 16: end if 17: for 𝑜𝑢𝑡 ∈ confirmedBatches do 18: if Current block height is past out’s batch expiry height then 19: sweep(out). 20: end if 21: end for 22: for (vtxo, tx) ∈ spent do 23: if vtxo ∈ L𝑂 then 24: Submit tx to ΠBTC . 25: end if 26: end for 27: end while 2:
Routine 25 Tasks a party 𝑃 performs in order to spend a set of VTXO vtxos 𝑃 would want to spend collaboratively/unilaterally. Require: Assume 𝑃 is able to provide a witness to both a unilateral and collaborative script path of each VTXO in vtxos, and that 𝑃 has knowledge of the fully signed virtual transactions on path(vtxo) for all vtxo ∈ vtxos. Let 𝑡 be the batch expiry height. In the case of an Ark transaction, we assume that the transaction inputs can be accessed via the set paths of virtual transaction paths, that the transaction outputs are in the set vtxos′ , and that 𝑃 has defined a set of cosigner 𝑁 and a function 𝜂 : 𝑁 → P (vtxos′ ) which maps each cosigner to a set of VTXOs that that cosigner should be able to batch swap or exit with. 1: if 𝑃’s current block height is smaller than 𝑡 − 2𝑘 − 1 then 2: if 𝑃 wants to perform a batch swap or exit then 3: Initiate the desired batch swap or exit request. 4: Collaborate with 𝑂 in the corresponding processRequests(. . .). 5: else if 𝑃 wants to perform an Ark transaction tx then 6: Initiate the desired Ark transaction request 𝑟 with outputs vtxos′ according to Routine 8. 7: if 𝑃 obtains the fully signed Ark and reset transactions after a successful verifyArkTxRequest(𝑟 ) then 8: for 𝑄 ∈ 𝑁 do 9: 𝑃 executes sendArkTx(𝑄, tx, 𝜂 (𝑄), paths). 10: end for 11: end if 12: end if 13: Perform the desired batch swap or exit request, collaborating with 𝑂. 14: else if 𝑃’s current block height is 𝑡 − 2𝑘 − 1 and spending vtxos failed then 15: for vtxo ∈ vtxos do 16: 𝑃 executes unilateralExit(vtxo) and spends the newly created UTXO. 17: end for 18: end if
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
E
Formal Analysis
In this section, we formally define and prove the security of the Ark protocol. As mentioned in §2.1, we work with the Bitcoin backbone static model (fixed set of miners, static difficulty) presented in [27] to model the Bitcoin blockchain. In this model, we proceed in discrete rounds. By the synchrony assumption, every message sent at round 𝑟 by an honest party will be received by all other honest party at round 𝑟 + 1. At round 𝑟 , each Ark party 𝑄 maintains its own view of 𝑄 the ledger L𝑄 (𝑟 ). We write L −𝑘 (𝑟 ) for this local view with the last 𝑘 1 blocks removed. We write L ⪯ L 2 if L 1 is a prefix of L 2 . To reason about the confirmation of transactions and the possibility of reorgs, we treat Bitcoin as a protocol Π BTC with depth parameter 𝑘 and wait parameter 𝑢, which ensures, with overwhelming probability (w.o.p.), • Persistence: For any two honest parties 𝑄 and 𝑄 ′ , and any round 𝑄 𝑄′ 𝑄 𝑄′ 𝑟 , we either have L −𝑘 (𝑟 ) ⪯ L −𝑘 (𝑟 ) or L −𝑘 (𝑟 ) ⪰ L −𝑘 (𝑟 ). We 𝑄 refer to L −𝑘 (𝑟 ) as the stable part of 𝑄’s ledger, as this will no longer change from round 𝑟 onward. • Liveness: For any transaction tx submitted to ΠBTC by an honest 𝑄 party at round 𝑟 , we have tx ∈ L −𝑘 (𝑠) for every honest 𝑄 by round 𝑠 = 𝑟 + 𝑢. If we treat Bitcoin as above, one can show the following. Corollary E.1 (Corollary 4.12 in [27]). W.o.p., ΠBTC ensures any 𝑘 consecutive blocks in the chain of an honest party contain at least one block produced by an honest miner, who includes all valid transactions it has heard of by the round it produces the block. We translate the liveness property defined above to a statement in terms of rounds. To this end, we state and prove the following Lemma (adapted from Lemma 16 in [3]). Lemma E.2. If an honest party 𝑄 submits a transaction tx to Π BTC at round 𝑟 , at which time the latest stable block in 𝑄’s ledger is 𝐵𝑄 , a block 𝐵 ∗ including tx it will be in the stable part of the ledger of all honest parties at most 3𝑘 blocks away from 𝐵𝑄 , w.o.p. Proof. We know by Persistence that at round 𝑟 , there are 𝑘 consecutive blocks on top of 𝐵𝑄 in L𝑄 . By Liveness, any tx submitted by an honest party 𝑄 to ΠBTC at round 𝑟 will be in the stable part of the ledger of any honest party by round 𝑠 = 𝑟 + 𝑢. We now know two things: (i) every honest miner will have heard of tx from round 𝑟 +1 onward. Therefore, tx will be included in the first honest block mined from round 𝑟 + 1 onward. However, by Corollary E.1, we know that w.o.p., there cannot be more than 𝑘 − 1 blocks between round 𝑟 and round 𝑠. Indeed, if there would, this would mean there would be a sequence of 𝑘 consecutive blocks that do not contain an honest block, as an honest block would have included tx. Hence, there are at most 2𝑘 − 1 blocks between 𝐵𝑄 and 𝐵 ∗ . (ii) by round 𝑠, 𝐵 ∗ is in the stable part of every honest party’s ledger, i.e., 𝐵 ∗ is at least 𝑘 blocks deep. Thus, combining (i) and (ii), 𝐵 ∗ is in the stable part of every honest party’s ledger after at most 3𝑘 consecutive blocks from 𝐵𝑄 . □ This implies, if an honest party 𝑄’s local view is currently at block height ℎ, and 𝑄 submits tx to Π BTC at that height, then w.o.p., tx will be included in a block that is a most 3𝑘 blocks away from 𝑄’s latest stable block (at block height ℎ − 𝑘). That is, tx will be in
the stable part of any honest party’s ledger at latest at block height ℎ − 𝑘 + 3𝑘 = ℎ + 2𝑘. We use this realisation throughout the rest of the proofs and state it as a Corollary. Corollary E.3. If an honest party submits tx to ΠBTC at block height ℎ, tx will be in the stable part of every honest party’s ledger at latest at block height ℎ + 2𝑘, w.o.p. We can now introduce the notion of an Ark state, which represents all VTXOs in an Ark. Next, we define Ark state transitions as sets of Ark actions. These notions will help us to formally define the security properties stated in §2.3. Definition E.4 (Ark State). The Ark state of an Ark run by 𝑂 is defined as a tuple Σ := (𝐶, 𝐹, 𝑆), where 𝐶 is the set containing each VTXO, that is part of a batch confirmed onchain, for which there is no valid transaction spending that VTXO collaboratively in case it would be present onchain, 𝑆 is the set of VTXOs for which 𝑂 holds a fully signed reset transaction, or a fully signed forfeit transaction spending an anchor output confirmed onchain, and 𝐹 is the set of VTXOs that are outputs of Ark transactions, but not in 𝑆 (viz., unspent outputs). Definition E.5 (Ark Action). An Ark action is a concise way to denote an Ark protocol action. It is a tuple 𝛼 = (𝑃, 𝑁 , 𝑂, 𝑣𝑖𝑛 , 𝑢𝑖𝑛 , 𝑣𝑜𝑢𝑡 , 𝑢𝑜𝑢𝑡 , 𝑎), where 𝑃 is the party providing the required witnesses to spend the VTXOs in 𝑣𝑖𝑛 and UTXOs in 𝑢𝑖𝑛 , in order to create the VTXOs in 𝑣𝑜𝑢𝑡 and UTXOs in 𝑢𝑜𝑢𝑡 . 𝑁 is the cosigner set involved in committing any VTXO to a batch. Finally, 𝑎 is a binary variable equal to 1 if and only if 𝛼 is an Ark transaction. Definition E.6 (Ark State Transition). An Ark state transition 𝜏 is a set of Ark actions that changes the Ark state from (𝐶, 𝐹, 𝑆) 𝜏 to (𝐶 ′, 𝐹 ′, 𝑆 ′ ). We may also write (𝐶, 𝐹, 𝑆) → (𝐶 ′, 𝐹 ′, 𝑆 ′ ). Ark state transitions include commitment transactions, unilateral exits, Ark transactions, and batch sweeps. For all but Ark transactions, these transitions only occur if the relevant transactions are confirmed onchain. While the latter three involve a single action each, a commitment transaction may group multiple actions. Thus, we may represent a commitment transaction tx as a set {𝛼𝑖 }𝑖 ∈𝐼 for some index set 𝐼 . Conversely, a set of actions {𝛼𝑖 }𝑖 ∈𝐼 with 𝛼𝑖 = (𝑃𝑖 , 𝑁𝑖 , 𝑣𝑖𝑛,𝑖 , 𝑢𝑖𝑛,𝑖 , 𝑣𝑜𝑢𝑡,𝑖 , 𝑢𝑜𝑢𝑡,𝑖 , 0) defines a commitment Ð Ð transaction tx with inputs 𝑖 ∈𝐼 𝑢𝑖𝑛,𝑖 , outputs 𝑖 ∈𝐼 𝑢𝑜𝑢𝑡,𝑖 , batch outÐ Ð puts holding 𝑖 ∈𝐼 𝑣𝑜𝑢𝑡,𝑖 , requiring signatures from 𝑖 ∈𝐼 𝑁𝑖 , and Ð connector outputs for 𝑖 ∈𝐼 𝑣𝑖𝑛,𝑖 . Witnesses come from the correÐ sponding parties in 𝑖 ∈𝐼 𝑃𝑖 . As claimed in §2.3, the Ark protocol with operator 𝑂, Π ark (𝑂), gives a number of security guarantees. Informally, VTXO Security gives static guarantees that VTXOs cannot be spent by unauthorised parties, and that authorised parties can always spend VTXOs up to a certain time. This is fundamental in showing User Balance Security. Ark Atomicity ensures that for any honest intent to change the state, the state either changes exactly according to the intent, or not at all. In both cases, honest users can rely on the guarantees of VTXO Security. Intuitively, Ark Atomicity ensures that transacting VTXOs works as expected. Of most importance to an honest operator is that it does not lose funds. We phrase this as Operator Balance Security. Finally, under the extra assumptions (A1)-(A4), we show that users who opted into the fast finality mechanism enjoy Fast Finality Balance Security; extending balance security guarantees to
Ark: Offchain Transaction Batching in Bitcoin
VTXOs that have not been committed to by a confirmed onchain batch. Let us now precisely state and prove each security property. Theorem E.7 (VTXO Security). The protocol Πark (𝑂) is (i) VTXO-safe, i.e., for each Ark state Σ = (𝐶, 𝐹, 𝑆), for each vtxo ∈ 𝐶 confirmed in a batch with expiry 𝑇 , and for each Ark state 𝜏 transition 𝜏 before 𝑇 such that (𝐶, 𝐹, 𝑆) → (𝐶 ′, 𝐹 ′, 𝑆 ′ ), if the cosigner set 𝑁 from the action creating vtxo is honest, we have that if vtxo ∈ 𝐶 and vtxo ∉ 𝐶 ′ , there must be an action 𝛼 = (𝑃, 𝑁 ′, 𝑂, 𝑣𝑖𝑛 , 𝑢𝑖𝑛 , 𝑣𝑜𝑢𝑡 , 𝑢𝑜𝑢𝑡 , 𝑎) ∈ 𝜏 such that 𝛼 is a unilateral exit of vtxo, or 𝑃 can construct with 𝑂 a valid witness for vtxo. (ii) VTXO-live, i.e., for each Ark state Σ = (𝐶, 𝐹, 𝑆), for each vtxo ∈ 𝐶 in a confirmed batch with expiry 𝑇 , if the cosigner set 𝑁 from the action creating vtxo is honest, vtxo can, at latest at block height 𝑇 − 2𝑘 − 1, be turned w.o.p. into a UTXO with the same spending conditions by anyone who can submit the fully signed transactions in path(vtxo). Proof. Consider an arbitrary Ark state Σ = (𝐶, 𝐹, 𝑆), and let vtxo ∈ 𝐶 be a VTXO in a confirmed batch with expiry 𝑇 (we assume that 𝐶 ≠ ∅). We assume that vtxo has been created by an Ark action with honest cosigner set 𝑁 . Routine 15 guarantees that 𝑁 is among the signers required to spend the batch output before expiry, and every output on the path of virtual transactions to vtxo. Since 𝑁 is honest, it will not agree to sign off on another transaction that would render vtxo invalid. This realisation implies the following: 𝜏
(i) For each state transition 𝜏 such that (𝐶, 𝐹, 𝑆) → (𝐶 ′, 𝐹 ′, 𝑆 ′ ) before 𝑇 , assume that vtxo ∈ 𝐶 and vtxo ∉ 𝐶 ′ . Since the batch containing vtxo did not yet expire, the only way vtxo would not be a part of 𝐶 ′ any more, is if vtxo would be turned into a UTXO via a unilateral exit, or if there exists a valid (virtual) transaction spending vtxo collaboratively. This transaction can only exist if it includes a valid witness for vtxo’s collaborative locking scripts. 𝑃 should thus be able to provide such a witness, cooperating with 𝑂. (ii) Before batch expiry, the only way to spend the batch is with presigned transactions from the VTXT specifying the batch. Anyone in possession of the virtual transactions on path(vtxo) can thus submit these transactions, and be sure that there can be no double-spend. This as long as all transactions in the path get confirmed before block height 𝑇 . By Corollary E.3, this happens w.o.p. within at most 2𝑘 blocks. In other words, as long as all transactions in path(vtxo) get submitted to Π BTC by a party at latest at block height 𝑇 − 2𝑘 − 1 in that party’s local view, vtxo will be available onchain as a confirmed UTXO. □ Remark E.8. Note how our formal model deviates from reality in the previous proof. For one, we assume that all transactions in path(vtxo) are submitted at once, and can all be included at once in a block. While this is true if the party submitting the transactions would talk directly to a miner, it is not true in practice with Bitcoin’s current P2P relay policy. Bitcoin Core at the time of writing only supports packages of one parent and one child transaction being relayed through the network. Hence, a chain of transactions like path(vtxo), which relies on CPFP (child-pays-for-parent) in order to bump the fees
of the parent transactions to guarantee inclusion onchain, may not get relayed reliably through the network. One would have to first make sure that parent transaction are successfully broadcast and included in the mempools of miners, and then broadcast the children (one-by-one). At the time of writing, work is ongoing [14] to introduce full package relay into Bitcoin, which would remove this inconvenience as it would allow larger packages of transactions to be relayed together. Second, the Bitcoin backbone model effectively assumes arbitrarily large blocks, such that all transactions submitted (and available in an honest miner’s mempool) will be included by that honest miner in one single block. This assumption may no longer be realistic in case of a bank run scenario (see §7), where congestion may occur by the sheer number of transactions submitted. Definition E.9 (Ark Balance). For a given party 𝑃, for a given Ark state Σ = (𝐶, 𝐹, 𝑆) and a given chain view L 𝑃−𝑘 , we define the Ark Í Σ,L Σ,L balance 𝑏 𝑃 of 𝑃 at Σ as the sum 𝑏 𝑃 := vtxo ∈𝑉 Σ vtxo.value + 𝑃 Í L out.value, where 𝑉𝑃 is the set of all vtxo ∈ 𝐶 which are out ∈𝑅 𝑃
more than 2𝑘 blocks from expiry, for which only 𝑃 can provide a witness for a unilateral script path of vtxo and possesses all fully L signed transactions in path(vtxo), and where 𝑅𝑃 is the set of all unspent boarding outputs, i.e., all out ∈ L 𝑃−𝑘 with out.lockScript = Taproot(False, 𝑆𝐶 , 𝑆𝑈 ) where each script path in 𝑆𝐶 requires 𝑂’s signature and where only 𝑃 can provide a witness for the script paths in 𝑆𝑈 . Theorem E.10 (User Balance Security). The Ark protocol Π ark (𝑂) with batch expiry time 𝑡𝑒 guarantees that for each honest party 𝑃, each Ark state Σ = (𝐶, 𝐹, 𝑆), and each chain view L 𝑃−𝑘 , 𝑃 can claim Σ,L
its Ark balance 𝑏 𝑃
onchain, subtracting mining fees, w.o.p.
Proof. By part (ii) of Theorem E.7, 𝑃 can turn each vtxo ∈ 𝑉𝑃 into a UTXO confirmed onchain w.o.p., as 𝑃 is honest and knows path(vtxo). Of course, 𝑃 has to pay the corresponding mining fees to have all these virtual transactions confirmed onchain. Since 𝑃 also knows the witness of a unilateral script path of each of these newly created UTXOs, as well as the witness of a unilateral script path of each boarding output, 𝑃, and only 𝑃 by part (i) of Theorem E.7, can spend all these UTXOs (paying mining fees doing so) and thus claim the funds locked by them. Moreover, 𝑃 can retrieve the funds L locked in boarding outputs out ∈ 𝑅𝑃 by spending these outputs via one their unilateral script paths (paying mining fees), due to validity of Bitcoin as only 𝑃 knows corresponding valid witnesses. Σ,L In conclusion, 𝑃 can claim its Ark balance 𝑏 𝑃 onchain, up to mining fees, w.o.p. □ Remark E.11. Note that for the Ark balance to be non-trivial, and for an honest party to actually have retrievable funds, the Ark’s batch expiry time should be larger than 2𝑘. Theorem E.12 (Ark Atomicity). For any Ark state Σ = (𝐶, 𝐹, 𝑆), and for any Ark action 𝛼 = (𝑃, 𝑁 , 𝑂, 𝑣𝑖𝑛 , 𝑢𝑖𝑛 , 𝑣𝑜𝑢𝑡 , 𝑢𝑜𝑢𝑡 , 𝑎) with 𝑃, 𝑂 ≠ ∅, as long as 𝑃, 𝑁 , or 𝑂 is honest, Π ark (𝑂) ensures that exactly one of the following will happen: (i) 𝛼 does not get included in a state transition, or (ii) 𝛼 is included in a state transition 𝜏 resulting in a state (𝐶 ′, 𝐹 ′, 𝑆 ′ ), where: • ∀vtxo ∈ 𝑣𝑖𝑛 : 𝐶 ′ ∪ 𝐹 ′ ∌ vtxo ∧ 𝑆 ′ ∋ vtxo.
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
• Each UTXO in 𝑢𝑖𝑛 is spent onchain. • ∀vtxo ∈ 𝑣𝑜𝑢𝑡 : (𝑎 = 0 =⇒ vtxo ∈ 𝐶 ′ ) ∧ (𝑎 = 1 =⇒ vtxo ∈ 𝐹 ′ ). • Each UTXO in 𝑢𝑜𝑢𝑡 is confirmed onchain. Proof. For an arbitrary Ark state Σ = (𝐶, 𝐹, 𝑆), let us consider an arbitrary Ark action 𝛼 = (𝑃, 𝑁 , 𝑂, 𝑣𝑖𝑛 , 𝑢𝑖𝑛 , 𝑣𝑜𝑢𝑡 , 𝑢𝑜𝑢𝑡 , 𝑎) with 𝑃, 𝑂 ≠ ∅. Assume that 𝑃 or 𝑂 is honest. Then if 𝛼 is not an Ark action described by the protocol with 𝑃, 𝑂 ≠ ∅, i.e., (𝑎) a boarding, (𝑏) a batch swap, (𝑐) a collaborative exit, or (𝑑) an Ark transaction, the honest participant will not participate in this request, meaning that it will not be included in a state transition. This is because either the honest party is 𝑃, and will not provide witnesses approving the action for any of the required inputs from 𝑣𝑖𝑛 and 𝑢𝑖𝑛 , or the honest party is 𝑂, and will ignore any action that is not in the form of an Ark transaction or a request to be part of a commitment transaction. Thus, it remains to check that in cases (𝑎)-(𝑑) we end up either with (i) or with (ii): (a) A boarding action is of the form 𝛼 = (𝑃, 𝑁 , 𝑂, ∅, outboard, 𝑣𝑜𝑢𝑡 , ∅, 0). First, assume that 𝑃 is honest. In that case, 𝛼 gives rise to an honestly created boarding request (Routine 3), which does not spend VTXOs that are already spent. This request either gets ignored by 𝑂, or it gets (possibly incorrectly) included in a commitment transaction. 𝑃 will verify this commitment transaction according to Routine 19 (in particular Lines 4-16 and 40), and will only cooperate to create the witness for outboard if the verification is successful, according to Routine 23 Line 13. In particular, an honest 𝑃 will only validate a commitment transaction which spends outboard and which has batch outputs that contain all the VTXOs in 𝑣𝑜𝑢𝑡 , with the corresponding virtual transaction paths requiring signatures from 𝑁 . Hence, if this commitment transaction is confirmed onchain, outboard will be spent, and each vtxo ∈ 𝑣𝑜𝑢𝑡 will be included in 𝐶 ′ (with (𝐶 ′, 𝐹 ′, 𝑆 ′ ) being the state after this commitment transaction). If it is not confirmed, 𝛼 will not get included there, but may be included in a different commitment transaction, for which the same reasoning holds. In conclusion, we either have (i) or (ii). Now, assume that 𝑂 is honest. 𝛼 may only be included in a commitment transaction if 𝑂 receives the corresponding boarding request and it passes verification according to Routine 4. It will thus only include 𝛼 in an honestly created commitment transaction, which, if confirmed onchain, guarantees to spend outboard and adds all VTXOs in 𝑣𝑜𝑢𝑡 to 𝐶 ′ of the new state (𝐶 ′, 𝐹 ′, 𝑆 ′ ). Otherwise, if one of the cosigners or requesters is not responding, 𝛼 will not get included. Note that Line 3 makes sure that the boarding output cannot be double-spent, but even if it could be, this will not lead to atomicity being broken. (b) A batch swap action is of the form 𝛼 = (𝑃, 𝑁 , 𝑂, 𝑣𝑖𝑛 , ∅, 𝑣𝑜𝑢𝑡 , ∅, 0). Assume that 𝑃 is honest. 𝛼 then gives rise to an honestly created batch swap request (Routine 5), which does not spend VTXOs that have already been spent, and which either gets ignored by 𝑂, or incorporated (possibly incorrectly) in a commitment transaction. 𝑃 will verify this transaction according to Routine 19 Lines 17-31 and Line 40. Only if verification succeeds, will 𝑃 cooperate with 𝑂 to create the necessary witnesses for the forfeit transactions spending each vtxo ∈ 𝑣𝑖𝑛 , by Routine 23
Line 23. In particular, an honest 𝑃 will only cooperate for a commitment transaction which has connector outputs containing anchors for each vtxo ∈ 𝑣𝑖𝑛 , and batch outputs containing each vtxo ∈ 𝑣𝑜𝑢𝑡 , with the corresponding virtual transaction paths requiring signatures from 𝑁 . If this commitment transaction is confirmed onchain, each vtxo ∈ 𝑣𝑖𝑛 will not be present in 𝐶 ′ or 𝐹 ′ depending on whether it was the output of an Ark transaction, and will be in 𝑆 ′ , as the corresponding forfeit transaction can now spend vtxo if ever present onchain, and each vtxo ∈ 𝑣𝑜𝑢𝑡 will be included in the new 𝐶 ′ . If not confirmed, 𝛼 does not change the state. We indeed have either (i) or (ii). To conclude, assume that 𝑂 is honest. 𝛼 is only included in a commitment transaction if 𝑂 receives the corresponding batch swap request. It will then verify the request according to Routine 9. Consequently, a verified 𝛼 will only be included in an honestly created commitment transaction. This transaction will only be submitted onchain once 𝑂 has the fully signed forfeit transactions corresponding to each VTXO in 𝑣𝑖𝑛 . If confirmed onchain, this commitment transaction guarantees that all VTXOs in 𝑣𝑖𝑛 will not be in 𝐶 ′ ∪ 𝐹 ′ and will be in 𝑆 ′ , and that all VTXOs in 𝑣𝑜𝑢𝑡 are in 𝐶 ′ of the new state (𝐶 ′, 𝐹 ′, 𝑆 ′ ). Otherwise, if one of the cosigners or requesters is not responding, 𝛼 will not be included. (c) We can write a collaborative exit action as 𝛼 = (𝑃, ∅, 𝑂, 𝑣𝑖𝑛 , ∅, ∅, 𝑢𝑜𝑢𝑡 , 0). If 𝑃 is honest, 𝛼 gives rise to an honestly created exit request (Routine 6), in particular not spending VTXOs that have already been spent. This either gets ignored by 𝑂, or added (possibly incorrectly) to a commitment transaction. 𝑃 will verify this commitment transaction according to Routine 19 Lines 32-39 and Line 40. 𝑃 will only cooperate with 𝑂 to create the necessary witnesses for the forfeit transactions spending each vtxo ∈ 𝑣𝑖𝑛 if verification succeeds, by Routine 23 Line 31. An honest 𝑃 will only cooperate for a commitment transaction which has connector outputs containing anchors for each vtxo ∈ 𝑣𝑖𝑛 , and separate outputs corresponding to each out ∈ 𝑢𝑜𝑢𝑡 . If this commitment transaction is confirmed onchain, each vtxo ∈ 𝑣𝑖𝑛 will not be in 𝐶 ′ or 𝐹 ′ depending on whether it was the output of an Ark transaction, and will simultaneously be added to 𝑆 ′ , as the corresponding forfeit transaction can now spend vtxo if ever present onchain, and each out ∈ 𝑢𝑜𝑢𝑡 will be available onchain. If not confirmed, 𝛼 does not change the state. Once again, we have either (i) or (ii). If we now assume that 𝑂 is honest, 𝛼 will only be included in a commitment transaction if 𝑂 receives the corresponding exit request. It will then verify the request according to Routine 10. Hence, a verified 𝛼 will only be included in an honestly created commitment transaction. This transaction will be submitted onchain only if 𝑂 has the fully signed forfeit transactions corresponding to each VTXO in 𝑣𝑖𝑛 . This commitment transaction guarantees that all VTXOs in 𝑣𝑖𝑛 will not be in 𝐶 ′ ∪ 𝐹 ′ but in 𝑆 ′ , and that all UTXOs in 𝑢𝑜𝑢𝑡 are confirmed onchain, once the commitment transaction is confirmed onchain. Otherwise, if one of the cosigners or requesters is not cooperating, 𝛼 will not be included. (d) An Ark transaction action can be denoted as 𝛼 = (𝑃, ∅, 𝑂, 𝑣𝑖𝑛 , ∅, 𝑣𝑜𝑢𝑡 , 𝑢𝑜𝑢𝑡 , 1). If 𝑃 is honest, 𝛼 gives rise to an honestly created Ark transaction request (Routine 8), not spending VTXOs that have already
Ark: Offchain Transaction Batching in Bitcoin
been spent. 𝑂 either ignores this request, or cooperates with 𝑃 to provide the required witnesses (possibly after verifying it via Routine 11), making the Ark transaction valid. In the former case, 𝛼 is not included in a state transition. In the latter case, the existence of valid reset transactions spending each VTXO in 𝑣𝑖𝑛 , implies that these VTXOs are no longer present in 𝐶 ′ but instead in 𝑆 ′ , and the VTXOs in 𝑣𝑜𝑢𝑡 are in 𝐹 ′ . Finally, if we assume that 𝑂 is honest, 𝛼 will only be included in a state transition if 𝑂 receives the corresponding Ark transaction request and it passes verification (Routine 11). Only then will 𝑂 cooperate to provide the required witnesses, leading to the fully signed reset transactions that ensure the VTXOs in 𝑣𝑖𝑛 are not in 𝐶 ′ but in 𝑆 ′ and the VTXOs in 𝑣𝑜𝑢𝑡 are in 𝐹 ′ . □ Theorem E.13 (Operator Balance Security). The Ark protocol Πark (𝑂) with batch expiry time 𝑡𝑒 and VTXO unilateral delay 𝑡𝑢 guarantees that if 𝑂 is honest and 𝑡𝑢 > 4𝑘, 𝑂 can w.o.p. from block height ℎ + 4𝑘 +𝑡𝑒 retrieve at least the amount it put in the Ark through commitment transactions confirmed by block height ℎ, subtracting mining fees. Proof. We first state and prove a number of intermediate results. Lemma E.14. The Ark protocol Π ark (𝑂) with VTXO unilateral delay 𝑡𝑢 guarantees, if 𝑡𝑢 > 4𝑘 and 𝑂 is honest, that for every Ark state Σ = (𝐶, 𝐹, 𝑆), every vtxo ∈ 𝑆 that appears onchain will be spent by a reset transaction or forfeit transaction, w.o.p. Proof. Assume without loss of generality that vtxo can be spent by any of its collaborative script paths immediately once posted onchain. Since vtxo ∈ 𝑆, an honest operator holds either a valid reset transaction or a valid forfeit transaction (spending an anchor output confirmed onchain) that spends vtxo. If the virtual transactions in path(vtxo) are submitted to Π BTC at block height 𝑡, we know by Corollary that by height 𝑡 + 2𝑘, they are in L𝑂 . −𝑘 Routine 24 Lines 22-26 instructs the honest operator to post the reset transaction spending vtxo or the forfeit transaction, as soon as vtxo enters 𝑂 local view of the chain. By height 𝑡 + 2𝑘, vtxo is definitely in L𝑂 , so 𝑂 will for sure have broadcast the required reset/forfeit transaction(s) by height 𝑡 + 2𝑘. By Corollary E.3, these will be confirmed by height 𝑡 + 4𝑘. By Definition 3.1, any unilateral spend of vtxo is delayed by at least 𝑡𝑢 (this is enforced by an honest operator who only includes correctly formed VTXOs in its commitment transactions). Since 𝑡𝑢 > 4𝑘, there are no possible race conditions and an honest operator is guaranteed to spend vtxo with either the corresponding forfeit or reset transaction. □ Lemma E.15. Suppose a batch output expires, and the current Ark state is Σ = (𝐶, 𝐹, 𝑆). If 𝑡𝑢 > 4𝑘, w.o.p., an honest operator can claim all funds locked in the VTXOs contained in the batch that are in 𝐶 ∪ 𝐹 ∪ 𝑆, i.e., all funds contained in the batch, except those locked in VTXOs that are both unilaterally exited and for which there is no forfeit transaction. Proof. By Routine 24 Line 18, an honest operator will perform a sweep operation on the expired batch as defined in Routine 21. If we assume the expired batch output is specified via a VTXT (𝑉 , 𝐴),
every non-leaf transaction in 𝑉 present onchain will be spent by the operator as the locking script only requires the timelock to be expired and an operator signature. Every leaf transaction has a VTXO locking script, and will therefore not be spent by the operator through the sweep operation. These are exactly the VTXOs that have been unilaterally exited. However, by Routine 24 Line 24 and by Lemma E.14, since 𝑡𝑢 > 4𝑘, any VTXO that has been spent prior to being put onchain through a unilateral exit, has been spent already w.o.p. by the honest operator via the corresponding reset and/or forfeit transaction, which an honest 𝑂 has by Theorem E.12. In case of a reset transaction, any of the VTXOs in the subsequent Ark transaction (if valid) that have been spent can also be claimed via a forfeit transaction an honest operator has. In aggregate, this means that the operator claims all funds locked in VTXOs that either have not been spent and not unilaterally exited (which are the VTXOs of the expired batch that are in 𝐶 ∪ 𝐹 ), or have been spent (which are the VTXOs in 𝑆, regardless of whether they have been unilaterally exited). That is, an honest operator can claim all funds held in the expired batch, up to those funds that have been unilaterally exited and that have not been spent, or spent in an Ark transaction included onchain. □ Lemma E.16. Suppose that from block height ℎ onward, an honest operator 𝑂 does no longer accept incoming batch swap and boarding request, only accepting exit requests, in order to shut down its Ark. Then Π ark (𝑂) with batch expiry time 𝑡𝑒 and VTXO unilateral delay 𝑡𝑢 guarantees w.o.p. that, if 𝑡𝑢 > 4𝑘, by block height ℎ + 4𝑘 + 𝑡𝑒 , 𝑂 has retrieved exactly the value it put into the Ark by funding commitment transactions, subtracting mining fees, and adding at least fees it collected for processing requests. Proof. This proof amounts to keeping track of all the flows of funds, in particular, which funds are and will come under control of the operator, assuming this operator exactly follows the protocol. For simplicity, we assume the connector outputs hold a negligible amount of funds. All groups of funds are greater than or equal to zero. Fix the block height ℎ. We denote the commitment transactions from the operator 𝑂 that are confirmed onchain by tx 𝑗 , where 𝑗 runs through 0, . . . , 𝑘ℎ , . . . , 𝑘𝑒 , . . .. The index 𝑘ℎ refers to the latest commitment transaction confirmed before or at block height ℎ, and 𝑘𝑒 to the latest commitment transaction confirmed before or at block height ℎ + 2𝑘 + 𝑡𝑒 . Furthermore, we denote by 𝑒 ( 𝑗) the latest commitment transaction before the expiry of the batches in tx 𝑗 . For example, we have 𝑘𝑒 = 𝑒 (𝑘ℎ ). By construction of any honestly created commitment transaction tx 𝑗 as specified in Routine 14, we can categorise the following incoming and outgoing groups of funds, based on the transaction inputs and outputs: • Incoming funds: – 𝐿 𝑗 : the liquidity coming directly from 𝑂 to finance tx 𝑗 . – 𝐵 𝑗 : the funds coming from boarding transactions. • Outgoing funds: – 𝑉𝑗 : the funds locked in batch outputs holding VTXOs. – 𝑈 𝑗 : the funds locked in UTXOs as a consequence of exit requests. – 𝑀 𝑗 : the mining fees.
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
We can further categorise the outgoing funds 𝑉𝑗 and 𝑈 𝑗 by tracking which VTXOs or boarding transaction outputs were used as part of the boarding, batch swap, or exit requests that led to the formation of the VTXOs and UTXOs in tx 𝑗 . That is, we can write Í 𝑉𝑗 = 𝑖 ≤ 𝑗 𝑉𝑖,𝑗 , where 𝑉𝑖,𝑗 is the aggregate value of all VTXOs or boarding transaction outputs that were spent in order to (partially) fund the VTXOs in tx 𝑗 . Notice that 𝑉𝑗,𝑗 = 𝐵 𝑗 , as all the boarding transaction outputs spent in tx 𝑗 are used to create new VTXOs in txj by Routine 14, and 𝑂 ensures to not have more value locked in the VTXOs created from a boarding request than the value locked in the corresponding boarding output (Routine 4 Line 4). Similarly, Í we write 𝑈 𝑗 = 𝑖< 𝑗 𝑈𝑖,𝑗 (notice the strict inequality now). Since any commitment transaction must be a valid Bitcoin transaction, we must have the following conservation of funds, for every 𝑗 ≥ 0: 𝐿 𝑗 + 𝐵 𝑗 = 𝑉𝑗 + 𝑈 𝑗 + 𝑀 𝑗 . Recalling that 𝐵 𝑗 = 𝑉𝑗,𝑗 , we can rewrite the above to: ∑︁ ∑︁ 𝐿𝑗 = 𝑉𝑖,𝑗 + 𝑈𝑖,𝑗 + 𝑀 𝑗 . 𝑖< 𝑗
(2)
𝑖< 𝑗
We can also establish a second conservation identity, realising that with an honest operator, a VTXO is either spent as part of a batch swap or exit request, leading to a VTXO or UTXO in a later commitment transaction, or through a unilateral exit, or not spent at all. Note that a VTXO can also be spent by an Ark (reset) transaction. However, the funds in that VTXO will just be relocated in another VTXO, that will either be batch swapped, exited, or not spent at all. Since an honest operator does not allow for spending a VTXO that has already been spent in an Ark transaction (via a reset transaction) (by Routines 9 Lines 1-4, 10 Lines 1-4, 11) Lines 1-5), we can just distribute these funds over the other categories. Hence, for every 𝑗 ≥ 0, and because an honest operator will only let a VTXO be spent exactly once (again, by Routines 9 Lines 1-4, 10 Lines 1-4, 11 Lines 1-5), and not allow more funds in the outputs than in the inputs of each batch swap or exit (by Routines 9 Line 8 and 10 Line 5), we have: ∑︁ ∑︁ ∑︁ 𝑉𝑖,𝑗 = 𝑉𝑗,𝑘 + 𝑈 𝑗,𝑘 + 𝐸𝑈𝑗 + 𝑋 𝑗 + 𝐹 𝑗 . (3) 𝑖≤𝑗
𝑘> 𝑗
where the last two terms 𝐸 𝑀 𝑗 are the funds the operator needs to give in mining fees for forfeit transactions, Ark (reset) transactions spending unilaterally exited, spent VTXOs (Routine 24 Lines 22-26), and 𝑆 𝑀 𝑗 are the funds the operator needs to give in mining fees for sweep transactions, respectively. Now, realise that since 𝑂 does not accept boarding or batch swap requests after block height ℎ, 𝑆 𝑂𝑗 = 0 for 𝑗 > 𝑘ℎ . Indeed, (tx 𝑗 ) 𝑗 >𝑘ℎ will have 𝐵 𝑗 = 𝑉𝑗 = 0. Only 𝑈 𝑗 may be non-zero, containing UTXOs from users exiting collaboratively from batches with index less than or equal to 𝑘ℎ . More specifically, 𝑈𝑖,𝑗 may be non-zero for 𝑖 ≤ 𝑘ℎ , but 𝑈𝑖,𝑗 = 0 for 𝑖 > 𝑘ℎ . Also, realise that 𝑈𝑖,𝑗 = 0 for 𝑗 > 𝑘𝑒 , as by then all batches confirmed before or at height ℎ have now expired and an honest operator would not perform a collaborative exit for a VTXO coming from an expired batch. We can thus focus on the commitment transactions confirmed before or at block height ℎ. By block height ℎ + 2𝑘 + 𝑡𝑒 , every batch 𝑘ℎ contained in one of the commitment transaction (tx 𝑗 ) 𝑗=0 will have expired due to Routine 14, and by Routine 24 an honest operator will have initiated sweeps for all expired, unspent funds. The latest sweep transactions will thus be submitted at height ℎ + 2𝑘 + 𝑡𝑒 , and will be confirmed by height ℎ + 4𝑘 + 𝑡𝑒 w.o.p. by Corollary E.3. Note that as long as a sweep is not confirmed onchain, a user might still try to unilaterally exit funds. In case the user’s exit transactions get confirmed instead of 𝑂’s sweep transactions, we count the corresponding funds as a part of 𝐸𝑈𝑗 . The total amount gained through commitment transactions before and at block height ℎ is thus:
∑︁
(4)
𝑆 𝑂𝑗 =
𝑗 ≤𝑘ℎ
∑︁ ∑︁
=
𝑖≤𝑗
𝑗 ≤𝑘ℎ (3)
𝑀 𝑉𝑖,𝑗 − 𝐸𝑈𝑗 − 𝐸 𝑀 𝑗 − 𝑆𝑗
∑︁ ∑︁
(𝑉𝑗,𝑘 + 𝑈 𝑗,𝑘 )
𝑗 ≤𝑘ℎ 𝑘 > 𝑗
+
∑︁
𝑀 (𝑋 𝑗 + 𝐹 𝑗 − 𝐸 𝑀 𝑗 − 𝑆 𝑗 ),
(5)
𝑗 ≤𝑘ℎ
𝑘> 𝑗
Since 𝑉𝑘 = 0 for 𝑘 > 𝑘ℎ , we rewrite the first term of (5) as We introduced the term 𝐸𝑈𝑗 to indicate unilateral exits of unspent VTXOs or VTXOs spent by Ark transactions (via reset transactions). We explicitly do not account for spent VTXOs that one attempts to unilaterally exit with as well, as this would result in double counting. Also, we introduced 𝑋 𝑗 to account for all VTXOs that have not been spent. Finally, 𝐹 𝑗 represents the fees that the operator may charge for processing requests. Indeed, when creating the new outputs in return for batch swap/exits, their aggregate value might be less than 𝑉𝑗 , where the difference has been claimed by the 𝑂 once the batch expires. By Lemma E.15, since 𝑡𝑢 > 4𝑘, an honest operator will be able to claim w.o.p. all the funds held in expired batches, except for the unilaterally exited VTXOs for which 𝑂 does not hold a forfeit transaction. In other words, the amount 𝑆 𝑂𝑗 swept by the operator is given by: ∑︁ 𝑀 𝑆 𝑂𝑗 = 𝑉𝑖,𝑗 − 𝐸𝑈𝑗 − 𝐸 𝑀 (4) 𝑗 − 𝑆𝑗 , 𝑖≤𝑗
∑︁ ∑︁
(𝑉𝑗,𝑘 + 𝑈 𝑗,𝑘 )
𝑗 ≤𝑘ℎ 𝑘 > 𝑗
=
∑︁
∑︁
(𝑉𝑗,𝑘 + 𝑈 𝑗,𝑘 ) +
𝑗 ≤𝑘ℎ 𝑗 <𝑘 ≤𝑘ℎ
=
∑︁ ∑︁
(𝑉𝑗,𝑘 + 𝑈 𝑗,𝑘 ) +
∑︁ ∑︁ 𝑘 ≤𝑘ℎ 𝑗 <𝑘
𝑈 𝑗,𝑘
𝑗 ≤𝑘ℎ 𝑘>𝑘ℎ
∑︁ ∑︁
𝑈 𝑗,𝑘
𝑗 ≤𝑘ℎ 𝑘>𝑘ℎ
𝑘 ≤𝑘ℎ 𝑗 <𝑘
=
∑︁ ∑︁
(𝑉𝑗,𝑘 + 𝑈 𝑗,𝑘 ) +
∑︁
∑︁
𝑈 𝑗,𝑘 ,
(6)
𝑘ℎ <𝑘 ≤𝑘𝑒 𝑗 <𝑘
where the second equality is just a rearrangement of the sums, and the third equality first uses that 𝑈 𝑗,𝑘 = 0 for 𝑗 > 𝑘ℎ and for 𝑘 > 𝑘𝑒 , and then rearranges the sums.
Ark: Offchain Transaction Batching in Bitcoin
On the other hand, the funds put in by the operator through commitment transactions before and at block height ℎ add up to ∑︁ ∑︁ ∑︁ ∑︁ (2) 𝐿𝑗 = (𝑉𝑖,𝑗 + 𝑈𝑖,𝑗 ) + 𝑀𝑗 𝑗 ≤𝑘𝑒
𝑗 ≤𝑘𝑒 𝑖< 𝑗
=
∑︁ ∑︁
𝑗 ≤𝑘𝑒
(𝑉𝑖,𝑗 + 𝑈𝑖,𝑗 ) +
𝑗 ≤𝑘ℎ 𝑖< 𝑗
+
∑︁
∑︁
∑︁
𝑈𝑖,𝑗
𝑘ℎ < 𝑗 ≤𝑘𝑒 𝑖< 𝑗
(7)
𝑀𝑗 ,
𝑗 ≤𝑘𝑒
where in the second equality, we used that 𝑉𝑗 = 0 for 𝑗 > 𝑘ℎ . Substituting (6) into (5), and then combining the latter with (7), we obtain the net balance of the operator at block height ℎ + 4𝑘 + 𝑡𝑒 : ∑︁ ∑︁ ∑︁ ∑︁ 𝑀 𝑆 𝑂𝑗 − 𝐿𝑗 = (𝑋 𝑗 + 𝐹 𝑗 − 𝐸 𝑀 𝑀𝑗 , 𝑗 − 𝑆𝑗 ) − 𝑗 ≤𝑘𝑒
𝑗 ≤𝑘𝑒
𝑗 ≤𝑘ℎ
𝑗 ≤𝑘𝑒
which means that 𝑂 retrieves all funds that it put into the Ark, subtracting the mining fees and adding the fees the operator charges for processing requests. Additionally, the operator may gain any funds from VTXOs that have not been spent in any way before their batch expired, and have therefore just been swept by the operator. This identity then immediately gives us a necessary condition for running an Ark profitably; the operator fees should cover the mining fees (minus any potential unspent VTXOs that have been swept). □ Lemma E.16 now finishes the proof of Theorem E.13. Indeed, if an operator wants to retrieve its funds it put in up to and including block height ℎ, it can always decide to stop processing boarding and batch swap requests received after ℎ, and be guaranteed w.o.p., if 𝑡𝑢 > 4𝑘, to have retrieved from block height ℎ + 4𝑘 + 𝑡𝑒 onward at least the funds it put in via commitment transactions confirmed by block height ℎ, subtracting mining fees. □ Henceforth, we assume that there is a set 𝑁 ff of users who opted into Ark’s fast finality mechanism, and that assumptions (A1)-(A4) hold. We denote by Πff (𝑂) the fast finality Ark protocol, i.e., the ark Ark protocol Πark (𝑂) extended by Protocol 1, and the requirement that 𝑂 has funded a collateral UTXO of value 𝑐 > 𝑣 (given by (A4)) which cannot be spent by 𝑂 alone before all VTXOs held by users in 𝑁 ff expired, and ensures that each of the VTXOs, as well as the relevant batch outputs and VTXT transaction outputs, allow for private key extraction in case of double-signing, as described in §4. Definition E.17 (Fast Finality Ark Balance). For a given party 𝑃 in 𝑁 ff and for a given Ark state Σ = (𝐶, 𝐹, 𝑆), we define the Fast Finality Ark balance 𝑏 𝑃Σ,ff of 𝑃 at Σ as the sum 𝑏 𝑃Σ,ff := Í vtxo.value, where 𝑉𝑃Σ,ff is the set of all vtxo ∈ 𝐹 which vtxo ∈𝑉 Σ,ff
Proof. Assume 𝑃 is honest. Let vtxo ∈ 𝑉𝑃Σ,ff be arbitrary. Then vtxo.value ≤ 𝑣 by (A4). Denote by 𝑝 = (txark, txre, path(vtxo)) the payment in which 𝑃 received vtxo. Without loss of generality, assume that path(vtxo) is a simple sequence of virtual transactions as in Definition 3.2, with a number of fast finality Ark transactions appended to it. In particular, path(vtxo) contains exactly one virtual transaction spending a batch output confirmed onchain. Furthermore, denote by tx* a transaction that conflicts with vtxo, i.e., there exists a transaction tx ∈ path(vtxo) that spends the same output as tx* . In case tx* has a VTXO as output, we denote it as vtxo∗ . By definition, 𝑃 received vtxo ∈ 𝑉𝑃Σ,ff at least a time period of 2Δ ago. We claim that since 𝑃 behaves honestly, Protocol 1 ensures that no other honest user 𝑃 ′ would have a conflicting vtxo∗ in its set 𝑉𝑃Σ,ff ′ . In other words, no two honest users could be defrauded by a double-sign. To see this, recall from Protocol 1 that every honest receiver of a payment vtxo finalises the transaction only if no conflicting transaction has been received from another user 2Δ after broadcasting the payment 𝑝 to 𝑁 ff . Indeed, if 𝑃 receives 𝑝 at time 𝑡 and broadcasts it immediately, it can be sure that every honest user has received it by 𝑡 + Δ. We now distinguish two cases. (1) If a conflicting VTXO vtxo∗ is received by 𝑃 ′ as part of a payment 𝑝 ′ , after 𝑡 + Δ, the double-signing will be detected ′ and 𝑃 ′ will not accept 𝑝 ′ , so vtxo∗ ∉ 𝑉𝑃Σ,ff ′ . Moreover, 𝑃 ′ ff will broadcast 𝑝 to 𝑁 , and burn the operator collateral. Observe that 𝑃 may receive 𝑝 ′ after 𝑡 + 2Δ, and would have thus accepted 𝑝 by then. (2) If vtxo∗ is received by 𝑃 ′ before 𝑡 + Δ, 𝑃 ′ also broadcast 𝑝 ′ to 𝑁 ff , meaning 𝑃 receives it by 𝑡 + 2Δ. At that point, 𝑃 will not accept the payment (neither will 𝑃 ′ , in fact). Once again, the operator collateral would have been burned. It is important to realise that at most one honest user can be defrauded. Indeed, we see from the first case that 𝑃 could have accepted 𝑝 even though there was a double-sign. This would mean that 𝑃 does not have a guarantee to unilaterally exit vtxo. However, in both cases, 𝑃 ′ does not accept 𝑝 ′ . The gain from double-signing is thus zero, whereas the burned collateral is 𝑐 > 𝑣 ≥ vtxo.value > 0. A rational operator would therefore not double-sign in the first place, and 𝑃 can be sure that he can unilaterally exit vtxo. Now that we have argued how no two honest users could be defrauded by a double-sign, we should consider the case that not an honest, but a malicious user 𝑃 ∗ in 𝑁 ff holds a transaction tx* conflicting with tx ∈ path(vtxo). There are two possibilities:
are more than 2𝑘 blocks from expiry, that 𝑃 accepted as a payment output, for which only 𝑃 can provide a witness for a unilateral script path of vtxo and possesses all fully signed transactions in path(vtxo).
(1) tx* is a virtual transaction in the VTXT. 𝑃 ∗ would have to collude with batch cosigners and the operator in order to achieve this, or (2) tx* is an Ark transaction which does not have vtxo∗ as an output.
Theorem E.18 (Fast Finality Balance Security). The fast finality Ark protocol Π ff (𝑂) with batch expiry time 𝑡𝑒 guarantees ark that for each honest party 𝑃 in 𝑁 ff and each Ark state Σ = (𝐶, 𝐹, 𝑆), 𝑃 can claim its fast finality Ark balance 𝑏 𝑃Σ,ff onchain, subtracting mining fees, w.o.p.
First observe that in both cases, since 𝑃 is monitoring the chain, if 𝑃 ∗ tries to exit onchain by publishing tx* , 𝑃 will be able to extract 𝑂’s private key from tx* and the conflicting tx ∈ path(vtxo), and burn the collateral. In other words, 𝑃 is either able to exit unilaterally and claim its fast finality Ark balance (by Corollary E.3) onchain,
𝑃
Pim Keer, Matteo Maffei, Marco Argentieri, Andrew Camilleri, and Zeta Avarikioti
or ends up in a race condition with a conflicting tx* , which will lead to the collateral being burned. Assume that tx* ∈ path(vtxo∗ ) 12 , then 𝑃 ∗ could have done a (i) batch swap, (ii) cooperative exit, (iii) unilateral exit or (iv) Ark transaction with vtxo∗ . For (i) and (ii), 𝑂 would have taken over ownership of the funds in vtxo∗ . For (iii), 𝑃 ∗ would still own the funds in vtxo∗ . Finally, for (iv), an honest user in 𝑁 ff would not accept it in case of a fast finality Ark transaction as we argued before, or would only consider it finalised after a batch swap or cooperative exit with 𝑂, which puts us back in case (i) or (ii). In other words, the gain from double-signing is at most vtxo.value. Once again, since the burned collateral is 𝑐 > 𝑣 ≥ vtxo.value, 𝑂 will not double-sign, and 𝑃 is able to claim vtxo onchain.
The only remaining risk for 𝑃 is that a previous owner along path(vtxo) exits unilaterally, trying to claim funds already spent offchain through Ark transactions. However, every unilateral path is gated by a relative timelock, allowing 𝑃 to immediately post the collaborative Ark transactions that spend the contested VTXO (bringing other inputs onchain as needed, which one should note may be costly) and thus win the race. Since 𝑃 monitors the chain, a previous owner will not be able to claim 𝑃’s funds. We can repeat this argument for any vtxo ∈ 𝑉𝑃Σ,ff , for any Í 𝑃 ∈ 𝑁 ff . Since vtxo ∈ Ð vtxo.value = 𝑣 < 𝑐, we are 𝑉 Σ,ff 𝑃 ∈𝑁 ff
done.
𝑃
□
12 If this is not the case, we have that tx* is a virtual transaction in a malformed VTXT which does not lead to a VTXO output, but some other output that would simply be put onchain, as if it were a VTXO unilateral exit.