The purpose of this is to write the idea down so we have it somewhere. It’s not a proposal in any way. I’d also like to point out that this wouldn’t solve 2-step txs.
Why
The intuition behind this idea is that changing the accumulator, that checks if an output has been spent, from a position based check to the element set membership check. This might eliminate replay attacks and allow for some safe transactions without kernels.
Currently, we check if an output has been spent by looking up the bit value at a certain position in the Bitmap MMR. This allows two commitments that are the same to be spent because they have a different position in the MMR.
Let’s see what would change if the accumulator would check if a commitment has been spent regardless of its position. Let’s call this new Bitmap MMR the spent output accumulator abrv. SOA short for spent output accumulator.
Claim 1:
This prevents replay attacks.
Why? Consider a 1-2 transaction T where Alice sends money to Bob through output O1. If Bob has not spent O1, then Alice can’t replay T because the O1 output already exists in the UTXO set and we don’t allow duplicates. If Bob spent O1, then Alice can’t replay T because it would try to recreate O1 which would be in SOA so the tx would be invalid.
Claim 2:
This allows for safe payjoins without kernels, but at the cost of no known way to do payment proofs.
Let’s assume we have a payjoin transaction T. Since in a payjoin, both parties have an input and an output, we could prove we know the private key of the excess by showing the private key of their difference excess_pk. This is unsafe today because one could do the “undo attack” where they would flip the input and output side of T and negate the excess by doing -excess_pk. This, however, seems impossible now because if T happened, then the reversed transaction would try to create output commitments that have been already spent, so the SOA would have these in the set and the non-membership check would fail, meaning that inversed transaction is invalid.
Claim 3:
This allows safe payjoins in 2-steps, but again without the payment proofs.
We can already do 2-step transactions without payment proofs. If Alice wants to send money to Bob, she creates a transaction T1 that has a kernel, but the tx is invalid because it lacks bob_v*H. Bob creates a transaction T2 that has a separate kernel and this transaction creates bob_v coins out of thin air and so is invalid. But their aggregate transaction is valid, so Bob can merge the two and broadcast. This comes at a cost of an additional kernel. If we had SOA, then this trick would come for free for payjoin transactions, because it would need no kernels at all.
Tradeoffs
The following are the good and the bad things I currently see (assuming we had an efficient set check accumulator).
Pros:
- replay protection
- payjoins possible without kernels
- payjoins without kernels allow safe 2 step txs (without payment proofs)
- not having kernels for some transactions blinds the number of transactions in an aggregated tx
- spent output accumulator becomes constant in size. The current Bitmap MMR is growing with the number of txos (though this isn’t really a practical problem)
Cons:
- accumulator might add new cryptographic assumptions (not sure what the consequences of would be if Bitmap MMR would be replaced)
- we don’t know how to do payment proofs without kernels
From my very limited understanding, perhaps a possible SOA would be the RSA accumulator and we would be checking the exclusion with exclusion proofs that I think can be aggregated. I also think that creating the exclusion proofs for the RSA accumulator doesn’t require having the set of the accumulator.
