From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1WPK0p-0002qQ-Bj for bitcoin-development@lists.sourceforge.net; Sun, 16 Mar 2014 22:58:35 +0000 X-ACL-Warn: Received: from mout.perfora.net ([74.208.4.194]) by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1WPK0l-00077G-Hs for bitcoin-development@lists.sourceforge.net; Sun, 16 Mar 2014 22:58:35 +0000 Received: from netbook (108-193-6-130.lightspeed.sntcca.sbcglobal.net [108.193.6.130]) by mrelay.perfora.net (node=mrus2) with ESMTP (Nemesis) id 0MaJ9M-1WjBH40NnE-00KS3u; Sun, 16 Mar 2014 18:58:26 -0400 Received: by netbook (Postfix, from userid 1000) id 85CED2E4B38; Sun, 16 Mar 2014 15:58:20 -0700 (PDT) Received: by flare (hashcash-sendmail, from uid 1000); Sun, 16 Mar 2014 15:58:19 -0700 Date: Sun, 16 Mar 2014 15:58:19 -0700 From: Adam Back To: Bitcoin-Dev Message-ID: <20140316225819.GA19846@netbook.cypherspace.org> References: <20130519132359.GA12366@netbook.cypherspace.org> <5199C3DE.901@gmail.com> <20131014180807.GA32082@netbook.cypherspace.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline In-Reply-To: <20131014180807.GA32082@netbook.cypherspace.org> User-Agent: Mutt/1.5.21 (2010-09-15) X-Hashcash: 1:20:140316:bitcoin-development@lists.sourceforge.net::7Lr3Z/R95+Rwe pRT:000000000000000000000Ndw X-Hashcash: 1:20:140316:adam@cypherspace.org::VdsBhGkcXxtOi2Xv:00000000000000000 0000000000000000000000000fc+ X-Hashcash: 1:20:140316:gmaxwell@gmail.com::0tkZvsqdLq+98bJX:0000000000000000000 0000000000000000000000004x0z X-Provags-ID: V02:K0:bNdN2H4X4DzZ7N0Bww6Ogd5i6zOiXA4rVss9bRyhreP W936CfnwNFTSMh0VxSWPYI7VQiFWkX99LE/7X4upiyUZgS1yFI 7b+FGNgsINFnXm0CIet/93St32Bcr3kGmSizG+8TAueUHc5SeV afWCScb7OwjU9jkkPa0gqIX3NS96tQ0iKg/pUcGplKMtFjP6zQ h89OYbKvqqnu5voTaXuljx9VQpWWwc+L/h0PUHqdhZEB3lZHyI KDAxutKsgVwhZ2CVAuMvkUAgkGgkAuTb3Ge3DkTzmgd9ihGOx+ NeiUJgPu0hXGyvndohq7C26GByRndwJVDgUxBpCXJ5AJJUgf2O gtgoCGfmOgSBkoW19cmCw0vXiuuS/pz8/a4HRV8qE X-Spam-Score: -0.0 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/, no trust [74.208.4.194 listed in list.dnswl.org] -0.0 SPF_HELO_PASS SPF: HELO matches SPF record X-Headers-End: 1WPK0l-00077G-Hs Subject: [Bitcoin-development] 2-way pegging (Re: is there a way to do bitcoin-staging?) X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 16 Mar 2014 22:58:35 -0000 So an update on 1-way pegging (aka bitcoin staging, explained in quoted text at bottom): it turns out secure 2-way pegging is also possible (with some bitcoin change to help support it). The interesting thing is this allows interoperability in terms of being able to move bitcoin into and out of a side chain. The side chains may have some different parameters, or experimental things people might want to come up with (subject to some minimum compatibility at the level of being able to produce an SPV proof of a given form). At the time of the 1-way peg discussion I considered 2-way peg as desirable and it seemed plausible with bitcoin changes, but the motivation for 1-way peg was to make it less risky to make changes on bitcoin, so that seemed like a catch-22 loop. Also in the 2-way peg thought experiment I had not realized how simple it was to still impose a security firewall in the 2-way peg also. So Greg Maxwell proposed in Dec last year a practically compact way to do 2-way pegging using SPV proofs. And also provided a simple argument of how this can provide a security firewall. (Security firewall means the impact of security bugs on the side-chain is limited to the people with coins in it; bitcoin holders who did not use it are unaffected). [1] How it works: 1. to maintain the 21m coins promise, you start a side-chain with no in-chain mining subsidy, all bitcoin creation happens on bitcoin chain (as with 1-way peg). Reach a reasonable hash rate. (Other semantics than 1:1 peg should be possible, but this is the base case). 2. you move coins to the side-chain by spending them to a fancy script, which suspends them, and allows them to be reanimated by the production of an SPV proof of burn on the side-chain. 3. the side-chain has no mining reward, but it allows you to mint coins at no mining cost by providing an SPV proof that the coin has been suspended as in 2 on bitcoin. The SPV proof must be buried significantly before being used to reduce risk of reorganization. The side-chain is an SPV client to the bitcoin network, and so maintains a view of the bitcoin hash chain (but not the block data). 4. the bitcoin chain is firewalled from security bugs on the side chain, because bitcoin imposes the rule that no more coins can be reanimated than are currently suspend (with respect to a given chain). 5. to simplify what they hypothetical bitcoin change would need to consider and understand, after a coin is reanimated there is a maturity period imposed (say same as fresh mined coins). During the maturity period the reanimation script allows a fraud proof to spend the coins back. A fraud bounty fee (equal to the reanimate fee) can be offered by the mover to incentivize side-chain full nodes to watch reanimations and search for fraud proofs. 6. a fraud proof is an SPV proof with a longer chain showing that the proof of burn was orphaned. There are a few options to compress the SPV proof, via Fiat-Shamir transform to provide a compact proof of amount work contained in a merkle tree of proofs of work (as proposed by Fabien Coelho link on http://hashcash.org/papers/) with params like 90% of work is proven. But better is something Greg proposed based on skip-lists organized in a tree, where 'lucky' proofs of work are used to skip back further. (Recalling that if you search for a 64-bit leading-0 proof-of-work, half the time you get a 65-bit, quarter 66-bit etc.) With this mechanism you can accurately prove the amount of proof of work in a compressed tree (rather than ~90%). Apart from pegging from bitcoin to a side-chain, if a private chain is made with same rules to the side-chain it becomes possible with some modifications to the above algorithm to peg the side-chain to a private chain. Private chain meaning a chain with the same format but signature of single server in place of hashing, and timestamping of the block signatures in the mined side chain. And then reactive security on top of that by full nodes/auditors trying to find fraud proofs (rewrites of history relative to side-chain mined time-stamp or approved double-spends). The reaction is to publish a fraud proof and move coins back to the side chain, and then regroup on a new server. (Open transactions has this audit + reactive model but as far as I know does it via escrow, eg the voting pools for k of n escrow of the assets on the private server.) I also proposed the same reactive audit model but for auditable namespaces [4]. Private chains add some possiblity for higher scaling, while retaining bitcoin security properties. (You need to add the ability for a user to unilaterally move his coins to the side-chain they came from in event the chain server refuses to process transactions involving them. This appears to be possible if you have compatible formats on the private chain and side-chain). This pegging discussion involved a number of #bitcoin-wizards, Greg Maxwell, Matt Corallo, Pieter Wuille, Jorge Timon, Mark Freidenbach, Luke Dashjr. The 2-way peg seems to have first been described by Greg. Greg thought of 2-way pegging in the context of ZK-SNARKS and the coinwitness thread [2]. (As a ZK-SNARK could compactly prove full validation of a side chain rules). There was also something seemingly similar sounding but not described in detail by Alex Mizrahi in the context of color coins in this post [3]. Adam [1] http://download.wpsoftware.net/bitcoin/wizards/2013-12-18.txt [2] https://bitcointalk.org/index.php?topic=277389.40 [3] https://bitcointalk.org/index.php?topic=277389.msg4167554#msg4167554 [4] http://www.cypherspace.org/p2p/auditable-namespace.html On Mon, Oct 14, 2013 at 08:08:07PM +0200, Adam Back wrote: >Coming back to the staging idea, maybe this is a realistic model that could >work. The objective being to provide a way for bitcoin to move to a live >beta and stable being worked on in parallel like fedora vs RHEL or odd/even >linux kernel versions. > >Development runs in parallel on bitcoin 1.x beta (betacoin) and bitcoin 0.x >stable and leap-frogs as beta becomes stable after testing. > >Its a live beta, meaning real value, real contracts. But we dont want it to >be an alt-coin with a floating value exactly, we want it to be bitcoin, but >the bleeding edge bitcoin so we want to respect the 21 million coin limit, >and allow coins to move between bitcoin and betacoin with some necessary >security related restrictions. > >There is no mining reward on the betacoin network (can be merge mined for >security), and the way you opt to move a bitcoin into the betacoin network >is to mark it as transferred in some UTXO recognized way. It cant be >reanimated, its dead. (eg spend to a specific recognized invalid address on >the bitcoin network). In this way its not really a destruction, but a move, >moving the coin from bitcoin to betacoin network. > >This respects the 21 million coin cap, and avoids betacoin bugs flowing back >and affecting bitcoin security or value-store properties. Users may buy or >swap betacoin for bitcoin to facilitate moving money back from betacoin to >bitcoin. However that is market priced so the bitcoin network is security >insulated from beta. A significant security bug in beta would cause a >market freeze, until it is rectified. > >The cost of a betacoin is capped at one BTC because no one will pay more >than one bitcoin for a betacoin because they could alternatively move their >own coin. The reverse is market priced. > >Once bitcoin beta stabalizes, eg say year or two type of time-frame, a >decision is reached to promote 1.0 beta to 2.0 stable, the remaining >bitcoins can be moved, and the old network switched off, with mining past a >flag day moving to the betacoin. > >During the beta period betacoin is NOT an alpha, people can rely on it and >use it in anger for real value transactions. eg if it enables more script >features, or coin coloring, scalabity tweaks etc people can use it. >Probably for large value store they are always going to prefer >bitcoin-stable, but applications that need the coloring features, or >advanced scripting etc can go ahead and beta. > >Bitcoin-stable may pull validated changes and merge them, as a way to pull >in any features needed in the shorter term and benefit from the betacoin >validation. (Testing isnt as much validation as real-money at stake >survivability). > >The arguments are I think that: > >- it allows faster development allowing bitcoin to progress features faster, > >- it avoids mindshare dilution if alternatively an alt-coin with a hit > missing feature takes off; > >- it concentrates such useful-feature alt activities into one OPEN source > and OPEN control foundation mediated area (rather than suspected land > grabs on colored fees or such like bitcoin respun as a business model > things), > >- maybe gets the developers that would've been working on their pet > alt-coin, or their startup alt-coin to work together putting more > developers, testers and resources onto something with open control (open > source does not necessarily mean that much) and bitcoin mindshare > branding, its STILL bitcoin, its just the beta network. > >- it respects the 21 million limit, starting new mining races probably > dillutes the artificial scarcity semantic > >- while insulating bitcoin from betacoin security defects (I dont mean > betacoin as a testnet, it should have prudent rigorous testing like > bitcoin, just the very act of adding a feature creates risk that bitcoin > stable can be hesitant to take). > >Probably the main issue as always is more (trustable) very high caliber >testers and developers. Maybe if the alt-coin minded startups and >developers donate their time to bitcoin-beta (or bitcoin-stable) for the >bits they are missing, we'll get more hands to work on something of reusable >value to humanity, in parallel with their startup's objectives and as a way >for them to get their needed features, while giving back to the bitcoin >community, and helping bitcoin progress faster. > >Maybe bitcoin foundation could ask for BTC donations to hire more developers >and testers full time. $1.5b of stored value should be interested to safe >guard their value store, and develop the transaction features. > >Adam > >On Mon, May 20, 2013 at 02:34:06AM -0400, Alan Reiner wrote: >> This is exactly what I was planning to do with the >> inappropriately-named "Ultimate Blockchain Compression". [...] >> >> For it to really work, it's gotta be part of the mainnet validation >> rules, but no way it can be evaluated realistically without some kind of >> "staging". > >> On 5/19/2013 11:08 AM, Peter Vessenes wrote: >> >> I think this is a very interesting idea. As Bitcoiners, we often stuff >> things into the 'alt chain' bucket in our heads; I wonder if this idea >> works better as a curing period, essentially an extended version of the >> current 100 block wait for mined coins.