Adversarial program generator for gas model validation

Tutors: Ilias Garnier, Lucas Randazzo, Yann Régis-Gianas

Subject

Tezos is a self-amendable distributed ledger. It includes a virtual machine for Michelson, a strongly typed stack-based language used to program smart contracts. Since Tezos is an open platform, proper sharing of computational resources between users must be ensured. This is done by instrumenting the virtual machine to account for resource utilization using a cost indicator called "gas" and setting per-transaction limits to gas consumption.

Gas costs for type-checking and program execution are obtained by constructing and fitting statistical models. It is crucial for the security of the chain that these models be predictive over the set of programs allowed on chain.

Goals

The goal of this internship is to investigate adversarial Michelson program generation, i.e. generation of Michelson terms for which the statistical model predicting computational resource consumption is wrong. You will perform a state of the art on the subject of program generation and implement a system able to search for such programs.

Requirements

We expect you to be proficient in at least one statically typed functional language and have a strong interest in machine learning or more generally, computational statistics. An interest in technologies related to blockchains is welcome.

Bibliography

The following article is not related to adversarial program generation but gives a good overview on the techniques that could be involved in this internship.

Learning to Infer Program Sketches (Nye, Hewitt, Tenenbaum, Solar-Lezama)1

Internship Context

You will work at the Nomadic Labs' offices in Paris or Grenoble.

Participating in a large scale open-source project you will have to rapidly learn to use collaborative tools (Git, merge request, issues, gitlab, continuous integration, documentation) and to communicate about your work. The final results might be presented at an international conference or workshop.

You will have a designated advisor at Nomadic Labs and will have to work independently and to propose thoroughly-considered solutions to the different problems you will have to solve. You will be encouraged to seek advice from members of the team.

Intellectual Property

All material produced (essays, documentation, code, etc.) will be released under an open source license (e.g. MIT or CC).