Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 37BF7EEA for ; Thu, 10 Dec 2015 04:14:20 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-oi0-f52.google.com (mail-oi0-f52.google.com [209.85.218.52]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A9861135 for ; Thu, 10 Dec 2015 04:14:18 +0000 (UTC) Received: by oies6 with SMTP id s6so38887687oie.1 for ; Wed, 09 Dec 2015 20:14:18 -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=9jxT0aydGQPl2eWNf/bg1wFqwzYKJa8kZnr8VbHhy2E=; b=JkNn7WhZe3HyUUL1IdxNiHtFMARWjC3y9Fvh9xgCHaLeESy8FHbFEczroPR0dZ5GbP 408X5TNspCIHIFa0LsgIofFmblMdvk+gfzYYt0cNWMWZwJH5/klsgLGkNjOBH1fUZR0f WI9oW68QnpHkmSjjIanemDPnGzvgnpQ8Bwm90w9kNO7lBC1+LTqYJtRC8/saUQ4mMfzw /Lzlk6i92wgqD68h7Ajb8VZoXJTwZ+RoATfwX0JgXj3RHu/z6tE0P8v2/uO1hPO4jSie mblZxR6tDSf94uiZSIr0xByCj7RwLhbBorMDe0ODy9eNLxX/cASRadPSNT1hqUVCdJ1W Se8w== MIME-Version: 1.0 X-Received: by 10.202.222.193 with SMTP id v184mr7316305oig.15.1449720858046; Wed, 09 Dec 2015 20:14:18 -0800 (PST) Sender: dscotese@gmail.com Received: by 10.60.15.169 with HTTP; Wed, 9 Dec 2015 20:14:17 -0800 (PST) In-Reply-To: References: Date: Wed, 9 Dec 2015 20:14:17 -0800 X-Google-Sender-Auth: -BWqCU1H-A6FfLKyopeG3odwZSQ Message-ID: From: Dave Scotese To: Andrew Content-Type: multipart/alternative; boundary=001a113d54d4c4799d05268370c8 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:14:20 -0000 --001a113d54d4c4799d05268370c8 Content-Type: text/plain; charset=UTF-8 Edit: "... as well as those blocks with hashes for which the last B bits match any of the next N bit patterns where *N is largest* integer for which the claimed output is not *greater* than (subsidy+fees)*(N/(2^B)). On Wed, Dec 9, 2015 at 8:08 PM, Dave Scotese wrote: > 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 > -- 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 --001a113d54d4c4799d05268370c8 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Edit:
"... as well as those blocks with hashes for= which the last B bits match any of the next N bit patterns where N is largest integer for which=20 the claimed output is not greater than (subsidy+fees)*(N/(2^B)).

On Wed, Dec 9, = 2015 at 8:08 PM, Dave Scotese <dscotese@litmocracy.com> wrote:
=
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 "co= in," then every transaction may have to use all the other partitions t= o 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 fr= action of what it is now.=C2=A0 We would want the current situation to be i= dentical to one in which all the participants are handling all the partitio= ns.=C2=A0 So how can we break up the work so that any participant can handl= e whatever fraction of the work he or she wants?=C2=A0 One idea is to use t= he last bits of the address that will receive the subsidy and fees.=C2=A0 Y= ou 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 t= he same bits.

This solution is broadcast in the hope that othe= rs will start attempting to validate that same block on their own partition= . If they are mining the same partition, they simply change their subsidy a= ddress to work on a different partition.=C2=A0 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 frac= tion of the reward-plus-subsidy.=C2=A0 In this way, several miners contribu= te 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 eigh= t 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 gen= eration transaction, where the bit-pattern of the last byte of the public k= ey identifies the first partition, and the proportion of the total reward f= or the block (51/256) indicates how many partitions a solution will cover.<= br>
Suppose that the last byte of the subsidy address is 0xF0.=C2=A0 Thi= s 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 abstr= acted out to a certain level.=C2=A0 Perhaps a miner can indicate how many b= its B the partitioning should use in the CoinBase. The blocks for which a p= artition miner claims responsibility are all those with a bit pattern of le= ngth B at the end of their hash matching the the bits at the end of the fir= st 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 p= atterns where for the largest integer N for which the claimed output is not= less than (subsidy+fees)*(N/(2^B)).

If you on= ly store and validate against one partition, and that partition has a solut= ion already, then you would start working on the next block (once you'v= e validated the current one against your subset of the blockchain).=C2=A0 Y= ou 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 (assu= ming the current block is valid on all partitions).

It seems that a miner who covers only one partition will be at a serious d= isadvantage, but as the rate of incoming transactions increases, the fracti= on of time he must spend validating (being about half of all other miners w= ho cover just one more partition) makes up for this disadvantage somewhat.= =C2=A0 He is a "spry" miner and therefore wins more rewards durin= g times of very dense transaction volume.=C2=A0 If we wish to encourage min= ers to work on smaller partitions, we can provide a difficulty break for sm= aller fractions of the work.=C2=A0 In fact, the difficulty can be adjusted = down for the first solution, and then slowly back up to full for the last p= artition(s).

This proposal has the added benefit of encouragin= g the assembly of blocks by miners who work on single partitions to get the= m out there with a one-partition solution.

On Wed, Dec 9, 20= 15 at 2:35 PM, Andrew via bitcoin-dev <bitcoin-dev@lis= ts.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, "Loi Luu via = bitcoin-dev" <bitcoin-dev@lists.linuxfoundation.org> wrote:<= br type=3D"attribution">
Dear Akiva,

Its Loi Luu, one of the authors of the SCP protocol (http://eprint.iacr.org/2015/1168= .pdf=C2=A0).
<= span>

Before SCP, we had been t= hinking hard about how to do sharding efficiently without degrading any sec= urity guarantee. A simple solution which splits the coins, or TXs in to sev= eral partitions will just not work. You have to answer more questions to ha= ve a good solutions. For example, I wonder in your proposal, if a transacti= on spends a "coin" that ends in "1" and creates a new c= oin that ends in "1", which partition should process the transact= ion? What is the prior data needed to validate that kind of TXs?

The problem with other propo= sals, and probably yours as well,=C2=A0=C2=A0that we see is that the amount= of data that you need to broadcast immediately to the network increases li= nearly 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=C2=A0bandwidth=C2=A0used, and only = broadcast only a=C2=A0minimal=C2=A0data to the network.

Clearly we are able to localize the b= andwidth used with our SCP protocol. The cost is that now=C2=A0recipients= =C2=A0need to=C2=A0=C2= =A0themselves=C2=A0veri= fy whether a transaction is double spending. However, we think that=C2=A0it= is=C2=A0a reasonable tradeoff, given the potential scalability that SCP ca= n provides.

<= div>
Thanks,
Loi Luu.
=

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 pro= vide some work at no charge to prove my value. Do you need a techie?=C2=A0 =
I own Litmocrac= y and Meme Raci= ng (in alpha).
I'm the webmaster for The Voluntaryist which now accepts Bitc= oin.
I also code for The Dollar Vigilante.
"He ought to find it more profitab= le to play by the rules" - Satoshi Nakamoto



--
I like to provide some work at no charge to prove = my value. Do you need a techie?=C2=A0
I own Litmocracy and Meme Racing (in alpha).
I'm the we= bmaster for The V= oluntaryist which now accepts Bitcoin.
I also code for The Dollar Vigilante.
&= quot;He ought to find it more profitable to play by the rules" - Satos= hi Nakamoto
--001a113d54d4c4799d05268370c8--