[fastx dist sys] Design and implement re-configuration

[gdanezis]

fastx operates in epochs. Within each epoch committee and stake are stable, but between epochs they may change. Between epoch a rec-configuration protocol is ran between validators and a consensus system to ensure safety and liveness. We need to implement this re-configuration mechanism, specifically:

• The logic by which a validator closes an epoch, and asks 2f+1 validators of the next epoch to provide a certificate over the set of certificates processed.
• The logic by which an epoch starts through a validator accepting the first 2f+1 certificates (on the consensus core), initializes its database, and start processing transactions.
• Efficiency improvements to minimize downtime.
• Make decisions and implement the smart contract on an L1/consensus core driving the governance logic, and sequencing the certificates of state between epochs.

[gdanezis]

Capturing a key conversation with @sblackshear :

It would be nice if our reliance on an external L1 was minimal (to none) and we can go some way to do this by reusing as much as possible fastx native operations to express state that is used in reconfig:

• Locking tokens to express stake can be done within fastx. This leads to a locked token object with a nominated delegate.
• Authorities can express their wish to reconfigure, and a snapshop hash of their state within fastx, and then restrict the orders that can be processed to those from other authorities.
• Authorities can express their approval of snapshots from other authorities as commands within fastx.

Give the above authorities are able to (1) close an epoch (2) gather 2f+1 authority states (or more) with 2f+1 votes each. Now comes the part that requires agreement: all authorities need to agree on the same 2f+1 set of certified states as the starting state for the next epoch. Then using this authoritative decision they can (3) decide the membership and stake distribution, and (4) start the next epoch.

The above outlines a design that only requires a validated one shot agreement, rather than a more complex core. And is an interesting option.

[oxade]

@gdanezis
Can an authority with considerable stake force an epoch if it leaves the network or dies?
Our notion of epochs seems like controlled transitions but is that always the case?

[gdanezis]

Can an authority with considerable stake force an epoch if it leaves the network or dies?
Our notion of epochs seems like controlled transitions but is that always the case?

We do not have definite answers on this.

There is no conceptual issue (with respect to safety) with a strategy that gives authorities some discretion about when to end the epoch. So in such a system an authority could:

• Vote to end the epoch after a time (end of day).
• Vote to end the epoch if it sees the network having many crashed authorities.
• Vote to end the epoch after a certain volume of certificates have been processed by it.

All that matters is that once f+1 out of 3f+1 of stake has voted to end the epoch (potentially for any personal reason), all others also vote to end the epoch up to 2f+1 votes, then we agree on the end-of-epoch-stake, derive the stake distribution for the next epoch, and re-start with that committee.

What I am trying to say is: the decision to end the epoch can be subjective for an authority (if we wish) -- and remember that in a distributed system time and timeouts are subjective.

So we can do any of these policies, or a combination -- the questions is what we should do out of all these choices.

[gdanezis]

The above also points to the need of an emergency protocol in case some delegates with collectively more than f+1 stake become unavailable / crash / byzantine, to recover the network. This is obviously disaster recovery, so no one expects it to be pretty or efficient.

Some thoughts on this:

• At this point we are operating in a synchronous setting, authority operators jump on discord.
• Priority should be: gather a state based on certificates. Propose it for others to accept. Integrate re-delegation orders to come to a set of delegates that are live. Launch new epoch with this set.
• If many different coalitions do the above we end up with forks.
• How are bridges / light clients affected by all this?

[huitseeker]

FWIW, the two following papers claim to do reconfiguration without consensus:
https://www.microsoft.com/en-us/research/wp-content/uploads/2010/10/paper-1.pdf
https://arxiv.org/abs/1607.05344

They are interesting because they speak about storage systems, where the question of passing state on from one configuration to the next is bundled with agreeing on who the members of the new quorum are. So far I've seen a plethora of people doing the later, but the former, not so many.

[asonnino]

We need consensus to support shared objects, but we are currently able to use it as a black box (it simply sequences bytes and is basically stateless). So if we end up using consensus for reconfiguration it would be great (if possible) to also use it in that way.

[asonnino]

Linking the sync story as it may be relevant for checkpointing before committee reconfiguration: #194

[LefKok]



The design below assumes an existing checkpoint functionality #194 :

We split the reconfiguration of an epoch into three steps:


1)Stake-recalculation step
2)New Committee Ready Step
3)Epoch Handover Step

The first step is triggered at a predetermined blockchain height. The first checkpoint after this height is considered the ‘’static stake distribution`` of the next epoch. Out of this, the new committee is well-defined. Care needs to be taken on the “chain quality” during the delegation period and before the checkpoint is issued. An easy way is to not charge extra for duplicate delegation transactions such that the delegators can send their votes to 2f+1 honest parties. If the honest parties do not see their delegation transactions approved, they can stop processing checkpoints until their delegations have gone through (more on this in OmniLedger).

Once the checkpoint is issued the new committee members at their own pace load it locally and each delegate sends a “bootstrap ready” transaction to the old committee. When a quorum of stake is ready the next checkpoint includes these messages signalling that the epoch is about to end. At this point only consensus blocks are allowed, fast-path no longer finalises (read below how to still allow fast path). Finally the 3rd step is triggered as the prior committee inserts an “epoch-handover” transaction at the end of their final checkpoint and then goes away (remaining available only for data availability). The next committee can take over right away and reenable the fast path.

This design decouples all the essential steps that are needed for a secure reconfiguration to occur. This decoupling allows for the necessary logic of defining the new committee and of providing the new committee sufficient time to bootstrap from the actual hand-over. As a result while steps 1 and 2 are happening there is no need for halting processing.

The time between 2 and 3 would need to stop finalisation of transactions that do not go through the consensus pipeline (single-owner objects).
This can be remedied either by going through the consensus pipeline even for these transactions or double-validating the transactions (which could be reduced to the normal operation if committees have sufficient overlap). The double-validation simply requires for a transaction issued after step 2 to get approval from the old committee (who is still authoritative over the state) and then get approval (by relaying the proof) from the new committee (which acts as a promise to not forget it and apply the moment they take over and before they accept any new transactions).

[LefKok]

Extending on the double-validation idea:

We can split the Sui single-object workflow in two parts: 1) Transaction Validation (TV) and 2)Certificate-Inclusion Promise (CIP). In normal operation TV is the consistent broadcast of the transaction and CIP is the persistent broadcast of the certificate (notice that consistent and persistent broadcast are the same protocol for different functionalities).

During the epoch change, the TV and the CIP responsibilities of the committee are handovered at different points in the process to the next committee. When the 2nd step (referred as bootstrap new epoch above) appears in consensus the new committee takes the CIP responsibilities, this means that any transaction TVed by the old committee need to get a CIP from the new committee, the old committee stops replying to these messages once it initiates the "epoch-handover" checkpoint.

When the epoch-handover checkpoint is available the new committee also bootstraps from this and takes over the TV duties. To start replying to TV messages committees members replay all the CIP messages they have acknowledged on their state and only afterward start processing TVs.

[asonnino]

What is exactly the “persistent broadcast” part? Is it another echo?

[LefKok]

Yes it is the same pattern as a consistent broadcast but its goal is not to prevent equivocation, it is to guarantee inclusion in the next checkpoint (so it needs quorum intersection with the checkpoint mechanism).

[asonnino]

So we only need this persistent broadcast upon committee change/checkpoint or do we need it all time (also as part of normal operations)?

[LefKok]

Always. Sui's workflow is 1) Consistent broadcast the transaction and 2)Persistent Broadcast the Certificate. They are both the same protocol (I can remove the difference if it is confusing), they simple have a different purpose. Στις Τρί 22 Μαρ 2022 στις 3:48 μ.μ., ο/η Alberto Sonnino < ***@***.***> έγραψε:

…

So we only need this persistent broadcast upon committee change/checkpoint or do we need it all time (also as part of normal operations)? — Reply to this email directly, view it on GitHub <#75 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACXPJMSZKJHG56DAWL3YRILVBHMT5ANCNFSM5KNX2FOQ> . You are receiving this because you were assigned.Message ID: ***@***.***>

[asonnino]

I see, so we have the overhead of making 2 extra round-trips for every transaction in order to support reconfiguration.

[LefKok]

No, it is zero overhead. The difference is that the second part of the transaction (sending the certificate and collecting 2f+1 acks to reach finality) is done with the new committee after some point. Στις Τρί 22 Μαρ 2022 στις 6:01 μ.μ., ο/η Alberto Sonnino < ***@***.***> έγραψε:

…

I see, so we have the overhead of making 2 extra round-trips for every transaction in order to support reconfiguration. — Reply to this email directly, view it on GitHub <#75 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACXPJMSGDWX7PDTSGBYTLPTVBH4GLANCNFSM5KNX2FOQ> . You are receiving this because you were assigned.Message ID: ***@***.***>

[asonnino]

After that we can workout the details such as cleanup, shared objects, etc

[asonnino]

Got it! Makes sense to me, and I think I understand why is is safe. I’m happy to go more formal

[gdanezis]

Just caught up on the double validation idea. I think this is viable, can we work out details and a more formal description + argument for safety? I get the intuition but the devil is often in the details. On the side of checkpoints, we will have them, no worries so steps 1, 2 in the post 15 days ago will be taken care of.

[gdanezis]

I closed the issue about adding epoch to transactions here: #74
We should work out if we should do this, according to the protocols here.

[LefKok]

Summed up the design and provided some proof sketches here: https://docs.google.com/document/d/1qFfT749PpNT20L8MhdNWt-9df90tIQE8M44W_zXzYA0/edit#

[lxfind]

Close this one as we have broken down the work to smaller issues