Return-Path: <loi.luuthe@gmail.com> Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 63D36CD4 for <bitcoin-dev@lists.linuxfoundation.org>; Wed, 9 Dec 2015 21:16:02 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-io0-f179.google.com (mail-io0-f179.google.com [209.85.223.179]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3F01FE5 for <bitcoin-dev@lists.linuxfoundation.org>; Wed, 9 Dec 2015 21:16:01 +0000 (UTC) Received: by iouu10 with SMTP id u10so75402127iou.0 for <bitcoin-dev@lists.linuxfoundation.org>; Wed, 09 Dec 2015 13:16:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=UCnx1cNiJ7NevUSO6rqoO8lL24nmWlBcf/CWL9Un+gw=; b=BoqWXYaUZQbHfZ/7eLMPtcuqz3KZxg9Ui1CSSb8UOK8k+ieR7HUKqXWUXW505nXhgs CCmzFYkfiO/sb+BX7nq7JOrarWF9tPcNtjeQHykonNE9YRUifeMo6WEWqj0/eCgT434z hUrnuYTeCwC6bN1/irJJLXNmTnyEDV/1IHbBGiYqzhSaRcrsnWo/XL+yby2miS1pqgs0 A/u8YxbEXZLWopSUHvEWH+oBocpRix1rf/CDOEuz6TGov13vgrHAYbxOmCJhmRQOZRwP L25AlGX9p5H21UuyY/1dZzRG40qvVK0W8w/Ju7jgJW4cNdhuveKVQyNuoYhJu5XpI1FC ODwQ== MIME-Version: 1.0 X-Received: by 10.107.169.202 with SMTP id f71mr7713421ioj.154.1449695760661; Wed, 09 Dec 2015 13:16:00 -0800 (PST) Received: by 10.64.252.168 with HTTP; Wed, 9 Dec 2015 13:16:00 -0800 (PST) Received: by 10.64.252.168 with HTTP; Wed, 9 Dec 2015 13:16:00 -0800 (PST) In-Reply-To: <CABCnA7VAO2XKLwd4axaYcttUHzhvXXEvYrwg7XDKH9nfo1k7RA@mail.gmail.com> References: <CABCnA7Wqz76m8qo5BYT41Z=hBH+fUfOc4xsFAGg=Niv7Jgkqsg@mail.gmail.com> <CAJmQggC1X5Lgt4xGoMtBZ_v3hC2GXcYaj2FngV2_7A=TDfSuEg@mail.gmail.com> <CABCnA7VAO2XKLwd4axaYcttUHzhvXXEvYrwg7XDKH9nfo1k7RA@mail.gmail.com> Date: Thu, 10 Dec 2015 05:16:00 +0800 Message-ID: <CAJmQggBfYyk3cPAL57NZ3ecPG_ZxffjPftc0-EkTzKagjodgNQ@mail.gmail.com> From: Loi Luu <loi.luuthe@gmail.com> To: Akiva Lichtner <akiva.lichtner@gmail.com> Content-Type: multipart/alternative; boundary=001a1142789ed8c55d05267d98a6 X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,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 X-Mailman-Approved-At: Wed, 09 Dec 2015 21:18:11 +0000 Cc: bitcoin-dev@lists.linuxfoundation.org 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 <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, 09 Dec 2015 21:16:02 -0000 --001a1142789ed8c55d05267d98a6 Content-Type: text/plain; charset=UTF-8 I guess the most basic question is how do you define a coin here? Thanks, Loi Luu On 10 Dec 2015 2:26 a.m., "Akiva Lichtner" <akiva.lichtner@gmail.com> wrote: > Thanks for giving serious consideration to my post. > > With regard to your question "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?", I would answer that only one > partition is involved. In other words, there are N independent block > chains that never cross paths. > > With regard to your question "what is the prior data needed to > validate that kind of TXs?" I do not understand what this means. If > you can dumb it down a bit that would be good because there could be > some interesting concern in this question. > > Since partitions are completely segregated, there is no need for a > node to work on multiple partitions simultaneously. For attacks to be > defeated a node needs to be able to work on multiple partitions in > turn, not at the same time. The reason is because if the computing > power of the good-faith nodes is unbalanced this gives attackers an > unfair advantage. > > On 12/9/15, 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 > >> > >> > > > --001a1142789ed8c55d05267d98a6 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <p dir=3D"ltr">I guess the most basic question is how do you define a coin = here?</p> <p dir=3D"ltr">Thanks,<br> Loi Luu</p> <div class=3D"gmail_quote">On 10 Dec 2015 2:26 a.m., "Akiva Lichtner&q= uot; <<a href=3D"mailto:akiva.lichtner@gmail.com">akiva.lichtner@gmail.c= om</a>> wrote:<br type=3D"attribution"><blockquote class=3D"gmail_quote"= style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Th= anks for giving serious consideration to my post.<br> <br> With regard to your question "if a transaction spends a "coin&quo= t; that<br> ends in "1" and creates a new coin that ends in "1", wh= ich partition<br> should process the transaction?", I would answer that only one<br> partition is involved. In other words, there are N independent block<br> chains that never cross paths.<br> <br> With regard to your question "what is the prior data needed to<br> validate that kind of TXs?" I do not understand what this means. If<br= > you can dumb it down a bit that would be good because there could be<br> some interesting concern in this question.<br> <br> Since partitions are completely segregated, there is no need for a<br> node to work on multiple partitions simultaneously. For attacks to be<br> defeated a node needs to be able to work on multiple partitions in<br> turn, not at the same time. The reason is because if the computing<br> power of the good-faith nodes is unbalanced this gives attackers an<br> unfair advantage.<br> <br> On 12/9/15, Loi Luu via bitcoin-dev<br> <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@li= sts.linuxfoundation.org</a>> wrote:<br> > Dear Akiva,<br> ><br> > Its Loi Luu, one of the authors of the SCP protocol (<br> > <a href=3D"http://eprint.iacr.org/2015/1168.pdf" rel=3D"noreferrer" ta= rget=3D"_blank">http://eprint.iacr.org/2015/1168.pdf</a> ).<br> ><br> > Before SCP, we had been thinking hard about how to do sharding efficie= ntly<br> > without degrading any security guarantee. A simple solution which spli= ts<br> > the coins, or TXs in to several partitions will just not work. You hav= e to<br> > answer more questions to have a good solutions. For example, I wonder = in<br> > your proposal, if a transaction spends a "coin" that ends in= "1" and<br> > creates a new coin that ends in "1", which partition should = process the<br> > transaction? What is the prior data needed to validate that kind of TX= s?<br> ><br> > The problem with other proposals, and probably yours as well,=C2=A0 th= at we see<br> > is that the amount of data that you need to broadcast immediately to t= he<br> > network increases linearly with the number of TXs that the network can= <br> > process. Thus, sharding does not bring any advantage than simply using= <br> > other techniques to publish more blocks in one epoch (like Bitcoin-NG,= <br> > Ghost). The whole point of using sharding/ partition is to localize<br= > > the bandwidth used, and only broadcast only a minimal data to the netw= ork.<br> ><br> > Clearly we are able to localize the bandwidth used with our SCP protoc= ol.<br> > The cost is that now recipients need to=C2=A0 themselves verify whethe= r a<br> > transaction is double spending. However, we think that it is a reasona= ble<br> > tradeoff, given the potential scalability that SCP can provides.<br> ><br> > Thanks,<br> > Loi Luu.<br> ><br> > On Wed, Dec 9, 2015 at 12:27 AM, Akiva Lichtner via bitcoin-dev <<b= r> > <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@l= ists.linuxfoundation.org</a>> wrote:<br> ><br> >> Hello,<br> >><br> >> I am seeking some expert feedback on an idea for scaling Bitcoin. = As a<br> >> brief introduction: I work in the payment industry and I have twen= ty<br> >> years'<br> >> experience in development. I have some experience with process gro= ups and<br> >> ordering protocols too. I think I understand Satoshi's paper b= ut I admit<br> >> I<br> >> have not read the source code.<br> >><br> >> The idea is to run more than one simultaneous chain, each chain de= feating<br> >> double spending on only part of the coin. The coin would be partit= ioned<br> >> by<br> >> radix (or modulus, not sure what to call it.) For example in order= to<br> >> multiply throughput by a factor of ten you could run ten parallel = chains,<br> >> one would work on coin that ends in "0", one on coin tha= t ends in "1",<br> >> and<br> >> so on up to "9".<br> >><br> >> The number of chains could increase automatically over time based = on the<br> >> moving average of transaction volume.<br> >><br> >> Blocks would have to contain the number of the partition they belo= ng to,<br> >> and miners would have to round-robin through partitions so that an= <br> >> attacker<br> >> would not have an unfair advantage working on just one partition.<= br> >><br> >> I don't think there is much impact to miners, but clients woul= d have to<br> >> send more than one message in order to spend money. Client message= s will<br> >> need to enumerate coin using some sort of compression, to save spa= ce.<br> >> This<br> >> seems okay to me since often in computing client software does hav= e to<br> >> break things up in equal parts (e.g. memory pages, file system blo= cks,)<br> >> and<br> >> the client software could hide the details.<br> >><br> >> Best wishes for continued success to the project.<br> >><br> >> Regards,<br> >> Akiva<br> >><br> >> P.S. I found a funny anagram for SATOSHI NAKAMOTO: "NSA IS OO= OK AT MATH"<br> >><br> >><br> >> _______________________________________________<br> >> bitcoin-dev mailing list<br> >> <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-d= ev@lists.linuxfoundation.org</a><br> >> <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitc= oin-dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation= .org/mailman/listinfo/bitcoin-dev</a><br> >><br> >><br> ><br> </blockquote></div> --001a1142789ed8c55d05267d98a6--