paritytech
Sassafras Protocol
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:
- W3F research page offers a fairly approachable description of the protocol components
- W3F github repo contains the last research paper
- ring-vrf rust implementation using zk-SNARKs
- 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:
- [x] Prototype 1: first minimal implementation.
- [x] Prototype 2: improved implementation.
- [ ] Prototype 3: Ring-VRF integration: replace Shnorkel-VRF with Ring-VRF for slot tickets generation and validation
- [ ] Prototype 4: Tickets Proxy: (almost) anonymous ticket submission via a proxy validator.
Prototype 1 - KISS
Regardless of the simplification compromises, the protocol core logic should work as close as possible to the one described by the paper.
- [x] Prototype binary derived from the
node-templatefor simplicity. No fancy pallets only stuff strictly necessary to have something "that works". - [x] Identify and implement the very basic components of the Sassafras protocol (for FRAME, primitives and client).
- [x] Fixed validators set.
- [x] Block randomness accumulator for next epoch randomness seed.
- [x] Tickets generation initially performed via Schnorrkel VRF (instead of Ring VRF). Use the same key used to produce block randomness.
- [x] On-chain publication directly by the author (no proxy) via unsigned extrinsics (best practice?)
- [x] (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 .
- [x] If num-tickets < num-slots then AURA fallback for empty slots. - This will address the genesis warm-up phase as well.
- [x] Block verification for primary and secondary method
Prototype 2 - Improve, test and refactor
- [x] Improved tickets management strategy (double buffering).
- [x] Validators and configuration change.
- [x] Session pallet integration.
- [x] Aux data revert.
- [x] Report equivocations.
- [x] Skipped epochs handling.
- [x] Testing for pallet and native components.
Prototype 3 - Ring-VRF Integration
- [x] Warp sync support
- [x] Structured ticket (as discussed during the Sardinia Retreat)
- [x] Fix Slot VRF output
- [ ] Integrate Ring VRF implementation. At this point we hope something has been officially released.
- [ ] Better define the parameters used to compute the threshold and the formula itself
- [ ] Add tests for zombienet and missing tests (e.g. equivocation report)
- [ ] Pallet extrinsics benchmarks (where required).
- [ ] Something else? For sure...
Prototype 4 - Tickets Proxy
- [ ] Submit tickets on-chain via a proxy validator.
- [ ] Code refactory, e.g. remove some Babe duplicated code.
- [ ] Something else? For sure...
Additional Considerations
Randomness Accumulator
In contrast to BABE, current epoch randomness is not collected in a vector and then hashed together at the end of the epoch.
Without any security loss, we maintain epoch randomness in a single value that is incrementally updated with block randomness as it is received.
As the hash function H we can use blake2-256.
~Open~ Closed Questions
- Can we use the faster twox-256 for randomness accumulator (instead of blake2-256)? The user can't freely choose the hash input.
- Currently the tickets are sorted using the VRF output (32 bytes). To speed-up tickets sort procedure, can we sort just using the upper or lower 16 bytes of VRF output? In this way we can sort using
u128Rust primitive type. - When a slot is claimed using the ticket (primary-claim-mechanism), the claim also comes together with a "block VRF output" to be used to compute the next epoch seed (similar to babe). Question:If a block is claimed using the AURA-like fallback mechanism, should this claim come with the "block VRF output" as well? I.e. with randomness used next epoch block seed?
- Primary claim strategy (i.e. tickets) allows to have exactly one validator per slot. Should we produce an extra block using the secondary mechanism as a fallback in case the primary method is not used (e.g. offline validator). This strategy is adopted by BABE.
Here you can find the board with specific sub-tasks to this milestone: https://github.com/orgs/paritytech/projects/18/views/7
-
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.
-
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.
-
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.
-
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.
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.
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.