Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 142EFC013A for ; Fri, 1 Jan 2021 00:06:39 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 03EAD87511 for ; Fri, 1 Jan 2021 00:06:39 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 1wy5KYR5hRTC for ; Fri, 1 Jan 2021 00:06:37 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-ej1-f44.google.com (mail-ej1-f44.google.com [209.85.218.44]) by hemlock.osuosl.org (Postfix) with ESMTPS id 37C00852D9 for ; Fri, 1 Jan 2021 00:06:13 +0000 (UTC) Received: by mail-ej1-f44.google.com with SMTP id b9so26907864ejy.0 for ; Thu, 31 Dec 2020 16:06:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=MsjzaaoTo4fI3jBZsEk2ZDunSB4NZuoTq27eSzy/w0U=; b=Swn1Z9918vsu/B2tHDxsMHrN45+bsOfA8oPu5h0LR0TzgeI7ktnIa9q/2vyVRTioJ9 b9TG1h3SNHi1ft17eXZt1tYGWX0mxzTMliNWfP4R0Kqq6h+8FKMTmkxRa89z5OByb7tF mmUmHYFPxJVJ5pLOLu1Mfe3r1bhmuVNYpWDlpc79zo/ZFZa6PFfKqG5OJtsFZ1d7xQvt OrRF6iV8hs0NsVHij5GkKc3HpRUHFshGOvTTp8hspp5eBrO2NWoiv60BAtaTwO/RYwDy r++Ej+MxiFTKW/oBs1BcRi3eKOHnpSy4O5c/kPpLk60C0Esau6ly/aTstwgsQkBLI4Gn tXKQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=MsjzaaoTo4fI3jBZsEk2ZDunSB4NZuoTq27eSzy/w0U=; b=SRFwlmaqdMh232wgZxI7YiHjAiGBYdckrHk4Okq1Vy3dTIhFPh3w1VzzFbONLsi6/H 0PAbnTpeCDDo9Lw9TKMtX4ewY5I3q9uceUXjyvHAh1ltjFX0vYwFzAyH3ksMcKYogHiw svGabqWJ9FVaCwLyzWy8qOXH8ZBmZaqkvZdMlaxvZhgYmUOUY/DXKDo2zeYjtU1HQUve 7/PtiT4n36VlR2sT+zb69UOGS2SK++YzFJY9oXjKvWsLEV/FGoQSJpZP7IQQNi0b8s/k BSmH3Fh5X1zSU8u7FNftuZtiUPoC/CsFhhFbjaF47phXYNiHCk7D4qrLUE/bq9vDDd7/ TOXA== X-Gm-Message-State: AOAM530B1QpgM4low9aX8SP8/9K++UzNPRTdBb34fgXw2J6ovH1TuKwX qd0ptUUxIdiwHkFmwxN0EJNtGjp7eRg4cCd8At8= X-Google-Smtp-Source: ABdhPJztu1qf9noNVW2Xvy8Tp1ZzuAzRCpp+Unft2WlwEiuVU8b5PEHSyRRRO50lrfwkN144RZTKexTa0v5zhHWMcrg= X-Received: by 2002:a17:907:3fa3:: with SMTP id hr35mr55258769ejc.71.1609459571444; Thu, 31 Dec 2020 16:06:11 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Ruben Somsen Date: Fri, 1 Jan 2021 01:05:59 +0100 Message-ID: To: Sergio Demian Lerner Content-Type: multipart/alternative; boundary="000000000000094f9105b7cb82fc" X-Mailman-Approved-At: Fri, 01 Jan 2021 00:18:55 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [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: Fri, 01 Jan 2021 00:06:39 -0000 --000000000000094f9105b7cb82fc Content-Type: text/plain; charset="UTF-8" Hi Sergio, Thanks for taking an interest. >I don't understand how your proposal prevents miners proposing a peg-out for an invalid sidechain fork which is not made available to the nodes (there are missing blocks) Good question. Data availability is a common problem for sidechain designs, but PoW FP are actually a unique solution to this problem. In order for a block with missing data to be accepted for a peg-out, it has to a.) remain in the chain with the most PoW for a whole year, and b.) no fork that questions the validity/availability of that block must exist. If a fork does exist, this triggers all nodes to attempt to download the block with the missing data. Since they will fail, the chain will be considered invalid. I recommend reading the original posts about PoW FP ([1] and [2] in my original post) for more elaboration. >it is very limited in the types of sidechains it can verify I agree that something like drivechains is much more flexible, but it comes with a security tradeoff that many find uncomfortable. >based on both a large multisig AND a drivechain, where both groups need to agree for the peg-out to occur. It's a censorship/security trade-off that most users would be willing to accept I think federations are an absolutely fine tradeoff, but of course the softchain design is one that deliberately tries to avoid them for reasons that I assume are obvious. >until a trusted-setup-free SNARK-like based solution is finally available From my research into SNARKs I concluded that they still won't get you away from having the sidechain function like an extension block, so the fruit doesn't seem to be hanging that low from my perspective. This is because SNARKs actually do suffer from the data availability problem you were asking about. You can definitely save a lot by aggregating witness data with SNARKs, but non-witness data cannot be aggregated and must be downloaded by everyone, so you're still going to be restricted by bandwidth. I described the issue here in detail: https://medium.com/@RubenSomsen/snarks-and-the-future-of-blockchains-55b82012452b Cheers, Ruben On Fri, Jan 1, 2021 at 12:38 AM Sergio Demian Lerner < sergio.d.lerner@gmail.com> wrote: > Hi Roben, > It's an interesting proposal, but I have two issues with it, one > technical and one philosophical. > > On the technical side, I don't understand how your proposal prevents > miners proposing a peg-out for an invalid sidechain fork which is not made > available to the nodes (there are missing blocks). It seems that the system > would need to allow users to challenge miners to make available full > sidechain blocks that are missing, which really complicates the protocol. > > On the philosophical side, as you mentioned, it is very limited in the > types of sidechains it can verify. I won't be able to verify RSK > (merge-mined with Bitcoin, but with different block format and different > functionality). It cannot verify a zCash-like sidechain for the same > reasons. Therefore it is strictly a payment scalability solution. > Drivechains, on the other hand, enable many new use cases apart from > scaling, which have a much lower level of complexity (if implemented > correctly). > > Since the inception of RSK sidechain, I suggested in its white-paper that > sidechains should be designed to support an hybrid peg-out system, based on > both a large multisig AND a drivechain, where both groups need to agree for > the peg-out to occur. It's a censorship/security trade-off that most users > would be willing to accept until a trusted-setup-free SNARK-like based > solution is finally available. > Until we have a sidechain-selectable SNARK-like succinct verification of > any block state transition function, having a single succint proof to cover > the whole sidechain validity, as in Coda (now renamed Mina), drivechains > are the low-hanging-fruit. > > regards > > On Thu, Dec 31, 2020 at 7:01 PM Ruben Somsen via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> 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 >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > --000000000000094f9105b7cb82fc Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Sergio,

Thanks for taking an interes= t.

>I don't understand how your proposal pr= events miners proposing a peg-out for an invalid sidechain fork which is no= t made available to the nodes (there are missing blocks)

=
Good question. Data availability is a common problem for sidecha= in designs, but PoW FP are actually a unique solution to this problem. In o= rder for a block with missing data to be accepted for a peg-out, it has to = a.) remain in the chain with the most PoW for a whole year, and b.) no fork= that questions the validity/availability of that block must exist. If a fo= rk does exist, this triggers all nodes to attempt to download the block wit= h the missing data. Since they will fail, the chain will be considered inva= lid. I recommend reading the original posts about PoW FP ([1] and [2] in my= original post) for more elaboration.

>it is ve= ry limited in the types of sidechains it can verify

I agree that something like drivechains is much more flexible, but it com= es with a security tradeoff that many find uncomfortable.

>based on both a large multisig AND a drivechain, where both gro= ups need to agree for the peg-out to occur.=C2=A0 It's a censorship/sec= urity trade-off that most users would be willing to accept

I think federations are an absolutely fine tradeoff, but of course= the softchain design is one that deliberately tries to avoid them for reas= ons that I assume are obvious.

>until a trusted= -setup-free SNARK-like based solution is finally available

From my=C2=A0research into SNARKs I concluded that they still won&= #39;t get you away from having the sidechain=C2=A0function like an extensio= n block, so the fruit doesn't seem to be hanging that low from my persp= ective. This is because SNARKs actually do suffer from the data availabilit= y problem you were asking about. You can definitely save a lot by aggregati= ng witness data with SNARKs, but non-witness data cannot be aggregated and = must be downloaded by everyone, so you're still going to be restricted = by bandwidth. I described the issue here in detail:

Cheers,
Ruben
=


=C2=A0=C2=A0

On Fri, Jan 1, 2021 = at 12:38 AM Sergio Demian Lerner <sergio.d.lerner@gmail.com> wrote:
Hi Roben= ,
=C2=A0It's an interesting=C2=A0proposal, but I have two issues wi= th it, one technical and one philosophical.

On the= technical side, I don't understand how your proposal prevents miners p= roposing a peg-out for an invalid sidechain fork which is not made availabl= e to the nodes (there are missing blocks). It seems that the system would n= eed to allow users to challenge miners to make available full sidechain blo= cks that are missing, which really complicates the protocol.=C2=A0

On the philosophical side, as you mentioned, it is very li= mited in the types of sidechains it can verify. I won't be able to veri= fy RSK (merge-mined with Bitcoin, but with different block format and diffe= rent functionality). It cannot verify a zCash-like sidechain for the same r= easons. Therefore it is strictly a payment scalability solution. Drivechain= s, on the other hand, enable many new use cases apart from scaling, which h= ave a much lower level of complexity (if implemented correctly).
=
Since the inception of RSK sidechain, I suggested in its whi= te-paper that sidechains=C2=A0should be designed to support an hybrid peg-o= ut system, based on both a large multisig AND a drivechain, where both grou= ps need to agree for the peg-out to occur.=C2=A0 It's a censorship/secu= rity trade-off that most users would be willing to accept until a trusted-s= etup-free SNARK-like based solution is finally available.
Until we have a sidechain-selectable SNARK-like succinct=C2=A0verificatio= n of any block state transition function, having a single succint proof to = cover the whole sidechain validity, as in Coda (now renamed Mina), drivecha= ins are the low-hanging-fruit.=C2=A0

<= div>regards

On Thu, Dec 31, 2020 at 7:01 PM Ruben Somsen via bitcoin-d= ev <bitcoin-dev@lists.linuxfoundation.org> wrote:
Hi everyo= ne,

This post describes a fully decentralized two-way p= eg 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 effici= ent consensus mechanism that only requires the validation of disputed block= s. This does increase the validation burden of mainchain full nodes, but on= ly by a minimal amount (~100MB per chain per year). It's similar to dri= vechains[0], but without the major downside of having to rely on miners, si= nce all Bitcoin full node users can efficiently validate each sidechain.

Proof-of-Work Fraud Proofs

Last year I posted the idea of P= oW FP to the Bitcoin mailing list[1][2]. The idea is that we can use the ex= istence of a fork in Bitcoin's PoW as evidence that a block might be in= valid (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 r= eject 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 compar= ed to running a full node.

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

The reason consensus is considered slow, i= s 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 mean= s 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 ord= er to have two-way pegged sidechains, you need a succinct method for provin= g 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 vali= d. The slowness of PoW FP consensus is not an issue, as peg-outs can be mad= e 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 a= ddition of UTXO set commitments, and disabling non-taproot address types to= minimize certain resource usage issues[5]. All users validate the mainchai= n 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 softchai= n, 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 s= oftchain. Peg-outs occur by creating a mainchain transaction that points to= a peg-out transaction on a softchain and waiting for a sufficient number o= f mainchain confirmations. If the peg-out transaction remains part of the s= oftchain according to PoW FP consensus, the coins become spendable.

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


Potential dangers=

Softchain consensus still requires a form of validation from mainch= ain users, which means that consensus bugs can have an adverse effect. In p= articular, if a softchain suffers from a non-deterministic consensus bug, i= t may be the case that a majority accepts a peg-in, while a minority reject= s it. This specific scenario could cause a chain split in mainchain consens= us. This is why it would be safest to base softchain designs on Bitcoin Cor= e.

Similarly, it can theoretically be possible that a softchain gets= a major reorg, invalidating a peg-out right as it would have become accept= ed on the mainchain, thus splitting consensus. The slow peg-out process mak= es this increasingly unlikely, but not impossible. One thing that might hel= p (or perhaps only make it worse) is introducing a consensus rule that disa= llows 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 affec= ts 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 go= es 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 pa= rticipate), but of course this would also put an additional validation burd= en on miners.


In closing

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

Thank you for ta= king the time to read and comprehend my work. I will happily answer any que= stions and I look forward to any feedback on issues that I might have overl= ooked, and ideas on mitigating problems to ensure maximum safety.

Ho= pefully this will bring decentralized two-way peg sidechains one step close= r to becoming a reality.

Happy new year, everyone.


-- Rub= en Somsen



This p= ost is mirrored and kept up-to-date here:
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000094f9105b7cb82fc--