Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 80DF61174 for ; Sat, 9 Jun 2018 11:04:33 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-lf0-f41.google.com (mail-lf0-f41.google.com [209.85.215.41]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 0D890604 for ; Sat, 9 Jun 2018 11:04:31 +0000 (UTC) Received: by mail-lf0-f41.google.com with SMTP id y20-v6so23811277lfy.0 for ; Sat, 09 Jun 2018 04:04:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=jONLnOE+xgNDoCG6rY5ZuLisfsHj5PQhVkQv8WkQoOY=; b=DJ5itZ1Kys9KgciHLMDW2z82Nr7gS1rVgHBEQhpfYreaDyTr98qinIRi7XaPZP9JOG ZfiQOUGFTN+zZKISxf0+TAqtXBJ7e2cMpIar1g3M8+vUX4B5JANcqIbHS1BPmWL9C5z9 2uazEJoNs3BhV7nJxi6dLrkqBbV1jEMC3UdGul4XFxWnrj2CsgB1P9oAiuYKmYQGy3Bv HYNLOaJ+ornyxwjhOR3N0kAKonU7/ao0csQjL6mxrUj0PcoxoTMsKrofwJchLGJab6kD XdrkxM4oOae+RCevVGkVLXFlpzqkol/S/NT+U7vbdX8wHX9KP0uIEQqlGACn5dln/F8A qF1Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=jONLnOE+xgNDoCG6rY5ZuLisfsHj5PQhVkQv8WkQoOY=; b=ArTM+WrzlAU3qT0N2D1WyNUlK00c3bDQBvQOCpDXQdAdebQC6AiiVWPoiYRJK5py5x 31mw8ytUkC0NRR8U3YR1/fX2HAIBanPF8LUPkWcL3EJnFOZH4Kycpl0pHnFWti8KMR2A AdNxkMbfVzZmKp03iLA8Tlv5MSh7cPrsp6bKz+RQrBdQGPrC7l7QtE3BlXPdZ06FL/Wg 6yGwFJVbI5iv+zaLEI6xm71Awco9Rz9epX17umUjsfdYW4E61A8PjZS9954rdY5JLqg+ CCBTyYQjYhqpwgQa/9sWV8fXOTPvRzex0MgLJlmEUDxaSVxUrHkYOgGwKG7QzS/jtcNx 1vFg== X-Gm-Message-State: APt69E2cgdqjryduwAVrNrkWBMnpArbO8ZB4XMlq0ccsrErHQdcD4crg lVMyMKR1CWU5eYXV0oXpLTsEAdXuFXWMidQmkyxutlgd X-Google-Smtp-Source: ADUXVKLoV1T3gVRWKLIJ7oFwU/dTO7dSMiU7RvaNEqrM6vDKIXkKZ0uiPb1TZPjjh2CCGPKGxdveOPZOlUqiB0sHTRU= X-Received: by 2002:a19:e544:: with SMTP id c65-v6mr6296876lfh.134.1528542270419; Sat, 09 Jun 2018 04:04:30 -0700 (PDT) MIME-Version: 1.0 References: <20180607171311.6qdjohfuuy3ufriv@petertodd.org> <20180607222028.zbva4vrv64dzrmxy@petertodd.org> In-Reply-To: From: Sergio Demian Lerner Date: Sat, 9 Jun 2018 13:03:53 +0200 Message-ID: To: bram@chia.net, bitcoin-dev Content-Type: multipart/alternative; boundary="0000000000000d757e056e337b00" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, 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: Sat, 09 Jun 2018 14:58:55 +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: Sat, 09 Jun 2018 11:04:33 -0000 --0000000000000d757e056e337b00 Content-Type: text/plain; charset="UTF-8" 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 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 > --0000000000000d757e056e337b00 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Peter,
We reported this as CVE-2017-12842, although= it may have been known by developers before us.=C2=A0
There are= =C2=A0hundreds of SPV wallets out there, without even considering other mor= e sensitive systems relying on SPV proofs.=C2=A0
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 peop= le 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.
<= div>
My suggestion is to use in the version bits 4 bits indic= ating the tree depth (-1), as a soft-fork, so=C2=A0
00=3D1 depth,= =C2=A0
0F =3D 16 depth (maximum 64K transactions).=20 Very clean.
=C2=A0
The other option is to ban transaction with= size lower or equal to 64.=C2=A0

Best regards,
=C2=A0Sergio.

On Sat, Jun 9, 2018 at 5:31 AM Bram Cohen via bitcoin-dev <bitcoin-dev@lists.linuxfo= undation.org> wrote:
So are you saying that if fully validating nodes wish to prune th= ey can maintain the ability to validate old transactions by cacheing the nu= mber 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 inn= er nodes
> > are
> > hashed the same way. This potentially poses a problem for tx incl= usion
> > proofs,
> > as a miner could (with ~60 bits of brute forcing) create a transa= ction that
> > committed to a transaction that was not in fact in the blockchain= .
> >
> > Since odd-numbered inner/leaf nodes are concatenated with themsel= ves 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, t= his
> > vulnerability can be trivially avoided by simply comparing the le= ngth of
> > the
> > merkle path to that known depth. For pruned nodes, if the depth i= s saved
> > prior
> > to pruning the block contents itself, this would allow for comple= tely safe
> > verification of tx inclusion proofs, without a soft-fork; storing= this
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0^^^^^^^^^^^^^^^^^^^

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

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

_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--0000000000000d757e056e337b00--