Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 930FD256 for ; 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 ; Wed, 12 Oct 2016 01:28:48 +0000 (UTC) Received: by mail-wm0-f45.google.com with SMTP id b201so2668338wmb.0 for ; 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: References: From: Natanael Date: Wed, 12 Oct 2016 03:28:46 +0200 Message-ID: To: Bitcoin Dev , John Hardy 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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

Den 12 okt. 2016 01:33 skrev "John Hardy via bitcoin-de= v" <bitcoi= n-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 whic= h there can be any number with radically different approaches.
>
> 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.
>
> 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?

More of a treechain / clusterchain, then?

> Instead of transferring Bitcoin into individual sidecha= ins, you move them into the master sidechain, which I'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.
>
> 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.
>
> 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.
>
> 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.
>
> 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.
>
> 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.
>
> I wrote this as a TLDR summary for a (still evolving) idea I had on th= e best approach to scale Bitcoin infinitely. I've written more of my th= oughts on the idea at=C2=A0https://seebitcoin.com/2016/09/introducing-buzz-a-turing-complete-co= ncept-for-scaling-bitcoin-to-infinity-and-beyond/
>
> 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.

I've got a similar idea since quite a while back, but I&= #39;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 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.

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

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).

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.

Every set of programs (transactions) can be transformed into= a "diff" 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.

Obviously that validation can get inefficient if many chains= interact, as you can'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).

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).

I really do hope it can be resolved effectively. I'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't guarantee commutativity for all actions would likel= y be to be rate limited.

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.

--047d7beb93c225bc2d053ea0ea8e--