This is our submission to The Great Reddit Scaling Bake-off. It’s a StarkEx Rollup (data on-chain).
Sincerely,
TL;DR
Show & Tell
Our Deck
Detailed Description
Table of Contents
StarkEx — General
- System Overview
- Product Documentation
StarkEx — the Reddit Bake-off
- Cost Analysis
- System Architecture
- Code
System Overview
The StarkEx engine has on-chain and off-chain components. Generally speaking, off-chain is for heavy-duty computation and storage, while on-chain is for the computationally-lean verification , state commitment, and data-availability required for using the escape hatch.
For a more detailed overview read our medium post. Note, however, that this post describes StarkEx in Validium mode (off-chain data), whereas in this bake-off we demonstrated StarkEx in Rollup mode (on-chain data).
A note on terminology: Rollups using cryptographic proofs are often called “ZK-Rollups” even when the proofs are not Zero-Knowldge (ZK); we shall use this common term when referring to the general class of proof-based Rollups.
Product Documentation
See here.
StarkEx Demo for the Reddit Bake-off
Cost Analysis
TL;DR
- StarkEx can operate with either on-chain data (Rollup mode) or off-chain data (Validium mode).
- In this bake-off, we operated in Rollup mode. Our total Mainnet on-chain gas cost was 94.47M gas, which translates to an average of 315 gas per Tx. The off-chain costs were a small fraction of this. These are actual measured Mainnet costs, not optimistic estimates.
- Running the bake-off in Validium mode would have cost 5M gas total, which is under 17 gas per Tx. StarkWare already has a StarkEx system in Validium mode deployed on Mainnet.
- StarkEx outperforms other Rollup solutions
- It outperforms existing ZK-Rollups in both on-chain and off-chain costs.
- It fundamentally out-performs Optimistic Rollups (OR) in on-chain costs. Because cost is dominated by on-chain costs, it has a fundamental cost advantage over OR.
Details
There are two sets of costs in a StarkEx system:
- On-chain costs
- Submitting and verifying proofs
- (Only In Rollup mode:) publishing data pertaining to state changes
2. Off-chain costs: running the StarkEx cloud service, and specifically the provers
In Rollup mode, the on-chain portion is the dominating part of the cost. Note that the actual on-chain cost per Tx is much lower in ZK-Rollup solutions than in OR solutions, since the amount of data that needs to be published is much smaller.
In the bake-off, the actual on-chain costs were 94.47M, (average of 315 gas per Tx) and the off-chain costs were negligible in comparison (less than 5% of on-chain cost).
At a gas cost of 70 gwei, this cost us 6.6 ETH, which at an ETH price of $230 cost $1,518 (average on-chain cost of ¢0.5 per bake-off Tx). Naturally, the USD price fluctuates with the price of gas on Ethereum, and the price of ETH.
94.5% of on-chain costs were due to operating in Rollup mode, i.e. for posting the transaction data on-chain (section 1.b above). Had we run the same in Validium mode, the on-chain costs would have been a mere 5M gas (average of under 17 gas per Tx), and would have cost 0.35 ETH, which translates to a total of $80.5 (average of ¢0.02 per bake-off Tx).
On-Chain Gas Consumption Summary:
With StarkEx, the verification cost grows only poly-logarithmically with respect to the batch size. This is displayed most clearly in Validium mode, where data is not posted on-chain, and thus on-chain cost scales sub-linearly (logarithmically) with batch size. Consequently, at high scale, the amortized on-chain cost of a single Tx in Validium mode goes to zero with batch size, and the off-chain cost dominates. In terms of off-chain cost, STARKs have a significant advantage over SNARK-based solutions: latest state of the art STARK provers are 20x faster than state of the art SNARK provers and this speedup is based on fundamental cryptographic reasons¹.
In general, the actual cost depends on various factors, including:
- As stated above, on the price of gas on Ethereum, and the price of ETH.
- System throughput (number of Tx per second): StarkEx achieves efficiency via batching, as verification cost is only logarithmic wrt the batch size. The bigger the batches, the lower the cost per Tx. Generally speaking, higher throughput lends itself to bigger batches, and thus lower average cost per Tx.
- Maximal latency allowed between Tx and its submission on-chain: the bigger the allowed latency, the bigger the batches, and the lower the cost per Tx. Larger latency also better enables timing proof submissions for when gas costs are lower.
- Data Availability solution: as mentioned above, the current bakeoff was in Rollup mode, where most of the system cost is the on-chain data availability. Running in Validium mode would have reduced the on-chain cost by a factor of 20x.
- Number of concurrent competing off-chain proof operators and mechanism of distributing proofs between them: generally speaking, if several proof operators generate proofs in parallel and compete for submitting them, the off-chain costs grow, as those operators all need to be compensated for their on-going cloud costs.
- Business relationship/agreement with the proof operators: if Reddit runs the proof operator itself, the off-chain costs are just the out-of-pocket costs of running the service (including prover license/usage fees). If other entity/ies provide the service, the cost could be higher.
- Whether the proofs contain just Reddit Txs, or are they bundled together with Txs from other applications: since batching lowers costs, bundling Reddit Txs alongside Txs from other applications into the same proofs can lower the average cost per Tx.
- Optimizations based on usage patterns: StarkEx contains various optimisations within each batch (e.g. bundling together different Txs that relate to the same accounts). In some cases, the usage patterns of the application benefit more from these optimisations (e.g. if in many cases, a batch contains many Txs for the same accounts, the average cost will be lower).
The cost quoted above for the bake-off can provide a decent rough cost estimate for a live system (once again, assuming on-chain data availability; otherwise they would be considerably lower). More exact estimates could be provided once we get tighter specifications for the desired system configuration.
Note that the costs quoted above are the actual variable costs for running the bake-off on Mainnet. We have read various publications from competing scaling solutions quoting costs that are merely estimates, and often neglect significant parts of the actual cost structure, as typically they don’t yet have a fully functional product. As far as we know, STARK (as a cryptographic protocol) and StarkEx (our specific implementation for this use case) are significantly more efficient than other cryptographic proof systems. For example, ethSTARK, our EF-funded open-source code, is 20X faster than any other proof system we know of. This efficiency translates to a cost advantage over other alternatives, when all considerations are taken into account.
System Architecture
Highlights
- Scalability: High throughput enabled by batching transactions.
- Integrity: Cryptographic proofs and commitments ensure true ownership of Points.
- Accessibility: Support by leading wallets, and no on-chain operations required from users.
System Components
Minting (1)
Minting is done by transferring Points from the moderator accounts to chosen users (per Reddit’s specification, users claim these Points). This is done via the Moderator API.
UX — Subscribe, Tip, and Burn (2)
Initiating User Commands
StarkWare built a Reddit Chrome Extension (RCE) that monitors user activity on the Reddit website. The RCE catches events such as Subscribe (clicking the subreddit “JOIN” button), and Tip (adding a response starting with “/tip”), and interprets them appropriately. Whenever the RCE catches a user command, it constructs the required StarkEx transaction, and requests the user to sign it with their selected wallet. The signed transactions are passed by the RCE to the StarkEx Scalability Engine (SESE) in the cloud. StarkEx batches transactions, generates a STARK proof attesting to their integrity, and writes to Ethereum the proof, a commitment to the updated user balances data structure, and the modified user balances.
Frictionless User Experience
Users limiting themselves to the basic Reddit Point interactions (namely: claiming Points, subscribing to a subreddit, tipping other users, and burning Points) need not interact with Ethereum, and in particular, no on-chain registration is required. Only when users choose to interact with Ethereum, e.g. to withdraw or deposit Points, do they need to register on-chain as well. On-chain registration simply means linking a user’s Ethereum address with their StarkEx account.
Wallet Support (3)
Native Integration
Several wallets support the StarkEx ECDSA signature scheme and APIs, offering maximal security to their users. These wallets securely present to the user StarkEx transactions in a clear and readable format, so the user knows what they are signing. This ensures that any attempts at tampering with the message (e.g. by malware) can be detected by the user prior to signing.
Currently provided by: Ledger, Authereum, Portis, and Argent (via WalletConnect).
Standard Integration
Where Native Integration with StarkEx has yet to be completed, we opted for Standard Integration. For the Reddit bake-off, these wallets are used strictly for the secure storage of the user’s private key. When using such a wallet, the RCE itself signs the message with the key it obtains from the wallet.
Currently provided by: MetaMask and Torus.
StarkEx Scalability Engine (4)
The SESE runs in the cloud, and is responsible for batching transactions, generating a STARK proof attesting to their integrity, and updating a commitment (a hash) to the new state of accounts following this batch. StarkEx sends to Ethereum the STARK proof, alongside the commitment. The StarkEx smart contract system checks the proof, and if it is accepted, it stores the commitment on-chain. StarkEx accompanies each proof sent to Ethereum with the list of modified account balances verified by the proof as well (aka on-chain data availability), thus ensuring the anti-censorship mechanism described below.
StarkEx Batch Explorer (5)
The StarkEx batch explorer connects to the SESE. It allows viewing the batches created, and the transactions in each batch. The batch explorer also displays a readable format of the modified accounts data that StarkEx puts on-chain, which the explorer reads directly from the blockchain. Note that the set of transactions displayed requires trust in the explorer, as it cannot be derived merely from observing the commitment and the modified accounts recorded on the blockchain.
Anti-Censorship Mechanism
Serving All or No One
In StarkEx, a user should always be able to withdraw their Points to the Ethereum blockchain, as ERC-20 coins. In the standard flow, a user sends a withdrawal request to the SESE via an off-chain API. Off-chain API service requires trust in the Operator (e.g. system availability). If a withdrawal request isn’t serviced by the Operator, the user submits a Full Withdrawal request (think of it as the equivalent of filing a complaint to a trustless party) to the StarkEx-Reddit Smart Contract. This triggers a grace period during which the Operator may submit a proof serving the withdrawal request. If that happens, the system reverts to its normal operation. Otherwise, the smart contract freezes the StarkEx system by declining to process any further updates.
Withdrawing Points from a Frozen StarkEx
When the system is frozen, users can claim their Points and withdraw them on-chain , by demonstrating to the smart-contract that they indeed own the claimed assets. The commitment stored on-chain is actually a Merkle tree commitment to the user balances. A user can withdraw funds directly from the contract by providing a Merkle authentication-path from their account (a leaf in the tree) to the root (the commitment kept on-chain). The on-chain data-availability sent with every batch processed contains the information needed to allow a user to construct such authentication paths (the data is broadcast solely for this purpose).
Code
Proxy contract:
https://etherscan.io/address/0x7737d2afcd437a07dc8d58792344e76b4f8e93b6#code
Implementation contract:
https://etherscan.io/address/0x4126cf347cd0d3aa900041756329de4c319933b0#code
¹ Briefly, SNARKs require computationally heavy number-theoretic cryptography while STARKs use lean (post-quantum safe) symmetric cryptography. See this post for a more detailed survey and comparison of deployed proof systems.
