Sassafras Consensus - Githubissues

davxy commented 11 months ago

This RFC outlines the core components and procedures of Sassafras consensus protocol.

This RFC does not cover the following topics:

Implementation details necessary for interoperability: structure of the on-chain storage, host functions and runtime API.
Deployment strategies, especially in the context of already existing blockchain networks
Parameters required for the zk-SNARK (SRS).
Networking protocol to deliver tickets to relayers.

These (and probably other) topics are fairly complex and somewhat independent of the core protocol. They should be the subject of separate, dedicated RFCs for proper exploration and discussion.

Rendered

Reference implementation tracking issue: https://github.com/paritytech/polkadot-sdk/issues/41

davxy commented 10 months ago

I haven't reviewed everything carefully, but from a light client perspective I need a way to verify the authenticity of block headers without verifying block bodies, and for warp syncing purposes I need a way to retrieve the current state of Sassafras (i.e. anything necessary to verify the block headers of the children of a block) through runtime calls or storage reads.

Block verification is performed on the header. You need to fetch some data from chain state to check if the claimed slot is associated to a ticket

tomaka commented 10 months ago

Block verification is performed on the header. You need to fetch some data from chain state to check if the claimed slot is associated to a ticket

The RFC should give some details about that. I guess the verification is explained the research paper, but the RFC should have the names of the runtime functions, layout of the data returned (which must be stable), etc.

burdges commented 9 months ago

I need a way to verify the authenticity of block headers without verifying block bodies

@eskimor We need a Merkle proof into the chain state for the sassafras ticket and validator's public key. You guys did a bunch of this in async backing, so can one of you guys who @davxy how that worked?

burdges commented 9 months ago

Actually @tomaka do you have an example of using a Merkle proof for a validator key? We must do this for babe already I guess, no?

tomaka commented 9 months ago

The way it's done in smoldot for Babe is by calling three runtime functions that return data structures containing all the information needed: the list of current and next epoch validators, current epoch number, slots per epoch, etc

It could in theory also simple be done by reading directly from the storage. The fact that it's a runtime function call is just for pragmatic purposes. It's to make it possible to change the format and location of the values in storage without breaking what the function returns. Also runtime functions have a version number, which again is useful for backwards compatibility, while plain storage items don't.

So the Merkle proof is actually a "call proof". The proof generator calls the function(s) and builds a proof containing all the trie nodes that are accessed during the call.

My point above is that ideally this RFC should describe which runtime functions to call and what they return. Or if it's too difficult to design this ahead of time, mention that it will be designed on the fly with that constraint in mind.

davxy commented 9 months ago

My point above is that ideally this RFC should describe which runtime functions to call and what they return. Or if it's too difficult to design this ahead of time, mention that it will be designed on the fly with that constraint in mind.

@tomaka I already have a quite clear idea of what are the required runtime functions and their interfaces. I'll update the RFC soon. I took some time to experiment with the WiP pallet first

burdges commented 8 months ago

Around the randomness-ticket cycle here, we have six stages which occur in sequence:

authority set determined defined in previous epoch,
accumulate block randomnesses for full epoch to define future randomness r,
wait for probabilistic finality on r,
make & publish tickets using r,
wait for probabilistic finality on ticket set that uses r,
claim tickets in full epoch.

We always want 1 & 5 to be full epochs of course, but exactly how 2-4 align with epochs remains a question. If each of 2-4 requires a full epoch like in praos, then we've many epochs between becoming an authority and doing the work, which causes annoyances elsewhere in the protocol.

We instead optimized this by placing 2-4 into one single epoch, so the whole cycle does not last longer than in praos, but this means how long each of 2-4 take becomes a configuration parameter, along with the full epoch length, so how do we choose these?

A full epoch should be long enough so that we believe one honest node's block randomness gets accumulated, so that a randomness adversary loses control over the randomness. They can still bias randomness, but this bias becomes relatively small.

We need 4 to be long enough to have probabilistic finality upon the set of ticket, meaning so adversaries cannot fork out blocks that posted tickets during 3. We need 3 to be long enough that all valid tickets get posted to the chain, which depends upon the chain's censorship resistance.

We need 2 to be long enough to have probabilistic finality on the accumulation r of randomness in the previous epoch. If 2 winds up too short, then we do not fail per se but now different sassafras tickets make sense for each surviving chain fork. In other words, prover and verifier time wind up multiplied by the number of forks, which becomes considerable CPU time. Although bad, I think 2 could run into 3 slightly, which gives us some slack for 2.

A priori, I'd suggest 4 be roughly half the full epoch, with 2 and 3 being a quarter epoch each. If 3 needs more time, then we could go as small as 2 being 1/6th of an epoch, and 3 being 1/3rd of an epoch. If we need more than 1/3rd of an epoch for 3 then we should discuss optimizations I think.

We sort the ticket set during 4 too, but when in 4 matters. If too early, then we'll sort separately on each fork. If too late, then we might end the epoch without the sorted ticket list. Aka we have

4a. wait for ticket set 4b. sort ticket set 4c. wait for sorted ticket set

A priori I'd suggest we sort right in the middle, so all told our initial config should be: 1st quarter does 2. 2nd quarter does 3. 3rd quarter minus epsilon does 4a. around 3rd quarter mark do 4b. 4th quarter does 4c. We build in some flexibility on 4b however.

davxy commented 1 month ago

/rfc help

paritytech-rfc-bot[bot] commented 1 month ago

The RFC action aims to help with the creation of on-chain RFC referenda and with handling the RFC PRs.

The main commands are /rfc propose and /rfc process.

See usage instructions.

davxy commented 1 month ago

/rfc propose

paritytech-rfc-bot[bot] commented 1 month ago

Hey @davxy, here is a link you can use to create the referendum aiming to approve this RFC number 0026.

Instructions

1. Open the [link](https://polkadot.js.org/apps/?rpc=wss%3A%2F%2Fpolkadot-collectives-rpc.polkadot.io#/extrinsics/decode/0x3d003e02015901000049015246435f415050524f564528303032362c33313762623761366334316161323234363233636435343639383761333634376332656165663934643462313939306364363363303539363331663832393364290100000000). 2. Switch to the `Submission` tab.

3. Adjust the transaction if needed (for example, the proposal Origin). 4. Submit the Transaction