path: root/69/90f294491a6b170d7728e80641a94dac820797

Return-Path: <bram@chia.net>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 15B923EE
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	Thu,  7 Jun 2018 21:15:37 +0000 (UTC)
Received: by mail-wm0-f68.google.com with SMTP id r125-v6so21762746wmg.2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bram@chia.net>
Date: Thu, 7 Jun 2018 14:15:35 -0700
Message-ID: <CAHUJnBB7UL3mH6SixP_M4yooMVP3DgZa+5hiQOmF=AiqfdpfOg@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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

<div dir=3D"ltr">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.</div><div class=3D"gmail_extra"><b=
r><div class=3D"gmail_quote">On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd vi=
a bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.lin=
uxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</=
a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0=
 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">It&#39;s well known =
that the Bitcoin merkle tree algorithm fails to distinguish<br>
between inner nodes and 64 byte transactions, as both txs and inner nodes a=
re<br>
hashed the same way. This potentially poses a problem for tx inclusion proo=
fs,<br>
as a miner could (with ~60 bits of brute forcing) create a transaction that=
<br>
committed to a transaction that was not in fact in the blockchain.<br>
<br>
Since odd-numbered inner/leaf nodes are concatenated with themselves and ha=
shed<br>
twice, the depth of all leaves (txs) in the tree is fixed.<br>
<br>
It occured to me that if the depth of the merkle tree is known, this<br>
vulnerability can be trivially avoided by simply comparing the length of th=
e<br>
merkle path to that known depth. For pruned nodes, if the depth is saved pr=
ior<br>
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<br>
the block header database would be a simple thing to do.<br>
<br>
Lite client verification without a trusted source of known-valid headers is=
<br>
dangerous anyway, so this protection makes for a fairly simple addition to =
any<br>
lite client protocol.<br>
<br>
<br>
# Brute Force Cost Assuming a Valid Tx<br>
<br>
Consider the following 64 byte transaction:<br>
<br>
=C2=A0 =C2=A0 tx =3D CTransaction([CTxIn(COutPoint(<wbr>b&#39;\xaa&#39;*32,=
0xbbbbbbbb),<wbr>nSequence=3D0xcccccccc)],[<wbr>CTxOut(2**44-1,CScript([b&#=
39;\<wbr>xdd\xdd\xdd&#39;]))],nLockTime=3D2**<wbr>31-1)<br>
<br>
If we serialize it, the last 32 bytes are:<br>
<br>
=C2=A0 =C2=A0 aaaaaaaaaa bbbbbbbb 00 cccccccc 01 ffffffffff0f0000 04 03dddd=
dd ffffff7f<br>
=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<br>
=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<br>
<br>
Of those fields, we have free choice of the following bits:<br>
<br>
prevhash:=C2=A0 40 - prev tx fully brute-forcable, as tx can be created to =
match<br>
prev_n:=C2=A0 =C2=A0 16 - can create a tx with up to about 2^16 outputs<br>
seq:=C2=A0 =C2=A0 =C2=A0 =C2=A032 - fully brute-forcable in nVersion=3D1 tx=
s<br>
nValue:=C2=A0 =C2=A0 44 - assuming attacker has access to 175,921 BTC, wort=
h ~1.3 billion right now<br>
pubk:=C2=A0 =C2=A0 =C2=A0 32 - fully brute-forcable if willing to lose BTC =
spent; all scriptPubKeys are valid<br>
nLockTime: 31 - valid time-based nLockTime<br>
Total: 195 bits free choice =E2=86=92 61 bits need to be brute-forced<br>
<br>
Additionally, this can be improved slightly by a few more bits by checking =
for<br>
valid scriptSig/scriptPubKey combinations other than a zero-length scriptSi=
g;<br>
the attacker can also avoid creating an unspendable output this way, and<br=
>
recover their funds by spending it in the same block with a third transacti=
on.<br>
An obvious implementation making use of this would be to check that the hig=
h<br>
bits of prevout.n are zero first, prior to doing more costly checks.<br>
<br>
Finally, if inflation is not controlled - and thus nValue can be set freely=
 -<br>
note how the brute force is trivial. There may very well exist crypto-curre=
ncies<br>
for which this brute-force is much easier than it is on Bitcoin!<br>
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
-- <br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> &#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org"=
 rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br>
</font></span><br>______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br></blockquote></div><br></div>

--000000000000d62a6c056e13c852--