Starknet decentralization may be roughly split in two parts: the decentralized protocol and the decentralized governance and decision-making. On February 7, 2023, StarkWare held two concurrent decentralization workshops, respectively dedicated to the above components and collectively referred to as DeGo day. This post is an account of the decentralized protocol workshop. We’ll proceed in five parts.
- About the event
- Background and featured design questions
- Post-workshop reflections
- Ideas and insights from the workshop
- Summary
Being the first workshop on this topic, we decided to start out small. First, we contacted LambdaClass, Nethermind, Equilibrium, and Maker, both because they are deeply familiar with Starknet and because they will likely continue to develop many relevant aspects and features. Second, we reached out to strong academics who showed interest in the protocol. Lastly, we invited three builders who showed initiative and proposed concrete solutions to various decentralization problems. In total, there were 29 attendees: 15 StarkWare and 14 externals who varied from builders to academics and between. An attendance list is attached at the end of the post.
Starknet is blessed with a marvelous community and we hope for its increasing involvement in the decentralization process.
About the event
The workshop had two goals:
- Strengthen community involvement in the decentralization process.
- Gain insight on designing a decentralized Starknet protocol, with a focus on proofs in the protocol.
The workshop lasted six hours (10:00-16:00) with a simple schedule:
- 9:30-10:00 –
Breakfast - 10:00-10:45 – Introduction
- 10:45-13:00 – Division into 5 work-groups, each either focused on a particular aspect of protocol design or aiming for a complete suggestion
- 13:00-14:00 –
Lunch - 14:00-16:00 – Continuation of work-groups
- 16:00-16:30 – Brief presentation by each group
- 16:30-00:00 – Mandatory bare knuckle fight between groups until the last man standing
Background and highlighted design questions
The background material consisted of our series of community forum posts, with emphasis on proofs. We decided to focus on proofs because we’re pleased with our understanding of questions revolving around consensus.
At a high level, we decomposed the protocol into three steps: consensus, proofs, and L1 state update. \begin{array}{ccccc} \underset{\square}{\text{consensus}} & \longrightarrow & & \overbrace{\underset{▣}{\text{proofs}}}^\text{compute} & \longrightarrow &\overbrace{\underset{\blacksquare}{\text{state update}}}^{\text{L1 interaction}}\\ _{\text{(sequencers)}} & & & _{\text{(provers)}} & &_{\text{(open?)}} \end{array}
The first part of the introductory talk outlined the abstraction of consensus to a black box which outputs an L2 ledger alongside periodic L1 checkpoints. The second part outlined the proposed design questions. Specifically, we focused on proof production, proof price discovery, L1 state updates, and reward issuance. For those interested, here is the notion link used for the talk. Note the many implicit references to the post on proofs in the protocol.
Post-workshop reflections
With the benefit of hindsight, we use this section to refine and reflect on some of the workshop’s insights. We postpone the “raw” ideas to the next section to streamline the flow of the post.
-
For optimal performance, always have an open competition for each job with some backup mechanism. To mitigate redundancy, stop the backup as soon as someone wins the open competition.
-
Issue backup rewards according to performance, which is now measured in terms of “how much you did until you were stopped”.
-
Several approaches to backup mechanisms:
- Consolation prizes for the open competition (silver & bronze metals etc.).
- Separate mechanism using some Sybil e.g race between a PoS committee (with consolation prizes).
-
With the former type of backup there is a risk in case of a deterministic open race: the fastest prover will multiply identities and win all the consolation and consequently impede proof liveness if it fails. As discussed in the post on proofs, introducing nondeterminism may be interesting.
-
The latter type of PoS backup seems incentive compatible for rational stakers assuming sufficient decentralization: people will delegate their stake to large pools that compete in prover races and they will switch pools according to prover performance for profit.
-
PoS mempool protocol for proofs
-
Propagating proofs off-chain and off-ledger (outside of Starknet blocks) is beneficial:
- It avoids expensive L1 interaction.
- It does not consume L2 block space.
- It keeps proofs out of the critical path of L2 consensus.
-
On the other hand, consensus on proofs can in particular be interpreted as guarantee that stakers have proof data availability.
-
The idea is to have a proof-mempool protocol that ensures data availability without ordering (no full-fledged consensus as proofs don’t need to be ordered).
-
Data availability can be used to prevent provers from hiding proofs with maliciously timed reveals. For example, malicious prover P₁ withholds a proof of job J until prover P₂ is almost finished computing the same proof, and then reveals, causing P₂ to waste computation.
-
We can use a PoS mempool protocol like Narwhal to create an available proofDAG. Note however that Narwhal collects quorum certificates, which (in a sense) defeats the purpose of a longest chain protocol.
-
-
Secrecy seems like an elegant way to incentivize provers to perform by keeping them in the dark about possible competitors.
-
To defend against underpaid transactions, use a protocol-level algorithmic base fee as an enforced lower bound for the prover resource price. Unlike 1559 it seems there’s no need to burn as provers cannot collude by bloating blocks.
-
Minting to cover underpaid jobs
- The base fee may fail if the proof price sharply increases, e.g due to fluctuation of the exchange rate between the token and the fiat used by provers. In this case we are again at risk of consensus on transactions which are unprofitable for provers. We want a solution which does not rely on altruistic proving.
- A natural idea is to gradually increase the reward for pending jobs by minting new tokens. Note user fees will usually cover most of the proving cost due to the enforced base fee, so minting is only needed to cover the “difference”. In practice, this means that fluctuating exchange rates will trigger mild taxation of all token holders to fund pending jobs.
- Increasing rewards may be vulnerable to collusion by provers who wait for higher rewards. This will prevent correct price discovery and also increase latency. To mitigate such attacks, we can disincentivize collusion by increasing rewards only during competition for the job in question. Intuitively, people will prove instead of waiting, in fear of others doing the same.
Ideas and insights from the workshop
In this section we sketch some of the key ideas that came out during the work-groups and presentations. Some are conflicting, and below they are roughly batched into groups.
-
Tortoise and hare protocols
-
Designation of labor
- For optimal performance, always have an open race for each job (setting aside the question of job determination i.e division of labor). The open race has no consolation prizes and rewards only the hare.
- The backup mechanism is a closed race between a committee (tortoises) chosen through PoS.
- To mitigate redundancy, stop the tortoise race as soon as the hare finishes.
-
Reward issuance – backup rewards based on tortoise speed, which is now measured in terms of “how much you did until you were stopped”.
-
-
Chained proof protocols
-
Designation of labor
- By “chained proofs” we mean a protocol in which the sequencer of block n+k has a priority turn to include a proof of block n (possibly alongside a merge proof) in its block. Backup is open competition.
- Proofs are submitted as Starknet transactions to an L2 proof registry contract.
-
Reward issuance
- Prover rewards are issued according to the L2 proof registry upon L1 state update.
- To prioritize older jobs over newer ones, we increase job rewards with time.
- Backups with increasing rewards are vulnerable to collusion attacks if participation is restricted and predictable. To this end it’s best to employ open competition.
-
-
Random prover committees
-
Division of labor – a queue of (large) jobs that is determined by the protocol. For example, blocks are divided into batches of 128, and a job is to prove such a batch.
-
Designation of labor – random PoS committee chooses provers. Backup is open competition.
- No internal division of labor, so all sorts of recursive tree structures are allowed.
- Committee may compete or cooperate.
-
L1 state update – the first committee member to submit a proof to L1 may initiate a state update. After a timeout, fallback to an open race.
-
Reward issuance
- Rewards are distributed amongst contributing provers (i.e everyone involved in generating the recursive tree).
- To incentivize liveness in case of committee competition, issue consolation rewards based on speed.
- To reduce the amount of (expensive) L1 verifications, issue rewards optimistically: committee members may submit a proof hash to a collateralized L1 proof index contract; the index is periodically sampled and the selected committee member is slash unless the proof is subsequently submitted in full.
-
-
Base fee for prover resource
- Suppose you want an open market as a price discovery mechanism for connected nodes. Wallets (and other full-nodes) will suggest user transaction fees for the prover resource according to the market.
- Major threat: consensus on transactions which underpay for the prover resource will not be proven and will consequently need to be reverted.
- To mitigate, use a base fee mechanism to set a protocol-level lower bound on the price of the prover resource at each block.
- Sequencers are now prohibited from including underpaying transactions.
-
Secret designation of labor
- We want to get the benefits of competition without its drawbacks, e.g centralization and redundancy.
- Idea: make it so nobody knows whether or not there is competition. Specifically, each person only knows if they’re eligible for a job but knows nothing about other candidates (apart perhaps from their expected number in terms of stake).
- By issuing rewards according to performance, people are incentivized to always behave as though they’re competing.
- To incentivize participation, the potential candidates must be restricted, otherwise people may not participate in fear of potential competition against strong machines.
- Example implementation: PoS VRF lottery.
-
PoS proof dissemination protocol
- Recursion has many benefits, but small proofs are expensive to verify on L1. Hence many proofs may be computed without L1 state updates.
- We may want to track proof production.
- A collateralized L1 proof index is one such tracking mechanism. However, these proofs can be secret since only a hash is uploaded.
- Another idea is to collect quorum certificates on proofs as evidence of their availability to the stakers. Only certified proofs will be viable for rewards, since they are provably visible to a majority of the stake.
-
Overpay provers by minting
- The threat: users underpay for the proving resource in their transaction fees, resulting in consensus on transactions that are not profitable to prove. This eventually leads to reversion of consensus (or altruistic proving), which is bad.
- Instead of constant price discovery through market mechanisms, Starknet governance periodically sets a higher-than-market price for the prover resource.
- Users do not directly pay this higher price in transaction fees. Instead, the necessary tokens are minted. Thus token holders indirectly participate in payment for proofs.
Summary
The first Starknet decentralized protocol workshop was amazing! The atmosphere was great and the problems were concrete enough to interest the participants but open enough to inspire many creative ideas and discussions. We aim to preserve the momentum generated by the workshop in two ways:
- Continue to increase community involvement by providing more content (be it published posts, community calls, or public research sessions).
- Start suggesting and analyzing concrete decentralized protocols for Starknet.
As always, we welcome your input, feedback, and suggestions. Until next time!
Appendix – list of participants
- Ittai Abraham (Hebrew University of Jerusalem; VMWare)
- Rafael Pass (Tel Aviv University; Cornell Tech)
- Alessandro Chiesa (Berkeley)
- Noam Nisan (Hebrew University of Jerusalem; StarkWare)
- Oded Naor (Technion; StarkWare)
- Orfeas Stefanos (University of Edinburgh; Common Prefix)
- Mikhail Komarov (Nil)
- Iñaki Garay (LambdaClass)
- Juan Bono (LambdaClass)
- Mirko von Leipzig (Equilibrium)
- Krisztian Kovacs (Equilibrium)
- Albert Garreta (Nethermind)
- Milan Cermak (Lindy Labs)
- David Galindo (Valory)
- Bartek Kiepuszewski (Maker)
- Maciek Kaminski (Maker)
- Ariel Elperin (StarkWare)
- Ohad Barta (StarkWare)
- Tom Brand (StarkWare)
- Avihu Levy (StarkWare)
- Oren Katz (StarkWare)
- Gideon Kaempfer (StarkWare)
- Anat Ganor (StarkWare)
- Ittay Dror (StarkWare)
- Ilya Lesokhin (StarkWare)
- Lior Goldberg (StarkWare)
- Alex Manuskin (StarkWare)
- Evyatar Oster (StarkWare)
- Ilia Volokh (StarkWare)