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 7ED7E1932 for ; Mon, 16 Sep 2019 16:49:33 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from newmail.dtrt.org (li1228-87.members.linode.com [45.79.129.87]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D9DD681A for ; Mon, 16 Sep 2019 16:49:32 +0000 (UTC) Received: from harding by newmail.dtrt.org with local (Exim 4.92) (envelope-from ) id 1i9uBv-0003ZH-QW; Mon, 16 Sep 2019 12:49:31 -0400 Date: Mon, 16 Sep 2019 06:48:21 -1000 From: "David A. Harding" To: Ruben Somsen , Bitcoin Protocol Discussion Message-ID: <20190916164821.yi6i6ymljpg4izgk@ganymede> References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: NeoMutt/20180716 X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,KHOP_HELO_FCRDNS autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [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: Mon, 16 Sep 2019 16:49:33 -0000 On Sun, Sep 08, 2019 at 05:39:28AM +0200, Ruben Somsen via bitcoin-dev wrote: > After looking more deeply into Tadge Dryja’s utreexo work [0], it has > become clear to me that this opens up a way to implement PoW fraud > proofs [1] without a soft fork. This is a nifty idea. > [...] you’d need to download: > > [...] > > 3. the utreexo merkle proofs which prove that all inputs of N+1 are > part of the UTXO set (~1MB) I think "~1 MB" is probably a reasonable estimate for the average case but not for the worst case. To allow verification of the spends in block N+1, each UTXO entry must contain its entire scriptPubKey. I believe the current consensus rules allow scriptPubKeys to be up to 10,000 bytes in size. A specially-constructed block can contain a bit more than 20,000 inputs, making the worst case size of just the UTXO entries that needs to be communicated over 200 MB. > 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’s say block M, and you simply execute the same three steps to find > out which peer is wrong I think this also expands to a worst-case of over 200 MB. A lying peer will only be able to get you on one of these checks, so it's 200 MB per lying peer. For an honest peer communicating valid blocks, the worst case is that they'll need to communicate both of these state transactions, so over 400 MB. That could be a bandwidth-wasting DoS attack on honest listening nodes if there were a large number of SPV clients using this type of fraud proofs. Additionally, each node capable of providing fraud proofs will need to persistently store the state transition proof for each new block. I assume this is equal to the block undo data currently stored by archival full nodes plus the utreexo partial merkle branches. This data would probably not be stored by pruned nodes, at least not beyond their prune depth, even for pruned nodes that use utreexo. That would mean this system will only work with archival full nodes with an extra "index" containing the utreexo partial merkle branches, or it will require querying utreexo bridge nodes. Given that both of those would require significant additional system resources beyond the minimum required to operate a full node, such nodes might be rare and so make it relatively easy to eclipse attack an SPV client depending on these proofs. Finally, this system depends on SPV clients implementing all the same consensus checks that full nodes can currently perform. Given that most SPV clients I'm aware of today don't even perform the full range of checks it's possible to run on block headers, I have serious doubts that many (or any) SPV clients will actually implement full verification. On top of that, each client must implement those checks perfectly or they could be tricked into a chainsplit the same as a full node that follows different rules than the economic consensus. > [1] Improving SPV security with PoW fraud proofs: > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-April/016873.html One thing I didn't like in your original proposal---which I appologize for keeping to myself---is that the SPV client will accept confirmations on the bad chain until a fork is produced. Even a miner with a minority of the hash rate will sometimes be able to produce a 6-block chain before the remaining miners produce a single block. In that case, SPV clients with a single dishonest peer in collusion with the miner will accept any transctions in the first block of that chain as having six confirmations. That's the same as it is today, but today SPV users don't think fraud proofs help keep them secure. I think that, if we wanted to widely deploy fraud proofs depending on forks as a signal, we'd have to also retrain SPV users to wait for much higher confirmation counts before accepting transactions as reasonably secure. -Dave