Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 2CC29C013A for ; Thu, 31 Dec 2020 22:00:33 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 2651D87096 for ; Thu, 31 Dec 2020 22:00:33 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id i8urxN0BWPW6 for ; Thu, 31 Dec 2020 22:00:31 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-ed1-f48.google.com (mail-ed1-f48.google.com [209.85.208.48]) by whitealder.osuosl.org (Postfix) with ESMTPS id 46A0687092 for ; Thu, 31 Dec 2020 22:00:31 +0000 (UTC) Received: by mail-ed1-f48.google.com with SMTP id h16so19147614edt.7 for ; Thu, 31 Dec 2020 14:00:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=c3p7hfNEt5M6CwK4gQ5MGl8f2CCvlSkIMjBp9mAmtD4=; b=uqv9Bh3xdMoq2zGcp2Og41idOM4o35Zvsd5vKUvhpxfhvM4QVOtvQMLNbS+b2fB036 hwXp1oOwt1WMfTArlABvXFr9O/sxtnaZjPARHAgvznF/z4piJymLq5lmLTHvOUwP9eE8 Qy8u22/nbfbMxJQ1GcQREVp7tcQ71k7jNCloUUyxXWzEKv5mit/RCc2iTbauntyen12M 0M+L/XudvOOFnmo2K4KDVLiNDWDo7H4Q5wRac4TCUiwtPKGm9HKVg9jt1Y40RLML2yTI MZF1Q0IHDP1Gf8Hne0QoqFx1yFR6SPX3vKlA+SbpgCVKghzxda9iMyhtPH5b+V2t9z4N 0KaA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=c3p7hfNEt5M6CwK4gQ5MGl8f2CCvlSkIMjBp9mAmtD4=; b=ggEV5WIPBt8aiRdmLkc8CeGwPaseJHMQG2IXG5EczA/mPishv83Sjr+JI2o7ci0N7M lYnAt3QY7goEAp6qssg00rS3GbNymNVrIh2bY0xLsrSH+/Mnrb9wvKK3xSUTGOwFiahI 0c+8dXxDVsquApgKv1KbfqpAeKqz2Ks//iYeeRaJq2CSBLwMfGY8qtl0Cr9eY2K8KYGL 4a441UNlZCky4ytzAOd8hAwZ8zRqpmDIgZHYf/j2zm3O5NT6Gv4n/5wbRwmoqJJdO0LT CWSqH4nMMVngyLQ44u7ELIoBTq2vw0Wl4QWUvH6n4AUJV8AbFcNyMIV80ANSBZEIFEg8 UijQ== X-Gm-Message-State: AOAM5329aq2mUezibc7IYQ6gUa5oXi+ytn4dteMC8BXCF+thz863mmP4 sx+Rb9LuXoM5D2T2vJil6+V1hg8RKHfAoV62RhB5D9ucA7KH9A== X-Google-Smtp-Source: ABdhPJyjKgHLgAQ8Z+0RIpfrTGt5lP7yMui8VgnghXs/mbDNwgePoxWjDQQjE1w4Ir85KBLfKM58Rywq/sg9ccQopO4= X-Received: by 2002:aa7:db14:: with SMTP id t20mr56372554eds.158.1609452029441; Thu, 31 Dec 2020 14:00:29 -0800 (PST) MIME-Version: 1.0 From: Ruben Somsen Date: Thu, 31 Dec 2020 23:00:17 +0100 Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="0000000000007f7b0305b7c9c0fd" X-Mailman-Approved-At: Thu, 31 Dec 2020 22:00:59 +0000 Subject: [bitcoin-dev] Softchains: Sidechains as a Soft Fork via Proof-of-Work Fraud Proofs X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 31 Dec 2020 22:00:33 -0000 --0000000000007f7b0305b7c9c0fd Content-Type: text/plain; charset="UTF-8" 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 --0000000000007f7b0305b7c9c0fd Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi everyone,

This post describes = a fully decentralized two-way peg sidechain design. Activating new sidechai= ns 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 (Po= W FP) -- a slow but very efficient consensus mechanism that only requires t= he 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 efficien= tly validate each sidechain.


Proof-of-Work Fraud Proofs

L= ast 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 ev= idence that a block might be invalid (i.e. a proof of potential fraud). Whe= never this occurs, we download the block in question to verify whether it w= as valid (and available), and reject it if it was not. We forego the need f= or maintaining a UTXO set with UTXO set commitments (such as utreexo[3]), b= y 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 valid= ation costs considerably compared to running a full node.

In the pas= t 4 months, Forkmonitor has registered 11 stale and invalid blocks[4]. Extr= apolating from that data, a PoW FP node verifying Bitcoin consensus would h= ave to download and verify a little over 100MB per year in order to have co= nsensus guarantees that come close to that of a full node:
- All PoW hea= ders (~4MB per year)
- 3 x 11 =3D 33 full blocks (~2MB x 33 =3D 66MB)- UTXO merkle proofs (~1MB x 33 =3D 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 a= ll miners are honest, this means consensus slows down by 100x. If you are n= ormally satisfied waiting for 6 confirmations, you now need to wait 600 con= firmations. The longer you wait, the less honest miners you need.

Softchains

In order to have two-way pegged sidechains, you ne= ed 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 cha= in, and thus a peg-out, is valid. The slowness of PoW FP consensus is not a= n issue, as peg-outs can be made arbitrarily slow (e.g. one year).

T= he safest design would be a set of softchains that shares its consensus cod= e with Bitcoin Core, with the addition of UTXO set commitments, and disabli= ng non-taproot address types to minimize certain resource usage issues[5]. = All users validate the mainchain as usual with their full node, and all sof= tchains are validated with PoW FP consensus. If a user is interested in dir= ectly using a specific softchain, they should run it as a full node in orde= r to get fast consensus.

Peg-ins occur by freezing coins on the main= chain and assigning them to a softchain. Peg-outs occur by creating a mainc= hain transaction that points to a peg-out transaction on a softchain and wa= iting for a sufficient number of mainchain confirmations. If the peg-out tr= ansaction remains part of the softchain according to PoW FP consensus, the = coins become spendable.

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

<= br>
Potential dangers

Softchain consensus still requires a= form of validation from mainchain users, which means that consensus bugs c= an 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 c= hain split in mainchain consensus. This is why it would be safest to base s= oftchain 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 consensu= s. The slow peg-out process makes this increasingly unlikely, but not impos= sible. One thing that might help (or perhaps only make it worse) is introdu= cing a consensus rule that disallows reorgs that are bigger than half the p= eg-out time (e.g. half a year, if the peg-out is one year). This kind of ru= le does not actually solve this consensus problem, but instead pushes the p= roblem forward so it plays out first on the softchain, giving time to take = action before the problem affects the mainchain.

It is also importan= t 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 resour= ce 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 t= hat would allow the softchains to potentially receive the same hashrate as = Bitcoin (assuming all miners participate), but of course this would also pu= t an additional validation burden on miners.


In closi= ng

It may turn out that the consensus risks outlined above make this= prohibitively risky, but at the very least it seems worth exploring the po= ssibilities. 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 e= nsure maximum safety.

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

Happy new ye= ar, everyone.


-- Ruben Somsen

--0000000000007f7b0305b7c9c0fd--