Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.220.51 as permitted sender)
	client-ip=209.85.220.51; envelope-from=elombrozo@gmail.com;
	helo=mail-pa0-f51.google.com; 
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2098\))
Content-Type: multipart/signed;
	boundary="Apple-Mail=_25D3CD58-3475-44C5-964C-FB84EBB3D32B";
	protocol="application/pgp-signature"; micalg=pgp-sha512
From: Eric Lombrozo <elombrozo@gmail.com>
In-Reply-To: <674CED15-3F4C-4E24-BCA2-3C474CC01708@gmail.com>
Date: Sun, 14 Jun 2015 17:55:07 -0700
Message-Id: <35D2C620-DCCF-4D2C-B72C-07B276A28862@gmail.com>
References: <CALqxMTHrnSS9MGgKO-5+=fVhiOOvk12Recs11S0PcSUxQT1wdQ@mail.gmail.com>
	<CANEZrP1nx9rNf1q-nubP77U8RMABuLtmEB_P7UpY2zyFf-Ns-w@mail.gmail.com>
	<CALqxMTENbj+E7ypJASrM1r04eW3kYe+afwy+Rt3i9ubeT-=2mA@mail.gmail.com>
	<674CED15-3F4C-4E24-BCA2-3C474CC01708@gmail.com>
To: Adam Back <adam@cypherspace.org>
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] comments on BIP 100
Precedence: list


--Apple-Mail=_25D3CD58-3475-44C5-964C-FB84EBB3D32B
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8


> On Jun 14, 2015, at 5:53 PM, Eric Lombrozo <elombrozo@gmail.com> =
wrote:
>=20
> I think the whole complexity talk is missing the bigger issue.
>=20
> Sure, per block validation scales linearly (or =
quasilinearly=E2=80=A6there=E2=80=99s an O(log n) term in there =
somewhere but it=E2=80=99s probably dominated by linear factors at =
current levels=E2=80=A6asymptotic limits don=E2=80=99t always apply very =
well to finite systems). And there=E2=80=99s an O(n^2) bandwidth issue.

For accuracy=E2=80=99s sake, I meant to say O(n log n).

>=20
> The real issue, though, is validation cost. The n in O(n) here does =
not represent block size - it represents the size of the entire block =
chain for every new validator that must be synchronized! It means we =
have no way to construct short proofs (or at least arguments that are =
computationally *hard* to forge) without requiring the validator to =
maintain the complete system state. And currently, there is no mechanism =
for directly compensating validators.
>=20
> A full validator that goes offline even for a short period of time =
takes a while to fully catch up to the rest of the network - and =
starting up a new validator from scratch will continue to be =
painful=E2=80=A6even for those of us who=E2=80=99ve turned this into =
routine by now, let alone new nontechnical users.
>=20
> Satoshi=E2=80=99s SPV is not a real solution - it=E2=80=99s a mere =
suggestion that wasn=E2=80=99t fully thought out at the time of the =
Bitcoin white paper. Besides lacking a good validation security model, =
practical implementations of it weaken privacy and complicate client =
implementations substantially=E2=80=A6and the worst part, it still =
doesn=E2=80=99t scale all that well. The validator still has to query =
every single block (even if filtered) back to the first transaction =
(which cannot be determined without doing a blockchain scan anyway).
>=20
> So yes, we will most certainly need algorithmic improvements!
>=20
> - Eric Lombrozo
>=20
>=20
>> On Jun 14, 2015, at 4:58 PM, Adam Back <adam@cypherspace.org> wrote:
>>=20
>> Hi Mike
>>=20
>> On 15 June 2015 at 00:23, Mike Hearn <mike@plan99.net> wrote:
>>>> One thing that is concerning is that few in industry seem inclined =
to
>>>> take any development initiatives or even integrate a library.
>>>=20
>>> Um, you mean except all the people who have built more scalable =
wallets over
>>> the past few years, which is the only reason anyone can even use =
Bitcoin
>>> from their phone?
>>=20
>> No slight intended obviously to people who do write actual client =
code.
>>=20
>> That was probably insufficiently specific, let me rephrase: I am
>> referring to the trend that much of the industry is built on web2.0
>> technology using bitcoin via a library in a web scripting language,
>> often with consensus bugs, and even outsourcing and not even running
>> their own full node, so that the service itself offered to their =
users
>> isn't even SPV secure to the operator.  As well as being heavily =
based
>> on a third-party custody model that is the root cause of the repeated
>> wallet breaches.  Some of these companies have a noted tendency not =
to
>> upgrade or fix code.
>>=20
>> So I mean this not to call out specific companies, but in the sense
>> that if we're technologists we should be trying to move the =
technology
>> forward, not just changing parameters which run into an O(n^2) =
scaling
>> wall or break decentralisation security.  And we shouldnt take the
>> above state of affairs as an immutable reality.  It can not persist
>> for bitcoin to reach maturity on scale nor security.
>>=20
>>> I still think you guys don't recognise what you are actually asking =
for here
>>> - scrapping virtually the entire existing investment in software, =
wallets
>>> and tools.
>>=20
>> As I said I dont think we can expect Bitcoin to scale with no further
>> algorithmic improvements.  Algorithmic improvements take code.  There
>> is reasonable scope to build in an incrementally deployable way,
>> there's plenty of time for people to code, test and opt-in to things,
>> the sky is not falling.  Companies do care about scaling, and can
>> invest in the integration and coding implied to improve their =
products
>> scalability, they have an economic incentive to do it and there is no
>> scalable and safe way todo it without this work.
>>=20
>>> Computational complexity for the entire network is O(nm) where
>>> n=3Dtransactions and m=3Dfully validating nodes. There is no fixed =
relationships
>>> between those two variables.
>>=20
>> I am referring to global bandwidth O(n^2) with n=3Dusers, or O(n) per
>> user bandwidth cost to the system, while O(nm) is accurate nodes is =
an
>> internal system concept.  Anyway suffice to say the network does not
>> scale O(1) in per user cost.
>>=20
>>> "Exposing the companies to back-pressure" sounds quite nice and =
gentle. Let
>>> me rephrase it to be equivalent but perhaps more direct: you mean =
"breaking
>>> the current software ecosystem to force people into a new, fictional =
system
>>> that bears little resemblance to the Bitcoin we use today, whether =
they want
>>> that or not".
>>>=20
>>> As nothing that has been proposed so far (Lightning, merge mined =
chains,
>>> extension blocks etc) has much chance of actual deployment any time =
soon,
>>> that leaves raising the block size limit as the only possible path =
left.
>>=20
>> A hard-fork takes a long period of time to deploy due to the
>> non-upgrade risk, people are working on things in the mean-time.
>> There can be a case for some increase to create some breathing room =
to
>> work on scaling and decentralising tech, I just mean to say that if =
we
>> do it in isolation, we're not focussing on the big picture.
>>=20
>> Adam
>>=20
>> =
--------------------------------------------------------------------------=
----
>> _______________________________________________
>> Bitcoin-development mailing list
>> Bitcoin-development@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>=20


--Apple-Mail=_25D3CD58-3475-44C5-964C-FB84EBB3D32B
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename=signature.asc
Content-Type: application/pgp-signature;
	name=signature.asc
Content-Description: Message signed with OpenPGP using GPGMail

-----BEGIN PGP SIGNATURE-----
Comment: GPGTools - https://gpgtools.org

iQIcBAEBCgAGBQJVfiJrAAoJEJNAI64YFENUBLoP/iRqjwXtQClFc6P2PachVA4Z
XbowdfWywtDffeK+n0JoUNl69G89JAsM5fq2SXyAwZnBgF5VhQq1AxLIFXScU2nk
r6DYprGGxtNXuYAG7xI++6CaVNWKnBs36O6ZXd58pIWtaUrgtj1/rkxR9bKngnDC
jmf4Dw+Jv5+mSdHegqQ4lSSfB7UER5l0wKsBVDkLQIs4IfPz6h+Se4T2WuKC02Po
T72bjkjv/7Kf/Gw8EUOb+Ze5BPDAnNTnFDNw6WpB4rE8RCOWcgeYleeS7pOBQy78
Iva+Xu6IyRVNpUjHEEMSU5heuz2YLPxmwQa1+YJB2Hjn+YB+2KjPoT1RczSFIL6c
u4vaXLdu8pT5UnZPL9Xt6U641yuCpIMr0cCf+TmgoTzabO2LzTyqqywPgmQ8HdZH
yssbdLHQgQtT6fT2sD2GIknEK2dpeKSKNXR993+vHSaC6RY6CIbcGgwOb2wt1+lW
dlKruZ7hXnaVE86waZOqb3KX35r4DxQU5V97Vn9mPpTmKF7uLcDiz3bZa/kTkUgs
PA+wYiBLD5c5w7oQRF3sRW0v258hiN6OZzbjXw0WIU6XZ/XxtdVqtvxHyRMSIKpl
nBrxfohHMAzIVffjm9YYUltCKALkGUNM0FSUFFo7ggJmJuixdKk9B4+AfKkZN6fE
uE5OpJ+/mtMdxglCC5JZ
=raZd
-----END PGP SIGNATURE-----

--Apple-Mail=_25D3CD58-3475-44C5-964C-FB84EBB3D32B--