Test Definition Format: (Fork Choice Immediate Message Driven GHOST)

[terencechain]

The test format for Casper fork choice rule is up for discussion here
As a team, we should decide if we like the format and come up with a comprehensive design doc. It's also important we study what other client teams are doing for synchrony. (Ex: ethereum/beacon_chain#58)
This issue is associated with #255

More on fork choice rule here: https://ethresear.ch/t/immediate-message-driven-ghost-as-ffg-fork-choice-rule/2561

[prestonvanloon]

What is RPJ?

[prestonvanloon]

So the task is to come up with some language agnostic format for describing tests.

Given the example in the first link:

100V,8E,32S,8M: 0-5*A, 0-5AB, 2-7AC [2]6-7AC, 0-4CD,, [=6] 0-4DE 5-7AB: E**

We understand the the first values are the test configuration:

Param	Value
validators	100
epoch length	8
shard count	32
minimum committee size	8

message Configuration {
   int64 validator_count = 1;
   int64 epoch_length = 2;
   int64 shard_count = 3;
   int64 minimum_committee_size = 4;
}

And then we have a list of validator actions that should occur to test the fork choice.

Slot	Definition	Description
0	0-5*A	Validators 0 through 5 vote on object A, a child of the genesis *.
1	0-5AB	Validators 0 through 5 vote on object B, a child of object A.
2	2-7AC	Validators 2 through 7 vote on object C, a child of object A.
3	[2]6-7AC	Validators 6 through 7 (and validators defined in slot 2) vote on object C, a child of object A.
4	0-4CD	Validators 0 through 4 vote on object D, a child of object C.
5		Emply slot?
6	[=6] 0-4DE 5-7AB	Validators 0 through 4 vote on object E, a child of object D. Validators 5 though 7 vote on object B, a child of object A. [=6] is meant to enforce that this particular definition is at slot 6 explicitly.

Finally, we have the chain head definition. E**. This is where we expect the chain head to be given that the last justified block is genesis and the last finalized block is the genesis.

Open question:

• What is the significance of slot ordering? If these are merely conditions of what to vote on, why does the ordering matter? And why is there possibility for empty slots?
• What is the benefit of referencing other slots rather than having denormalized data declarations? The former adds additional complexity to the test runner.

message ValidationVoteCondition {
  repeated int64 validators = 1;
  string object_id = 2;
}

message Object {
  string id = 1;
  string parent_id = 2;
  bool is_genesis = 3;
}

message ForkChoiceTest {
  Configuration config = 1;
  repeated Object objects = 2;
  repeated ValdiatorVoteCondition vote_conditions = 3;
  string expected_head_object_id = 4;
}

Full ForkChoiceTest definition written out in protobuf text format:

# Test configuration
config {
  validator_count: 100
  epoch_length: 8
  shard_count: 32
  minimum_committee_size: 8
}

# Object definitions
objects {
  id: "*"
  is_genesis: true
}

objects {
  id: "A"
  parent_id: "*"
}

objects {
  id: "B"
  parent_id: "A"
}

objects {
  id: "C"
  parent_id: "A"
}

objects {
  id: "D"
  parent_id: "C"
}

objects {
  id: "E"
  parent_id: "D"
}

# Validator vote condition definitions

# Slot 0 
vote_conditions {
  validators: 0
  validators: 1
  validators: 2
  validators: 3
  validators: 4
  validators: 5
  object_id: "A"
}

# Slot 1 
vote_conditions {
  validators: 0
  validators: 1
  validators: 2
  validators: 3
  validators: 4
  validators: 5
  object_id: "B"
}

# Slot 2
vote_conditions {
  validators: 2
  validators: 3
  validators: 4
  validators: 5
  validators: 6
  validators: 7
  object_id: "B"
}

# Slot 3
vote_conditions {
  validators: 2
  validators: 3
  validators: 4
  validators: 5
  validators: 6
  validators: 7
  validators: 6
  validators: 7
  object_id: "B"
}

# Slot 4 
vote_conditions {
  validators: 0
  validators: 1
  validators: 2
  validators: 3
  validators: 4
  object_id: "D"
}

# Slot 5 is empty so not defined 

# Slot 6 is split into two conditions
# Slot 6, condition 0
vote_conditions {
  validators: 0
  validators: 1
  validators: 2
  validators: 3
  validators: 4
  object_id: "E"
}
# Slot 6, condition 1
vote_conditions {
  validators: 5
  validators: 6
  validators: 7
  object_id: "B"
}

# Final expected head object
expected_head_object_id: "E"

The above could also be represented in JSON format with the same data. I have chosen protobufs due to their type safe nature.

The key advantages here over a parsable text format is that this is already understood by most languages and a parser does not need to be implemented by each language. There might be a scenario where the parser is incorrect and gives false positives to fork choice rule tests.

[terencechain]

This is great. Thanks a lot for the comprehensive thoughts! @prestonvanloon

What is the significance of slot ordering?

I see is slot ordering can be used for certain shorts. For example, [2] means validators defined in slot 2. [=6] means to enforce that this particular definition is at slot 6 explicitly.

Why is there possibility for empty slots?
I think empty slots can happen because validators can go offline, each slot is just a 8 seconds time window.

[prestonvanloon]

A slot is referring to a segment of time? Why?

My other question is why reference another slot rather than denormalize the data? These slot references or concatenations add additional complexity.

I don’t see any time related functionality here. Rather we are establishing the chain state-of-the-universe for the fork choice rule to decide the head.

[nisdas]

@prestonvanloon
Isnt that in the definition of a slot ? A period of 8s. So 6 slots would come out to a period of 48s

Agree on the slot references, they needlessly complicate things and I do not really see the advantage of having them, why not just explicitly state what the data is.

[djrtwo]

Slots are actually important to this construction. The current shuffling of validators (indices_for_heights) provides a different subset of validators for each slot in a cycle so when you say 0-5 in slot 0, it is not necessarily the same as 0-5 in slot 1.

I haven't reviewed your notes in detail yet. On the run currently! Wanted to drop that piece of info in, and I'll come back with more notes later.

[prestonvanloon]

Maybe we could define what a slot actually is and how they are related, if at all, and why are they related?

If slots are related to shuffling, are we assured that the shuffling is deterministic?

[djrtwo]

Because of the epoch-less casper consensus rules, a validator attesting to a block at slot N is a casper vote for the block at slot N and the blocks in the previous CYCLE_LENGTH-1 slots (voting on a total of CYCLE_LENGTH slots). If there are empty blocks for some of these slots that are to be voted on by an attestation, then it is simply skipped. Note, it is not the previous CYCLE_LENGTH blocks that receive votes, but instead slots.

This notion of an attestation casting votes for ancestor blocks is key in assessing both the fork choice and the rules around justification/finalization.

For the purposes of these tests, an RNG for shuffling can be assumed and is thus deterministic. The exact shuffling is unimportant, but rather the notion of only a subset of validators being able to attest at each slot is important. Say there are 100 validators and 10 slots, there are then 10 validators per slot with no overlap. So you would say, build a block B at slot 0 and have validtaors 0-9 attest. If you did the same at slot 1, the validators 0-9 attesting to slot 1 will be entirely different from the validators at slot 0. This again is important when assessing justification/finalization as you count total votes on blocks from individual validators.

I'm open to alternative schemes to write these tests out in, but I am pretty certain we cannot remove the notion of slots (and empty slots for that matter). If we move toward a scheme similar to the one you have proposed, I would toward json.

[djrtwo]

Note: ChiCheng has moved forward with the string parser for now, but we can replace the parser and tests with a different format and still keep the guts the same when we decide on a more favorable format here.

[prestonvanloon]

Link to @ChihChengLiang's PR: ethereum/beacon_chain#80

Why do we need shuffling here if this is testing the fork choice rule?

My interpretation of this test is to build a scenario for the fork choice rule to select the proper head given the information provided to the method.

To answer my earlier question: What is a slot and how are they related? @djrtwo answered offline as follows:

A slot is a period of time in which a certain validator is supposed to propose a block. For every slot there is also a committee that is supposed to attest to a block at that slot. They attest to whatever block appears to be the head of the chain during that slot. These attestations serve as votes for the consensus. See epoch-less casper for more details on that.
Because this is a simulation, the notion of time doesn't really matter, but the duties of validators (who and what they are supposed to do) is still dictated by this sequential notion of slots

I don't understand why we need slots that are applied in a sequential order given that the test is to determine the final head at the end of the scenario.

Given the above scenario of block heirarchy and some vote information. Example:

Vote block	Validator Index	Was Randomly Selected at Epoch/Slot	Expected FC Behavior*
A	0	Yes	Valid vote
A	1	No	Ignore: not selected by RNG
A	99	Yes	Valid vote
B	88	Yes	Ignore: double vote
C	88	Yes	Ignore: double vote

*Note: Expected behavior is just for understanding and is not directly tested in this framework.

Key information for this method are whether or not the the validator was randomly selected during the epoch/slot where they should vote, what was their vote, and what is their index.

[djrtwo]

Why do we need shuffling here if this is testing the fork choice rule?

We don't really need to be shuffling anything, but we do need the concept of only a subset of validators per slot (~len(active_validator_set)/CYCLE_LENGTH). Thus when you say I want 0-9 to attest to slot-1, we are saying the 0-9 assigned to slot-1, not the 0-9 of the total validator set. The specification of this shouldn't allow us to specify validators to attest to a slot that aren't supposed to, and the specification should make it easy to select the validators that are assigned to a certain slot.

The fork choice rule is not simply based on the blocks that are built, but also on the votes the block has received. Votes come from attestations. An attestation of a block at slot N, applies votes to that block and all its ancestors that are in the previous CYCLE_LENGTH slots. This is at minimum a vote for one block and maximum a vote for CYCLE_LENGTH blocks, and could be anywhere in between depending on if any slots were skipped in the chain. It is imperative that we capture this notion of slots and the idea that slots can be skipped in this testing framework.

Happy to hop on a call to explain. I think we might be having something lost in our text communication.

[vbuterin]

The reason I went with a human-writable language is that it really does make life easier for a human to easily be able to crank out a test in 2 minutes without having to fiddle around with tools. I'd personally take JSON over protobuf text format, as most existing ethereum tests are in JSON; I suppose we could get the same gains as we had from the human-writable language by creating a translator? It would not be too difficult, basically the same code that clients would have had to implement to parse the language anyway.

[prestonvanloon]

I agree with JSON. My suggestion for protobuf is to provide the type safety and schema for non-type-safe languages. However, protobuf text format is... not great. It's actually quite bizzare and hard to understand initially. This suggestion might be overkill or an imposition on others.

Back to JSON: I'd imagine that it would be possible to parse the originally proposed language into the JSON and then we only need one implementation of the parser.

I'm interested to hear if any other team has an opinion in tomorrow's call and maybe we can clarify the specific goals of the testing framework.

@djrtwo If you have time, could we schedule a short call to hash out some of my questions?

So the test data need to represent:

• The indices of validators that are assigned during each slot
• The votes cast by a subset of those validators

Is that right? Otherwise, how are we determining which of the 100 validators are assigned to a given slot?

[mratsim]

Following yesterday's call, reposting my comments from the beacon chain repo

Properties

Here are the properties I would find useful:

• Comment support
  • This is important for self documentation, and also quickly disabling/re-enabling tests
  • Note that JSON does not support comment
• Readable
  • This means white-space are insignificant so we can prettify alignment by using whitespaces
• Can be autogenerated
  • This will be helpful to create new test cases
  • Can serve as dump format for logs or crashes for reproduction.
• A clear distinction between input, output and exceptions
  • The exceptions expected should be properly defined as well (i.e. say integer overflow vs array indexing error)

Comments on current proposal

It seems like inspired by CSV for input, with : to separate constants: votes: result, rules should be clear on:

• separator allowed (only , and :)
  if ever needed:
  • quote ' "
  • escaping quotes, comments, line breaks and the escape characters

What is needed?

To clarify what is needed, we should probably make sure of what the lang should encode, I note:

• Validator
• Epoch length
• Shard Count
• Min Committee Size
• numerical range of validator
• uppercase alphabetical range of fork choice. I probably missed it but are there situation with more than 26 choices?
• specifying empty slots
• validators from multiple sets voting for the same fork 2-7AC [2]6-7AC
• asserting the slot you are in [=6]
• Am I missing something?

Canonical test

This vote part for slot 2 and 3 is a bit unclear 0-5AB, 2-7AC [2]6-7AC

• In slot 2, validators 0-5 of the validator set of slot 2 vote on B, a child of A
• In slot 3, validators 2-7 of the validator set of slot 3 vote on C, a child of A, and validators 6-7 from the validator set of slot 2 do the same

So we could use the following as an equivalent right?
6-7AC [3]2-7AC, [2]0-5AB

In summary, human readable/writable format are good but it needs comment (which JSON doesn't support). I do prefer using a widespread format rather than a custom one we would need to write parsers for.

I feel like TOML or YAML can fit all those concerns.

Comparison of TOML and YAML

From https://gist.github.com/oconnor663/9aeb4ed56394cb013a20, with YAML fixed

title = "TOML Example"

[owner]
name = "Tom Preston-Werner"
dob = 1979-05-27T07:32:00-08:00

[database]
server = "192.168.1.1"
ports = [ 8001, 8001, 8002 ]
connection_max = 5000
enabled = true

[servers]

  [servers.alpha]
  ip = "10.0.0.1"
  dc = "eqdc10"

  [servers.beta]
  ip = "10.0.0.2"
  dc = "eqdc10"

[clients]
data = [ ["gamma", "delta"], [1, 2] ]

hosts = [
  "alpha",
  "omega"
]

title: YAML Example

owner:
  name: Tom Preston-Werner
  dob: 1979-05-27T07:32:00-08:00

database:
  server: 192.168.1.1
  ports: [ 8001, 8001, 8002 ]
  connection_max: 5000
  enabled: true

servers:

  alpha:
    ip: 10.0.0.1
    dc: eqdc10

  beta:
    ip: 10.0.0.2
    dc: eqdc10

clients:
  data: [ [gamma, delta], [1, 2] ]

  hosts:
    - alpha
    - omega

And adding this TOML quirk, from strictyaml documentation:

TOML

[[fruit]]
name = "apple"

[fruit.physical]
color = "red"
shape = "round"

vs YAML

fruit:
  name: apple
  physical:
    color: red
    shape: round

(StrictYAML is a type-safe restricted subset of YAML, for example strings must be quoted.)

[rauljordan]

@mratsim YAML is a good compromise. +1.

[ChihChengLiang]

To shed some light on how this test language would be applied, let me paste here the chain test example from the deprecated hybrid Casper.

• Test examples
• Test language implementation, and the meaning of test string token defined at L73-L79.

Note that in the example, the test language is agnostic to the client, database, or server. The tests focus on the chain data and usually test the consistency of the fork choice rule by [S]aving block hash, [R]everting to saved hashes, building a fork, and finally checking the desired [H]ead at the end of the string.

With the test string, it is easy and quick to write a complicate testing scenario in a one-liner.

[prestonvanloon]

My primary issue with the string format is that it is difficult to read or understand.

It seems reasonable to me that we could come up with some mechanism to easily create test scenarios while making it easy to read and understand. This could be writing a string language that can generate the test code in strictYAML or a GUI if someone was so inclined to do so.

[djrtwo]

Agreed on YAML being a good option. @ChihChengLiang We can build and support a simple python tool that converts the string representation into yaml output.

I'll write up a new proposal taking into account @prestonvanloon's and @mratsim's notes/questions.

[djrtwo]

Proposed YAML format: https://notes.ethereum.org/s/r11GVSBuQ

Leave any comments here. We can discuss in depth at our Thursday meeting.