[Discussion] What is the authoritative state of a fastx system?

[gdanezis]

Today @stella3d asked a very important question, that is also at the heart of a lot of the client side issue, namely: What is the authoritative state of a fastx system?

We have potentially many authorities storing different objects at different versions, and having processed different certificates. What should a block explorer display? There are a few levels at which we can answer this question:

View 1. The state of the fastx system is the causal execution of the set of all certificates that can be retrieved from all authorities. In this view a replica of the system simply downloads and re-executes as many certificates as it can from authorities, and considers this the state of the system. Interesting, once we reason in terms of certificates, there are no forks or no need to rollback -- all certificates (subject to the safety assumption of the system) are correct and can be executed in any causal order to yield correct versions of the overall database.

View 2 (more strict). The state of the fastx system is the causal execution set of all certificates that can be retrieved from any >2/3 authorities. In this definition we consider a certificate to be within the state of the system if it has been shared and executed with at least >2/3 authorities, and therefore is guaranteed to be available if we ask any >2/3 authorities. This is in line with the reconfiguration logic as we are thinking about it today.

The short coming with Def 1 was that a certificate in the hand of 1 dishonest authority may not be guaranteed to be available. However, in all cases a certificate that is used by another certificate (through the objects created) is guaranteed to satisfy Def 2. So if one sees a certificate they know that all certificates that came before it will definitely be part of the state even if we use the more strict definition 2. But how can we ensure, as a replica, that a certificate we got from say a single authority, will also have been seen by >2/3 other authorities? There are three options: (a) we ask them if they have seen it, (b) we give it to them directly or indirectly (through a gossip sync) or (c) we see the objects resulting from the execution of the cert being used in the execution of a subsequent cert.

Is fastx really that different from other blockchains. Yes, and no, in my opinion. It is not different in the sense that different authorities have a different view of the state. Blockchains based on byzantine consensus (cosmos) also have authorities that are consistent but may have seen up to a different sequence of the stream of transactions. Proof of work chains are even worse in that there may be forks for a while, while the longest/most work chain is not the same for all.

However, what is different about fastx is that two consistent states cannot be compared in terms of the length of the sequence of transactions executed (as in BFT), or the hash of the last block (as in Pow). Instead if two authorities A1 and A2 in fastpay are consistent, it means that A1 has processed a set of certificates C1 and A2 has processed a set of certificates C2, and there is a common set of certificates that are both in C1 and C2 (intersection) that are in common. But otherwise both A1 and A2 may have some extra certs that they need to exchange to be in sync. (unlike the case of a sequence where one authority is always strictly ahead, and one strictly behind).

[huitseeker]

For the block explorer:

View 2 captures the state with respect to which a client can craft a new transaction and expect a non-zero chance of success (whereas any state element in View 1 but not yet in View 2, and used in a further transaction will always make the transaction fail if submitted at that instant).

As a consequence, I think View 2 is that we need to implement in the block explorer eventually. /cc @stella3d

---

Comparison to other blockchains:

It is not different in the sense that different authorities have a different view of the state.

I don't understand: authorities in FastPay, honest or otherwise, absolutely have a different view of the state. The only guarantee they have is that if we were to stop transactions flowing in, honest authorities would eventually converge to a single same state. On the other hand, in a PoS blockchain, there is no way for any honest actor to designate state that's anything but pre-negotiated to be unique across the system.

Blockchains based on byzantine consensus (cosmos) also have authorities that are consistent but may have seen up to a different sequence of the stream of transactions.

Cosmos is an ecosystem of blockchains. The majority of chains related to Cosmos are Tendermint PoS-based, and as a consequence, only speak of consensual state. Any other speech is by definition a hard fork. On the other hand, there may be block heights that an individual node cannot speak of yet: maybe that's what you meant?

Proof of work chains are even worse in that there may be forks for a while, while the longest/most work chain is not the same for all.

Indeed.

[gdanezis]

I don't understand: authorities in FastPay, honest or otherwise, absolutely have a different view of the state.

My grammar was confusing. Yes absolutely our authorities have a different (but consistent) state at any time. But we are not different from others in that respect. Other BFT chains also have authorities with different but consistent states (like Cosmos).

On the other hand, there may be block heights that an individual node cannot speak of yet: maybe that's what you meant?

This is indeed what I was suggesting. In a traditional BFT system where we all agree on a sequence, two honest authorities can have a different consistent state, BUT the difference can be expressed succinctly in terms of the height / sequence number they last committed. In contrast, in fastx the difference in the databases has to be expressed in terms of the subset of certificates we have processed in common (which is usually a larger amount of information and more complex to communicate for authorities to each other).

[stella3d]

I think View 2 is that we need to implement in the block explorer eventually.

I agree - the explorer shouldn't show anything to users that they can't yet rely on to take action.

[huitseeker]

For the block explorer:

FYI: View 1.5 adds something about the items that have been seen by ≥ f+1 authorities but < 2f+1. Once we have a synchronization mechanism, those are items that will be eventually synced by all authorities (but that acting on would result in a rejected transaction as of now).

---

Comparison to other blockchains:

This is indeed what I was suggesting. In a traditional BFT system where we all agree on a sequence, two honest authorities can have a different consistent state, BUT the difference can be expressed succinctly in terms of the height / sequence number they last committed.

But there's a huge difference this belies: in a blockchain, there can be no confusion as to the validity of the answer to a request: either

• the node does not manage to produce an answer,
• or the node gives a comprehensive and valid answer at the block height I asked about,
• or the node reveals themselves as byzantine by giving an invalid answer.

As I explained elsewhere in FastNFT, one can receive a valid answer that's incomplete, and that incompleteness is not attributable clearly to either of lateness or byzantine behavior.

In contrast, in fastx the difference in the databases has to be expressed in terms of the subset of certificates we have processed in common (which is usually a larger amount of information and more complex to communicate for authorities to each other).

Absolutely not. That's just one possible explanation. Another explanation is that the authority I asked something of is Byzantine and willfully hides part of the state.

In particular:

• we do not have the guarantee that the same query replayed twice (with the same authority) will yield the same results if it produces any,
• we do not have the guarantee that a query will produce state reflecting more or less transactions on the second time than on the first time (with the same authority),

The second result is the most surprising one:

• the reason that an authority may return more information on the second replay is because it may have learnt new transactions relevant to my query (address, object reference ...) since the first round,
• the reason that an authority may return strictly less information on the second round is they may decide to withhold some information,
• the reason that an authority may return an incomparable amount of information is that both of the above can occur simultaneously.

To summarize: in a PoW blockchain, finality is probabilistic. In a PoS blockchain, finality is at the instant of commit.

In FastX, it is up to whoever has copy of the a certificate for the signed transactions they want to be final, along with a remediation pathway when an authority does not reflect the effects of what's in that certificate upon query.. I'm paraphrasing the FastPay paper section 4.1.

[huitseeker]

I think this is now subsumed by the discussions in #194 (sp. the distinction between causal fragments of state and agreement). I'm tempted to re-direct folks there and close as duplicate, wdyt @gdanezis ?

[gdanezis]

Yes, lets close this.