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 D55CF13EB for ; Fri, 18 Sep 2015 19:05:43 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wi0-f173.google.com (mail-wi0-f173.google.com [209.85.212.173]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 49A6E15B for ; Fri, 18 Sep 2015 19:05:43 +0000 (UTC) Received: by wicge5 with SMTP id ge5so44834630wic.0 for ; Fri, 18 Sep 2015 12:05:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:content-type:content-transfer-encoding:subject:message-id:date :to:mime-version; bh=W79hzA9f6JDzbJ37pSlGcl+66s3Os/78Nph1G7cpfUs=; b=EatUY81dv8Pqa1so3uYBGJfHnSeyUHmz7ZMmtpGrh1x12IbUVm+i9aJ/sFmjkCOnfc vSm7PACA+Fr6h00vpL6lW3hlKukGyp8oG3ACH6jnqpvMoRKaz8AOI0006Wzjl+EYsnPs d9mvFtXn+FMHNQ6orpQjYk8ao17H2PqAWPa/eNO2I5l/2A1pKpymQyF4u/mJvDC5g5xN kRqTdZ1CUzjTMYC6oykeMNkGrVnfVf2XSoCCQokrH/iyAsXuCvHCsiJR4X+3ot9+OZFs stK/o11Drq6lItFL28Kkcq13JafI4IAek6ZdyUR/0pY1MCmYP+KmE3crNxkMZaIzDTTA 1LgQ== X-Received: by 10.194.60.115 with SMTP id g19mr8711333wjr.29.1442603141665; Fri, 18 Sep 2015 12:05:41 -0700 (PDT) Received: from [192.168.1.33] ([212.60.121.11]) by smtp.gmail.com with ESMTPSA id le3sm209348wjb.25.2015.09.18.12.05.40 for (version=TLS1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 18 Sep 2015 12:05:41 -0700 (PDT) From: =?utf-8?Q?Rune_Kj=C3=A6r_Svendsen?= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Message-Id: <5D55F6EC-801B-4607-882F-B76CF57298B1@gmail.com> Date: Fri, 18 Sep 2015 21:05:37 +0200 To: bitcoin-dev@lists.linuxfoundation.org Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2104\)) X-Mailer: Apple Mail (2.2104) X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, MIME_QP_LONG_LINE, RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [bitcoin-dev] Hash of UTXO set as consensus-critical X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 18 Sep 2015 19:05:44 -0000 Currently, when a new node wants to join the network, it needs to = retrieve the entire blockchain history, starting from January 2009 and = up until now, in order to derive a UTXO set that it can verify new = blocks/transactions against. With a blockchain size of 40GB and a UTXO = size of around 1GB, the extra bandwidth required is significant, and = will keep increasing indefinitely. If a newly mined block were to = include the UTXO set hash of the chain up until the previous block =E2=80=94= the hash of the UTXO set on top of which this block builds =E2=80=94 = then new nodes, who want to know whether a transaction is valid, would = be able to acquire the UTXO set in a trustless manner, by only verifying = proof-of-work headers, and knowing that a block with an invalid UTXO set = hash would be rejected. I=E2=80=99m not talking about calculating a complicated tree structure = from the UTXO set, which would put further burden on already burdened = Bitcoin Core nodes. We simply include the hash of the current UTXO set = in a newly created block, such that the transactions in the new block = build *on top* of the UTXO set whose hash is specified. This actually = alleviates Bitcoin Core nodes, as it will now become possible for nodes = without the entire blockchain to answer SPV queries (by retrieving the = UTXO set trustlessly and using this to answer queries). It also saves = bandwidth for Bitcore Core nodes, who only need to send roughly 1GB of = data, in order to synchronise a node, rather than 40GB+. I will continue = to run a full Bitcoin Core node, saving the entire blockchain history, = but it shouldn=E2=80=99t be a requirement to hold the entire transaction = history in order to start verifying new transactions. As far as I can see, this also forces miners to actually maintain an = UTXO set, rather than just build on top of the chain with the most = proof-of-work. Producing a UTXO set and verifying a block against a = chain is the same thing, so by including the hash of the UTXO set we = force miners to verify the block that they want to build on top of. Am I missing something obvious, because as far as I can see, this solves = the problem of quadratic time complexity for initial sync: = http://www.youtube.com/watch?v=3DTgjrS-BPWDQ&t=3D2h02m12s The only added step to verifying a block is to hash the UTXO set. So it = does require additional computation, but most modern CPUs have a SHA256 = throughput of around 500 MB/s, which means it takes only two seconds to = hash the UTXO set. And this can be improved further (GPUs can do 2-3 = GB/s). A small sacrifice for the added ease of initial syncing, in my = opinion. /Rune=