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.

You might also like...
Would upload anything I do with/related to brainfuck

My Brainfu*k Repo Basically wanted to create something with Brainfu*k but realized that with the smol brain I have, I need to see the cell values real

vimBrain is a brainfuck-based vim-inspired esoteric programming language.

vimBrain vimBrain is a brainfuck-based vim-inspired esoteric programming language. vimBrainPy Currently, the only interpreter available is written in

A simple assembly- and brainfuck-inspired stack-based language

asm-stackfuck A simple assembly- and brainfuck-inspired stack-based language. The language has a few goals: Be stack-based Look like assembly Have a s

A brainfuck-based game oriented language written in python.

GF.py STILL WIP Gamefuck.py is a programming language based off brainfuck. It is oriented towards game development, and as such has many commands spec

Implementation of the 😇 Attention layer from the paper, Scaling Local Self-Attention For Parameter Efficient Visual Backbones
Implementation of the 😇 Attention layer from the paper, Scaling Local Self-Attention For Parameter Efficient Visual Backbones

HaloNet - Pytorch Implementation of the Attention layer from the paper, Scaling Local Self-Attention For Parameter Efficient Visual Backbones. This re

A Pythonic introduction to methods for scaling your data science and machine learning work to larger datasets and larger models, using the tools and APIs you know and love from the PyData stack (such as numpy, pandas, and scikit-learn).

This tutorial's purpose is to introduce Pythonistas to methods for scaling their data science and machine learning work to larger datasets and larger models, using the tools and APIs they know and love from the PyData stack (such as numpy, pandas, and scikit-learn).

Image-Scaling Attacks and Defenses
Image-Scaling Attacks and Defenses

Image-Scaling Attacks & Defenses This repository belongs to our publication: Erwin Quiring, David Klein, Daniel Arp, Martin Johns and Konrad Rieck. Ad

A PyTorch implementation of " EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks."

EfficientNet A PyTorch implementation of EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks. [arxiv] [Official TF Repo] Implemen

Official pytorch implementation of
Official pytorch implementation of "Scaling-up Disentanglement for Image Translation", ICCV 2021.

Official pytorch implementation of "Scaling-up Disentanglement for Image Translation", ICCV 2021.

For auto aligning, cropping, and scaling HR and LR images for training image based neural networks

ImgAlign For auto aligning, cropping, and scaling HR and LR images for training image based neural networks Usage Make sure OpenCV is installed, 'pip

Official code for On Path Integration of Grid Cells: Group Representation and Isotropic Scaling (NeurIPS 2021)
Official code for On Path Integration of Grid Cells: Group Representation and Isotropic Scaling (NeurIPS 2021)

On Path Integration of Grid Cells: Group Representation and Isotropic Scaling This repo contains the official implementation for the paper On Path Int

Minesweeper clone with 3 modes of difficulty, UI scaling and custom games feature.

Insect Sweeper Minesweeper clone with 3 modes of difficulty, UI scaling and custom games feature. Mines are replaced with random insects that a player

Implementation of "Scaled-YOLOv4: Scaling Cross Stage Partial Network" using PyTorch framwork.

YOLOv4-large This is the implementation of "Scaled-YOLOv4: Scaling Cross Stage Partial Network" using PyTorch framwork. YOLOv4-CSP YOLOv4-tiny YOLOv4-

Python framework for creating and scaling up production of vector graphics assets.

Board Game Factory Contributors are welcome here! See the end of readme. This is a vector-graphics framework intended for creating and scaling up prod

Unofficial PyTorch reimplementation of the paper Swin Transformer V2: Scaling Up Capacity and Resolution

PyTorch reimplementation of the paper Swin Transformer V2: Scaling Up Capacity and Resolution [arXiv 2021].

[SIGGRAPH'22] StyleGAN-XL: Scaling StyleGAN to Large Diverse Datasets
[SIGGRAPH'22] StyleGAN-XL: Scaling StyleGAN to Large Diverse Datasets

[Project] [PDF] This repository contains code for our SIGGRAPH'22 paper "StyleGAN-XL: Scaling StyleGAN to Large Diverse Datasets" by Axel Sauer, Katja

As-ViT: Auto-scaling Vision Transformers without Training
As-ViT: Auto-scaling Vision Transformers without Training

As-ViT: Auto-scaling Vision Transformers without Training [PDF] Wuyang Chen, Wei Huang, Xianzhi Du, Xiaodan Song, Zhangyang Wang, Denny Zhou In ICLR 2

FastAPI + Django experiment

django-fastapi-example This is an experiment to demonstrate one potential way of running FastAPI with Django. It won't be actively maintained. If you'

Toy example of an applied ML pipeline for me to experiment with MLOps tools.

Toy Machine Learning Pipeline Table of Contents About Getting Started ML task description and evaluation procedure Dataset description Repository stru

Owner
Diederik Loerakker
Platform architect, specialized in Ethereum R&D. Building Eth2. Twitter: @protolambda
Diederik Loerakker
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 8, 2022
Experimental python optimistic rollup fraud-proof generation

Macula Experimental python optimistic rollup fraud-proof generation tech by @protolambda. Working on a python version for brevity and simplicity. See

Diederik Loerakker 30 Sep 1, 2022
OpenZeppelin Contracts written in Cairo for StarkNet, a decentralized ZK Rollup

OpenZeppelin Cairo Contracts A library for secure smart contract development written in Cairo for StarkNet, a decentralized ZK Rollup. ⚠️ WARNING! ⚠️

OpenZeppelin 592 Jan 4, 2023
Test scripts etc. for experimental rollup testing

rollup node experiments Test scripts etc. for experimental rollup testing. untested, work in progress python -m venv venv source venv/bin/activate #

Diederik Loerakker 14 Jan 25, 2022
Simple python code for compile brainfuck program.

py-brainf*ck Just a basic compiled that compiles your brainf*ck codes and gives you informations about memory, used cells, dumped version, logs etc...

null 4 Jun 13, 2021
One line Brainfuck interpreter in Python

One line Brainfuck interpreter in Python

null 16 Dec 21, 2022
A Brainfuck interpreter written in Python.

A Brainfuck interpreter written in Python.

Ethan Evans 1 Dec 5, 2021
Encode and decode cancro lang files to and from brainfuck

cancrolang Encode and decode cancro lang files to and from brainfuck. examples python3 main.py -f hello.cancro --run Hello World! the interpreter is n

witer33 1 Dec 20, 2021
MindF**k it's a programming language as BrainFuck, but with some cool features.

MindF**k Description MindF**k it's a programming language as BrainFuck, but with some cool features. Symbol What does symbol mean > Next slot < Previo

tixcode 0 Jun 15, 2022
An implementation of an interpreter for the Brainfuck esoteric language in Python

Brainfuck Interpreter in Python An implementation of an interpreter for the Brainfuck esoteric language in Python. ?? The Brainfuck Language Created i

Carlos Santos 0 Feb 1, 2022