[bitcoin-dev] PoW fraud proofs without a soft fork

[Ruben Somsen]

After looking more deeply into Tadge Dryja’s utreexo work [0], it has
become clear to me that this opens up a way to implement PoW fraud
proofs [1] without a soft fork. With utreexo, we can efficiently
verify state transitions between blocks. Verifying a block from a
valid utreexo hash requires only about a megabyte worth of merkle
proofs.

PoW fraud proofs assume that block N is valid if no miner has tried to
fork it (read my original post for details [1]). We can extend that
assumption to the utreexo hash of block N, and use that to verify fork
block N+1, and reject it if the block is invalid, with just 2-3MB of
data.

For simplicity, I’ll first start by explaining a version with
commitments (which would require a soft fork).

When a fork (i.e. a PoW fraud proof) occurs at height N+1, indicating
that the block might be invalid, you’d need to download:

1. block N+1 from the most PoW chain (~1-2MB)
2. the utreexo hash commitment inside of block N (e.g. a merkle path
to the coinbase)
3. the utreexo merkle proofs which prove that all inputs of N+1 are
part of the UTXO set (~1MB)

Of course step 2 requires a soft fork, but we can also do a
non-committed version by relying on the assumption that at least one
of your peers is honest and then evaluate disagreements.

We simply replace step 2 above with the following:
2. [Download] the utreexo hash of block N from all your peers

If it turns out that one of your peers disagrees on what the correct
hash is, you find the last utreexo hash where that peer still agreed,
let’s say block M, and you simply execute the same three steps to find
out which peer is wrong: download block M+1, then get the merkle
proofs to verify whether the peer correctly transitioned their utreexo
hash from M to M+1.

One might intuitively feel that the lack of a commitment is unsafe,
but there seems to be no impact on security (only bandwidth). The only
way you can be fooled is if all peers lie to you (Sybil), causing you
to follow a malicious minority chain. But even full nodes (or the
committed version of PoW fraud proofs) can be fooled in this way if
they are denied access to the valid most PoW chain. If there are
additional security concerns I overlooked, I’d love to hear them.

In short, utreexo can enable PoW fraud proofs without a soft fork. At
the cost of downloading a couple of MB per stale block (and per
malicious peer), an SPV client gains the ability to (eventually)
reject the most PoW chain as long as one honest block gets mined,
thereby increasing its security beyond 51% honest miners.

Finally, while I think this goes without saying, I’d like to reiterate
that this is by no means a replacement for running a full node. You’re
depending on other full nodes to do full verification and assuming at
least some of the miners are honest. If everyone did this, Bitcoin
would not be secure.

-- Ruben Somsen


[0] Utreexo paper: https://eprint.iacr.org/2019/611.pdf

[1] Improving SPV security with PoW fraud proofs:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-April/016873.html