Bitmap MMR vs set accumulator

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.


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.


The following are the good and the bad things I currently see (assuming we had an efficient set check accumulator).

  • 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)


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


Interesting idear. A few things that come to mind based on my own limited understanding.

  1. Can range proof of spend outputs still be thrown away when using such an appraoch using SOA?
  2. Would it be a replacement or a parralel alternative to normal transactions?

I guess for performance reasons it would be best if these are ‘special transactions’ that require checking at multiple positions (which I assume comes at a performance cost) are somehow seperated from the other transactions. Which I have no idear if it is even possible since to my understanding the Grin blockchain is basically one big transaction, unless you put these special kernel less transactions in a sort of side chain. I am not expecting an answer, just some thoughts that came to mind.

  1. This doesn’t in any way impact rangeproofs. Nodes that would have the ability to seed new nodes need to have them, others can prune them

  2. Well, what I described is not ideal because we have no payment proofs (and possibly other reasons as well). This would be a normal payjoin that could be done in 2-step way and not come at a cost of an additional kernel but at a benefit of not needing a kernel

The above idea is, for reasons mentioned above, not ideal though. You likely don’t want new assumptions for these cases. The more interesting part is that if a set accumulator exists that can be used without new crypto, then perhaps it would be worth looking at imo.
Why? Because what’s common to both replay attack and the undo attack is that they want to create an already spent input. This becomes impossible so they go away.

P.S. while the undo attack goes away, only a payjoin transaction is safe without a kernel. This is because if you have not contributed an input, then the other party can find you excess private key and spends your outputs.

1 Like

So if I understand it correctly it is something very similar to Bitcoins Merkle root proofs which are used as payment proofs by light clients.
So what is the difference in this case, any link or paper on what exclusion proofs are? Or with exclusion proofs you mean checking all inclusion proofs, to prove exclusion or something?

Bitcoin SPV clients can use Merkle proofs to see that their tx is included in some block, but cannot verify the correctness of blocks themselves. That’s what distinguishes them from full (i.e. fully verifying) nodes.

A nimble Grin node is still a full node however. What it can’t do is seed other nodes.

1 Like

A ok, so in a sence this would superior to Merkle proofs. Could you specify here what the corectnes of a block means, no double spend outputs?

Edit: I think I start getting it. So on top of agregating the transactions you prove exclusion of an output in a block meaning no double spend?

Note here that you can build an exclusion proof just from having the accumulator and the element, then you can batch these.

P.S. it’s possible i’m misunderstanding it

Just a thought. If a receiving party would commit a small input, e.g. transaction fee, and the sender would automatically increase any send amount witht he transaction fee, two step transactions using SOA can also be used for normal transactions keeping the receiver safe using this small commitment. This would leave the lack of payment proofs as major con, I do not think there are any new cryptographic assumptions.
Anyhow, I am sure it crossed your minds as well. Just thinking that using the transaction fee would be handy since it is standardized and can as such be computed by both sides before hand where the sender sets the transaction fee. Not sure though if this allows the receiver to lower the transaction fee as such slightly increasing the amount he/she gets.

Edit: Or maybe better to let the receiver commit half of the transaction fee and highten the senders amount with half the transaction fee. I am not certain, but there might be benefits to having this simetry in transaction fee commited by both receiver and sender such as 1) maybe making it harder to determine directionality of the transaction 2) preventing skimming of the transaction fee by the receiver since you can enforce that both need to commit an equal transaction amount to the transaction fee. Alternatively, the sender could sign for the transaction amount in order to fix it. :thinking:

I think the best way to split transaction fees is for each party to pay for their own inputs and outputs, and to split the kernel (that they both sign) fees 50/50.