From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 15B923EE for ; Thu, 7 Jun 2018 21:15:39 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f68.google.com (mail-wm0-f68.google.com [74.125.82.68]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id E72CA747 for ; Thu, 7 Jun 2018 21:15:37 +0000 (UTC) Received: by mail-wm0-f68.google.com with SMTP id r125-v6so21762746wmg.2 for ; Thu, 07 Jun 2018 14:15:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=chia-net.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=YFqI0VmWywQRxGPkU6MIcqx26ngcjYsM7BMEa6xl0yM=; b=ksAUkYimrxrl6rZNN7at348aPjqZed4vDXB96QtbZowsccPgvS4VTxpiL+3PAEONrQ N04mkVXZ4HpMAXzMsD81jco7/Bp/7pAC7/wFeynu2nHMWRbnOXi+FJVslthlp2GWYhhz JMMo26b7s0aEJrVtzb8tC/5mFzDIMZULe+jTforbPMLxNcRPDaoVjbLRTwyN19UNVpVt zFqdtFavVfCDNMSYS3swVC6KhCVEXSwD590WQOxlTUW8tJfbjMp+o6zoffSRDf/2DZAq Td0I/0h+XIFJL1eLU+LP1L0rctTbtgn0n587XR5xbFz1wP1JkBosuH+ItxHVSVG03C3Z CPpA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=YFqI0VmWywQRxGPkU6MIcqx26ngcjYsM7BMEa6xl0yM=; b=S8KcZFSfBwnG/8EBf59p9DEGLR1NYnHstWdsC6YwovrCJz26/PT7xsC3gESMTGDxsQ HnotYzMZzlSVX5BzeZQoeugXlpN2fV4lN3Vo57vewfIVG5xjqXlm/khXEeNiIP+Y8DON dZZwIkEouPbQ4r0AE1k2WkZTifjs9SgX5gpJtgni+nklRqSmm8OWUAYQsrVmDBI5FNiE pWV7AxnBNFHW0waJj6EXnEjY0v9iq+ys0EYOkX/J2Eu/GFnqqoDbtxTxAHmP8cXN6IxW uOUKvglEi/qA1qLKl5h2OzNSHEDEF9bCtHgGLcKDQvgx5oAZJPlnNumtVyqEReu3YyFM dUAg== X-Gm-Message-State: APt69E3I70ZJPI2JH6E3hvWYABC/rpJRAzpDB/wNy8WXbOQBHjE14iap DuusVNwu6ABEYboYZqc2aFdxPqxQvzLQ/O7DM8ahnA1X X-Google-Smtp-Source: ADUXVKJaesxelHNj7IKdTKu+5zagqdeoguQQk7lnuwyjMIHtng8rogfR4dU/C1YMaAdBbtEoosWrGFoAUn3j6zHLw0g= X-Received: by 2002:a1c:c687:: with SMTP id w129-v6mr2698665wmf.66.1528406136458; Thu, 07 Jun 2018 14:15:36 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:a1c:b984:0:0:0:0:0 with HTTP; Thu, 7 Jun 2018 14:15:35 -0700 (PDT) X-Originating-IP: [65.200.105.218] In-Reply-To: <20180607171311.6qdjohfuuy3ufriv@petertodd.org> References: <20180607171311.6qdjohfuuy3ufriv@petertodd.org> From: Bram Cohen Date: Thu, 7 Jun 2018 14:15:35 -0700 Message-ID: To: Peter Todd , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000d62a6c056e13c852" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Thu, 07 Jun 2018 21:17:52 +0000 Subject: Re: [bitcoin-dev] Trusted merkle tree depth for safe tx inclusion proofs without a soft fork X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 07 Jun 2018 21:15:39 -0000 --000000000000d62a6c056e13c852 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 distingui= sh > 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 th= at > 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 saf= e > 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 t= o > any > lite client protocol. > > > # Brute Force Cost Assuming a Valid Tx > > Consider the following 64 byte transaction: > > tx =3D CTransaction([CTxIn(COutPoint(b'\xaa'*32,0xbbbbbbbb), > nSequence=3D0xcccccccc)],[CTxOut(2**44-1,CScript([b'\ > xdd\xdd\xdd']))],nLockTime=3D2**31-1) > > If we serialize it, the last 32 bytes are: > > aaaaaaaaaa bbbbbbbb 00 cccccccc 01 ffffffffff0f0000 04 03dddddd > ffffff7f > =E2=86=B3prevhash=E2=86=B2 =E2=86=B3 n =E2=86=B2 =E2=86=B3 seq = =E2=86=B2 =E2=86=B3 nValue =E2=86=B2 =E2=86=B3 pubk =E2=86=B2 = =E2=86=B3lockt > =E2=86=B2 > =E2=86=B3 sig_len =E2=86=B3num_txouts = =E2=86=B3scriptPubKey_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 mat= ch > prev_n: 16 - can create a tx with up to about 2^16 outputs > seq: 32 - fully brute-forcable in nVersion=3D1 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 =E2=86=92 61 bits need to be brute-forced > > Additionally, this can be improved slightly by a few more bits by checkin= g > 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 > > --000000000000d62a6c056e13c852 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Are you proposing a soft fork to include the number of tra= nsactions in a block in the block headers to compensate for the broken Merk= le format? That sounds like a good idea.
On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd vi= a 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 a= re
hashed the same way. This potentially poses a problem for tx inclusion proo= fs,
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 ha= shed
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 th= e
merkle path to that known depth. For pruned nodes, if the depth is saved pr= ior
to pruning the block contents itself, this would allow for completely safe<= br> 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:

=C2=A0 =C2=A0 tx =3D CTransaction([CTxIn(COutPoint(b'\xaa'*32,= 0xbbbbbbbb),nSequence=3D0xcccccccc)],[CTxOut(2**44-1,CScript([b&#= 39;\xdd\xdd\xdd']))],nLockTime=3D2**31-1)

If we serialize it, the last 32 bytes are:

=C2=A0 =C2=A0 aaaaaaaaaa bbbbbbbb 00 cccccccc 01 ffffffffff0f0000 04 03dddd= dd ffffff7f
=C2=A0 =C2=A0 =E2=86=B3prevhash=E2=86=B2 =E2=86=B3 n=C2=A0 =C2=A0 =E2=86=B2= =C2=A0 =C2=A0 =E2=86=B3 seq=C2=A0 =E2=86=B2=C2=A0 =C2=A0 =E2=86=B3 nValue= =C2=A0 =C2=A0 =C2=A0 =C2=A0=E2=86=B2=C2=A0 =C2=A0 =E2=86=B3 pubk =E2=86=B2 = =E2=86=B3lockt =E2=86=B2
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =E2=86=B3 sig_len=C2=A0 =C2=A0=E2=86=B3num_txouts=C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0=E2=86=B3scriptPubKey_len

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

prevhash:=C2=A0 40 - prev tx fully brute-forcable, as tx can be created to = match
prev_n:=C2=A0 =C2=A0 16 - can create a tx with up to about 2^16 outputs
seq:=C2=A0 =C2=A0 =C2=A0 =C2=A032 - fully brute-forcable in nVersion=3D1 tx= s
nValue:=C2=A0 =C2=A0 44 - assuming attacker has access to 175,921 BTC, wort= h ~1.3 billion right now
pubk:=C2=A0 =C2=A0 =C2=A0 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 =E2=86=92 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 scriptSi= g;
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 transacti= on.
An obvious implementation making use of this would be to check that the hig= h
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-curre= ncies
for which this brute-force is much easier than it is on Bitcoin!

--
http= s://petertodd.org 'peter'[:-1]@petertodd.org

_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev


--000000000000d62a6c056e13c852--