Question about consensus algorithm behavior under non deterministic execution

Developers Education
1

I am reading the “white paper” and trying to learn little bit about the “internals”. While reading about the “consensus and message routing layers”, I was wondering about a case where all replicas are working as expected (and none is a bad actor) but the output from of each replica after executing an update call is different (e.g. if an update call returns the current system time retrieved with rust), then each replica would return a slightly different value.

From sections 2.2 and 2.3, I understand that only the so called “leader of the round replica” will be responsible to insert the new block with the corresponding “non deterministic” output (i.e. different time). Then, the “per round certified state” functionality in the “routing layer” of all “replicas” will be responsible to guarantee the consistency across all replicas using chain key cryptography. So, all replicas would detect that the block inserted by the “leader of the round” is not consistent with their execution output (in this example, a different time), so all replicas would raise a flag of “non deterministic behavior”.

Is this “mental” simulation correct?

2

IC doesn’t support non deterministic execution, all input values have to be agreed upon before replicas start executing code. Things like system time are determined before execution.

3

Yes, I know. My question was about the internal mechanism. I wanted to know whether I understood correctly the mechanism to detect “non-deterministic” execution and how it is distributed between consensus and message routing layers.

4

It’s not so much that the block can be non-deterministic, but the execution of that block. Divergence happens if each replica starts with the same state and the same next block (chosen by the leader), but at the end of execution, they somehow don’t have the same state.
After execution, each replica computes a certificate and then consensus requires that 2/3 of the replicas have the same certificate. A replica can then detect that it diverged if its certificate is different from the consensus one. So divergence is always by an individual replica vs the consensus state.
Of course, in the absence of malicious nodes any sort of divergence would be due to a bug.

1 Like