path: root/b6/793e25b402b7903791436ec9cb42f34540281c

Return-Path: <natanael.l@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 930FD256
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 12 Oct 2016 01:28:50 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f45.google.com (mail-wm0-f45.google.com [74.125.82.45])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F33B810A
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 12 Oct 2016 01:28:48 +0000 (UTC)
Received: by mail-wm0-f45.google.com with SMTP id b201so2668338wmb.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 11 Oct 2016 18:28:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to; 
	bh=jWZZYn1/oro2ElzWxxK5SXOeyS2shTieClUQvOMjiAA=;
	b=CH0G4G4eUNM26lUn8jBuPCO2zHOeLtAdtZsU204NoAIlMgs4S8bHddqDSyVwaA9W/D
	pXnGExIpTkCdCtDGVUtcfm0JAK/6R7Bm6ScvSUHMzl85OQuYOGSTq/X+sVwqUuxkHI8Y
	tZRWCqpYQYDBICfyDHtamz1ztbvs7y6eNPFoyAydJLEubY6vQ9qlojc/D9UpZXG8EZfK
	N6LFBAO1yOL6JVZ4kl0STuXbQCcXTTNd69m4BvNSkICtgAnQNJKGpgq2TtWkSpeQ1tt6
	dkEtgdYQRXn/4+ogSpjKGnvS3u0LwfMR5881qmf55rcUyJ9KyehqL56YpQ3zX337fZ8G
	KOzg==
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;
	bh=jWZZYn1/oro2ElzWxxK5SXOeyS2shTieClUQvOMjiAA=;
	b=HCb31JbdpT4SJPB3ifvYIGQLkmRXxFZ2ZHZ+deq0HpUQkJim+cbGA/iikqn4yPkqDJ
	LDHmDgN4e4El+ytllWYrtCLVFQibQ0J5A1aFApRWov11F6OIT+l1oK4tLQcUWT57P66p
	gJwXfFgsDZlf/eNKk4IK8q8yA4v7LRAZ4rqV7JU3dnXY+QVmmuGxpGN3XB5AhJaqYsf5
	aAHD+jDCKRJNwIVbwEaQievWNVb2/eCP3H9RAEYStX+nYI4aEGagJu9Ly0n6nGe9J1Ct
	uvPaqcibnmNFrVCBWGSdIEfKF0THJ0hueaTVwm4oaYRS7Fu+DP0haUV08E4i49LTN5xr
	KjTg==
X-Gm-Message-State: AA6/9Rn0tAtawwkkdfWZKUmb7DVLuL5tuHFGLyDcYfuU5Qa0V+SCF5imjaOldV8XRnL6nDWmHUn8CnH9O5iv2w==
X-Received: by 10.194.79.170 with SMTP id k10mr7449024wjx.209.1476235727580;
	Tue, 11 Oct 2016 18:28:47 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.80.183.208 with HTTP; Tue, 11 Oct 2016 18:28:46 -0700 (PDT)
Received: by 10.80.183.208 with HTTP; Tue, 11 Oct 2016 18:28:46 -0700 (PDT)
In-Reply-To: <DUB118-W404335B158A3BE61A6D164EFDA0@phx.gbl>
References: <DUB118-W3025C67626835237E907A9EFC20@phx.gbl>
	<DUB118-W404335B158A3BE61A6D164EFDA0@phx.gbl>
From: Natanael <natanael.l@gmail.com>
Date: Wed, 12 Oct 2016 03:28:46 +0200
Message-ID: <CAAt2M19Vkbp82Pat7dSrdunFthNX0zSVsLAvZ+5X=i6Fz+s+ew@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>,
	John Hardy <john@seebitcoin.com>
Content-Type: multipart/alternative; boundary=047d7beb93c225bc2d053ea0ea8e
X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
	RCVD_IN_DNSWL_NONE, 
	RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Could a sidechain protocol create an addressable
 "Internet of Blockchains" and facilitate scaling?
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol 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, 12 Oct 2016 01:28:50 -0000

--047d7beb93c225bc2d053ea0ea8e
Content-Type: text/plain; charset=UTF-8

Den 12 okt. 2016 01:33 skrev "John Hardy via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org>:
> Sidechains seem an inevitable tool for scaling. They allow Bitcoins to be
transferred from the main blockchain into external blockchains, of which
there can be any number with radically different approaches.
>
> In current thinking I have encountered, sidechains are isolated from each
other. To move Bitcoin between them would involve a slow transfer back to
the mainchain, and then out again to a different sidechain.
>
> Could we instead create a protocol for addressable blockchains, all using
a shared proof of work, which effectively acts as an Internet of
Blockchains?

More of a treechain / clusterchain, then?

> Instead of transferring Bitcoin into individual sidechains, you move them
into the master sidechain, which I'll call Angel. The Angel blockchain sits
at the top of of a tree of blockchains, each of which can have radically
different properties, but are all able to transfer Bitcoin and data between
each other using a standardised protocol.
>
> Each blockchain has its own address, much like an IP address. The Angel
blockchain acts as a registrar, a public record of every blockchain and its
properties. Creating a blockchain is as simple as getting a
createBlockchain transaction included in an Angel block, with details of
parameters such as block creation time, block size limit, etc. A
decentralised DNS of sorts.
>
> Mining in Angel uses a standardised format, creating hashes which allow
all different blockchains to contribute to the same Angel proof of work.
Miners must hash the address of the blockchain they are mining, and if they
mine a hash of sufficient difficulty for that blockchain they are able to
create a block.
>
> Blockchains can have child blockchains, so a child of Angel might have
the address aa9, and a child of aa9 might have the address aa9:e4d. The
lower down the tree you go, the lower the security, but the lower the
transaction fees. If a miner on a lower level produces a hash of sufficient
difficulty, they can use it on any parents, up to and including the Angel
blockchain, and claim fees on each.
>
> Children always synchronise and follow all parents (and their
reorganisations), and parents are aware of their children. This allows you
to do some pretty cool things with security. If a child tries to withdraw
to a parent after spending on the child (a double spend attempt) this will
be visible instantly, and all child nodes will immediately be able to
broadcast proof of the double spend to parent chain nodes so they do not
mine on those blocks. This effectively means children can inherit a level
of security from their parents without the same PoW difficulty.
>
> There are so many conflicting visions for how to scale Bitcoin. Angel
allows the free market to decide which approaches are successful, and for
complementary blockchains with different use cases, such as privacy, high
transaction volume, and Turing completeness to more seamlessly exist
alongside each other, using Bitcoin as the standard medium of exchange.
>
> I wrote this as a TLDR summary for a (still evolving) idea I had on the
best approach to scale Bitcoin infinitely. I've written more of my thoughts
on the idea at
https://seebitcoin.com/2016/09/introducing-buzz-a-turing-complete-concept-for-scaling-bitcoin-to-infinity-and-beyond/
>
> Does anybody think this would be a better, more efficient way of
implementing sidechains? It allows infinite scaling, and standardisation
allows better pooling of resources.

I've got a similar idea since quite a while back, but I've never really
written it down in full. Here one link:

http://www.metzdowd.com/pipermail/cryptography/2015-January/024338.html

Some thoughts on how to design it;

The basic idea is to compress the validation data maximally, and yet
achieve Turing completeness for an arbitary number of interacting chains,
or "namespaces".

The whole thing is checkpointed and uses Zero-knowledge proofs to enable
secure pruning, making it essentially a rolling blockchain with complete
preservation of history. It grows approximately linearly with
non-deprecated state.

This latest checkpoint's header + the following headers and accompanying
Zero-knowledge proofs would together act as the root for the system.

Having that is all you would need to confirm that any particular piece of
data from the blockchain is correct, given that it comes with enough
metadata to trace it all the way to the root. (Merkle tree hashes, ZKP:s,
etc).

Every chain would be registered under a unique name (the root chain would
essentially just deal with registering chain names + their rules), and
would define its own external API towards other chains, and it would define
its own rules for how its data can be updated and when. Every single
interaction with a chain is done by an atomic program (transaction), and
all sets of validated changes must be conflict-free (especially across
chains). Everything would practically be composed of a hierarchy of
interacting programs.

Every set of programs (transactions) can be transformed into a "diff" on
the blockchain state plus an accompanying Zero-knowledge proof. The proofs
can even be chained, such that groups of users of one chain can create a
proof for their own changes, submit it to some chain coordinator who does
another compressing merge and proof generation, to then send it to the
miners who merges the collective changes for all chains and generates a
proof for the root.

Obviously that validation can get inefficient if many chains interact, as
you can't simply just look for conflicting UTXO:s in programs (unless the
chain designers are *really* smart with their conflict resolution
mechanisms). Either you have to use programmatic locking, very slow block
rates or chose to not guarantee that any particular action has succeeded
(essentially turning validated programs (transactions) into *requests* to
the API up towards the root, to eventually be resolved later with responses
propagated back down, instead of having them be direct changes to the
state).

The latter option requires a lot more interaction by the client to get the
intended behavior in many circumstances. The first two can both kill
performance (nobody wants small programs with a few round-trips to take a
week to execute).

I really do hope it can be resolved effectively. I'm guessing some serious
restrictions on the API:s would be necessary. You would want most programs
to be provably independent (such as not accessing the same resources) to be
able to easily just create a small checkpoint of the global state and
generate a proof for it. Programs simultaneously accessing resources that
don't guarantee commutativity for all actions would likely be to be rate
limited.

Best case scenario: some genius manages to create the equivalent of
Lightning Network (with in-chain arbitration authority assigned to chosen
servers in the chain definitions, and cross-chain negotiation between those
authorities when programs use the API) for processing the programs in near
real-time, and quickly settling on what changes to commit to the root.
Programs would practically need to be designed to be networked
(multi-stage) so that the servers can let them negotiate over their API:s
across all chains, until the server has a complete set of changes without
conflicts to commit to the root.

--047d7beb93c225bc2d053ea0ea8e
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<p dir=3D"ltr">Den 12 okt. 2016 01:33 skrev &quot;John Hardy via bitcoin-de=
v&quot; &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoi=
n-dev@lists.linuxfoundation.org</a>&gt;:<br>
&gt; Sidechains seem an inevitable tool for scaling. They allow Bitcoins to=
 be transferred from the main blockchain into external blockchains, of whic=
h there can be any number with radically different approaches.<br>
&gt;<br>
&gt; In current thinking I have encountered, sidechains are isolated from e=
ach other. To move Bitcoin between them would involve a slow transfer back =
to the mainchain, and then out again to a different sidechain.<br>
&gt;<br>
&gt; Could we instead create a protocol for addressable blockchains, all us=
ing a shared proof of work, which effectively acts as an Internet of Blockc=
hains?</p>
<p dir=3D"ltr">More of a treechain / clusterchain, then?</p>
<p dir=3D"ltr">&gt; Instead of transferring Bitcoin into individual sidecha=
ins, you move them into the master sidechain, which I&#39;ll call Angel. Th=
e Angel blockchain sits at the top of of a tree of blockchains, each of whi=
ch can have radically different properties, but are all able to transfer Bi=
tcoin and data between each other using a standardised protocol.<br>
&gt;<br>
&gt; Each blockchain has its own address, much like an IP address. The Ange=
l blockchain acts as a registrar, a public record of every blockchain and i=
ts properties. Creating a blockchain is as simple as getting a createBlockc=
hain transaction included in an Angel block, with details of parameters suc=
h as block creation time, block size limit, etc. A decentralised DNS of sor=
ts.<br>
&gt;<br>
&gt; Mining in Angel uses a standardised format, creating hashes which allo=
w all different blockchains to contribute to the same Angel proof of work. =
Miners must hash the address of the blockchain they are mining, and if they=
 mine a hash of sufficient difficulty for that blockchain they are able to =
create a block.<br>
&gt;<br>
&gt; Blockchains can have child blockchains, so a child of Angel might have=
 the address aa9, and a child of aa9 might have the address aa9:e4d. The lo=
wer down the tree you go, the lower the security, but the lower the transac=
tion fees. If a miner on a lower level produces a hash of sufficient diffic=
ulty, they can use it on any parents, up to and including the Angel blockch=
ain, and claim fees on each.<br>
&gt;<br>
&gt; Children always synchronise and follow all parents (and their reorgani=
sations), and parents are aware of their children. This allows you to do so=
me pretty cool things with security. If a child tries to withdraw to a pare=
nt after spending on the child (a double spend attempt) this will be visibl=
e instantly, and all child nodes will immediately be able to broadcast proo=
f of the double spend to parent chain nodes so they do not mine on those bl=
ocks. This effectively means children can inherit a level of security from =
their parents without the same PoW difficulty.<br>
&gt;<br>
&gt; There are so many conflicting visions for how to scale Bitcoin. Angel =
allows the free market to decide which approaches are successful, and for c=
omplementary blockchains with different use cases, such as privacy, high tr=
ansaction volume, and Turing completeness to more seamlessly exist alongsid=
e each other, using Bitcoin as the standard medium of exchange.<br>
&gt;<br>
&gt; I wrote this as a TLDR summary for a (still evolving) idea I had on th=
e best approach to scale Bitcoin infinitely. I&#39;ve written more of my th=
oughts on the idea at=C2=A0<a href=3D"https://seebitcoin.com/2016/09/introd=
ucing-buzz-a-turing-complete-concept-for-scaling-bitcoin-to-infinity-and-be=
yond/">https://seebitcoin.com/2016/09/introducing-buzz-a-turing-complete-co=
ncept-for-scaling-bitcoin-to-infinity-and-beyond/</a><br>
&gt;<br>
&gt; Does anybody think this would be a better, more efficient way of imple=
menting sidechains? It allows infinite scaling, and standardisation allows =
better pooling of resources.</p>
<p dir=3D"ltr">I&#39;ve got a similar idea since quite a while back, but I&=
#39;ve never really written it down in full. Here one link:</p>
<p dir=3D"ltr"><a href=3D"http://www.metzdowd.com/pipermail/cryptography/20=
15-January/024338.html">http://www.metzdowd.com/pipermail/cryptography/2015=
-January/024338.html</a></p>
<p dir=3D"ltr">Some thoughts on how to design it;</p>
<p dir=3D"ltr">The basic idea is to compress the validation data maximally,=
 and yet achieve Turing completeness for an arbitary number of interacting =
chains, or &quot;namespaces&quot;.</p>
<p dir=3D"ltr">The whole thing is checkpointed and uses Zero-knowledge proo=
fs to enable secure pruning, making it essentially a rolling blockchain wit=
h complete preservation of history. It grows approximately linearly with no=
n-deprecated state. </p>
<p dir=3D"ltr">This latest checkpoint&#39;s header + the following headers =
and accompanying Zero-knowledge proofs would together act as the root for t=
he system. </p>
<p dir=3D"ltr">Having that is all you would need to confirm that any partic=
ular piece of data from the blockchain is correct, given that it comes with=
 enough metadata to trace it all the way to the root. (Merkle tree hashes, =
ZKP:s, etc). </p>
<p dir=3D"ltr">Every chain would be registered under a unique name (the roo=
t chain would essentially just deal with registering chain names + their ru=
les), and would define its own external API towards other chains, and it wo=
uld define its own rules for how its data can be updated and when. Every si=
ngle interaction with a chain is done by an atomic program (transaction), a=
nd all sets of validated changes must be conflict-free (especially across c=
hains). Everything would practically be composed of a hierarchy of interact=
ing programs. </p>
<p dir=3D"ltr">Every set of programs (transactions) can be transformed into=
 a &quot;diff&quot; on the blockchain state plus an accompanying Zero-knowl=
edge proof. The proofs can even be chained, such that groups of users of on=
e chain can create a proof for their own changes, submit it to some chain c=
oordinator who does another compressing merge and proof generation, to then=
 send it to the miners who merges the collective changes for all chains and=
 generates a proof for the root. </p>
<p dir=3D"ltr">Obviously that validation can get inefficient if many chains=
 interact, as you can&#39;t simply just look for conflicting UTXO:s in prog=
rams (unless the chain designers are *really* smart with their conflict res=
olution mechanisms). Either you have to use programmatic locking, very slow=
 block rates or chose to not guarantee that any particular action has succe=
eded (essentially turning validated programs (transactions) into *requests*=
 to the API up towards the root, to eventually be resolved later with respo=
nses propagated back down, instead of having them be direct changes to the =
state). </p>
<p dir=3D"ltr">The latter option requires a lot more interaction by the cli=
ent to get the intended behavior in many circumstances. The first two can b=
oth kill performance (nobody wants small programs with a few round-trips to=
 take a week to execute). </p>
<p dir=3D"ltr">I really do hope it can be resolved effectively. I&#39;m gue=
ssing some serious restrictions on the API:s would be necessary. You would =
want most programs to be provably independent (such as not accessing the sa=
me resources) to be able to easily just create a small checkpoint of the gl=
obal state and generate a proof for it. Programs simultaneously accessing r=
esources that don&#39;t guarantee commutativity for all actions would likel=
y be to be rate limited. </p>
<p dir=3D"ltr">Best case scenario: some genius manages to create the equiva=
lent of Lightning Network (with in-chain arbitration authority assigned to =
chosen servers in the chain definitions, and cross-chain negotiation betwee=
n those authorities when programs use the API) for processing the programs =
in near real-time, and quickly settling on what changes to commit to the ro=
ot. Programs would practically need to be designed to be networked (multi-s=
tage) so that the servers can let them negotiate over their API:s across al=
l chains, until the server has a complete set of changes without conflicts =
to commit to the root. </p>

--047d7beb93c225bc2d053ea0ea8e--