Bitcoin SPV Prover SDK

[Alex-distributed-lab]

This proposal outlines the development of a Bitcoin Simplified Payment Verification (SPV) prover implemented in the Noir language. This tool will enable developers to generate sophisticated proofs concerning the Bitcoin blockchain, with the long-term objective of establishing comprehensive Bitcoin-type definitions, data structures, and ecosystem components within the Noir environment.

Rationale

We want to extend the Noir language ecosystem with robust mechanisms for facilitating interoperability between EVM and Bitcoin-like networks. Our first step included developing the SPV contract, which collects and verifies Bitcoin block headers, manages reorganization, etc. The biggest problem with the naive SPV contract is the operating cost. Having a single block header verification ~$1.7 (on Ethereum, as of May 19th) and around 900,000 blocks in Bitcoin, we can calculate the cost of full synchronization >$1.5m. So, an initial idea included covering the majority of verifications with a recursive proof and launching SPV from the n-th block.

Then we came up with the idea of creating a library for the Noir that covers some additional points and provides an opportunity to build a bunch of practical things, like:

• Proof of Bitcoin blockchain history integrity
• Proof of transaction occurrence (expenditure verification)
• Proof of knowledge of expenditure conditions (Taproot leaf or P2WSH preimage)
• Proof of knowledge of a valid script witness satisfying a specific expenditure condition

Furthermore, this initiative will introduce standardized libraries for Bitcoin entities, including types, algorithms, and data structures, to the Noir toolchain.

Methodology

The implementation will proceed in three phases.

Phase 1: Simple History Validation

This phase involves verifying block hash integrity, confirming the equality of the previous hash field in a block header with the preceding block's hash, and validating difficulty adjustments based on block height.

Two approaches are proposed:

1. Generating a proof for N blocks starting from the genesis block.
2. Employing a recursive strategy to prove chunks of 2016 blocks. Block headers are private; however, hashes from the first to last block are public, along with the proof from the preceding 2016-block set. The chunk size corresponds to the block count considered for difficulty retargeting.

Phase 2: Validation of Output Expenditure and Preimage Knowledge

Building upon the established historical validation and implementation of Merkle trees with double SHA256 hashing, verification of transaction inclusion within a block's Merkle root becomes feasible. This extends validation to full blocks with transactions and allows users to demonstrate the existence of a transaction within a particular block. This is particularly useful for verifying the spending of Bitcoin outputs.

Additionally, this phase involves proving knowledge of expenditure conditions for P2WSH, P2SH, and P2TR outputs. For P2WSH and P2SH, this entails proving knowledge of the SHA256 preimage. P2TR requires the implementation of “tagged” SHA256 hashes within the Merkle Tree, which is achievable.

Phase 3: Validation of Output Witness Fulfillment

While previous phases focus on validating preimages, hash computations, and value derivations, the Noir language enables more advanced functionality, specifically validating Bitcoin Script Interpreter execution. This permits demonstrating knowledge of a script witness that executes successfully, combined with a script from an existing transaction.

Phase 4: (Future Development) Comprehensive Chain Verification with Double Spending Detection

In the future, we may also prove that double spending is impossible without a Bitcoin node, but this could be unachievable soon (we need to dedicate more time to researching this direction).

Timeline and Deliverables

• Phase 1: (1-2 weeks)
• Phase 2: (2 weeks)
• Phase 3: (2-3 weeks)

What Noir has and what else needs to be implemented

• Our implementation of Ripemd160
• Merkle Tree with Sha256 hash (tagged hashes, double hashes, would be great to have something generic like on zk-kit)
• Secp256k1 key derivation, for Taproot (absent)
• Bitcoin data structures: blocks, scripts, addresses (absent)

Team

Distributed Lab
[email protected]

Start Date

26.05.25

[clarus]

I have a question: the link to https://github.com/distributed-lab/spv-contracts is not working. Is it a Solidity contract as you mention Ethereum?

[Alex-distributed-lab]

Oops, the repository was private. Already opened!

Yes, solidity contracts

[clarus]

Thanks!