cannon: proof of concept multi-threading support

[protolambda]

Description

This is a proof of concept that shows how we can implement a minimal version of futexes and thread scheduling to handle concurrent programs.

This enables Cannon to run Go programs with GC and other concurrency like mutexes, channels, waitgroups, etc.

Cannon still proves only a single sequential execution trace, but as part of the syscalls and instruction execution it can now rotate between threads to support async functionality of programs deterministically.

The proof of concept:

• changes the state format to separate a "thread context" from the global VM state
• updates the offchain MIPS emulator code to support several new syscalls:
  • futex: with wait & wake ops, to support the locking functionalities requird by the Go runtime
    • wake prioritizes finding a thread to test unlock that is stuck on the requested memory address
    • wait parks a thread and continues with the next
  • clone: to create threads
  • exit: to shut down threads
  • yield and nanosleep: simply makes the scheduler look at the next thread
  • several no-op syscalls, to cover new runtime behavior that can be ignored (hints / performance / time things)

This does not yet update the witness-encoding or the onchain emulator part.

For onchain functionality we need to add a fixed-size proof for the current thread in the threads-list (as binary merkle tree), and an optional second proof to help append a new thread upon clone operation. And then just mirror the Go logic for state changes.

Tests

Updated the "hello" Go program to include some concurrent things in Go:

• waitgroup
• non-blocking and blocking channels
• go routines
• GC

And I had to disable the EVM <> Go tests for now, as I have not updated the solidity implementation or applied the state format chnages to the EVM Go tests.

Additional context

For now just an experiment, but for longer heavier programs making this production ready may be worth the benefits of GC.

[semgrep-app[bot]]

Semgrep found 6 todos_require_linear findings:

• cannon/mipsevm/state.go: L40, L39, L38
• cannon/mipsevm/mips.go: L36
• cannon/mipsevm/instrumented.go: L86, L66

Please create a Linear ticket for this TODO.

_{Ignore this finding from todos_require_linear.}

[github-actions[bot]]

This PR is stale because it has been open 14 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[github-actions[bot]]

This PR is stale because it has been open 14 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[github-actions[bot]]

This PR is stale because it has been open 14 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[github-actions[bot]]

This PR is stale because it has been open 14 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[github-actions[bot]]

This PR is stale because it has been open 14 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[github-actions[bot]]

This PR is stale because it has been open 14 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[github-actions[bot]]

This PR is stale because it has been open 14 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[protolambda]

Keeping this PR open just to preserve the branch at this point, so I can look at it when experimenting with Cannon/Asterisc in new domains, soon hopefully, once higher priority work clears up :sweat_smile: .

[refcell]

Hey @protolambda, tacking on the https://github.com/ethereum-optimism/optimism/labels/S-exempt-stale label on here so you don't need to constantly remove https://github.com/ethereum-optimism/optimism/labels/Stale

[codecov[bot]]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 2.35%. Comparing base (61b2b36) to head (a60c3cb). Report is 1 commits behind head on develop.

:exclamation: Current head a60c3cb differs from pull request most recent head 32b29ff

Please upload reports for the commit 32b29ff to get more accurate results.

Additional details and impacted files

@@             Coverage Diff             @@
##           develop   #7281       +/-   ##
===========================================
- Coverage    54.65%   2.35%   -52.30%     
===========================================
  Files           37      25       -12     
  Lines         2944     637     -2307     
  Branches       415     115      -300     
===========================================
- Hits          1609      15     -1594     
+ Misses        1303     622      -681     
+ Partials        32       0       -32     

Flag	Coverage Δ
cannon-go-tests	?
chain-mon-tests	?
contracts-bedrock-tests	2.35% <ø> (?)
sdk-tests	?

Flags with carried forward coverage won't be shown. Click here to find out more.

see 62 files with indirect coverage changes

[protolambda]

One key insight that I had after the initial draft, and which I am not sure I put put there on github, is that it can be implemented without merkleizing a list of thread contexts

The trick is to not go 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3 etc. through the threads, but instead 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, ....

By going back and forth in the list of thread-contexts, you can instead just maintain two hash-onions, much simpler to prove, just a single bytes32 witness necessary.

For multi-threading, it doesn't really matter all that much which order the thread continuations are attempted in, as there's no guarantee in an actually parallel environment anyway. It just needs to be deterministic

So by maintaining two "stacks" of thread contexts, committed to as hash-onions, you can get a very simple/elegant way of traversing all that thread data.

And, bonus: adding/removing threads is super simple: you navigate to the thread with the given ID, and then not push it back on either the left or right stack, to remove it. Or, if creating a thread, just add it to either stack, by hashing the new thread with the existing value, and then overwriting the existing value with that

[semgrep-app[bot]]

Semgrep found 1 writable-filesystem-service finding:

• ufm-test-services/docker-compose.yml
  • L27 - Triage

Service 'grafana' is running with a writable root filesystem. This may allow malicious applications to download and run additional payloads, or modify container files. If an application inside a container has to save something temporarily consider using a tmpfs. Add 'read_only: true' to this service to prevent this.

_{Ignore this finding from writable-filesystem-service.}

Semgrep found 3 port-all-interfaces findings:

• ufm-test-services/docker-compose.yml
  • L8 - Triage
  • L18 - Triage
  • L31 - Triage

Service port is exposed on all interfaces

_{Ignore this finding from port-all-interfaces.}

Semgrep found 1 missing-user finding:

• ufm-test-services/metamask/Dockerfile
  • L27 - Triage

By not specifying a USER, a program in the container may run as 'root'. This is a security hazard. If an attacker can control a process running as root, they may have control over the container. Ensure that the last USER in a Dockerfile is a USER other than 'root'.

_{Ignore this finding from missing-user.}

[tynes]

heroic