[bitcoin-dev] Validity Rollups on Bitcoin

[bitcoin-dev] Validity Rollups on Bitcoin

[John Light]

Hi all,

Today I am publishing "Validity Rollups on Bitcoin", a report I produced as part of the Human Rights Foundation's ZK-Rollup Research Fellowship.

Here's the preface:

> Ever since Satoshi Nakamoto first publicly announced bitcoin, its supporters, critics, and skeptics alike have questioned how the protocol would scale as usage increases over time. This question is more important than ever today, as blocks are increasingly full or close to full of transactions. So-called "Layer 2" (L2) protocols such as the Lightning Network have been deployed to take some transaction volume "offchain" but even Lightning needs to use _some_ bitcoin block space. It's clear that as bitcoin is adopted by more and more of the world's population (human and machine alike!) more block space will be needed. Another thread of inquiry concerns whether bitcoin's limited scripting capabilities help or hinder its value as electronic cash. Researchers and inventors have shown that the electronic cash transactions first made possible by bitcoin could be given new form by improving transaction privacy, supporting new types of smart contracts, and even creating entirely new blockchain-based assets.
> 
> One of the results of the decade-plus research into scaling and expanding the capabilities of blockchains such as bitcoin is the invention of the validity rollup. Given the observed benefits that validity rollups have for the blockchains that have already implemented them, attention now turns to the question of whether they would be beneficial for bitcoin and existing bitcoin L2 protocols such as Lightning, too. We explore this question by examining validity rollups from several angles, including their history, how they work on a technical level, how they could be built on bitcoin, and what the benefits, costs, and risks of building them on bitcoin might be. We conclude that validity rollups have the potential to improve the scalability, privacy, and programmability of bitcoin without sacrificing bitcoin's core values or functionality as a peer-to-peer electronic cash system. Given the "trustless" nature of validity rollups as cryptographically-secured extensions of their parent chain, and given bitcoin's status as the most secure settlement layer, one could even say these protocols are a _perfect match_ for one another.

You can find the full report here:

https://bitcoinrollups.org

Happy to receive any comments and answer any questions the bitcoin dev community may have about the report!

Best regards,
John Light

Re: [bitcoin-dev] Validity Rollups on Bitcoin

[Greg Sanders]

[-- Attachment #1: Type: text/plain, Size: 3109 bytes --]

Thanks for the writeup John,

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?

On Tue, Oct 11, 2022 at 11:52 AM John Light via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi all,
>
> Today I am publishing "Validity Rollups on Bitcoin", a report I produced
> as part of the Human Rights Foundation's ZK-Rollup Research Fellowship.
>
> Here's the preface:
>
> > Ever since Satoshi Nakamoto first publicly announced bitcoin, its
> supporters, critics, and skeptics alike have questioned how the protocol
> would scale as usage increases over time. This question is more important
> than ever today, as blocks are increasingly full or close to full of
> transactions. So-called "Layer 2" (L2) protocols such as the Lightning
> Network have been deployed to take some transaction volume "offchain" but
> even Lightning needs to use _some_ bitcoin block space. It's clear that as
> bitcoin is adopted by more and more of the world's population (human and
> machine alike!) more block space will be needed. Another thread of inquiry
> concerns whether bitcoin's limited scripting capabilities help or hinder
> its value as electronic cash. Researchers and inventors have shown that the
> electronic cash transactions first made possible by bitcoin could be given
> new form by improving transaction privacy, supporting new types of smart
> contracts, and even creating entirely new blockchain-based assets.
> >
> > One of the results of the decade-plus research into scaling and
> expanding the capabilities of blockchains such as bitcoin is the invention
> of the validity rollup. Given the observed benefits that validity rollups
> have for the blockchains that have already implemented them, attention now
> turns to the question of whether they would be beneficial for bitcoin and
> existing bitcoin L2 protocols such as Lightning, too. We explore this
> question by examining validity rollups from several angles, including their
> history, how they work on a technical level, how they could be built on
> bitcoin, and what the benefits, costs, and risks of building them on
> bitcoin might be. We conclude that validity rollups have the potential to
> improve the scalability, privacy, and programmability of bitcoin without
> sacrificing bitcoin's core values or functionality as a peer-to-peer
> electronic cash system. Given the "trustless" nature of validity rollups as
> cryptographically-secured extensions of their parent chain, and given
> bitcoin's status as the most secure settlement layer, one could even say
> these protocols are a _perfect match_ for one another.
>
> You can find the full report here:
>
> https://bitcoinrollups.org
>
> Happy to receive any comments and answer any questions the bitcoin dev
> community may have about the report!
>
> Best regards,
> John Light
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 3791 bytes --]

Re: [bitcoin-dev] Validity Rollups on Bitcoin

[John Light]

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!

Re: [bitcoin-dev] Validity Rollups on Bitcoin

[AdamISZ]

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

Re: [bitcoin-dev] Validity Rollups on Bitcoin

[Trey Del Bonis]

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

Re: [bitcoin-dev] Validity Rollups on Bitcoin

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 2049 bytes --]

On Fri, Nov 4, 2022 at 4:04 PM Trey Del Bonis via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> 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?)


These opcodes went live on Liquid along with Taproot <
https://blog.liquid.net/taproot-on-liquid-is-now-live/>, so feel free to
try them out on Elements or Liquid.

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).
>

I'd be interested in knowing what sort of Simplicity Jets would facilitate
rollups.  I suppose some pairing-friendly curve operations would do.  It
might not make the first cut of Simplicity, but we will see.

Simplicity's design doesn't have anything like a 520 byte stack limit.
There is just going to be an overall maximum allowed Simplicity evaluation
state size of some value that I have yet to decide.  I would imagine it to
be something like 1MB.

[-- Attachment #2: Type: text/html, Size: 2744 bytes --]

Re: [bitcoin-dev] Validity Rollups on Bitcoin

[ZmnSCPxj]

Good morning Trey,

> * 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 thing I had been musing on is to reuse pay-to-contract to store a commitment to the state.

As we all know, in Taproot, the Taproot outpoint script is just the public key corresponding to the pay-to-contract of the Taproot MAST root and an internal public key.

The internal public key can itself be a pay-to-contract, where the contract being committed to would be the state of some covenant.

One could then make an opcode which is given an "internal internal" pubkey (i.e. the pubkey that is behind the pay-to-contract to the covenant state, which when combined serves as the internal pubkey for the Taproot construct), a current state, and an optional expected new state.
It determines if the Taproot internal pubkey is actually a pay-to-contract of the current state on the internal-internal pubkey.
If the optional expected new state exists, then it also recomputes a pay-to-contract of the new state to the same internal-internal pubkey, which is a new Taproot internal pubkey, and then recomputes a pay-to-contract of the same Taproot MAST root on the new Taproot internal pubkey, and that the first output commits to that.

Basically it retains the same MASTed set of Tapscripts and the same internal-internal pubkey (which can be used to escape the covenant, in case a bug is found, if it is an n-of-n of all the interested parties, or otherwise should be a NUMS point if you trust the tapscripts are bug-free), only modifying the covenant state.
The covenant state is committed to on the Taproot output, indirectly by two nested pay-to-contracts.

With this, there is no need for quining and `OP_PUSHSCRIPT`.
The mechanism only needs some way to compute the new state from the old state.

In addition, you can split up the control script among multiple Tapscript branches and only publish onchain (== spend onchain bytes) the one you need for a particular state transition.

Regards,
ZmnSCPxj