Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 489A9C002D for ; Fri, 4 Nov 2022 19:53:40 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 12D1B821C2 for ; Fri, 4 Nov 2022 19:53:40 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 12D1B821C2 Authentication-Results: smtp1.osuosl.org; dkim=pass (2048-bit key) header.d=protonmail.com header.i=@protonmail.com header.a=rsa-sha256 header.s=protonmail3 header.b=jHI4Cmr9 X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.102 X-Spam-Level: X-Spam-Status: No, score=-2.102 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id u1f5TMPYwoFB for ; Fri, 4 Nov 2022 19:53:38 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 96EB8821C1 Received: from mail-4322.protonmail.ch (mail-4322.protonmail.ch [185.70.43.22]) by smtp1.osuosl.org (Postfix) with ESMTPS id 96EB8821C1 for ; Fri, 4 Nov 2022 19:53:38 +0000 (UTC) Date: Fri, 04 Nov 2022 19:53:31 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail3; t=1667591616; x=1667850816; bh=v+SawYK3cVdFefG+8L62wsu5nU4kKIyINq+dtFphfbs=; h=Date:To:From:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector; b=jHI4Cmr9IRnnyDj6PwDEO3cEgk0sZxZrMgSn4Itmh78P4ejI+qyZhZO+CjllF/nkS 2jRgi4YFPJP+/DXSqLLGz5Mgxvdkv/3H3MXeOFkBI+Xfj7VzNAcjEGd9eCi70YS5Ci UpEzRrYtJEiiRfGqyHSnn50Gy7nWLjWu60EkBcSCj9K/stt107l89G7SB0Jodu14ps fKKmuzBbqe3cG6OXbgP6Y3pym/Nv185SJYnELFgykvPw56u4759WTDFwjEkPdUeVTN FSIvr66Ak3YwLMh9jT5seZDGf/OciqcPlJk1fmUFAnimkzBwFmDv5QJQdck3WcDN43 nhNWxij6Fm97g== To: AdamISZ , Bitcoin Protocol Discussion , John Light From: Trey Del Bonis Message-ID: <629da3d8-ee34-9acb-511b-4af1913eceff@protonmail.com> In-Reply-To: References: <689ed481-e7eb-4fea-8ca7-578503f3f285@app.fastmail.com> <224cf2f4-2577-4331-9977-ea71e9723ffe@app.fastmail.com> Feedback-ID: 18633789:user:proton MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Mailman-Approved-At: Fri, 04 Nov 2022 20:04:44 +0000 Subject: Re: [bitcoin-dev] Validity Rollups on Bitcoin 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, 04 Nov 2022 19:53:40 -0000 Hi all, I figured I could answer some of these rollup questions, There's a few different possibilities to make rollups work that have different tradeoffs.=C2=A0 The core construction I worked out in [1] involv= es a quine-ish recursive covenant that stores some persistent "state" as part of the beginning of the script which is then updated by the transaction according to rules asserted by the program and then constructs a new scriptPubKey that we assert is on the first output.=C2= =A0 This is apparently not a new idea, as I was recently made aware of that the sCrypt project does something similar to build a Solidity-looking stateful contract environment by using OP_PUSH_TX. Instead of that approach, I assume we have fairly granular transaction introspection opcodes from a list in Elements [2] (which seem like they aren't actually used in mainnet Liquid?) that can be used to implement covenants since the 520 byte limit means it's hard to pull data out of OP_PUSH_TX.=C2=A0 I also assume some math and byte manipulation opcodes (OP_ADD, OP_MUL, OP_CAT, OP_RIGHT, OP_LEFT, OP_SUBSTR, etc.) that were disabled years ago are re-added. One complicated part is the actual proof verification.=C2=A0 I had consider= ed looking into what it would take to build a verifying for a modern proof system if we used pairings as a primitive, but it turns out even that is pretty involved even in a higher level language (at least for PLONK [3]) and would be error-prone when trying to adapt the code for new circuits with differently-shaped public inputs.=C2=A0 The size of the code on-chain alone would probably make it prohibitively expensive, so it would be a lot more efficient just to assume we can introduce a specific opcode for doing a proof verification implemented natively.=C2=A0 The way I assumed it would work is taking the serialized proof, a verification key, and the public input as separate stack items.=C2=A0 The public input is the concatenation of the state and deposit commitments we took from the input, the batch post-state commitment (provided as part of the witness), data from transaction outputs corresponding to internally-initiated withdrawals from the rollup, and the rollup batch data itself (also passed as part of the witness). The parameters used in the PLONK system for the one zk-rollup I looked at give us a verification key size of 964 bytes and a proof size of 1088 bytes, which means that they're larger than the 520 byte stack element size limit so we'd actually have to use 2 stack elements for those.=C2= =A0 But that seems messy.=C2=A0 The worse issue though is the public inputs would probably blow way past the 520 byte stack element size limit, especially if we wanted to pack a lot of batch txs in there.=C2=A0 One solution to tha= t is by designing the proof verification opcode to take multiple stack elements, but the complexity to shuffle around the elements as we're getting ready to verify the proof seems like it would be extremely error prone and would further impact the size of the script.=C2=A0 The size of th= e script alone is very roughly around 1000 bytes. Other nice-to-haves: * something like OP_PUSHSCRIPT which would remove the need for the introspection the the prevout's script and avoids duplicating data in the witness * some kind of OP_MERKLEUPDATEVERIFY which checks a merkle proof for a leaf against a root *and* checks if replacing the leaf with some hash using the proof yields a specified updated root (or instead, a version that just pushes the updated root) * if we really wanted to golf the size of the script, then possibly a limited form of OP_EVAL if we can't figure out another way to split up the different spend paths into different tapleafs while still being able to do the recursive covenant, but still the script and the vk would still be significant so it's not actually that much benefit per-batch * a negative relative timelock to prevent a sniping issue I outlined in the doc It's probably possible that some of the introspection opcodes to look at outputs could be replaced with OP_CHECKTEMPLATEVERIFY and putting a copy of all the outputs on the stack, which combined with OP_PUSHSCRIPT means I think we wouldn't need any of the Elements-style introspection opcodes linked above, but it would be slightly messier and mean more data needs to get duplicated in the witness. It may be the case that there's enough issues with the above requirements that the safer path to take is just to soft-fork in Simplicity (or something like Chialisp as was suggested for consideration in a prior mailing list thread a while back [4]) with support for the necessary transaction introspection and go from there.= =C2=A0 Regardless of which option is decided upon, somehow we'll need to use a new witness version since there's non-soft-forkable requirements in any other case. Moving on, I had not considered the possibility that a non-zk optimistic rollup might be practical on Bitcoin.=C2=A0 I had assumed based on my understanding of existing ones that the amount of statefulness required across multiple transactions playing out the fraud game would make it infeasible, but it would be interesting to see if I was wrong. The current centralization in productionalized rollups definitely is a cause for concern.=C2=A0 I think it would be unwise to drop all restriction= s on who can submit a batch (since then a trivial DoS would be to just submit empty batches with a high fee rate as soon as the batch submission window opens, which would be more efficient at outcompeting an honest sequencer submitting nonempty batches), but a moderately large rotating set of sequencers (64 seems like a good number?=C2=A0 with some sequencer skipping mechanism if the next one fails to propose in time) is something that seems pretty possible without substantially changing the design. How you'd pick who gets to be in the quorum is another open question, but perhaps it could be based on using lightning nodes, which would be somewhat sibyl resistant since we could semi-verifiably check for long-lived nodes with a consistent level of activity as a proxy for honesty.=C2=A0 But that still feels like a centralizing force.=C2=A0 In pra= ctice I would expect several instances of these rollups with staggered batch submissions to run in parallel, hopefully with mostly disjoint sets of sequencers. -Trey [1] https://tr3y.io/articles/crypto/bitcoin-zk-rollups.html [2] https://github.com/ElementsProject/elements/blob/2dda79cf616e8928346eeb9e32= 82f5744955aa88/doc/tapscript_opcodes.md [3] https://github.com/matter-labs/zksync/blob/master/contracts/contracts/Plonk= Core.sol [4] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-March/020036.h= tml On 11/2/22 13:19, AdamISZ via bitcoin-dev wrote: > Hi John, > > Sorry for late feedback. Very much appreciated the in depth report! > > So, I second Greg's main question, which I've really been thinking about = a bit myself since starting to research this area more: it feels like the B= itcoin protocol research community (or, uh, some of it) should focus in on = this question of: what is the minimal functionality required onchain (via, = presumably soft fork) that enables something close to general purpose offch= ain contracting that is provable, ideally in zero knowledge, but at the ver= y least, succinctly, with onchain crypto operations. An example might be: i= f we had verification of bilinear pairings onchain, combined with maybe som= e covenant opcode, does it give us enough to do something like a rollup/sid= echain model with full client side computation and very compact state updat= e and verification onchain? (To be clear: just made that up! there is certa= inly no deep theory behind that particular combination .. although I did se= e this [1] thread on *optimistic* + covenant). > > Is the actual answer to this something like Simplicity? (Above my paygrad= e to answer, that's for sure!) > > Ideally you would want (don't laugh) for this to be the 'soft fork to end= all soft forks' so that innovation could all be then in higher layers. > > As to rollups themselves: centralization in the sequencer/publisher of st= ate updates seems to be a really big issue that's somewhat brushed under th= e carpet. Depending on the model, there are cases where it actually is a th= eft risk (e.g. full control of an onchain smart contract), but there's sign= ificant censorship risk at the very least, as well as availability/uptime r= isk. At the extreme, Optimism has a 'security model' [3] that is frankly la= ughable (though, no doubt it's possible that will radically change) and for= things like Arbitrum you have centralized sequencers, where the claim is t= hat it will migrate to a more decentralized model; maybe, but that's a huge= part of the challenge here, so while it's nice to see the sexy 'fast, chea= p, scale' aspect straight away, I feel like those models haven't done the h= ard part yet. I also think these optimistic L2 models have a 'fake finality= ' issue from my perspective; the delay needed onchain is how long it takes = to *really* confirm. (e.g > .: rollups look cool compared to sidechains from the pov of 'instant' i= nstead of confirmations on a chain, but that seems a bit sleight-of-hand-y)= . > > It's notable to compare that with a payment-channels style L2 where decen= tralization and trustlessness are sine-qua-non and so the limitations are m= uch more out in the open (e.g. the capacity tradeoff - while the 'instantne= ss' is much more real perhaps, with the appropriate liveness caveat). > > For the validity rollups, some of the above qualms don't apply, but afaik= the concrete instantiations today still have this heavy sequencer/publishe= r centralization. Correct me if I'm wrong. > > In any case, I do agree with a lot of people that some variant of this mo= del (validity rollups) intuitively looks like a good choice, for the future= , in comparison with other possible L2s that focus on *functionality* - wit= h a mild censorship and centralization tradeoff perhaps. > > And I'm maybe a bit heretical but I see no issue with using 1 of N securi= ty models for trusted setup here (note how it's probably different from bas= e chain), so PLONK type stuff is just as, if not more, interesting than STA= RKS which aiui are pretty big and computationally heavy (sure, maybe that c= hanges). So if that's true, it comes back to my first paragraph. > > Cheers, > AdamISZ/waxwing > > [1] https://nitter.it/salvatoshi/status/1537362661754683396 > [3] https://community.optimism.io/docs/security-model/optimism-security-m= odel/ > > > Sent with Proton Mail secure email. > > ------- Original Message ------- > On Wednesday, October 12th, 2022 at 16:40, John Light via bitcoin-dev wrote: > > >> On Wed, Oct 12, 2022, at 9:28 AM, Greg Sanders wrote: >> >>> Is there a one page cheat sheet of "asks" for transaction >>> introspection/OP_ZKP(?) and their uses both separately and together for >>> different rollup architectures? >> >> We do not have this yet. Trey Del Bonis wrote a more detailed technical = post about how those components would be used in a validity rollup, which w= as cited in my report and can be found here: >> https://tr3y.io/articles/crypto/bitcoin-zk-rollups.html >> >> But it'll take more research and design work to suss out those details y= ou asked for and put them into a nice cheatsheet. I like this idea though! >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev