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. The core construction I worked out in [1] involves 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. 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. 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. I had considered 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. 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. The way I assumed it would work is taking the serialized proof, a verification key, and the public input as separate stack items. 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. But that seems messy. 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. One solution to that 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. The size of the 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. 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. 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. I think it would be unwise to drop all restrictions 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? 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. But that still feels like a centralizing force. In practice 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/2dda79cf616e8928346eeb9e3282f5744955aa88/doc/tapscript_opcodes.md [3] https://github.com/matter-labs/zksync/blob/master/contracts/contracts/PlonkCore.sol [4] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-March/020036.html 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 > Bitcoin 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 > offchain contracting that is provable, ideally in zero knowledge, but at the > very least, succinctly, with onchain crypto operations. An example might be: > if we had verification of bilinear pairings onchain, combined with maybe some > covenant opcode, does it give us enough to do something like a > rollup/sidechain model with full client side computation and very compact > state update and verification onchain? (To be clear: just made that up! there > is certainly no deep theory behind that particular combination .. although I > did see this [1] thread on *optimistic* + covenant). > > Is the actual answer to this something like Simplicity? (Above my paygrade 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 state > updates seems to be a really big issue that's somewhat brushed under the > carpet. Depending on the model, there are cases where it actually is a theft > risk (e.g. full control of an onchain smart contract), but there's > significant censorship risk at the very least, as well as availability/uptime > risk. At the extreme, Optimism has a 'security model' [3] that is frankly > laughable (though, no doubt it's possible that will radically change) and for > things like Arbitrum you have centralized sequencers, where the claim is that > 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, cheap, > scale' aspect straight away, I feel like those models haven't done the hard > 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' > instead 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 > decentralization and trustlessness are sine-qua-non and so the limitations > are much more out in the open (e.g. the capacity tradeoff - while the > 'instantness' 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/publisher > centralization. Correct me if I'm wrong. > > In any case, I do agree with a lot of people that some variant of this model > (validity rollups) intuitively looks like a good choice, for the future, in > comparison with other possible L2s that focus on *functionality* - with a > mild censorship and centralization tradeoff perhaps. > > And I'm maybe a bit heretical but I see no issue with using 1 of N security > models for trusted setup here (note how it's probably different from base > chain), so PLONK type stuff is just as, if not more, interesting than STARKS > which aiui are pretty big and computationally heavy (sure, maybe that > changes). 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-model/ > > > Sent with Proton Mail secure email. > > ------- Original Message ------- > On Wednesday, October 12th, 2022 at 16:40, John Light via bitcoin-dev > <bitcoin-dev@lists.linuxfoundation.org> 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 was >> 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 you >> 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 _______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
