ethereum/cbc-casper

cbc-casper's Issues

update make commands

Issue

Default commands don't give as much flexibility as they should (we want nice commands to run all types of protocols in all types of situations!)

Proposed Implementation

Extend commands in make file to be more diverse and cover more interesting situations.

Assess finality gadget use of ethereum network data in simulations

Issue

Supposedly somewhere in pyethereum/finality gadget repo are some network simulations that use real ethereum network data. We are discussing adding some complexity to the simulations and want to see if this stuff in the ethereum repo could be of use.

Proposed Implementation

• Reach out to @karlfloersch to see where this stuff is
• Discuss relevance here.

Problem following install instructions

Issue

• What's wrong?
  I tried to follow the install instructions

• How are things currently?
  Installing the following causes the install process to fail:

line-profiler==2.0
scandir==1.6

(I removed line-profiler, then it crashed on scandir, then i removed it and the install process completed)

I'm running Ubuntu 16.04 and I have an i7.

Migrate to d3 visualizations

Issue

• matplotlib visualizations from the command line aren't super sweet
• d3 visualizations + a web interface for running & rerunning simulations are super sweet

@karlfloersch implemented this in March in PR 1, but it has serious merge conflicts.

Proposed implementation

Use PR 1 as a reference for implementing d3 + web interface in the current repo.

Hold off on implementation until blockchain branch is merged into master

Make CI work again

Issue

Migration from Karl's repo to Vlad's broke CI, which no longer runs any tests.

Proposed Implementation

Fix circleci so it works on Vlad's repo, and we can have CI again.

Collect Relevant Statistics

We should begin to compile relevant statistics + visualizations for papers and a blog post.

Relevant statistics:

1. Time to finality (rounds) + overhead vs. orphan rate (and how this changes with the number of validators).
2. As a simpler version of the above, the number of finalized messages per some number of blocks generated (depending on strategies?)

Relevant Visualizations:

1. GIFs of each preset mode of operation

Two subsets of validator set may have same weight

In some cases, two subsets of validators will be initialized with the same weight. Because of how validator weight is chosen currently, this is often just two validators who are initialized with a weight of 20.000...001.

As a result of this, two blocks in the fork choice may have the same weight. Currently, this is dealt with by taking a random choice between the two blocks. However, this means that two validators with the same view could potentially make the different estimates, which means this simulation does not satisfy the safety proof.

Furthermore, this may cause further complications in the future if validators are ever made to equivocate or create invalid messages in the simulation, as validators may identify certain messages as invalid when they are not.

Proposed Fix:

1. When starting the simulation and creating random weights for the validators, add some small (< 1), pseudo-random number to their weights. This makes it unlikely two sets of validators will have the same weight.
2. Remove the line in the fork choice that randomly selects from the children w/ max weight if there is more than one. Instead, add a sanity check that makes sure there is a single child block of max weight, as there should no longer be ties.

write unit tests for TestLangCBC methods

Issue

A lot of our tests rely on TestLangCBC, but TestLangCBC is not tested.

Proposed Implementation

• Create a new test file -- tests/test_test_lang.py
• Write unit tests for initialization and methods

Remove decide_if_safe call from make_latest_bet

Total time: 349.029 s
File: validator.py
Function: make_new_latest_bet at line 98

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    98                                               @profile
    99                                               def make_new_latest_bet(self):
   100                                           
   101       674         1132      1.7      0.0          if len(self.view.bets) == 0 and self.my_latest_bet is None:
   102        75          504      6.7      0.0              self.latest_estimate = r.choice(tuple(ESTIMATE_SPACE))
   103        75         2375     31.7      0.0              self.my_latest_bet = self.make_bet_with_null_justification(self.latest_estimate)
   104        75          514      6.9      0.0              self.view.add_bet(self.my_latest_bet)
   105                                           
   106        75       300043   4000.6      0.1              self.decide_if_safe()
   107        75           95      1.3      0.0              return self.my_latest_bet
   108                                           
   109       599          529      0.9      0.0          if self.my_latest_bet is None:
   110                                                       already_committed_view = View(set())
   111                                                   else:
   112       599      1444239   2411.1      0.4              already_committed_view = View(View(self.my_latest_bet.justification).get_extension())
   113                                           
   114       599        92771    154.9      0.0          estimate = self.get_latest_estimate()
   115       599          506      0.8      0.0          justification = set()
   116     45524        21981      0.5      0.0          for v in VALIDATOR_NAMES:
   117     44925        23207      0.5      0.0              if v in self.latest_observed_bets:
   118     26530        71297      2.7      0.0                  justification.add(self.latest_observed_bets[v])
   119                                           
   120       599          477      0.8      0.0          to_be_removed = set()
   121     27129        14003      0.5      0.0          for j in justification:
   122     26530        66877      2.5      0.0              if j in already_committed_view.bets:
   123     14622        36672      2.5      0.0                  to_be_removed.add(j)
   124                                           
   125       599         1993      3.3      0.0          justification.difference_update(to_be_removed)
   126                                           
   127       599          372      0.6      0.0          sender = self.name
   128                                           
   129       599        71024    118.6      0.0          self.my_latest_bet = Bet(estimate, justification, sender)
   130       599    201274877 336018.2     57.7          self.my_latest_bet.make_redundancy_free()
   131                                           
   132       599          845      1.4      0.0          self.latest_estimate = estimate
   133       599         6544     10.9      0.0          self.view.add_bet(self.my_latest_bet)
   134       599          608      1.0      0.0          self.latest_observed_bets[self.name] = self.my_latest_bet
   135                                           
   136       599    145594828 243063.2     41.7          self.decide_if_safe()
   137       598          825      1.4      0.0          return self.my_latest_bet

remove kernprof from makefile

Issue

We use kernprof to run casper.py by default in the Makefile. Why?
This seems like it should be used just if/when we need to profile something rather than the default command to run simulations.

Suggested Implementation

• Remove kernprof from default commands in Makefile
• Add make target that does kernprof for if/when needed

enable blockchain and binary consensus to live in same branch

Issue

Blockchain and Binary consensus live in separate branches and are currently in conflict with each other. Goal is to make underlying components modular enough so different consensus protocols can use the same underlying structure/tools.

Proposed Implementation

add special validator number to check the global forkchoice

https://github.com/karlfloersch/cbc-casper/blob/071655de04e9ee1bc4393a7d853a683de4b6f44d/casper/testing_language.py#L126

add flake8 to CI and cleanup lint

Issue

pylint is currently in our makefile but is not a part of CI. I would like like linting to ultimately be a part of tests passing/failing.

Proposed implementation

• add flake8 to CI
• cleanup repo to pep8 standards so CI passes

Propagate sampled viewables rather than just latest messages

Issue:

Currently, the simulation gives us "unrealistic liveness" as the most recent messages from each validator in the global view are the only messages that propagate (this combined w/ justifications containing the messages is a very unrealistic combination).

We should send messages more realistically, by sampling from messages that a validator has not seen.

Implementation:

When sending a message from validator V1 to validator V2, sample randomly from the messages V1 has created that V2 has seen, rather than just sending the latest message.

Message generation does not have to change, but there can be a step where these pairs of validators sample some int between sequence number of current message and sequence of last seen message, then choose the message with this sequence number to send.

Move test_string out of test_lang creation to parsing.

Issue

It's currently impossible to assert things about intermediate state in the testing language. For example, I might want to assert something about the state of some validator halfway through the testing code (something that the testing language cannot feasibly support [e.g. that their oracle manager has X blocks being tracked currently]).

The workaround currently is having two tests - one that tests the intermediate state, and then one that tests the final state later. However, this imposes an unnecessary amount of overhead - and it would be better if we can parse the testing language in pieces.

Proposed Implementation

Pass in the testing string to the parser with the call to the parsing function instead of passing it in on creation. Can continually pass in more strings to the testing language which are then parsed.

Run tests against multiple oracles.

Issue

Tests are only run with CliqueOracle in TestLang and Validator. All relevant tests should run against CliqueOracle and AdversaryOracle.

Proposed Implementation

• Make oracle used by Validator and TestLang configurable
• Run tests requiring oracles against a list of Oracles.

Note: TestLang only uses the oracle for --report option.

More casper.py command line options

Issue

Casper.py takes in a few command line options, but there are a few more like specifying weights that could be useful.

Proposed Implementation

• Add --weights option to specify validator weights (overrides default random generation)
• Add params to override generate_random_validator_set params

Add support for python3

Issue

A lot of the python community is defacto using python3 these days especially in crypto projects due to the support for bytes type (note: bytes in python2 is just a wrapper for string. aka a nightmare). I don't think it would take too much to add python3 support. I imagine the biggest change is likely to calls to print

Proposed implementation

• convert prints
• convert class styles where necessary
• ensure simulations run on py3
• ensure tests pass on py3

Validator memorizes values about previous calls to oracle

Issue

Right now, the validator reinitializes a new Oracle when checking estimate safety regardless of any previous checks to estimate safety and any intermittent results/calculations. This is a huge source of inefficiencies.

Proposed implementation

• Validator keeps Oracle data around (as long as needed).
• Validator updates Oracle data upon receiving new message
  • Oracles should all implement a method update_estimate_cache (not sure about name) that is called upon receiving a new message. Cache would be dependent on Oracle type.
  • Implementation decision:
    • Validator can either keep a dict of Oracles (one per candidate estimate) -- updating each upon new messages, and removing particular Oracles as candiate_estimates become non-relevant
    • OR Validator only has one Oracle and the Oracle is responsible for organizing info per candidate estimate.

Copy of `justification` required for `bet.py` not understood

For some reason we need to copy the justification of bets when initializing them. When we don't, we get a recursive depth error. We should investigate why this is the case.

Add test_string output for experiments

Issue

There is no way to re-run experimental results or to analyze/visualize what actually happened each run.

Proposed Implementation

• For each simulation run in the experiment, output a corresponding weights dictionary and test_string so it can be re-run/visualized with test_lang
• use and output a seed for rand so the exact experiment can be re-run
• seed rand with "seed" if provided in an experiment.

Organize source files into sub directory

Issue

Source files are in root directory. Currently living with install files, config files, etc.

Proposed Implementation

• create subdirectory. maybe called casper or cbc-casper
• move .py files into casper
• ensure simulations and tests still run correctly

Rework casper.py

Issue

casper.py works... but is a single function that is hard to read and hard to change/extend.

Proposed Implementation

Build a more generic simulation runner. More details to follow

Make Oracles Descend From Common Ancestor

Create ValidatorSet class

Issue

We should consider moving the validator set initialization and variables out of settings.py and have it be its own class ValidatorSet.

Will be useful to have it as its own logical unit for when (if) we start simulating changes to the validator set. Will also be useful to be able to test different configurations of validators more easily (number of validators, distribution of weights, etc).

Proposed implementation

• Create class ValidatorSet
• Move variables related to the validator set (ex: NUM_VALIDATORS, VALIDATOR_NAMES, etc) to ValidatorSet. These can be configured on __init__.
• ValidatorSet can have list (set?) of Validators.
• Move specific validator weights and names to each Validator.
• Refactor references to validators and settings vars to reference the validator_set on network.
• Adversary can attack by manipulating a copy of the current network ValidatorSet. I think this will allow us to remove or at least simplify ModelValidator and related models

Expand upon Experiment and Analyzer tests

Issue

They are lacking.

Proposed Implementation

Build them out.
Need a standard way to seed/create a run Simulation (from a test_string!) to easily test Analyzer.

prettify the graphs

label axes, give title, etc. Not clear what I'm looking at

document/explain weights

Make casper.py data structure agnostic

Issue

Currently, casper.py must change depending on the data structures on which consensus is being formed. This makes it harder for binary + blockchain + possible re-write proof stuff to live in the same branch as it will lead to a fair bit of code duplication.

This is one of the considerations for issue #26

Implementation

Change casper.py to be data structure agnostic by having Casper deal mostly with message propagation and generation. Then, the resulting view (and validator set?), as well as the most recent messages propagated, can be passed into some plot tool, which can display them in the regular view graph.

Without this refactor, the plot tool will have to change in any case - but this reduces the amount of code that has to change and/or duplicated for multiple data structures to exist together (and this likely makes it easier to change).

Refactor test lang to be data structure agnostic

Issue

Currently, the testing language is both written for and only suited to testing the CBC-Casper w/ blockchain data structures. This will become an issue when we want to test the binary, rewrite proof, and more!

Proposed Implementation

Refactor the testing language to be data structure agnostic. A lot of this is name changes rather than functionality changes (e.g. make_block -> make_message).

The main complication here is testing estimates becomes more complicated (in some cases, we want to just pass in a 1 (binary), while in others we want to pass in a block name, or whatever the rewrite proof would be). To resolve this, we can likely store both messages and estimates (in the case of binary, msg.value, in the case of blockchain, msg.prev_block).

Possible the best implementation of this is some common abstract class (in Java - not sure what the equivalent is in python), and then implementing the remaining functions.

Going to think about this a bit more in the coming days. Will also take some shots at it and post issues I run into here.

Testing language uses blockchain plot tool.

Issue

Testing language reuses code that exists in the plot tool, which is unnecessary.

Proposed Implementation

Move the test_lang to use the blockchain plot tool (or some plot tool), depending on the data structures. This will require a call to the "update" function after each sent message.

Write some sample experiments using SimulationRunner

details coming

Binary cleanup

Issue

The binary branch has fallen behind - and currently does not take advantage of the cleanup + abstractions + efficiency improvements of the blockchain branch.

Implementation

Total rewrite of the binary protocol to take advantage of the abstractions, etc currently in the master (previously blockchain) branch. With the goal of it living side by side other protocols in master.

This likely requires #52 and is part of the bigger story here: #26

Validator weights do not display correctly

Another very minor bug.

This may be a machine specific issue, but when running Casper, the weights of the validators do not show up on the bottom of the graph until ~4 rounds in or so. They then appear to move farther and farther up the graph before stopping somewhere in the middle of the first blocks from the validators.

Example:

add Makefile

suggested:

• make install
• make test
• make run_rounds
• make run_blockchain

Fork choice invisible in some (very rare) conditions

Very minor bug and/or just a note. Essentially, if the fork choice is one of the starting blocks, and no further blocks are built on top of it, it can appear like the fork choice is non-existent, as the fork choice is displayed as highlights on prev block pointers (and there are no prev block pointers to highlight). This can be somewhat confusing.

Might just be worth noting this behavior, but otherwise, a simple fix would be highlighting the blocks that are in the fork choice.

Example:

Migrate tests to pytest

Issue

• Currently, we use unittest as our unit testing framework, which is limiting in terms of using command line arguments w/ tests.
• lengthy self.assertEquals statements are lengthy :)

Proposed implementation

Move to pytest as our unit testing framework. Should be a simple enough refactor - but will allow for better command line arguments and cleaner tests.

Subtasks...

• add command line arg to enable plotting test graphs

Transfer repo ownership to Vlad

Issue

Need to Transfer repo ownership to @vladzamfir

Proposed Implementation

yooooo @karlfloersch, can you handle this this morning?
please and thanks

Make Genesis Message (Block)

Issue

No notion of initial state/genesis block. This will be required when we start working on validator rotation.

Proposed Implementation

• Add validator_set to message
• Validators are passed an initial_message or genesis
• ValidatorSet becomes part of the message
  • For static, it just stays constant across all messages in the protocol
  • For validator set rotation, it can change via the message (under some rules).
• unsure how this ripples through the codebase. specifically how the oracles handle the validator_sets from messages.

I realized that I started scoping validator set rotation as part of this, but that's not really in the title.

We can break this into a Genesis Message issue and a ValidatorSet rotiaton issue if that makes more sense

document/explain the options used when running kernprof

(rand | rrob | full | nofinal)

Adversary Oracle testing bug

Issue

One test_lang safety test fails for AdversaryOracle, but passes for CliqueOracle. It was my understanding that these oracles were supposed to perform exactly the same.

Proposed Implementation

Fix test. Might as well hammer out #53 while we're at it.

bets included in justification, instead of hash-linking

I think fixing this will involve some healthy refactoring in validator.py.

the validator will need to keep bets for that they don't have dependencies (that satisfy the hash link/commitment) in "limbo". It separates receive_bet from 'add_bet_to_view' (name bad, tentative) which makes it possible to use a bet in safety calculation.

It also would mean that the size of bets on the network won't the size of its entire dependency - this will play into our network.py/casper.py refactoring

circle CI integration

related to #21 and #23

Remove default to blockchain

Issue

System currently defaults to "blockchain" protocol where ever possible. This shouldn't be the case.

Proposed Implementation

• move protocol specific tests into tests/casper/*protocol_name*
• refactor testing to be generic where possible, and to test specific protocols where doing so
• Maybe provide minimum implementations of most methods on the abstract classes (message and view) so that generic tests can pass
• make testlang protocol agnostic
• pass in protocol as a param to casper.py
• require specify protocol in experiment .json file
• Will have to make a specific analyzer to each protocol. i.e. BlockchainAnalyzer

Blockchain not realizing that it is safe

on commit 1446772

see:

adversary oracle, can we do a free block check?

https://github.com/karlfloersch/cbc-casper/blob/d97e0073e6fa3ea88dda33eb63c320253356ee68/casper/safety_oracles/adversary_oracle.py#L49

One off bet bug

A validator when calculating safety doesn't include their own latest bet

Add license in root directory

Looks like MIT is the most permissive and likely what we want here.
Check out https://choosealicense.com/ for info.

Ultimately I will defer to @vladzamfir, but we should definitely integrate a LICENSE file before we open up the repo

apply pylint and add to CI

Add user defined errors for easier testing

Issue

Currently, if we want to test that some condition is false (e.g. that some block is not the forkchoice), we can construct a string that asserts it is true, and then test that running the testing language with this string fails an assertion. However, we cannot be sure which assert is really causing the error to fail.

See discussion #19 for more details.

Implementation

Add necessary user-defined errors (like ForkChoiceError) that allow us to check the correct part of the test is failing.