Re: [bitcoin-dev] Improving SPV security with PoW fraud proofs

[Ethan Heilman <eth3rs@gmail.com>]

Good morning to you as well ZmnSCPxj,

My above email contains an error. The SPV client needs to only
download S+1, not S+1 and S+2.

I agree with you that a weakness of this approach is a miner can make
SPV clients do substantially more work. However:

1. Mining a block which will never be accepted is an expensive way to
make SPV clients download, validate and discard ~2-4 megabytes of
data. There are far less expensive ways of wasting the resources of
SPV clients. Its unclear why someone would want to do this instead of
just packeting full nodes or SPV servers like we saw with the recent
DDoS attacks against electrum servers.

2. SPV clients may not even learn about these splits because it
requires that someone relay the split to them. Honest full nodes
should not relay such splits. To their bitcoin's worth the attacker
must also connect to lots of SPV clients.

3. Having SPV clients slow down or become full nodes when a malicious
miner with significant mining power is attempting to disrupt the
network is probably a best case outcome. I would prefer this failure
mode to the current SPV behavior which is to just go with the
"longest" chain.

Thanks,
Ethan

On Thu, Apr 18, 2019 at 10:53 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ethan,
>
> Thank you for clarifying, I understand better now.
>
> It seems that minority miners can disrupt SPV clients such that SPV clients will download 2 blocks for every block the minority miner can find, not 1.
>
> This can be done by simply making multiple 1-block chainsplits, rather than a single persistent chainsplit, and alternating split-off and non-split-off.
>
> For instance, such a minority miner might split at S+1, forcing SPV clients to download S+1 and S+2.
> Then the minority miner splits at S+3, forcing SPV clients to download S+3 and S+4.
> With a mere 33% hashrate, this can force SPV clients to download every block, i.e. become a fullnode anyway.
>
> Since there exist pools with >33% hashrate, the above attack is possible so the only solution is to become a fullnode anyway.
>
> Regards,
> ZmnSCPxj
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On Friday, April 19, 2019 9:13 AM, Ethan Heilman <eth3rs@gmail.com> wrote:
>
> > Hi ZmnSCPxj,
> >
> > Let's see if I understand what you are saying. In your scenario chain
> > A consists of honest miners (10% of the hash rate) and chain B (90%
> > of the hash rate) consists of dishonest miners who are inflating the
> > coin supply.
> >
> > Chain A: S, S+1
> > Chain B: S, S+1 (invalid), S+2, S+3, S+4, S+5, S+6, S+7, S+8, S+9
> >
> > Chain B S+1 has a invalid coinbase
> >
> > > At around height S+9, the minority miners generate an alternate block at height S+1. So SPV nodes download S+9 and S+8 on the longer chain, and see nothing wrong with those blocks.
> >
> > What I am suggesting is that when the minority miners generate an
> > alternate block at S+1 (chain A) the SPV node would download blocks
> > S+1 and S+2 from chain B (the dishonest chain). Since S+1 has the
> > invalid coinbase the SPV node would learn that chain B is invalid and
> > abandon it.
> >
> > Bitcoin is in big trouble if a malicious party controls 90% of the
> > mining power. The malicious miners can spend +11% of their mining
> > power ensuring that the honest chain never reaches consensus by
> > continuously forking it. The malicious miners can then extend their
> > favored chain using the other 79% of the mining power. This would
> > produce a scenario in which users are forced to choose between a
> > stable chain that violates a consensus rule and an unstable honest
> > chain that is completely unusable and which never pays out mining
> > rewards. I agree that SPV nodes and many wallets would make this even
> > worse especially in their current condition where they just trust the
> > hash rate/wallet provider and there are no fraud proofs.
> >
> > On Thu, Apr 18, 2019 at 8:25 PM ZmnSCPxj ZmnSCPxj@protonmail.com wrote:
> >
> > > Good morning Ethan,
> > > Sent with ProtonMail Secure Email.
> > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > > On Friday, April 19, 2019 4:12 AM, Ethan Heilman eth3rs@gmail.com wrote:
> > >
> > > > I'm probably repeating a point which has been said before.
> > > >
> > > > > I suppose a minority miner that wants to disrupt the network could simply create a valid block at block N+1 and deliberately ignore every other valid block at N+1, N+2, N+3 etc. that it did not create itself.
> > > >
> > > > If this minority miner has > 10% of network hashrate, then the rule of
> > > > thumb above would, on average, give it the ability to disrupt the
> > > > SPV-using network.
> > > > Proposed rule:
> > > > Whenever a chainsplit occurs SPV clients should download and validate
> > > > the "longest chain" up to more than one block greater than the height
> > > > of the losing chain.
> > > > Lets say a block split causes chain A and chain B: Chain A is N blocks
> > > > long, chain B is M blocks long, and N < M. Then the SPV client should
> > > > download all the block data of N+1 blocks from Chain B to verify
> > > > availability of chain B. Once the SPV client has verified that chain B
> > > > is available they can use fraud proofs determine if chain B is valid.
> > >
> > > Let us then revert to the original scenario.
> > > Suppose a supermajority (90%) of miners decide to increase inflation of the currency.
> > > They do this by imposing the rule:
> > >
> > > 1.  For 1 block, the coinbase is 21,000,000 times the pre-fork coinbase value.
> > > 2.  For 9 blocks, the coinbase is the pre-fork value.
> > > 3.  Repeat this pattern every 10 blocks.
> > >
> > > The above is a hardfork.
> > > However, as they believe that SPV nodes dominate the economy, this mining supermajority believes it can take over the network hashpower and impose its will on the network.
> > > At height S+1, they begin the above rule.
> > > This implies that at heights S+1, S+11, S+21, s+31... the coinbase violates the pre-hardfork rules.
> > > At around height S+9, the minority miners generate an alternate block at height S+1.
> > > So SPV nodes download S+9 and S+8 on the longer chain, and see nothing wrong with those blocks.
> > > At around height S+18, the minority miners generate an alternate block at height S+2.
> > > So SPV nodes download S+18, S+17, S+16 and again see nothing wrong with those blocsk.
> > > This can go on for a good amount of time.
> > > With a "rare enough" inflation event, miners may even be able to spend some coinbases on SPV nodes that SPV nodes become unwilling to revert to the minority pre-hardfork chain, economically locking in the post-hardfork inflation.
> > > Again: every rule is an opportunity to loophole.
> > > Regards,
> > > ZmnSCPxj
> > >
> > > > An attacker could use this to force SPV clients to download 1 block
> > > > per block the attacker mines. This is strictly weaker security than
> > > > provided by a full-node because chain B will only be validated if the
> > > > client knows chain A exists. If the SPV client's view of the
> > > > blockchain is eclipsed then the client will never learn that chain A
> > > > exists and thus never validate chain B's availability nor will the
> > > > client be able to learn fraud proofs about chain B. A full node in
> > > > this circumstance would notice that the chain B is invalid and reject
> > > > it because a full node would not depend on fraud proofs. That being
> > > > said this rule would provide strictly more security than current SPV
> > > > clients.
> > > > On Thu, Apr 18, 2019 at 3:08 PM ZmnSCPxj via bitcoin-dev
> > > > bitcoin-dev@lists.linuxfoundation.org wrote:
> > > >
> > > > > Good morning Ruben,
> > > > > Sent with ProtonMail Secure Email.
> > > > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > > > > On Thursday, April 18, 2019 9:44 PM, Ruben Somsen via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:
> > > > >
> > > > > > Simplified-Payment-Verification (SPV) is secure under the assumption
> > > > > > that the chain with the most Proof-of-Work (PoW) is valid. As many
> > > > > > have pointed out before, and attacks like Segwit2x have shown, this is
> > > > > > not a safe assumption. What I propose below improves this assumption
> > > > > > -- invalid blocks will be rejected as long as there are enough honest
> > > > > > miners to create a block within a reasonable time frame. This still
> > > > > > doesn’t fully inoculate SPV clients against dishonest miners, but is a
> > > > > > clear improvement over regular SPV (and compatible with the privacy
> > > > > > improvements of BIP157[0]).
> > > > > > The idea is that a fork is an indication of potential misbehavior --
> > > > > > its block header can serve as a PoW fraud proof. Conversely, the lack
> > > > > > of a fork is an indication that a block is valid. If a fork is created
> > > > > > from a block at height N, this means a subset of miners may disagree
> > > > > > on the validity of block N+1. If SPV clients download and verify this
> > > > > > block, they can judge for themselves whether or not the chain should
> > > > > > be rejected. Of course it could simply be a natural fork, in which
> > > > > > case we continue following the chain with the most PoW.
> > > > >
> > > > > I presume you mean a chain split?
> > > > >
> > > > > > The way Bitcoin currently works, it is impossible to verify the
> > > > > > validity of block N+1 without knowing the UTXO set at block N, even if
> > > > > > you are willing to assume that block N (and everything before it) is
> > > > > > valid. This would change with the introduction of UTXO set
> > > > > > commitments, allowing block N+1 to be validated by verifying whether
> > > > > > its inputs are present in the UTXO set that was committed to in block
> > > > > > N. An open question is whether a similar result can be achieved
> > > > > > without a soft fork that commits to the UTXO set[0][1].
> > > > > > If an invalid block is created and only 10% of the miners are honest,
> > > > > > on average it would take 100 minutes for a valid block to appear.
> > > > > > During this time, the SPV client will be following the invalid chain
> > > > > > and see roughly 9 confirmations before the chain gets rejected. It may
> > > > > > therefore be prudent to wait for a number of confirmations that
> > > > > > corresponds to the time it may take for the conservative percentage of
> > > > > > miners that you think may behave honestly to create a block (including
> > > > > > variance).
> > > > >
> > > > > I suppose a minority miner that wants to disrupt the network could simply create a valid block at block N+1 and deliberately ignore every other valid block at N+1, N+2, N+3 etc. that it did not create itself.
> > > > > If this minority miner has > 10% of network hashrate, then the rule of thumb above would, on average, give it the ability to disrupt the SPV-using network.
> > > > >
> > > > > > 10% of network hashrate to disrupt the SPV-using nodes would be a rather low bar to disruption.
> > > > > > Consider that SPV-using nodes would be disrupted, without this rule, only by >50% network hashrate.
> > > > >
> > > > > It is helpful to consider that every rule you impose is potentially a loophole by which a new attack is possible.
> > > > > Regards,
> > > > > ZmnSCPxj
> > > > > bitcoin-dev mailing list
> > > > > bitcoin-dev@lists.linuxfoundation.org
> > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>