By Steven Roose
Source: https://roose.io/blog/hark-erk-evolving-the-ark-protocol-using-ctv-and-csfs/
(This article is also posted on the Delving Bitcoin forum .)
Last week on the OP_NEXT forum, I proposed a new variant of the Ark protocol, called "Erk," that eliminates all interaction required by users to participate in rounds. In this post, Erik De Smedt and I hope to clarify Erk and other optimizations that can be made on top of Ark using CTV ( OP_CHECKTEMPLATEVERIFY ) and CSFS ( OP_CHECKSIGFROMSTACK ).
In short, we arrive at two competing protocols for Ark, which have the following properties:
- "Erk":
- No user interaction is required to participate in a round
- Offline refresh (the service provider can refresh for the user)
- Perpetual offline refresh (the service provider can refresh for a user continuously, with no expiration date)
- Works best on a single-input, single-output VTXO
- Requires CTV + CSFS
- "hArk":
- No user interaction is required to participate in a round
- Very efficient, even if there are multiple inputs
- Offline refresh is not possible (at least so far)
- Only CTV required
About Ark
We first summarize the existing CTV-based Ark protocol and the MuSig-based clArk protocol, followed by a detailed explanation of the new Erk and hArk variants.
First, let's summarize the core concepts that will be used in the following explanations.
We denote the Ark service provider’s public key as $S$ and the user’s public key as $A, B, …$
The fundamental building block of the Ark protocol is the transaction tree, which allows multiple users to share a single on-chain UTXO. The skeleton diagram below shows a transaction tree where Alice ($A$) owns 4 BTC, Bob ($B$) owns 3 BTC, Carol ($C$) owns 2 BTC, and Dave ($D$) owns 1 BTC. Ark is an off-chain protocol, so in the optimistic scenario, only the funding transaction (FUNDING) in the entire transaction tree will be confirmed by the blockchain.
(每个方框都是一笔比特币交易) +------------+ | FUNDING | +------------+ | 10₿ +-----+------+ | NODE 1 | +-----+------+ +---------┴--------------+ 7₿ | | 3₿ +----+----+ +----+----+ | NODE 2 | | NODE 3 | +----+----+ +----+----+ | | +-----+-----+ +-----+-----+ 4₿ | 3₿ | 2₿ | | 1₿ +---+----+ +---+----+ +---+----+ +---+----+ | EXIT A | | EXIT B | | EXIT C | | EXIT D | +--------+ +--------+ +--------+ +--------+In this setup, Alice can unilaterally exit and claim her funds by broadcasting her branch of the transaction tree. Her branch consists of four transactions: FUNDING , NODE 1 , NODE 2 , and EXIT A . When Alice knows these transactions (along with the witness data required to make them valid) and can spend them using her public key $A$ , she is said to own a VTXO.
Every Ark VTXO has an expiration date. Before this expiration date, the VTXO must be either spent or refreshed (otherwise, the user loses its value). "Refreshing a VTXO" essentially means exchanging one VTXO for a new one (one with a later refresh date). This refresh operation occurs during an Ark "round," an online interaction between the Ark service provider and its users.
After the expiration date, the service provider can clear the value in the entire transaction tree. Ideally, the service provider can directly clear (spend) the funding transaction, but if one (or some) users have performed a unilateral exit, the service provider can only clear the value in all remaining nodes where no user has exited.
Arkoor
If Alice holds a VTXO and wants to pay Bob, she can create a new off-chain transaction (typically called an "arkoot transaction"), spending her own VTXO (the output of her exit transaction) to create a new VTXO for Bob. Bob can then store all the transactions that made up Alice's VTXO, plus the arkoot transaction she created, to form his new arkoot VTXO .
(Translator's note: "Arkoor" is the abbreviation of "Ark out-of-round". As the name suggests, it is performed outside the round.)
Output spending conditions
We divide the output spending conditions used in the Ark protocol into three types:
- Node transaction spending conditions : spending conditions used in all node transactions (including funding transactions)
- Leaf Condition : The spending condition used in the output of the last node transaction, paid to an exit transaction
- Exit Condition : The spending condition used in the exit transaction; the exit transaction is the leaf of the entire transaction tree and can be used by users to perform a unilateral exit
Logically, you can think of these three spending conditions as being sequential. The diagram below illustrates the spending conditions for the outputs shown above. An exit transaction can be followed by either an arkoor transaction or a relinquish transaction.
FUNDING+-------------+-----+| node policy | 10₿ |+-------------+-----+NODE 1+-------------+-----+| node policy | 7₿ |+-------------+-----+| node policy | 3₿ |+-------------+-----+NODE 2+-------------+-----+| leaf policy | 4₿ |+-------------+-----+| leaf policy | 3₿ |+-------------+-----+EXIT A+-------------+-----+| exit policy | 4₿ |+-------------+-----+All variants have the following common features:
Each round will be at an expired block height $T_{exp}$. After this block, the funds in this round (corresponding transaction tree) can be cleared by the Ark service provider key.
In our construction, all transactions have zero fees and have a fee anchor output. In practice, fees can be non-zero if the service provider prefers to subsidize user exit costs. Having transaction fees isn't a requirement for the construction to work, but having a fee anchor output is. (Translator's note: This anchor output allows users to add fees via the "CPFP" method.)
Both node spending conditions and leaf spending conditions function by continuing a branch of the transaction tree with an alternative spending path, allowing the service provider to clear funds after expiration.
For users, the liveness requirement means that they must return to the internet some time before their VTXOs expire (i.e., before $T_{exp}$) to either refresh their VTXOs or perform a unilateral exit (if the service provider and any previous owner of their arkoor VTXOs behave improperly).
Once the exit transaction is confirmed by the block, the expiration mechanism becomes invalid and the funds will enter the exit conditions . The exit conditions have two main functions and corresponding terms :
- Payment terms , which provide a way for users and service providers to collaboratively create instant spends (used to create Arkoor transactions and abandonment transactions)
- Exit clause , providing a way for the user to access these funds if he/she never creates an instant spend with this VTXO
The original design of the exit condition used a relative time lock in the exit clause , but our updated design combines an absolute time lock $T_{exp}$ and a relative time lock $\Delta t$.
- This relative time lock ensures that payment terms take precedence over exit terms .
- This absolute timelock ensures that any subsequent owner of this VTXO (anyone who may receive this VTXO through an arkoor transaction using the payment terms ) has no liveness requirement other than being online some time before $T_{exp}$.
Detailed description of some variants
Ark
The original version of the Ark Protocol was based on CTV. Our latest iteration of the idea is the same.
Both node spending conditions and exit conditions use OP_CTV to commit to the next transaction.
- Node conditions and leaf conditions : $CTV\ or\ (S + T_{exp})$
- Exit condition : $(A + S)\ or\ (A + T_{exp} + \Delta t)$
During a round (when refreshing VTXO), users sign a waiver transaction , transferring their VTXOs to the service provider. This waiver transaction is conditional on the successful start of the next round. A connector is a dedicated descendant transaction of the next round's funding transaction. It is used as an output of the waiver transaction , ensuring that the service provider can only enforce the waiver transaction if the next round's funding transaction is successfully confirmed. Once all users have signed the waiver transaction for their VTXOs, the service provider can sign the funding transaction and broadcast it to the Bitcoin network.
A surrender transaction has two inputs:
- Output of the exit transaction, using the payment terms of the exit spending conditions
- Connector input, an output from a chain of descendant transactions from the new round's funding transaction
A waiver transaction has only one output, which is to send all funds to the service provider.
forfeit tx:| inputs | outputs | +===========+=========+| exit tx | S | +-----------+---------+| connector | | +-----------+---------+ clArk, "Ark without the strings attached"
clArk is very similar to Ark, but uses a recursive multi-signature mechanism on the transaction tree. Each node condition contains a multi-signature mechanism that uses the public keys of all leaves below that node.
- Node conditions : $(A + B + C + … + S)\ or\ (S + T_{exp})$
- Leaf condition : $(A + S) or\ (S + T_{exp})$
- Exit condition : $(A + S)\ or\ (A + T_{exp} + \Delta t)$
The round mechanism is the same and connectors are used. The only difference is that an additional phase is required where all clients sign their branch of the transaction tree.
Erk, "Erik's Ark"
Since I demoed Erk at the OP_NEXT conference, we've made some additional upgrades.
The spending conditions in Erk are exactly the same as in Ark, but we make the signatures rebindable (“rebindable signatures” are signatures that use APO semantics, meaning they don’t commit to a specific UTXO input and can therefore be used to spend any output containing the same public key). We can use CTV + CSFS to implement rebindable signatures.
- Node conditions and leaf conditions : $CTV\ or\ (S + T_{exp})$
- Exit condition : $(A + S)\ or\ (A + T_{exp} + \Delta t)$
The $A + S$ in the exit condition is where we use the rebinding signature.
The core and fundamental principles of Erk are embodied in the following transaction, which we call a refund transaction .
refund tx:| inputs | outputs | +====================+================+| old exit tx for A | exit policy A' | +--------------------+----------------+| new exit tx for A' | S | +--------------------+----------------+An Erk round has no user interaction (we define "user interaction" as "all users taking an action simultaneously"). A user participates in a round by sending a new public key ($A'$) and a signed refund transaction to the service provider. Note that one input of the refund transaction is signed with the current public key $A$, while the other input is signed with the new public key $A'$.
At this point, the service provider can safely create a new VTXO tree and issue the same VTXO to the user (minus some fees). This new VTXO has an exit condition using the new public key $A'$.
Users can safely sign this refund transaction at any time because they will still receive their money from one of the transaction outputs. So if this transaction is used maliciously by the service provider, the user will not lose any funds.
The service provider can also create a round after receiving such a signed refund transaction, because, if the user tries to (maliciously) withdraw the original old VTXO, the service provider can reveal this new VTXO and spend both at the same time, taking something the user is not entitled to.
Arkoor
Implementing arkoor transactions in the Erk variant requires special care. Imagine that user Alice sends her new VTXO to Bob (using an arkoor transaction) and then maliciously attempts to withdraw her old VTXO. The service provider will be forced to broadcast the new VTXO and use a refund transaction, which will invalidate Bob's arkoor VTXO.
However, because the exit transaction, a leaf of the transaction tree, has the same output spending conditions as the refund transaction (for public key $A'$), Bob can ask Alice for a rebinding arkoor signature: this signature can be used on both outputs. (Note that only one of them can exist at a time, because the refund transaction is a child of the exit transaction.)
This design allows Arkoor transactions to work on Erk, provided that each new VTXO comes from a single VTXO input. When we try to generalize this design to the case where multiple VTXO inputs are combined into a single VTXO output, the Arkoor construction breaks down.
Offline refresh
Now, imagine that the user has pre-signed a refund transaction for their VTXO (right after the VTXO is created), submitted this signature to the service provider, and then gone offline. This means that the service provider can securely reissue the VTXO at any time. As long as they have the refund transaction, there's no risk of the user claiming both VTXOs simultaneously. This means that even if the user forgoes manual refresh, the service provider can automatically assist them. Alternatively, a watchtower could monitor the Ark and notify the user if the service provider fails to assist with refreshing the user's VTXO.
(Translator's note: "Watchtower" refers to an Internet service that can monitor the Bitcoin blockchain and respond to events on its behalf.)
Furthermore, assuming the first flush changes public key $A$ to $A'$, Alice could also pre-sign a refund transaction for a future VTXO $A'$, thereby changing the public key to $A''$. In fact, Alice could pre-sign any number of flushes, each transferring funds to a new public key (and possibly deducting some amount each time as a service fee for the service provider). This way, a service provider could continually flush a VTXO without the user having to go back online unless a watchtower alerted them that the service provider wasn't complying.
Perhaps a malicious service provider could try to apply all of these refund transactions quickly, thereby pocketing all the service fees (note that this is not necessarily economical, as they would need to pay mining fees for each transaction). This can be avoided by placing an absolute time lock on each refund transaction: the service provider can only use the corresponding refund transaction after a future time calculated based on the expected round time.)
hArk, "Hash Lock Ark"
Erk looked very powerful (although we discarded the potential codename "aArk"), but it had two major drawbacks:
- To retaliate against a malicious exit, the service provider must reveal the transaction tree branch where the new VTXO resides. This is particularly problematic for "entry VTXOs"—VTXOs created by users when transferring funds to an Ark. Entry VTXOs consist of only one funding transaction and one exit transaction (the funding transaction's output uses leaf spend conditions ). This means that the cost of attempting a malicious exit is low for the user, while the cost of retaliation for the service provider can be high.
- Erk can only support the refresh of a single VTXO input.
hArk is not a variant of Erk, but a completely different variant of Ark. Its round mechanism does not require any user interaction, it minimizes on-chain traces, and is perfectly adapted to the situation of multiple VTXO inputs.
In hArk, leaf spending conditions differ from node spending conditions in that the former requires knowledge of a secret value.
- Node condition : $CTV\ or\ (S + T_{exp})$
- Leaf condition : conceptually $(CTV + secret) or \ (S + T_{exp})$ ( $secret$ is the required secret value), but the alternative $(A + S + secret tweak) or \ (S + T_{exp})$ can be spent using the Taproot key path, so it is more efficient
- Exit condition : $(A + S)\ or\ (A + T_{exp} + \Delta t)$
During a hArk round, users submit VTXO outputs they wish to refresh. The service provider creates a secret value for each new VTXO in the tree. Because this secret value is initially known only to the service provider, it can securely fund the round (transaction tree). Initially, none of the new VTXOs are accessible to users, as all secret values remain confidential.
After the round funding transaction is confirmed by the block, the user signs a waiver transaction . This waiver transaction is different from the waiver transactions in Ark and clArk. It allows the service provider to claim the value of the VTXO by revealing the secret value.
The output spending condition of this abstention transaction is $(S + secret)\ or\ (A + \Delta t)$. Roughly speaking, the secret value check can be implemented by using a simple hash lock, but it can also be implemented using "adapter signatures" in Taproot's key spending path (Schnorr signatures), which can save some bytes.
forfeit tx:| inputs | outputs | +=========+============+| exit tx | S + secret || | or A + Δt |+---------+------------+After the user signs the waiver transaction, the service provider tells the user the secret value, which allows the user to access the new VTXO.
If the service provider refuses to hand over the relevant secret value after the user signs the waiver transaction, the user will be forced to attempt a unilateral exit. Ultimately, either the money will be returned to the user, or the service provider will reveal the secret value on the chain.
in conclusion
If CTV is available, we can completely eliminate all user interaction from the Ark round mechanism. VTXO refresh will become a completely asynchronous process, where users can freely register, service providers can independently issue new VTXOs, and users can complete the entire process by returning to the internet later.
If CSFS is available on top of CTV, offline refresh can even be used recursively. This allows service providers to automatically refresh VTXOs without user involvement, and users can delegate the task of monitoring correct behavior to a third party (a watchtower).
Erk and hArk can be used simultaneously. Users can always pre-sign Erk refund transactions in case they cannot be online in time, but still use the hArk method to manually participate in rounds, such as when they need to merge multiple VTXOs into one, or when they want to refresh as soon as possible.
We imagine that the above solution can greatly enhance Ark's user experience, Ark's usability in mobile scenarios, and the functionality that Ark service providers can provide.
(over)
