From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <danny.thorpe@gmail.com> Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 2275198C for <bitcoin-dev@lists.linuxfoundation.org>; Mon, 17 Apr 2017 07:11:12 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-lf0-f48.google.com (mail-lf0-f48.google.com [209.85.215.48]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 97725F0 for <bitcoin-dev@lists.linuxfoundation.org>; Mon, 17 Apr 2017 07:11:10 +0000 (UTC) Received: by mail-lf0-f48.google.com with SMTP id 88so14655530lfr.0 for <bitcoin-dev@lists.linuxfoundation.org>; Mon, 17 Apr 2017 00:11:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=szG8TwH/AuVaO36vEupnualefkijGq7Ub+uzYGDfzIk=; b=FizBHgsqmbYgwmvzb4PMachnvhF0BOZnwiq/U3zxtQDNYxx+w9J0aRinxiVEeFCaNc obbP2ukEgZybsVuGUD+1a1BqpHSDtL6xAj+qFR1mAV44DuAwMyoyhnpcHa4r559sjDhT EO8bfuzYDASgIG9Q500sjt0mPlR1qihWpeKbrTDlpJ8U5vN+do92gq3dChqVZwif28cw eA5U/OjCz4UH2QRMGBfBKn5im27VNUJYFOnv4IZAYB/5h9T3ifNlk3wCeuTvKKVEmNGQ O9IbchM3dtGGT4kFQVzsL3kMEg6tfIBiuXnmUzveYB+MZMNejo74cHvxKdc1xIo+IH5U +3gA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=szG8TwH/AuVaO36vEupnualefkijGq7Ub+uzYGDfzIk=; b=IURbQwDiFmgLh0FQxAiZOIEFpf1wsjht59Q63AjNEc+s9uGfFKFpZbR5LIUvXgnaIi OzZzIFMBWAdhWmo2Mop2EWC6IfLua7bc1nudOVFtu8NzR/IpKFBrTgKslMesXD7IiBNB Zz1h2kkY7EB19q9B6RKmthx/novL4glJNh1DvyB3DGMeNnQnIfPkEYoedyS0NtgD6dt0 2+UewoMniE0o3LdlHtj2X0cJLJnXrCGj+6dMcWcKNrPr9CBAsI5yt3CqyDaZvnLCLkSj +DfGyR7p/dTixxI7VuBZdQv04rjVP9ogsUed0SIKXoyHVml7slMVI7Z59S6LmbRESkrK SziQ== X-Gm-Message-State: AN3rC/4VscAXSKOk2Bp2Ad3zX4TK5pLdcQHKQ5QI0tFarRv0VfXjKmdW g5G/+1xo4VpgdIN3FLj9Eq2A7b2agw== X-Received: by 10.25.26.69 with SMTP id a66mr2351907lfa.48.1492413068933; Mon, 17 Apr 2017 00:11:08 -0700 (PDT) MIME-Version: 1.0 Received: by 10.46.32.9 with HTTP; Mon, 17 Apr 2017 00:11:07 -0700 (PDT) Received: by 10.46.32.9 with HTTP; Mon, 17 Apr 2017 00:11:07 -0700 (PDT) In-Reply-To: <CAFVRnypbQQ-vsSLqv48cYaqTCty4R1DmFRqfAvxe4mAqyQNXxQ@mail.gmail.com> References: <CAFVRnypbQQ-vsSLqv48cYaqTCty4R1DmFRqfAvxe4mAqyQNXxQ@mail.gmail.com> From: Danny Thorpe <danny.thorpe@gmail.com> Date: Mon, 17 Apr 2017 00:11:07 -0700 Message-ID: <CAJN5wHW=p+q+DT9R=uheLxOjKBX=xcB+fOZR2KACgJO9SdXypw@mail.gmail.com> To: David Vorick <david.vorick@gmail.com> Content-Type: multipart/alternative; boundary=001a11472d54d4fea5054d577ef8 X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org> Subject: Re: [bitcoin-dev] Small Nodes: A Better Alternative to Pruned Nodes 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: Mon, 17 Apr 2017 07:11:12 -0000 --001a11472d54d4fea5054d577ef8 Content-Type: text/plain; charset=UTF-8 1TB HDD is now available for under $40 USD. How is the 100GB storage requirement preventing anyone from setting up full nodes? On Apr 16, 2017 11:55 PM, "David Vorick via bitcoin-dev" < bitcoin-dev@lists.linuxfoundation.org> wrote: > *Rationale:* > > A node that stores the full blockchain (I will use the term archival node) > requires over 100GB of disk space, which I believe is one of the most > significant barriers to more people running full nodes. And I believe the > ecosystem would benefit substantially if more users were running full nodes. > > The best alternative today to storing the full blockchain is to run a > pruned node, which keeps only the UTXO set and throws away already verified > blocks. The operator of the pruned node is able to enjoy the full security > benefits of a full node, but is essentially leeching the network, as they > performed a large download likely without contributing anything back. > > This puts more pressure on the archival nodes, as the archival nodes need > to pick up the slack and help new nodes bootstrap to the network. As the > pressure on archival nodes grows, fewer people will be able to actually run > archival nodes, and the situation will degrade. The situation would likely > become problematic quickly if bitcoin-core were to ship with the defaults > set to a pruned node. > > Even further, the people most likely to care about saving 100GB of disk > space are also the people least likely to care about some extra bandwidth > usage. For datacenter nodes, and for nodes doing lots of bandwidth, the > bandwidth is usually the biggest cost of running the node. For home users > however, as long as they stay under their bandwidth cap, the bandwidth is > actually free. Ideally, new nodes would be able to bootstrap from nodes > that do not have to pay for their bandwidth, instead of needing to rely on > a decreasing percentage of heavy-duty archival nodes. > > I have (perhaps incorrectly) identified disk space consumption as the most > significant factor in your average user choosing to run a pruned node or a > lite client instead of a full node. The average user is not typically too > worried about bandwidth, and is also not typically too worried about > initial blockchain download time. But the 100GB hit to your disk space can > be a huge psychological factor, especially if your hard drive only has > 500GB available in the first place, and 250+ GB is already consumed by > other files you have. > > I believe that improving the disk usage situation would greatly benefit > decentralization, especially if it could be done without putting pressure > on archival nodes. > > *Small Nodes Proposal:* > > I propose an alternative to the pruned node that does not put undue > pressure on archival nodes, and would be acceptable and non-risky to ship > as a default in bitcoin-core. For lack of a better name, I'll call this new > type of node a 'small node'. The intention is that bitcoin-core would > eventually ship 'small nodes' by default, such that the expected amount of > disk consumption drops from today's 100+ GB to less than 30 GB. > > My alternative proposal has the following properties: > > + Full nodes only need to store ~20% of the blockchain > + With very high probability, a new node will be able to recover the > entire blockchain by connecting to 6 random small node peers. > + An attacker that can eliminate a chosen+ 95% of the full nodes running > today will be unable to prevent new nodes from downloading the full > blockchain, even if the attacker is also able to eliminate all archival > nodes. (assuming all nodes today were small nodes instead of archival nodes) > > Method: > > A small node will pick an index [5, 256). This index is that node's > permanent index. When storing a block, instead of storing the full block, > the node will use Reed-Solomon coding to erasure code the block using a > 5-of-256 scheme. The result will be 256 pieces that are 20% of the size of > the block each. The node picks the piece that corresponds to its index, and > stores that instead. (Indexes 0-4 are reserved for archival nodes - > explained later) > > The node is now storing a fragment of every block. Alone, this fragment > cannot be used to recover any piece of the blockchain. However, when paired > with any 5 unique fragments (fragments of the same index will not be > unique), the full block can be recovered. > > Nodes can optionally store more than 1 fragment each. At 5 fragments, the > node becomes a full archival node, and the chosen indexes should be 0-4. > This is advantageous for the archival node as the encoded data for the > first 5 indexes will actually be identical to the block itself - there is > no computational overhead for selecting the first indexes. There is also no > need to choose random indexes, because the full block can be recovered no > matter which indexes are chosen. > > When connecting to new peers, the indexes of each peer needs to be known. > Once peers totaling 5 unique indexes are discovered, blockchain download > can begin. Connecting to just 5 small node peers provides a >95% chance of > getting 5 uniques, with exponentially improving odds of success as you > connect to more peers. Connecting to a single archive node guarantees that > any gaps can be filled. > > A good encoder should be able to turn a block into a 5-of-256 piece set in > under 10 milliseconds using a single core on a standard consumer desktop. > This should not slow down initial blockchain download substantially, though > the overhead is more than a rounding error. > > *DoS Prevention:* > > A malicious node may provide garbage data instead of the actual piece. > Given just the garbage data and 4 other correct pieces, it is impossible > (best I know anyway) to tell which piece is the garbage piece. > > One option in this case would be to seek out an archival node that could > verify the correctness of the pieces, and identify the malicious node. > > Another option would be to have the small nodes store a cryptographic > checksum of each piece. Obtaining the cryptographic checksum for all 256 > pieces would incur a nontrivial amount of hashing (post segwit, as much as > 100MB of extra hashing per block), and would require an additional ~4kb of > storage per block. The hashing overhead here may be prohibitive. > > Another solution would be to find additional pieces and brute-force > combinations of 5 until a working combination was discovered. Though this > sounds nasty, it should take less than five seconds of computation to find > the working combination given 5 correct pieces and 2 incorrect pieces. This > computation only needs to be performed once to identify the malicious peers. > > I also believe that alternative erasure coding schemes exist which > actually are able to identify the bad pieces given sufficient good pieces, > however I don't know if they have the same computational performance as the > best Reed-Solomon coding implementations. > > *Deployment:* > > Small nodes are completely useless unless the critical mass of 5 pieces > can be obtained. The first version that supports small node block downloads > should default everyone to an archival node (meaning indexes 0-4 are used) > > Once there are enough small-node-enabled archive nodes, the default can be > switched so that nodes only have a single index by default. In the first > few days, when there are only a few small nodes, the previously-deployed > archival nodes can help fill in the gaps, and the small nodes can be useful > for blockchain download right away. > > ---------------------------------- > > This represents a non-trivial amount of code, but I believe that the > result would be a non-trivial increase in the percentage of users running > full nodes, and a healthier overall network. > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --001a11472d54d4fea5054d577ef8 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <div dir=3D"auto">1TB HDD is now available for under <span class=3D"money">= $40</span>=C2=A0USD.=C2=A0 How is the 100GB storage requirement preventing = anyone from setting up full nodes?</div><div class=3D"gmail_extra"><br><div= class=3D"gmail_quote">On Apr 16, 2017 11:55 PM, "David Vorick via bit= coin-dev" <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org"= >bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br type=3D"attributio= n"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left= :1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div><div><b>Rationale:<= /b><br></div><div><br>A node that stores the full blockchain (I will use th= e term archival node) requires over 100GB of disk space, which I believe is= one of the most significant barriers to more people running full nodes. An= d I believe the ecosystem would benefit substantially if more users were ru= nning full nodes.<br><br></div>The best alternative today to storing the fu= ll blockchain is to run a pruned node, which keeps only the UTXO set and th= rows away already verified blocks. The operator of the pruned node is able = to enjoy the full security benefits of a full node, but is essentially leec= hing the network, as they performed a large download likely without contrib= uting anything back.<br><br></div><div>This puts more pressure on the archi= val nodes, as the archival nodes need to pick up the slack and help new nod= es bootstrap to the network. As the pressure on archival nodes grows, fewer= people will be able to actually run archival nodes, and the situation will= degrade. The situation would likely become problematic quickly if bitcoin-= core were to ship with the defaults set to a pruned node.<br><br></div><div= >Even further, the people most likely to care about saving 100GB of disk sp= ace are also the people least likely to care about some extra bandwidth usa= ge. For datacenter nodes, and for nodes doing lots of bandwidth, the bandwi= dth is usually the biggest cost of running the node. For home users however= , as long as they stay under their bandwidth cap, the bandwidth is actually= free. Ideally, new nodes would be able to bootstrap from nodes that do not= have to pay for their bandwidth, instead of needing to rely on a decreasin= g percentage of heavy-duty archival nodes.<br><br></div><div>I have (perhap= s incorrectly) identified disk space consumption as the most significant fa= ctor in your average user choosing to run a pruned node or a lite client in= stead of a full node. The average user is not typically too worried about b= andwidth, and is also not typically too worried about initial blockchain do= wnload time. But the 100GB hit to your disk space can be a huge psychologic= al factor, especially if your hard drive only has 500GB available in the fi= rst place, and 250+ GB is already consumed by other files you have.<br><br>= </div><div>I believe that improving the disk usage situation would greatly = benefit decentralization, especially if it could be done without putting pr= essure on archival nodes.<br></div><div><br></div><div><b>Small Nodes Propo= sal:</b><br><br></div><div>I propose an alternative to the pruned node that= does not put undue pressure on archival nodes, and would be acceptable and= non-risky to ship as a default in bitcoin-core. For lack of a better name,= I'll call this new type of node a 'small node'. The intention = is that bitcoin-core would eventually ship 'small nodes' by default= , such that the expected amount of disk consumption drops from today's = 100+ GB to less than 30 GB.<br><br></div><div>My alternative proposal has t= he following properties:<br><br></div><div>+ Full nodes only need to store = ~20% of the blockchain<br></div><div>+ With very high probability, a new no= de will be able to recover the entire blockchain by connecting to 6 random = small node peers.<br></div><div>+ An attacker that can eliminate a chosen+ = 95% of the full nodes running today will be unable to prevent new nodes fro= m downloading the full blockchain, even if the attacker is also able to eli= minate all archival nodes. (assuming all nodes today were small nodes inste= ad of archival nodes)<br><br></div><div>Method:<br><br></div><div>A small n= ode will pick an index [5, 256). This index is that node's permanent in= dex. When storing a block, instead of storing the full block, the node will= use Reed-Solomon coding to erasure code the block using a 5-of-256 scheme.= The result will be 256 pieces that are 20% of the size of the block each. = The node picks the piece that corresponds to its index, and stores that ins= tead. (Indexes 0-4 are reserved for archival nodes - explained later)<br><b= r></div><div>The node is now storing a fragment of every block. Alone, this= fragment cannot be used to recover any piece of the blockchain. However, w= hen paired with any 5 unique fragments (fragments of the same index will no= t be unique), the full block can be recovered.<br><br></div><div>Nodes can = optionally store more than 1 fragment each. At 5 fragments, the node become= s a full archival node, and the chosen indexes should be 0-4. This is advan= tageous for the archival node as the encoded data for the first 5 indexes w= ill actually be identical to the block itself - there is no computational o= verhead for selecting the first indexes. There is also no need to choose ra= ndom indexes, because the full block can be recovered no matter which index= es are chosen.<br><br></div><div>When connecting to new peers, the indexes = of each peer needs to be known. Once peers totaling 5 unique indexes are di= scovered, blockchain download can begin. Connecting to just 5 small node pe= ers provides a >95% chance of getting 5 uniques, with exponentially impr= oving odds of success as you connect to more peers. Connecting to a single = archive node guarantees that any gaps can be filled.<br><br></div><div>A go= od encoder should be able to turn a block into a 5-of-256 piece set in unde= r 10 milliseconds using a single core on a standard consumer desktop. This = should not slow down initial blockchain download substantially, though the = overhead is more than a rounding error.<br></div><div><br></div><div><b>DoS= Prevention:</b><br><br></div><div>A malicious node may provide garbage dat= a instead of the actual piece. Given just the garbage data and 4 other corr= ect pieces, it is impossible (best I know anyway) to tell which piece is th= e garbage piece.<br><br></div><div>One option in this case would be to seek= out an archival node that could verify the correctness of the pieces, and = identify the malicious node.<br><br></div><div>Another option would be to h= ave the small nodes store a cryptographic checksum of each piece. Obtaining= the cryptographic checksum for all 256 pieces would incur a nontrivial amo= unt of hashing (post segwit, as much as 100MB of extra hashing per block), = and would require an additional ~4kb of storage per block. The hashing over= head here may be prohibitive.<br><br></div><div>Another solution would be t= o find additional pieces and brute-force combinations of 5 until a working = combination was discovered. Though this sounds nasty, it should take less t= han five seconds of computation to find the working combination given 5 cor= rect pieces and 2 incorrect pieces. This computation only needs to be perfo= rmed once to identify the malicious peers.<br><br></div><div>I also believe= that alternative erasure coding schemes exist which actually are able to i= dentify the bad pieces given sufficient good pieces, however I don't kn= ow if they have the same computational performance as the best Reed-Solomon= coding implementations.<br></div><br><div><b>Deployment:</b><br><br></div>= <div>Small nodes are completely useless unless the critical mass of 5 piece= s can be obtained. The first version that supports small node block downloa= ds should default everyone to an archival node (meaning indexes 0-4 are use= d)<br><br></div><div>Once there are enough small-node-enabled archive nodes= , the default can be switched so that nodes only have a single index by def= ault. In the first few days, when there are only a few small nodes, the pre= viously-deployed archival nodes can help fill in the gaps, and the small no= des can be useful for blockchain download right away.<br><br>--------------= ----------------<wbr>----<br><br></div><div>This represents a non-trivial a= mount of code, but I believe that the result would be a non-trivial increas= e in the percentage of users running full nodes, and a healthier overall ne= twork.<br></div></div> <br>______________________________<wbr>_________________<br> bitcoin-dev mailing list<br> <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.= <wbr>linuxfoundation.org</a><br> <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org= /mailman/listinfo/bitcoin-<wbr>dev</a><br> <br></blockquote></div></div> --001a11472d54d4fea5054d577ef8--