atomic_txs.md

Transaction atomicity

Disclaimer: The author is NOT a cryptographer and is not saying this is a good idea, but believes it might be a direction worth researching further.

What

Consider we want to make two transactions atomic on Bitcoin. We'd like them to stay separate in the sense of inputs and outputs they use, but we want them to be atomic.

How

We consider two transactions separate if they don't share any input. Anyone seeing transactions T1 and T2 which are separate can join the two into an atomic group of transactions. To achieve atomicity, we can use Schnorr signature half-aggregation. Once we have half-aggregated their signature, you would need to know the original transaction signatures (deaggregated version) in order to deaggregate them. In this sense, it is easy for anyone to make two non-atomic transactions atomic, but it's impossible for someone that has not seen the transactions prior to becoming atomic to deaggregate them.

NOTE: This requires a new way of validating an atomic group. To validate a group of transactions that had half-aggregated signature, we use the procedure described in this video.

There's a newer Schnorr half-aggregation scheme which supports incremental half-aggregation meaning we could add a transaction with non-aggregated Schnorr signature to an already existing atomic group by applying half-aggregation. However, from my understanding, it unfortunately doesn't support grouping two already half-aggregated signatures into a single one. This would be ideal as we'd be able to eventually make the whole block a single half-aggregated atomic group.

Why

A couple of potential benefits of atomic transactions groups:

1. we get true atomicity of separate transactions - I don't really know what the benefits of this are yet, but I suspect there are benefits
2. new variants of privacy techniques
3. some space reduction is expected, but not as much as doing half-aggregation across the block

Below, I'll focus on some known privacy techniques done slightly differently through atomic groups.

Truly atomic CoinSwap

Consider Alice has output AO1 and Bob has output BO1. They both send some coins to someone and they end up with their change outputs AO2 and BO2. These change output chains continue forever. Essentially, we are continuing on our graph by always adding a new edge that links to our new output. Two main techniques to obfuscate the graph on Bitcoin are Coinjoin and Coinswap. Coinjoin tries to obfuscate which edge in the graph is the graph continuation. Coinswap on the other hand, exchanges the edge with another party while making it look like a regular edge continuation. The latter is much more powerful in theory because, if done right, the links aren't visible. Coinswap requires 4 transactions to exchange a graph edge and achieves this with pseudo-atomicity through multiple blocks. The benefit is that it should be impossible to tell with which transaction the graph was exchanged.

We can make a less powerful, but simpler and safer coinswap variant with an atomic group of 2 transactions. As mentioned, this is inferior because these two transactions would be visibly linked. However, since grouping two transactions into an atomic group is noninteractive, you wouldn't be able to tell if the two transactions were created atomically and thus the owners wanted them to be atomic (e.g. exchange of edges), or someone not involved in transactions just glued them together through noninteractive half-aggregation.

Example: Let's say Alice wants to fake a coinswap with a random transaction. She sees a transaction in Dandelion stem phase passing through that is not in an atomic group. She can see what outputs it creates and creates a self-spend transaction that produces the same outputs and then makes an atomic group from these two transactions prior to sending it forward in the next dandelion phase.

# Tx1 (stem tx with unknown owner)
5 -> 1
  -> 4

# Instead of sending this transaction forward, she creates an atomic group
# with a self-spend transaction to fake a coinswap.

------------ START Atomic group --------

# Tx1
5 -> 1
  -> 4

# Tx2 (Alice fake coinswap tx which is really a self-spend)
2 -> 1
3 -> 4

------------ END Atomic group -----------

What can an observer infer from seeing this transaction in the mempool? The transaction could be:

1. a truly atomic coinswap (exchange of edges)
2. two regular transactions
3. two self-spends (from 1 or more different owners)
4. a regular transaction and a payjoin
5. a combination of the above
6. something new?

If you don't know who to coinswap with, you can wait for a transaction passing by, produce an equivalent self-spend and make the transactions an atomic group. Even if the observer suspected one is a regular transaction and the other a self-spend, they won't be able to tell which one is which. With Incremetal Aggregation Schnorr scheme, it would be possible to add a transaction (or many) to an atomic group of transactions that we see.

Disjoint CoinJoin

Note that in the example above it's impossible to know where the input 2 truly continued the graph. It could have been in any of the 4 outputs that are present in the two transactions. This property is similar to that of a coinjoin where an input could go to any other output. Atomic groups could be used for coinjoins as well. Two parties could construct a coinjoin in two separate transactions and make an atomic transactions group out of it. This way, coinjoins can't be told apart from regular transactions that were atomically grouped together by a random person that saw these. These coinjoins can also scale to multiple parties and multiple transactions.

Open questions

1. Is there a simple way to prevent the other party from deaggregating the tx by computing s value prior to half-aggr sig key scaling?
2. Can atomic set merging be done more than once making it a monoid structure similar to Mimblewimble transaction aggregation? In other words, can we merge two atomic sets into a single atomic set? - I suspect the answer to this might be yes, but may require new security proofs and may come with more curve operations
3. Schnorr half-sig aggregation on signatures breaks adaptor signature assumption. Is there a way around this? Does atomicity bring something new to the table that may be worth this?
4. What are some other applications that can be done by using atomicity of two transactions?
5. Are there other ways of exchanging an edge?
6. It is possible to make N transactions atomic, not just two, what are the use-cases of that?