This week’s top story — Game of STARKs

Read the full weekly crypto recap here.

“To allow blockchains to scale we need methods that allow for verification of computational integrity that are faster than naive replay.” StarkWare

Some Definitions

• Computational integrity: The idea that the output of a certain computation is correct, even when it is executed on an untrustworthy or malicious machine.
• Inclusive accountability: a node connected to the permissionless blockchain network should be able to verify the computational integrity of the network’s transactions.
• Naive replay: This refers to the aspect of many permissionless blockchains that requires all nodes to replay the computation that verifies every network transaction. This is the consequence of inclusive accountability.

StarkWare is a startup based in Israel developing the ZK-STARK proof system, which is said to be an advancement on the very efficient ZK-SNARKs. STARKs stands for Scalable, Transparent, ARgument of Knowledge. Scalable refers to the fact that both the proof size and the verification time grow logarithmically with the computation. Transparency refers to the fact that STARKS rely on public randomness — there is no trusted setup, a decidedly different approach compared to ZK-SNARKs. This alone is a major step forward, because even well-meaning actors may accidentally leak information (see the ZCash counterfeiting vulnerability). ZK-STARKs are also quantum resistant, while ZK-SNARKs are not.

The StarkWare team wants to commercialize STARKs by bringing the technology to different blockchains and dApps. StarkWare’s initial focus will be to use STARKs to address scalability issues on applications on Ethereum. The first project is StarkDEX, a joint effort with 0x to scale transaction throughput on DEXes. A more recent announcement is StarkPay, which uses STARKs to scale blockchain payments.

StarkWare does not have a token and is blockchain agnostic. StarkWare has raised a total of $40 million in funding as of February 2019 over two equity rounds and has received a grant from the Ethereum Foundation. Investors in the company include Paradigm, Pantera Capital, Multicoin Capital, Polychain Capital, Naval Ravikant among others.

STARKs for scalability

Permissionless blockchain systems allow for “inclusive accountability” in theory, where everyone connected to the network may verify the computational integrity of the system. However, verification is expensive and does not scale. Thus, there is a need for quickly verifiable proofs of transaction integrity. StarkWare aims to address these challenges using STARKs. With STARKs, proving time scales quasi-linearly with computation, but verifier time (verifying the proof) takes exponentially less time. Fast verification could also encourage more participants to validate the integrity of transactions. Provers must do work off-chain to compute proofs, that are then stored on-chain, but verifiers only need to perform a logarithmic amount of computation to verify correctness. So long as the verifier is valid, it does not matter who is operating the prover (i.e. it is not necessary to trust the prover).

StarkDEX

StarkWare’s first deployment of STARKs will address scalability in the settlement phase of trading on decentralized exchanges. Because decentralized exchanges allow users to maintain custody of their assets, every trade that occurs on a decentralized exchange appears as a settlement on the chain, and the number of trades is bound by scalability limitations of the underlying blockchain. The lack of scalability is one reason for negligible volume on DEXes. Trade settlement on-chain costs 100K to 200K gas, which implies the settlement of three trades per second on Ethereum (even if all resources of Ethereum were devoted to trades settlement on DEXes).

With StarkDEX, transactions are first sent to a prover that resides off-chain. The prover processes the transactions, generates a proof that they are correct, and sends the proof to the on-chain verifier contract along with the Merkle Root of the new state. The prover also updates a data set maintained off-chain.

Currently, total gas costs of DEX trades scale linearly with the number of transactions. The cost of verifying a proof increases poly-logarithmicly (by exponentially less) with the number of transactions or trades. In a demo at the Stanford Blockchain Conference in February 2019, Eli Ben Sasson showed that verifying a proof of 30 trades cost ~5.5 million gas. Following, he demonstrated that verifying 500 trades (an ~17x increase in throughput) cost only 6.7 million gas, an increase of only 1.2x, and still within the 8 million gas limit per block. At a more recent event, StarkWare shared that it has generated proofs for settling batches of 8K trades within a single block on Ethereum, yielding a per trade cost of less than 1K gas. As this example makes evident, the gas cost of verifying a proof of a batch of transactions is amortized across the number of transactions included in the proof.

StarkDEX is expected to launch on an Ethereum testnet in mid-April. For a detailed explanation and demo, we recommend this presentation by Eli Ben Sasson, The STARK Truth About DEXes.

StarkPay

More recently, StarkWare announced the application of STARKs in scaling payments with StarkPay. Like StarkDEX, StarkPay has off-chain and on-chain components. Similar to StarkDEX, StarkPay has a prover that resides off-chain and maintains an off-chain data set, and has a verifier contract that resides on-chain and verifies proofs of payment transaction batches generated by the prover. Additionally, StarkPay has a payment contract on-chain that stores the commitment to the new state of the off-chain data set. StarkWare mentions that StarkPay can create a proof that batches 10K transactions in a single block on Ethereum. Moreover, as the transaction batch size rises, the gas required to verify the batch grows only logarithmically i.e. StarkWare claims if the transaction batch size grew by 1000%, the cost to verify it would grow by only 50%. Thus, the first and foremost advantage of StarkPay is scalability.

For a detailed description of StarkPay, we suggest reading this post by StarkWare, When Lightning Starks.

Challenges

In StarkDEX and StarkPay, data is maintained in an off-chain data set. The consequence is the lack of on-chain data availability. StarkWare is considering different solutions to the data availability problem. They could start by establishing a federation to attest to the fact that data tied to a given proof is available off-chain and down the line find the right data availability solution.

Also, StarkWare will operate the prover function in both applications of STARKs. This adds the potential for censorship and an element of centralization. In regards to censorship, STARKs can also be leveraged for their privacy features that would allow users to shield payment details from provers. In such a set-up, the payer would send the prover a proof-of-payment, and the prover would send the verifier contract a proof that it verified the proof-of-payment. As the projects mature, other participants can join the system to serve the prover function, fostering competition and addressing both censorship and centralization.

Another challenge with STARKs is that payment transactions and trade settlements are not instant. Rather, the process of generating proofs for transaction batches can take a few minutes.

Finally, STARKs have a larger proof size relative to SNARKs and Bulletproofs. According to this post, STARK proofs are ~100x larger than SNARK proofs and ~20x larger than Bulletproofs. This gap may have come down since the post was published as the team has actively been working on reducing the proof length. Further, proof size becomes less important as they scale because the amortized cost approaches zero as the size of the batch grows.

For more information on StarkWare and technical explanations of STARKs, follow their blog here and see Vitalik Buterin’s series of posts on STARKs here.

Thank you to Mira Belenkiy and the StarkWare team for their feedback.

Reports, market insights, and other information (“Information”) provided by Circle Internet Financial Limited (“Circle”) or its affiliates have been prepared solely for informative purposes and should not be the basis for making investment decisions or be construed as a recommendation to engage in investment transactions or be taken to suggest an investment strategy in respect of any financial instruments or the issuers thereof. Information has not been prepared in accordance with the legal requirements designed to promote the independence of investment research and is not subject to any prohibition on dealing ahead of the dissemination of investment research under the Market Abuse Regulation (EU) No 596/2014. Information provided is not related to the provision of advisory services regarding investment, tax, legal, financial, accounting, consulting or any other related services and is not a recommendation to buy, sell, or hold any asset. Information is based on sources considered to be reliable, but not guaranteed, to be accurate or complete. Any opinions or estimates expressed herein reflect a judgment made as of the date of publication, and are subject to change without notice. Trading and investing in digital assets involves significant risks including price volatility and illiquidity and may not be suitable for all investors. Circle and its affiliates trade and hold positions in digital assets and may now or in the future trade or hold a position in an asset that is the subject of Information provided. As a result, Circle or its affiliates may be subject to certain conflicts of interest in connection with the provision of Information. Circle will not be liable whatsoever for any direct or consequential loss arising from the use of this Information.