Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.192.169 as permitted sender)
	client-ip=209.85.192.169; envelope-from=elombrozo@gmail.com;
	helo=mail-pd0-f169.google.com; 
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2098\))
Content-Type: multipart/signed;
	boundary="Apple-Mail=_7C3316F3-5759-4409-905D-5D7B8C393E5F";
	protocol="application/pgp-signature"; micalg=pgp-sha512
From: Eric Lombrozo <elombrozo@gmail.com>
In-Reply-To: <20150615041149.GA13286@muck>
Date: Sun, 14 Jun 2015 21:43:09 -0700
Message-Id: <B0D24D77-EAF8-4EB4-9E1B-0A3539C0AAA9@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>
	<20150615041149.GA13286@muck>
To: Peter Todd <pete@petertodd.org>
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] comments on BIP 100
Precedence: list


--Apple-Mail=_7C3316F3-5759-4409-905D-5D7B8C393E5F
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8


> On Jun 14, 2015, at 9:11 PM, Peter Todd <pete@petertodd.org> wrote:
>=20
> On Sun, Jun 14, 2015 at 05:53:05PM -0700, Eric Lombrozo wrote:
>> 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.
>>=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
> ...and can there be? The goal of validation after all is finding if a
> mistake has been made, and current production cryptography doesn't =
have
> any way to prove you have done that honestly. You need "moon math" =
like
> recursive SNARKS to do that, and it's unknown when they'll be =
available
> for production usage.
>=20

While things like zero-knowledge and homomorphic encryption would be =
awesome, they are not really needed to achieve the objective of an =
efficient proof that is hard to forge with at least a decently thought =
out security model (i.e. we can make information withholding far more =
difficult)=E2=80=A6and we can dramatically improve search times and =
local storage requirements by doing some of the things that you=E2=80=99ve=
 actually proposed, Peter, like shifting the responsibility of =
maintaining and constructing proofs over to transaction senders and =
committing proof hashes to the global state. At least the incentives =
would be far better aligned in such a scenario.

How do we deal with things like the discovery of an invalid proof a =
couple weeks after it=E2=80=99s already been committed? This is a tricky =
issue I=E2=80=99ve been giving a lot of thought to recently - but =
we=E2=80=99ll deal with this topic in a separate thread. :)

> When we say "compensating validators", if we're being honest with
> outselves what we really mean is the much more boring task of
> compensating servers who are giving us blockchain data. That has =
nothing
> to do with validation.

If we were to shift responsibility of constructing proofs over to =
transaction senders, today's =E2=80=9Cvalidators=E2=80=9D would indeed =
become nothing more than compensated servers. Clients would be able to =
query for proofs and verify them for themselves efficiently.

> A useful task would be to make an SPV archival node implementation =
that
> did no validation at all, while distributing the blockchain data =
linked
> to the longest chain. Such an implementation can and should serve SPV
> clients, as this is what their actual security model usually is given
> the lack of authentication of the identity of the server they're
> connecting too. Actually implementing this would be a simple matter of
> patching Bitcoin Core to turn off block validation.
>=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
> Concretely, 20MB blocks lead to 20GB/week of blocks. On my 1MB/second
> down internet, turning on my node after a week away would take five
> hours; starting up a new node after two years of 20MB blocks would =
take
> 23 days - likely longer in practice.
>=20
> There's serious unsolved and undiscussed devops and development issues
> with this. For instance, after changes to the validation code, it's
> routine to resync/reindex Bitcoin Core to ensure starting up a new =
node
> actually works. Even now we haven't really come to grips with what
> consistent 1MB blocks looks like from this point of view after a few
> years of usage, let another order of magnitude longer sync times.
>=20

It=E2=80=99s a disaster. Even with 1MB blocks this is already the =
principal centralization pressure on Bitcoin.

>> 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
> Note how with 20MB blocks it would take up to 1TB of IO per =
year-synced
> for a bloom-filter-using wallet to sync the blockchain. We already =
have
> a bloom IO DoS attack issue - what are the consequences of making that
> issue 20x worse? Nobody has analysed it yet.
>=20

We clearly need better data structures and algorithms. This talk of =
bigger blocks seems so petty by comparison, TBH.

> --
> 'peter'[:-1]@petertodd.org
> 0000000000000000127ab1d576dc851f374424f1269c4700ccaba2c42d97e778


--Apple-Mail=_7C3316F3-5759-4409-905D-5D7B8C393E5F
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

iQIcBAEBCgAGBQJVflfdAAoJEJNAI64YFENU0u0P/0lw6iempwjmHht5b9laBJOu
uDNIEpuwYBN9/TNTJwHLPwvQs2NG5wM7xguJj5853dhGDUxvJK80kpqPbJvsL8X/
8cbXeOLZEdZZgzdkE4s2L0ecfeGxZWTlDAIlwUjcJc5KuNNKlZEZ07a3tD6LvEcg
6i6NRNomMn61MR6WkBf26qF9K14PHz892nk384ZcA+di3Ha7k5d+Z1bjac8IAHIR
lEqOnKihgX52OdMNvQVJcqwi/BmfOZMJeEONsA+ct1IBz/BuVB/GLExe7qdek7ky
bs/I8074thxS8R9thOJSCbGdg3iv85IaRpZQ2ykXsv53yUVcQE0x+DLQMCdAuQDg
vttqRDOnvCLdscSt0HaJraWnnQL5oAr7r3oz/oTewF+XInSnzn1tdzaUT1ixBXCj
7gIDs8n1XBNZFWijLzM36Oe4Usl+8fQ4Tv2EoBGeIhfLQCrR0nnfRAHGukC1SsBc
7UPjpzebz5/FpKB2IP+EyiEI/jQ7s7jpXSEoNegMnE1iQfw9ZegwBtV0minQFdkN
j1Ia3GecfAhM3G2vUfgcbQTXCmu69/TLciF+tUBmPx+FnIdOrXLvC8y1JdZLJ4YS
zX2HH//3XKSUMVkCJN1YoaBH9t7Z/0XReJ1gB8WZwXyri+9T5zTFcZslr77J72Ja
IkTLYgW5zt3Xcy1lruA5
=apbX
-----END PGP SIGNATURE-----

--Apple-Mail=_7C3316F3-5759-4409-905D-5D7B8C393E5F--