Skip to content

Instantly share code, notes, and snippets.

@RubenSomsen
Last active September 10, 2024 07:08
Show Gist options
  • Save RubenSomsen/a394beb1dea9e47e981216768e007454 to your computer and use it in GitHub Desktop.
Save RubenSomsen/a394beb1dea9e47e981216768e007454 to your computer and use it in GitHub Desktop.

Simplest Ark Explanation

A footprint-minimal coinswap protocol. Alice gives a coin to the Server, provided the Server gives a coin to Bob. There is no trust involved. Because all swaps go through the Server and the timelock eventually expires in their favor, a large number of swaps can be aggregated in a single UTXO that is efficiently on-chain redeemable by them. This comes at the cost of not being able to instantly access their funds, meaning the Server ends up locking up a substantial amount of coins.

Explanation

All transactions that are involved with A sending to B

Holding coins

Alice (A) holds coins with Server (S) that she can trustlessly redeem

On-chain UTXO_1 looks as follows:
A+S || S in 1 month

A has an off-chain REDEEM_TX (signed by S) that spends from UTXO_1 with the following output:
A+S || A in 1 month

Preparing to send coins

Now A wants to send her coins to Bob (B)

S promises to fund and create new on-chain UTXO_2 that will look as follows:
B+S || S in 1 month

B receives an off-chain REDEEM_TX (signed by S) that spends from UTXO_2 with the following output:
B+S || B in 1 month

If UTXO_2 appears on-chain, B will be paid.

The swap (the important part)

A wants to forfeit her claim on UTXO_1 (i.e. A to S) provided UTXO_2 appears on-chain (i.e. S to B)

In order to achieve this, A signs the following FORFEIT_TX that spends her REDEEM_TX:
S if UTXO_2 exists* || A in 1 month

*This kind of script is not possible today but is easier to explain, actual non-softfork version explained later

The effect is that S can claim the funds from UTXO_1 if UTXO_2 is published.

Possible outcomes

Ideal/expected outcome:

  • S publishes UTXO_2, meaning B got paid
  • A won't publish her REDEEM_TX
  • The timelock on UTXO_1 expires and S claims the funds (timelock could be circumvented if A releases her privkey)

Outcome adversarial A:

  • S publishes UTXO_2, meaning B got paid
  • A publishes her REDEEM_TX
  • S publishes the corresponding FORFEIT_TX and claims the funds

Outcome adversarial S:

  • S never publishes UTXO_2, so B did NOT get paid
  • A publishes her REDEEM_TX
  • S publishes the corresponding FORFEIT_TX
  • The FORFEIT_TX timelock expires and A claims the funds

Outcome offline A:

  • A fails to ask S to transfer the funds to B
  • A fails to publish her REDEEM_TX in time
  • The timelock on UTXO_1 expires and S claims A's funds

On-chain efficiency

The protocol that was described thus far isn't any more efficient than A simply sending an on-chain payment to B. The final trick is that a single UTXO can contain coins for multiple users.

UTXO_1 is being shared here by two users and is eventually fully claimable by S

For instance, let's say A and B both had coins in the same pool as illustrated above. UTXO 1 would then be A+B+S || S in 1 month and this would branch off in a tree to two off-chain UTXOs with A+S || S in 1 month and B+S || S in 1 month. If both A and B forfeit their claim as expected, the off-chain UTXOs will never go on-chain. This works with any number of users and is what makes the protocol efficient.

Creating this transaction structure currently requires A+B+S to pre-sign, meaning all recipients have to interact with each other whenever a new UTXO is being created. OP_CTV would remove that requirement (update: this scheme similarly reduces interactivity without requiring CTV).

Worst case redemption

A single user might publish a REDEEM_TX. That single user will have to pay the fees to expand the tree of off-chain transactions and reach their specific output. This is costly to that user and thus puts a economic limit on what the smallest viable denomination inside Ark could be.

Also, since the tree got expanded, S now has to spend log(n) outputs instead of 1 in order to claim the funds.

Cooperative on-chain exit

Instead of swapping for a new off-chain REDEEM_TX with S, it is also simply possible to swap for an on-chain output without any timelocks, allowing for an optimally efficient exit.

"if UTXO_2 exists" without soft fork

The transaction that contains UTXO_2 could contain another small ANCHOR_OUTPUT that can only be spent by S. A can then include it as an input to her FORFEIT_TX to S. Now the FORFEIT_TX can't be sent on-chain unless the transaction containing UTXO_2 as well as the ANCHOR_OUTPUT go on-chain first, thus fulfilling the "if UTXO_2 exists" condition.

The ANCHOR_OUTPUT can be kept off-chain by placing it inside an off-chain tree of transactions, though this does mean S has to expand the tree if it ever needed the anchor.

Payment pool comparison

The main upside is the simplified interaction and no messy issues with eviction - spending coins doesn't require you to interact with all the people in the pool, just S.

The main downside is reduced liquidity - the coins the Server receives back won't be available to them immediately, so the faster coins move hands, the more of S's liquidity becomes locked up. If we assume a locktime of 30 days and on average 1BTC moving hands every 10 minutes, then S will end up having 6 * 24 hours * 30 days = 4320BTC locked up.

Confirmation times

A transfer isn't complete until the relevant UTXO confirms on-chain. However, if the recipient is willing to trust S never to change transactions that are waiting to be confirmed, transfers could be subjectively viewed as instant.


The aim of this write-up was to concisely explain the core concepts behind Ark, as the original documentation has been difficult for many (myself included) to comprehend. Full accuracy was not the goal - and a lot of it was educated guess work / reverse engineering - so the actual Ark design will perhaps differ somewhat (though hopefully not massively) from what is written here.

Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@RubenSomsen
Copy link
Author

(This explanation assumes you've read my Ark write-up)

Reducing Ark Interactivity Without Soft Fork

Currently both senders and recipients need to be online simultaneously to transfer value in Ark. This requirement can be reduced by a soft fork (i.e. OP_CTV). We can eliminate the need for a soft fork by giving both the sender and the recipient the option to complete a swap with S, allowing the recipient to complete the payment on their own. This method preserves proof of payment and has no race conditions.

Let's say A wants to send to B. A gets S to sign a new REDEEM_TX_AB with the following script: B+S or A+S or A in 1 month (i.e. adding the B+S condition). We ensure the new REDEEM_TX_AB becomes valid before the old REDEEM_TX_A with timelocks. Now A foregoes her claim on the old REDEEM_TX_A by signing an unconditional FORFEIT_TX, thus allowing S to simply claim the money if REDEEM_TX_A ever gets published.

A now sends REDEEM_TX_AB to B, who can claim the payment by swapping with S. If B isn't responsive, A can perform the swap instead, or attempt to repeat the same steps with another recipient (note each attempt decrements the timelock - this could be mitigated as well but probably isn't needed).

Proof of payment can be obtained from S once B performs a swap. If S maliciously refuses to cooperate (i.e. neither shows a proof of payment or performs a swap), A can force S's hand by publishing REDEEM_TX_AB, forcing S to reveal whether B has swapped (i.e. if B signed a FORFEIT_TX).

@tromp
Copy link

tromp commented Nov 20, 2023

Were the players of a correspondence chess game back in 1804 [1] also "online simultaneously" ?
Better to say that sender and recipient need to exchanges messages.

[1] https://www.nytimes.com/2022/11/09/crosswords/correspondence-chess.html

@RubenSomsen
Copy link
Author

@tromp I agree it's a bit vaguely worded. It's hard to describe exactly what is going on and still be succinct. Basically the server will interact with a bunch of senders and recipients, and only if everyone agrees and completes the protocol (a couple of roundtrips) can this batch of transfers be finalized. If this all doesn't occur within a minute or so, a new round would have to be started while excluding the slow/unresponsive parties.

This seems like a big bottleneck to me. The more people you try to "simultaneously" interact with in this fashion, the higher the likelihood that your rounds will fail. My proposed change improves on this by allowing recipients to complete this step without requiring further interaction from senders (the senders also interacted with the server, but this interaction is no longer time-sensitive), thus cutting the number of involved participants in half.

@tromp
Copy link

tromp commented Nov 20, 2023

Why must the round complete within minutes?
Why couldn't it happen on larger timescales, like an hour, or a day?
(I'm sorry is the answer is obvious; but I haven't studied Ark in any detail).

@RubenSomsen
Copy link
Author

@tromp it's a fair question. Conceptually it's somewhat similar to the required interactivity in coinjoins, so you could look at how those protocols are designed to get a sense for it, but here are some reasons:

  • Limiting DoS potential, as the longer you're willing to wait, the more effective you make attacks with deliberate non-responses
  • A "round" consists of multiple roundtrips, and if you wait too long before starting the next roundtrip, it's increasingly likely that by then other people will become unresponsive, sort of a multiplicative effect
  • It's costly to have many active and unfinished rounds of which many will end in failure because the server has to put up the capital to fund all the swaps in a round (probably also makes it harder to start rounds in parallel)
  • Better UX, users want to know whether their transfer went through instead of being left with uncertainty

@tromp
Copy link

tromp commented Nov 20, 2023

required interactivity in coinjoins, so you could look at how those protocols are designed

The one I did design [1] fortunately has no required interactivity, but I can see how coinjoins for other chains need to deal with many possible attacks that aggravate with longer running times.

[1] https://bitcointalk.org/index.php?topic=567625.msg56288711#msg56288711

[1]

@cluelesStudent
Copy link

Hi there, thanks a lot for the write-up; it improved my understanding a lot, but I am not quite there yet. A question I still had; isn't B at risk of having his funds forfeited if he completes the swap and A (maliciously?) publishes REDEEM_TX_AB afterwards (essentially emulating a double-spend by B)? With this transaction now on-chain, S could post the FORFEIT_TX signed by B to claim his funds?

Thanks in advance!

@RubenSomsen
Copy link
Author

RubenSomsen commented Sep 9, 2024

@cluelesStudent thanks for taking the time to understand the scheme.

S could post the FORFEIT_TX signed by B to claim his funds

The FORFEIT_TX alone still doesn't determine whether B or S gets the funds (output script: S if UTXO_2 exists* || B in 1 month). This is described in the initial write-up. If the swap was properly completed and B received money from S (i.e. UTXO_2 went on-chain), then S can claim the output in the FORFEIT_TX. If the swap wasn't completed then S will be unable to claim it and the money goes to B after a timelock.

Edit: the part that probably confuses you is that there are two types of forfeit transactions (a conditional one and an unconditional one) and I didn't particularly label them differently.

@cluelesStudent
Copy link

@RubenSomsen Right, I see, this is exactly what I confused. There are two different forfeit transactions and as B performs a swap with S he will sign a conditional forfeit instead of an unconditional one. B's funds cannot be stolen the way I described earlier, indeed.

Thank you for your swift and clear response!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment