For those following this thread, we have now written a paper
describing the side-chains, 2-way pegs and compact SPV proofs.
(With additional authors Andrew Poelstra & Andrew Miller).

http://blockstream.com/sidechains.pdf

Adam

On 16 March 2014 15:58, Adam Back <adam@cypherspace.org> wrote:
> 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.

------------------------------------------------------------------------------
_______________________________________________
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development