How would SPV proofs be verified when moving assets back in 2-way pegged sidechains?

Question

I've seen similar questions posted all around, but haven't found an answer I can comprehend.

Ok, so the process of 2 way pegging is:

1. I move some coins to OP_SPVPROOFVERIFY on the parent blockchain.
2. I wait for some time (e.g. 1 day)
3. I get coins on the sidechain, transact.
4. Now, I want to move some of those coins back to the parent/main blockchain.
5. I send them to a special address on the sidechains, and they are now locked on that chain.
6. ... magic magic
7. Now I can "SPV prove" that the coins are done with on the sidechain and are now free for transacting on the main chain.

How does step 6 work?

Assumptions

• Only a subset of the parent chain miners & spv & full nodes are aware this sidechain even exists
• The sidechain may use completely different proof of work, block format, address scheme (Or rather: what can a sidechain change compared to Bitcoin, and what is fixed?)

Under these assumptions, how can a full node running the parent chain recognize that the coins really vanished from the sidechain (of which they are not explicitly aware)? Remember, the parent full node isn't aware of the type of proof of work (if any) that happens on the sidechain, address scheme, really it only knows and speaks the language of Bitcoin, not the sidechain. So how does step 6 work?

Answer 1

Your question is spot on and poses the main problem of sidechain interfacing: How to prove to some chain (call it the "mainchain") that an event (such as a deposit) took place on a remote chain (call it the "sidechain").

As far as I'm aware there is as of yet no precise specific of how this works, but there are several approaches that can be taken. The approach usually taken here is to allow for a set of "functionaries" or "fishermen" to observe the transaction on the sidechain, wait for it to become confirmed there, and then vouch for the fact that it took place by signing off a statement (a "certificate") which attests to the fact that the transaction in the sidechain really took place. This can work well if there are some honesty assumptions about the functionaries, e.g., that the majority of them is honest. In that case, in practice, the withdrawal can really be a multisig check. This approach would work with the existing bitcoin implementation. This approach is very compatible with sidechains whose consensus is permissioned/byzantine, e.g. Plasma, Polkadot, Elements.

If you don't want to remain within the realm of bitcoin, there are more elegant solutions with different trust assumptions that can be realized. If you dislike the threat model of a centralized group of functionaries (or a "federation" thereof) and you want to go completely trustless, you need to produce a proof of a remote event in a decentralized manner. This proof will need to have the form of a simple string which attests to the fact that something happened on the remote chain, even if the local miners do not connect to that remote chain and do not know how its consensus works.

If the sidechain has Proof-of-Work consensus, then these proofs make a claim which attests to the fact that sufficient proof-of-work took place to bury a transaction on the remote chain. As they prove that proof-of-work took place, they are "Proofs of Proof-of-Work" (PoPoWs). The verification of such proofs is not a trivial manner and bitcoin does not have an opcode to do this currently, nor is there any support being planned. Hence, such schemata would be possible when the mainchain is a Turing-complete blockchain or supports a PoPoW opcode (unlikely).

On the other hand, the sidechain has to support the generation of these proofs too. This can be built-in to the chain, like ERGO, WebDollar, or Nimiq. A blockchain without PoPoW support can add it without soft forking and without miner approval by conducting an appropriate velvet fork.

Finally, these PoPoWs have to be produced by sidechains maintainers in a "one-shot" attempt that generates a simple string and they should not require interaction, i.e., they should be Non-Interactive Proofs of Proof-of-Work (NIPoPoWs). Given these ingredients, you can do it in a completely trustless manner.

All of the above constructions pre-suppose that the sidechain and mainchain survive securely independently. For example, the sidechain needs to have honest majority computation power if it's PoW-based.

To summarize, bitcoin does not currently have a way to do what you're asking in a trustless manner, but there are federated / cothority ways to do it. If you're willing to work on new systems, you can do it in a decentralized manner.

Disclaimer: I am one of the co-authors of the Non-Interactive Proofs of Proof-of-Work paper.

Answer 2

The first important thing to understand is that this method is one of two different ways of moving coins back and forth between two chains. The other is called Federated Peg, which I believe will be more successful despite being less technically sophisticated and more centralized.

General concept

The first step is that you send a transaction on the sidechain that locks your money in place. Once that transaction has a few confirmations, you create the SPV proof to send to the mainchain.

Let's go into more detail about that last step:

When you run an SPV client, your client doesn't download full blocks. It downloads headers. Then, it downloads the transactions to or from your wallet. Then, it downloads the merkle branches to connect your transaction to one of the block headers.

When you create an SPV proof, you take those block headers that you downloaded, and those merkle branches that you need to connect to your transaction, and your special coin-locking transaction, and you serialize them into a single datastructure.

Why do we need to serialize the SPV proof at all?

…can't the nodes checking the SPV proof ask nodes on the sidechain to provide the SPV data?

No, because the sidechain nodes might reply differently to different mainchain nodes. That would result in a fork of the mainchain. A serialized SPV proof will be evaluated the same way by all mainchain nodes.

Some complications

SPV proof might not match sidechain network

If I have lots of mining power, I don't need to have money on the sidechain in order to withdraw money from sidechain outputs on the mainchain. (i.e. I can fake a sidechain withdrawal.)

This is how it works: I create a transaction from a fake output on the sidechain. If I broadcasted this to the sidechain, all of the nodes would reject it. However, I mine a block containing this transaction, and I keep going until I get enough blocks that the mainchain will trust my SPV proof.

Mitigations

1. Require more confirmations before moving money from sidechain to mainchain
2. Create a grace period where someone can block your withdrawal by creating a 'counter SPV proof,' which shows a longer chain of proof of work that does not include your block header.
3. When the sidechain detects that someone successfully stole money, it marks down all future withdrawals to avoid a bank run.

What you're depositing won't match what you're withdrawing

If you're using the sidechain for transactions, you're going to wind up with more or less than when you started. However, this is a softfork, so we can't just deposit all of the incoming funds into a single pot. All of the funds are spread around many different outputs, and in Bitcoin, you need to entirely spend any output you claim. (You can't partially claim an output.) There are two solutions to this:

1. Lock up the exact amount of money of an output on the mainchain, then claim that. Potentially do this many times. This is simple, but has two problems: first, it uses more blockchain space than nessary; second, if there is no set of outputs that add up precisely to what you're withdrawing, some of your money will be stuck in the sidechain.

2. Allow people to claim one or more outputs, and optionally send change to another OP_SPVPROOFVERIFY output. This solution is much more flexible, but has some hidden teeth. (Can you accidentally send an 80 BTC miner fee because you screwed up your javascript? Will people have an incentive to avoid the dust outputs, leading to a bunch of outputs that nobody wants to pay to redeem?)

Things that aren't complications

Nodes on the mainchain that don't understand OP_SPVPROOFVERIFY

Since this is a softfork, not all nodes have to upgrade.

What can be changed in a sidechain?

Since we're supposing that we're designing a new opcode from scratch, we can make it support many different things. It could support Scrypt, X11, whatever hashing algorithm we want. It can't support pure Proof of Stake in a meaningful way. It could support multiple different target times, address types, etc.

However, it can't support unanticipated changes, so if someone comes up with a brilliant change that's visible to SPV clients, it won't work with the above.

Well, that's not entirely true. You could create two instructions, OP_SPVPROOFCHECKERREGISTER, and OP_SPVPROOFVERIFY. The first one would register an ethereum-like script that could keep state, and would check all incoming redemption requests. The second would commit a sum of money until the former script said that it could be unlocked. That would allow arbitrary SPV proof systems (although it still wouldn't allow pure PoS systems) at the cost of increased complexity.