[bitcoin-dev] Softchains: Sidechains as a Soft Fork via Proof-of-Work Fraud Proofs

[Ruben Somsen <rsomsen@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 6645 bytes --]

Hi everyone,

This post describes a fully decentralized two-way peg sidechain design.
Activating new sidechains requires a soft fork, hence the name softchains.
The key aspect is that all softchains are validated by everyone via
Proof-of-Work Fraud Proofs (PoW FP) -- a slow but very efficient consensus
mechanism that only requires the validation of disputed blocks. This does
increase the validation burden of mainchain full nodes, but only by a
minimal amount (~100MB per chain per year). It's similar to drivechains[0],
but without the major downside of having to rely on miners, since all
Bitcoin full node users can efficiently validate each sidechain.


Proof-of-Work Fraud Proofs

Last year I posted the idea of PoW FP to the Bitcoin mailing list[1][2].
The idea is that we can use the existence of a fork in Bitcoin's PoW as
evidence that a block might be invalid (i.e. a proof of potential fraud).
Whenever this occurs, we download the block in question to verify whether
it was valid (and available), and reject it if it was not. We forego the
need for maintaining a UTXO set with UTXO set commitments (such as
utreexo[3]), by assuming that the commitment inside the last block to exist
in both forks is valid. As a result, we only need to download as many
blocks (and their corresponding UTXO set proofs) as there are orphans,
which lowers the validation costs considerably compared to running a full
node.

In the past 4 months, Forkmonitor has registered 11 stale and invalid
blocks[4]. Extrapolating from that data, a PoW FP node verifying Bitcoin
consensus would have to download and verify a little over 100MB per year in
order to have consensus guarantees that come close to that of a full node:
- All PoW headers (~4MB per year)
- 3 x 11 = 33 full blocks (~2MB x 33 = 66MB)
- UTXO merkle proofs (~1MB x 33 = 33MB with utreexo)

The reason consensus is considered slow, is because we need to allow time
for a honest PoW minority to fork away from an invalid chain. If we assume
only 1% of all miners are honest, this means consensus slows down by 100x.
If you are normally satisfied waiting for 6 confirmations, you now need to
wait 600 confirmations. The longer you wait, the less honest miners you
need.


Softchains

In order to have two-way pegged sidechains, you need a succinct method for
proving to the mainchain that a peg-out is valid. PoW FP provides exactly
that -- a low-bandwidth way of determining if a chain, and thus a peg-out,
is valid. The slowness of PoW FP consensus is not an issue, as peg-outs can
be made arbitrarily slow (e.g. one year).

The safest design would be a set of softchains that shares its consensus
code with Bitcoin Core, with the addition of UTXO set commitments, and
disabling non-taproot address types to minimize certain resource usage
issues[5]. All users validate the mainchain as usual with their full node,
and all softchains are validated with PoW FP consensus. If a user is
interested in directly using a specific softchain, they should run it as a
full node in order to get fast consensus.

Peg-ins occur by freezing coins on the mainchain and assigning them to a
softchain. Peg-outs occur by creating a mainchain transaction that points
to a peg-out transaction on a softchain and waiting for a sufficient number
of mainchain confirmations. If the peg-out transaction remains part of the
softchain according to PoW FP consensus, the coins become spendable.

The peg-in/peg-out mechanism itself would require a soft fork (the exact
design is an open question), and subsequently every softchain that gets
activated will also require a soft fork.


Potential dangers

Softchain consensus still requires a form of validation from mainchain
users, which means that consensus bugs can have an adverse effect. In
particular, if a softchain suffers from a non-deterministic consensus bug,
it may be the case that a majority accepts a peg-in, while a minority
rejects it. This specific scenario could cause a chain split in mainchain
consensus. This is why it would be safest to base softchain designs on
Bitcoin Core.

Similarly, it can theoretically be possible that a softchain gets a major
reorg, invalidating a peg-out right as it would have become accepted on the
mainchain, thus splitting consensus. The slow peg-out process makes this
increasingly unlikely, but not impossible. One thing that might help (or
perhaps only make it worse) is introducing a consensus rule that disallows
reorgs that are bigger than half the peg-out time (e.g. half a year, if the
peg-out is one year). This kind of rule does not actually solve this
consensus problem, but instead pushes the problem forward so it plays out
first on the softchain, giving time to take action before the problem
affects the mainchain.

It is also important that each softchain produces a non-trivial amount of
PoW, because if the difficulty is too low, the cost of creating forks and
increasing the resource usage of PoW FP consensus goes down. It may
therefore make sense to have a minimum accepted difficulty for softchain
blocks (slowing down the chain when fees are not sufficient). Merged Mining
could also help here, since that would allow the softchains to potentially
receive the same hashrate as Bitcoin (assuming all miners participate), but
of course this would also put an additional validation burden on miners.


In closing

It may turn out that the consensus risks outlined above make this
prohibitively risky, but at the very least it seems worth exploring the
possibilities. At a minimum it would provide more opt-in block space, and
it could potentially open the door to chains with entirely different
consensus rules.

Thank you for taking the time to read and comprehend my work. I will
happily answer any questions and I look forward to any feedback on issues
that I might have overlooked, and ideas on mitigating problems to ensure
maximum safety.

Hopefully this will bring decentralized two-way peg sidechains one step
closer to becoming a reality.

Happy new year, everyone.


-- Ruben Somsen



This post is mirrored and kept up-to-date here:
https://gist.github.com/RubenSomsen/7ecf7f13dc2496aa7eed8815a02f13d1


[0] Drivechains
https://www.drivechain.info/

[1] PoW FP
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-April/016873.html

[2] PoW FP without a soft fork
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017287.html

[3]: utreexo
https://eprint.iacr.org/2019/611.pdf

[4]: Forkmonitor
https://forkmonitor.info/notifications

[5]: Harding on worst-case utreexo
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017298.html

[-- Attachment #2: Type: text/html, Size: 7586 bytes --]