Overview
Allow the user to have a rollup-only account. The user won’t have any conservative balance to pay fees on L1, and instead will pay a premium for L1 storage.
- For instance, if the user only has USD to begin with, she can send her USD to an exchange, and in return the exchange will send coins into her (newly created) rollup account.
- This user will have only non-conservative balance, and each of her rollup-only transactions will reduce her non-conservative balance by transferring a fee (at a premium) to a gas-station’s rollup account, and the gas-station will cover the L1 storage cost of her transaction.
Specifications
Technically, in addition to the standalone (a.k.a. standard) transaction format, we support a new format called “gas-station transaction”.
The gas-station transaction specifies a list \tilde{T} of rollup-only transactions tx_1, tx_2, tx_3, \ldots, tx_n, such that for 1\leq j \leq n each tx_j is a rollup transaction whose format is the tuple (sender_addr_and_validate_data, destination_rollup_addr, destination_method, calldata, counter, L1_storage_gas_price, rollup_max_fee).
- For simplicity, the gas-station transaction itself only collects \tilde{T} and does nothing else.
- That is, the gas-station transaction doesn’t execute anything on its own.
- If destination_rollup_addr is \ \bot\ then destination_rollup_addr,==sender_addr
- The counter (TTLcounter-with-sub-nonce in our case) lets us regard each rollup-only transaction in \tilde{T} as if it’s a standalone transaction.
- Just like a standard transaction, the counter protects against replays and out-of-order execution.
- Unlike a standard transaction that always deducts a storage fee from the conservative balance of the sender’s account, each transaction tx_j \in \tilde{T} doesn’t touch the sender’s conservative account balance.
Let \texttt{sizeof}(\text{data}) denote the number of bytes of \text{data}
Covering the entire L1 storage cost of all the rollup-only transactions in \tilde{T}:
- The gas-station transaction specifies its own gas_price p_{gs}, and the total fee that it pays (to the L1 miners) includes the amount \ p_{gs}\cdot \text{gas\_units\_per\_L1\_byte}\cdot\texttt{sizeof}(\tilde{T})
- This is imprecise due to deduplications (see below regarding the precise total fee).
- The L1_storage_gas_price parameter of tx_j specifies the price that the sender of tx_j will pay for each gas unit of L1 storage, by transferring the required amount to the rollup account of the gas_station_transaction.
- This required amount is deducted from the rollup_max_fee of tx_j, and the remaining funds of rollup_max_fee will be used for rollup execution according to the gas units that tx_j consumes.
- Let p_j denote the L1_storage_gas_price that tx_j specified.
- There isn’t a “rollup_gas_price” parameter in each tx_j \in \tilde{T}, and instead
p_\text{min}=\text{min}(p_{gs}, p_j) is used when executing every rollup transaction tx_j \in \tilde{T}- To be explicit, if tx_j consumed x gas units such that x\cdot p_\text{min} exceeds the amount that remained in the rollup_max_fee of tx_j, then tx_j is aborted and becomes ineffective.
- This is related to the larger issue of L1 miners selecting the rollup transactions that have a high-enough fee, but only the executors actually parse and execute the selected transactions.
- If the gas table has a good estimate for gas_units_per_L1_byte relative to the other VM instructions, then everything works well.
- If this estimate is out of order, then this selection process will turn out badly and the problems will be amplified.
- Therefore, we may opt to “lower the stakes” of the gas table estimates by supporting rollup_gas_price (in standalone transactions, and in rollup-only transactions that reside in \tilde{T} of a gas-station transaction), so that all the rollup transactions with rollup_gas_price below a minimum-decided-by-the-executors will just pay the L1 storage fee and become ineffective without being executed at all.
- The L1_storage_gas_price p_j is the premium that tx_j is willing to pay for storage upon being included in a gas-station transaction that will be put into the L1 storage.
- There’s no good reason for tx_j to also pay a premium for the gas consumed during the execution in the VM of rollup, because the L1 miners and rollup executors should be satisfied with the gas price p_{gs} that the gas-station transaction specified.
- To prevent a malicious gas-station transaction from mounting a griefing attack by specifying a very high p_{gs} and thereby making each tx_j pay a very high fee to the rollup executors, we use p_\text{min}=\text{min}(p_{gs}, p_j) as the gas price that the rollup executors earn by executing tx_j
- This is imprecise: rather than using p_{gs} of the individual gas-station transaction, the full protocol uses p^\text{median}_{gs} (explained below).
Free market of gas-stations with deduplication:
The following is one approach regarding who/when is allowed to include the user’s rollup transaction tx_j into their gas-station transactions (there are other approaches too).
Overview:
- Anyone can create a gas-station transaction.
- If more than one gas-station transaction is accepted by the hare, then the UCB deduplicates the rollup-only transactions (that the gas-station transactions collected) and associates (in a random fashion) each deduplicated rollup-only transaction with only one gas-station transaction.
Details:
-
Let f_\text{mix} be a mixing function.
-
f_\text{mix} can be a cryptographically secure hash function such as blake3
-
f_\text{mix} can even be XOR
-
-
The VRF unique signatures of all the accepted tortoise proposals are mixed into a random value R_\text{vrfs} using f_\text{mix}
-
Suppose for example that gstx_\text{alice},\ gstx_\text{bob},\ gstx_\text{carol} are (the txid hash of) the 3 gas-station transactions that were accepted by the hare.
-
Suppose that the rollup-only transaction tx_\text{dave} was collected by gstx_\text{alice} and gstx_\text{carol}
-
In other words: tx_\text{dave}\in \tilde{T}_\text{alice}\ and \ tx_\text{dave}\in \tilde{T}_\text{carol}
-
If f_\text{mix}(R_\text{vrfs}, gstx_\text{alice},tx_\text{dave}) \leq f_\text{mix}(R_\text{vrfs}, gstx_\text{carol},tx_\text{dave}) then tx_\text{dave} is associated with gstx_\text{alice}, otherwise tx_\text{dave} is associated with gstx_\text{carol}
-
-
Suppose that the rollup-only transaction tx_\text{eve} was collected by gstx_\text{alice},\ gstx_\text{bob},\ gstx_\text{carol}
-
Let m_\text{abc} be the minimum among f_\text{mix}(R_\text{vrfs}, gstx_\text{alice},tx_\text{eve}), f_\text{mix}(R_\text{vrfs}, gstx_\text{bob},tx_\text{eve}), f_\text{mix}(R_\text{vrfs}, gstx_\text{carol},tx_\text{eve})
-
tx_\text{eve} is associated with gstx_\text{id} where \text{id} is the one among \text{alice},\text{bob},\text{carol} that achieved m_\text{abc}
-
-
Suppose that it turns out that gstx_\text{carol} is associated with tx_\text{eve}
-
p_{eve}\cdot \text{gas\_units\_per\_L1\_byte} \cdot \texttt{sizeof}(tx_\text{eve}) coins will be deducted from the account (and rollup_max_fee) of \text{eve} and transferred to the rollup account of \text{carol}
- See “Flow of a rollup-only transaction” below for the precise algorithm.
-
Nothing will be transferred to the rollup accounts of \text{alice} and \text{bob}.
-
How gas-station transactions and rollup-only transactions are stored in the UCB:
-
The individual rollup-only transactions (such as tx_\text{dave} and tx_\text{eve}) are shuffled together with all the non-rollup-only transactions.
- For example, if we assume that tx_\text{fred} and tx_\text{greg} and tx_\text{harry} are standard transactions, then the final shuffle of the UCB can be (tx_\text{greg}, tx_\text{eve}, tx_\text{harry}, tx_\text{fred}, tx_\text{dave})
-
The rollup-only transactions that participate in the shuffle are those that are in any of the gas-station transactions that were included into the UCB.
- For example, if gstx_\text{alice} and gstx_\text{bob} and gstx_\text{carol} are included in the UCB, then all the rollup-only transactions in the union \tilde{T}_\text{alice} \cup \tilde{T}_\text{bob} \cup \tilde{T}_\text{carol} will participate in the shuffle.
-
The UCB has a commitment hash h_{gs} to all the gas-station transactions.
-
Each gas-station transaction in the preimage of h_{gs} isn’t stored in its original format, instead it is stored in a transformed format where each rollup-only transaction id is replaced with its index after the shuffle.
-
For example, if gstx_\text{alice} has \tilde{T}_\text{alice}=(tx_\text{dave},tx_\text{eve}), and the final shuffle of the UCB is (tx_0,tx_1,tx_2,tx_3,tx_4)=(tx_\text{greg}, tx_\text{eve}, tx_\text{harry}, tx_\text{fred}, tx_\text{dave}) then gstx'_\text{alice} will have \tilde{T}'_\text{alice}=(4,1) and gstx'_\text{alice} will be stored in the preimage of h_{gs}
-
The signature verification of gstx'_\text{alice} is done by replacing (4,1) with (tx_\text{dave},tx_\text{eve}) according to the shuffled order in the UCB, and then using he signature of gstx_\text{alice} for verification.
-
Each stored index should occupy just 2 bytes.
-
-
The total fee that gstx'_\text{alice} pays (to the L1 miners) is:
-
Let p^\text{alice}_{gs} be the gas price that gstx_\text{alice} specified,
-
Let \text{sum}_\text{alice} be the byte size of gstx'_\text{alice} plus the byte size of all the rollup-only transactions that are associated with gstx_\text{alice}
-
The total fee that gstx'_\text{alice} pays is p^\text{alice}_{gs} \cdot \text{gas\_units\_per\_L1\_byte} \cdot \text{sum}_\text{alice}
-
For example, if \tilde{T}_\text{alice}=(tx_\text{dave}, tx_\text{eve}) and given R_\text{vrfs} it turns out that both tx_\text{dave} and tx_\text{eve} are associated with gstx_\text{alice}, then the total fee that gstx'_\text{alice} pays is p^\text{alice}_{gs}\cdot \text{gas\_units\_per\_L1\_byte}\cdot(\texttt{sizeof}(gstx'_\text{alice})+\texttt{sizeof}(tx_\text{dave})+\texttt{sizeof}(tx_\text{eve}))
- Plus the fee due to the runtime complexity of verifying gstx_\text{alice} (which includes just a single signature verification operation) and storing gstx'_\text{alice}
-
-
If any gas-station transaction such as gstx_\text{bob} doesn’t get associated with enough rollup-only transactions then it becomes unprofitable (because it still pays for 2 bytes of storage per rollup-only transaction in \tilde{T}_\text{bob})
-
In this case gstx'_\text{bob} is excluded from h_{gs}, i.e., excluded from the UCB altogether.
-
This is done in order to protect the gas-station account \text{bob}
-
Albeit possibly delaying liveness to the rollup-only users in \tilde{T}_\text{bob}
-
The exclusion is done by comparing the sum of coins that (optimistically) will be transferred to the gas-station account from all the rollup-only transactions in \tilde{T}_\text{bob}
-
This sum is known given R_\text{vrfs} and the subset of \tilde{T}_\text{bob} that’s associated with gstx_\text{bob}
-
If the fee that gstx'_\text{bob} pays is higher than this sum, then gstx'_\text{bob} is excluded from the UCB
-
-
-
Pruning of gas-station transactions:
-
All the included gas-station transactions reside in the preimage to the hash h_{gs}, and we may prune each such preimage when it’s old enough.
-
The pruning rule: if the distance between the UCB and the current ballot is less than D layers then the honest ballot will vote in favor of the UCB only if the preimage of h_{gs} is available, otherwise the honest ballot votes in favor even if the preimage is unavailable.
-
For this purpose, the UCB should include an explicit list of the gas-station accounts with the amount of coins that are debited from each, and an explicit median p^\text{median}_{gs} of the gas prices among all the included gas-station transactions.
-
Exemplary list: ((\text{alice}, 500), (\text{bob}, 380), (\text{carol}, 430))
-
If the preimage of h_{gs} is (gstx'_\text{alice},gstx'_\text{bob},gstx'_\text{carol}) then p^\text{median}_{gs} is the median among their gas prices p_\text{alice},\ p_\text{bob},\ p_\text{carol}
-
-
In case the protocol dictates pruning of the old h_{gs} preimages, it will have safeguards to prevent damage by a temporary dishonest majority.
-
Specifically, every L1 account has a flag (that’s off by default) that specifies whether it can act as a gas-station. The explicit list of the gas-station accounts (with amounts debited from each) in the UCB can only include accounts for which this flag is turned on.
-
Prudent gas-station accounts should be aware that keeping a high balance in their account is relatively more risky than in a non-gas-station account.
-
-
The gas price that every rollup-only transaction gstx_\text{id} in the UCB pays for executing the VM instructions is \min(p^\text{median}_{gs}, p_\text{id}), where p_\text{id} denotes L1_storage_gas_price of gstx_\text{id}
-
This allows executing each rollup-only transaction tx_\text{id} by accessing only p^\text{median}_{gs} and the data of tx_\text{id} itself.
-
Without having to process R_\text{vrfs} and all the gas_station transactions in the UCB in order to determine the gas price that tx_\text{id} will pay for each gas unit.
-
Per the above discussion regarding “lower the stakes”, if each rollup-only transaction also has the rollup_gas_price parameter then p^\text{median}_{gs} is unneeded.
-
Flow of a rollup-only transaction (such as tx_\text{dave}) verification:
- Given R_\text{vrfs}, suppose that tx_\text{dave} is associated with gstx_\text{alice}
- Let p_{dave} denote the L1_storage_gas_price that tx_\text{dave} specified.
- Fetch the non-conservative balance n_\text{dave} of the rollup account of \text{dave} from the rollup state.
- Let f_\text{dave}=p_\text{dave}\cdot \text{gas\_units\_per\_L1\_byte}\cdot\texttt{sizeof}(tx_\text{dave})
- Compute d_\text{dave} = n_\text{dave} - f_\text{dave}
- If d \leq 0 then transfer the n_\text{dave} coins from the rollup balance of \text{dave} to the rollup balance of \text{alice}, deem tx_\text{dave} as ineffective, and terminate.
- Set the new rollup balance of \text{dave}$ to be d_\text{dave}
- Increment the rollup balance of \text{alice} by f_\text{dave} coins.
- Let p_\text{min}=\min(p^\text{median}_{gs},\ p_\text{dave})
- Execute tx_\text{dave} with gas price p_\text{min}, and if the consumed gas exceeds the remaining balance n_\text{dave} then abort and deem tx_\text{dave} as ineffective.
Gas-station transaction verification:
-
Any gas-station transaction (such as gstx_\text{alice}) is verified purely on L1
-
The rollup executors/challengers/provers don’t process gstx_\text{alice} at all.
-
The rollup balance of \text{alice} is modified only when processing rollup-only transactions (that were included in \tilde{T}_\text{alice}).
Rational for the free market of gas-stations with deduplication:
-
If too many gas-station transactions are included in the block, then each gas-station transaction gstx'_\text{id} will pay a penalty for a relatively high number of rollup-only transactions that are included in gstx'_\text{id} but aren’t associated with gstx'_\text{id}
-
This is because each rollup-only transaction is associated with only one gas-station transaction.
-
Hence, some of the participating gas-stations will drop out because it’s unprofitable to continue to perform this work (while each gas-station never loses money in nominal terms, it may lose when accounting for its operational costs).
- The remaining gas-stations should then receive proper earnings.
-
-
If there are too few active gas-stations, then only the few that participate enjoy collecting the premium storage fees that the rollup-only users are willing to pay, so it becomes more likely that additional gas-stations will opt to join.
-
The deduplication (and possibly pruning) minimize the systemic overhead costs when uncoordinated competing gas-stations collect rollup-only transactions (the overhead is due to overlaps).
-
Pruning implies that lower fees should be paid for the data that’s stored in the preimage of h_{gs}
-
This minimization makes it more attractive for gas-stations to participate, because the gas-stations cover the costs of the duplications.
-
The L1 miners always collect a fee for every byte that’s stored on L1, and the user pays a storage fee that covers only the byte size of her transaction (without the duplications), so only the gas-stations are penalized for duplications.
-
It indeed makes sense that the gas-stations will be the ones who have an incentive to minimize duplications.
-
The build-in consensus protocol rules for deduplication/pruning help the gas-stations by minimizing the cost of duplications, and also improves the efficiency of the entire L1 system (by reducing paid-for bloat).
-
-
-
There can be an additional selection rule that permits (or encourages) a rollup-only transaction such as tx_\text{dave} to be included in a gas-station transaction such as gstx_\text{alice} only if \text{hash}(\text{alice\_account\_addr},tx_\text{dave}) is small.
-
The \text{hash}() can be replaced with \text{vrf}()
-
The purpose of such a rule is to increase the coordination among gas-stations, and thereby reduce the duplications.
-
It’s probably better that the core consensus protocol won’t enforce this selection rule (it increases overhead and requires gas-stations to register in advance), and instead the honest/rational gas-stations can employ such a (non-strict) rule to discourage deduplications.
-
Support for account abstraction:
-
The VM instruction set that can be invoked during validate() includes the ALREADY_APPROVED opcode that returns TRUE if and only if one of the following two conditions holds:
- The transaction is a standalone (a.k.a. non-rollup-only) transaction.
- The transaction is a rollup-only transaction and validate() is being executed from an extracted account address (as described next).
-
For a rollup-only transaction:
-
If sender_addr_and_validate_data is 64 bytes then it’s parsed as a signature (the sender’s account address can be derived from this signature by extracting the pubkey pk from the signature and computing the hash of the concatenation of pk with the predefined fixed data of the standard account template).
- In this case, if the ALREADY_APPROVED opcode is invoked during validate() then it will return TRUE.
-
If sender_addr_and_validate_data is larger than 64 bytes then it’s parsed as (sender_rollup_address, validate_calldata), where validate_calldata is the input to the validate() function of the sender’s rollup account.
- In this case, if the ALREADY_APPROVED opcode is invoked during validate() then it will return FALSE.
-
-
By default, the rollup validate() function of the account is a special function that isn’t composed of VM opcodes but rather performs the following:
"if ALREADY_APPROVED then return TRUE else run the logic of the L1 verification precompile"-
For simplicity, an inferior option is that the default validate() will just be
"return ALREADY_APPROVED", which will already work well in most cases.-
With the inferior option, in cases where this simple validate() isn’t enough, the account can override (just like with full-fledged account abstraction) the default validate() and replace it with
"if ALREADY_APPROVED then return TRUE else {the explicit logic of the L1 verification expressed by VM opcodes}" -
For example, if the account is 3-out-of-3 multisig of (pk_1, pk_2, pk_3) then the overridden validate() will be
"if ALREADY_APPROVED then return TRUE else return verifysig_{pk_1}(txndata, sig_1) AND verifysig_{pk_2}(txndata, sig_2) AND verifysig_{pk_1}(txndata, sig_3)"
-
-
-
Thus, if the account is 3-out-of-3 multisig of (pk_1, pk_2, pk_3) then for standalone transactions the calldata for validate() is empty, and validate() will return TRUE because pk_1 and pk_2 and pk_3 already agreed to pay the L1 storage fee and thus approved the transaction (ALREADY_APPROVED==TRUE).
- However, if the account also wishes to perform rollup-only transactions, then it will need to provide (sig_1, sig_2, sig_3) as calldata for validate() by encoding sender_addr_and_validate_data=(my_explicit_addr, sig_1, sig_2, sig_3)
-
For the standard account template, the calldata for validate() is always empty (both when the transaction is standalone and when the transaction is rollup-only).
Usefulness for account abstraction:
-
Suppose that the rollup account is a smart wallet with daily-spending rules, for example
"return (verifysig_{pk_1}(txndata, sig_1) AND (daily_spent_coins < 500)) OR verifysig_{pk_2}(txndata, sig_2)", where the daily_spent_coins variable in the account storage is modified by the methods of the roll account during execution, i.e., after validate() already terminated. -
Explanation:
-
The L1 account is a standard account template whose identity is pk_1, but the vast majority of the coins of the account reside in its non-conservative rollup balance.
-
If the user intends to perform rollup-only transactions exclusively, then her L1 account is irrelevant and all of her coins are kept in her non-conservative rollup balance.
-
The identity pk_2 is considered to be the “master id” that’s usually kept in cold storage, and allows spending an amount larger than the daily spending limit in unusual circumstances.
-
Such unusual circumstances include the scenario where pk_1 (which is kept in hot storage) was stolen by a hacker.
- The hacker can gain the daily spending amount and also start a griefing attack that depletes the conservative balance, until an honest transaction with a signature by pk_2 stops the attack.
-
-
This smart wallet can be implemented efficiently by overriding the default validate() with a tailored-made validate(), as follows:
"if (ALREADY_APPROVED and (daily_spent_coins < 500)) OR verifysig_{pk_2}(txndata, sig_2)"-
In this implementation, the user enjoys a secure smart wallet via account abstraction, with the following two benefits:
-
Efficiency: each of the user’s transactions requires only a single signature, doesn’t require sending the account address, and doesn’t require any calldata.
-
In unusual circumstances in which pk_2 needs to be used:
-
If it’s a rollup-only transaction: the transaction includes the user’s account address but still only a single signature (the gas-station itself will have just one signature for all of the rollup-only transactions that it collected).
-
If it’s a standalone transaction using the user’s L1 account and conservative balance: the transaction requires two signatures (for pk_1 and for pk_2) and doesn’t require the user’s account address.
-
If it’s a standalone transaction using someone else’s L1 account (perhaps because the hacker already depleted the entire conservative balance of the user’s account): the transaction requires two signatures (one for the “someone else’s” account and one for pk_2) and the user’s account address.
-
-
-
Ease of use: if the user pays the premium for rollup-only transactions then she never needs to maintain a conservative balance.
- The user also never needs to worry that a hacker who obtains her hot privkey will damage her by taking more than the daily spending limit per day (i.e., by depleting her conservative balance too).
-
-
Reminder: unrelated to all of this, the maximal runtime complexity of validate() (that the core consensus protocol allows) must be low, otherwise the rollup executors will be susceptible to severe DoS attacks.