Validium uses validity proofs like ZK-rollups but data is not stored on the main layer 1 Ethereum chain【off-chain】. This can lead to 10k transactions per second per validium chain and multiple chains can be run in parallel.
Validium returns to the idea of keeping layer 2 data off-chain, unlocking much greater scalability gains than the rollup constructions can offer. Unlike Plasma, though, Validium doesn't rely on fraud proofs for validating computation, instead adopting zero knowledge proofs.
Like zkRollup, this means Validium is currently limited to application specific implementations, and StarkEx is indeed purpose-built for use by decentralized exchanges.
This tradeoff, though, comes with some notable advantages over Plasma. The main chain verification of the zero knowledge proofs makes it impossible for operators to advance invalid state transitions. This mitigates the damage that network operators can perpetrate by withholding data. It would be impossible, for example, for colluding operators to push a state which transferred a user's tokens to their own wallets. This removes the need to design "mass exit" incentive games or to include long withdrawal delays in the protocol.
As several other researchers have pointed out, usage of zero knowledge proofs is not a cure-all for data availability attacks. Operators can, for example, make valid changes to state using properly funded accounts they control, but by withholding the data about those transactions, prevent other users from submitting the Merkle proofs they need for their own withdrawals.
This attack effectively freezes account balances, and opens up users to bribery attacks from the operators, who might refuse to publish the required state unless the users surrender some fraction of their funds.
To lessen the likelihood of such an attack, the StarkWare team has used what I would describe as an "engineering hack." The StarkEx product includes a federated "Data Availability Committee," whose members are required to sign data and keep it available at all times. As long as one of them is honest and operating, users should always be able to get the data they need to make withdrawals.
This solution isn't perfect, but it's probably acceptable for many usecases. Remember, everything is about tradeoffs. Compared to a completely trustless DEX on the base chain, a StarkEx exchange does involve slightly higher third-party risk. In exchange for that risk, a StarkEx exchange provides orders of magnitude better performance - a property that's important for serious traders. Compared to a centralized exchange a Validium layer 2 is still far more secure and trust minimized.
Bibliography: