[ProjectTracking]: Stateless validation MVP

[walnut-the-cat]

Goals

Horizontally scalable blockchain is what makes NEAR unique in the field. Currently, we have phase 1 of sharding in mainnet which is not a true form of sharding. With recent collaboration with various partners such as SWEAT and Kaiching, NEAR protocol has seen massive increase in daily txn volume and expect the number to grow beyond our current capacity in 2024. This naturally brings criticality of introducing the next phase of sharding in mainnet, so we can keep up with our growth.

As phase 1 of sharding requires block producers to track all shards due to underlying security concerns, the team explored potential ways to achieve phase 2 of sharding, where none of the validators has to track all shards.

Initial design of phase 2 relied on the security assumption that as long as there is one honest validator or fisherman tracking a shard, the shard is secure; by doing so, it naturally relied on protocol's ability to challenge (when an honest validator or fisherman detects a malicious behavior), rollback (when validators agree that the submitted challenge is valid), slashing (to punish the malicious validator), and rewarding (for chllenger). While it sounds straigtforward and simple on paper, the detailed implication and implementation of these features turned out to be extremely complicated.

As a result, the team sought alternative approach and concluded that stateless validation is the most realistic and promising one; stateless validation approach does not assume the existence of fishermen and assumes that a shard is secure if every single chunk in that shard is validated by a randomly sampled subset of all validators.

The fundamental idea is that validators do not need to have state locally to validate chunks.

• Under stateless validation, responsibility of a chunk producer extends to package transactions and receipts and annotate them with state witnesses (we will call them with the new role name, chunk proposers).
• State witness of a chunk is defined to be the state alongside proof of inclusion that is needed to execute a chunk. State witness allows anyone to execute a chunk without having the state of a shard locally.
• Then, validators will not store state locally and be randomly assigned to a shard at a given block height. Once a validator receives a chunk, along with its state witnesses, it verifies the state transition of the chunk, signs an approval, and sends it to the next block producer, similar to how it works today.

Links to external documentations and discussions

• Stateless validation index
• Stateless validation stage 0
• Stateless validation with pre-state root
• Stateless validation roadmap
• Stateless validation dependency graph
• NEP-509
• Zulip channel

Estimated effort

The project started with three engineers, Alex, Anton, and Robin, and we plan to onboard more engineers. For now, the newly boarded engineers won't work on MVP, but building foundation for the next step.

We target all the necessary components to be landed by end of 2023 early January, and connect the dots together and complete MVP in mid January for a demo-able MVP.

Assumptions

• Decentralized State sync is enabled in Mainnet
• Initial round of shard split (4->5) is completed in Mainnet
• Merkle Patricia Trie is underlying data structure

Tasks

Major tasks (for MVP)

• In memory trie: REF @robin-near
• Validatior seat assignment @mooori
• Validator seat assignment integration with nearcore @robin-near
• State witness
  • generation (chunk proposer) @Longarithm
  • delivery (chunk proposer -> chunk validator) @robin-near
  • validation (chunk validator) @robin-near
  • fill source_receipt_proofs @jancionear
  • Transactions validation for Stateless Validation @staffik
  • delayed receipts handling
• Chunk endorsement
  • generation (chunk validator) @robin-near
  • collection (block producer) @shreyan-gupta
  • block production - add chunk endorsements @shreyan-gupta
  • block processing - check chunk endorsements @shreyan-gupta
• Updated block validation and endorsement @robin-near
• Test state witness generation and validation on a mainnet node @pugachAG
• metrics and dashboard @pugachAG
• Testing setup @robin-near
  • e.g. Add EntityDebug UI entities for stateless validation nearcore#10524
• Set up statelessnet feature, build the binary @Longarithm
  • Consider adding dedicated CI
• Figure out initial hardware requirements

[walnut-the-cat]

• Robin started working on state witness exchange and validation flow
• Alex is almost done with delayed chunk execution and will move on to state witness production
• Anton will start working on code refactoring for better dev env
• Shreyan will onboard with stateless validation and start tackling state witness size limit and distribution

[walnut-the-cat]

12/18 status update

• PR is merged in for state witness distribution, chunk validation, and chunk approval distribution
• Shadow job is running for nightly to make sure outcome is same between what we have in mainnet and updated handling logic with delayed chunk execution
• Alex starting working on removing stateful jobs and that revealed series of complex matters, related to ranges of missing chunks and state update commits. Plan is to tackle them this year before moving on to state witness generation as this part is requirement for MVP.
• Initial refactoring work is landed (group runtime apply_txns block/chunk related arguments), but no further progress since due to NEAT incident RC investigation

[walnut-the-cat]

Jan 16th Status update

• Jan(#10259) and Adam(#10414) started onboarding with Stateless validation
• Wac is also onboarding with Stateless validation to provide project management support
• StatelessNet doc has been written and reviewed by stakeholders
• All remaining tasks for Stateless validation MVP are WIP and e2e tests to prepare for StatelessNet will soon begin.

[Longarithm]

Feb 2nd update:

• Added support for chunk endorsements
• Conducted tests with 5/15 validator nodes; fixed discovered issues; reached relatively low percentage of missing chunks. Setting kickout threshold to 50% for now
• Metrics, more tests, replacing hacks with proper design
• Provided binary for StatelessNet

If there are no major issues with StatelessNet, I anticipate this to be closed as completed soon and we switch to #46.

[Longarithm]

January update from myself:

• Merging code for state proof production for state witness
• Adding signing&verifying state witness
• Reviewing PRs
• Helping with statelessnet launch and troubleshooting

[staffik]

2024 January update from myself:

• Onboarded to Stateless Validation.
• Stateless Transaction Validation.

[Longarithm]

Stateless was running for a week with some simple loadtesting. Closing as completed.