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

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

[Ruben Somsen]

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

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

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

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

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

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

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

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

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

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

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

-- Ruben Somsen


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

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

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

[ZmnSCPxj]

Good morning Ruben,


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


I think it would be better to more precisely say that:

1.  In event of a sybil attack, a fullnode will stall and think the blockchain has no more miners.
2.  In event of a sybil attack, an SPV, even using this style, will follow the false blockchain.

This has some differences when considering automated systems.

Onchain automated payment processing systems, which use a fullnode, will refuse to acknowledge any incoming payments.
This will lead to noisy complaints from clients of the automated payment processor, but this is a good thing since it warns the automated payment processor of the possibility of this attack occurring on them.
The use of a timeout wherein if the fullnode is unable to see a new block for, say, 6 hours, could be done, to warn higher-layer management systems to pay attention.
While it is sometimes the case that the real network will be unable to find a new block for hours at a time, this warning can be used to confirm if such an event is occurring, rather than a sybil attack targeting that fullnode.

On the other hand, such a payment processing system, which uses an SPV with PoW fraud proofs, will be able to at least see incoming payments, and continue to release product in exchange for payment.
Yet this is precisely a point of attack, where the automated payment processing system is sybilled and then false payments are given to the payment processor on the attack chain, which are double-spent on the global consensus chain.
And the automated system may very well not be able to notice this.

Regards,
ZmnSCPxj

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

[Dragi Bucukovski]

How much do I have in my account can you please tell me 

Sent from my iPhone

> On 9 Sep 2019, at 2:14 pm, ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> Good morning Ruben,
> 
> 
>>    One might intuitively feel that the lack of a commitment is unsafe,
>>    but there seems to be no impact on security (only bandwidth). The only
>>    way you can be fooled is if all peers lie to you (Sybil), causing you
>>    to follow a malicious minority chain. But even full nodes (or the
>>    committed version of PoW fraud proofs) can be fooled in this way if
>>    they are denied access to the valid most PoW chain. If there are
>>    additional security concerns I overlooked, I’d love to hear them.
> 
> 
> I think it would be better to more precisely say that:
> 
> 1.  In event of a sybil attack, a fullnode will stall and think the blockchain has no more miners.
> 2.  In event of a sybil attack, an SPV, even using this style, will follow the false blockchain.
> 
> This has some differences when considering automated systems.
> 
> Onchain automated payment processing systems, which use a fullnode, will refuse to acknowledge any incoming payments.
> This will lead to noisy complaints from clients of the automated payment processor, but this is a good thing since it warns the automated payment processor of the possibility of this attack occurring on them.
> The use of a timeout wherein if the fullnode is unable to see a new block for, say, 6 hours, could be done, to warn higher-layer management systems to pay attention.
> While it is sometimes the case that the real network will be unable to find a new block for hours at a time, this warning can be used to confirm if such an event is occurring, rather than a sybil attack targeting that fullnode.
> 
> On the other hand, such a payment processing system, which uses an SPV with PoW fraud proofs, will be able to at least see incoming payments, and continue to release product in exchange for payment.
> Yet this is precisely a point of attack, where the automated payment processing system is sybilled and then false payments are given to the payment processor on the attack chain, which are double-spent on the global consensus chain.
> And the automated system may very well not be able to notice this.
> 
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Ruben Somsen]

Hi ZmnSCPxj,

Thank you for your comments. You raise an important point that I should clarify.

>1.  In event of a sybil attack, a fullnode will stall and think the blockchain has no more miners.

You can still attack the full node by feeding it a minority PoW chain,
then it won't stall.

>2.  In event of a sybil attack, an SPV, even using this style, will follow the false blockchain.

Correct, but this false blockchain does need to have valid PoW.

So in both cases valid PoW is required to fool nodes. The one
difference is that for a full node, the blocks themselves also need to
be valid (except for the fact that they are in a minority chain), but
the end result is still that a victim can be successfully double spent
and lose money.

I hope this clarifies why I consider the security for these two
situations to be roughly equivalent. In either situation, victims can
be fooled into accepting invalid payments.

Cheers,
Ruben

On Mon, Sep 9, 2019 at 6:14 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ruben,
>
>
> >     One might intuitively feel that the lack of a commitment is unsafe,
> >     but there seems to be no impact on security (only bandwidth). The only
> >     way you can be fooled is if all peers lie to you (Sybil), causing you
> >     to follow a malicious minority chain. But even full nodes (or the
> >     committed version of PoW fraud proofs) can be fooled in this way if
> >     they are denied access to the valid most PoW chain. If there are
> >     additional security concerns I overlooked, I’d love to hear them.
>
>
> I think it would be better to more precisely say that:
>
> 1.  In event of a sybil attack, a fullnode will stall and think the blockchain has no more miners.
> 2.  In event of a sybil attack, an SPV, even using this style, will follow the false blockchain.
>
> This has some differences when considering automated systems.
>
> Onchain automated payment processing systems, which use a fullnode, will refuse to acknowledge any incoming payments.
> This will lead to noisy complaints from clients of the automated payment processor, but this is a good thing since it warns the automated payment processor of the possibility of this attack occurring on them.
> The use of a timeout wherein if the fullnode is unable to see a new block for, say, 6 hours, could be done, to warn higher-layer management systems to pay attention.
> While it is sometimes the case that the real network will be unable to find a new block for hours at a time, this warning can be used to confirm if such an event is occurring, rather than a sybil attack targeting that fullnode.
>
> On the other hand, such a payment processing system, which uses an SPV with PoW fraud proofs, will be able to at least see incoming payments, and continue to release product in exchange for payment.
> Yet this is precisely a point of attack, where the automated payment processing system is sybilled and then false payments are given to the payment processor on the attack chain, which are double-spent on the global consensus chain.
> And the automated system may very well not be able to notice this.
>
> Regards,
> ZmnSCPxj

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

[ZmnSCPxj]

Good morning Ruben,

Yes, I suppose that is correct.

I suppose the critical difference is that invalid inflation can fool the SPV node, the fullnode will not be so fooled.

A somewhat larger-scale attack is to force a miner-supported miner-subsidy-increase / blocksize-increase hard fork.
If enough such SPV nodes can be sybilled, they can be forced to use the hard fork, which might incentivize them to support the hard fork rather than back-compatible consensus chain.

Regards,
ZmnSCPxj

> Hi ZmnSCPxj,
>
> Thank you for your comments. You raise an important point that I should clarify.
>
> > 1.  In event of a sybil attack, a fullnode will stall and think the blockchain has no more miners.
>
> You can still attack the full node by feeding it a minority PoW chain,
> then it won't stall.
>
> > 2.  In event of a sybil attack, an SPV, even using this style, will follow the false blockchain.
>
> Correct, but this false blockchain does need to have valid PoW.
>
> So in both cases valid PoW is required to fool nodes. The one
> difference is that for a full node, the blocks themselves also need to
> be valid (except for the fact that they are in a minority chain), but
> the end result is still that a victim can be successfully double spent
> and lose money.
>
> I hope this clarifies why I consider the security for these two
> situations to be roughly equivalent. In either situation, victims can
> be fooled into accepting invalid payments.
>
> Cheers,
> Ruben
>
> On Mon, Sep 9, 2019 at 6:14 AM ZmnSCPxj ZmnSCPxj@protonmail.com wrote:
>
> > Good morning Ruben,
> >
> > >     One might intuitively feel that the lack of a commitment is unsafe,
> > >     but there seems to be no impact on security (only bandwidth). The only
> > >     way you can be fooled is if all peers lie to you (Sybil), causing you
> > >     to follow a malicious minority chain. But even full nodes (or the
> > >     committed version of PoW fraud proofs) can be fooled in this way if
> > >     they are denied access to the valid most PoW chain. If there are
> > >     additional security concerns I overlooked, I’d love to hear them.
> > >
> >
> > I think it would be better to more precisely say that:
> >
> > 1.  In event of a sybil attack, a fullnode will stall and think the blockchain has no more miners.
> > 2.  In event of a sybil attack, an SPV, even using this style, will follow the false blockchain.
> >
> > This has some differences when considering automated systems.
> > Onchain automated payment processing systems, which use a fullnode, will refuse to acknowledge any incoming payments.
> > This will lead to noisy complaints from clients of the automated payment processor, but this is a good thing since it warns the automated payment processor of the possibility of this attack occurring on them.
> > The use of a timeout wherein if the fullnode is unable to see a new block for, say, 6 hours, could be done, to warn higher-layer management systems to pay attention.
> > While it is sometimes the case that the real network will be unable to find a new block for hours at a time, this warning can be used to confirm if such an event is occurring, rather than a sybil attack targeting that fullnode.
> > On the other hand, such a payment processing system, which uses an SPV with PoW fraud proofs, will be able to at least see incoming payments, and continue to release product in exchange for payment.
> > Yet this is precisely a point of attack, where the automated payment processing system is sybilled and then false payments are given to the payment processor on the attack chain, which are double-spent on the global consensus chain.
> > And the automated system may very well not be able to notice this.
> > Regards,
> > ZmnSCPxj

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

[Ruben Somsen]

Hi ZmnSCPxj,

>I suppose the critical difference is that invalid inflation can fool the SPV node, the fullnode will not be so fooled.

That is correct. If you sybil the SPV node, you can break any
consensus rule you like. I believe this is inherent to fraud proofs in
general, because you skip consensus checks unless you're able to
receive a fraud proof.

But note that my goal in the comparison was to assert that there is no
security difference between committing or not committing the utreexo
hash into a block. The attack your describe works in either situation,
so my conclusion remains that committing the hash adds no security.

Other weaknesses compared to full nodes are:
- the SPV nodes rely on the existence of a healthy network of utreexo
supporting full nodes
- at least one honest block needs to be mined
- consensus slows down, because you need to allow time for an honest
minority to produce a block

Cheers,
Ruben

On Mon, Sep 9, 2019 at 8:58 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ruben,
>
> Yes, I suppose that is correct.
>
> I suppose the critical difference is that invalid inflation can fool the SPV node, the fullnode will not be so fooled.
>
> A somewhat larger-scale attack is to force a miner-supported miner-subsidy-increase / blocksize-increase hard fork.
> If enough such SPV nodes can be sybilled, they can be forced to use the hard fork, which might incentivize them to support the hard fork rather than back-compatible consensus chain.
>
> Regards,
> ZmnSCPxj
>
> > Hi ZmnSCPxj,
> >
> > Thank you for your comments. You raise an important point that I should clarify.
> >
> > > 1.  In event of a sybil attack, a fullnode will stall and think the blockchain has no more miners.
> >
> > You can still attack the full node by feeding it a minority PoW chain,
> > then it won't stall.
> >
> > > 2.  In event of a sybil attack, an SPV, even using this style, will follow the false blockchain.
> >
> > Correct, but this false blockchain does need to have valid PoW.
> >
> > So in both cases valid PoW is required to fool nodes. The one
> > difference is that for a full node, the blocks themselves also need to
> > be valid (except for the fact that they are in a minority chain), but
> > the end result is still that a victim can be successfully double spent
> > and lose money.
> >
> > I hope this clarifies why I consider the security for these two
> > situations to be roughly equivalent. In either situation, victims can
> > be fooled into accepting invalid payments.
> >
> > Cheers,
> > Ruben
> >
> > On Mon, Sep 9, 2019 at 6:14 AM ZmnSCPxj ZmnSCPxj@protonmail.com wrote:
> >
> > > Good morning Ruben,
> > >
> > > >     One might intuitively feel that the lack of a commitment is unsafe,
> > > >     but there seems to be no impact on security (only bandwidth). The only
> > > >     way you can be fooled is if all peers lie to you (Sybil), causing you
> > > >     to follow a malicious minority chain. But even full nodes (or the
> > > >     committed version of PoW fraud proofs) can be fooled in this way if
> > > >     they are denied access to the valid most PoW chain. If there are
> > > >     additional security concerns I overlooked, I’d love to hear them.
> > > >
> > >
> > > I think it would be better to more precisely say that:
> > >
> > > 1.  In event of a sybil attack, a fullnode will stall and think the blockchain has no more miners.
> > > 2.  In event of a sybil attack, an SPV, even using this style, will follow the false blockchain.
> > >
> > > This has some differences when considering automated systems.
> > > Onchain automated payment processing systems, which use a fullnode, will refuse to acknowledge any incoming payments.
> > > This will lead to noisy complaints from clients of the automated payment processor, but this is a good thing since it warns the automated payment processor of the possibility of this attack occurring on them.
> > > The use of a timeout wherein if the fullnode is unable to see a new block for, say, 6 hours, could be done, to warn higher-layer management systems to pay attention.
> > > While it is sometimes the case that the real network will be unable to find a new block for hours at a time, this warning can be used to confirm if such an event is occurring, rather than a sybil attack targeting that fullnode.
> > > On the other hand, such a payment processing system, which uses an SPV with PoW fraud proofs, will be able to at least see incoming payments, and continue to release product in exchange for payment.
> > > Yet this is precisely a point of attack, where the automated payment processing system is sybilled and then false payments are given to the payment processor on the attack chain, which are double-spent on the global consensus chain.
> > > And the automated system may very well not be able to notice this.
> > > Regards,
> > > ZmnSCPxj
>
>

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

[David A. Harding]

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