Instantly share code, notes, and snippets.

RubenSomsen/Ark_Diagram_1.svg

Last active February 19, 2024 14:26
Show Gist options
• 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
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
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
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

harding commented May 31, 2023

Thanks! I think that substantially matches my understanding and
hopefully matches what we published in this week's optech newsletter,
although I was a bit more abstract there as I knew my attempt to
reconstruct the details of the protocol was likely to differ from the
particulars he had in mind, and I didn't want a minor error in the
details to imply that the broader description was invalid.

In your description, you assume the OP_UTXO_EXISTS_VERIFY opcode exists.
I didn't feel like Keceli was actually pushing for that, so I ignored it
and looked at just the anchors version. (Also OP_UTXO_EXISTS_VERIFY
seems like a huge footgun for S during a reorg.) I think anchors only is
actually simpler and makes it easier to compare the protocol to previous
work by other people.

(timelock could be circumvented if A releases her privkey)

Nitpick, this is obviously correct but it might be better to say "with
A's cooperation". Releasing privkeys is always kinda scary, and
according to an interview with Keceli on the Stephan Livera podcast
(around time index 20m, I'd guess), he's planning to use silent payment
style addresses where the release of A's privkey would compromise all
her other funds.

Worst case redemption

Your OP_CTV analysis here seems accurate, but FYI, I got the
impression that Keceli is really looking for something like
OP_TLUV or OP_EVICT that will allow A to exit from the pool
for a fixed cost and will keep S's costs constant no
matter how many exits there are.

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.

I hadn't caught this implication, thanks!

Payment pool comparison [...] no messy issues with eviction

could call this an automatic evicting payment pool---if you don't pay
your monthly rent, you either need leave or the landlord gets all

I think maybe that idea could be applied to previously described payment
pools. E.g., the problem with n-of-n multisignature payment pools is
that it's combinatorial to create presigned eviction transactions for
each participant. But what if a pool of N "users" did:

``````multi(N, ...)
|| ( multi(N-1, ...) && older(28 days) )
|| ( multi(N-2, ...) && older(29 days) )
|| ( multi(N-3, ...) && older(30 days) )
...
``````

...and also n-of-n presigned N transactions giving each "user" an exit
for their funds which returns the remaining funds to the remaining N-1
"users"? ("Users" in quotes because multiple users could be the same
person, and we'd want to be robust against that.)

The problems with that approach are (1) your ability to spend can be
blocked for up to 28 days and (2) having to take an action within 28
days or you lose your money is kinda scary. Both of those problems also
apply to Keceli's approach. (1) is mitigated to a reasonable degree by
the service provider losing reputation and income if they go offline;
(2) remains a problem AFAICT---you could leave your exit transaction
with watchtowers, but they'd have to be trusted watchtowers since one of

Also, nitpick, your text says "1 month" but all your diagrams say "1
week".

Thanks again for the awesome description! I really wish I had this when
I started digging into the proposal.

@harding

I was a bit more abstract there

Makes sense to me, we write with different purposes for different audiences. My concern was mainly with trying to get people (myself included) to more easily understand the novel parts of the idea as opposed to fully accurately conveying what Keceli had in mind.

you assume the OP_UTXO_EXISTS_VERIFY opcode exists. I didn't feel like Keceli was actually pushing for that, so I ignored it

Yeah, I agree with your assessment. The only reason I chose to mention it is because it made my explanation of how the protocol works more succinct, which makes it easier for people to quickly grasp the concept. Maybe I can be a bit more explicit about that.

might be better to say "with A's cooperation"

I thought about that, but that won't be realistic in a setting where multiple coins exist within a single UTXO. People give up their claim at different times, so we can't expect them to all come together again to cooperatively sign after the last person got out. This is also not something Keceli proposed but something I decided to add simply to point out it's a possibility that could be considered.

he's planning to use silent payment style addresses where the release of A's privkey would compromise all her other funds

I haven't looked closely at that aspect, but I have a hunch there are ways in which you can design around such issues.

Your OP_CTV analysis here seems accurate, but FYI, I got the impression that Keceli is really looking for something like OP_TLUV or OP_EVICT

Yeah something like OP_TLUV seems promising here in theory, though in that section the scenario I was trying to sketch was about the version without any soft forks, including OP_CTV (in the pre-signed version you still have a tree of transactions, I believe).

I hadn't caught this implication, thanks!

Ah, that was actually a slight over-simplification of the reality in order to keep the document concise, but I'll expand on it here. Instead of a tree of ANCHOR_OUTPUTs Keceli suggests a linked list and requires the FORFEIT_TX to be signed multiple times to be compatible with any of the ANCHOR_OUTPUTs. This way the ANCHOR_OUTPUTs can be revealed one at a time, which is more on-chain efficient if you assume the number of anchors that will be required will not often exceed more than 1 or 2. So instead of expanding a log(n) tree for a single specific ANCHOR_OUTPUT, you'd only have to reveal a single ANCHOR_OUTPUT and another output containing the rest of the ANCHOR_OUTPUTs.

if you don't pay your monthly rent, you either need leave or the landlord gets all your stuff

I like this line of thinking and your ideas for how this might apply to payment pools. Will have to mull it over.

your text says "1 month" but all your diagrams say "1 week"

Yeah that's a mistake, thanks.

Thanks again for the awesome description! I really wish I had this when I started digging into the proposal.

Thanks for taking the time to read and comment!

RubenSomsen commented Jul 18, 2023

(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 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.

RubenSomsen commented Nov 20, 2023

@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 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 commented Nov 20, 2023

@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 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]