Brainfuck rollup scaling experiment for fun

Overview

Optimistic Brainfuck

Ever wanted to run Brainfuck on ethereum? Don't ask, now you can! And at a fraction of the cost, thanks to optimistic rollup tech!

If you can plug in Brainfuck, you can plug in anything. EVM is a work in progress.

State

State:

  • There are 256 brainfuck contract slots
  • Contracts can only be created via a L1 deposit, with a fee (not implemented)
  • Memory cells and pointer are persisted per contract, essentially cheap and easy to navigate storage
  • Regular transactions are input data to the contract specified by the transaction, it's up to the contract to read and process it
  • The l1 sender is always put in the first 20 input bytes, so the contract can trust the user (compare it against its memory)
  • Contract program counter always starts at 0
  • Execution stops as soon as the contract outputs a 0x00 (success, changes are persisted). Higher codes are used as error codes (reverts to pre-state memory and ptr), e.g. stack-overflow, out-of-gas, etc. 0xff is reserved as placeholder during execution.

Gas: a transaction gets 1000 + 128 times the gas based on its payload length, to loop around and do fun things. 1 gas is 1 brainfuck opcode. No gas is returned on exit. These numbers can be tuned.

Running

Quick install in encapsulated environment:

python -m venv venv
source venv/bin/activate
pip install -e .

Get a genesis state:

# create a state with example contract
obf init-state state.json

Output:

+++++++<-]", "ptr": 0, "cells": [ 0 ] } } } ">
{
  "contracts": {
    "0": {
      "code": ",,,,,,,,,,,,,,,,,,,,,[>+++++++<-]",
      "ptr": 0,
      "cells": [
        0
      ]
    }
  }
}

This is a simple contract that skips over the standard sender address data (first 20 bytes), and multiplies the first byte with 7.

# call the default 0 contract with some input data, and a dummy 0xaa.... address
obf transition state.json state_out.json '0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' 0 '0x03'

This produces state_out.json:

+++++++<-]", "cells": [ 0, 21 ], "ptr": 0 } } } ">
{
  "contracts": {
    "0": {
      "code": ",,,,,,,,,,,,,,,,,,,,,[>+++++++<-]",
      "cells": [
        0,
        21
      ],
      "ptr": 0
    }
  }
}

Now say some malicious sequencer committed to a different state of this contract, what happens?

  1. Any honest user sees the mismatch with their local transition
  2. Generate a fraud proof witness
  3. They open a challenge on-chain
  4. They do an interactive game to find the first differing step
  5. They extract the witness for this particular step from the fraud proof data
  6. They submit it, to finish the on-chain work, showing that indeed the sequencer was claiming a different result than could be computed with a tiny step on-chain, on top of the previous undisputed step (base case is just loading the transaction into a step).

Generate a fraud proof:

obf gen state.json proof.json '0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' 0 '0x03'

Output:

[left node, right node] */}, "step_roots": [ /* merkle roots of each step, as well as the final output, to play dispute game on */], "access": [ /* per step, a list of 32-byte encoded generalized indices, to point which nodes are relevant to the step */] } ">
{
   "nodes": { /* key -> [left node, right node] */},
   "step_roots": [ /* merkle roots of each step, as well as the final output, to play dispute game on */],
   "access": [ /* per step, a list of 32-byte encoded generalized indices, to point which nodes are relevant to the step */]
}

Build a witness for a specific step, e.g. step 53:

step-witness proof.json step53.json 53
value nodes }, "pre_root": "0x3ea782a870598661a410b833761ab5483002362cc4ce077ab96bf5e038be394a", "post_root": "0x438d23b78af4c6701d00630bb716c6dfdab5390ce0a5425fe5419f0cd0242184", "step": 53 } ">
{
  "node_by_gindex": {
    "0x0000000000000000000000000000000000000000000000000000000000000008": "0x0000000000000433000000000000000000000000000000000000000000000000",
     "0x0000000000000000000000000000000000000000000000000000000000000009": "0x0000001d00000000000000000000000000000000000000000000000000000000",
    // some more gindex -> value nodes
  },
  "pre_root": "0x3ea782a870598661a410b833761ab5483002362cc4ce077ab96bf5e038be394a",
  "post_root": "0x438d23b78af4c6701d00630bb716c6dfdab5390ce0a5425fe5419f0cd0242184",
  "step": 53
}

And now the last part: format the witness as a call to the L1 executor contract, to finish the game with. This prototype does not have a solidity implementation of the verification (yet? next project maybe), but it does have a python one:

obf verify step53.json "0x438d23b78af4c6701d00630bb716c6dfdab5390ce0a5425fe5419f0cd0242184"
parsing fraud proof
verifying fraud proof
transaction was effective, post contract root: 0x438d23b78af4c6701d00630bb716c6dfdab5390ce0a5425fe5419f0cd0242184
root matches, no fraud

Or with a slightly different root (thus wrong, like a malicious actor might try):

obf verify step53.json "0x438d23b78af4c6701d00630bb716c6dfdab5390ce0a5425fe5419f0cd0242183"
parsing fraud proof
verifying fraud proof
transaction was effective, post contract root: 0x438d23b78af4c6701d00630bb716c6dfdab5390ce0a5425fe5419f0cd0242184
root did not match, fraud detected!

License

MIT, see LICENSE file.

Owner
Diederik Loerakker
Platform architect, specialized in Ethereum R&D. Building Eth2. Twitter: @protolambda
Diederik Loerakker
Know your customer pipeline in apache air flow

KYC_pipline Know your customer pipeline in apache air flow For a successful pipeline run take these steps: Run you Airflow server Admin - connection

saeed 4 Aug 01, 2022
Control-Alt-Delete - Help Tux Escape Beastie's Jail!

Control-Alt-Delete Help Tux escape Beastie's jail by completing the following challenges! Challenges Challenge 00: Drinks: Tux needs to drink less. Ch

NDLUG 8 Oct 31, 2021
Run async workflows using pytest-fixtures-style dependency injection

Run async workflows using pytest-fixtures-style dependency injection

Simon Willison 26 Jun 26, 2022
Find dependent python scripts of a python script in a project directory.

Find dependent python scripts of a python script in a project directory.

2 Dec 05, 2021
produces PCA on genotypes from fasta files (popPhyl's ID format)

popPhyl_PCA Performs PCA of genotypes. Works in two steps. 1. Input file A single fasta file containing different loci, in different populations/speci

camille roux 2 Oct 08, 2021
Utility to extract Fantasy Grounds Unity Line-of-sight and lighting files from a Univeral VTT file exported from Dungeondraft

uvtt2fgu Utility to extract Fantasy Grounds Unity Line-of-sight and lighting files from a Univeral VTT file exported from Dungeondraft This program wo

Andre Kostur 29 Dec 05, 2022
Small project to interact with python, C, HTML, JavaScript, PHP.

Micro Hidroponic Small project to interact with python, C, HTML, JavaScript, PHP. Table of Contents General Info Technologies Used Screenshots Usage P

Filipe Martins 1 Nov 10, 2021
Create a Web Component (a Custom Element) from a python file

wyc Create a Web Component (a Custom Element) from a python file (transpile python code to javascript (es2015)). Features Use python to define your cu

7 Oct 09, 2022
Retrying is an Apache 2.0 licensed general-purpose retrying library, written in Python, to simplify the task of adding retry behavior to just about anything.

Retrying Retrying is an Apache 2.0 licensed general-purpose retrying library, written in Python, to simplify the task of adding retry behavior to just

Ray Holder 1.9k Dec 29, 2022
Various importers for cointracker

cointracker_importers Various importers for cointracker To convert nexo .csv format to cointracker .csv format: Download nexo csv file. run python Nex

Stefanos Anastasiou 9 Oct 24, 2022
Modeling Category-Selective Cortical Regions with Topographic Variational Autoencoders

Modeling Category-Selective Cortical Regions with Topographic Variational Autoencoders Getting Started Install requirements with Anaconda: conda env c

T. Andy Keller 4 Aug 22, 2022
A functional standard library for Python.

Toolz A set of utility functions for iterators, functions, and dictionaries. See the PyToolz documentation at https://toolz.readthedocs.io LICENSE New

4.1k Dec 30, 2022
Give you a better view of your Docker registry disk usage.

registry-du Give you a better view of your Docker registry disk usage. This small tool will analysis your Docker registry(vanilla or Harbor both work)

Nova Kwok 16 Jan 07, 2023
Python code to generate and store certificates automatically , using names from a csv file

WOC-certificate-generator Python code to generate and store certificates automatically , using names from a csv file IMPORTANT In order to make the co

Google Developer Student Club - IIIT Kalyani 10 May 26, 2022
Daiho Tool is a Script Gathering for Windows/Linux systems written in Python.

Daiho is a Script Developed with Python3. It gathers a total of 22 Discord tools (including a RAT, a Raid Tool, a Nuker Tool, a Token Grabberr, etc). It has a pleasant and intuitive interface to faci

AstraaDev 32 Jan 05, 2023
Helper script to bootstrap a Python environment with the tools required to build and install packages.

python-bootstrap Helper script to bootstrap a Python environment with the tools required to build and install packages. Usage $ python -m bootstrap.bu

Filipe Laíns 7 Oct 06, 2022
A string extractor module for python

A string extractor module for python

Fayas Noushad 4 Jul 19, 2022
Exports the local variables into a global dictionary for later debugging.

PyExfiltrator Julia’s @exfiltrate for Python; Exports the local variables into a global dictionary for later debugging. Installation pip install pyexf

6 Nov 07, 2022
✨ Un générateur de lien raccourcis en fonction d'un lien totalement fait en Python par moi, et en français.

Shorter Link ❗ Un générateur de lien raccourcis en fonction d'un lien totalement fait en Python par moi, et en français. Dépendences : pip install pys

MrGabin 3 Jun 06, 2021
A set of Python scripts to surpass human limits in accomplishing simple tasks.

Human benchmark fooler Summary A set of Python scripts with Selenium designed to surpass human limits in accomplishing simple tasks available on https

Bohdan Dudchenko 3 Feb 10, 2022