You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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
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.
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.)
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.
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).
The text was updated successfully, but these errors were encountered:
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.
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
CliqueOracle
class is in effect attempting to simulate an adversary and find a scenario where the estimate of validatorv_b
can be changed through the selective application of some messages known to validatorv_a
.v_a
is aware of some valid messages whichv_b
is not. (I.e., there exists a message in the storage ofv_a
which does not exist in the storage ofv_b
.)CliqueOracle
tests all agreeing validators against all other agreeing validators (2-combination) to see ifv_1
can build an "attack" onv_2
. Then, it finds a clique of validators where they all agree on a estimate and couldn't "attack" each other.v
accepts a messagem
from any single validator,v
processes all messages in the justification ofm
and updates its knowledge of the "latest messages" for all validators. I.e., it is possible for av
to have a "latest message" from a validatorv_x
when there has never been a direct message fromv_x
tov
. (I've been calling this "learning-by-proxy")Conclusion
Let say there are
n
validators and we'll refer to them asv_1 ... v_n
. Lets say thatv_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) wherev_2
"attacks"v_3
without also detecting that same attack fromv_1
(itself). That is to say that the set of "attacks" found byv_1
fromv_2
onv_3
is a subset of the attacks found byv_1
fromv_1
(itself) onv_3
.Therefore, when checking the safety from the perspective of
v_1
it is only necessary to test for attacks betweenv_1
and all other agreeing validators, not the 2-combinations of all agreeing validators (as in assumption 3).The text was updated successfully, but these errors were encountered: