Reliable Timing

[igormcoelho]

Summary or problem description Some recent improvements in time were made, such as https://github.com/neo-project/neo/issues/1959, by promoting local time calculation to the earliest point block is known, however, there is still a inherent uncertainty on relying on single node timers. We argue that it's easy and possible to fix this, by trusting on the time provided by the median of all nodes, meaning that it's one of the 2f+1 honest nodes (no byzantine node will be able to propose any time).

We also argue that timestamp is an important service provided by Neo Blockchain, and if timing cannot be considered reliable, the proper approach would be to remove timestamp from blocks. So, instead of removing it, we can make it more reliable, as several real-world applications depend on it (timelock contracts, decentralized certificates, etc). Another application is for consensus itself, since every synchronous or quasi-synchonous consensus will always rely on time. If random time values are considered, consensus would never work (besides pure async consensus), so like it or not, we depend on a more-or-less precise time (and we can easily offer this, by simple changes).

Although we expect some deviation in times for every possible clock, we argue that honest nodes should make efforts to make their times as close as possible to the real time, and the punishment for not doing so can result in block rejection during consensus. This allows reducing current upper bound on time to virtually zero.

Proposal is to allow first round consensus (view 0) to consider past round consensus messages to infer the correct time of previous block, as a median, that provides the time of an honest node, regardless of any single-node attack. After change views, time strategy can be removed, as fallback mechanism, if one expects that catastrophic events may require "time adjustments" in the blockchain.

Do you have any solution you want to propose? Add time computation regarding median of time values indicated by previous 2f+1 consensus Commit messages (need to adjust payload and add this info). Next speaker would be forced to adopt some "current time" bounded by the indicated median value (speaker node could also re-send commits as proofs, in a more strict strategy, but since we are avoiding these overheads, we can simply assume that all nodes will keep each other times locally stored, so the median will represent in fact the variance between all honest nodes, ranging from f+1 up to 2f+1). If proposed value is not bounded up to extra "small timelimit tolerance", block is rejected. After change view, as a fallback mechanism, no time will be checked as usual (forcing long time resync adjustments, as usual).

Neo Version

• Neo 3

Where in the software does this update applies to?

• Consensus
• Other:

[roman-khimov]

Linking #626 there as it contains some relevant comments. Let me ask though, are we talking about block timestamp correctness here or following MillisecondsPerBlock more accurately? Because these two problems are different to me even though they're somewhat related.

[vncoelho]

From my perspective, #626 was a nice PR and pieces of it can still be used, @roman-khimov, it was well tested from our side on private and shared private nets, as well as testnets with delays. But at that time we decided to close it. It was also a little bit confusing. Later on we improved our understanding of consensus and possible improvements.

You are right about these two problems:

• block timestamp correctness
• MillisecondsPerBlock more accurately

But as @igormcoelho described, I believe that

Proposal is to allow first round consensus (view 0) to consider past round consensus messages to infer the correct time of previous block

is a good approach that will assist both, block timestamp correctness and also a good prediction for proposing next block and make MillisecondsPerBlock more accurately.

On the other hand, double speakers is what will mostly make MillisecondsPerBlock more accurately with less change views.

[igormcoelho]

Very good point @roman-khimov, there are indeed two problems being solved simultaneously with this proposal. Regarding first problem: The recent efforts made by community allowed to decrease delay over MillisecondsPerBlock, which is very good. However, current proposal intends to make this deviation precisely zero (as long as no change view occurs and network delays are "small"). Regarding second problem: reliability of timestamp value is not currently handled. Currently, there are worldwide notary systems that rely on timestamp provided by many blockchains. We expect some deviations to occur due to inherent nature of the problem (even on honest nodes), but currently we have absolutely no control over what is being proposed as timestamp.

On short, this proposal allows a strict control of timestamp value, by "narrowing it" towards the median value of 2f+1 nodes. This means that, even if f byzantine nodes try to intentionally push this down, or up, they will not be able to interfere (median goes towards the time of an honest node).

How to make that happen: As a first thought, we can put timestamp on Commit message, so each node will have "some knowledge" regarding the "notion of time", by taking the median of the accepted 2f+1 commits. Note that median will vary on nodes, since more than 2f+1 nodes may respond (creating many distinct Quorum), and byzantine nodes may also doubly respond Commit with different timestamps. Because of that, we assume that median will be allowed within the following safe zone:

f byzantine up commit values (may be repeated as 'down')
------ median safe zone up
f good responses (or not)
1
f good responses (or not)
----- median safe zone down
f byzantine down commit values (may be repeated as 'up')

In this sense: AllowedDeviation >= median_safe_zone_up - median_safe_zone_down + p2p_delays, which is the necessary control over local clocks in honest nodes (via any mechanism necessary).

If AllowedDeviation on safe zone is "large enough" (few seconds), every honest node will be able to agree on the proposed timestamp, as long as speaker is also honest. However, if timestamp is near safe zone limits and delays are high, it may happen that some honest node decides not to follow the speaker... to circumvent these situations, it may be interesting to attach the past block commits during Block proposal, so that every honest node will behave the same, regardless of small delay variations. But this also costs more p2p efforts, we must discuss if this is indeed necessary, or not.

Finally, as long as node agree on the validity of the proposed timestamp, all nodes will adjust their consensus timers in order to fulfill exactly 15 second blocks, thus also solving the first problem. These recessive adjusts have also some "natural" limits, in the same way that "we must never go back in time", so I think it's important to disable this precise timing after a change view occurs (blockchain could have been disabled for a while, so a new "notion of time" will be created, and naturally, block times will vary far away from expected 15 seconds).