Liveness optimistic safety oracle

[nrryuya]

There seem to be various techniques like Turan oracle which detects t-finality in lucky cases, sometimes requiring more (than the corresponding q of) validators and denser message DAG.

This compromises fault tolerance for liveness and requires stronger synchrony assumption but might be good in practice about computational complexity (compared to clique oracle) or time to detection (compared to k-level inspector).

(If an algorithm to find that a lower bound of a clique is >q need >q + α of validators, the fault tolerance for plausible liveness is reduced proportionally to α)

Ideas:

• One of such ideas is Turan oracle with pre-processing.
  • E.g. First, remove all the validators who are not connected to more than q of validators (This needs O(n^2)) and if there remained more than q validators then apply the Turan theorem
• Turan oracle for 3-rounds clique oracle with observable equivocations 3-round Clique oracle with "observable" equivocations #3