[PM] Goal

[minaminao]

Goal

Phase 1

• Summarize
  • Algorithm and data structures to detect finality
  • Algorithm and data structures to update when a message comes in or when a validator is added or deleted
• Compare existing safety oracles
  • Clique Oracle
  • Turán Oracle
  • Adversary Oracle
  • The Inspector
  • Ideal Oracle (Necessary and sufficient oracle)
• Metrics
  • Threshold: (Number of validators required to form the DAG, which decides the fault tolerance for plausible liveness)
  • Time to detection
  • Time complexity
  • Space complexity (Storage, Memory)

Phase 2

• Modified Adversary Oracle
• Simulation

[nrryuya]

Time to detection

If we assume that the network is In full synchrony and there are a sufficient number of honest validators, this basically depends on the number of layers.
Also, now we know that the original adversary oracle is equivalent to clique oracle with "q = n/2 + t".
Therefore, this metric is quite simple.
(Clique oracle:2, adversary oracle:2, Inspector: k)

In small network failure i.e. Δ > 1 slot, clique oracle needs more epochs but it would be future work.

[nrryuya]

Reorganization of our milestone!

Phase1

• 1. Computational complexity
  • Inspector needs to find a maximum q Inspector needs to find a maximum q #14
  • Redefine q with F(σ) Redefine q with F(σ) #17
• 2. More insights
  • Compare completeness Compare completeness #27
    • Is the original adversary oracle equivalent to Inspector (k = 1)? The original adversary oracle is equivalent to Inspector (k = 1)? #13
      • In the first place, the threshold is correct? Is the fault tolerance for the original adversary oracle correct? #5
  • More explicity comparision on fault tolerance
    • Explain "why higher rounds" Explain the rationale of "higher-round" oracles #28
    • Explain Turán Oracle needs more than q Explain Turan oracle requires more than q of validators #24
  • Add conclusion Add conclusion #26
• 3. 3-round finality in CBC Casper
  • Theorem: CBC Casper needs at least 3 rounds to have n/3 fault tolerance Theorem: CBC Casper needs at least 3 rounds to have n/3 fault tolerance #16
  • 3-round clique oracle with observable equivocations for n/3 fault tolerance 3-round Clique oracle with "observable" equivocations #3
    • If it is correct, why >3-round Clique oracle? Why >3 round clique oracle? (not inspector?) #8

Phase2

• 5. Adversary oracle with observable equivocations Adversary oracle with observable equivocations #4
• 6. Liveness optimistic safety oracle Liveness optimistic safety oracle #9

Future work

• Safety oracle for sharding
• Safety oracle for a light client (?)
• What is the best combo of oracles in practice?

Misc

• Further improvements on algorithms for practical use Initial detection of the latest finalized block #6 Update of the latest finalized block #7