Fast Finality in Filecoin (FIP-0086)

[hmoniz]

FIP: https://github.com/filecoin-project/FIPs/blob/master/FIPS/fip-0086.md
Project brief: https://docs.google.com/document/d/10IE6hfK16dbrH9lPWlPS7vGcFRRTAtYzjXEEeYhdkek/edit#heading=h.gigkakuxvvlw

Problem

Currently, in the Filecoin mainnet, a tipset is considered final after 900 epochs. This value corresponds to around 7.5 hours; each epoch lasts 30 seconds. This long time to finality hinders the user experience considerably. It limits applications on Filecoin built with FVM and IPC. Exchanges must have a very long confirmation period for users to manage their FIL assets. Bridges are also notoriously affected by the long wait times in transferring assets.

Goal

ConsensusLab would like to propose a mechanism for the fast finalization of tipsets called the finalization module (FM). During regular network operation, we expect the FM to finalize tipsets within their epoch of proposal. This single-epoch finalization of tipsets is a significant improvement from the current 900-epoch finalization delay.

Background

Expected Consensus (EC) is the current mechanism by which participants in the Filecoin network reach an agreement on tipsets. A tipset is a set of blocks with the same epoch and the same set of parents.

EC is a longest-chain protocol (more accurately, a heaviest-chain protocol) in which each participant builds the chain speculatively as it receives blocks from the network. The protocol elects a set of network participants (i.e., storage providers) to become proposers on each epoch. Each proposer can build a new block and broadcast it to the network.

Additionally, each participant executes a continuous task colloquially called the EC syncer. The syncer receives blocks from the network, performs validation checks, and adds the blocks that pass validation to the chain. In the figure below, we depict this syncing mechanism in a simplified way with one block per tipset. On the left side of the figure, we have the syncer receiving blocks from the network and adding them to the chain. On the right side of the figure, we have the chain where each tipset points to its parent tipset.

If two or more blocks/tipsets of the same epoch have a different set of parent tipsets, this creates a fork in the chain. We can see in the figure that there are two different paths from epoch 104 to epoch 101, resulting in a fork. Forks are resolved using a fork choice rule, a deterministic algorithm that assigns a weight to each tipset in the chain and returns the heaviest path from some tipset, called the head, to the genesis tipset. We refer to this path as the canonical chain. In the figure, the tipset 𝒉 is the head, and the path from 𝒉 all the way to the genesis block is the canonical chain.

If a new block, however, were to be appended to the alternative path (represented by the dashed lines), this path could become the heaviest and, consequently, the canonical chain. This change is a reorganization - a different path to the genesis tipset becomes the canonical chain due to becoming heavier than any other path. We say a path is finalized when a different path can't become the canonical chain.

In EC and, generally, longest-chain protocols, the probability of a path from some tipset 𝒉 to the genesis tipset becoming finalized increases with the number of descendent tipsets of 𝒉. A tipset “inherits” the weight of its descendants and thus becomes harder for a different path to overcome that weight. Over time, that probability becomes high enough that the tipset is considered final for all practical purposes. In the Filecoin network, a tipset is considered final after 900 epochs (or, equivalently, 7.5 hours) from its proposal.

Solution

We propose to solve the problem of the long finalization delay by introducing a finalization module (FM). The figure below shows how the FM augments the existing system to finalize tipsets with a very low delay.

The FM consists of two components:

• A Byzantine fault-tolerant consensus protocol called Granite.

• The Finalizer. A straightforward algorithm (despite the ominous name) that uses Granite to finalize tipsets. Finalizing a tipset also finalizes the path from that tipset to the genesis.

We can see from the figure that FM requires the chain to expose only two operations: (1) read the current head, and (2) mark a tipset as finalized. Notably, the FM does not interact directly with EC. The only changes required in EC are adjusting the fork choice rule to account for the tipsets marked as finalized by the FM, and removing the 900-epoch “lookback” finalization rule.

Granite

Granite is a protocol that solves the consensus problem in its classic formulation from the scientific literature. Each participant inputs a proposal value, and the protocol outputs one of the input values as the final decision value. We emphasize final because, unlike a longest-chain protocol such as EC, the output of Granite is immutable.

Granite exists in partially synchronous and asynchronous variants. We have a working paper that specifies the partially synchronous variant in detail. We discuss here some of the features that make Granite a desirable protocol for Filecoin:

• The protocol has optimal resilience, i.e., it tolerates f Byzantine participant failures up to just less than a third of the total number of participants n, i.e., n ≥ 3f + 1.

• Unlike PBFT, HotStuff, Tendermint, and many other protocols in this space, Granite is a leaderless protocol. This property makes it resistant to denial of service attacks because no designated participant represents the weakest link.

• Participants can have different weights, which aligns with how storage providers have different amounts of storage committed to the network. A participant's weight in the execution of the protocol can be proportional to their share of committed storage. As such, we can simply use the power table to define the membership in Granite.

• At an acceptable cost of resilience, Granite can employ self-selecting committees for scalability such that, regardless of the total number of participants, each communication step only has a constant number of participants broadcasting a message. In the context of the Filecoin network and its peer-to-peer overlay, this technique reduces communication complexity per participant from O(n * log n) to O(log n).

• Even when employing constant-sized committees, Granite is resistant to denial of service attacks due to the identity of the committee members remaining secret until after they take action.

• Low latency → fast finality. During periods of good communication, Granite will finish in 2-3 communication steps. We expect this to happen well within the 30-second epoch duration. We also define good communication very conservatively, such that we expect the network to provide good communication most of the time. Thus, we expect the FM to finalize a tipset in the same epoch the tipset is proposed.

Finalizer

The Finalizer is a simple algorithm that employs Granite to finalize Filecoin tipsets. It executes as a separate task in a loop. Each iteration of the loop consists of five steps:

1. Read the chain and obtain the current head tipset.
2. Propose the head tipset as input to an instance of Granite.
3. Wait until Granite completes its execution.
4. Upon completion, Granite outputs some tipset as the decision.
5. Mark the path from the decided tipset to the genesis block as final.

The figure below shows the chain after an iteration of the Finalizer in which Granite outputs tipset 𝑏. Notice that upon finalizing 𝑏, we also eliminate the fork from the chain.

Future Opportunities

The introduction of the FM also paves the way for future improvements to the network. In particular:

• Removal of tipsets. Tipsets are a consequence of EC and its nature as a longest-chain protocol. With the FM, we can move towards single-block epochs, simplifying network operation and the implementation of clients and removing delayed execution.

• Shorter block time. In EC, the long block time (i.e., 30-second epochs) is used as a stabilization mechanism to ensure that participants have more or less the same view of the chain. Due to its final output, we can leverage the Granite protocol to reduce block time significantly, particularly in its asynchronous variant.

Feedback

We welcome feedback from the community and look forward to stimulating discussion.

[raulk]

This looks promising. Thanks for the research, conceptualization and communication work here, @hmoniz!

Could you elaborate on the following topics? Some or all of these might be specified in the paper, but I think it's worth hoisting them to the discussion for easier accessibility and alignment.

• Granite consensus membership. Do all SPs elegible for block production become automatic members of the Granite consensus overlay/module? Can an SP participate in EC and abstain from Granite?
• Granite consensus economics/incentives. How do participants in Granite consensus stay honest, and specifically how does that map to Filecoin's cryptoeconomy?
• Commitment. Does Granite output a commitment on the Filecoin chain? Or does Granite stay as an independent overlay?
  • If the latter, what are the security implications for FVM actors/smart contracts that wish to rely on quicker finality for its operation (e.g. some dispute mechanism)? Would be great if on-chain logic could deterministically learn which portion of the chain has been irreversibly declared final.
  • In other words, can you expand on what happens in this step "Mark the path from the decided tipset to the genesis block as final."? You say "Notably, the FM does not interact directly with EC." -- I understand that, but the finalisation status of the chain could be tracked in an built-in / user-land Granite actor. If a built-in actor, the state transition could be executed as an implicit system message, but that would establish a harder cross-dependency between EC and Granite.

[hmoniz]

Hey @raulk. Thank you for the questions! Here's my take:

• Membership. What we have in mind is for the power table to define the membership in Granite. The power an SP has in the table translates to an equivalent weight in Granite. It doesn't have to be like this though. If there are advantages to having a membership other than the power table, we can go down that route. Granite is flexible enough to accommodate it. Do you have something in particular in mind?

• Incentives. So far, we are not anticipating changes to the cryptoeconomics of Filecoin. SPs who propose blocks that are included in a finalized tipset are still rewarded in the same manner. For Granite specifically, I think that a slashing mechanism for Byzantine behavior (e.g., sending equivocating messages) can be useful. Other than that, I don't think we would need to introduce anything new. Of course, this is open to discussion and I'd love to learn about different points of view.

• Commitment. Yes, there will be some information on the chain indicating which prefix of the chain is finalized. This will replace the 900-epoch lookback rule. Upon reading my post again, I realize that we were not very explicit about this. We don't prescribe a particular implementation. One possibility is, like you mention, an actor where we post a proof of Granite's latest decision. We're open to anything though. Like many other implementation details, this is something where the feedback from the devs will be crucial.

[ranchalp]

incentives. So far, we are not anticipating changes to the cryptoeconomics of Filecoin. SPs who propose blocks that are included in a finalized tipset are still rewarded in the same manner. For Granite specifically, I think that a slashing mechanism for Byzantine behavior (e.g., sending equivocating messages) can be useful. Other than that, I don't think we would need to introduce anything new. Of course, this is open to discussion and I'd love to learn about different points of view.

AFAIK, most quorum-based sub-protocols in other blockchains (Cosmos, Cardano, etc.) propose similar arguments. However, we can discuss more complex incentive mechanisms, even explicit rewards for participation (ala Ethereum's finality gadget). I would however stay away from explicit rewards for participation if possible, as WinningPoSts cannot be used for Granite participants (a Granite vote cannot become invalid if received late in time to ensure safety without synchrony).

Also, the FM would bring a tiny increase in communication and computation from participants in exchange for a very significant improvement in the service that they offer, which would drive the value of the service up and generate indirect revenue for SPs.

Commitment. Yes, there will be some information on the chain indicating which prefix of the chain is finalized. This will replace the 900-epoch lookback rule. Upon reading my post again, I realize that we were not very explicit about this. We don't prescribe a particular implementation. One possibility is, like you mention, an actor where we post a proof of Granite's latest decision. We're open to anything though. Like many other implementation details, this is something where the feedback from the devs will be crucial.

My preference is to modify blockheader structs adding a pointer to the latest finalized block in a new parameter. This easily signals the state of power table used by the SP to propose the block, and determines the weight of the block (as the fork choice rule must be changed to first choose chain with the heaviest finalized prefix, and only measure the weight of the suffices following the heaviest finalized chain in order to break draws).

[arajasek]

I'd suggest editing the OP to mention that the proposed membership of the Granite committee is the power table (though this is potentially open for discussion).

[hmoniz]

Done. I've added it to the third bullet point in the Granite subsection.

[aakoshh]

I also think adding the finality certificate to the header is a better solution than adding it in an actor, because it makes it visible to things like light clients that do not want to execute blocks, and also makes it possible to evaluate two forks purely based on their headers, rather than having to download and execute both before deciding which is the canonical chain. Evidence of equivocation is also easier to prove based on headers.

[jennijuju]

Thank you team for getting this up! Bring my question from another private forum here: could you please shed some light on why the existing EC requires 900 epoch for finality? Im sure there are many challenges/issues to “simply” bring that number down, and would like to understand a bit more there!

[ranchalp]

Users in Filecoin can decide to locally consider a block as final before 900 epochs using local heuristics (e.g. a user will not wait that much to finalize a payment for a coffee). The 900 epoch value being a explicit system parameter is the result of Filecoin explicitly requiring a conservative static finalization parameter to determine the state of the power table (as Lotus does not tolerate reorganizations of the power table). The concrete value was the result of an analysis of multiple attacks simulated on EC in a strongly synchronous setting, without any proof of correctness.

I do agree with the sentiment that we could modify EC to bring the finalization parameter down, but this comes at the cost of:
(i) Significant changes to the codebase
(ii) A finalization value still in the order of tens of minutes
(iii) Probabilistic guarantees that assume some form of synchrony
(iv) Deferred execution (unless we remove tipsets from EC, which involves either decreasing throughput in expectation or even more changes to EC)

Point (iii) is particularly concerning, and an assumption that is not to be expected from the Internet (even more so if the finalization time is brought down). A concerning attack example is that of a participant that suffers an eclipse attack for long enough finalizing the wrong fork of Filecoin.

In contrast, Granite offers:

(i) Minimal changes to existing codebase (just addition of FM in a modular way)
(ii) A finalization in the order of seconds (in the good case even within the same epoch of the EC proposal)
(iii) Strong provable guarantees of safety even without any form of synchrony
(iv) Path to remove deferred execution (and virtually removed already when Granite provides sub-epoch finalization)

[arajasek]

Thanks for getting this started! I'm excited for Granite, and think this proposal is well-motivated. @adlrocha was kind enough to give me a walkthrough of Granite a while ago, and I think it makes sense. I'm looking forward to feedback on the high-level idea from more people (in particular, anyone who thinks this is a bad idea).

I'm also looking forward to flesh out the details of how we would introduce this to Filecoin. I think some important blanks to fill include:

• a summary of the Granite protocol itself (we don't necessarily need this here, but we will definitely need it for the FIP itself)
• details on what running Granite would be like in Filecoin (who's in the committee, what are they actually saying to each other, whom do they communicate the "final" result to)
• what actually makes a block final? say I'm just a follower-node (not in the power table, not participating in Granite itself) -- how do I actually know what we've considered final?
  • In particular, are we proposing changing the structure of the BlockHeader itself to include some "link" to its finalized ancestor / "proof" of that finality?

[arajasek]

Awesome, thanks for the responses!

Committees: Our goal is to have full participation, i.e. all block miners participate in Granite. However there will be a practical limit (whether the current number of block miners, 3500, already reaches it or not), and as a result we should have a fallback to large committees if the number of block miners becomes too large for Granite to handle fast enough. The specific number is not known before we have an actual implementation and tests, but we are confident Granite can handle committees in the order of the current 3500 block miners.

Makes sense, thank you. I think it's fine to leave this part under-specified until we have an implementation. I agree that we'll want to describe (and implement) the large-committee fallback regardless, because it'll be important to have.

It sounds like the proposal is for participants to be weighted by their power in the power table, but it doesn't need to be done this way, correct? I think we'll wind up sticking with weighted by power, but it's interesting to think about other approaches.

The "final" result can be communicated to observers (i.e. clients), for example, by having the DECIDE message be sent via a different Pubsub topic to all of them. An observer, upon receiving enough DECIDE messages to account for a supermajority of quality adjusted power for the same value in the same Granite instance, can consider that block as final.
Strictly speaking, we do not need to change the BlockHeader itself (nor a built-in/user-land actor tracking finality). It suffices with broadcasting DECIDE messages to observers and changing the fork-choice rule to select the heaviest finalized chain first and then the heaviest non-finalized suffix that extends the heaviest finalized chain.

This is very interesting, thank you for the reply. I think everything you said is correct -- we could do this by simply tweaking the fork-choice rule. As an implementation detail, we actually already have this logic implemented in Lotus -- in addition to the 900-epoch hard finality, we also allow users to mark certain tipsets as "checkpointed". Any checkpointed tipset will never be reorg-ed away from. We could very easily extend that logic to effectively "checkpoint" tipsets as informed by the Fast Finality Module.

From my perspective, that gets the job done, and so we can leave the primary chain structure as-is. However, I suspect we'll want a lot more discussion on whether we want to change the block structure itself (and if so how, and what we stand to gain and risk by doing so). We could also consider approaching this in two stages -- a simpler stage one that simply relies on the client to track what is final, and a more involved future stage that moves the concept of that finality into the blockchain itself somehow.

[ranchalp]

It sounds like the proposal is for participants to be weighted by their power in the power table, but it doesn't need to be done this way, correct? I think we'll wind up sticking with weighted by power, but it's interesting to think about other approaches.

What are other approaches you had in mind? If participants are not weighted by power then there is an incentive for participants to increase their influence in Granite by dividing their sectors into multiple identities (a type of Sybil attack essentially), decreasing the tolerance to an adversary.

This is very interesting, thank you for the reply. I think everything you said is correct -- we could do this by simply tweaking the fork-choice rule. As an implementation detail, we actually already have this logic implemented in Lotus -- in addition to the 900-epoch hard finality, we also allow users to mark certain tipsets as "checkpointed". Any checkpointed tipset will never be reorg-ed away from. We could very easily extend that logic to effectively "checkpoint" tipsets as informed by the Fast Finality Module.

From my perspective, that gets the job done, and so we can leave the primary chain structure as-is. However, I suspect we'll want a lot more discussion on whether we want to change the block structure itself (and if so how, and what we stand to gain and risk by doing so). We could also consider approaching this in two stages -- a simpler stage one that simply relies on the client to track what is final, and a more involved future stage that moves the concept of that finality into the blockchain itself somehow.

This is very interesting, and certainly looks like a perfectly valid implementation. I would still like to eventually replace the 900-epoch lookback parameter altogether so that there is no possibility for an attacker to 'break' the system by delaying the termination of a Granite instance for longer than 900 epochs, but this is arguably a very far-fetched and very unlikely to take place (specially if we assume the current synchrony assumptions of Filecoin, which are not needed for Granite).

[jsoares]

We need to assess the ROI of changing the chain structure, and whether it's worth doing now or e.g. together with later tipset changes. Leveraging the existing mechanism to mark tipsets as final/checkpointed seems like a straightforward and elegant way to proceed, and should probably be our base case.

[arajasek]

@jsoares So my immediate instinct is to agree with you here, because making this decision would make implementation much easier (really just "Granite" itself needs to be implemented, the "integration" into Filecoin becomes almost trivial).

I think we need to discuss this further, though. I worry that there's going to be a lot lost if we don't have some way to (easily) "prove" why we consider something final. Being able to make such a "proof" doesn't necessarily need a change to the chain structure, though that's probably the easiest thing from a theoretical perspective. I see @Stebalien has already raised this point below, so maybe we can take the discussion there.

[Stebalien]

So, to make this provable, I think we'll at least need to create some provable form of the power table. We will also need some way to aggregate these pubsub messages into a proof.

As far as I know, neither requires changing the chain structure, although embedding a commitment to this provable power table into the block headers will likely make this easier. On the other hand, we can also do this by building a secondary chain on-top-of the main chain.

[ranchalp]

One thing we should discuss is that of a catch up mechanism in Granite (disregarding long-range attacks prevention as this FIP is not intending to solve that). That is, what a participant does when it disconnects for some time and reconnects later. I see 3 options:

1- Add to block headers a new parameter to the latest finalized block (locally seen), that includes some verifiable proof of finality. An example of a proof of finality is a list of the signed DECIDE messages signed by enough participants to account for 2/3s of the power in the power table. That is prohibitively expensive though, and threshold aggregation with weights is non-trivial. BLS aggregation can provide verifiability in about 500 Bytes with the current number of participants, for example. It can make support for committees more difficult though (see for example this WIP doc).

2- Implement a catchup procedure that navigates from the oldest power table known before the participant went offline, waits for the participants in that power table to re-send to the participant catching up signed DECIDE messages accounting for 2/3s of the power in the power table, and iterate through Granite decisions until reaching the head. This can be optimized by requesting only a constant number of participants (as they must locally have the required DECIDE messages). The drawback of this is that it is not verifiable with only on-chain information.

3- A sort of mix of 1 and 2. Have periodic verifiable 'checkpoints' that rest on-chain, and in between checkpoints rely on the catchup procedure (or directly wait for next checkpoint when catching up if they are frequent enough).

[anorth]

waits for the participants in that power table to re-send ...

I don't see why the participants from that power table are needed. They could all be retired by the time catch-up is started anyway. But all participants currently executing finality decisions must have that history of DECIDE messages (else how do they know the current finalised proposal is valid, which depends on the previous one, etc). So this seems like a small deal – all participants should have the history. It's just like a blockchain.

The drawback of this is that it is not verifiable with only on-chain information.

I'm not quite sure what you mean here. Given a power table, the DECIDE message should prove a decision on a next finalised tipset. That tipset then specifies a new power table, which validates the next set of DECIDE messages, and so on. If by on-chain you meant "in block headers directly", then yes the power table is not present in the block headers (but is in chain state, so is still verifiable). But probably we should put a power table commitment into either the main chain headers, or the blocks in a parallel Granite blockchain, so that it is all immediately verifiable from a chain of headers.

[Stebalien]

Is the current proposal succinctly provable? That is, we need some way to, given some proven granite consensus "block" at time T, validate some granite consensus "block" at tome T+1 without access to the rest of the Filecoin blockchain.

From the sound of it, granite doesn't cover this and doesn't produce any provable outputs (and requires access to, e.g., the Filecoin power table to validate). That helps achieve fast finality, but doesn't solve the overall goal of fast cross-chain communication.

[Stebalien]

We'd like to support trustless bridging (bridging without an oracle). To do that:

1. Both chains must have a concept of hard finality (ideally, fast finality for fast communication). There's no way to revert cross-chain, so, when sending a message from chain A to chain B, we need to wait for finality on chain A before we can consider the message sent.
2. It must be possible for each chain to validate, in a smart contract, that some tipset/block has, in fact, been "finalized" on the other chain. This makes it possible to, e.g., prove that a message was sent from chain A to chain B.

It's that second case that requires succinctly provable finality.

[aakoshh]

Perhaps a relevant paper here is Mithril: Ad-hoc Threshold Multisignatures. In Ouroboros the power table is fixed for times of two weeks (what they call epochs), which might be feasible to be exported into a smart contract where signatures can subsequently be verified.

[ranchalp]

(Also linking @aakoshh comment on finality certificates) One of the easiest succint proofs of finality I know would be a BLS aggregated signature, which can result in too large verification costs and on-chain storage for full participation (about 500B for 2^10 participants), and not immediately easy to preserve an optimized bitset (one bit per committee member to signal partial signatures present in aggregate) if instead we have VRF-based self-selected committees. There are other options, and this paper just accepted for S&P'24 is perhaps also a fantastic reference to compare the state of the art and for the paper's proposal itself: hinTS: Threshold Signatures with Silent Setup.

I am however wondering if we should just focus on fast finality for this FIP and abstract the discussion on succint proofs of finality for a separate FIP. For 2 main reasons:

1. Generating succint proofs can be considered an orthogonal goal. Even if the final design can be leveraged for optimizations in Granite (what we call message justification in the doc instead of re-broadcasting, for rewards through incentives, etc.), a future FIP can address those changes.

2. If the 'best' design for succint proofs is not already obvious (and I do not think it is), it seems to me like its design will be the result of many more cycles dedicated to an orthogonal-ish problem. Overachieving with this FIP can delay the overall goal of fast finality, instead of phasing out updates as we have them specced out and tested. I do think we should continue this discussion, just not that we should necessarily block this FIP to have a joint design for fast finality and succint proofs of fast finality.

[jsoares]

As already said above, I'm in favour of bounding the scope of this FIP and the subsequent implementation complexity. The way I see it, fast finality is a pressing need for everything, whereas trustless bridging is a nice-to-have. Provided the choices made here do not hinder the later implementation of proofs of finality, I find it reasonable to solve fast finality in Q1 and leave the remaining changes to Q2 (as it seems that's the upgrade schedule we're moving towards).

[Stebalien]

Trustless bridging is a high priority and was one of the primary motivations for fast finality, but I agree we can take it in multiple steps.

However, I really don't want to lock ourselves into a solution where we can't get provable finality. I also don't want to have to re-do a bunch of work to get there. E.g., we may want to pick a signature algorithm that can be aggregated.

[ZenGround0]

Is there a succinct comparison between granite and other existing / deployed finality gadgets from other ecosystems?

[ranchalp]

Work out of David Tse's group has been on my radar for a while i.e. https://eprint.iacr.org/2021/628.pdf https://arxiv.org/abs/2009.04987, though I haven't engaged at all.

In the same overleaf doc I cited above we have in related work a specific comparison to this line of work. David Tse's ebb-n-flow work does not provide an architecture for fast finality, but one hat enhances security (by tolerating both a <50% Adversary in synchrony and a <33.33% Adversary without synchrony). The way they achieve that is by having the already considered finaliz block from the LC protocol and give it as input to the BFT protocol. In Filecoin, this would mean waiting for 900 epochs and only then running Granite, which achieves no fast finality.

Besides, as @vukolic mentioned, their architecture does not prescribe a novel consensus protocol (that is why we compare with that work in the WIP doc we have for the architecture, not in the one for Granite).

Some of the other networks under discussion during today's core devs call like Cosmos and Cardano also come to mind. I don't know any of the details here but I don't think ethereum is the only network out there designing for fast finality at large scales. IMO there is a lot of value in the practical proof of a protocol securely running a real system.

Cosmos (Tendermint) is also explicitly compared in the related work of both Overleaf docs (latest version in the Granite doc), particularly cited in the comparison with leader-based protocols: "The presence of a designated leader introduces a bottleneck in the consensus process, limiting latency and throughput, as the speed at which the protocol decides outputs depends on the leader’s computational power and the bandwidth and latency of network routes connecting participants to the leader. Moreover, relying on a single leader creates a single point of failure, making the protocol vulnerable to attacks or disruptions if leaders are repeatedly compromised or experience issues (e.g., Denial-of-Service attack)". The same occurs for the BFT versions of Ouroboros (line of work of Cardano), with all of them also requiring to assume synchrony for safety (vulnerable to network disruptions).

In the case of the longest chain implementation of Ouroboros (the one in present day Cardano), like with any other longest chain type of protocol, finality needs to span an amount of time at least in the order of tens of minutes (and in fact they recommend a day): "Transaction finality can be achieved in approximately one day, and cannot happen in less than a day, according to Ouroboros consensus design. Note that although a high level of confidence is already reached in a matter of minutes or hours, the probability of a block being ultimately discarded decreases exponentially with its depth and the number of nodes that have to adopt this block".

I strongly suggest we have in depth yet compact comparison of Granite wrt state of the art. A table found in many papers would help the discussion.

Definitely agree we should do this eventually (although the main points of comparison are already there in some of our docs), and also compare with specific latency results once we have an MVP.

[aakoshh]

@ZenGround0 have you looked at the followup paper https://eprint.iacr.org/2021/628 ?

I believe that one does provide faster finality. It's a similar construct to the Ebb-and-Flow protocols, but also modifies the LC to respect the finality decision, thus, when there is no network partition, there is fast finality, when there is a network partition, there is either liveness for clients still following LC, or safety for those following the BFT, so clients can choose what they value more.

[ranchalp]

@ZenGround0 have you looked at the followup paper https://eprint.iacr.org/2021/628 ?

I believe that one does provide faster finality. It's a similar construct to the Ebb-and-Flow protocols, but also modifies the LC to respect the finality decision, thus, when there is no network partition, there is fast finality, when there is a network partition, there is either liveness for clients still following LC, or safety for those following the BFT, so clients can choose what they value more.

Skimming again through this paper and yes, the architecture of their "Accountability gadget" is very similar to the one we propose here with our FM, and allows for fast finality. They use HotStuff which is less fitted for open systems than Granite due to the role of a leader (see my above comment for more details on why that hinders performance, or some of the docs I linked there).

Full disclosure: since it is brought up by their paper, just like their accountability gadget, our FM would lead the Filecoin system to have to chose between availability and safety in the event of extremely adversarial conditions. For example, if we leave the local lookback parameter of 900 epochs in the client's implementations, we favour liveness after 900 epochs. That is, if an adversary prevents termination of a Granite instance for 900 epochs or more, there is no guarantee that the FM will finalize the same tipset that is "considered final" by the lookback parameter.

@hmoniz and I discussed this inherent (and unsolvable) consistency-availability dilemma and this is why we would prefer just removing references to 900 epochs as a finality value in the implementation and instead pointing to the latest finalized tipset by Granite, so as to favour safety over liveness. In any case, we are talking about an extremely unlikely scenario:

• With full participation, as long as the adversary controls less than a third of the total power, it cannot prevent liveness of a Granite instance.
• Using committees, with the current power table size of M=3500 miners see the attached figure that provides the required committee size (y-axis) to ensure safety and liveness against an adversary controlling a percentage of the power table (x-axis) (for simplicity assume equal weight for the purpose of the figure, easily adjustable, and assume committees are always exactly the targeted expected size) except for some negligible value. We also plot it for M=35000 and for the asymptotic value (M considered infinitely large, so repetition disregarded).

Then again, this is extremely unlikely to happen and I do not think problematic in practice, besides just being a dilemma that any solution would have to deal with.

[ranchalp]

See this table for a Comparison of different approaches and protocols for fast finality in Filecoin.

[ZenGround0]

Appreciate all the replies they are very clarifying

[anorth]

I have been reading and evaluating the Granite paper and have a range of points and concerns. I understand the paper is presented as a consensus algorithm independent from Filecoin, but the position for all of my comments is motivated by its use by Filecoin, and I think that perspective is all that this forum need concern ourselves with. I couldn't find a great structure for my comments, so please forgive the form of a long list.

I am not a consensus researcher. There's a good chance that some of my comments are rooted in some misunderstanding of common background knowledge or similar. Please do point out when that is the case. But please also understand that most of the stakeholders in Filecoin protocol, including most of the core devs and technical contributors, are also not consensus researchers. Any eventual complete proposal for protocol change needs to be understandable by me and others, so my misunderstandings should also point to where explanation and documentation will eventually be needed in order for the community to evaluate a proposal. That said, I hope my relative naiveté is of some advantage here in thinking about things from a different point of view.

Some of the below might be appropriate to break out into top-level comments so we can have a threaded discussion, but I can't tell which ones yet.

Required properties, goals etc

Somewhere between the opening discussion above and the Granite paper is a missing piece of alignment about what requirements we have for a finality protocol. "Fast" is an obvious goal, but I mean what properties we want of the integrated protocol. We need these to be articulated so we can evaluate a protocol proposal against them. E.g.

• No two correct nodes should ever finalise a different tipset at the same epoch, or tipsets that aren't on the same chain
• The protocol should never finalise a tipset unless at least half the QAP considers it to be on the heaviest chain
• The protocol should be accountable, so that attempts to undermine it are economically punishable
  Etc. I'm sure there's a standard set for consensus algos in general, and then some more for their specific integration as finalising modules for blockchains. These would give good context to those reviewing and analysing the proposal.

Beyond requirements, there are also desired properties. Latency under certain circumstances is one. Multiple posts above have pointed out a desire for the finality to be externally verifiable, especially in smart contracts, without requiring evaluation of the entire EC blockchain. A solution to this would probably answer questions about catch up, indefinite rebroadcasting etc. My impression is that there is some attempt to ignore this desire, but I caution that this may amount to merely postponing the debate until you've already done a lot of work that might need to be redone, vs gaining better alignment up front and then doing the work once.

Weights are definitely needed, probably committees too

The paper is mostly written for an environment of a small, fixed number of equally weighted participants, but this is not the Filecoin environment. Participation must be weighted by the power table. The section toward the end that states some adjustments for weighting is a very difficult way of understanding the resulting protocol. I think it's incomplete. For example it mentions replacing comparisons of counts of nodes >= sums of weights, but does not mention how to adapt counts of nodes == sums of weights; but equality conditions are used e.g. in message validation for PREPARE. An exact match of weight may not be possible. The 6-page separation makes errors like this inevitable. We'll need a description of the protocol as Filecoin is actually supposed to execute it.

Similarly the quadratic message complexity of full participation is probably not ok. We should design for at least 100x participation than todays levels. So we need committees and weights. The paper considers as a "patch" to the initial protocol, but this makes it hard to grok. We need a clear description of the protocol assuming weighted committees from the start. Analysis of security and performance needs to include the uncertainty of weighted committee selection.

What are nodes deciding on?

The Granite paper talks about deciding on an abstract value v. We need to be clear about what this is for Filecoin finality. A simple answer like an (epoch, tipset CID) pair leaves a lot to be desired. There are two things to be decided here: (a) which epoch are we finalizing, and (b) what is the tipset for that epoch? These are different types of things. For the epoch, there are multiple acceptable answers, the problem is just to pick one. For the tipset, there is generally at most one acceptable answer and the problem is to check that a majority have observed the chain sufficiently to independently agree on that. There's not much impact of malicious behaviour selecting an epoch, but great impact deciding a tipset. The values shouldn't necessarily be treated the same.

How are nodes supposed to agree on which epoch they're attempting to finalise? If they don't agree on this, the chances of getting a majority to agree on the same tipset seem diminished. Is that what CONVERGE is for? If so, should we limit its values just to epochs? Alternatively, if nodes diverge on the epoch they select, can we use blockchain structure to drive the finality for the shortest agreed chain? I.e. a vote for finalising some tipset is implicitly a vote to finalise any prefix of that chain too. Or is there some out-of-band mechanism like a clock that dictates what epoch nodes should select when proposing?

Message validation and monotonicity

I am currently a bit confused about the role of message validity checking. "Ensure that messages from faulty participants conform to the protocol" is an odd goal. Do we not assume that a certain fraction participants are correct (non-faulty)? If that's assumed, why do we also have to check their work? Ultimately, if we have signed messages from a majority of power COMMITing to the same value, what is the message validation protecting us from? Perhaps all I need here is explanation of the design (why this is the simplest way of achieving some goal), but it seems complicated.

Regardless, I think we need to express and prove some criteria for the message validation step. It seems likely that monotonicity is such a criteria: no message received can invalidate a message previously considered valid. Can we prove that? It took me quite a while looking at the validation for PREPARE to convince myself it might be monotonic (it is at least subjective, and depends on message ordering. A node can validate multiple PREPARE messages with different values because it can observe different majorities for the PROPOSE that lead to it over time, and another node might never consider the same set of values valid).

Why would a node ever vote for someone else's proposal?

Our context is validating a blockchain. Each node has a clear view of the chain that it considers correct and, as far as I can see, no benefit from ever voting to finalise a different chain. Nodes might have different views, and a node might accept that a majority of others have finalised a chain other than its heaviest. But I don't see why a node should ever vote for anything other than its heaviest chain.

Say we've solved the "which epoch" problem. This means each node has exactly one tipset that it considers the right answer. It doesn't matter what anyone else proposes, it should never vote for anything else (except a null in order to "agree to disagree" and start over). The goal of this consensus algorithm is to confirm that a majority of power has all seen the same heaviest chain. If they haven't, the algorithm should not decide anything. I consider it an anti-goal for the algorithm to attempt to finalise something in this case. This is a different context from other uses of BFT consensus algorithms, including when they are a root chain.

In that context, I am concerned with all the steps in Granite where a sets its v_i <- v to anything other than the value it started the protocol with: setting it to the mode of PROPOSE messages or the majority of PREPARE messages.

I can see there might be some confusion if we reconsider the "which epoch" problem, e.g in CONVERGE. Here, if we're working with (epoch, tipset) pairs, it is ok for a node to go with another's proposal for which epoch to finalise, but not ok for it to vote for any tipset at that epoch other than its heaviest. The artificial separation of the abstract consensus algorithm from the integration into Filecoin might be hurting us here. For example, nodes could CONVERGE only on the epoch first (and take lowest ticket); or they could broadcast a set of (epoch, tipset) pairs and then converge on the mode that includes its own vote; or propose one but consider it a vote in favour of any parents in the chain, etc.

Secret, weighted committees are incompatible with evaluating majority

Various points in the main protocol and message validation evaluate whether a count of messages exceeds n-f or ((n+f)/2 + 1. This requires knowing n and f. The weighted voting section suggest replacing these comparisons with w(PI) - w(F) and (w(PI) + W(F))/2. But because the committee selection is secret, the total committee weight cannot be known. It seems impossible for a node to ever decide that a vote has some fraction of power when it does not know the denominator. I assume that it's unacceptable for either (a) a node to COMMIT to a second, different value after receiving an additional PREPARE, or (b) some valid committee member's vote to be ignored. A node should only commit when it's impossible for subsequent messages to change its decision. The paper does have a few sentences that appear to address this, but I don't understand how this problem is fundamentally overcome.

This seems like a tricky one. I can see some practical benefits to secret committees, but I can't see how they can ever decide something safely and finally. We may have to give up the practical benefits.

Rebroadcasting forever?

There's a throwaway sentence about rebroadcasting messages to ensure they are received by participants, but this seems insufficiently specified (especially if making claims about message complexity). Rebroadcast for how long? I don't think practical protocol can be rebroadcasting history forever. Instead, participants who miss the original broadcast probably need to catch up somewhere targeted. This raises the question of validation of this consensus algorithm for a fresh node starting up. How does it reach a notion of finality? It can scan the EC chain and (depending on unspecified details) perhaps read a finalised tipset CID out of a recent block header, but then it would be trusting the EC chain to be declaring its own finality or something – how can it discover that a majority of power on the previously finalised chain voted for this finalised tipset? Of course this is recursive, but all the message history is gone.

A finalising blockchain?

In some of the literature, the finalising module is itself a blockchain, but with a finalising consensus algorithm (such as Granite). It thus has its own chain of historical blocks and messages/inputs to those blocks, including a commitment to the power/stake table with which to validate the votes. This model presents a natural catch-up mechanism that would also be much more efficient that fully validating the EC chain. It's also potentially a solution to finality that can be verified in smart contracts inside other blockchains and low-trust systems, which would make the interop/bridging use cases driving this in the first place that much more secure.

This structure is somewhat independent of what algo the nodes use to decide on the block at each round, and Granite or a variant could probably be used. But I think there's an important gap to be filled in here regarding how instances of Granite are put together into a verifiable commitment to finality among Filecoin nodes.

[ranchalp]

Thank you for the detailed comments. Many of these comments are valid in the context of reviewing the attached Granite Overleaf document for the case of Filecoin. The attached Overleaf doc is made modular and independent of Filecoin. Our upcoming document (colloquially known as "Granite FIP Draft"), that we will release by the end of today (TBC) addresses many of the issues and question marks that you have brought up. In a nutshell, though, Granite is only one of the components of the architecture that we propose for finality, the main component being what we call the Finality Component (FC). The Overleaf doc only addresses Granite and not the integration of it in Filecoin via the FC.

I would have liked to post a link to the Granite FIP Draft already in this comment, but with it being so close to almost full completion, it would be suboptimal to share it here now instead of requesting your attention to the doc soon after when it is more ready for a review. It also seemed suboptimal to not reply already to this comment just because we are working on finalising the Granite FIP Draft. See below my comments to your review.

Required properties, goals.

Properties and goals like the ones you describe are clearly defined in the Granite FIP Draft. All of the properties you mention are stated and proven, with the exception of punishing for misbehaviors, which is instead briefly discussed in the incentives considerations section of the Granite FIP Draft. The section successfully addresses punishing for misbehaviors that are detectable (i.e. equivocating messages).

Weights are definitely needed, committees too

The equalities can all be made into equal or greater instead when dealing with weights. This should however be clarified in the Overleaf doc, thanks for noticing. We should also add a full specification of the protocol including weights and committees, instead of comprehensively listing the modifications of the algorithm to adopt weighted committees, as you mention.
The analysis of security and committees in the context of committees can be done modularly (first assuming 1 node = 1 unit of power and no committees, and then considering committees), which I believe will help separate reasoning about the protocol and about the implications of using committees. This is currently done in this way in the Granite FIP Draft. The implications of using committees and weights are not disregarded.

Message validation and monotonicity

Message validation is a technique that is strictly required to ensure that Granite solves the consensus problem. While other protocols rely on a leader eventually being correct in order to ensure liveness and safety, Granite does not rely on a leader. Instead, the set of possible valid messages is restricted by message validation in such a way that a Byzantine adversary cannot break safety or liveness. I do not personally think message validation should prove any properties or be used to prove any other property than those that show Granite solves consensus.

What are nodes deciding on and why would a node vote on someone else's proposal?

This is properly defined in the Granite FIP Draft. In short, nodes propose the head tipset of their local heaviest EC chain, and the FC finalizes the heaviest common prefix c backed by more than 50% the quality-adjusted power (QAP). In practice, this means that the rest of nodes that proposed a different chain of which c is not a prefix need to reach a compromise and converge towards the heaviest common prefix as c is backed by more than ½ the QAP. If no node ever voted for anything else than their locally seen heaviest EC chain then we would only finalize proposals when all correct see the same thing. We can do this with a simple change of a number in the FC (from >50% QAP to >66.(6)% the QAP during what we call the quality step), but I am personally happy with having nodes converge towards whatever the majority of the QAP agreed on.

Secret, weighted committees are incompatible with evaluating a majority.

It is true that while the committee remains secret it is not possible to know the exact size of the committee. But it is possible to know the expected size of the committee. One can then reason about the security of the system if the expected size of the committee differs greatly from the actual size of the committee: the larger the committee is wrt the expected size, the easier for the adversary to cause a safety attack, while the smaller the committee is wrt the expected size, the easier for the adversary to cause a liveness attack. We analyze security with secret committees like this in the Granite FIP Draft.

Dealing with public committees opens an attack vector in which selected nodes are denied service, and the FC halts. I believe this to be a greater problem than the damage to safety/liveness derived from the delta between expected committee size and actual committee size.

Rebroadcasting forever?

Nodes that disconnect for a period of time can catch up by simply executing a separated procedure through which they request DECISION messages. These can be provided either by clients or by participants (other nodes). This is explained in the Granite FIP Draft. Messages do not need to be rebroadcasted any more or any longer than the existing EC messages: the same GossipSub parameters will work just as well for all Granite messages.
A finalising blockchain? On an abstract level, the notion of a finalising module being itself a blockchain is what we present in the Granite FIP Draft, and what we call the FC. I understand that it can be confusing when looking for something like this in the Overleaf doc, or even in the message that started this FIP discussion perhaps, but the doc that actually patches Granite into what you suggest in many of your comments is coming very soon (end of today I think), and will solvent many of these comments.

[anorth]

Message validation is a technique that is strictly required to ensure that Granite solves the consensus problem.

I get that, but why is it required? And then why again to that response? What goes wrong without message validation? What alternative approaches might resolve the same problem? I'm trying to understand why the protocol is designed this way. I find it a complicated part of the protocol to understand and get any intuitive notion of its correctness and necessity.

I do not personally think message validation should prove any properties or be used to prove any other property than those that show Granite solves consensus.

Above you said "a Granite vote cannot become invalid if received late in time to ensure safety without synchrony". Does this mean

1. The protocol is constructed such that a valid Granite vote must never become invalid later in time, regardless of message ordering. It's an asserted property of the protocol that a vote can only ever transition from invalid -> valid (i.e monotonicity). Outcomes don't depend on message ordering, only the eventual set received. Or,
2. A vote could become invalidated later in time, but the protocol is constructed to commit to an initial interpretation of the vote as valid, so even something later invalidates it, the node won't change its decisions. Outcomes do depend on message ordering.

If (1), then it seems like message validation monotonicity is an assumption of the later protocol. We should prove it to ensure that the protocol components behave as we think they do.

If no node ever voted for anything else than their locally seen heaviest EC chain then we would only finalize proposals when all correct see the same thing.

I think maybe we're saying the same thing but with confused terminology. If a node only votes for its locally seen heaviest EC chain then that vote can count towards finalizing any prefix of that chain. I'm not saying that a vote for a tipset must mean that tipset and epoch only, I'm saying it should (at least in early phases) indicate the whole chain up to that tipset.

The protocol should only finalise anything when a majority agree on which fork they are on since the last finalised tipset. Then they can finalise as far along that chain as that majority remains in agreement.

We analyze security with secret committees

Ok, I'll look forward to seeing and understanding that (cc @nicola @irenegia @lucaniz too). One thing is to understand the increase probability of safety violations given an adversary size. Another is the increased influence an adversary can have over having a non-majority value finalised, safely, and how long they might expect to sustain such influence (thus causing censorship etc). Let's discuss numbers before weighing relative risks. Protocols with leaders don't have this problem, do they?

With secret committees, are safety violations occasionally possible even when all nodes follow the protocol rules? There could be two different subcommittees each with >E(weight/2), couldn't there? If so, we need a fork choice rule or something for finality too 😝 .

The increased chance of safety violations due to outlier committee sizes + adversary makes it that much more important to understand accountability and be able to punish attempts.

[ruseinov]

I would have liked to post a link to the Granite FIP Draft already in this comment, but with it being so close to almost full completion, it would be suboptimal to share it here now instead of requesting your attention to the doc soon after when it is more ready for a review. It also seemed suboptimal to not reply already to this comment just because we are working on finalising the Granite FIP Draft. See below my comments to your review.

Any news about the aforementioned doc?

[jsoares]

@ruseinov We have a new version of the protocol described in Incentive-Compatible Granite Pseudocode and Proof, albeit not in FIP format. Feel free to comment and/or join us in #fil-fast-finality where the work takes place. Additional resources are listed in the F3 indexer.

[ruseinov]

Perfect. Will do.

[vukolic]

After 5 weeks of intensive refinement of the specification (big shout out to @anorth @matejpavlovic @ranchalp @mb1896 @arajasek @jsoares) - it is time for another round of public discussion.

We are inviting community comments and discussion on our latest drafts Fast Finality in Filecoin (F3) (fka Finalizer, from the beginning of this thread) high-level design document, as well as documents linked therein, and notably GossiPBFT (fka Granite) implementation of F3.

In the following days, the community can expect a formal FIP, yet we would like to solicit feedback as early as possible since the designs largely stabilized.

F3 specification explains the high level design of fast finality in Filecoin and interaction with Expected Consensus. Interested readers should start from this document. The document discusses:

• High level orchestration between EC and F3, favoring minimal changes to EC
• Defines properties of F3 including very specific requirements that come from Filecoin and EC (EC incentive compatibility and resilience to Filecoin power leakage attacks by a strong adversary)
• Links to GossiPBFT implementation of F3
• Links to detailed ongoing designs (pls see the doc) related to exchange of finality information among Filecoin SPs (participants) and light clients, as well as how finality information can be used by Filecoin actors (smart contracts).

GossiPBFT implementation of F3 is a core design document of the consensus implementation of fast finality. We refined the previous proposal considerably, tailoring it to Filecoin and EC along the way. The end result can be seen as a variant of the celebrated Castro/Liskov PBFT protocol, maintaining its key invariants and common-case message pattern, without many of its limitations. Namely GossiPBFT:

• is tailored to using broadcast communication implemented by GossipSub, which is already used by Filecoin/EC
• is a leaderless protocol and avoids rotating leader bottlenecks and attack surfaces which the original PBFT features.
• entirely avoids PBFT view change protocol which has been traditionally the most complex part of PBFT to reason about and implement. In a sense GossiPBFT embeds PBFT view change in the 3-phase common-case message pattern and explicit abort signals.

We presents two versions of GossiPBFT: 1) base one with evidences embedded to messages (ala PBFT OSDI'99) which can be made really efficient by using BLS/Schorr signature aggregation, and 2) a version without evidences (Appendix A) that incurs a tradeoff of more elaborate background message validation and a stronger assumption on GossipSub.

In the meantime - implementation efforts have already kicked-off. Have a sneak peak at @anorth 's simulator (WIP) (https://github.com/anorth/f3sim/). We also have a WIP PlusCal/TLA+ GossiPBFT specification which is linked from the GossiPBFT design doc.

[jsoares]

The FIP has been submitted and is currently pending editor review (#896). We're yearning for feedback, so please go and read it!

Note that the FIP presents a more recent version of the protocol than the documents linked above. The documents still provide some more detailed reasoning and background information that wouldn't make sense to port over, and they're useful in that capacity, but please take the FIP as the authoritative version of the proposal.

[jennijuju]

The mention of power leakage attacks leads me to the following question. Given the current 900 epoch finality, technically the network has the ability to detect and potentially react to sudden and malicious power overtake (increase total power to 1/3 QAP within a short period of time) by one actor within 900 epochs. Responses could look like an emergency upgrade that reverts the malicious power overtake.

Similarly, implementations like lotus have flags LOTUS_DISABLE_NETWORKNAME to revert an unsuccessful upgrade within 900 epochs upon its activation under extreme circumstance.

I think the implementation mitigation pathway (emergency rollback mechanism) in the new EC+F3 world should be discussed before it is finalized in production mainnet.

cc @arajasek

[jennijuju]

Re: EC as the fallback in case of the F3 failures

Assuming with the introduction of F3, how could services that depend on/refer to finalities (taking certain finality period in execution logic, i.e: exchanges, bridges), detect and quickly react to the slower finality latency (increase the confirmation waiting period) when instant finality (f3) fails?

cc @Stebalien @Kubuxu

[jsoares]

F3 has been merged as (draft) FIP-0086 (https://github.com/filecoin-project/FIPs/blob/master/FIPS/fip-0086.md), and we're targeting deployment in nv23. Please continue to provide your input here or in #fil-fast-finality.

[Stebalien]

The current FIP states:

• If $p$ and $p'$ are honest, then every message broadcast by $p$ is eventually delivered by $p'$.

First, I assume that "delivered by" should have been "delivered to". But even in that case, this is not a safe assumption in the presence of network partitions and denial of service attacks against GossipSub. It's obviously impossible to maintain liveness under such conditions, but F3 still needs to be safe. Can we clarify how F3 depends on this assumption?

[ranchalp]

"delivered by" is typically also used on the receiver side (meaning that the receiver deliveres the message from the network to the protocol layer).

If a set of messages is not delivered to all its intended recipients then liveness may be lost but safety is preserved.

[Stebalien]

Got it. Can we remove the part about this being about honesty (this can fail even if all participants are honest) had to make it clear that this is just a liveness assumption.

[anorth]

Some threads for some technical review and considerations of the changes proposed in #998 (rebroadcast and queues).

The existing FIP skipped over the question of what to do when a message is received entirely. It just assumed they were all there for use in predicates like checking quorum. What the implementation actually does, which is necessary for any reasonable efficiency, is immediately process all messages that are received and maintain state corresponding to the aggregate decisions that they add up to. (So there is no need to subsequently reprocess any messages to calculate things like whether some value has quorum at some phase.)

#998 introduces an explicit queue for the first time, but this is a long way different from what is implemented or would be good to implement. I don't think specifying it this way in the FIP is a good idea because the FIP and implementation will be divergent in ways that are hard to mentally translate. Because the messages themselves are not retained, we can't implement the trim function as it is given in the proposed changes. Most of the FIP describes the algorithm in terms of predicates over sets of messages. The code doesn't directly implement these sets, but what it does implement is essentially a direct incremental computation of these predicates.

But I think we can make things simpler anyway. There's no practical problem with retaining messages from past rounds. The only thing we need to bound is spammable messages for future rounds. Only messages without justification are spammable. Given a rebroadcast fallback (such as that proposed), we can probably do fine with a crude dropping of messages from far-future rounds. But we chould also explore making no messages spammable, by requiring evidence that a strong quorum has reached that round (whether or not they agree on value).

So:

• Simplest option is just to specify that messages from N rounds in advance of the current are dropped (along with equivocations etc). Then rely on rebroadcast to catch up a node that was partitioned longer. Can remove all the queue stuff from the FIP. This is not as optimised as the proposal, but we can implement it (and, instead, message processing is optimised vs predicates over sets).
• Fancier and better in many ways would be to make message validity strictly require evidence that a strong quorum of nodes reached at least the previous round. This is more of a protocol change but then would make any, even implicit, queueing unnecessary by construction.

[ranchalp]

There's no practical problem with retaining messages from past rounds.

There must be some limit to that, and the absolute minimum for the rebroadcast to work is specified in #998 (no messages from past rounds are needed at all). Anything other than that is IMO an implementation decision and not part of the FIP.

Fancier and better in many ways would be to make message validity strictly require evidence that a strong quorum of nodes reached at least the previous round. This is more of a protocol change but then would make any, even implicit, queueing unnecessary by construction.

As noted in a discussion we had some days ago in the design doc:

If the only problem was COMMIT for 丄 (only message that carries no evidence), a much easier fix would be to require evidence for a COMMIT for 丄 (we can enforce this). The range of issues is broader however, for example: a partition can actually go much further ahead than another one with the help of some adversary, only for then the adversary to disappear and leave both partitions of correct unable to communicate with each other (the stragglers dropped the messages and the ones further ahead are not rebroadcasting anything).

Making messages harder to spam does not fix attacks like the one shown above or deal with message loss, which were part of the problems considered when proposing #998 . If we are just worried about an attacker spamming COMMITs for 丄, and not about message loss or distant partitions, surely much easier to just make COMMITs for bottom carry an evidence, but we should make explicit the assumptions that this implies:

(1.) No message loss (or some explicit limit to message loss), because making messages harder to spam does not fix message loss.
(2.) Assume the fastest participant can be at most δ rounds ahead than the slowest participant, and queue all messages δ rounds ahead.

So yes, the solution would be much simpler to implement, but the robustness of it is not comparable. If (1.) and (2.) seem reasonable in practice, no reason not to go with it.

Nevertheless, from your message I am understanding that the problem is with how to implement the Trim function as specified in #998 . Again, this only describes the bare minimum set of messages that must be kept for the protocol to work (be able to jump ahead and finish current round). Making all messages carry evidences does not change what is the minimum set of messages that a participant needs to keep.

My understanding is that you suggest keeping the message rebroadcasting and most of the pseudocode for jumping ahead from #998 , and instead change the Trim function. I think for this you mean that we do not really have a bounded queue at all (in the implementation), and instead make all messages carry evidences, plus have some implicit assumption that limit how much further ahead the fastest participant is comparatively to the slowest participant, in that their distance in rounds will not be as much as to overflow the queue of messages (assumption (2.)). Alternatively, instead of an unbounded queue, messages that are further ahead than some δ rounds can be dropped. This would be a less robust solution than the one currently in #998 , because of assumption (2.). If instead you propose to have a bound with some smart trimming (but more implementation-friendly) such that all messages from the current round and from the greatest round known are always kept in the queue, then that works. Keeping more messages than these in the queue brings no advantage (in terms of robustness), but can be justified if it makes the implementation easier. Anything that is easy to implement but keeps at least all messages in the current round and in the greatest round known works.

[anorth]

We discussed this in person, I'm summarising.

The spec currently says how to implement a message queue and trimming, and this is obscuring the requirements. The requirement seems to be to keep everything for the current round, all valid CONVERGE and PREPARE from the latest round that any valid CONVERGE has been received. Plus QUALITY, DECIDE.

In practise there is no problem keeping all non-spammable messages. If we drop equivocations, there is a fixed number of messages (fixed state size) per round, and through cryptography we know that these messages only exist if 2/3 of the power are actually executing in that round. There is no realistic number of rounds that could be executed that could strain the memory of a modern computer: hundreds or thousands is fine, and with exponential timeouts this would imply timescales way beyond where humans would intervene.

So, good to declaratively specify the minimum messages to keep (and see thread below for loosening that spec). But drop the queue and trim functions that attempt to specify how.

In practise we will only drop the spammable COMMITs for bottom which are outside the current round. As we discussed, it's not trivial to justify these since the preceding PREPARES may be for many different values, so the signatures don't aggregate.

[anorth]

#998 has been updated to remove mention of an explicit queue and trim function, instead delivering messages immediately, or dropping unjustified messages from future rounds.

[anorth]

#998 again. The location of the call to shouldJump is awkward for implementation. The parameter timeout is particularly wierd, where it's trying to reference a value from the current phase, but has no reference for it. If we assume it's referencing the value first initialized at line 4, there is no reference for timeout since when has expired.

I think this is mainly an issue of clarity and engineering rather than a fundamental protocol issue. This would all be much clearer if shouldJump was invoked directly from the main protocol pseudo code, and in particular was invoked:

• only in the steps for where a jump is possible,
• exactly after a timeout has just expired, and
• only when that current cannot complete (the draft says "terminate" but I assume it doesn't mean protocol termination, just that the step is blocked waiting to hear from 2/3 of power)

Structuring it like this would remove a bunch of pseudocode and prose that is attempting to establish these conditions from the place that it's proposed. It would also match closely how it could be implemented.

As for the point above, I don't think the FIP should describe it in the current way because the implementation will need to be quite different, rendering analysis and audits of the spec far less useful as assurance that the algorithm as implemented is correct.

[ranchalp]

A jump can be triggered at any time, or else after the timeout expires if the participant is stuck in the current phase. Consequently, bringing shouldJump to after a timeout has expired would mean having two slightly different functions (or at least two slightly different calls to the same function): (i) one for when jumping is triggered immediately and (ii) one for when jumping is triggered by an expired timeout. Even for (ii), it could be that the timeout expires first and only after its expiration a CONVERGE message for a future round is received, meaning that the triggering factor to jump in case (ii) is not necessarily the timeout expiring but the receival of a message, which justifies where shouldJump is in the current pseudocode. That is why the pseudocode considers timeout a global variable and just access it directly from shouldJump. Not against changing this, but the rationale is explained here and the suggested change from above does not handle when a CONVERGE that enables jumping is received after the timeout expires.

[anorth]

We discussed this in person too. Summarising:

There's interplay between this and the tight bounds given for the message queue. If we keep more messages, we can simplify the jumping. In particular, if we loosen the message queue to retain all CONVERGE and PREPARE messages (each of which carries evidence of 2/3 power being up to that round) then we can make a simpler shouldJump that is a pure function of received messages and doesn't need to reference timeouts.

[anorth]

#998 has been updated so that the jumping decision doesn't depend on any timeouts, it's just a predicate of the received messages.

[Stebalien]

We're having an issue where the network never seems to reach a decision and we believe that this might be due to the lack of rebroadcast of quality messages. Specifically:

1. The entire network proposes P in quality.
2. Greater than 1/3rd but less than 2/3rds of the network sees a strong quorum of quality messages for P.
3. Importantly, the participant with the highest ticket sees this strong quorum for P.

As long as the highest-ticket participant keeps participating, we'll never reach a decision because we have a weak quorum that will always vote for P.

• We'll never be swayed in CONVERGE because we'll never have a strong quorum for anything but bottom in COMMIT.
• We'll never be swayed in COMMIT because we always commit to bottom.
• We always COMMIT to bottom because we can never reach consensus in PREPARE (more than 1/3rd vote for P, but less than 2/3rds).

[Kubuxu]

I see. I will look for an alternative, as in a more fair, selection function.
The issue is a significant bias in the function we used.
Scenario: one participant with 50% power and 50 participants with 1% power each.
Assuming one of the 1% participants rolled max ticket (I'm biasing things against the large participant), this results in this 1% participant getting ticket quality of 1% (ticket_quality = ticket * weight/total_weight). This means that the large participant only needs to roll a ticket better than 0.02 (ticket = ticked_quality / (weight / total_weight) = 0.01 / 0.5 = 0.02), which will happen 98% of the time.

[Kubuxu]

I think we have to transform the uniformly distributed ticket into an exponentially distributed one.
This has a property that the minimum of independent exponential random variables is itself an exponential random variable.

[Kubuxu]

There were two bugs: one related to the ticket quality function, and the other was that we kept only the first ticket per converge value.

[Stebalien]

Yep.

Rod suggested:

1. Picking a subset of the tickets based on the power (e.g., how we select EC winners).
2. Randomly selecting from there.

I.e., your chances of being "in the running" are proportional to your power.

He also pointed out how lassie does this: https://github.com/filecoin-project/lassie/blob/main/pkg/session/state.go#L315-L338. That's the "correct" way but it's not very stable.

[Stebalien]

Well, your math skills are better than mine. That log-based function you proposed works perfectly in my simulation.

[Stebalien]

Proposed improvement to handle missed quality messages (addresses part of #809 (comment)):

1. Accept quality messages in every round/phase. We'll only accept one quality message from each sender, so we don't have any spam concerns. This should go a long way towards fixing the issue.
2. For rounds N+1, before every converge phase, add any newly discovered candidates. Basically, run a message-less quality phase every round after the first round.
3. Rebroadcast quality messages every along with the rest of message rebroadcast.
4. Implement the suggestion from leastathority where we pick the best ticket for a valid candidate, instead of picking our own candidate if the ticket we pick doesn't specify one of our candidates (protects against converge winners making bad proposals). (somewhat tangential but we might as well change this at the same time).

---

We could consider inferring quality messages from, e.g., converge messages but... I'm not 100% convinced that's secure due to how swaying works. It's also probably over-complicating things.

[anorth]

I'm glad that the observed behaviour has been tracked down to bias in the ticket selection, and that's the primary fix.

After that I'd err towards minimal changes, but points 1-3 seem fine anyway and the protocol could have been specified that way to begin with. I'll hazard easy to implement too.

Point 4 seems both less concretely motivated and harder to implement (which is part of the reason it wasn't done in the first place). And I would be hesitant to ad-lib a variation.

What's the remaining problem if point 4 is not done? Can it be quantified?

[Kubuxu]

Point 4 seems both less concretely motivated and harder to implement (which is part of the reason it wasn't done in the first place). And I would be hesitant to ad-lib a variation.

What's the remaining problem if point 4 is not done? Can it be quantified?

It is harder to quantify. One case it resolves is an adversarial ticket holder. We usually sweep it under the rug, but it can be a difference between a 12h instance and a 24h instance.
It also should result in shorter expected instance times when almost 1/3 of the power holds one conviction while 67% holds another.
The implementation is complete filecoin-project/go-f3#589, so if the implementation friction (and not theory friction) is the primary cause for putting it off, it should be no-factor.

[masih]

because in synchrony with a correct delta we will never need this

Aside from the ticket selection issue that's fixed, I wonder if we should revisit the current value of delta.

[Stebalien]

We've switched to 6s for testing but there are a few open questions:

1. Do we only need 6s for bootstrap (large messages)? Given the quality message issues, we had trouble getting past bootstrap with a shorter delta, so this is unclear.
2. How will this scale as the network size increases? Bandwidth will increase, which may increase message propagation time.

Unfortunately, we need to re-test at full scale with all the fixes in-place before we can come up with a final number.

[ranchalp]

This is if couldHaveBeenDecided returns false only I guess?

Yes, only if we were not swayed.

A slight variation of that proposal that I have implemented is:
Take all converge values and filter them down to ones that either are in the candidate set or sway us, then pick the best ticket out of these.

Said differently, we go through converge values; if a value is in our candidate set or sways us and has a better ticket than what we have chosen so far, use it. Repeat for all converge values.

Do you foresee any issues with this approach?

I actually think this should be fine (and that my previous comment is actually not right, your original point 4 is also fine even if not swaying) because of a property I implemented after Guy's audit in which it is ensured that if there is a decision by any correct then the only possible valid justification for a CONVERGE is for the decided value (Strong quorum of COMMIT for bottom or PREPARE for the value). Therefore both should be fine I think.

To be 100% confident about this (without spending too much time thinking about it) I would need access to the proofs that we made originally in the google docs (not sure if they are attached in the FIP repo or something), given I have not been thinking about this for a while now.