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 AFE9DE28 for ; Fri, 10 Aug 2018 00:22:24 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-lf1-f51.google.com (mail-lf1-f51.google.com [209.85.167.51]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id ED1D41FB for ; Fri, 10 Aug 2018 00:22:23 +0000 (UTC) Received: by mail-lf1-f51.google.com with SMTP id y200-v6so5366361lfd.7 for ; Thu, 09 Aug 2018 17:22:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=MuAJJ9igzG/IUAVoyIJc9CxxR89avLq/s4IwK2mN9co=; b=MaZMcGE33+8uNi/97rC688sxIYYWBsHCFeTYXJGskZrgftROFdbd7vKjPyqk0zv7Oi 56FbU+ogfKBd5UNHd5o+WomV6Dx3StsoGSPdyX2e6Iqviy3GWipm+wOeiF0VcPRGu29y ywbzUuRst1hVIS7olMsUsu4KkwidxD0jtp5dajpt4oAq2PB5cOFeH4QPdFO2B314/cf7 Tj2xGmFFg3WCnGgr3Es5xTvR/xRDluwZHK44NiVuawh5cEJlvH2xRI4dP0yR/JoGilk5 j+A01KeKcnYt0wIzAC5whtpMhWHDaJV+J4xywApW+/kVu2QsV3pGFBG5M9X6Sfwsnu64 8YoQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=MuAJJ9igzG/IUAVoyIJc9CxxR89avLq/s4IwK2mN9co=; b=Huv1ZOwro/Pr7pD3FQQkD+cV9kxy9GMgkIlG01RzewxWmWJUkpGbG0Hpw6F1iEjlJe YwEP7FCD1wWs+epXenWPwQIaPreG6/e32ObrRa0lHIhJiMjsMzP/EBR4iwJl0vCr85Im UN6MJNbu14Q3+cVzB8iC7msDpkN4Vax+blkHBCeQKo7WQhvZ38nKxDkNYc+q75ZJhPFw SqBwxRK2Feph4xRw4ZvZhpjJBw1gxb/JD78HKA1BKZjWOF5Feyo/rSPcNLKiSOu7jMHY jK2VQ6hLfukCK21jt5NawS+jMqmz2ZCktsK8Am6MN9ZQHQAI6foBw0BodiaG46y/Ik0o NhmA== X-Gm-Message-State: AOUpUlFwjlt702JD/nZWBVhHjDWqdP8aj699lTrcVSwqMjDnJHFBxvCY D0Yr+SmaBKfZZsEzrBwh469b8PJB00z9DMC4oBIVOvYZ X-Google-Smtp-Source: AA+uWPx0ylyWYg5kTf0z8Sc7eJIAGvRA6WhXBeiR+1TRtVTPUdWUUw6C4qmv9cjqpQIebRXhM6ZRk0+nfC2yruxgmtE= X-Received: by 2002:a19:2207:: with SMTP id i7-v6mr2745364lfi.69.1533860542005; Thu, 09 Aug 2018 17:22:22 -0700 (PDT) MIME-Version: 1.0 From: Sergio Demian Lerner Date: Thu, 9 Aug 2018 21:21:17 -0300 Message-ID: To: bitcoin-dev Content-Type: multipart/alternative; boundary="000000000000bdc692057309bc2e" 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: Mon, 13 Aug 2018 11:08:42 +0000 Subject: [bitcoin-dev] Simple change to the "merkleblock" command to protect from SPV proof extension attacks 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: Fri, 10 Aug 2018 00:22:24 -0000 --000000000000bdc692057309bc2e Content-Type: text/plain; charset="UTF-8" Hi, While fixing RSK's SPV bridge I came up with an idea to fix the MERKLEBLOCK command to prevent rogue peers from attacking SPV peers using Bitcoin's Merkle tree structure flaws. The most annoying attack is the one that tries to confuse a victim peer into thinking a transaction is an inner node, extending such node with a new right-sided branch with a fake transaction (*) . The old idea to soft-fork Bitcoin to make invalid 64-byte transactions is attractive, but also a coordination problem that could be avoided with this new proposal. The idea is simple, and it's not a fork, but a network protocol improvement. Let A be the hash digest that must be combined with the hash digest B, such that the upper node hash is SHA256(SHA256(A | B)). Therefore A = SHA256(SHA256(X)) and B = SHA256(SHA256(Y)), and X and Y are either Bitcoin transactions or other inner nodes. Instead of storing A, the merkleblock structure should store a pre-image of A, or SHA256(X). If the block only has the coinbase, nothing is done. The pre-image change could be done to both left and right hashes, but it's enough to do it to all left-side hashes that do not have children in the partial merkle tree structure (let's call them terminal hahes. to avoid confusion with leaf hashes). Verifiers (SPV nodes) would apply a single SHA256() operation to the left-sided terminal hashes before combining them. The cost to the verifier is in the worse case only 33% more. This basically limits the attacker's ability to supply chosen-hash digests in order to build a transaction. Because the left side contains most of the previn hash, the attacker would need to bruteforce a huge space (about 208 bits) in order to come up with a pre-image that maps to a owned previn. Meet-in-the-middle attacks would be expensive as UTXOs are not free. To implement this change, a new command MERKLEBLOCK2 could be implemented or the protocol version could be used to differentiate between the two modes of the MERKLEBLOCK command. If the idea gets community support, I may write the BIP/code or invite anyone to do it. regards (*) https://bitslog.wordpress.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/ --000000000000bdc692057309bc2e Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi,
=C2=A0While fixing RSK's SPV bridge I came up = with an idea to fix the MERKLEBLOCK command to prevent rogue peers from att= acking SPV peers using Bitcoin's Merkle tree structure flaws. The most = annoying attack is the one that=C2=A0tries to confuse a victim peer into th= inking a transaction is an inner node, extending such node with a new right= -sided branch with a fake transaction (*) .=C2=A0

= The old idea to soft-fork Bitcoin to make invalid 64-byte transactions is a= ttractive, but also a coordination problem that could be avoided with this = new proposal.

The idea is simple, and it's not= a fork, but a network protocol improvement.
Let A be the hash di= gest that must be combined with the hash digest B, such that the upper node= hash is SHA256(SHA256(A | B)).
Therefore A =3D SHA256(SHA256(X))= and B =3D SHA256(SHA256(Y)), and X and Y are either Bitcoin transactions o= r other inner nodes.=C2=A0
Instead of storing A, the merkleblock = structure should store a pre-image of A, or=C2=A0SHA256(X).
<= div> https://bitslog.wordpress.com/2018/06/09/leaf-node-we= akness-in-bitcoin-merkle-tree-design/

--000000000000bdc692057309bc2e--