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:
{
"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
:
{
"contracts": {
"0": {
"code": ",,,,,,,,,,,,,,,,,,,,,[>+++++++<-]",
"cells": [
0,
21
],
"ptr": 0
}
}
}
Now say some malicious sequencer committed to a different state of this contract, what happens?
- Any honest user sees the mismatch with their local transition
- Generate a fraud proof witness
- They open a challenge on-chain
- They do an interactive game to find the first differing step
- They extract the witness for this particular step from the fraud proof data
- 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:
{
"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
{
"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.