Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id D56E1DC0 for ; Thu, 10 Dec 2015 04:08:06 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-oi0-f54.google.com (mail-oi0-f54.google.com [209.85.218.54]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id EFAA3135 for ; Thu, 10 Dec 2015 04:08:04 +0000 (UTC) Received: by oige206 with SMTP id e206so38435374oig.2 for ; Wed, 09 Dec 2015 20:08:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=+OLi+Zj3/9hnEwAlJeyEqwIbtnwUpSmCNzSsL/nplN4=; b=aLrMGlHc/R9nyQatimuJlJzz83JCuOUlBSkxs2nLk2drIwNOxLi0rjF54ZRaLx2eAZ sr9vHo6uN4OYF5D+cqtZFq7uDecDiwztg2zZepBwWwn3QnBlDHgeWf9/hEn19bClng5B B92AGul0QmJQC8isMzaY8BUAoR6AHtOD72cgZf8jbg4Rrvlgcu3aSAtqoAm1At9SdYgz SJRK6wHwbWUMZG6XRBPpC3l4FT5CR6OLIpS7EziToucGuhnsoS/hr4EzYilv+QF8L/Am cQfWV9kBRrbeSgznxpbOD6RyulNtjFyN29NqJQb7JjmlsQUtU6WDwT8FaH/dLixD0DHr QtyA== MIME-Version: 1.0 X-Received: by 10.202.227.199 with SMTP id a190mr6840130oih.35.1449720484125; Wed, 09 Dec 2015 20:08:04 -0800 (PST) Sender: dscotese@gmail.com Received: by 10.60.15.169 with HTTP; Wed, 9 Dec 2015 20:08:04 -0800 (PST) In-Reply-To: References: Date: Wed, 9 Dec 2015 20:08:04 -0800 X-Google-Sender-Auth: OkMXx79arD8eQ2WQAKrmki4fAAU Message-ID: From: Dave Scotese To: Andrew Content-Type: multipart/alternative; boundary=001a11407c8c7ae16a0526835a43 X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,FREEMAIL_FROM,HTML_MESSAGE,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 Cc: Bitcoin Dev Subject: Re: [bitcoin-dev] Scaling by Partitioning 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: Thu, 10 Dec 2015 04:08:06 -0000 --001a11407c8c7ae16a0526835a43 Content-Type: text/plain; charset=UTF-8 If we partition the work using bits from the TxID (once it is no longer malleable) or even bits from whatever definition we use for "coin," then every transaction may have to use all the other partitions to verify that the incoming coin is good. If all partitions are involved in validating and storing every transaction, then we may be doing more work in total, but any one node will only have to do (and store) a fraction of what it is now. We would want the current situation to be identical to one in which all the participants are handling all the partitions. So how can we break up the work so that any participant can handle whatever fraction of the work he or she wants? One idea is to use the last bits of the address that will receive the subsidy and fees. You solve the block for your partition by determining that all transactions in the block are valid against the subset of blocks whose hashes end with the same bits. This solution is broadcast in the hope that others will start attempting to validate that same block on their own partition. If they are mining the same partition, they simply change their subsidy address to work on a different partition. Each time a new-but-not-last partition is solved, everyone working on the block adds the new solver's output address to their generation transaction with the appropriate fraction of the reward-plus-subsidy. In this way, several miners contribute to the solution of a single block and need only store those blocks that match the partitions they want to work on. Suppose we use eight bits so that there are 256 partitions and a miner wishes to do about 1/5 of the work. That would be 51 partitions. This is signaled in the generation transaction, where the bit-pattern of the last byte of the public key identifies the first partition, and the proportion of the total reward for the block (51/256) indicates how many partitions a solution will cover. Suppose that the last byte of the subsidy address is 0xF0. This means there are only 16 partitions left, so we define partition selection to wrap around. This 51/256 miner must cover partitions 0xF0 - 0xFF and 0x00 - 0x23. In this way, all mining to date has covered all partitions. The number of bits to be used might be able to be abstracted out to a certain level. Perhaps a miner can indicate how many bits B the partitioning should use in the CoinBase. The blocks for which a partition miner claims responsibility are all those with a bit pattern of length B at the end of their hash matching the the bits at the end of the first output's public key in the generation transaction, as well as those blocks with hashes for which the last B bits match any of the next N bit patterns where for the largest integer N for which the claimed output is not less than (subsidy+fees)*(N/(2^B)). If you only store and validate against one partition, and that partition has a solution already, then you would start working on the next block (once you've validated the current one against your subset of the blockchain). You could even broadcast a solution for that next block before the previous block is fully solved, thus claiming a piece of the next block reward (assuming the current block is valid on all partitions). It seems that a miner who covers only one partition will be at a serious disadvantage, but as the rate of incoming transactions increases, the fraction of time he must spend validating (being about half of all other miners who cover just one more partition) makes up for this disadvantage somewhat. He is a "spry" miner and therefore wins more rewards during times of very dense transaction volume. If we wish to encourage miners to work on smaller partitions, we can provide a difficulty break for smaller fractions of the work. In fact, the difficulty can be adjusted down for the first solution, and then slowly back up to full for the last partition(s). This proposal has the added benefit of encouraging the assembly of blocks by miners who work on single partitions to get them out there with a one-partition solution. On Wed, Dec 9, 2015 at 2:35 PM, Andrew via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Hi Akiva > > I sketched out a similar proposal here: > https://bitcointalk.org/index.php?topic=1083345.0 > > It's good to see people talking about this :). I'm not quite convinced > with segregated witness, as it might mess up some things, but will take a > closer look. > On Dec 9, 2015 7:32 AM, "Loi Luu via bitcoin-dev" < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> Dear Akiva, >> >> Its Loi Luu, one of the authors of the SCP protocol ( >> http://eprint.iacr.org/2015/1168.pdf ). >> >> Before SCP, we had been thinking hard about how to do sharding >> efficiently without degrading any security guarantee. A simple solution >> which splits the coins, or TXs in to several partitions will just not work. >> You have to answer more questions to have a good solutions. For example, I >> wonder in your proposal, if a transaction spends a "coin" that ends in "1" >> and creates a new coin that ends in "1", which partition should process the >> transaction? What is the prior data needed to validate that kind of TXs? >> >> The problem with other proposals, and probably yours as well, that we >> see is that the amount of data that you need to broadcast immediately to >> the network increases linearly with the number of TXs that the network can >> process. Thus, sharding does not bring any advantage than simply using >> other techniques to publish more blocks in one epoch (like Bitcoin-NG, >> Ghost). The whole point of using sharding/ partition is to localize >> the bandwidth used, and only broadcast only a minimal data to the network. >> >> Clearly we are able to localize the bandwidth used with our SCP protocol. >> The cost is that now recipients need to themselves verify whether a >> transaction is double spending. However, we think that it is a reasonable >> tradeoff, given the potential scalability that SCP can provides. >> >> Thanks, >> Loi Luu. >> >> On Wed, Dec 9, 2015 at 12:27 AM, Akiva Lichtner via bitcoin-dev < >> bitcoin-dev@lists.linuxfoundation.org> wrote: >> >>> Hello, >>> >>> I am seeking some expert feedback on an idea for scaling Bitcoin. As a >>> brief introduction: I work in the payment industry and I have twenty years' >>> experience in development. I have some experience with process groups and >>> ordering protocols too. I think I understand Satoshi's paper but I admit I >>> have not read the source code. >>> >>> The idea is to run more than one simultaneous chain, each chain >>> defeating double spending on only part of the coin. The coin would be >>> partitioned by radix (or modulus, not sure what to call it.) For example in >>> order to multiply throughput by a factor of ten you could run ten parallel >>> chains, one would work on coin that ends in "0", one on coin that ends in >>> "1", and so on up to "9". >>> >>> The number of chains could increase automatically over time based on the >>> moving average of transaction volume. >>> >>> Blocks would have to contain the number of the partition they belong to, >>> and miners would have to round-robin through partitions so that an attacker >>> would not have an unfair advantage working on just one partition. >>> >>> I don't think there is much impact to miners, but clients would have to >>> send more than one message in order to spend money. Client messages will >>> need to enumerate coin using some sort of compression, to save space. This >>> seems okay to me since often in computing client software does have to >>> break things up in equal parts (e.g. memory pages, file system blocks,) and >>> the client software could hide the details. >>> >>> Best wishes for continued success to the project. >>> >>> Regards, >>> Akiva >>> >>> P.S. I found a funny anagram for SATOSHI NAKAMOTO: "NSA IS OOOK AT MATH" >>> >>> >>> _______________________________________________ >>> bitcoin-dev mailing list >>> bitcoin-dev@lists.linuxfoundation.org >>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>> >>> >> >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> >> > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > -- I like to provide some work at no charge to prove my value. Do you need a techie? I own Litmocracy and Meme Racing (in alpha). I'm the webmaster for The Voluntaryist which now accepts Bitcoin. I also code for The Dollar Vigilante . "He ought to find it more profitable to play by the rules" - Satoshi Nakamoto --001a11407c8c7ae16a0526835a43 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
If we partition the work using bi= ts from the TxID (once it is no longer malleable) or even bits from whateve= r definition we use for "coin," then every transaction may have t= o use all the other partitions to verify that the incoming coin is good.
If all partitions are involved in validating and storing every t= ransaction, then we may be doing more work in total, but any one node will = only have to do (and store) a fraction of what it is now.=C2=A0 We would wa= nt the current situation to be identical to one in which all the participan= ts are handling all the partitions.=C2=A0 So how can we break up the work s= o that any participant can handle whatever fraction of the work he or she w= ants?=C2=A0 One idea is to use the last bits of the address that will recei= ve the subsidy and fees.=C2=A0 You solve the block for your partition by de= termining that all transactions in the block are valid against the subset o= f blocks whose hashes end with the same bits.

This solution is= broadcast in the hope that others will start attempting to validate that s= ame block on their own partition. If they are mining the same partition, th= ey simply change their subsidy address to work on a different partition.=C2= =A0 Each time a new-but-not-last partition is solved, everyone working on t= he block adds the new solver's output address to their generation trans= action with the appropriate fraction of the reward-plus-subsidy.=C2=A0 In t= his way, several miners contribute to the solution of a single block and ne= ed only store those blocks that match the partitions they want to work on.<= br>
Suppose we use eight bits so that there are 256 partitions and= a miner wishes to do about 1/5 of the work. That would be 51 partitions.= =C2=A0 This is signaled in the generation transaction, where the bit-patter= n of the last byte of the public key identifies the first partition, and th= e proportion of the total reward for the block (51/256) indicates how many = partitions a solution will cover.

Suppose that the last byte of the = subsidy address is 0xF0.=C2=A0 This means there are only 16 partitions left= , so we define partition selection to wrap around.=C2=A0 This 51/256 miner = must cover partitions 0xF0 - 0xFF and 0x00 - 0x23. In this way, all mining = to date has covered all partitions.

The number of bits to= be used might be able to be abstracted out to a certain level.=C2=A0 Perha= ps a miner can indicate how many bits B the partitioning should use in the = CoinBase. The blocks for which a partition miner claims responsibility are = all those with a bit pattern of length B at the end of their hash matching = the the bits at the end of the first output's public key in the genera= tion transaction, as well as those blocks with hashes for which the last B = bits match any of the next N bit patterns where for the largest integer N f= or which the claimed output is not less than (subsidy+fees)*(N/(2^B)).
<= /div>

If you only store and validate against one partiti= on, and that partition has a solution already, then you would start working= on the next block (once you've validated the current one against your = subset of the blockchain).=C2=A0 You could even broadcast a solution for th= at next block before the previous block is fully solved, thus claiming a pi= ece of the next block reward (assuming the current block is valid on all pa= rtitions).

It seems that a miner who covers only on= e partition will be at a serious disadvantage, but as the rate of incoming = transactions increases, the fraction of time he must spend validating (bein= g about half of all other miners who cover just one more partition) makes u= p for this disadvantage somewhat.=C2=A0 He is a "spry" miner and = therefore wins more rewards during times of very dense transaction volume.= =C2=A0 If we wish to encourage miners to work on smaller partitions, we can= provide a difficulty break for smaller fractions of the work.=C2=A0 In fac= t, the difficulty can be adjusted down for the first solution, and then slo= wly back up to full for the last partition(s).

This proposal h= as the added benefit of encouraging the assembly of blocks by miners who wo= rk on single partitions to get them out there with a one-partition solution= .

On Wed= , Dec 9, 2015 at 2:35 PM, Andrew via bitcoin-dev <bitc= oin-dev@lists.linuxfoundation.org> wrote:

Hi Akiva

I sketched out a similar proposal here: https://bitco= intalk.org/index.php?topic=3D1083345.0

It's good to see people talking about this :). I'm n= ot quite convinced with segregated witness, as it might mess up some things= , but will take a closer look.

On Dec 9, 2015 7:32 AM, "L= oi Luu via bitcoin-dev" <bitcoin-dev@lists.linuxfoundation.org&= gt; wrote:
Dear Akiva,

Its Loi Luu, one of the authors of the SCP protoc= ol (http://eprint.iacr.or= g/2015/1168.pdf=C2=A0).

Bef= ore SCP, we had been thinking hard about how to do sharding efficiently wit= hout degrading any security guarantee. A simple solution which splits the c= oins, or TXs in to several partitions will just not work. You have to answe= r more questions to have a good solutions. For example, I wonder in your pr= oposal, if a transaction spends a "coin" that ends in "1&quo= t; and creates a new coin that ends in "1", which partition shoul= d process the transaction? What is the prior data needed to validate that k= ind of TXs?

The pr= oblem with other proposals, and probably yours as well,=C2=A0=C2=A0that we = see is that the amount of data that you need to broadcast immediately to th= e network increases linearly with the number of TXs that the network can pr= ocess. Thus, sharding does not bring any advantage than simply using other = techniques to publish more blocks in one epoch (like Bitcoin-NG, Ghost). Th= e whole point of using sharding/ partition is to localize the=C2=A0bandwidt= h=C2=A0used, and only broadcast only a=C2=A0minimal=C2=A0data to the networ= k.

Clearly we are = able to localize the bandwidth used with our SCP protocol. The cost is that= now=C2=A0recipients=C2=A0need to=C2=A0=C2=A0t= hemselves=C2=A0verify whether a transaction is double spending. However, we= think that=C2=A0it is=C2=A0a reasonable tradeoff, given the potential scal= ability that SCP can provides.

Thanks,
Loi Luu.
<= /span>

On Wed, Dec 9, 2015 at 12:27 AM, Akiva Licht= ner via bitcoin-dev <bitcoin-dev@lists.linuxfoundation= .org> wrote:
Hello,

I am seeking= some expert feedback on an idea for scaling Bitcoin. As a brief introducti= on: I work in the payment industry and I have twenty years' experience = in development. I have some experience with process groups and ordering pro= tocols too. I think I understand Satoshi's paper but I admit I have not= read the source code.

The idea is to run more than one simult= aneous chain, each chain defeating double spending on only part of the coin= . The coin would be partitioned by radix (or modulus, not sure what to call= it.) For example in order to multiply throughput by a factor of ten you co= uld run ten parallel chains, one would work on coin that ends in "0&qu= ot;, one on coin that ends in "1", and so on up to "9".=

The number of chains could increase automatically over time b= ased on the moving average of transaction volume.

Blocks would= have to contain the number of the partition they belong to, and miners wou= ld have to round-robin through partitions so that an attacker would not hav= e an unfair advantage working on just one partition.

I don't think there is much impact to miners, but clients would = have to send more than one message in order to spend money. Client messages= will need to enumerate coin using some sort of compression, to save space.= This seems okay to me since often in computing client software does have t= o break things up in equal parts (e.g. memory pages, file system blocks,) a= nd the client software could hide the details.

Best wishes for continued success to the project.

=
Regards,
Akiva

P.S. I found a funny anagram for= SATOSHI NAKAMOTO: "NSA IS OOOK AT MATH"


_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev



_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev


_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev




--
I like to provide some work at no charge to pr= ove my value. Do you need a techie?=C2=A0
I own Litmocracy and Meme Racing (in alpha).
I'm th= e webmaster for T= he Voluntaryist which now accepts Bitcoin.
I also code for The Dollar Vigilante= .
"He ought to find it more profitable to play by the rules" -= Satoshi Nakamoto
--001a11407c8c7ae16a0526835a43--