pull down to refresh

pons: Proof Of Non-Spam for Bitcoin - AbdelStarkgithub.com/AbdelStark/pons
1092 sats \ 10 comments \ @Scoresby 6 Aug bitcoin
Abdel (@dimahledba on X) posted this pretty cool note about using starks to prove that a bitcoin transaction is not "spam."1.
People can stick arbitrary data in a transaction by making it look like any number of things: a public key, a script, a merkle root, a hash. Abdel is proposing a way of using stark's to prove something like a public key is an actually valid public key that corresponds to a private key. Whether or not you think spam is a problem, it's always delightful to see bitcoiners wonking away at solutions.
Here's Abdel's post so you don't have to go look it up:
Hear me out, PONS: Proof Of Non-Spam for Bitcoin!
I was discussing with @LukeDashjr about various usage of ZKP for Bitcoin, and he came with this intriguing idea to use Zero Knowledge Proofs to fight spam on Bitcoin (without breaking some designs such as BitVM). Initially I was sceptical, but the more I think about it, the more I am convinced that it could be a very interesting idea to explore.
Just to be concrete, here are some examples of valid / non spam materials that could be theoretically proven via a system like PONS:
  • Schnorr public keys: Prove knowledge of corresponding private key
  • Hash preimages: Prove knowledge of data hashing to claimed values
  • Taproot scripts: Prove leaf scripts are valid Bitcoin Script, not arbitrary bytes
  • Merkle roots: Prove correspondence to actual Merkle trees of valid elements
As usual, I like to experiment and play with ideas, so I started to implement a proof of concept of this idea, for the minimalistic simplest example here that is: prove that a public key is "real" and not a "fake" public key.
You can see in the demo video below the following flow:
  • Generate a Schnorr public key and its corresponding private key
  • Create a digital signature of an arbitrary message
  • Run a Cairo program that verify the signature against the public key
  • Generate a STARK proof of the Cairo program execution using STWO prover
  • Verify the STARK proof using STWO verifier
Sorry @LukeDashjr I know that you consider Rust as a woke language haha, but for now we have the STWO prover and verifier only implemented in Rust, so I used it for the demo. We can easily integrate the STWO verifier in Bitcoin Core or Knots via ffi though (as we already did in another POC).
So of course here it's completely overkill to use a STARK proof for this and you could do it much more efficiently without a ZKP, but it is to show how the architecture could look like end to end.
There are many interesting design questions, like how to make nodes / miners play nicely and prioritise transactions with valid proofs, how to incentivise the generation of proofs, how to make it efficient and not bloated, etc.
I am curious to hear your thoughts on this idea, and if you think it could be a good idea to explore further.
There's also a video demo

Footnotes

  1. I'm still in denial that any valid transaction can be spam, but the conversation has been beaten to death at this point -- but I'm still going to stick some scare quotes around the word. ↩
write
preview
related posts
504 sats \ 0 replies \ @kepford 6 Aug
Its rather funny to me. Just thought of this again, bitcoin has always had an anti-spam mechanism. The transaction fee market. It works...
I mean, I'm open to arguments that it could be improved but the sky is falling nonsense we've been subjected to recently is dumb to me. But what do I know. I'm just a pleb.
reply
212 sats \ 3 replies \ @oomahq 6 Aug
I don't get where this idea that fees are a spam prevention mechanism came from. Fees are just to bid miners for transaction confirmation.
As a counterexample, spam completely obliterated the UTXO set in the 2023-2024 period while fees where generally very high.
https://mainnet.observer/charts/utxoset-by-count/
reply
100 sats \ 2 replies \ @Scoresby OP 6 Aug
If a transaction follows Bitcoin's consensus rules, it will be included in a block if it pays enough fees to convince some miner to put it in a block they find. The only thing that could possibly prevent a transaction from ending up in a block is if the block is filled with other transactions.
The fact that you can offer a bigger fee and incentivize miners to include your transaction rather than those other transactions means the transactions that end up in blocks are those that people were willing to pay the most to put in blocks -- which is my definition of not spam. The fee market means the blockspace goes to the people to whom it is most valuable.
If, however, you don't agree, and you think some valid transactions are spam, we now need to figure out by what criteria we should divide the spam from not spam. This is an endless argument that only ends in two options: change the consensus rules or try to stop the transactions from getting to miners. I think both are fool's errands.
If someone wants to pay 1000 sats per vB to obliterate the UTXO set they can -- the only thing that stops them is someone else being willing to spend more than 1000 sats per vB to do a less utxo-set-obliterating transaction.
reply
0 sats \ 1 reply \ @oomahq 6 Aug
To give a clear-cut definition of spam this common misconception that "transactions bid for blockspace" has to be dispelled first:
Transactions bid for (more or less timely) confirmation, not space in blocks.
In fact "purchasing blockspace" is an undesired side effect to real Bitcoin users. If a new type of address was introduced whose transactions were half the size of the current ones a lot of users would adopt the new format just to pay half the fees at any given feerate. If you could confirm your transaction by purchasing no blockspace at all you would (and that's the idea behind LN: a single onchain tx supports a theoretically infinite number of offchain balance updates of that tx). This dynamic leads to a virtuous cycle where tx footprint gets smaller, users pay less fees, and so more users can use the chain.
On the other hand spammers are true purchasers of blockspace, something that Bitcoin is not designed for (and thanks to the SegWit discount they even get a 4x cost reduction byte per byte). This leads to a vicious cycle where only just a few spammers can quickly purchase all the available blockspace, spike the fees and so less people can use the chain.
Bottom line, since the legit group of bidders want to minimize their purchase of blockspace, while the spammers want to maximize it (and even gets a discount) there's only one possible outcome that we've already seen plenty of times: denial of service. Obviously all that is immaterial to the fees. If someone paid 10 bitcoins in fees to inscribe a hi-res video over the next 1500 blocks as one huge tx per block, that's still spam.
reply
0 sats \ 0 replies \ @nitter 6 Aug bot
https://xcancel.com/udiWertheimer/status/1087142827346354177
reply
202 sats \ 1 reply \ @Filiprogrammer 6 Aug
Really cool in theory! But this might not be practicable. Everyone making a transaction would also have to publish a proof. And verifying a proof also comes with some computational cost, potentially opening up a DoS attack vector.
reply
70 sats \ 0 replies \ @Scoresby OP 6 Aug
yeah, it's hard to beat miner fees as a spam prevention mechanism.
reply
0 sats \ 0 replies \ @ZezzebbulTheMysterious 7 Aug
Luke considers rust “woke”? Uhhhh
reply
0 sats \ 0 replies \ @BITC0IN 6 Aug
interesting
reply
0 sats \ 0 replies \ @nitter 6 Aug bot
https://xcancel.com/dimahledba/status/1953085230593487089
reply