search

ethereum / cbc-casper

GNU Affero General Public License v3.0
229 stars 44 forks source link

CliqueOracle optimisation? #178

Closed paulhauner closed 6 years ago

paulhauner commented 6 years ago

I have been implementing a safety oracle in JS with reference to CliqueOracle here. I suspect the method I am intending to use is an optimisation on the method used here. To assert this, I'll start with some assumptions and then come to a conclusion. I'd love to hear your feedback and find where I may have gone wrong.

Assumptions

  1. The CliqueOracle class is in effect attempting to simulate an adversary and find a scenario where the estimate of validator v_b can be changed through the selective application of some messages known to validator v_a.
  2. To find an "attack" scenario (as in 1), it is necessary that v_a is aware of some valid messages which v_b is not. (I.e., there exists a message in the storage of v_a which does not exist in the storage of v_b.)
  3. The current implementation of CliqueOracle tests all agreeing validators against all other agreeing validators (2-combination) to see if v_1 can build an "attack" on v_2. Then, it finds a clique of validators where they all agree on a estimate and couldn't "attack" each other.
  4. When a validator v accepts a message m from any single validator, v processes all messages in the justification of m and updates its knowledge of the "latest messages" for all validators. I.e., it is possible for a v to have a "latest message" from a validator v_x when there has never been a direct message from v_x to v. (I've been calling this "learning-by-proxy")

Conclusion

Let say there are n validators and we'll refer to them as v_1 ... v_n. Lets say that v_1 wants to check the safety of its current estimate.

Because of assumption 4, v_1 could not find a scenario (using its own storage) where v_2 "attacks" v_3 without also detecting that same attack from v_1 (itself). That is to say that the set of "attacks" found by v_1 from v_2 on v_3 is a subset of the attacks found by v_1 from v_1 (itself) on v_3.

Therefore, when checking the safety from the perspective of v_1 it is only necessary to test for attacks between v_1 and all other agreeing validators, not the 2-combinations of all agreeing validators (as in assumption 3).

paulhauner commented 6 years ago

Oh I figured this out. The continue on line 32 covers this case.

You might still be able to get some speed increases by not iterating over validators which are not aware of each other, but the increase wouldn't be as large as I initially thought.