How to Validate Bitcoin Payments in Ethereum (for only 700k gas!)

On November 15 at 10 am PT, Summa will run the world’s first cross-chain auction. We’ll auction 10 non-fungible tokens (NFTs) on Ethereum for Bitcoin in a completely trustless process featuring direct interaction between Solidity smart contracts and Bitcoin payments. These 10 tokens are unique badges of participation in the first cross-chain auction. For a higher-level introduction to our products and instructions on how to participate in our auction, check out this post.

Our auctions and smart contracts verify proofs of Bitcoin payment on-chain to power cross-chain communication. This means fast, efficient cross-chain interoperability without oracles, trusted third parties, or centralized exchanges. We tried hard to streamline the auction app’s user experience such that many technical aspects are difficult to notice. This post gives you a quick peek behind the curtain into one of the underlying tools: Simplified Payment Verification (“SPV”) proofs. SPV Proofs are compact proofs of payment. They can be used to prove to a client that isn’t running a full node that an on-chain payment actually happened.

SPV Verification

Summa’s SPV proofs allow any Ethereum-style smart contract to verify Bitcoin payments quickly and securely. In a nutshell, we communicate to a smart contract that someone paid Bitcoin, along with any extra information the smart contract needs. Think of it as registering Solidity callbacks for Bitcoin transactions. It’s an incredibly powerful tool for cross-chain programming.

Contrary to popular belief, Ethereum contracts can verify Bitcoin transactions directly, by enforcing some standards and checking everyone’s work. To do this, the contract needs to be able to dissect Bitcoin transactions and blocks. We wrote an entire Solidity library for doing just that, so we can inspect a Bitcoin payment without checking the entire chain.

First, we verify the Bitcoin transaction inside a Solidity smart contract. This part is a quick run-through of all inputs and outputs, to ensure the caller isn’t trying to sneak through fake outputs. Second, we verify that the Bitcoin transaction is included in a block by checking a Merkle proof of inclusion. Third, we verify a chain of blockheaders. We need to check that each block references the previous one, and then calculate the total Proof of Work spent to make that chain. We can’t be 100% sure that the headers we see came from Bitcoin’s mainnet, but we can have a very high degree of confidence.

Transaction Validation

Bitcoin’s transactions are simple. They have money coming in, money going out, authorization information, and not much else. Each transaction is a list of inputs, a list of outputs, and a list of signatures and other spend authorization info called “witnesses”. The witness proves that the owner of the Bitcoin input authorized the transaction. If the inputs are worth more than the outputs, and the witnesses check out, then the transaction is valid.

We built bitcoin-spv to support native SegWit. While it’s possible to work with legacy Bitcoin transactions, the process becomes very complicated. Legacy transactions are messy, malleable by third-parties, and enable obscure attacks on SPV verifiers. SegWit standardizes and simplifies the transaction format, meaning we only need to parse about 200–500 bytes (depending on how many inputs and outputs our tx has), about a 40% savings compared to parsing legacy transactions.

Since we know the transaction format we can extract the information we want. We can grab the value in satoshi of the first output, find the Ethereum account associated with the pubkey in the second witness, or pull data from an OP_RETURN to use for contract data calls. Our BTCUtils library has a complete set of tools for extracting data from transactions.

Inclusion Validation

Bitcoin transactions, like Ethereum state, are included in a Merkle tree. Each Bitcoin block header contains the root of the Merkle tree for that block’s transactions. Given a header and a transaction, we can validate a merkle path from the root to the leaf that holds the transaction, which is called the Merkle-based inclusion proof. This means we only need the Bitcoin block header, transaction, and its inclusion proof to be stored in our smart contract, and nothing else.

Typically a full Bitcoin block has around 2,500 transactions, yielding a merkle tree of height 12 (12 = ceil(log_2(2500)). Since each hash is 32 bytes, and our merkle path from the root to the leaf is the height of the tree, the merkle path is 12 * 32 bytes = 384 bytes. We’ll have to do at most 24 sha256 operations since Bitcoin uses double-sha256 for almost everything. This is reasonable to do on-chain in Ethereum, so with the transaction, the header, and a few hundred bytes of proof info, we can demonstrate inclusion in the header.

Stateless SPV Validation

Connecting the tx to a header is critical. Headers are how we check work, and work is how we check security. Each header contains a number known as nBits. Bitcoin’s consensus algorithm sets the nBits field to communicate the amount of work a header needs. It encodes the work target, and by extension the block’s difficulty. As proof of work gets harder, targets go down and difficulty goes up.

Summa’s contracts use “stateless” SPV proofs. This means that instead of tracking Bitcoin’s state all the time like BTCRelay or NiPoPow-based constructions, we look at a specific slice of headers, say 6 or 7. The main Bitcoin chain builds header chains for honest participants for free, but dishonest participants must spend hashpower (which means spending money) to build fake proofs. By inspecting these headers, we can figure out how expensive it would be to build that slice. This means we set an adjustable economic security parameter. In other words, validation gives us $X of confidence in the proof, and we can require X be as high as we want.

Economic confidence comes from checking the headers’ work. Proof of Work is expensive. Right now Bitcoin issues $13MM dollars per day. To fake a proof, a Bitcoin miner would have to give up some of that reward, because they’d have to stop mining on the main chain to mine on the fake proof instead. If 10% of the hashrate decided to mine fake proofs instead of real Bitcoin, they’d lose over $1MM per day. In addition, if 10% of the hashrate wants to mine a fake proof, it takes 9x as long to generate a proof. This means that if the order is filled honestly, the main chain will outrace the fake header proof anyway. In that case, the fake proof is entirely worthless. As you can see, it’s very expensive to fake a proof, and you have no guarantee that it will be worth anything in the end.

The quality of a proof is determined by “accumulated difficulty,” which is to say, the sum of the difficulty of each header in a proof. To verify a stateless proof, we take a list of headers and verify a) that they contain the work they say they do, b) that each header links to the previous one, and c) that the accumulated difficulty of the proof is above our security parameter. Bitcoin headers are always exactly 80 bytes. For 6 headers, this means 540 bytes 10 sha256 operations (5 double-sha256 links in the header chain). Again, this is inexpensive and reasonable for on-chain verification.

Summary

In review, our smart contracts validate the tx, check that the tx is included in a block header’s transaction root, then validate that that header is buried under a certain amount of accumulated difficulty. The whole adventure takes just over 1KB of information, and costs around 700,000 gas. If the proof isn’t valid, our ValidateSPV library returns a failure code rather than reverting. This allows contract developers to decide whether to take actions when receiving an invalid proof.

SPV proofs are incredibly versatile tools. We’ve used it to build simple sale orders, first-price auctions, Dutch auctions, and a whole lot more. Soon it’ll match complex cross-chain contracts like options and forwards, enforce Bitcoin covenants, and build real cross-chain markets. Linking Ethereum’s state and expressive smart contracts to Bitcoin’s liquidity and reliability.

Participate in a cross-chain auction and stay up to date with our work at https://summa.one.