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
Dynamic key remapper for Wayland Window System, especially for Sway

wayremap Dynamic keyboard remapper for Wayland. It works on both X Window Manager and Wayland, but focused on Wayland as it intercepts evdev input and

Kay Gosho 50 Nov 29, 2022
python-codicefiscale: a tiny library for encode/decode Italian fiscal code - codifica/decodifica del Codice Fiscale.

python-codicefiscale python-codicefiscale is a tiny library for encode/decode Italian fiscal code - codifica/decodifica del Codice Fiscale. Features T

Fabio Caccamo 53 Dec 14, 2022
Library for processing molecules and reactions in python way

Chython [ˈkʌɪθ(ə)n] Library for processing molecules and reactions in python way. Features: Read/write/convert formats: MDL .RDF (.RXN) and .SDF (.MOL

16 Dec 01, 2022
A Python script that transcript Arcaea chart file (.aff file) into AutoJS touchscreen script which automatically plays the Arcaea chart

ArcaeaAutoplay (AutoJS Version) A Python script that transcript Arcaea chart file (.aff file) into AutoJS touchscreen script which automatically plays

7 Dec 03, 2021
Here, I find the Fibonacci Series using python

Fibonacci-Series-using-python Here, I find the Fibonacci Series using python Requirements No Special Requirements Contribution I have strong belief on

Sachin Vinayak Dabhade 4 Sep 24, 2021
Automatic generator of readmes for git repositories (Includes file' listing)

Readme Generator We are bored of write the same things once and once again. We trust in the comments made inside of our files, and we decided to autom

Natalia Vera Duran 6 Jul 20, 2021
Delete all of your forked repositories on Github

Fork Purger Delete all of your forked repositories on Github Installation Install using pip: pip install fork-purger Exploration Under construc

Redowan Delowar 29 Dec 17, 2022
Audio Steganography is a technique used to transmit hidden information by modifying an audio signal in an imperceptible manner.

Audio Steganography Audio Steganography is a technique used to transmit hidden information by modifying an audio signal in an imperceptible manner. Ab

Karan Yuvraj Singh 1 Oct 17, 2021
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
Nmap script to guess* a GitLab version.

gitlab-version-nse Nmap script to guess* a GitLab version. Usage https://github.com/righel/gitlab-version-nse cd gitlab-version-nse nmap target --s

Luciano Righetti 120 Dec 05, 2022
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
Small Python script to parse endlessh's output and print some neat statistics

endlessh_parser endlessh_parser is a small Python script that parses endlessh's output and prints some neat statistics about it Usage Install all the

ManicRobot 1 Oct 18, 2021
A small python tool to get relevant values from SRI invoices

SriInvoiceProcessing A small python tool to get relevant values from SRI invoices Some useful info to run the tool Login into your SRI account and ret

Wladymir Brborich 2 Jan 07, 2022
Airspy-Utils is a small software collection to help with firmware related operations on Airspy HF+ devices.

Airspy-Utils Airspy-Utils is a small software collection to help with firmware related operations on Airspy HF+ devices on Linux (and other free syste

Dhiru Kholia 11 Oct 04, 2022
✨ Un générateur de mot de passe aléatoire totalement fait en Python par moi, et en français.

Password Generator ❗ Un générateur de mot de passe aléatoire totalement fait en Python par moi, et en français. 🔮 Grâce a une au module random et str

MrGabin 3 Jul 29, 2021
Simple profile athena generator for Fortnite Private Servers.

Profile-Athena-Generator A simple profile athena generator for Fortnite Private Servers. This profile athena generrator features: Item variants Get al

Fevers 10 Aug 27, 2022
Astvuln is a simple AST scanner which recursively scans a directory, parses each file as AST and runs specified method.

Astvuln Astvuln is a simple AST scanner which recursively scans a directory, parses each file as AST and runs specified method. Some search methods ar

Bitstamp Security 7 May 29, 2022
python package for generating typescript grpc-web stubs from protobuf files.

grpc-web-proto-compile NOTE: This package has been superseded by romnn/proto-compile, which provides the same functionality but offers a lot more flex

Roman Dahm 0 Sep 05, 2021
Two fast AUC calculation implementations for python

fastauc Two fast AUC calculation implementations for python: python-based is approximately 5X faster than the default sklearn.metrics.roc_auc_score()

Vsevolod Kompantsev 26 Dec 11, 2022
EthTx - Ethereum transactions decoder

EthTx - Ethereum transactions decoder Installation pip install ethtx Requirements The package needs a few external resources, defined in EthTxConfig o

398 Dec 25, 2022