Date: Sat, 18 Jun 2016 18:09:29 -0400
From: Peter Todd <pete@petertodd.org>
To: Bram Cohen <bram@bittorrent.com>
Message-ID: <20160618220929.GA24713@fedora-21-dvm>
References: <CA+KqGkosGrWQ2Lpg3Ptc+UyidK7H4_HLQ_QWx2DOAFRmLkv4zQ@mail.gmail.com>
	<20160616001040.GA5026@fedora-21-dvm>
	<CA+KqGko2jW9999A9vkkBrM3EPb5OXYe4OPu0_Ot=fGnc7Cge-Q@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="IS0zKkzwUGydFO0o"
Content-Disposition: inline
In-Reply-To: <CA+KqGko2jW9999A9vkkBrM3EPb5OXYe4OPu0_Ot=fGnc7Cge-Q@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkle trees and mountain ranges
Precedence: list


--IS0zKkzwUGydFO0o
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Fri, Jun 17, 2016 at 08:22:04PM -0700, Bram Cohen wrote:
> On Wed, Jun 15, 2016 at 5:10 PM, Peter Todd <pete@petertodd.org> wrote:
> > Agreed - regardless of approach adding latency to commitment calculatio=
ns
> > of
> > all kinds is something I think we all agree can work in principle, alth=
ough
> > obviously it should be a last resort technique when optimization fails.
> >
>=20
> An important point: Adding latency to utxo commitments does not imply
> latency to proofs of inclusion and exclusion! If roots of what's added and
> deleted in each block are added as well, then a proof of inclusion can be
> done by having a proof of inclusion of the trailing utxo set followed by a
> proof of exclusion from all the following deletion sets, or a proof of
> inclusion in one of the single block addition sets followed by proofs of
> exclusion from all the more recent deletion sets. Likewise a proof of
> exclusion can be a proof of exclusion from the utxo set followed by proofs
> of exclusion from all the more recent addition sets or a single proof of
> inclusion in a recent deletion set.
>=20
> This does make proofs larger (except in the case of recent deletions and
> maybe recent additions) and adds complexity, so it shouldn't be done unle=
ss
> necessary.

So, to be clear you're assuming that blocks commit to key:value maps of the
block contents, specifically a pre-block "UTXO deletion/things that this bl=
ock
spent" set? First of all, it's interesting how the much smaller dataset of a
pre-block key:value map would make L2/L3 caching optimizations much more li=
kely
to be relevant. :)


That type of solution would be very similar to the solutions treechains wou=
ld
need to prove coins haven't been doublespent. Basically, in treechains the
system as a whole is a datastructure indexed by time and prefix. So, if you
want to prove a valid spend you need to convince me of three things:

1. The coin existed as of time t1 at prefix p

2. At t2, p, a valid spend was published.

3. Between t1 and t2 at prefix p no other valid spend was published.

Paths to any prefix p as of time t, will have about log2(len(p)) size (beyo=
nd
the top-level chain), similar to your above suggestion. Of course, unlike y=
our
above suggestion, in treechains it's not clear if step #1 can be done witho=
ut
another n*log(N)-ish sized proof in a truly trustless environment!

> But validation before block propagation needs to be extremely
> fast, so for utxo roots this trick is probably both necessary and
> sufficient.

I'm _not_ of the optinion that validation before propagation needs to be do=
ne
at all - I think it's perfectly reasonable to propgate blocks that you have=
 not
validated at all (beyond checking PoW as an anti-DoS measure).  The time it
takes miners to start mining the next block - and collecting fees - is howe=
ver
very important.

In practice, I think we're mostly in agreement here, but because I'm happy =
to
propagate prior to validating I'd be ok with protocol designs that required
miners to have relatively large amounts of RAM - say 32GB - dedicated to UT=
XO
lookup because that wouldn't require relay nodes to also have those kinds of
resources available to them once validationless propagation was implemented.

--=20
https://petertodd.org 'peter'[:-1]@petertodd.org

--IS0zKkzwUGydFO0o
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----

iQEcBAEBCAAGBQJXZcaWAAoJEGOZARBE6K+ytI4H/2ifzMFzewtKW97h6SVMVD7l
xfSKnAIErFsJYPwjpUXCAL2cdMDTzwCBTvuRcErcAMwYrHodExx+bGyuju7hQbWg
XN3aGcXGsdIsl7U4JXVcvb1gwjg7PPHjWRb8lu7Qk4ai9hlVLGV20AYZwV2IIe6t
WesU3SVBr39OO1sTp1GVTNhwjQpxmqQwsYeIsRhwLV2FJul/fvU7EynI4UN0b09f
tya1f8/Tfyi52SBiKnWL2+Yla165q5ZG532j6FPsZhAhqQhAV/8+B4g5kAHCPLDR
Oi0ucVLOQeGg7jidzIUzyzh51q608OrB8AUDJKxVcPM9BzqbYBkdxFEhdhEmgwg=
=hPgB
-----END PGP SIGNATURE-----

--IS0zKkzwUGydFO0o--