diff --git a/docs/alpha/protocol.rst b/docs/alpha/protocol.rst index ddd4a330ab8bc55785526785a879fa7fbb00c094..5be57e8077954f5aa63181c5f09ab510683bd152 100644 --- a/docs/alpha/protocol.rst +++ b/docs/alpha/protocol.rst @@ -90,3 +90,4 @@ Sapling, etc), and some details about its implementation. :maxdepth: 2 event + diff --git a/docs/alpha/zk_rollup.rst b/docs/alpha/zk_rollup.rst new file mode 100644 index 0000000000000000000000000000000000000000..16dc8f9f2ef080474a680393b8cb28de141b697d --- /dev/null +++ b/docs/alpha/zk_rollup.rst @@ -0,0 +1,383 @@ +ZK Rollups +========== + +Summary +------- + +This document describes a framework for the Tezos economic protocol to +support a large class of provably-correct rollup designs, also known +as **ZK Rollups** because of their underlying technology. +The key advantages of ZK Rollups for the Tezos chain are: + +* Scalability with very little verification cost for the main chain. +* Modularity with a small footprint on the code of the economic protocol. +* Privacy for the rollup with respect to the Tezos chain. + +In this document we describe the operations offered by the protocol to +interact with ZK Rollups and the general design that rollup applications +must follow. + +Introduction +------------ + +A unique characteristic of cryptographic proving systems (SNARKS in +particular) is the asymmetry between the cost of proving a statement, +which typically is relatively costly, and the +cost of verifying it, which is almost negligible and quasi-constant in +the size of the statement. +In the context of blockchain scalability, such a proving system allows +the majority of the validation cost to be moved towards the prover, who +submits only a succinct proof on chain, which can be cheaply verified. +We focus on proving systems called SNARKs, where the SN part stands +for Succinct and Non-interactive, two important properties for the +blockchain setting. +ZK-SNARKs additionally produce proofs that reveal no information +(Zero-Knowledge) about the statement or its inputs, an important +property for privacy-related applications. +This statement is represented by an arithmetic circuit, which +encodes a predicate over the prover inputs. +The ZK of ZK-SNARKs has somewhat stuck as a label for this class of +Rollups, which is an unfortunate misnomer because in the case of +scalability there is no need for the zero-knowledge property and it is +usually disabled (as it incurs an additional cost). + +Such a proving system can be used to build a provably-correct Rollup, +meaning that after the validation of each proof, the chain is certain +of the correctness of the state of the Rollup. +For comparison, Optimistic Rollups (ORUs), another popular scaling +technology can only produce proofs of fraud, not ones of validity. +This means that only fraudulent behavior can be +proved. The difference between the two is subtle but has +important practical consequences. + +In Optimistic Rollups such as SCORU, in order to verify fraud-proofs +(also called disputes) the host chain must understand the internals of +the rollup. +In particular the host protocol needs the rollup definition of +supported operations, its state transition function (``apply`` in Tezos) +and its state (``context`` in Tezos). In other words the rollup protocol +is embedded in the host protocol. +Additionally, in order to resolve disputes, the host protocol needs +access to all transactions, making data-availability mandatory for all +transactions. +If we want to integrate several virtual machines through Optimistic +Rollups, the impact on the host protocol becomes significant. +The main advantage of ORU, however, is that they can run anything that +the host protocol can, including Michelson smart contracts. + +On the other hand, in ZK Rollups each update to the state is proved +to be correct by the accompanying proof, allowing the host protocol +to be agnostic of the details of the rollup. +Indeed for a ZK Rollup, the equivalent of the ORU transition function +is a very compact representation of its circuits. +The state of the ZK Rollup is also extremely compact, typically +amounting to a Merkle tree root. +Furthermore, since rollup operations are opaque values for the +protocol, data availability becomes optional, which means that the +rollup is space efficient for the transport layer of +the host chain too. + +In addition, the fact that ZK Rollups use proofs of validity means that +each update is final. +This significantly simplifies security assumptions and reduces latency +for the finality of a transaction. +The verification cost of the proof for the host chain is +independent from the number of transactions validated in the rollup, +thus providing great scalability. + +In this proposal we further exploit the opaque nature of the ZK Rollup +to design a minimal API that allows a large class of ZK Rollups to be +hosted on the Tezos chain, with minimal impact on the code of the economic +protocol. All that is needed is one new rollup account and three new +operations: ``origination``, ``publish`` and ``update``. +This minimal API ensures good modularity, which allows rollup designers +rollup designers to deploy new solutions without amending the protocol, +that is, encourages innovation and customization of rollups for +specific needs (e.g. an NFT market, a local private currency, +an exchange service, etc.). + +ZK Rollups in Tezos +------------------- + +Plompiler and aPlonK +~~~~~~~~~~~~~~~~~~~~ + +Nomadic Labs develops an in-house proving system aPlonK and circuit +design library Plompiler. +Plompiler allows to write a statement in a high-level language (eDSL) +and produces a circuit that can be used with aPlonK. The statements +can be seen as boolean functions that can be satisfied with the right +combination of inputs. +So instead of seeing a rollup transition function as producing the +next state (e.g. ``op -> state -> state``) it should be defined as a +function that takes an operation, the old and new state, and +verifies if they are all coherent (e.g. ``op -> state -> state -> +bool``). +Because of this, it is the responsibility of whoever submits the proof +to also submit the new state, as opposed to an L1 operation where the +chain itself is computing the new state. + +aPlonK is a PlonK based SNARK proving system which provides the +following API (here simplified): + +.. code-block:: ocaml + + val setup : circuit -> srs -> (prover_public_parameters, verifier_public_parameters) + + val prove : prover_public_parameters -> public_inputs -> private_inputs -> proof + + val verify : verifier_public_parameters -> public_inputs -> proof -> bool + + +In order to setup the system a Structured Reference String needs to be +provided. Two large SRS were generated by the ZCash and Filecoin +projects and are both used in aPlonK. +Notice also that the circuit is used only at setup and, regardless of its size, +from its size, the resulting verifier_public_parameters will be a +succinct piece of data that will be posted on-chain to allow +verification and they are bound to the specific circuit that generated +them. +The prover_public_parameters can be much larger and are all the prover +needs from the circuit to perform its task. + +It is important to notice that the prover takes two sets of inputs, +public and private, while the verifier takes only the public ones. This +is the defining feature which enables scalability and privacy. + +As a privacy example imagine we wanted to prove that we own a certain +public key, we could prove this using the secret key as a private input +and any verifier could check the proof simply using our public key as a +public input. + +As a scalability example, if we wanted to spare the L1 from handling +large amounts of data, we could input the set of transactions and the +state as private inputs and we can bind them to two small public +inputs that succinctly represent the state of our rollup before and +after the application of the transactions (e.g. two Merkle roots). + +It is important to remember that to maintain the good properties of +the proving system, the circuits must be designed to minimize the +number of public inputs as the verifier cost is linear with respect to +them. + +Overview +~~~~~~~~ + +Each ZK Rollup has an associated account in Tezos, which contains a succinct +representation of its state and a commitment to the circuits that encode its +state transition function. +Additionally, each ZKRU is linked to a list of pending L2 operations +(the *pending list*) which is kept in the Tezos' storage. + +The first operation added to Tezos is ``origination``, +which creates a new ZKRU. +To do so, it includes in its payload the commitment to its circuits and an +initial state. +The commitment to the circuits of a ZKRU cannot be modified after origination. + +ZK Rollup L2 operations don't need to be published on chain in general, +but it's useful (and in some cases, necessary) to be able to do so. +For example, in a ZK Rollup that implements handling of L1 tickets, +all L2 operations that result in an exchange of tickets between L1 and L2 +must be published on the main chain. This is because the L1 has to keep track +of the tickets that enter the rollup to make sure that withdrawing them later +is safe. +Our design of ZKRU allows for publishing L2 operations on chain by keeping a +pending list of L2 operations per rollup. +A new Tezos operation, ``publish``, is defined to publish an L2 op into the +pending list of the ZKRU it targets. +Additionally, each rollup has a mock ``%deposit`` entrypoint that allows +appending an operation to a ZKRU's pending list while transferring a ticket +(more on this later). + +The pending list has two main uses: + +* Any L2 operation whose interpretation implies a token transfer between + L1 and L2 has to appear in the pending list, so that the L1 can handle the + token transfer. +* Every time the L2 state is updated, a certain prefix of the pending + list has to be processed. If the pending list is not empty, then this + prefix must also be nonempty. This means that, once an L2 operation is + in the pending list, we can be sure that it will eventually be processed + by an update. + Then, the pending list can be used as a mechanism to avoid censorship + from the ZKRU operator. + + +The final Tezos operation introduced for the ZKRU is ``update``. +This is submitted by the operator of a ZKRU after processing a number of public +(those from the pending list) and private operations. +The operator will apply them and produce a proof of correctness for a new +rollup state, which will be sent alongside the proof. +On the protocol size, this proof is verified and, if successful, the state is +updated. +The prefix of the pending list processed in the update is removed. + +ZKRU Address +~~~~~~~~~~~~ + +ZK Rollups are identified by **zk rollup addresses**, +which are assigned by the layer 1 upon ZK Rollup origination. +These addresses are prefixed by ``zkr1`` when encoded in a base58 +alphabet. + +ZKRU Account +~~~~~~~~~~~~ + +A ZK Rollup's L1 account holds both static configuration of the rollup, which +is set at origination, and it's dynamic compact representation of the L2 state. +See module ``Zk_rollup_account_repr`` for more details. + +Pending List +~~~~~~~~~~~~ + +In addition to the account just described, each ZK Rollup address is linked to +a pending list. +This list represents a FIFO structure for pairs of ZKRU operations and optional +ticket hashes. + +The storage for a pending list is done in two levels. + +The lower level is a mapping between integer indices and the actual pairs +of ZKRU operations and optional ticket hashes we want to store, which +we'll call ``pending_ops``. + +On a higher lever we have a pending list descriptor, which is represented by +the type: :: + + type pending_list = + | Empty of {next_index : int64} + | Pending of {next_index : int64; length : int} + +L1 view of L2 Operations +~~~~~~~~~~~~~~~~~~~~~~~~ + +ZK Rollup operations are semi-opaque for the protocol, as they expose +a transparent header. +This header contains: + +* An ``op_code`` in the range ``[0, nb_ops)``. +* ``price = (ticket_hash, amount)`` represents the token flow between + L1 and L2 that the operation causes. Here, ``ticket_hash`` is used as + a ticket identifier, and ``amount`` is positive if the operation transfers + tickets from L1 to L2, negative if it does so from L2 to L1, and zero + when no transfer is done between layers. +* ``l1_dst`` is the public key hash of the implicit account that will + be credited with the transfer from L2 to L1 generated by this + operation, if any. +* ``rollup_id`` is the address of the rollup this operation targets. + +The rest of a ZK Rollup operation is seen by the protocol as an opaque +array of scalars. + +Ticket integration +~~~~~~~~~~~~~~~~~~ + +ZKRUs use tickets for exchanging tokens with L1. +The ticket integration follows a design similar to the one from the +`TORU `_. + +We call ZKRU ops that transfer a ticket to L2 from L1 **deposits**, +and the protocol can identify them using the ``price`` field from +the operation's header. +Conversely, we'll call **withdrawal** a ZKRU operation that transfers +a ticket from L2 to L1, i.e. operations with negative price. + +To enable these ticket deposits, ZKRUs in the protocol expose a mock +entrypoint named ``%deposit``. +This entrypoint expects as argument a pair of a ticket and the bytes +corresponding to an encoded ZKRU operation. +The deposited ticket and amount must correspond to the ZKRU operation's +price. +After calling this entrypoint, the submitted operation will be appended +to the pending list. +In order to be able to transfer the ticket back (if the L2 operation is +invalid, for example), an additional ticket hash will be stored in the +pending list together with the operation. +This hash will encode the same ticket that has been deposited, but owned +by an implicit account (whose address is found in the header of the operation). + +The price of a ZKRU operation is used to determine what sort of +transfer from the ZKRU to an L1 implicit account should be +triggered after processing the operation, if any. +The final step of an update, then, is to transfer to ``l1_dst`` the ticket +from ``price`` (taking the absolute value of the amount) for some operations. +To decide whether this transfer is performed or not, the operator +sends a boolean value for every public operation it processes. +We call these transfers **exits**, as they could represent valid withdrawals +or the return of a ticket in the case of an invalid deposit. + +The exit mechanism for the ZKRU is very similar to the one from the TORU, +as only exits to implicit accounts are possible. +Therefore, the ZKRU also relies on the **transfer ticket** L1 operation +to transfer tickets from implicit accounts to smart contracts. + +Format of an update +~~~~~~~~~~~~~~~~~~~ + +The PlonK proving system is able to prove and verify collections of circuits, +which are identified by a string. +Each circuit has a set of public inputs that are needed to verify a proof. +Although the number and inner logic of circuits might change from rollup to +rollup, circuits will be grouped into three categories with respect to their +public inputs: + +* Public operation circuits: used to prove a single public L2 operation. + As public inputs, they expect: :: + + < + old_state : scalar array, + new_state : scalar array, + fee : scalar, + exit_validity : scalar, + rollup_id : scalar, + operation : scalar array, + > + + The ``fee`` input represents the L2 fee paid to the operator as a result + of this operation. + ``exit_validity`` should represent a boolean value (0 or 1), to determine + if the exit associated with this operation should be triggered. + + NB: if a public operation is invalid (in the rollup's logic), + the ``fee`` input should be zero. + +* Batch of private operations circuits: used to prove a collection of + private operations. + As public inputs, they expect: :: + + < + old_state : scalar array, + new_state : scalar array, + fees : scalar, + rollup_id : scalar, + > + + In this case, the input ``fees`` is the sum of L2 fees over all the processed + operations. + + NB: only circuits declared as private during origination will be considered + in this group. + +- Fee circuit: circuit for crediting all the accumulated L2 fees from the + previous two groups to the operator. There will only be one circuit in this + group, that every ZK Rollup should define with the name of "fee". + This circuits expects as public inputs: :: + + < + old_state : scalar array, + new_state : scalar array, + fees : scalar, + > + +The protocol, then, will need the public inputs of the different circuits +proved in an update. +However, the operator will only provide a subset of those previously described, +as some inputs can (and should) be computed by the protocol. +An example of this is the state, which should be threaded between the +consecutive circuits, so that only the new state has to be sent for +each circuit. + +The module ``Zk_rollup_update_repr`` defines precisely which inputs are expected +to be part of the payload of an update operation. +