Terminology:SPV: Simplified Payment Verification. How non-fully-validating wallets have trust in your balance. Basically a chain of block headers that proves that a certain amount of work has happened after a particular txn was posted.
https://en.bitcoin.it/wiki/Scalability#Simplified_payment_verificationSPV proof of burn: Someone who wants to "reanimate" coins on the bitcoin blockchain (chain A) needs to submit proof that the coins were spent on chain B into the 1chainAxfer (well known unspendable address -- i.e. the coins were "burned" on that chain) AND that sufficient work has been done subsequently to make it unlikely that a fork will unroll this spend. Rather than force the chain A miners to access the chain B blockchain, the entity who wants to "reanimate" the coin gathers all this information into a "proof" and submits it as part of the "reanimate" transaction.
Security Firewall: Ensure that no matter what happens on side-chains, people/coins that have only been used on the main chain remain unaffected. Most importantly, no accidental inflation.
1-way peg: This refers to moving bitcoins to a sidechain. To understand the term, note that if it is possible to move bitcoins to the sidechain, the price of the sidechain coins cannot exceed that of 1 bitcoin. The price is "pegged". If ever did exceed 1 bitcoin did people would simply move bitcoins to the sidechain and sell them...
2-way peg: This refers to moving bitcoins to a sidechain and back. This functionality "pegs" the price of the sidechain coin to that of bitcoin because any deviation simply allows people to move coins to the lower priced chain and sell them.
References:This chat is really the best description:
http://download.wpsoftware.net/bitcoin/wizards/2013-12-18.txt00:24:30 <BlueMatt> are there any serious or semi-serious proposals for how to fix an altcoin 1:1 to bitcoin without a large cost to bitcoin miners given some hardfork changes to bitcoin?
00:26:38 <gmaxwell> if not for the disabled operators you could probably do it without hardfork changes to bitcoin, though you would only have SPV security in the altcoin-bitcoin direction.
00:27:16 <BlueMatt> even getting spv security in the altcoin-> bitcoin direction is non-trivial, no?
00:27:26 <BlueMatt> (given hardfork to reenable opcodes)
00:27:54 <BlueMatt> you'd have to have the whole chain history, or some subset starting from the time of the bitcoin->altcoin transfer
00:28:03 <BlueMatt> well, whole block-header-chain-history
00:28:27 <gmaxwell> yea, you just write a script that can do a spv validation and then takes a chunk of headers of a prespecified sufficient difficulty.
00:28:44 <gmaxwell> the proof can start at the point the txn of interest was mined.
00:28:45 <BlueMatt> that gets pretty expensive?
00:28:57 <gmaxwell> I mean, it's 80 bytes per header. so not really.
00:29:02 <BlueMatt> very expensive if you hold the alt for an extended period...
00:29:21 <BlueMatt> well, no miner is gonna mine a tx that is 80 bytes*N where N is a few weeks/months of headers
00:29:24 <gmaxwell> BlueMatt: oh no, you don't do it over the life of the alt.
00:29:32 <gmaxwell> crazy no no thats not how it works.
00:30:25 <gmaxwell> you take some coin and assign it to a scriptPubKey that can be redeemed by anyone who provide a SPV fragment from the altcoin showing any of those coins being reassigned back to bitcoin, with a sum difficulty of at least X.
00:30:47 <adam3us> gmaxwell, BlueMatt: a 1:1 peg - doesnt that import security risk from the alt into bitcoin? (i suggested a 1 way peg "bitcoin staging" only so bitcoin is security firewalled) are we talking about the same area of feature
00:31:39 <gmaxwell> adam3us: only to the limit of the alt. say the alt was somehow totally insecure... you could then steal all the bitcoins that had been assigned to the altcoin.
00:31:44 <gmaxwell> but no more.
00:32:01 <adam3us> gmaxwell: hmm that might be ok
00:32:18 <BlueMatt> adam3us: what gmaxwell said (if you decide to put your btc in the alt, sucks for you)
00:32:43 <gmaxwell> BlueMatt: one problem there is that isn't really spv security, its "spv transcript" security, in that the bitcoin network isn't going to go out and find a longer chain.
00:32:48 <adam3us> BlueMatt: yes that is an acceptable trade off and already at risk with a 1-way peg
00:33:20 <gmaxwell> BlueMatt: But I did come up with a way to boost that to more like real SPV security with a bit more script power.
00:33:33 <BlueMatt> gmaxwell: well, ok, sum difficulty is one way...but very non-ideal
00:34:18 <gmaxwell> (you make the relase of coins back into bitcoin two phase. The first phase you do a header proof for the release.. and that gets mined.. but it can only output to a special holding script with the following rules:
00:35:13 <gmaxwell> after N blocks the releasing party can grab the coins. OR at any point, any party can show a longer chain to prove the release was bogus. and then they can only be redeemed with a new release on a chain longer than that one.
00:35:55 <gmaxwell> In any case I think most of the stuff thats been said of any technical substance on this is in the coinwitness thread (where I suggest using SNARKs for C to compact the proofs, though its not essential):
https://bitcointalk.org/index.php?topic=277389.000:36:17 <gmaxwell> obviously if you compact the proofs things start sounding more interesting from a scaling perspective.
00:37:04 <gmaxwell> also if the headers of the altcoin form a MMR (insertion ordered binary tree) it may be cheaper to prove long spans of difficulty.
00:37:09 <BlueMatt> yea, though depending on cutting-edge crypto is ugly...
00:38:02 <gmaxwell> BlueMatt: well there are less ambitious (efficiency wise) ways to construct these proofs, but they're larger... though I'm not sure if we could get the direct proofs down with special support. Maybe.
00:38:08 <gmaxwell> SPV fragments can be pretty small.
00:39:02 <BlueMatt> yea, its all a bit expensive, really
00:39:23 <BlueMatt> it would be fun to be able to peg arbitrary altcoins to bitcoin as it really addresses the issues altcoins cause
00:40:02 <BlueMatt> allows them to innovate (ie risk people's money) while not costing bitcoin's digital scarcity/competing on store-of-value
00:40:51 <gmaxwell> BlueMatt: one way is easy— just have them validate bitcoin too.
00:40:55 <adam3us> BlueMatt: agreed
00:41:57 <gmaxwell> BlueMatt: one point is that you could coinjoin your cross chain merges perhaps, to make them smaller. e.g. one proof and then a dozen transactions hop the gap.
00:44:18 <BlueMatt> gmaxwell sure, but if you only peg one-way its really not particularly useful
00:44:40 <BlueMatt> well, it is, but not as useful
00:44:54 <BlueMatt> gmaxwell: sure, you could limit to like 1 coinjoin'd alt->btc tx per day
00:45:03 <BlueMatt> but even that could be expensive
00:45:29 <gmaxwell> I dunno, I mean, it's a seralized transaction and spv proof, plus some additional headers.
00:45:43 <BlueMatt> well, if you have 100 alts all doing that, it does
00:46:04 <adam3us> BlueMatt: I like 1:1 peg idea, I only suggested 1-way peg to insulate security, if you can insulate security to the coins in the alt, thats even better
00:47:41 <BlueMatt> as long as you limit it to the people who transferred their coins...
00:47:49 <BlueMatt> gmaxwell: hmm...
00:47:57 <gmaxwell> lets say there are 2^12 txn per altcoin block, ... lets imagine you make the altcoin txn themselves hashtree so you can get to only their outputs.. so say maybe 64 bytes for the altcoin output, 384 bytes for the spv tree. 4 bytes for a spv index, and 12 80 byte headers = 1.4k.
00:48:15 <gmaxwell> it's bigger than a typical ecdsa signature, but not murderous.
00:48:48 <gmaxwell> and if they coinjoin the biggest parts (960 bytes of headers, 384 bytes of hashes) can be shared.
00:49:56 <gmaxwell> adam3us: yea, I don't think there is a security need to make it one way. If you can never "pull back" more from an altcoin than was sent to it, then only the holders of the altcoin are at risk.
00:50:43 <adam3us> gmaxwell: seems plausible indeed, i just didnt think of it in those terms at the time. good
00:51:22 <gmaxwell> the altcoin is also a bitcoin node, and monitors bitcoin for coins assigned to the altcoin, and then permits someone on the altcoin to emerge those coins from thin air.. and then when you want to send them back you make a special transaction in the altchain and prove you did it to bitcoin.
00:51:23 <adam3us> gmaxwell: i suppose the other thing is it itself requires bitcoin changes, perhaps non-trivial ones, and that is part of the reason for the exercise.
00:51:46 <gmaxwell> yea, unfortunately it requires changes to bitcoin.
00:52:18 <gmaxwell> we could _almost_ do it in script without the disabled opcodes, but there are enough little corners that I suspect we can't.
2-peg side chain links:2-way pegging, Adam Back:
http://sourceforge.net/p/bitcoin/mailman/message/32108143/Description of skip-lists that can space-efficiently prove difficulty (SPV proof of burn):
The High-Value Hash Highway:
https://bitcointalk.org/index.php?topic=98986.0Compact SPV proofs via block header commitments:
http://sourceforge.net/p/bitcoin/mailman/message/32111357/