[bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 3008 bytes --]

It's well known that the Bitcoin merkle tree algorithm fails to distinguish
between inner nodes and 64 byte transactions, as both txs and inner nodes are
hashed the same way. This potentially poses a problem for tx inclusion proofs,
as a miner could (with ~60 bits of brute forcing) create a transaction that
committed to a transaction that was not in fact in the blockchain.

Since odd-numbered inner/leaf nodes are concatenated with themselves and hashed
twice, the depth of all leaves (txs) in the tree is fixed.

It occured to me that if the depth of the merkle tree is known, this
vulnerability can be trivially avoided by simply comparing the length of the
merkle path to that known depth. For pruned nodes, if the depth is saved prior
to pruning the block contents itself, this would allow for completely safe
verification of tx inclusion proofs, without a soft-fork; storing this data in
the block header database would be a simple thing to do.

Lite client verification without a trusted source of known-valid headers is
dangerous anyway, so this protection makes for a fairly simple addition to any
lite client protocol.


# Brute Force Cost Assuming a Valid Tx

Consider the following 64 byte transaction:

    tx = CTransaction([CTxIn(COutPoint(b'\xaa'*32,0xbbbbbbbb),nSequence=0xcccccccc)],[CTxOut(2**44-1,CScript([b'\xdd\xdd\xdd']))],nLockTime=2**31-1)

If we serialize it, the last 32 bytes are:

    aaaaaaaaaa bbbbbbbb 00 cccccccc 01 ffffffffff0f0000 04 03dddddd ffffff7f
    ↳prevhash↲ ↳ n    ↲    ↳ seq  ↲    ↳ nValue       ↲    ↳ pubk ↲ ↳lockt ↲
                        ↳ sig_len   ↳num_txouts         ↳scriptPubKey_len

Of those fields, we have free choice of the following bits:

prevhash:  40 - prev tx fully brute-forcable, as tx can be created to match
prev_n:    16 - can create a tx with up to about 2^16 outputs
seq:       32 - fully brute-forcable in nVersion=1 txs
nValue:    44 - assuming attacker has access to 175,921 BTC, worth ~1.3 billion right now
pubk:      32 - fully brute-forcable if willing to lose BTC spent; all scriptPubKeys are valid
nLockTime: 31 - valid time-based nLockTime
Total: 195 bits free choice → 61 bits need to be brute-forced

Additionally, this can be improved slightly by a few more bits by checking for
valid scriptSig/scriptPubKey combinations other than a zero-length scriptSig;
the attacker can also avoid creating an unspendable output this way, and
recover their funds by spending it in the same block with a third transaction.
An obvious implementation making use of this would be to check that the high
bits of prevout.n are zero first, prior to doing more costly checks.

Finally, if inflation is not controlled - and thus nValue can be set freely -
note how the brute force is trivial. There may very well exist crypto-currencies
for which this brute-force is much easier than it is on Bitcoin!

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Bram Cohen]

[-- Attachment #1: Type: text/plain, Size: 3650 bytes --]

Are you proposing a soft fork to include the number of transactions in a
block in the block headers to compensate for the broken Merkle format? That
sounds like a good idea.

On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> It's well known that the Bitcoin merkle tree algorithm fails to distinguish
> between inner nodes and 64 byte transactions, as both txs and inner nodes
> are
> hashed the same way. This potentially poses a problem for tx inclusion
> proofs,
> as a miner could (with ~60 bits of brute forcing) create a transaction that
> committed to a transaction that was not in fact in the blockchain.
>
> Since odd-numbered inner/leaf nodes are concatenated with themselves and
> hashed
> twice, the depth of all leaves (txs) in the tree is fixed.
>
> It occured to me that if the depth of the merkle tree is known, this
> vulnerability can be trivially avoided by simply comparing the length of
> the
> merkle path to that known depth. For pruned nodes, if the depth is saved
> prior
> to pruning the block contents itself, this would allow for completely safe
> verification of tx inclusion proofs, without a soft-fork; storing this
> data in
> the block header database would be a simple thing to do.
>
> Lite client verification without a trusted source of known-valid headers is
> dangerous anyway, so this protection makes for a fairly simple addition to
> any
> lite client protocol.
>
>
> # Brute Force Cost Assuming a Valid Tx
>
> Consider the following 64 byte transaction:
>
>     tx = CTransaction([CTxIn(COutPoint(b'\xaa'*32,0xbbbbbbbb),
> nSequence=0xcccccccc)],[CTxOut(2**44-1,CScript([b'\
> xdd\xdd\xdd']))],nLockTime=2**31-1)
>
> If we serialize it, the last 32 bytes are:
>
>     aaaaaaaaaa bbbbbbbb 00 cccccccc 01 ffffffffff0f0000 04 03dddddd
> ffffff7f
>     ↳prevhash↲ ↳ n    ↲    ↳ seq  ↲    ↳ nValue       ↲    ↳ pubk ↲ ↳lockt
> ↲
>                         ↳ sig_len   ↳num_txouts         ↳scriptPubKey_len
>
> Of those fields, we have free choice of the following bits:
>
> prevhash:  40 - prev tx fully brute-forcable, as tx can be created to match
> prev_n:    16 - can create a tx with up to about 2^16 outputs
> seq:       32 - fully brute-forcable in nVersion=1 txs
> nValue:    44 - assuming attacker has access to 175,921 BTC, worth ~1.3
> billion right now
> pubk:      32 - fully brute-forcable if willing to lose BTC spent; all
> scriptPubKeys are valid
> nLockTime: 31 - valid time-based nLockTime
> Total: 195 bits free choice → 61 bits need to be brute-forced
>
> Additionally, this can be improved slightly by a few more bits by checking
> for
> valid scriptSig/scriptPubKey combinations other than a zero-length
> scriptSig;
> the attacker can also avoid creating an unspendable output this way, and
> recover their funds by spending it in the same block with a third
> transaction.
> An obvious implementation making use of this would be to check that the
> high
> bits of prevout.n are zero first, prior to doing more costly checks.
>
> Finally, if inflation is not controlled - and thus nValue can be set
> freely -
> note how the brute force is trivial. There may very well exist
> crypto-currencies
> for which this brute-force is much easier than it is on Bitcoin!
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

[-- Attachment #2: Type: text/html, Size: 4515 bytes --]

Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1726 bytes --]

On Thu, Jun 07, 2018 at 02:15:35PM -0700, Bram Cohen wrote:
> Are you proposing a soft fork to include the number of transactions in a
> block in the block headers to compensate for the broken Merkle format? That
> sounds like a good idea.
> 
> On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> > It's well known that the Bitcoin merkle tree algorithm fails to distinguish
> > between inner nodes and 64 byte transactions, as both txs and inner nodes
> > are
> > hashed the same way. This potentially poses a problem for tx inclusion
> > proofs,
> > as a miner could (with ~60 bits of brute forcing) create a transaction that
> > committed to a transaction that was not in fact in the blockchain.
> >
> > Since odd-numbered inner/leaf nodes are concatenated with themselves and
> > hashed
> > twice, the depth of all leaves (txs) in the tree is fixed.
> >
> > It occured to me that if the depth of the merkle tree is known, this
> > vulnerability can be trivially avoided by simply comparing the length of
> > the
> > merkle path to that known depth. For pruned nodes, if the depth is saved
> > prior
> > to pruning the block contents itself, this would allow for completely safe
> > verification of tx inclusion proofs, without a soft-fork; storing this
                                         ^^^^^^^^^^^^^^^^^^^

Re-read my post: I specifically said you do not need a soft-fork to implement
this. In fact, I think you can argue that this is an accidental feature, not a
bug, as it further encourages the use of safe full verifiaction rather than
unsafe lite clients.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Bram Cohen]

[-- Attachment #1: Type: text/plain, Size: 2037 bytes --]

So are you saying that if fully validating nodes wish to prune they can
maintain the ability to validate old transactions by cacheing the number of
transactions in each previous block?

On Thu, Jun 7, 2018 at 3:20 PM, Peter Todd <pete@petertodd.org> wrote:

> On Thu, Jun 07, 2018 at 02:15:35PM -0700, Bram Cohen wrote:
> > Are you proposing a soft fork to include the number of transactions in a
> > block in the block headers to compensate for the broken Merkle format?
> That
> > sounds like a good idea.
> >
> > On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev <
> > bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > > It's well known that the Bitcoin merkle tree algorithm fails to
> distinguish
> > > between inner nodes and 64 byte transactions, as both txs and inner
> nodes
> > > are
> > > hashed the same way. This potentially poses a problem for tx inclusion
> > > proofs,
> > > as a miner could (with ~60 bits of brute forcing) create a transaction
> that
> > > committed to a transaction that was not in fact in the blockchain.
> > >
> > > Since odd-numbered inner/leaf nodes are concatenated with themselves
> and
> > > hashed
> > > twice, the depth of all leaves (txs) in the tree is fixed.
> > >
> > > It occured to me that if the depth of the merkle tree is known, this
> > > vulnerability can be trivially avoided by simply comparing the length
> of
> > > the
> > > merkle path to that known depth. For pruned nodes, if the depth is
> saved
> > > prior
> > > to pruning the block contents itself, this would allow for completely
> safe
> > > verification of tx inclusion proofs, without a soft-fork; storing this
>                                          ^^^^^^^^^^^^^^^^^^^
>
> Re-read my post: I specifically said you do not need a soft-fork to
> implement
> this. In fact, I think you can argue that this is an accidental feature,
> not a
> bug, as it further encourages the use of safe full verifiaction rather than
> unsafe lite clients.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>

[-- Attachment #2: Type: text/html, Size: 2866 bytes --]

Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Sergio Demian Lerner]

[-- Attachment #1: Type: text/plain, Size: 3177 bytes --]

Hi Peter,
We reported this as CVE-2017-12842, although it may have been known by
developers before us.
There are hundreds of SPV wallets out there, without even considering other
more sensitive systems relying on SPV proofs.
As I said we, at RSK, discovered this problem in 2017. For RSK it's very
important this is fixed because our SPV bridge uses SPV proofs.
I urge all people participating in this mailing list and the rest of the
Bitcoin community to work on this issue for the security and clean-design
of Bitcoin.

My suggestion is to use in the version bits 4 bits indicating the tree
depth (-1), as a soft-fork, so
00=1 depth,
0F = 16 depth (maximum 64K transactions). Very clean.

The other option is to ban transaction with size lower or equal to 64.

Best regards,
 Sergio.

On Sat, Jun 9, 2018 at 5:31 AM Bram Cohen via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> So are you saying that if fully validating nodes wish to prune they can
> maintain the ability to validate old transactions by cacheing the number of
> transactions in each previous block?
>
> On Thu, Jun 7, 2018 at 3:20 PM, Peter Todd <pete@petertodd.org> wrote:
>
>> On Thu, Jun 07, 2018 at 02:15:35PM -0700, Bram Cohen wrote:
>> > Are you proposing a soft fork to include the number of transactions in a
>> > block in the block headers to compensate for the broken Merkle format?
>> That
>> > sounds like a good idea.
>> >
>> > On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev <
>> > bitcoin-dev@lists.linuxfoundation.org> wrote:
>> >
>> > > It's well known that the Bitcoin merkle tree algorithm fails to
>> distinguish
>> > > between inner nodes and 64 byte transactions, as both txs and inner
>> nodes
>> > > are
>> > > hashed the same way. This potentially poses a problem for tx inclusion
>> > > proofs,
>> > > as a miner could (with ~60 bits of brute forcing) create a
>> transaction that
>> > > committed to a transaction that was not in fact in the blockchain.
>> > >
>> > > Since odd-numbered inner/leaf nodes are concatenated with themselves
>> and
>> > > hashed
>> > > twice, the depth of all leaves (txs) in the tree is fixed.
>> > >
>> > > It occured to me that if the depth of the merkle tree is known, this
>> > > vulnerability can be trivially avoided by simply comparing the length
>> of
>> > > the
>> > > merkle path to that known depth. For pruned nodes, if the depth is
>> saved
>> > > prior
>> > > to pruning the block contents itself, this would allow for completely
>> safe
>> > > verification of tx inclusion proofs, without a soft-fork; storing this
>>                                          ^^^^^^^^^^^^^^^^^^^
>>
>> Re-read my post: I specifically said you do not need a soft-fork to
>> implement
>> this. In fact, I think you can argue that this is an accidental feature,
>> not a
>> bug, as it further encourages the use of safe full verifiaction rather
>> than
>> unsafe lite clients.
>>
>> --
>> https://petertodd.org 'peter'[:-1]@petertodd.org
>>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 4744 bytes --]

Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Sergio Demian Lerner]

[-- Attachment #1: Type: text/plain, Size: 3792 bytes --]

Also it must be noted that an attacker having only 1.3M USD that can
brute-force 72 bits (4 days of hashing on capable ASICs) can perform the
same attack, so the attack is entirely feasible and no person should accept
more than 1M USD using a SPV wallet.

Also the attack can be repeated: once you create the "extension point"
block, you can attack more and more parties without any additional
computation.


On Sat, Jun 9, 2018 at 1:03 PM Sergio Demian Lerner <
sergio.d.lerner@gmail.com> wrote:

> Hi Peter,
> We reported this as CVE-2017-12842, although it may have been known by
> developers before us.
> There are hundreds of SPV wallets out there, without even considering
> other more sensitive systems relying on SPV proofs.
> As I said we, at RSK, discovered this problem in 2017. For RSK it's very
> important this is fixed because our SPV bridge uses SPV proofs.
> I urge all people participating in this mailing list and the rest of the
> Bitcoin community to work on this issue for the security and clean-design
> of Bitcoin.
>
> My suggestion is to use in the version bits 4 bits indicating the tree
> depth (-1), as a soft-fork, so
> 00=1 depth,
> 0F = 16 depth (maximum 64K transactions). Very clean.
>
> The other option is to ban transaction with size lower or equal to 64.
>
> Best regards,
>  Sergio.
>
> On Sat, Jun 9, 2018 at 5:31 AM Bram Cohen via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> So are you saying that if fully validating nodes wish to prune they can
>> maintain the ability to validate old transactions by cacheing the number of
>> transactions in each previous block?
>>
>> On Thu, Jun 7, 2018 at 3:20 PM, Peter Todd <pete@petertodd.org> wrote:
>>
>>> On Thu, Jun 07, 2018 at 02:15:35PM -0700, Bram Cohen wrote:
>>> > Are you proposing a soft fork to include the number of transactions in
>>> a
>>> > block in the block headers to compensate for the broken Merkle format?
>>> That
>>> > sounds like a good idea.
>>> >
>>> > On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev <
>>> > bitcoin-dev@lists.linuxfoundation.org> wrote:
>>> >
>>> > > It's well known that the Bitcoin merkle tree algorithm fails to
>>> distinguish
>>> > > between inner nodes and 64 byte transactions, as both txs and inner
>>> nodes
>>> > > are
>>> > > hashed the same way. This potentially poses a problem for tx
>>> inclusion
>>> > > proofs,
>>> > > as a miner could (with ~60 bits of brute forcing) create a
>>> transaction that
>>> > > committed to a transaction that was not in fact in the blockchain.
>>> > >
>>> > > Since odd-numbered inner/leaf nodes are concatenated with themselves
>>> and
>>> > > hashed
>>> > > twice, the depth of all leaves (txs) in the tree is fixed.
>>> > >
>>> > > It occured to me that if the depth of the merkle tree is known, this
>>> > > vulnerability can be trivially avoided by simply comparing the
>>> length of
>>> > > the
>>> > > merkle path to that known depth. For pruned nodes, if the depth is
>>> saved
>>> > > prior
>>> > > to pruning the block contents itself, this would allow for
>>> completely safe
>>> > > verification of tx inclusion proofs, without a soft-fork; storing
>>> this
>>>                                          ^^^^^^^^^^^^^^^^^^^
>>>
>>> Re-read my post: I specifically said you do not need a soft-fork to
>>> implement
>>> this. In fact, I think you can argue that this is an accidental feature,
>>> not a
>>> bug, as it further encourages the use of safe full verifiaction rather
>>> than
>>> unsafe lite clients.
>>>
>>> --
>>> https://petertodd.org 'peter'[:-1]@petertodd.org
>>>
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

[-- Attachment #2: Type: text/html, Size: 5596 bytes --]

Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Sergio Demian Lerner]

[-- Attachment #1.1: Type: text/plain, Size: 4245 bytes --]

Here is our internal report, if you want more details on the problem.
 (our reported attack complexity may slightly differ from what Peter has
provided, but the attack complexity depends on the funds the attacker is
willing to lock).

regards,
 Sergio.

On Sat, Jun 9, 2018 at 2:21 PM Sergio Demian Lerner <
sergio.d.lerner@gmail.com> wrote:

> Also it must be noted that an attacker having only 1.3M USD that can
> brute-force 72 bits (4 days of hashing on capable ASICs) can perform the
> same attack, so the attack is entirely feasible and no person should accept
> more than 1M USD using a SPV wallet.
>
> Also the attack can be repeated: once you create the "extension point"
> block, you can attack more and more parties without any additional
> computation.
>
>
> On Sat, Jun 9, 2018 at 1:03 PM Sergio Demian Lerner <
> sergio.d.lerner@gmail.com> wrote:
>
>> Hi Peter,
>> We reported this as CVE-2017-12842, although it may have been known by
>> developers before us.
>> There are hundreds of SPV wallets out there, without even considering
>> other more sensitive systems relying on SPV proofs.
>> As I said we, at RSK, discovered this problem in 2017. For RSK it's very
>> important this is fixed because our SPV bridge uses SPV proofs.
>> I urge all people participating in this mailing list and the rest of the
>> Bitcoin community to work on this issue for the security and clean-design
>> of Bitcoin.
>>
>> My suggestion is to use in the version bits 4 bits indicating the tree
>> depth (-1), as a soft-fork, so
>> 00=1 depth,
>> 0F = 16 depth (maximum 64K transactions). Very clean.
>>
>> The other option is to ban transaction with size lower or equal to 64.
>>
>> Best regards,
>>  Sergio.
>>
>> On Sat, Jun 9, 2018 at 5:31 AM Bram Cohen via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>> So are you saying that if fully validating nodes wish to prune they can
>>> maintain the ability to validate old transactions by cacheing the number of
>>> transactions in each previous block?
>>>
>>> On Thu, Jun 7, 2018 at 3:20 PM, Peter Todd <pete@petertodd.org> wrote:
>>>
>>>> On Thu, Jun 07, 2018 at 02:15:35PM -0700, Bram Cohen wrote:
>>>> > Are you proposing a soft fork to include the number of transactions
>>>> in a
>>>> > block in the block headers to compensate for the broken Merkle
>>>> format? That
>>>> > sounds like a good idea.
>>>> >
>>>> > On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev <
>>>> > bitcoin-dev@lists.linuxfoundation.org> wrote:
>>>> >
>>>> > > It's well known that the Bitcoin merkle tree algorithm fails to
>>>> distinguish
>>>> > > between inner nodes and 64 byte transactions, as both txs and inner
>>>> nodes
>>>> > > are
>>>> > > hashed the same way. This potentially poses a problem for tx
>>>> inclusion
>>>> > > proofs,
>>>> > > as a miner could (with ~60 bits of brute forcing) create a
>>>> transaction that
>>>> > > committed to a transaction that was not in fact in the blockchain.
>>>> > >
>>>> > > Since odd-numbered inner/leaf nodes are concatenated with
>>>> themselves and
>>>> > > hashed
>>>> > > twice, the depth of all leaves (txs) in the tree is fixed.
>>>> > >
>>>> > > It occured to me that if the depth of the merkle tree is known, this
>>>> > > vulnerability can be trivially avoided by simply comparing the
>>>> length of
>>>> > > the
>>>> > > merkle path to that known depth. For pruned nodes, if the depth is
>>>> saved
>>>> > > prior
>>>> > > to pruning the block contents itself, this would allow for
>>>> completely safe
>>>> > > verification of tx inclusion proofs, without a soft-fork; storing
>>>> this
>>>>                                          ^^^^^^^^^^^^^^^^^^^
>>>>
>>>> Re-read my post: I specifically said you do not need a soft-fork to
>>>> implement
>>>> this. In fact, I think you can argue that this is an accidental
>>>> feature, not a
>>>> bug, as it further encourages the use of safe full verifiaction rather
>>>> than
>>>> unsafe lite clients.
>>>>
>>>> --
>>>> https://petertodd.org 'peter'[:-1]@petertodd.org
>>>>
>>>
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>>
>>

[-- Attachment #1.2: Type: text/html, Size: 6287 bytes --]

[-- Attachment #2: Vulnerability in Bitcoin Merkle Tree Design.pdf --]
[-- Type: application/pdf, Size: 402454 bytes --]

Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1032 bytes --]

On Sat, Jun 09, 2018 at 02:21:17PM +0200, Sergio Demian Lerner wrote:
> Also it must be noted that an attacker having only 1.3M USD that can
> brute-force 72 bits (4 days of hashing on capable ASICs) can perform the
> same attack, so the attack is entirely feasible and no person should accept
> more than 1M USD using a SPV wallet.

That doesn't make any sense. Against a SPV wallet you don't need that attack;
with that kind of budget you can fool it by just creating a fake block at far
less cost, along with a sybil attack. Sybils aren't difficult to pull off when
you have the budget to be greating fake blocks.

> Also the attack can be repeated: once you create the "extension point"
> block, you can attack more and more parties without any additional
> computation.

That's technically incorrect: txouts can only be spent once, so you'll need to
do 2^40 work each time you want to repeat the attack to grind the matching part
of the prevout again.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1382 bytes --]

On Sat, Jun 09, 2018 at 01:03:53PM +0200, Sergio Demian Lerner wrote:
> Hi Peter,
> We reported this as CVE-2017-12842, although it may have been known by
> developers before us.

It's been known so long ago that I incorrectly thought the attack was ok to
discuss in public; I had apparently incorrectly remembered a conversation I had
with Greg Maxwell over a year ago where I thought he said it was fine to
discuss because it was well known.

My apologies to anyone who thinks my post was jumping the gun by discussing
this in public; cats out of the bag now anyway.

> There are hundreds of SPV wallets out there, without even considering other
> more sensitive systems relying on SPV proofs.
> As I said we, at RSK, discovered this problem in 2017. For RSK it's very
> important this is fixed because our SPV bridge uses SPV proofs.
> I urge all people participating in this mailing list and the rest of the
> Bitcoin community to work on this issue for the security and clean-design
> of Bitcoin.

My post is arguing that we *don't* need to fix the attack, because we can make
pruned nodes invulerable to it while retaining the ability to verify merkle
path tx inclusion proofs.

As for SPV, there is no attack to fix: they can be attacked at much lower cost
by simply generating fake blocks.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Sergio Demian Lerner]

[-- Attachment #1: Type: text/plain, Size: 1665 bytes --]

Yo can fool a SPV wallet even if it requires a thousands confirmations
using this attack, and you don't need a Sybil attack, so yes, it impacts
SPV wallets also. The protections a SPV node should have to prevent this
attack are  different, so it must be considered separately.

It should be said that a SPV node can avoid accepting payments if any
Merkle node is at the same time a valid transaction, and that basically
almost eliminates the problem.

SPV Wallet would reject valid payments with a astonishingly low probability.



On Sat, Jun 9, 2018 at 2:45 PM Peter Todd <pete@petertodd.org> wrote:

> On Sat, Jun 09, 2018 at 02:21:17PM +0200, Sergio Demian Lerner wrote:
> > Also it must be noted that an attacker having only 1.3M USD that can
> > brute-force 72 bits (4 days of hashing on capable ASICs) can perform the
> > same attack, so the attack is entirely feasible and no person should
> accept
> > more than 1M USD using a SPV wallet.
>
> That doesn't make any sense. Against a SPV wallet you don't need that
> attack;
> with that kind of budget you can fool it by just creating a fake block at
> far
> less cost, along with a sybil attack. Sybils aren't difficult to pull off
> when
> you have the budget to be greating fake blocks.
>
> > Also the attack can be repeated: once you create the "extension point"
> > block, you can attack more and more parties without any additional
> > computation.
>
> That's technically incorrect: txouts can only be spent once, so you'll
> need to
> do 2^40 work each time you want to repeat the attack to grind the matching
> part
> of the prevout again.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>

[-- Attachment #2: Type: text/html, Size: 2260 bytes --]

Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1060 bytes --]

On Sat, Jun 09, 2018 at 02:51:55PM +0200, Sergio Demian Lerner wrote:
> Yo can fool a SPV wallet even if it requires a thousands confirmations
> using this attack, and you don't need a Sybil attack, so yes, it impacts
> SPV wallets also. The protections a SPV node should have to prevent this
> attack are  different, so it must be considered separately.

There's hardly any cases where "thousands of confirmations" change anything.

Anyway, SPV is a discredited concept and we shouldn't be concerning ourselves
with it.

> It should be said that a SPV node can avoid accepting payments if any
> Merkle node is at the same time a valid transaction, and that basically
> almost eliminates the problem.

Indeed it does: between the number of txouts, scriptSig length, scriptPubKey
length, and the upper bits of nValue we have ~32 known bits that we can use to
distinguish between inner nodes and transactions. That's a false positive rate
of under one in a billion, so no issues there.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]