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
isort is a Python utility / library to sort imports alphabetically, and automatically separated into sections and by type.

isort is a Python utility / library to sort imports alphabetically, and automatically separated into sections and by type. It provides a command line utility, Python library and plugins for various e

Python Code Quality Authority 5.5k Jan 08, 2023
A tool written in python to generate basic repo files from github

A tool written in python to generate basic repo files from github

Riley 7 Dec 02, 2021
A (very dirty) experiment to remove layers from a Docker image.

Surgically remove layers from a Docker image (with a chainsaw)

Jérôme Petazzoni 9 Jun 08, 2022
MongoDB utility to inflate the contents of small collection to a new larger collection

MongoDB Data Inflater ("data-inflater") The data-inflater tool is a MongoDB utility to automate the creation of a new large database collection using

Paul Done 3 Nov 28, 2021
a demo show how to dump lldb info to ida.

用一个demo来聊聊动态trace 这个仓库能做什么? 帮助理解动态trace的思想。仓库内的demo,可操作,可实践。 动态trace核心思想: 动态记录一个函数内每一条指令的执行中产生的信息,并导入IDA,用来弥补IDA等静态分析工具的不足。 反编译看一下 先clone仓库,把hellolldb

25 Nov 28, 2022
Simple python module to get the information regarding battery in python.

Battery Stats A python3 module created for easily reading the current parameters of Battery in realtime. It reads battery stats from /sys/class/power_

Shreyas Ashtamkar 5 Oct 21, 2022
Tool for generating Memory.scan() compatible instruction search patterns

scanpat Tool for generating Frida Memory.scan() compatible instruction search patterns. Powered by r2. Examples $ ./scanpat.py arm.ks:64 'sub sp, sp,

Ole André Vadla Ravnås 13 Sep 19, 2022
ZX Spectrum Utilities: (zx-spectrum-utils)

Here are a few utility programs that can be used with the zx spectrum. The ZX Spectrum is one of the first home computers from the early 1980s.

Graham Oakes 4 Mar 07, 2022
An awesome tool to save articles from RSS feed to Pocket automatically.

RSS2Pocket An awesome tool to save articles from RSS feed to Pocket automatically. About the Project I used to use IFTTT to save articles from RSS fee

Hank Liao 10 Nov 12, 2022
Simple Python tool that generates a pseudo-random password with numbers, letters, and special characters in accordance with password policy best practices.

Simple Python tool that generates a pseudo-random password with numbers, letters, and special characters in accordance with password policy best practices.

Joe Helle 7 Mar 25, 2022
Python program for analyzing the output files of phonopy.

PhononTools Description Python program to analyze the results generated by phonopy. Using the .yaml and .dat files that phonopy generates one can plot

Harry LaBollita 8 Nov 27, 2022
NetConfParser is a tool that helps you analyze the rpcs coming and going from a netconf client to a server

NetConfParser is a tool that helps you analyze the rpcs coming and going from a netconf client to a server

Aero 1 Mar 31, 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
Generate random german words

Generate random german words / Generiere zufällige deutsche Wörter Getting Started Pip install with pip install zufallsworte Install the library with

Maximilian Freitag 5 Mar 24, 2022
🔩 Like builtins, but boltons. 250+ constructs, recipes, and snippets which extend (and rely on nothing but) the Python standard library. Nothing like Michael Bolton.

Boltons boltons should be builtins. Boltons is a set of over 230 BSD-licensed, pure-Python utilities in the same spirit as — and yet conspicuously mis

Mahmoud Hashemi 6k Jan 04, 2023
A workflow management tool for numerical models on the NCI computing systems

Payu Payu is a climate model workflow management tool for supercomputing environments. Payu is currently only configured for use on computing clusters

The Payu Organization 11 Aug 25, 2022
a simple function that randomly generates and applies console text colors

ChangeConsoleTextColour a simple function that randomly generates and applies console text colors This repository corresponds to my Python Functions f

Mariya 6 Sep 20, 2022
Personal Toolbox Package

Jammy (Jam) A personal toolbox by Qsh.zh. Usage setup For core package, run pip install jammy To access functions in bin git clone https://gitlab.com/

5 Sep 16, 2022
Basic loader is a small tool that will help you generating Cloudflare cookies

Basic Loader Cloudflare cookies loader This tool may help some people getting valide cloudflare cookies Installation 🔌 : pip install -r requirements.

IHateTomLrge 8 Mar 30, 2022
Python program for Linux users to change any url to any domain name they want.

URLMask Python program for Linux users to change a URL to ANY domain. A program than can take any url and mask it to any domain name you like. E.g. ne

2 Jun 20, 2022