Re: [bitcoin-dev] Validity Rollups on Bitcoin

From: Trey Del Bonis <trey.delbonis@protonmail•com>
To: AdamISZ <AdamISZ@protonmail•com>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>,
	John Light <bitcoin-dev@lightco•in>
Subject: Re: [bitcoin-dev] Validity Rollups on Bitcoin
Date: Fri, 04 Nov 2022 19:53:31 +0000	[thread overview]
Message-ID: <629da3d8-ee34-9acb-511b-4af1913eceff@protonmail.com> (raw)
In-Reply-To: <WJ0jiInq_I_IiiT8EiAZZN6axo2pSIRCxQWfyvgU-4rjRmeHnCXFNGWFSXoeOv7nVmqoAPr6EHeXRgc-1DfiPX3C8xHwdYzs2qn4Lck06fs=@protonmail.com>

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