[Spec] How to check whether some data is valid message or valid state efficiently?

[nrryuya]

Should we calculate M∞ Σ∞ ?

From cbc-casper's gitter

Ryuya Nakamura Feb 07 18:20
How (efficiently) check whether some data is valid message or valid state in an actual implementation of CBC Casper client?
There are definitions of M and Σ in the paper so we can check it like data ∈ M and data ∈ Σ but because M and Σ will be quite large set so I guess these are not efficient way.

[nrryuya]

In the Python PoC, justifications are hashed in messages (to reduce the data size?). (@yudetamago confirm?)
However, how to recover the pre-image of it?

[yudetamago]

to reduce the data size?

it might be so.

Actually Python PoC doesn't do any recovering, but only checks that the hashes of messages of justification are included in the hashes of justified messages.
To handle recovering, We need to store all received messages like cbc-casper-js I believe.

[yudetamago]

To be precise, when it comes to message it seems that 3 issues but some of these are overlapping.

1. Justification is a mapping from validator to latest message from the validator.
2. Detecting equivocation messages.
3. Detecting invalid messages.

(WIP)

[nrryuya]

Justification is a mapping from validator to latest message from the validator.

What if the validator is equivocating and has two latest messages?

[yudetamago]

What if the validator is equivocating and has two latest messages?

You mean the justification has two messages from one sender?
If so, the message will be regarded as invalid.

[nrryuya]

You mean the justification has two messages from one sender?

Yes!

If so, the message will be regarded as invalid.

In the theoritical spec, equivocating messages can be included in valid messages.

[nrryuya]

We can implement a client to make it keep its state valid and validate incoming messages.

• start from Σ(0) = ∅
• at a state σ, let k be the minimum integer s.t. σ ∈ Σ(k)
  • the necessary and sufficient condition for a message m to be valid and make state transition is:
    • Justification(m) ⊆ σ (necessary condition for state transition.)
    • This is also sufficient condition if Justification(m) is a valid state
    • Justification(m) is valid i.e. Justification(m) ∈ Σ(k)
      • From Justification(m) ⊆ σ, we don't need to check Σ(i) for i > n
        • This would be proved by the monotonicity of Σ(n)
      • [TODO] Is there any further improvement here?
    • other trivial validity condition
      • Estimate(m) ∈ C (Basically this is block validity)
      • Sender(m) ∈ V (+ verification of signature)
      • Estimate(m) = E(Justification(m)) (verification of fork choice)
• This does not work for a valid message which does not make state transition in σ.
  • In such a case, there exist in-flight messages the message justifies and the client can wait to receive them.
    • This might leads to DoS attack but this would be solved some time-out & resending rule. [Spec] "Pending" messages and DDoS attack #8