diff options
| author | Jim Posen <jim.posen@gmail.com> | 2019-04-03 16:03:12 -0700 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2019-04-03 23:03:26 +0000 |
| commit | 96c83107ec14451f0d2098cf0c0db651f079c342 (patch) | |
| tree | f4384d77944e3dc2956496ccb6475ea8d2bb136d | |
| parent | dff14c0caaf78b9da16d012b47d141420b4b4259 (diff) | |
| download | pi-bitcoindev-96c83107ec14451f0d2098cf0c0db651f079c342.tar.gz pi-bitcoindev-96c83107ec14451f0d2098cf0c0db651f079c342.zip | |
Re: [bitcoin-dev] assumeutxo and UTXO snapshots
| -rw-r--r-- | 46/e9898d6c1389c9fa93741e5dbb6b3c9c07cb5b | 403 |
1 files changed, 403 insertions, 0 deletions
diff --git a/46/e9898d6c1389c9fa93741e5dbb6b3c9c07cb5b b/46/e9898d6c1389c9fa93741e5dbb6b3c9c07cb5b new file mode 100644 index 000000000..90a07044c --- /dev/null +++ b/46/e9898d6c1389c9fa93741e5dbb6b3c9c07cb5b @@ -0,0 +1,403 @@ +Return-Path: <jim.posen@gmail.com> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 3BF0419A5 + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 3 Apr 2019 23:03:26 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.7.6 +Received: from mail-qt1-f175.google.com (mail-qt1-f175.google.com + [209.85.160.175]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C8C5C7A6 + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 3 Apr 2019 23:03:24 +0000 (UTC) +Received: by mail-qt1-f175.google.com with SMTP id x12so1069731qts.7 + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 03 Apr 2019 16:03:24 -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; + bh=meDNqgbJMXUk+LgCPrMhmqvmmO1Avkso4aSKiZfzEXk=; + b=GnFubEaCrpfkLJ36QMMRI0DgR/QByzbK0pfYwuINPY31Z/5n1CCjPUNzUsQqFV+GQv + KQEmSf9G/VncTePtYSkDZI/ZC5ri1mNmUQGF7uZfEjftDiYaDo4PSwBjBGLX4Fm754sN + LQPFI6HMmr4+ZX3x/X+BVRCk/owgKICa192sgoRdF8r63b6vNI+jMWSr02zvaD1wcOe8 + WeMATx2QmDjEobOJwdbDfSrVtXVsaCb1iBp3PNEmcGBZ341D81S2PRqZuREO1ScbXZit + kKrOqUBeA7bDcM9zgIvdDgvWgHJty/Zli56NNhmvg8zfKbNrtflicjKStDNS0kZfNvLa + XGMw== +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; + bh=meDNqgbJMXUk+LgCPrMhmqvmmO1Avkso4aSKiZfzEXk=; + b=EQjqOlfK87FEB7emSWmpyrZY/B5/MqT31PiCTnl4Har9JYq2wnWUsYRAsTDN3cnlX8 + 8cezqqqtwNmejQXCotU8V8NZZsiXE/9YVOrLqW6Ex515rlZljhdQH3Vjj4f/6MW9lVHQ + 5H7FH5UukrtWo6woz0EpHGYYZfBLNGp5hmxfWXA389U8piYZ3R2qcmxFHqA7BGVs3G/W + l1YtqVhI30GE229A030HXdGAvT1vDJKym8Gp7EA8UsgQjVxjo6AwrvJ4AIdBYVmltjJ1 + nM5/r7Hs05fkVY/Hy1sHuy1/Ip7y6f/AvdhHzZ1H9V9y2szYwW9BMM3vkJhLiBdTx/+i + AuyQ== +X-Gm-Message-State: APjAAAXfHXKEgYbeyMmVNyQHnP3gr/yG+7eZm4OCX5HdvF2tYTzzSRbT + OLzsM4nb/CZStmu52sm9eisIlZmENZVGBPowfnE= +X-Google-Smtp-Source: APXvYqwc9bxY2tx4hrForjYmZ1jOGiD3ME5BDd1YiJlmbepUPiAcGJUciQFJyQ/idm7jDfsy+FBchG3gUYQLSziHegA= +X-Received: by 2002:ac8:308a:: with SMTP id v10mr2502782qta.185.1554332603801; + Wed, 03 Apr 2019 16:03:23 -0700 (PDT) +MIME-Version: 1.0 +References: <CAPfvXf+JS6ZhXUieWVxiaNa4uhhWwafCk3odMKy5F_yi=XwngA@mail.gmail.com> +In-Reply-To: <CAPfvXf+JS6ZhXUieWVxiaNa4uhhWwafCk3odMKy5F_yi=XwngA@mail.gmail.com> +From: Jim Posen <jim.posen@gmail.com> +Date: Wed, 3 Apr 2019 16:03:12 -0700 +Message-ID: <CADZtCSjx-YeGzfs4DtuXZ-8y4tWiHB7Luh133S0ZPbQzWz-dbw@mail.gmail.com> +To: "James O'Beirne" <james.obeirne@gmail.com>, + Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +Content-Type: multipart/alternative; boundary="000000000000b665240585a842b2" +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: Thu, 04 Apr 2019 02:12:35 +0000 +Subject: Re: [bitcoin-dev] assumeutxo and UTXO snapshots +X-BeenThere: bitcoin-dev@lists.linuxfoundation.org +X-Mailman-Version: 2.1.12 +Precedence: list +List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> +X-List-Received-Date: Wed, 03 Apr 2019 23:03:26 -0000 + +--000000000000b665240585a842b2 +Content-Type: text/plain; charset="UTF-8" + +Big Concept ACK. I think this would be one of the biggest usability +improvements for Bitcoin and I see no security issues with the assumevalid +approach. I also agree that it's important to start work on this even +before the ultimate, perfect accumulator has been designed/tested and the +commitment scheme can always be upgraded later on. assumeutxo syncing +actually seems pretty orthogonal to the accumulator research. + +I have a few questions + +- So any nodes that do an initial sync will stop at the assumeutxo height, +serialize a snapshot of the chain state and store it? How many nodes are +expected to do this? Any idea how long this takes? Should it be enabled by +default? +- Would pruned nodes still download all historic blocks to double-check the +snapshot or only full nodes that intend to serve block data? +- How long are old snapshots retained? Presumably during a new release +nodes should keep at least a version back. Without P2P signalling of which +snapshots are available, they maybe have to keep all old snapshots or even +download old ones. + +and comments + +- The snapshot should probably be chunked up to minimize the amount of +bandwidth/IO/memory a malicious node could waste before you realize. Also, +it would make parallel downloading easier. + +On Tue, Apr 2, 2019 at 4:43 PM James O'Beirne via bitcoin-dev < +bitcoin-dev@lists.linuxfoundation.org> wrote: + +> Hi, +> +> I'd like to discuss assumeutxo, which is an appealing and simple +> optimization in the spirit of assumevalid[0]. +> +> # Motivation +> +> To start a fully validating bitcoin client from scratch, that client +> currently +> needs to perform an initial block download. To the surprise of no one, IBD +> takes a linear amount time based on the length of the chain's history. For +> clients running on modest hardware under limited bandwidth constraints, +> say a mobile device, completing IBD takes a considerable amount of time +> and thus poses serious usability challenges. +> +> As a result, having fully validating clients run on such hardware is rare +> and +> basically unrealistic. Clients with even moderate resource constraints +> are encouraged to rely on the SPV trust model. Though we have promising +> improvements to existing SPV modes pending deployment[1], it's worth +> thinking about a mechanism that would allow such clients to use trust +> models closer to full validation. +> +> The subject of this mail is a proposal for a complementary alternative to +> SPV +> modes, and which is in the spirit of an existing default, `assumevalid`. +> It may +> help modest clients transact under a security model that closely resembles +> full validation within minutes instead of hours or days. +> +> # assumeutxo +> +> The basic idea is to allow nodes to initialize using a serialized version +> of the +> UTXO set rendered by another node at some predetermined height. The +> initializing node syncs the headers chain from the network, then obtains +> and +> loads one of these UTXO snapshots (i.e. a serialized version of the UTXO +> set +> bundled with the block header indicating its "base" and some other +> metadata). +> +> Based upon the snapshot, the node is able to quickly reconstruct its +> chainstate, +> and compares a hash of the resulting UTXO set to a preordained hash +> hard-coded +> in the software a la assumevalid. This all takes ~23 minutes, not +> accounting for +> download of the 3.2GB snapshot[2]. +> +> The node then syncs to the network tip and afterwards begins a simultaneous +> background validation (i.e., a conventional IBD) up to the base height of +> the +> snapshot in order to achieve full validation. Crucially, even while the +> background validation is happening the node can validate incoming blocks +> and +> transact with the benefit of the full (assumed-valid) UTXO set. +> +> Snapshots could be obtained from multiple separate peers in the same +> manner as +> block download, but I haven't put much thought into this. In concept it +> doesn't +> matter too much where the snapshots come from since their validity is +> determined via content hash. +> +> # Security +> +> Obviously there are some security implications due consideration. While +> this +> proposal is in the spirit of assumevalid, practical attacks may become +> easier. +> Under assumevalid, a user can be tricked into transacting under a false +> history +> if an attacker convinces them to start bitcoind with a malicious +> `-assumevalid` +> parameter, sybils their node, and then feeds them a bogus chain +> encompassing +> all of the hard-coded checkpoints[3]. +> +> The same attack is made easier in assumeutxo because, unlike in +> assumevalid, +> the attacker need not construct a valid PoW chain to get the victim's node +> into +> a false state; they simply need to get the user to accept a bad +> `-assumeutxo` +> parameter and then supply them an easily made UTXO snapshot containing, +> say, a +> false coin assignment. +> +> For this reason, I recommend that if we were to implement assumeutxo, we +> not +> allow its specification via commandline argument[4]. +> +> Beyond this risk, I can't think of material differences in security +> relative to +> assumevalid, though I appeal to the list for help with this. +> +> # More fully validating clients +> +> A particularly exciting use-case for assumeutxo is the possibility of +> mobile +> devices functioning as fully validating nodes with access to the complete +> UTXO +> set (as an alternative to SPV models). The total resource burden needed to +> start a node +> from scratch based on a snapshot is, at time of writing, a ~(3.2GB +> + blocks_to_tip * 4MB) download and a few minutes of processing time, +> which sounds +> manageable for many mobile devices currently in use. +> +> A mobile user could initialize an assumed-valid bitcoin node within an +> hour, +> transact immediately, and complete a pruned full validation of their +> assumed-valid chain over the next few days, perhaps only doing the +> background +> IBD when their device has access to suitable high-bandwidth connections. +> +> If we end up implementing an accumulator-based UTXO scaling design[5][6] +> down +> the road, it's easy to imagine an analogous process that would allow very +> fast +> startup using an accumulator of a few kilobytes in lieu of a multi-GB +> snapshot. +> +> --- +> +> I've created a related issue at our Github repository here: +> https://github.com/bitcoin/bitcoin/issues/15605 +> +> and have submitted a draft implementation of snapshot usage via RPC here: +> https://github.com/bitcoin/bitcoin/pull/15606 +> +> I'd like to discuss here whether this is a good fit for Bitcoin +> conceptually. Concrete +> plans for deployment steps should be discussed in the Github issue, and +> after all +> that my implementation may be reviewed as a sketch of the specific software +> changes necessary. +> +> Regards, +> James +> +> +> [0]: +> https://bitcoincore.org/en/2017/03/08/release-0.14.0/#assumed-valid-blocks +> [1]: https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki +> [2]: as tested at height 569895, on a 12 core Intel Xeon Silver 4116 CPU @ +> 2.10GHz +> [3]: +> https://github.com/bitcoin/bitcoin/blob/84d0fdc/src/chainparams.cpp#L145-L161 +> [4]: Marco Falke is due credit for this point +> [5]: utreexo: https://www.youtube.com/watch?v=edRun-6ubCc +> [6]: Boneh, Bunz, Fisch on accumulators: https://eprint.iacr.org/2018/1188 +> +> _______________________________________________ +> bitcoin-dev mailing list +> bitcoin-dev@lists.linuxfoundation.org +> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev +> + +--000000000000b665240585a842b2 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr">Big Concept ACK. I think this would be one of the biggest = +usability improvements for Bitcoin and I see no security issues with the as= +sumevalid approach. I also agree that it's important to start work on t= +his even before the ultimate, perfect accumulator has been designed/tested = +and the commitment scheme can always be upgraded later on. assumeutxo synci= +ng actually seems pretty orthogonal to the accumulator research.<div><br></= +div><div>I have a few questions<div><br></div><div>- So any nodes that do a= +n initial sync will stop at the assumeutxo height, serialize a snapshot of = +the chain state and store it? How many nodes are expected to do this? Any i= +dea how long this takes? Should it be enabled by default?</div><div>- Would= + pruned nodes still download all historic blocks to double-check the snapsh= +ot or only full nodes that intend to serve block data?</div><div>- How long= + are old snapshots retained? Presumably during a new release nodes should k= +eep at least a version back. Without P2P signalling of which snapshots are = +available, they maybe have to keep all old snapshots or even download old o= +nes.</div><div><br></div><div>and comments</div><div><br></div><div>- The s= +napshot should probably be chunked up to minimize the amount of bandwidth/I= +O/memory a malicious node could waste before you realize. Also, it would ma= +ke parallel downloading easier.</div></div></div><br><div class=3D"gmail_qu= +ote"><div dir=3D"ltr" class=3D"gmail_attr">On Tue, Apr 2, 2019 at 4:43 PM J= +ames O'Beirne via bitcoin-dev <<a href=3D"mailto:bitcoin-dev@lists.l= +inuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org= +</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:= +0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">= +<div dir=3D"ltr"><div dir=3D"ltr"><div>Hi,<br></div><div><br></div><div>I&#= +39;d like to discuss assumeutxo, which is an appealing and simple=C2=A0</di= +v><div>optimization in the spirit of assumevalid[0].</div><div><br></div><d= +iv># Motivation</div><div><br></div><div>To start a fully validating bitcoi= +n client from scratch, that client currently</div><div>needs to perform an = +initial block download. To the surprise of no one, IBD=C2=A0</div><div>take= +s a linear amount time based on the length of the chain's history. For= +=C2=A0</div><div>clients running on modest hardware under limited bandwidth= + constraints,=C2=A0</div><div>say a mobile device, completing IBD takes a c= +onsiderable amount of time=C2=A0</div><div>and thus poses serious usability= + challenges.</div><div><br></div><div>As a result, having fully validating = +clients run on such hardware is rare and</div><div>basically unrealistic. C= +lients with even moderate resource constraints</div><div>are encouraged to = +rely on the SPV trust model. Though we have promising</div><div>improvement= +s to existing SPV modes pending deployment[1], it's worth</div><div>thi= +nking about a mechanism that would allow such clients to use trust</div><di= +v>models closer to full validation.</div><div><br></div><div>The subject of= + this mail is a proposal for a complementary alternative to SPV</div><div>m= +odes, and which is in the spirit of an existing default, `assumevalid`. It = +may</div><div>help modest clients transact under a security model that clos= +ely resembles</div><div>full validation within minutes instead of hours or = +days.</div><div><br></div><div># assumeutxo</div><div><br></div><div>The ba= +sic idea is to allow nodes to initialize using a serialized version of the<= +/div><div>UTXO set rendered by another node at some predetermined height. T= +he</div><div>initializing node syncs the headers chain from the network, th= +en obtains and</div><div>loads one of these UTXO snapshots (i.e. a serializ= +ed version of the UTXO set</div><div>bundled with the block header indicati= +ng its "base" and some other metadata).</div><div><br></div><div>= +Based upon the snapshot, the node is able to quickly reconstruct its chains= +tate,</div><div>and compares a hash of the resulting UTXO set to a preordai= +ned hash hard-coded</div><div>in the software a la assumevalid. This all ta= +kes ~23 minutes, not accounting for</div><div>download of the 3.2GB snapsho= +t[2].=C2=A0</div><div><br></div><div>The node then syncs to the network tip= + and afterwards begins a simultaneous</div><div>background validation (i.e.= +, a conventional IBD) up to the base height of the</div><div>snapshot in or= +der to achieve full validation. Crucially, even while the</div><div>backgro= +und validation is happening the node can validate incoming blocks and</div>= +<div>transact with the benefit of the full (assumed-valid) UTXO set.</div><= +div><br></div><div>Snapshots could be obtained from multiple separate peers= + in the same manner as</div><div>block download, but I haven't put much= + thought into this. In concept it doesn't</div><div>matter too much whe= +re the snapshots come from since their validity is</div><div>determined via= + content hash.</div><div><br></div><div># Security</div><div><br></div><div= +>Obviously there are some security implications due consideration. While th= +is</div><div>proposal is in the spirit of assumevalid, practical attacks ma= +y become easier.</div><div>Under assumevalid, a user can be tricked into tr= +ansacting under a false history</div><div>if an attacker convinces them to = +start bitcoind with a malicious `-assumevalid`</div><div>parameter, sybils = +their node, and then feeds them a bogus chain encompassing</div><div>all of= + the hard-coded checkpoints[3].=C2=A0</div><div><br></div><div>The same att= +ack is made easier in assumeutxo because, unlike in assumevalid,</div><div>= +the attacker need not construct a valid PoW chain to get the victim's n= +ode into</div><div>a false state; they simply need to get the user to accep= +t a bad `-assumeutxo`</div><div>parameter and then supply them an easily ma= +de UTXO snapshot containing, say, a</div><div>false coin assignment.</div><= +div><br></div><div>For this reason, I recommend that if we were to implemen= +t assumeutxo, we not</div><div>allow its specification via commandline argu= +ment[4].</div><div><br></div><div>Beyond this risk, I can't think of ma= +terial differences in security relative to</div><div>assumevalid, though I = +appeal to the list for help with this.</div><div><br></div><div># More full= +y validating clients</div><div><br></div><div>A particularly exciting use-c= +ase for assumeutxo is the possibility of mobile</div><div>devices functioni= +ng as fully validating nodes with access to the complete UTXO</div><div>set= + (as an alternative to SPV models). The total resource burden needed to sta= +rt a node</div><div>from scratch based on a snapshot is, at time of writing= +, a ~(3.2GB</div><div>+ blocks_to_tip * 4MB) download and a few minutes of = +processing time, which sounds</div><div>manageable for many mobile devices = +currently in use.</div><div>=C2=A0=C2=A0</div><div>A mobile user could init= +ialize an assumed-valid bitcoin node within an hour,</div><div>transact imm= +ediately, and complete a pruned full validation of their</div><div>assumed-= +valid chain over the next few days, perhaps only doing the background</div>= +<div>IBD when their device has access to suitable high-bandwidth connection= +s.</div><div><br></div><div>If we end up implementing an accumulator-based = +UTXO scaling design[5][6] down</div><div>the road, it's easy to imagine= + an analogous process that would allow very fast</div><div>startup using an= + accumulator of a few kilobytes in lieu of a multi-GB snapshot.</div><div><= +br></div><div>---</div><div><br></div><div>I've created a related issue= + at our Github repository here:</div><div>=C2=A0 <a href=3D"https://github.= +com/bitcoin/bitcoin/issues/15605" target=3D"_blank">https://github.com/bitc= +oin/bitcoin/issues/15605</a></div><div><br></div><div>and have submitted a = +draft implementation of snapshot usage via RPC here:</div><div>=C2=A0 <a hr= +ef=3D"https://github.com/bitcoin/bitcoin/pull/15606" target=3D"_blank">http= +s://github.com/bitcoin/bitcoin/pull/15606</a></div><div><br></div><div>I= +9;d like to discuss here whether this is a good fit for Bitcoin conceptuall= +y. Concrete</div><div>plans for deployment steps should be discussed in the= + Github issue, and after all=C2=A0</div><div>that my implementation may be = +reviewed as a sketch of the specific software</div><div>changes necessary.<= +/div><div><br></div><div>Regards,</div><div>James</div><div><br></div><div>= +<br></div><div>[0]: <a href=3D"https://bitcoincore.org/en/2017/03/08/releas= +e-0.14.0/#assumed-valid-blocks" target=3D"_blank">https://bitcoincore.org/e= +n/2017/03/08/release-0.14.0/#assumed-valid-blocks</a></div><div>[1]: <a hre= +f=3D"https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki" target= +=3D"_blank">https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki<= +/a></div><div>[2]: as tested at height 569895, on a 12 core Intel Xeon Silv= +er 4116 CPU @ 2.10GHz</div><div>[3]: <a href=3D"https://github.com/bitcoin/= +bitcoin/blob/84d0fdc/src/chainparams.cpp#L145-L161" target=3D"_blank">https= +://github.com/bitcoin/bitcoin/blob/84d0fdc/src/chainparams.cpp#L145-L161</a= +></div><div>[4]: Marco Falke is due credit for this point</div><div>[5]: ut= +reexo: <a href=3D"https://www.youtube.com/watch?v=3DedRun-6ubCc" target=3D"= +_blank">https://www.youtube.com/watch?v=3DedRun-6ubCc</a></div><div>[6]: Bo= +neh, Bunz, Fisch on accumulators: <a href=3D"https://eprint.iacr.org/2018/1= +188" target=3D"_blank">https://eprint.iacr.org/2018/1188</a></div><div><br>= +</div></div></div> +_______________________________________________<br> +bitcoin-dev mailing list<br> +<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">= +bitcoin-dev@lists.linuxfoundation.org</a><br> +<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = +rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail= +man/listinfo/bitcoin-dev</a><br> +</blockquote></div> + +--000000000000b665240585a842b2-- + |