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