Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id C8F78273 for ; Sun, 28 Jun 2015 15:24:10 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ig0-f174.google.com (mail-ig0-f174.google.com [209.85.213.174]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 7E21BE9 for ; Sun, 28 Jun 2015 15:24:09 +0000 (UTC) Received: by igcur8 with SMTP id ur8so19978698igc.0 for ; Sun, 28 Jun 2015 08:24:09 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=dibkrJNuHqIK/oR/TVi0opU6ozuS1eigS7ql3Q3iKsI=; b=A7nXnA8VOU9L/QHcypNGM881LnapogMFT9TPVi2n6Ee83JnVRVSi3txcICFzBKyWtq Bw8wd6tvT+28AyxibPuxzlBKHdYZ9x8Lmr3eqC/t+O8iS+T8uipYMMI7AaCPDrtGbXUK eRGIWlQQe9plnNDEQrOk7ZHxg66gt11B40A5du1CtW7ia2GRf+mfaf+zpmZlhWkpmq1q EP5ONs5IFaMcjp+ZFpo1mMKH3wcdhdH/+Cv2jAbT0ji7sp2eMOAzepOE/uE2jmGeKl45 BSnnCgaLkaItYaBKDNhpljjMpTlIjO6MF0w9n4E/wth1npgSOH77a8qKFIC26N3RKTWB pZDg== X-Gm-Message-State: ALoCoQnpt3JZbtQCiYi/76ezFtJDtnF8EcD+drc+G9VlvNdGdmVEyua4wE+l1f91oJiRu2cmQ3h8 X-Received: by 10.50.142.9 with SMTP id rs9mr9611613igb.17.1435505048978; Sun, 28 Jun 2015 08:24:08 -0700 (PDT) MIME-Version: 1.0 Received: by 10.107.149.20 with HTTP; Sun, 28 Jun 2015 08:23:49 -0700 (PDT) X-Originating-IP: [50.0.37.37] In-Reply-To: <38C2E2A1-EB6C-48EB-8FA1-7FAA97B3E911@gmail.com> References: <1164261435450448@web14h.yandex.ru> <558F583C.1000500@gmail.com> <2A94BDF7-F265-4D36-B438-DC4F432E1C67@gmail.com> <558F8634.90904@gmail.com> <38C2E2A1-EB6C-48EB-8FA1-7FAA97B3E911@gmail.com> From: Mark Friedenbach Date: Sun, 28 Jun 2015 08:23:49 -0700 Message-ID: To: Eric Lombrozo Content-Type: multipart/alternative; boundary=001a11c2ff1c84a25105199590b1 X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,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@lists.linuxfoundation.org Subject: Re: [bitcoin-dev] Original Vision 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: Sun, 28 Jun 2015 15:24:10 -0000 --001a11c2ff1c84a25105199590b1 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable There's a couple of things that Patrick could have been referring to when he said "Fraud proofs need to be at least more efficient than full node validation. Currently they are not." One of the issues is that you cannot efficiently encode or validate a proof of a negative. If a transaction input is a double-spend, you can build a semi-reasonable sized proof of the prior spend (or very reasonably sized with block header commitments). However if a transaction spends an output which never existed in the first place, there is no reasonable way to assert this other than witnessing the entire block history, as a full node does. UTXO commitments are the nominal solution here. You commit the validator state in each block, and then you can prove things like a negative by referencing that state commitment. The trouble is this requires maintaining a hash tree commitment over validator state, which turns out to be insanely expensive. With the UTXO commitment scheme (the others are not better) that ends up requiring 15 - 22x more I/O during block validation. And I/O is presently a limiter to block validation speed. So if you thought 8MB was what bitcoin today could handle, and you also want this commitment scheme for fraud proofs, then you should be arguing for a block size limit decrease (to 500kB), not increase. On Sat, Jun 27, 2015 at 10:32 PM, Eric Lombrozo wrote= : > Just to clarify, SPV is fundamentally busted as it currently exists. I=E2= =80=99m > talking about potential optimizations for future protocols. > > - Eric Lombrozo > > > On Jun 27, 2015, at 10:29 PM, Patrick Strateman < > patrick.strateman@gmail.com> wrote: > > > > Fraud proofs need to be at least more efficient than full node > validation. > > > > Currently they are not. > > > > On 06/27/2015 09:54 PM, Eric Lombrozo wrote: > >> Fraud proofs actually don=E2=80=99t need to be made super efficient=E2= =80=A6but they do > need to be secure, of course. > >> > >> The trick is aligning incentives. In order for fraud proofs to be > widely available there needs to be a market for them - there must be a wa= y > to buy one (because producing one is not free). What makes such a scheme > actually practical is that very few of these fraud proofs ever need to > actually be executed - it=E2=80=99s a classical Nimzowischian case of the= threat > being much stronger than the execution. > >> > >> - Eric Lombrozo > >> > >>> On Jun 27, 2015, at 7:13 PM, Patrick Strateman < > patrick.strateman@gmail.com> wrote: > >>> > >>>> Further, it appears clear that the original author intended > >>> organizations operating full network nodes would provide connectivity > to > >>> light clients and these light clients would make up the majority of t= he > >>> user base. > >>> > >>> Satoshi also believed that fraud proofs would be widely available and > >>> practical. > >>> > >>> If fraud proofs were practical SPV client security would be much clos= er > >>> to full node security than it is today. > >>> > >>> Unfortunately no design for fraud proofs which is both efficient and > >>> secure has been proposed; much less implemented and deployed. > >>> > >>> In building a system as new and innovative as bitcoin certain things > >>> will be wrong. > >>> > >>> The perception that SPV clients could be made nearly as secure as ful= l > >>> nodes is one example of something that was wrong. > >>> > >>> On 06/27/2015 05:14 PM, Santino Napolitano wrote: > >>>> There is much heated debate going on right now and I know it can be > very stressful but I'd like to point out that it is really amazing how > passionately so many feel about this once very small project. Let's not > forget there is something really special going on here and we're all part > of it. > >>>> > >>>> The current debate has little to do with block size or hard-forks, > IMO. It's about the nature of Bitcoin and what it means to people and how > it will grow. I would like to take a moment to share my interpretation of > the original author's intent based on everything I could find and read fr= om > this person. This is not to say their original vision is paramount-- or > even that I got it completely correct but I think it might do us some goo= d > to think about. > >>>> > >>>> It seems as though the incentive conceived of for running a full > network node was that it would enable mining. The proceeds from mining (n= ew > coins and transaction fees) would be the reward and provide a reason to > continue operating these nodes. If fees are ever to be a sufficient rewar= d > and still allow for a practical and useful system the size of the blocks > must grow significantly as must the user base. I'm not sure that this is > really contested but I haven't exhaustively reviewed everyone's opinion s= o > please excuse me if I have marginalized you. If you do contest that I wou= ld > be interested in hearing it. > >>>> > >>>> Further, it appears clear that the original author intended > organizations operating full network nodes would provide connectivity to > light clients and these light clients would make up the majority of the > user base. This is completely consistent with current trends in Internet > consumption, e.g. tablets and phones are becoming more preferred to even > owning a traditional computer. Having the system be entirely decentralize= d > and trustless for every client does not appear to me to be the original > design goal. Yes, the whitepaper speaks of the design goal as not having = a > need for a trusted third party but it does not say that some amount of > trust won't be preferred by a majority of users. In fact, in the SPV > section it implies some amount of localized trust is perhaps a necessary > trade-off and maybe businesses should still run their own full network no= de > if they want the stronger completely trustless guarantee. The global > decentralized consensus appears meant to make the network > >>> r > >>>> esilient to a single government or other adversary's ability to shut > the network down. If you really want to trust no one it is your option at= a > cost and should be possible by design. The author further gives evidence > that they believe Moore's observation would keep the idea of running a fu= ll > network node a practical one at global scale for perpetuity. It does not > appear as if they intended for every individual to run one at home nor in > their pocket. > >>>> > >>>> If my interpretation seems incorrect please do point it out. I hope > this hasn't been too off-topic and distracting. The original author's > engineering ingenuity is what gave me any interest in this project so > re-visiting their design and scaling intentions might be helpful for us t= o > move forward-- together. > >>>> > >>>> _______________________________________________ > >>>> 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 > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --001a11c2ff1c84a25105199590b1 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
There's a couple of things that Patrick coul= d have been referring to when he said "Fraud proofs need to be at leas= t more efficient than full node validation. Currently they are not."

One of the issues is that you cannot efficiently enco= de or validate a proof of a negative. If a transaction input is a double-sp= end, you can build a semi-reasonable sized proof of the prior spend (or ver= y reasonably sized with block header commitments). However if a transaction= spends an output which never existed in the first place, there is no reaso= nable way to assert this other than witnessing the entire block history, as= a full node does.

UTXO commitments are the nominal solution h= ere. You commit the validator state in each block, and then you can prove t= hings like a negative by referencing that state commitment. The trouble is = this requires maintaining a hash tree commitment over validator state, whic= h turns out to be insanely expensive. With the UTXO commitment scheme (the = others are not better) that ends up requiring 15 - 22x more I/O during bloc= k validation. And I/O is presently a limiter to block validation speed. So = if you thought 8MB was what bitcoin today could handle, and you also want t= his commitment scheme for fraud proofs, then you should be arguing for a bl= ock size limit decrease (to 500kB), not increase.

On Sat, Jun 27, 2015 at 10:32 PM,= Eric Lombrozo <elombrozo@gmail.com> wrote:
Just to clarify, SPV is fundamentally busted as it curr= ently exists. I=E2=80=99m talking about potential optimizations for future = protocols.

- Eric Lombrozo

> On Jun 27, 2015, at 10:29 PM, Patrick Strateman <patrick.strateman@gmail.com> wrote:
>
> Fraud proofs need to be at least more efficient than full node validat= ion.
>
> Currently they are not.
>
> On 06/27/2015 09:54 PM, Eric Lombrozo wrote:
>> Fraud proofs actually don=E2=80=99t need to be made super efficien= t=E2=80=A6but they do need to be secure, of course.
>>
>> The trick is aligning incentives. In order for fraud proofs to be = widely available there needs to be a market for them - there must be a way = to buy one (because producing one is not free). What makes such a scheme ac= tually practical is that very few of these fraud proofs ever need to actual= ly be executed - it=E2=80=99s a classical Nimzowischian case of the threat = being much stronger than the execution.
>>
>> - Eric Lombrozo
>>
>>> On Jun 27, 2015, at 7:13 PM, Patrick Strateman <patrick.strateman@gmail.com> wro= te:
>>>
>>>> Further, it appears clear that the original author intende= d
>>> organizations operating full network nodes would provide conne= ctivity to
>>> light clients and these light clients would make up the majori= ty of the
>>> user base.
>>>
>>> Satoshi also believed that fraud proofs would be widely availa= ble and
>>> practical.
>>>
>>> If fraud proofs were practical SPV client security would be mu= ch closer
>>> to full node security than it is today.
>>>
>>> Unfortunately no design for fraud proofs which is both efficie= nt and
>>> secure has been proposed; much less implemented and deployed.<= br> >>>
>>> In building a system as new and innovative as bitcoin certain = things
>>> will be wrong.
>>>
>>> The perception that SPV clients could be made nearly as secure= as full
>>> nodes is one example of something that was wrong.
>>>
>>> On 06/27/2015 05:14 PM, Santino Napolitano wrote:
>>>> There is much heated debate going on right now and I know = it can be very stressful but I'd like to point out that it is really am= azing how passionately so many feel about this once very small project. Let= 's not forget there is something really special going on here and we= 9;re all part of it.
>>>>
>>>> The current debate has little to do with block size or har= d-forks, IMO. It's about the nature of Bitcoin and what it means to peo= ple and how it will grow. I would like to take a moment to share my interpr= etation of the original author's intent based on everything I could fin= d and read from this person. This is not to say their original vision is pa= ramount-- or even that I got it completely correct but I think it might do = us some good to think about.
>>>>
>>>> It seems as though the incentive conceived of for running = a full network node was that it would enable mining. The proceeds from mini= ng (new coins and transaction fees) would be the reward and provide a reaso= n to continue operating these nodes. If fees are ever to be a sufficient re= ward and still allow for a practical and useful system the size of the bloc= ks must grow significantly as must the user base. I'm not sure that thi= s is really contested but I haven't exhaustively reviewed everyone'= s opinion so please excuse me if I have marginalized you. If you do contest= that I would be interested in hearing it.
>>>>
>>>> Further, it appears clear that the original author intende= d organizations operating full network nodes would provide connectivity to = light clients and these light clients would make up the majority of the use= r base. This is completely consistent with current trends in Internet consu= mption, e.g. tablets and phones are becoming more preferred to even owning = a traditional computer. Having the system be entirely decentralized and tru= stless for every client does not appear to me to be the original design goa= l. Yes, the whitepaper speaks of the design goal as not having a need for a= trusted third party but it does not say that some amount of trust won'= t be preferred by a majority of users. In fact, in the SPV section it impli= es some amount of localized trust is perhaps a necessary trade-off and mayb= e businesses should still run their own full network node if they want the = stronger completely trustless guarantee. The global decentralized consensus= appears meant to make the network
>>> r
>>>> esilient to a single government or other adversary's a= bility to shut the network down. If you really want to trust no one it is y= our option at a cost and should be possible by design. The author further g= ives evidence that they believe Moore's observation would keep the idea= of running a full network node a practical one at global scale for perpetu= ity. It does not appear as if they intended for every individual to run one= at home nor in their pocket.
>>>>
>>>> If my interpretation seems incorrect please do point it ou= t. I hope this hasn't been too off-topic and distracting. The original = author's engineering ingenuity is what gave me any interest in this pro= ject so re-visiting their design and scaling intentions might be helpful fo= r us to move forward-- together.
>>>>
>>>> _______________________________________________
>>>> bitcoin-dev mailing list
>>>> b= itcoin-dev@lists.linuxfoundation.org
>>>> https://lists.linuxfo= undation.org/mailman/listinfo/bitcoin-dev
>>>
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitco= in-dev@lists.linuxfoundation.org
>>> https://lists.linuxfounda= tion.org/mailman/listinfo/bitcoin-dev
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@l= ists.linuxfoundation.org
> https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev


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


--001a11c2ff1c84a25105199590b1--