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 D9D02BB3 for ; Sun, 8 Sep 2019 03:39:45 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f67.google.com (mail-wr1-f67.google.com [209.85.221.67]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 111E0619 for ; Sun, 8 Sep 2019 03:39:45 +0000 (UTC) Received: by mail-wr1-f67.google.com with SMTP id i1so9684224wro.4 for ; Sat, 07 Sep 2019 20:39:44 -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 :content-transfer-encoding; bh=d5czZX+1ZzZ8rLEGCz7lcCN6biNvXk2n4TkDQHRutcQ=; b=E5O8Z9QG1m7Y9GFiTbVVR7Chi31qn+ztoNPjYPqOoaFUC/fwDk++Uzw33uZQJLdcVd v5Otmh1W6Ku+S4sa9rsrtIJPH2xhNz4Do4DDyy71GcoUP7ZIX8sYhwFHbR8MqxcZnaIj Sov3pIHyk0d9EXXAw4rUv78i+1UeExYEIPKbvD9I/haX4F0RKA+tm1BRIgq2HARgE0FO xi18MfpSuDsCFYN/kzC6aLcn+UubGkW38pzevu6dwkFPFzOm0MJz+jMXj5pmqouj+Ps2 r823ghJNKF7Cte1EygzWVumxSw4fGkLQt4ImMYRukICa/EuKshMtubOqTsHFaJg0IwIV wwNg== 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 :content-transfer-encoding; bh=d5czZX+1ZzZ8rLEGCz7lcCN6biNvXk2n4TkDQHRutcQ=; b=HJYQNR7Pnuj5wTXo8dDoVz9zfDOApakCKKfymNJNb4leg4XmHOf6qmgpj/g2v8h+1Q QAPU6v/L0hqtbPs5YgeYeOnUkXneG1jiDI1bi2mlGBlabw6E9hov+n3FChfz3bF+B5lZ tiCBhXhf0n0f79nbhzTz7XhBwkOnIYntAQ46P9wliuVSBYTV3jJgxZDZ27T+chA2K9OY 4nOl5GAdzaXKTqse0bSUHilxO6SAMOyeuCo3xeXgIAKuvEACj4I3Y90USLl/O7vf+0gM Oa6ykIQfzoWBHinxk7qy/59etDC27ObXiPeOVkMTjTuyyKqgm9kbEawHgYmISESYNK+z IWuQ== X-Gm-Message-State: APjAAAW1hFu9J2AAGiUY14K9gMuL+6bqOC/w/bdcX9jeFPR+mWhlQ2L6 sVgLd3oGlLBKIr1/X8dv523yUF6n3kBdycZXV6Zd+3y8oAI= X-Google-Smtp-Source: APXvYqyzvDsxC/CiSUZBcTBSQdy7nlELyg6+gPXrnU5/roEB2CqW8CdbmV9tgz9I62PQXOVaBs0mA5CNWDU4e24pMNg= X-Received: by 2002:a5d:4146:: with SMTP id c6mr13111681wrq.205.1567913983346; Sat, 07 Sep 2019 20:39:43 -0700 (PDT) MIME-Version: 1.0 From: Ruben Somsen Date: Sun, 8 Sep 2019 05:39:28 +0200 Message-ID: To: Bitcoin Protocol Discussion Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, 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: Sun, 08 Sep 2019 04:00:24 +0000 Subject: [bitcoin-dev] PoW fraud 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: Sun, 08 Sep 2019 03:39:46 -0000 After looking more deeply into Tadge Dryja=E2=80=99s utreexo work [0], it h= as become clear to me that this opens up a way to implement PoW fraud proofs [1] without a soft fork. With utreexo, we can efficiently verify state transitions between blocks. Verifying a block from a valid utreexo hash requires only about a megabyte worth of merkle proofs. PoW fraud proofs assume that block N is valid if no miner has tried to fork it (read my original post for details [1]). We can extend that assumption to the utreexo hash of block N, and use that to verify fork block N+1, and reject it if the block is invalid, with just 2-3MB of data. For simplicity, I=E2=80=99ll first start by explaining a version with commitments (which would require a soft fork). When a fork (i.e. a PoW fraud proof) occurs at height N+1, indicating that the block might be invalid, you=E2=80=99d need to download: 1. block N+1 from the most PoW chain (~1-2MB) 2. the utreexo hash commitment inside of block N (e.g. a merkle path to the coinbase) 3. the utreexo merkle proofs which prove that all inputs of N+1 are part of the UTXO set (~1MB) Of course step 2 requires a soft fork, but we can also do a non-committed version by relying on the assumption that at least one of your peers is honest and then evaluate disagreements. We simply replace step 2 above with the following: 2. [Download] the utreexo hash of block N from all your peers If it turns out that one of your peers disagrees on what the correct hash is, you find the last utreexo hash where that peer still agreed, let=E2=80=99s say block M, and you simply execute the same three steps to f= ind out which peer is wrong: download block M+1, then get the merkle proofs to verify whether the peer correctly transitioned their utreexo hash from M to M+1. One might intuitively feel that the lack of a commitment is unsafe, but there seems to be no impact on security (only bandwidth). The only way you can be fooled is if all peers lie to you (Sybil), causing you to follow a malicious minority chain. But even full nodes (or the committed version of PoW fraud proofs) can be fooled in this way if they are denied access to the valid most PoW chain. If there are additional security concerns I overlooked, I=E2=80=99d love to hear them. In short, utreexo can enable PoW fraud proofs without a soft fork. At the cost of downloading a couple of MB per stale block (and per malicious peer), an SPV client gains the ability to (eventually) reject the most PoW chain as long as one honest block gets mined, thereby increasing its security beyond 51% honest miners. Finally, while I think this goes without saying, I=E2=80=99d like to reiter= ate that this is by no means a replacement for running a full node. You=E2=80= =99re depending on other full nodes to do full verification and assuming at least some of the miners are honest. If everyone did this, Bitcoin would not be secure. -- Ruben Somsen [0] Utreexo paper: https://eprint.iacr.org/2019/611.pdf [1] Improving SPV security with PoW fraud proofs: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-April/016873.h= tml