<p>Client side filters (neutrino) allow you to check whether a certain transaction is included in a block. This can act as a proof of non-inclusion.</p>

<p><a href="https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki" rel="nofollow noreferrer">https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki</a>
<a href="https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki" rel="nofollow noreferrer">https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki</a></p>

<p>Note that this is not part of consensus, so nodes could lie to you. There won't be an SPV merkle proof connected to PoW, so perhaps it's not good enough for what you have in mind.</p>

CC BY-SA 4.0
2018-08-28T17:08:30.963Z
2018-08-28T17:08:30.963Z
Ruben Somsen
<p>There is no known way to do this with the current consensus rules nor does it seem likely except via computationally expensive general ZKP.</p>

<p>The normal way to make compact proofs of non-membership is to have a hash tree which is ordered by the key you're looking to prove non-membership on.  The proof is just the two neighbors that are greater and lesser than the key in question.</p>

<p>To show non-membership in a block this with a general ZKP (like bulletproofs) you would have to write an arithmetic circuit that computes the hash root of a block, and also scans over transactions looking for the thing-of-interest.  If done using a bulletproof the proofs would be log in the size of the circuit, and take time to prove and verify linear in size... so they'd be somewhat slow but bandwidth efficient.</p>

CC BY-SA 4.0
2018-07-31T03:38:54.470Z
2018-07-31T03:38:54.470Z
G. Maxwell
<p>So light SPV clients give the user the ability to obtain merkle proofs (from a full node) that a given transaction is included in a block. Is there some cryptographic mechanism by which an SPV client could obtain proof that a transaction (or type of transaction) is <em>not</em> included in a block, while still being relatively "light" (O(log(n), say)?</p>

<p>Asking for a layer 2 solution ;) </p>

CC BY-SA 4.0
2018-07-30T19:38:24.253Z
You could check if it's in the mempool (this means it hasn't been confirmed yet). But, are you talking about any arbitrary transaction that may or may not have been submitted to the network?
JBaczuk
CC BY-SA 4.0
2018-07-30T20:01:42.997Z
I'm talking about transactions included in a block - I want my SPV to be able to ask a full node to prove that no blocks contain, say, a transaction that has a given address in its inputs or outputs.
DZack
<bitcoin-core><lightning-network><merkle-tree><spv>
Can SPV clients offer "proof of absence" of a transaction?
DZack
# Can SPV clients offer "proof of absence" of a transaction?

(Asked by: username_0 on 2018-07-30)

So light SPV clients give the user the ability to obtain merkle proofs (from a full node) that a given transaction is included in a block. Is there some cryptographic mechanism by which an SPV client could obtain proof that a transaction (or type of transaction) is *not* included in a block, while still being relatively "light" (O(log(n), say)?

Asking for a layer 2 solution ;)

**Tags:** bitcoin-core, lightning-network, merkle-tree, spv

> **Comments:**
> **username_1**: You could check if it's in the mempool (this means it hasn't been confirmed yet). But, are you talking about any arbitrary transaction that may or may not have been submitted to the network?  
> **username_0**: I'm talking about transactions included in a block - I want my SPV to be able to ask a full node to prove that no blocks contain, say, a transaction that has a given address in its inputs or outputs.  

---

## 2 answers

### Answer by username_3 on 2018-07-31. Score: 5 | Accepted answer

There is no known way to do this with the current consensus rules nor does it seem likely except via computationally expensive general ZKP.

The normal way to make compact proofs of non-membership is to have a hash tree which is ordered by the key you're looking to prove non-membership on. The proof is just the two neighbors that are greater and lesser than the key in question.

To show non-membership in a block this with a general ZKP (like bulletproofs) you would have to write an arithmetic circuit that computes the hash root of a block, and also scans over transactions looking for the thing-of-interest. If done using a bulletproof the proofs would be log in the size of the circuit, and take time to prove and verify linear in size... so they'd be somewhat slow but bandwidth efficient.


---

### Answer by username_2 on 2018-08-28. Score: 1

Client side filters (neutrino) allow you to check whether a certain transaction is included in a block. This can act as a proof of non-inclusion.

<https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki>
<https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki>

Note that this is not part of consensus, so nodes could lie to you. There won't be an SPV merkle proof connected to PoW, so perhaps it's not good enough for what you have in mind.


---

