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
MITRE ATT&CK Lookup Tool

MITRE ATT&CK Lookup Tool attack-lookup is a tool that lets you easily check what Tactic, Technique, or Sub-technique ID maps to what name, and vice ve

Curated Intel 33 Nov 22, 2022
Python humanize functions

humanize This modest package contains various common humanization utilities, like turning a number into a fuzzy human-readable duration ("3 minutes ag

Jason Moiron 1.6k Jan 01, 2023
Python Yeelight YLKG07YL/YLKG08YL dimmer handler

With this class you can receive, decrypt and handle Yeelight YLKG07YL/YLKG08YL dimmer bluetooth notifications in your python code.

12 Dec 26, 2022
A Python script that parses and checks public proxies. Multithreading is supported.

A Python script that parses and checks public proxies. Multithreading is supported.

LevPrav 7 Nov 25, 2022
Group imports from Windows binaries

importsort This is a tool that I use to group imports from Windows binaries. Sometimes, you have a gigantic folder full of executables, and you want t

【☆ ゆう ☆ 】 15 Aug 27, 2022
This tool analyzes the json files generated by stream-lnd-htlcs to find hidden channel demand.

analyze_lnd_htlc Introduction Rebalancing channels is an important part of running a Lightning Network node. While it would be great if all channels c

Marimox 4 Dec 08, 2022
Networkx with neo4j back-end

Dump networkx graph into nodes/relations TSV from neo4jnx.tsv import graph_to_tsv g = pklload('indranet_dir_graph.pkl') graph_to_tsv(g, 'docker/nodes.

Benjamin M. Gyori 1 Oct 27, 2021
ColorController is a Pythonic interface for managing colors by english-language name and various color values.

ColorController.py Table of Contents Encode color data in various formats. 1.1: Create a ColorController object using a familiar, english-language col

Tal Zaken 2 Feb 12, 2022
a tool for annotating table

table_annotate_tool a tool for annotating table motivated by wiki2bio,we create a tool to annoate all types of tables,this tool can annotate a table w

wisdom under lemon trees 4 Sep 23, 2021
A collection of custom scripts for working with Quake assets.

Custom Quake Tools A collection of custom scripts for working with Quake assets. Features Script to list all BSP files in a Quake mod

Jason Brownlee 3 Jul 05, 2022
Backman is a random/fixed background image setter for wlroots based compositors

backman Backman is a random/fixed background image setter for wlroots based compositors Dependencies: The program depends on swaybg, python3-toml (or

Hemish 3 Mar 09, 2022
Greenery - tools for parsing and manipulating regular expressions

Greenery - tools for parsing and manipulating regular expressions

qntm 242 Dec 15, 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
A script copies movie and TV files to your GD drive, or create Hard Link in a seperate dir, in Emby-happy struct.

torcp A script copies movie and TV files to your GD drive, or create Hard Link in a seperate dir, in Emby-happy struct. Usage: python3 torcp.py -h Exa

ccf2012 105 Dec 22, 2022
HeadHunter parser

HHparser Description Program for finding work at HeadHunter service Features Find job Parse vacancies Dependencies python pip geckodriver firefox Inst

memphisboy 1 Oct 30, 2021
Local backup made easy, with Python and shutil

KTBackup BETA Local backup made easy, with Python and shutil Features One-command backup and restore Minimalistic (only using stdlib) Convenient direc

kelptaken 1 Dec 27, 2021
Entropy-controlled contexts in Python

Python module ordered ordered module is the opposite to random - it maintains order in the program. import random x = 5 def increase(): global x

HyperC 36 Nov 03, 2022
RapidFuzz is a fast string matching library for Python and C++

RapidFuzz is a fast string matching library for Python and C++, which is using the string similarity calculations from FuzzyWuzzy

Max Bachmann 1.7k Jan 04, 2023
A simple and easy to use Spam Bot made in Python!

This is a simple spam bot made in python. You can use to to spam anyone with anything on any platform.

7 Sep 08, 2022
A utility that makes it easy to work with Python projects containing lots of packages, of which you only want to develop some.

Mixed development source packages on top of stable constraints using pip mxdev [mɪks dɛv] is a utility that makes it easy to work with Python projects

BlueDynamics Alliance 6 Jun 08, 2022