Date: Mon, 16 Sep 2019 06:48:21 -1000
From: "David A. Harding" <dave@dtrt.org>
To: Ruben Somsen <rsomsen@gmail.com>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20190916164821.yi6i6ymljpg4izgk@ganymede>
References: <CAPv7TjaE1wF-25R=LaOES33A78ovDAp9-waiC7n5YLJnMmNs9A@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CAPv7TjaE1wF-25R=LaOES33A78ovDAp9-waiC7n5YLJnMmNs9A@mail.gmail.com>
User-Agent: NeoMutt/20180716
Subject: Re: [bitcoin-dev] PoW fraud proofs without a soft fork
Precedence: list

On Sun, Sep 08, 2019 at 05:39:28AM +0200, Ruben Somsen via bitcoin-dev wrote:
> 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. 

This is a nifty idea.

> [...] you’d need to download:
>
> [...]
>
> 3. the utreexo merkle proofs which prove that all inputs of N+1 are
> part of the UTXO set (~1MB)

I think "~1 MB" is probably a reasonable estimate for the average case
but not for the worst case.  To allow verification of the spends in
block N+1, each UTXO entry must contain its entire scriptPubKey.  I
believe the current consensus rules allow scriptPubKeys to be up to
10,000 bytes in size.  A specially-constructed block can contain a bit
more than 20,000 inputs, making the worst case size of just the UTXO
entries that needs to be communicated over 200 MB.

> 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

I think this also expands to a worst-case of over 200 MB.  A lying peer
will only be able to get you on one of these checks, so it's 200 MB per
lying peer.  For an honest peer communicating valid blocks, the worst
case is that they'll need to communicate both of these state
transactions, so over 400 MB.  That could be a bandwidth-wasting DoS
attack on honest listening nodes if there were a large number of SPV
clients using this type of fraud proofs.

Additionally, each node capable of providing fraud proofs will need to
persistently store the state transition proof for each new block.  I
assume this is equal to the block undo data currently stored by archival
full nodes plus the utreexo partial merkle branches.

This data would probably not be stored by pruned nodes, at least not
beyond their prune depth, even for pruned nodes that use utreexo.  That
would mean this system will only work with archival full nodes with an
extra "index" containing the utreexo partial merkle branches, or it will
require querying utreexo bridge nodes.

Given that both of those would require significant additional system
resources beyond the minimum required to operate a full node, such nodes
might be rare and so make it relatively easy to eclipse attack an SPV
client depending on these proofs.

Finally, this system depends on SPV clients implementing all the same
consensus checks that full nodes can currently perform.  Given that most
SPV clients I'm aware of today don't even perform the full range of
checks it's possible to run on block headers, I have serious doubts that
many (or any) SPV clients will actually implement full verification.  On
top of that, each client must implement those checks perfectly or they
could be tricked into a chainsplit the same as a full node that follows
different rules than the economic consensus.

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

One thing I didn't like in your original proposal---which I appologize
for keeping to myself---is that the SPV client will accept confirmations
on the bad chain until a fork is produced.  Even a miner with a minority
of the hash rate will sometimes be able to produce a 6-block chain before
the remaining miners produce a single block.  In that case, SPV clients
with a single dishonest peer in collusion with the miner will accept any
transctions in the first block of that chain as having six
confirmations.  That's the same as it is today, but today SPV users
don't think fraud proofs help keep them secure.

I think that, if we wanted to widely deploy fraud proofs depending on
forks as a signal, we'd have to also retrain SPV users to wait for much
higher confirmation counts before accepting transactions as reasonably
secure.

-Dave