← index

A STARK proof of Bitcoin's UTXO set at block 972,500, with circuits proven in Lean

An archive of delvingbitcoin.org · view original topic →

· Henri · #1 ·

Hi everyone.

I’ve been working on a side project to see how far a STARK prover can go on Bitcoin consensus. Here is what I have so far.

Demo: Proven Bitcoin Repo GitHub - starknet-innovation/starked-bitcoin: Proving Bitcoin's chain with native Stwo AIRs, defined and proven in Lean · GitHub

What the proof says

There is one proof file (a “seal”) of 1.6 MB. A browser verifies it in about half a second. It shows three things:

  1. Headers. There is a header chain from genesis to the tip with the stated chainwork. Every header follows Core’s mainnet header rules: SHA256d linkage, proof of work, retargeting, median time past, minimum version and exact chainwork. The one exception is the wall-clock time-too-new rule. As with any SPV-style check, the verifier compares the chainwork against a trusted minimum.
  2. Blocks 935,001 to 972,500. Each block is replayed: raw block data against the Merkle root, txid and wtxid, Core’s structural block and transaction checks, amounts, and every coin created and spent.
  3. The coin set. The UTXO set after block 972,500 is the result of that replay. Its hash_serialized equals Core’s: Core’s gettxoutsetinfo / dumptxoutset at 972,500 gives 9f92d143…c8c4eb, the value the proof outputs. The proof also commits to a Merkle root over the set, so anyone can produce ~1 KB inclusion and non-inclusion proofs for single outpoints. The demo page does this by downloading one ~2 MB segment of the set per lookup.

What it does not say

How it’s built

A practical use: checking an assumeUTXO snapshot from anyone

chainproof verify-snapshot takes a Core dumptxoutset file and checks it against the seal: base block, coin count, total amount and hash_serialized. On a mainnet node running Core v31.1, I dumped a snapshot at 972,500 with rollback (164,539,066 coins, 9.39 GB). The check passed in 72 s using 0.5 GB of memory on an arm64 machine.

Today Core only loads snapshots whose hashes are hardcoded. Next, I plan to try a small patch that accepts a snapshot attested by a verified seal and skips background validation. That turns “a node in minutes” from a trust choice into a proof, with the caveats above. I expect this to be the controversial part, and I’d like opinions before going further.

Feedback is most welcome, and especially attempts to harden it. Cheers!

· Adam Gibson · #2 ·

Spec vs Core. The Lean specs are differentially fuzzed against Core’s own C++ code. That covers about 750,000 header-rule cases and 100,000 block and transaction cases, with 0 mismatches.

Very cool! I especially like this Lean part. It’s unfortunate about bitcoin that this fuzzing approach is the only one we can realistically take, but, good that you tried it.

You referred to batch signature verification indirectly (the message from Jonas you referred to was about the soundness of SNARK recursion), but that seems like a potentially interesting question here: I know that secp operations are going to be expensive in STARKs, but acceleration exists (I’ve been using it myself a bit in a project using RiscZero that provides that kind of acceleration), so I’m wondering if at some point you can’t do batch-verify on all the Schnorr signatures into one multi-scalar multiplication. Not even just blockwide, but blockchain-wide?

(I’m not even mentioning Scripts. I guess that part is easier than signatures).

I mean obviously even in this assume-utxo model this is already interesting, but “going the whole hog” would be even more interesting.

The longish verification time is presumably the same kind of O(log^2 n) that you get for communication/size, and why you have 72 seconds recorded. That’s a bit of a bummer. Could we consider doing the same trick as Risc Zero of “shrink wrap”: proof with Groth16 that the stark verifier passes, then get trivial verification time (the size doesn’t really matter, of course, but the time does I think. I’m imagining lighter clients like phones).

(At the same time I know a big part of the community is now considering anything non-QR as not interesting, but I disagree).

· Anthony Towns · #3 ·

I think it might be interesting to split this up into perhaps four parts:

I think a utxo-set-update proof system is likely to last longer and be more useful than the per-block validation stuff, because generally only the latter changes with any soft forks that might get introduced, and if you’re willing to take history for granted and just want to validate new blocks, then the utxo set verification is the hard part to be confident about.

I’m mostly speculating that by providing the complicated validation proof system with just the block and undo data/commitment (rather than the full utxo set), you might get more efficient proofs.

But I also think the undo data proof would possibly be helpful for things like swiftsync where you’re still running the validation code directly. And the utxo set maintenance should be reasonable to fully specify, I think, if you generalise it to also cover invalid blocks.

· Henri · #4 ·

Thank you both for the answers & interest! Replying to both in this post.

  1. A correction. I wrote earlier that the proof covers every rule except signatures and scripts, like assumevalid. Checking against @ajtowns’s list, two ConnectBlock rules are missing: BIP68 relative locktimes and the full sigop cost. Currently only legacy sigops are checked. P2SH and witness sigops aren’t. Core under assumevalid still enforces both, so today’s guarantee is a bit weaker than assumevalid. Both fit the existing design, since the undo records already carry each spent coin’s height and script. Time-based BIP68 locks also need older blocks’ median time past. I’ve updated the first post.

  2. To @AdamISZ comment on the 72 s checktime. My post wasn’t clear so I edited it. 70.7 of the 72 s is reading the 9.4 GB snapshot from disk to recompute its hash. The proof itself verifies in about 0.5 s in a browser (wasm). A Groth16 wrap wouldn’t buy much verification time. It would shrink 1.6 MB to a few hundred bytes, which matters for verifying on another chain though. The cost would be a trusted setup, and losing the hash-only security assumption that keeps a STARK plausibly post-quantum. I’d rather keep that for now.

  3. On batching Schnorr signatures. I agree that a random linear combination makes it one MSM, and nothing stops it spanning many blocks. I see two caveats: most historical signatures are ECDSA, which doesn’t batch the same way, and secp256k1 over M31 is foreign-field arithmetic, which I haven’t costed yet. It’s the obvious shape for a signature module.

  4. The 4 layers you mention @ajtowns are close to how this is built currently.

    1. A header chain proof: You’re correct it does not need ZK. What it gives is one proof for ~970k headers and an MMR commitment over block hashes that the later proofs bind to.
    2. Undo data commitments. Each block proof outputs a commitment to the block plus, per input, the spent coin (amount, scriptPubKey, height, coinbase flag), i.e. Core’s undo data.
    3. UTXO set updates. A multiset argument over coin events across the chain: each spend consumes an existing coin exactly once, the undo records are those coins, unspendable outputs are excluded, and the duplicate-coinbase cases match Core. It ends in Core’s hash_serialized
    4. Full per-block validation. Part of this is already in there: Merkle and witness commitments, CheckTransaction, finality, BIP34, legacy sigops, weight, and (because they need the undo data) coinbase maturity, inputs ≥ outputs and coinbase ≤ subsidy + fees. What’s missing: signatures, scripts, BIP68 and full sigop cost.

The difference from your split is that amounts and maturity sit with the coin-set layer rather than per-block validation. I agree with your main point: layer 3 is the long-lived part across soft forks and the hard one to be confident in, and it’s the part with the Lean soundness proofs. Your suggestion that layer 4 only needs the block plus its undo commitment is how the script module is meant to plug in. A proven undo commitment could also serve SwiftSync-style validation, as you say. I’d be happy to try that if someone wants it.

Thanks again to both of you for the review! I’ll keep working on this and see how I can make it better :slight_smile:

· Anthony Towns · #5 · · in reply to #4

What’s the (necessary) structure of the hash? Is it just a merkle-tree ordered by txid/vout (with MMR determining the layout), or is some rearrangement necessary?

I guess I’m wondering if it would be “better” if core output the merklized hash you use above, rather than (or as well as) calculating the current hash serialized?

Right – I’m mostly wondering if moving more stuff into the block validation layer could make the utxo-set-update proofs faster/cheaper (particularly on the proving side)?

In some sense block validation (given a trusted hash of the undo data) is the easy part: with a trusted link to the undo data, and no requirement to calculate the utxo set, you can use the actual code to validate blocks in parallel and out of order. Or you can just ignore it entirely, treating the assumeutxo/zkproof set as the “genesis/pre-mine”, on the assumption that that’s what everyone else has agreed upon, and has already been widely verified; just using your node to do full validation of future blocks, not past history, but being confident that it’ll report consistent results to anyone else who will ever accept any descendant block from the assumeutxo/zkproof point.

I guess I’m thinking:

If the utxo snapshot hash is a per-utxo merkle tree, that might also be useful in some sense for ~quarterly proof of reserves as well which presumably could also be done as a zkproof to avoid revealing explicit utxos.

· Henri · #6 ·

Hello hello, There are two structure for the hash. Both are over the coins in Core’s order (txid, then vout):

I guess I’m wondering if it would be “better” if core output the merklized hash

I think it would. Compared with hash_serialized it gives:

The open choice is the hash function. Blake2s (or another prover-friendly hash) is cheap to prove, but Core doesn’t have it today. SHA-256 is native to Core but much more costly to prove.

I’m mostly wondering if moving more stuff into the block validation layer could make the utxo-set-update proofs faster/cheaper

Possibly! But I haven’t measured the split yet. My expectation is that hashing the block bytes dominates the cost. And every layer needs that.

Amounts and maturity are a few columns on coin-event rows that exist anyway. I’ll measure the per-component cost and report back.

have core and this agree on a utxo snapshot hash that’s easy to calculate and easy to prove with / do this proof every 14,112 blocks / have the assumeutxo snapshot hash plus block hash at those heights be independently verifiable prior to downloading any data

If this is useful to Core I’d be happy to adapt whatever is needed to make it work. If there’s interest, I’d be glad to write up a concrete hash proposal (leaf encoding, tree shape, hash function) for discussion.

What you describe is close to what exists. The 1.6 MB proof attests the block hash at the snapshot height, hash_serialized and the Merkle root, and chainproof verify-snapshot checks the proof before reading the snapshot. What’s missing is your first point (a hash both sides compute natively) and a Core that accepts the result.

On proof of reserves: that is very doable. What is missing would be ownership signatures, and folding it in a zk proof.

As a follow up question: the current proof was generated from a assumeUTXO snapshot. Do you think it would be valuable to create a proof from genesis? I’m waiting before doing this, given it has a cost :smile: