Sassafras Protocol

[davxy]

The Vision

This issue tracks the implementation progress of the Sassafras block authoring protocol.

The protocol itself is currently considered experimental and the official whitepaper is still a work-in-progress.
Nevertheless the changes that we expect from the protocol are limited and we already have enough elements to start building a working prototype.

Available resources:

• Reference Implementation main PR
• W3F research page offers a fairly approachable description of the protocol components
• W3F github repo contains the last research paper
• bandersnatch vrf
• ring proof
• ring-vrf paper

The Plan

The overall work is divided into smaller and self-contained steps that incrementally should bring us to a sound implementation.

Identified sub-tasks:

• Prototype 1: first minimal implementation.
• Prototype 2: improved implementation.
• Prototype 3: Ring-VRF integration: replace Schnorrkel-VRF with Ring-VRF for slot tickets generation and validation
• Prototype 4: Tickets Proxy: (almost) anonymous ticket submission via a proxy validator.

---

Version 0.1 - KISS

Regardless of the simplification compromises, the protocol core logic should work as close as possible to the one described by the paper.

• Prototype binary derived from the node-template for simplicity. No fancy pallets only stuff strictly necessary to have something "that works".
• Identify and implement the very basic components of the Sassafras protocol (for FRAME, primitives and client).
• Fixed validators set.
• Block randomness accumulator for next epoch randomness seed.
• Tickets generation initially performed via Schnorrkel VRF (instead of Ring VRF). Use the same key used to produce block randomness.
• On-chain publication directly by the author (no proxy) via unsigned extrinsics (best practice?)
• (On epoch change) Tickets are sorted:
  - First lexicographic sort
  - If num-tickets > num-slots then drop extra tickets
  - Finally assign tickets to slots using outside-in strategy .
• If num-tickets < num-slots then AURA fallback for empty slots.
  - This will address the genesis warm-up phase as well.
• Block verification for primary and secondary method

Version 0.2 - Improve, test and refactor

• Improved tickets management strategy (double buffering).
• Validators and configuration change.
• Session pallet integration.
• Aux data revert.
• Report equivocations.
• Skipped epochs handling.
• Testing for pallet and native components.

Version 0.3 - Ring-VRF Integration

• Warp sync support
• Structured ticket (as discussed during the Sardinia Retreat)
• Fix Slot VRF output
• Integrate Ring VRF.
• Better define the parameters used to compute the threshold and the formula itself
• Pallet extrinsics benchmarks (especially ring ctx loading, ring verifier key generation and ticket verification).

Version 0.4

• RFC proposal
• Zombienet tests and missing unit tests
• Proper equivocation reporting system
• ...

Version 0.5 - Tickets Proxy

• Submit tickets on-chain via a proxy validator.
  • Encrypt tickets using Proxy public key and exchange tickets via a dedicated protocol.
  • Consider use of mixnet. Mixnet integration substrate#13904 and Mixnet integration substrate#14207
• ...

---

Here you can find the board with specific sub-tasks to this milestone:
https://github.com/orgs/paritytech/projects/18/views/15

[burdges]

1. Avoid xxhash here. It'll definitely have collisions. Ain't clear how one exploits them, but we do not care about the performance of one blake2 of 512 bits per block.

2. Yes, the sort is an off chain operation of on-chain data, so it'll be deterministic anyways. I doubt this maters much but whatever.

3. I'm not sure if I understand, but yes each block reveals a fresh VRF not seen before, and not the same as the ring VRF output.

4. No, we're doing sassafras mostly to remove the forks of the secondary claim strategy from babe. we do however pad the "inside" of the sorted list of tickets using some round robin like scheme.

[rphmeier]

Another additional consideration is higher-level code that uses the BABE per-block VRFs such as https://github.com/paritytech/polkadot/blob/master/node/primitives/src/approval.rs#L146 . Any hard fork needs to be coordinated (ideally using Runtime API presence/versioning) to ensure a seamless handover for such code.

[burdges]

We'll want the Sassafras per-block VRF in approvals I think, not the current randomness accumulator value. An adversary would know the randomness accumulator before making their attack, so it gives no benefits and permits more bias. It's beneficial when the adversary waits somewhat longer, but not a full epoch.