Replay resistance through payjoins and aggregators

I’ve been thinking about the replays and aggregators and I think this is another option that is similar to anchors, but without anchors. The idea was described in this gist and below is a paste of its content:

Replay resistance through aggregators

One of the previous protections against replay attacks required the attacker to replay a sequence of payjoin transactions until the attacker was met with an impossible requirement of replaying a transaction that was impossible to replay due to a duplicate output (anchor solution) consensus rule violation.

This is an attempt to not introduce an absolute protection as the anchor solution does, but perhaps something that is for most practical concerns a good enough solution.

Main idea

Let’s assume we have a daily aggregator A. Every transaction that gets published on the chain also sends a coinswap for each created output to A.

Let’s reuse the idea of making every transaction a payjoin. We now have the same first step part of the attack protected in the same way which is that the attacker would need to replay a sequence of payjoin transactions. But we lack the initial condition which would make it impossible to replay the first transaction.

Let’s assume we get an output from a daily aggregator O1. If a significant aggregation took place in A when O1 was created, then we can assume that it is extremely hard to replay the aggregated transaction that created O1. This is because all the outputs in the aggregated transactions need to be spent and the attacker would also need to know how to generate all the inputs of the aggregated transaction which seems almost impossible to do. The output O1 can thus play a similar role as an anchor, but can be spent.

All we have to do is know which outputs were ‘coinswapped’ and then use these as inputs for our payjoin transactions.

In order to be able to do simultaneous transactions, the wallet makes sure it has N “safe” outputs available. We could label a coinswapped output as “safe” by using one of the zero bits in the bulletproof and setting it to 1.

Note: When doing a payjoin with a safe input B_I', then the output we create B_O is also safe.

Wallet algorithm

Send

Alice (sender) has an input A_I and a change output A_O. After the transaction has been broadcasted, A_O' is created with a bulletproof coinswap bit set to 1 and A_O -> A_O' is sent to the daily aggregator.

Receive

Bob (receiver) contributes an input B_I' (coinswapped) to the transaction, making a payjoin. Bob also has an output B_O and similarly as in the case of Alice, after the transaction has been broadcasted, B_O' is created with a bulletproof coinswap bit set to 1 and B_O -> B_O' is sent to the daily aggregator.

First receive

It is impossible to contribute a coinswapped input when you don’t own any output. The first receive can be made safe if the received output is coinswapped in the aggregator before doing any other transaction.

Improvements

This is hard enough to replay as is, but can be made basically impossible if the daily aggregator contributes aggri-1 -> aggri to the daily aggregated transaction i and then in i+1 adds aggri -> aggri+1 and so on. This would require the attacker to replay everything from all the daily aggregators which is practically impossible.

3 Likes

Very nice idea, it does seem pretty much impossible to replay the aggregated tx since you would need to replay all of its inputs. The improvement part just makes it even way harder. I feel like this solution might be superior to anchors (basically the same idea but without creating the unspendable utxos), the only downside i see is that it doesn’t guarantee 100% protection, but i think the difference is negligible. Also want to point out that anchors and default aggregators don’t play well together because it would be very simple to spot anchors (everything goes in the aggregator except anchors).

I like it, especially that it removes the need of anchors with hardly anny costs in security. Replaying all daily aggregations is practically inpossible.

I’ll reiterate the anchor “impossible to replay condition” and show why the trick used in this alternative might be good enough. We define a safe transaction to be one that can’t be replayed. A transacting party is safe from a replay attack if this party contributed an input that was created in a safe transaction. The main idea in this approach is that we assume that the daily aggregated transaction is a safe transaction. Let’s investigate what happens if we apply the idea in the “improvements” section.

Every day from day 1 to day N, the daily aggregator broadcasts an aggregated daily transaction.
Let’s assume that we created our safe output in the daily transaction Ti. Let’s also assume all the outputs were spent from transaction Ti - if they weren’t spent, then it’s not possible to replay Ti until they were. If the attacker wanted to replay Ti, then they would need to recreate all the inputs of Ti which means that they would need to replay all the transactions that create these inputs.

The input can come from one of these transactions:

  1. A transaction is an initial transaction - we know we can protect this one by sending to the daily and not using unsafe output before we get safe outputs from the aggregator
  2. A transaction comes from a payjoin - in this case the attacker would need to replay a previous transaction which is again one of these 3 options
  3. A transaction comes from the daily aggregator

The 3. is where things get fun. One of the coinswaps is added by the aggregator which is aggri-1 -> aggri. This means that to recreate the input aggri-1, the attacker would need to solve this same replay problem also for the previous aggregated daily transaction Ti-1, and because Ti-1 contains aggri-2 -> aggri-1, the attacker would need to solve this same problem also for Ti-2 and so on until they would need to recreate all the inputs also for the first daily transaction T1. In order to make the replay impossible to do, we need to know that the aggregator is in fact adding the aggri -> aggri+1 (we could check that one coinswap is only being transfered from daily tx to the next daily tx) and then all we need is that out of all the transactions that we would need to be replayed, only one has to have an unspent output which would make it impossible to replay and hence it would make impossible to replay the whole chain needed to pull off a replay attack. It is exceedingly unlikely this would not be the case, and the probability would continue to get better with each daily aggregation.

In the anchor solution, each user created a single transaction for which we were guaranteed can’t be replayed - a transaction that contained an anchor. In this alternative approach, we assume that as the daily aggregator keeps broadcasting the dialy transactions, the probability of an unspent output not existing get smaller with each daily aggregation. A random unspent output that was forgotten will serve as an anchor for everyone involved in the daily aggregation.