zkRollup vs. Validium (StarkEx)

zkRollup vs. Validium (StarkEx) StarkEx is a major security enhancement for exchanges — but your funds can still be frozen, seized or hacked away. DeversiFi recently launched a new version of their exchange, powered by the StarkEx trading engine. This is an incredible technological achievement that raises the bar for the kind of security users can expect from crypto exchanges. It also marks a historical turning point: it’s the first ever application of STARKs (succinct zero-knowledge proofs without trusted setup) in a production system. For background, StarkEx is a Validium: a Layer-2 scaling solution in which the validity of all transactions is enforced using zero-knowledge proofs, while data availability is kept off-chain. This prevents the funds in the Validium from being stolen as every transfer of value from an account of a given user must be authorized by that user. Validium’s mechanism is very similar to a zkRollup, the only difference being that data-availability in a zkRollup is on-chain, while Validium keeps it off-chain. This permits Validium to achieve considerably higher throughput — but this comes at a price: Operators of a StarkEx Validium can freeze users’ funds. “The people who can destroy a thing, they control it.” Frank Herbert, Dune Without zkRollup’s data availability guarantees, the operator — or to be more precise: the data availability manager(s) — of a Validium can deny any user the right to move their funds. Here’s how it works: the operator makes a tiny change in the Merklized state without disclosing the state change to users. Lacking this information, users cannot create Merkle proofs of ownership for their accounts. Illustration: if account d3 is changed by the operator, the owner of account d1 will be missing the information about the node m they need in their proof in order to prove their account ownership. Is there a way to prevent data withholding attacks in Validium? This problem has been extensively discussed since the conception of Plasma in 2016, and zkRollups were born as an outcome of that research. Non-rollup attempts to trustlessly ensure data availability would result in losing most of Validium’s competitive advantages. While the problem is not entirely solvable, StarkEx mitigates it by introducing a permissioned Data Availability Committee (DAC). The DAC must acknowledge it has received the data by signing every update to the state by a quorum of its members. In StarkEx, the DAC consists of 8 participants (adding too many members will jeopardize the liveness of the system). These are well known, highly reputable organizations in established legal jurisdictions. It is very unlikely for them to ever even try to abuse their powers — or so the reasoning goes. Paradoxically, being well known, highly reputable, and residing in a jurisdiction with a strong state is exactly what makes them vulnerable. One plausible scenario of things going haywire: operators are required to implement KYC/AML regulations and are obliged to freeze all funds of the accounts with over $10k trading history (possibly forever). It gets even more interesting as we dive deeper. StarkEx implements a Verifier Contract Upgrade mechanism that permits the operator to add a new item to the chain of verifier contracts immediately, sans delay. This cannot invalidate any of the old logic — you can’t remove user signature checks for example. Rather it allows additional constraints to be added (you can think of constraints as `require()` statements, speaking in terms of Solidity). It is a nice security feature: should any missing constraint be found in the StarkEx’ STARK circuit logic, it can be fixed quickly without introducing any new vulnerabilities. However, this feature can be abused as a concealed censorship backdoor. In a nutshell, the StarkEx operator can always deploy an extension to the contract logic that introduces a blacklist without any prior warning to users. It’s not entirely clear from their documentation, but it looks like the consent of the DAC is not required to enforce the new rules. This doesn’t make much sense if you were to think of StarkEx as a fully decentralized exchange protocol. Imagine Vitalik Buterin owning a switch that can instantly freeze any Ethereum account. On the other hand, it makes perfect sense if you look at StarkEx as a security enhancement for crypto exchanges (which its creators surely do). Operators of a StarkEx Validium can seize users’ funds. Let’s extend our thought experiment. For whatever hypothetical reason (most likely owing to circumstances outside the control of the operators), the assets of a number of users are now frozen. Could users’ funds in StarkEx also be confiscated? As a matter of fact, this can happen. StarkEx, just like many other crypto projects, implements a state-of-the-art upgrade mechanism. Users are given 28 days notice before a new version is deployed and whoever doesn’t like it can exit. Except for those whose funds have been frozen. A new contract logic can be deployed after the grace period is over that transfers the frozen funds into custody of a designated party. Unfortunately, there is nothing affected users will be able to do against it. There are also reasonable concerns that the upgrade notice period per se might not be sufficient to allow every user who disagrees with the changes to exit (the so-called “mass exit” scenario). But this problem is a general contract upgradeability issue not unique to Validium. Update 2020–07–06: Justin Drake describes crypto-economic attack on Validium. In the follow-up discussion, Justin Drake pointed out that data availability approach of Validium can lead to an unexpected attack vector: should the signing keys of the quorum of the Data Availability Committee be compromised (and these keys are kept online, which makes it notoriously hard to secure them), attacker can transition Validium into a state only known to them, thus freezing all assets, and then demand ransom to unlock it. Theoretically, the contract upgrade mechanism should mitigate this attack. Validium’s operators could initiate deployment of a new version where the state is reverted to the last known one after 28 days of upgrade notice period. It would be a month of locked capital (which of course has quite significant costs), but if the DAC refused to negotiate, attacker would not get a single penny. However, it turns out there is a way for attacker to force the operators into deciding between losing everything or allowing the attacker to make a double-spend. It can be illustrated with the following example: Imagine that you can hack an ATM in such a way as to erase the entire bank database after your withdrawal is complete. You can only withdraw from your own account, but the details of the operation will be lost when the DB is gone. Bank employees can go through a complicated process of restoring the database in one month. But since they don’t know who did the withdrawal, by reverting to the last checkpoint they will also restore the balance on your account—restoring the balance you have withdrawn! Of course, this double-spend will be limited to the amount the attacker can provision on their account. However, it is trivial to construct a trustless contract and borrow the necessary capital from evil anonymous whales in the darknet. We will leave this exercise to the reader. This attack demonstrates that the security model of Validium is relatively similar to that of a PoA network. In fact, a PoA network with 20 nodes and 51% signing threshold might be more secure than a Validium with 8 nodes and 100% signing threshold. Data Availability in zkRollup protects users’ funds from seizure, censorship and hacks—at a cost of somewhat lower throughput. The rollup’s state is available to the zkRollup users as long as at least one Ethereum full node is online. How it works: for every zkRollup block, information required to reconstruct the changes in the state must be submitted as call-data of the Ethereum transaction — otherwise the zkRollup smart contract will refuse to make the state transition. State changes on zkRollups incurs a small gas cost per transaction which grows linearly with the number of transactions. With the Merkle tree data at hand, users who are being censored always have the ability to claim their funds directly from the zkRollup contract on the mainnet. All they need to do is to provide a Merkle proof of ownership on their account. Thus, on-chain data availability serves as a guarantee that nobody (including zkRollup operators) can freeze nor capture users’ funds. On-chain storage for data availability leads to a limitation in throughput — zkRollups have a strict practical ceiling of 2k transactions per second (TPS) on today’s Ethereum, while StarkEx Validium claims 9k+ TPS. This difference will likely play an important role in determining the application areas and use-cases for both technologies. For example, zkRollup is well suited for scaling decentralized crypto payments (VISA averages 2k TPS globally) and immutable smart contracts with strict requirements for trustlessness; Validium, on the other hand, could be a better fit for traditional high-frequency trading or games with lower trust assumptions. Conclusion We’ve shown that zkRollups and Validium (StarkEx) are relatively similar in how they work, with their main point of difference — whether data is available on-chain or off-chain — crucial in understanding them and where they can be used. This difference means that while zkRollup is a completely trustless decentralized scaling protocol, Validium displays more properties of a custodial PoA system— both in its throughput capacity and its risk profile — albeit with greatly improved security. Every technological development that reduces trust and provides users with more control over their assets is a step towards empowering the individual. There are always trade-offs we need to make in order to keep moving forward. Nevertheless, there is a growing consensus in the crypto-community that technology has passed the “don’t be evil” phase — it’s high time for “can’t be evil.” We can get there through self-custody, censorship-resistance, privacy and elimination of single points of failure. These ideas form the foundational values for the systems we’re striving to build. The time for fully trustless scalability is arriving and the count-down for Matter Labs’ big announcement is on — stay tuned!