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

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

[Ruben Somsen]

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.

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).

If users do not wait and happen to accept payments from an invalid
chain during this time, these payments could get reverted. This is a
weakness, but still seems preferably to continually following an
invalid chain. As long as a reasonable number of miners remains
honest, a dishonest majority can only temporarily control the network,
and their blocks (and all coins gained from it) will eventually be
rejected.

-- Ruben Somsen


[0] Olaoluwa Osuntokun, BIP 157: Client Side Block Filtering,
https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki

[1] Peter Todd, TXO commitments do not need a soft-fork to be useful,
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013591.html

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

[ZmnSCPxj]

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

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

[Ethan Heilman]

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.

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

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

[ZmnSCPxj]

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

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

[Ethan Heilman]

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
>
>

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

[ZmnSCPxj]

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

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

[Ethan Heilman]

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
>
>

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

[ZmnSCPxj]

Good morning Ethan,

> 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.


I understand.
It seems a reasonable point to do so.

As I understand it, this requires that UTXO commitments be mandatory.
In particular, if UTXO commitments were not mandatory, it would be trivial to force chainsplits at heights where a UTXO commitment was not made, and force an SPV node to download more blocks backwards until a block with a UTXO commitment is found.

More difficult is: how can an SPV node acquire the UTXO set at a particular block?
Fullnodes automatically update their UTXO set at each block they accept as tip.
Reversing the blocks to update the UTXO set at a particular past time would require a good amount of CPU and memory.
Thus any service that can provide the actual UTXO set at each block would potentially be attackable by simply requesting enough past blocks.


Regards,
ZmnSCPxj

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

[Ruben Somsen]

Hi ZmnSCPxj and Ethan,

I apologize if my initial explanation was confusing, but it looks like
you figured it out. For every fork, SPV clients only have to download
one block. If there is a fork after block N, this means there are two
blocks at N+1. You only download and verify N+1 from the longer chain.

>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

Absolutely, hence the name "PoW fraud proof". It gets naturally
created by honest miners and is prohibitively expensive to forge.

>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.

You could perform a fully valid repeated 1-block reorg from the top of
the chain. So at least theoretically you could get an honest network
to relay every split.

>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.

That is an excellent point.

>As I understand it, this requires that UTXO commitments be mandatory.

Perhaps UTXO sets can be made useful without committing them. I have
some very loose thoughts on the subject, I consider it an open
question.

> More difficult is: how can an SPV node acquire the UTXO set at a particular block?

I think you are asking fair questions about how the UTXO set
commitments would work in practice, and how viable that makes it. I'm
not sure. The most comprehensive work I have seen on this topic has
been the utreexo proposal by Tadge Dryja:
https://www.youtube.com/watch?v=edRun-6ubCc

Actually, now that I think about it... As an alternative to UTXO set
commitments, the old fraud proofs idea for segwit can be applied here.

We get miners to commit to the location of the UTXOs that are being
spent (e.g. transaction 5 in block 12). This allows full nodes to
succinctly prove invalidity to SPV clients in the following ways:

- a committed location does not contain the stated UTXO
- the UTXO has already been spent in a prior block

If no fraud proofs are given, then the inputs can be assumed to be valid.

As you may recall, these kinds of fraud proofs were abandoned mainly
because the data unavailability claim could only be verified by
downloading the data, resulting in a DoS vector where all blocks had
to be downloaded. This problem does not seem to apply here, because we
are only interested in blocks which have forks, so it's more doable to
download them.

-- Ruben Somsen

On Fri, Apr 19, 2019 at 6:48 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ethan,
>
> > 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.
>
>
> I understand.
> It seems a reasonable point to do so.
>
> As I understand it, this requires that UTXO commitments be mandatory.
> In particular, if UTXO commitments were not mandatory, it would be trivial to force chainsplits at heights where a UTXO commitment was not made, and force an SPV node to download more blocks backwards until a block with a UTXO commitment is found.
>
> More difficult is: how can an SPV node acquire the UTXO set at a particular block?
> Fullnodes automatically update their UTXO set at each block they accept as tip.
> Reversing the blocks to update the UTXO set at a particular past time would require a good amount of CPU and memory.
> Thus any service that can provide the actual UTXO set at each block would potentially be attackable by simply requesting enough past blocks.
>
>
> Regards,
> ZmnSCPxj

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

[ZmnSCPxj]

Good morning,


> > As I understand it, this requires that UTXO commitments be mandatory.
>
> Perhaps UTXO sets can be made useful without committing them. I have
> some very loose thoughts on the subject, I consider it an open
> question.

There is no safe way to use UTXO sets without identifying who is telling you those sets are valid, or making it expensive to lie.
The first option requires trust and is weaker than SPV, the second requires committing to a proof-of-work (and probably best to fold it into the Bitcoin blockchain if so).

You would get the UTXO commitment from the previous block (if the UTXO commitment is in the coinbase, then all you need is the Merkle proof of the coinbase).


>
> > More difficult is: how can an SPV node acquire the UTXO set at a particular block?
>
> I think you are asking fair questions about how the UTXO set
> commitments would work in practice, and how viable that makes it. I'm
> not sure. The most comprehensive work I have seen on this topic has
> been the utreexo proposal by Tadge Dryja:
> https://www.youtube.com/watch?v=edRun-6ubCc
>
> Actually, now that I think about it... As an alternative to UTXO set
> commitments, the old fraud proofs idea for segwit can be applied here.
>
> We get miners to commit to the location of the UTXOs that are being
> spent (e.g. transaction 5 in block 12). This allows full nodes to
> succinctly prove invalidity to SPV clients in the following ways:
>
> -   a committed location does not contain the stated UTXO
> -   the UTXO has already been spent in a prior block
>
>     If no fraud proofs are given, then the inputs can be assumed to be valid.
>
>     As you may recall, these kinds of fraud proofs were abandoned mainly
>     because the data unavailability claim could only be verified by
>     downloading the data, resulting in a DoS vector where all blocks had
>     to be downloaded. This problem does not seem to apply here, because we
>     are only interested in blocks which have forks, so it's more doable to
>     download them.

This makes no sense.
In order to validate block N, you need to know that every UTXO spent by a transaction in block N is valid.
The UTXO you want to validate is located in some other block, not on the single block you are verifying.

Thus the non-existent fraud proof can only be validated by loading the block of the UTXO purported to be spent, and every block between that and the current block you are verifying, i.e. fullnode.
Either that or you trust that every peer you have is not omitting the proof.

Regards,
ZmnSCPxj

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

[Ruben Somsen]

Hi ZmnSCPxj,

>There is no safe way to use UTXO sets without identifying who is telling you those sets are valid, or making it expensive to lie
>The first option requires trust and is weaker than SPV, the second requires committing to a proof-of-work

Olaoluwa Osuntokun's BIP157 manages to function without a commitment:
"If the client receives conflicting filter headers from different
peers for any block and filter type, it SHOULD interrogate them to
determine which is faulty."

I am wondering if the same logic can be applied to UTXO sets or the
fraud proofs I just described.

>This makes no sense
>or you trust that every peer you have is not omitting the proof.

It's the latter, you trust every peer you have is not omitting the
proof. It requires one honest peer. The reason this is acceptable is
because you're already making that assumption. If none of your peers
are honest, you have no guarantee of hearing about the chain with the
most PoW.

Again, this is not a new observation. I am just recalling the fraud
proof debate from when it was being considered for segwit (though of
course it's possible I got some details wrong).

-- Ruben Somsen

On Sat, Apr 20, 2019 at 3:59 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning,
>
>
> > > As I understand it, this requires that UTXO commitments be mandatory.
> >
> > Perhaps UTXO sets can be made useful without committing them. I have
> > some very loose thoughts on the subject, I consider it an open
> > question.
>
> There is no safe way to use UTXO sets without identifying who is telling you those sets are valid, or making it expensive to lie.
> The first option requires trust and is weaker than SPV, the second requires committing to a proof-of-work (and probably best to fold it into the Bitcoin blockchain if so).
>
> You would get the UTXO commitment from the previous block (if the UTXO commitment is in the coinbase, then all you need is the Merkle proof of the coinbase).
>
>
> >
> > > More difficult is: how can an SPV node acquire the UTXO set at a particular block?
> >
> > I think you are asking fair questions about how the UTXO set
> > commitments would work in practice, and how viable that makes it. I'm
> > not sure. The most comprehensive work I have seen on this topic has
> > been the utreexo proposal by Tadge Dryja:
> > https://www.youtube.com/watch?v=edRun-6ubCc
> >
> > Actually, now that I think about it... As an alternative to UTXO set
> > commitments, the old fraud proofs idea for segwit can be applied here.
> >
> > We get miners to commit to the location of the UTXOs that are being
> > spent (e.g. transaction 5 in block 12). This allows full nodes to
> > succinctly prove invalidity to SPV clients in the following ways:
> >
> > -   a committed location does not contain the stated UTXO
> > -   the UTXO has already been spent in a prior block
> >
> >     If no fraud proofs are given, then the inputs can be assumed to be valid.
> >
> >     As you may recall, these kinds of fraud proofs were abandoned mainly
> >     because the data unavailability claim could only be verified by
> >     downloading the data, resulting in a DoS vector where all blocks had
> >     to be downloaded. This problem does not seem to apply here, because we
> >     are only interested in blocks which have forks, so it's more doable to
> >     download them.
>
> This makes no sense.
> In order to validate block N, you need to know that every UTXO spent by a transaction in block N is valid.
> The UTXO you want to validate is located in some other block, not on the single block you are verifying.
>
> Thus the non-existent fraud proof can only be validated by loading the block of the UTXO purported to be spent, and every block between that and the current block you are verifying, i.e. fullnode.
> Either that or you trust that every peer you have is not omitting the proof.
>
> Regards,
> ZmnSCPxj

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

[ZmnSCPxj]

Good morning Ruben,

> Hi ZmnSCPxj,
>
> > There is no safe way to use UTXO sets without identifying who is telling you those sets are valid, or making it expensive to lie
> > The first option requires trust and is weaker than SPV, the second requires committing to a proof-of-work
>
> Olaoluwa Osuntokun's BIP157 manages to function without a commitment:
> "If the client receives conflicting filter headers from different
> peers for any block and filter type, it SHOULD interrogate them to
> determine which is faulty."
>
> I am wondering if the same logic can be applied to UTXO sets or the
> fraud proofs I just described.

UTXO sets can only be validated by actually running the entire blockchain, i.e. fullnoding.

What BIP157 does is summarize data that is within a block, thus validating them can be done simply by downloading the block in question.

UTXO sets summarize data in the entire blockchain, hence proper validation requires downloading the entire blockchain.
Thus it cannot be a comparison point.


> > This makes no sense
> > or you trust that every peer you have is not omitting the proof.
>
> It's the latter, you trust every peer you have is not omitting the
> proof. It requires one honest peer. The reason this is acceptable is
> because you're already making that assumption. If none of your peers
> are honest, you have no guarantee of hearing about the chain with the
> most PoW.

But peers can be set up to allow you to hear of all chains while denying you proof of the invalidity of some UTXO.
This is precisely the "data unavailability claim" that shot down the previous fraud proofs (i.e. absence of proof is not proof of absence, and proof of UTXO validity was defined by proof of absence of any intervening spend of the UTXO).

Perhaps in combination with BIP157/158 it may be possible, if the filters contain UTXO spends and a BIP158 filter was committed to on-chain.
Then a proof of absence could be done by revealing all the BIP158 filters from the UTXO creation to the block being validated, as well as the blocks whose BIP158 filters matched the UTXO and revealing that no, they actually do not spend the UTXO.

--

Tangentially, we cannot just magically commit to anything on the blockchain.
Header blocks commit to block data and commit to some other header block.
All those header blocks and the block data need to be stored and transmitted over the network somehow, even though they are "only" being committed to.
Thus, if you are adding new information to be committed, that may increase the resource usage of fullnodes.

So if UTXO set commitments, or utreexo commitments, or BIP158 filter digests, etc. are committed to in the coinbase, they have to be stored somehow in fullnodes the entire UUTXO set, or the actual utreexo structure, or the actual BIP158 filter, etc. at each block.
Otherwise it would be pointless to store those commitments since it would not be possible to somehow acquire the data being committed to after-the-fact.

This is probably still better than BIP37 but we should still be aware the additional load on fullnodes.

Regards,
ZmnSCPxj

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

[Ruben Somsen]

Hi ZmnSCPxj,


Allow me to reply to your post in mixed order (fraud proofs first):


>But peers can be set up to allow you to hear of all chains while denying you proof of the invalidity of some UTXO.

I don't believe this is fundamentally different. In either scenario
you end up on the wrong chain if all your peers are lying to you. One
happens by omission of a fraud proof, while the other happens by
omission of a valid longest chain.


>This is precisely the "data unavailability claim" that shot down the previous fraud proofs

The "data unavailability" issue I was referring to, and which I
believe is the reason why fraud proofs were abandoned, is the
following:

- Alice downloads a block with her full node, but the block is
incomplete (e.g. a transaction is missing).
- Alice reports this to Bob's SPV fraud proof client, who verifies
this by requesting the transaction from the network.
- If Bob can't download it, he rejects the block.
- If Bob can download it, either Alice was malicious, or a miner was
temporarily withholding the data.
- Since Bob can't be certain Alice was being malicious, Bob can't ban
her, which results in a DoS vector where SPV fraud proof clients can
be forced to download all blocks.

We circumvent the data unavailability problem here completely, since
we are only questioning the validity of blocks which are involved in a
fork (expensive and/or rare), and we are simply always downloading
them in full.

If my arguments above hold up, we can use fraud proof commitments as
described in segwit BIP141 [0] instead of UTXO set commitments, which
seems like the more elegant way to achieve the desired outcome.


>Perhaps in combination with BIP157/158 it may be possible, if the filters contain UTXO spends and a BIP158 filter was committed to on-chain. Then a proof of absence could be done by revealing all the BIP158 filters from the UTXO creation to the block being validated, as well as the blocks whose BIP158 filters matched the UTXO and revealing that no, they actually do not spend the UTXO.

Yes, I mentioned something similar to Laolu, but it does seem
computationally expensive to run every input in a block through the
filter of every past block. The fact that BIP157/158 can function
without commitments is also why I suspected we may not necessarily
need UTXO set commitments.


>UTXO sets can only be validated by actually running the entire blockchain, i.e. fullnoding.

It seems to me you can validate uncommitted UTXO sets by comparing
them. Download and compare UTXO set hashes from multiple peers. If
they disagree on a certain block, download that block and the relevant
merkle path(s) from the previous block's UTXO set, and then verify who
is right. Ban the peer who lied. Note that unlike fraud proofs, it is
not possible to lie by omission, but it does assume one of your peers
is honest. Of course this does nothing to dispute your earlier point
that this may not be all that efficient (e.g. full nodes keeping
merkle paths of all prior states).


>What BIP157 does is summarize data that is within a block, thus validating them can be done simply by downloading the block in question.
>UTXO sets summarize data in the entire blockchain, hence proper validation requires downloading the entire blockchain.
Thus it cannot be a comparison point.

It's still possible to lie by omission. Let's say a miner spends some
coins in block N, and spends the exact same coins again in block N+1,
making block N+1 invalid. If the filter for block N is maliciously
constructed, you won't notice the spend in block N, causing you to
think block N+1 is valid. In short, you're still relying on one of
your peers to give you a correct filter. If all your peers lie, you
can always be deceived.


>Tangentially, we cannot just magically commit to anything on the blockchain. [...] if you are adding new information to be committed, that may increase the resource usage of fullnodes. [...] This is probably still better than BIP37 but we should still be aware the additional load on fullnodes.

I agree with all this.


To summarize, this is my current understanding of our options for
enabling light clients to verify a single block in isolation:
1. UTXO set commitments (complex, more resource usage to full nodes)
2. BIP157/158 commitments (expensive for clients to check all filters
to get exclusion proofs)
3. BIP141 fraud proof commitments (assumes fraud proofs will be passed
on to the SPV client)

The debate is still open on whether the options above can be done
without actually committing them into blocks via a soft fork. My
current hunch is "yes" for 1 and 2, and "no" for 3, which would be
unfortunate, because 3 currently seems to me like the more elegant
solution.


-- Ruben Somsen


[0] https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#Compact_fraud_proof_for_SPV_nodes


>UTXO sets can only be validated by actually running the entire blockchain, i.e. fullnoding.
>What BIP157 does is summarize data that is within a block, thus validating them can be done simply by downloading the block in question.

UTXO sets summarize data in the entire blockchain, hence proper
validation requires downloading the entire blockchain.
Thus it cannot be a comparison point.


> > This makes no sense
> > or you trust that every peer you have is not omitting the proof.
>
> It's the latter, you trust every peer you have is not omitting the
> proof. It requires one honest peer. The reason this is acceptable is
> because you're already making that assumption. If none of your peers
> are honest, you have no guarantee of hearing about the chain with the
> most PoW.

But peers can be set up to allow you to hear of all chains while
denying you proof of the invalidity of some UTXO.
This is precisely the "data unavailability claim" that shot down the
previous fraud proofs (i.e. absence of proof is not proof of absence,
and proof of UTXO validity was defined by proof of absence of any
intervening spend of the UTXO).

Perhaps in combination with BIP157/158 it may be possible, if the
filters contain UTXO spends and a BIP158 filter was committed to
on-chain.
Then a proof of absence could be done by revealing all the BIP158
filters from the UTXO creation to the block being validated, as well
as the blocks whose BIP158 filters matched the UTXO and revealing that
no, they actually do not spend the UTXO.

--

Tangentially, we cannot just magically commit to anything on the blockchain.
Header blocks commit to block data and commit to some other header block.
All those header blocks and the block data need to be stored and
transmitted over the network somehow, even though they are "only"
being committed to.
Thus, if you are adding new information to be committed, that may
increase the resource usage of fullnodes.

So if UTXO set commitments, or utreexo commitments, or BIP158 filter
digests, etc. are committed to in the coinbase, they have to be stored
somehow in fullnodes the entire UUTXO set, or the actual utreexo
structure, or the actual BIP158 filter, etc. at each block.
Otherwise it would be pointless to store those commitments since it
would not be possible to somehow acquire the data being committed to
after-the-fact.

This is probably still better than BIP37 but we should still be aware
the additional load on fullnodes.

Regards,
ZmnSCPxj

On Sat, Apr 20, 2019 at 6:45 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ruben,
>
> > Hi ZmnSCPxj,
> >
> > > There is no safe way to use UTXO sets without identifying who is telling you those sets are valid, or making it expensive to lie
> > > The first option requires trust and is weaker than SPV, the second requires committing to a proof-of-work
> >
> > Olaoluwa Osuntokun's BIP157 manages to function without a commitment:
> > "If the client receives conflicting filter headers from different
> > peers for any block and filter type, it SHOULD interrogate them to
> > determine which is faulty."
> >
> > I am wondering if the same logic can be applied to UTXO sets or the
> > fraud proofs I just described.
>
> UTXO sets can only be validated by actually running the entire blockchain, i.e. fullnoding.
>
> What BIP157 does is summarize data that is within a block, thus validating them can be done simply by downloading the block in question.
>
> UTXO sets summarize data in the entire blockchain, hence proper validation requires downloading the entire blockchain.
> Thus it cannot be a comparison point.
>
>
> > > This makes no sense
> > > or you trust that every peer you have is not omitting the proof.
> >
> > It's the latter, you trust every peer you have is not omitting the
> > proof. It requires one honest peer. The reason this is acceptable is
> > because you're already making that assumption. If none of your peers
> > are honest, you have no guarantee of hearing about the chain with the
> > most PoW.
>
> But peers can be set up to allow you to hear of all chains while denying you proof of the invalidity of some UTXO.
> This is precisely the "data unavailability claim" that shot down the previous fraud proofs (i.e. absence of proof is not proof of absence, and proof of UTXO validity was defined by proof of absence of any intervening spend of the UTXO).
>
> Perhaps in combination with BIP157/158 it may be possible, if the filters contain UTXO spends and a BIP158 filter was committed to on-chain.
> Then a proof of absence could be done by revealing all the BIP158 filters from the UTXO creation to the block being validated, as well as the blocks whose BIP158 filters matched the UTXO and revealing that no, they actually do not spend the UTXO.
>
> --
>
> Tangentially, we cannot just magically commit to anything on the blockchain.
> Header blocks commit to block data and commit to some other header block.
> All those header blocks and the block data need to be stored and transmitted over the network somehow, even though they are "only" being committed to.
> Thus, if you are adding new information to be committed, that may increase the resource usage of fullnodes.
>
> So if UTXO set commitments, or utreexo commitments, or BIP158 filter digests, etc. are committed to in the coinbase, they have to be stored somehow in fullnodes the entire UUTXO set, or the actual utreexo structure, or the actual BIP158 filter, etc. at each block.
> Otherwise it would be pointless to store those commitments since it would not be possible to somehow acquire the data being committed to after-the-fact.
>
> This is probably still better than BIP37 but we should still be aware the additional load on fullnodes.
>
> Regards,
> ZmnSCPxj