ethereum-optimism / cannon Goto Github PK

One small, one big.

Minigeth removes all tests from upstream geth.

However, these could be quite useful in bolstering our confidence in the system.

An easy win would be to run a script over all tests in geth (in particular, in l2-geth-head), and reimport those tests that pass without modification.

Later, we can choose to put int the work to resurrect other tests as needed / convenient.

This is due to missing a Trie node when we do a delete. From trie/trie.go

				// If the remaining entry is a short node, it replaces
				// n and its key gets the missing nibble tacked to the
				// front. This avoids creating an invalid
				// shortNode{..., shortNode{...}}.  Since the entry
				// might not be loaded yet, resolve it just for this
				// check.

Now since the trie is a "SecureTrie" which hashes the key, we can't easily request the missing storage node, since we don't know the preimage of the key.

This issue can be fixed with a new API in upstream geth to fetch the trie node, but I'd really like to be able to do it with eth_getProof. Best idea I've had so far is brute forcing the SecureTrie. Any better ideas? We have the future.

I'm (only) half joking, when I ask: how hard would it be to run an optimistic Linux on the virtual MIPS processor validated by on-chain interactive fraud proofs?

kafka@largee:~/build/cannon$ npx hardhat test

  MIPSMemory contract
deployed at 0x5FbDB2315678afecb367f032d93F642f64180aa3 by 0xf39Fd6e51aad88F6F4ce6aB8827279cffFb92266
preimage initted
preimage updated
comp hash is 0x4a3d5976edd24a1a22f7fae2985b3bd41798eb1176802b50e5612f3e739d3c97
real hash is 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470

    1) Keccak should work

Not returning the correct empty hash. Easy to reproduce, who wants to fix it? 🥇

It's ported from https://github.com/firefly/wallet/blob/master/source/libs/ethers/src/keccak256.c, I would go about debugging this by diffing the two implementations and disabling rounds/transforms until you find the one that doesn't match.

@geohot could you point me where Truebit is implemented and the incentive structure for computation (Task Givers, Solvers, Verifiers)?

From README:

Preimage(hash) -> value # hash(value) == hash

In the naive case, it is easy to verify this on-chain using the SHA3 opcode. However, if the size of value is sufficiently large it becomes harder.

SHA3 uses a 1600-bit intermediate state which is fed constant-sized pieces of the input one single step at a time. However, it is not possible to verify that an individual piece of the preimage is correct up front, for the same reason. This is problematic because of the risk of an attacker inserting malicious pieces--you can't trustlessly bisect down to a single step as an honest user, since the divergent step might be a valid application of the SHA algorithm, just with invalid inputs, and this doesn't give L1 enough information to discern which party is wrong.

I tried to consider whether using a merkle tree of the data with fixed sized leaves is useful but I couldn't think of anything; it actually feels equivalent to steps where each step is a single-piece input to the SHA. Bounding the size of value is an obvious solution but not ideal.

After #77 is done, it will only be necessary to adapt/tweak the block validation so that minigeth can actually validate L2 blocks.

• document syscalls
  • in mipsevm/run_unicorn.go
  • in contract/MIPS.sol
  • document the alternative: stub out the syscalls in compile.py
  • add links to syscall references
• misc notes
  • mipigo/compile.py: document the fact that it's not easy to fully disable the GC with an env variable, because the thread is still created in case GC gets programatically re-enabled
  • document the sanity checking in mipsevm/main.go, cf. my comments here
    • for register fault, the number is the step number where the register will be modified

It's running 5M+ instructions without issue now, but it's a bit too slow to use in practice. I really don't want to maintain two implementations.

Profile and optimize, the dream is to run small blocks in 1 minute and large blocks in 10.

We can of course fast forward to the input oracle read, but that's meh.

Did I introduce it? Or was it always there, and the write back had issues always.

It's the current cause of the CI failure.

Break the program run into CHONKS.

Check each CHONK with the on chain in parallel.

./test.sh <pick a post London block number>

Will exit if a transition fails. Looking good so far!

Tested 13284475-13284575

Currently, this repo uses a fork of Unicorn made by @geohot https://github.com/geohot/unicorn.git

George said he made a few fixes to it, which do have to upstream and/or merged upstream before we can switch over, so we should track, push for the fixes to be merged and switch when we can.

Quick search releaved the following issue: unicorn-engine/unicorn#1470 but that seem to be fixed, but there seems to be more than that here: https://github.com/geohot/unicorn/commits/master

@geohot Could you comment as to what we need?

The game challenge game is a scaffold that was meant to facilitate the Cannon bug bounty. It is not secure as-is, as it assumes an honest defender, doesn't handle bonding (and probably has more issues).

This repository should inform the final design.

• #63
• #78
• #81

This should run all the scripts that are currently run in the CI (excluding the scenarios to be added in #64).

• The challenger agent is started by a verifier when he computes different output roots than the one the sequencer posted to L1. It is reponsible for playing the challenge game and proving that the output root is faulty.
• The defender agent is run by the sequencer and monitors the L1 chain for new challenges, and plays the challenge game to deny the assertion that the output root is faulty.

See implementation sketch and additional comments below.

c.L can only be changed by owner

https://github.com/ethereum-optimism/cannon/blob/master/contracts/Challenge.sol#L189-L192

if owner never calls respondState, binary search won't be finished

https://github.com/ethereum-optimism/cannon/blob/master/contracts/Challenge.sol#L209

or is there any mistake in my understanding?

The current challenge game assumes that the defender acts honestly.

Things that are needed, at minimum, we need to introduce a challenge period after which the last player to answer in the binary search wins by default if the binary search.

I would also like to take care of the issue that arises when the challenger and the defender disagree on the last step of the challenge game. In this case, the defender won't have supplied a state hash for the post state of that transition, and thus it can not prove the challenger wrong (but wins by default if the challenger doesn't prove he's right). I'd like to at least get ride of the ChallengerLosesByDefault event (as the previous paragraph implies a robust system for determining who loses by default if the challenge period expires without a clear winner). It might also make sense to allow the defender to provide the post state when proving the last step (in which case we must explicitly verify that the assert post-state is different than the one asserted by the challenger).

Dependabot is flagging a bunch of security issues with some indirect dependencies, it's probably time to update them.

Is there a library that, instead of needing each proof as a string, uses something similar to the preimage oracle?

It should also be able to write to the oracle/hashmap to allow full running of MIPS on chain with trie state.

This has to do with enabling manual intervention in case of a software bug.

If an incorrect, but unchallengeable output root is posted, governance will have 7 days to act and update the system.

However, if a correct but challengeable output root is posted, the current (unimplemented) design implies that a challenger will be able to claim the proposer bond, even though the proposer was honest and it's the system that was buggy. To avoid this, we would add a time delay (probably 7 days too) so that governance can take appropriate action.

you seem to be able to get rid of the

if err != nil {
  panic("processor error")
}

by doing a function like this according to : check nil interface

func isNil(i interface{}) {
  if i != nil {
     panic("processor error")
  }
}

then just call it like :
isNil(err)
But i dont know how to make it so you can access that function everywhere 🤣 so if this is right it should be a simple pull request for someone :)

My PR broke the demo scripts multiple times, it would be good to ensure that the CI verifies that they still run as expected.

The example fault injection scenario times out on my machine, on the very last step (the defender assertion).
This might be a hardhat issue, but it would be good to figure it out.

cf. #52 (comment)

Once that is done, we might want to add these scenarios to the CI.

kafka@largee:~/build/cannon/mipsevm$ ./evm.sh
Nothing to compile
hello
<nil> 916142 512.61µs 1 1 dead0000 test/bin/add.bin
<nil> 916813 484.401µs 1 1 dead0000 test/bin/addi.bin
<nil> 916715 468.807µs 1 1 dead0000 test/bin/addiu.bin
<nil> 916125 481.487µs 1 1 dead0000 test/bin/addu.bin
<nil> 905925 545.431µs 1 1 dead0000 test/bin/and.bin
<nil> 918999 457.992µs 1 1 dead0000 test/bin/andi.bin
<nil> 907735 532.294µs 1 1 dead0000 test/bin/bds_mtc0.bin
<nil> 910593 535.372µs 1 0 dead0000 test/bin/beq.bin
...

Should all be "1 1 dead0000", notice how beq.bin is failing

Help fix them!

Now that we have a nice makefile, it would be nice if we could make use of it to simplify the CI scripts.

Also take care of this TODO item.

The Challenge.sol contract uses uint256 without overflow checks, and there is some arithmetic in places that would benefit from overflow checks.

Updating the pragma to 0.8.x would include built-in solc overflow checks, easy fix that's worth doing.

https://github.com/ethereum-optimism/cannon/blob/master/contracts/Challenge.sol#L100-L106

will it be an L2 block hash?

and I have read SCC code, it doesn't save relationship between block number and block hash

https://github.com/ethereum-optimism/optimism/blob/develop/packages/contracts/contracts/L1/rollup/StateCommitmentChain.sol#L230-L273

Goal: have a more precise understanding of what's changed compared to mainline geth (at first, only compared to the reference commit (geth v1.10.8 release).

Setup

(You don't necessarily need to understand this, but it helps me keep things straight.)

Currently, unmodified geth files are listed in files_minigeth and synced via sync-minigeth.sh. This leaves a few added and modified files.

The new branch ns/clarify-geth-diff adds a few scripts + result files to figure this out:

• sync_minigeth2.sh
  • emits a list of added or modified (but not removed) files compared to the original commit
  • ... which it writes to minigeth2_modified_added_files
  • ... which it concatenates this with files_minigeth into files_minigeth_inc_modified_added
• sync_minigeth3.sh
  • takes files_minigeth_inc_modified_added as input
  • emits the list of changed (only) files to minigeth3_modified_files
  • emits the list of added (only) files to minigeth3_added_files
  • emits a git diff (not sure if a valid patch, it's a concat of individual git diff outputs) to minigeth3_diff_modified

Added Files

• README
• consensus/ethash/fake_ethash.go
• core/fake_blockchain.go
• crypto/btcec/README.md
• crypto/btcec/bench_test.go
• crypto/btcec/btcec.go
• crypto/btcec/btcec_test.go
• crypto/btcec/ciphering.go
• crypto/btcec/ciphering_test.go
• crypto/btcec/doc.go
• crypto/btcec/example_test.go
• crypto/btcec/field.go
• crypto/btcec/field_test.go
• crypto/btcec/genprecomps.go
• crypto/btcec/gensecp256k1.go
• crypto/btcec/precompute.go
• crypto/btcec/privkey.go
• crypto/btcec/privkey_test.go
• crypto/btcec/pubkey.go
• crypto/btcec/pubkey_test.go
• crypto/btcec/secp256k1.go
• crypto/btcec/signature.go
• crypto/btcec/signature_test.go
• go-ethereum
• main.go
• oracle/apitypes.go
• oracle/embedded_mips.go
• oracle/prefetch.go
• oracle/preimage.go

Modified Files

• Gist containing the diff

If necessary we could also manufacture a commit showcasing this diff.

One promise of L2 rollup is that one can recover L2 state purely from L1, if you only submit header to L1, it will break this promise IMO.

Move the GetBlock logic into the oracle, and remove all the typescript

It should do so to be consistent with respond.js and assert.js and enable alternative chain IDs to be used.

Describe the bug

While following the README instructions per #39 to build unicorn2 and add it to the path, then running (cd mipigo && pip3 install -r requirements.txt && ./build.sh), the build script fails in compile.py with:

minigeth: ELF 32-bit MSB executable, MIPS, MIPS32 version 1 (SYSV), statically linked, Go BuildID=bDYCrfVpTyMfiuLGtgZF/2QGo5f3BgyUSXs3lAsHt/1mOX1QQLpy7Zu7LDoXo9/8OegC7znh-c8tNFpPm6U, not stripped
Trying to load shared library /Users/maurelian/Projects/O/cannon/unicorn2/libunicorn.dylib
SUCCESS
Traceback (most recent call last):
  File "/Users/maurelian/Projects/O/cannon/mipigo/./compile.py", line 74, in <module>
    mu = Uc(UC_ARCH_MIPS, UC_MODE_32 + UC_MODE_BIG_ENDIAN)
  File "/Users/maurelian/Projects/O/cannon/venv/lib/python3.9/site-packages/unicorn/unicorn.py", line 312, in __init__
    raise UcError(uc.UC_ERR_VERSION)
unicorn.unicorn.UcError: Different API version between core & binding (UC_ERR_VERSION)

By adding some print statements to unicorn.py, it appears that the python package is expecting a v1 engine, but the core unicorn lib is v2.

• #64
• #84
• #86
• make it possible to randomize fault injection, cf. my comments here

Cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon?

Cannon cannon cannon cannon cannon cannon cannon cannon:

Cannon: cannon cannon cannon cannon
Cannon: cannon
Cannon: cannon cannon cannon cannon cannon cannon cannon cannon

Cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon cannon.

Then use the hash oracle to get the inputs. This saves gas.

There is a literal ton of files being written to the cache, even if you have a SSD, this has to be one of the slower parts of the operations being done (took quite some time to remove 50GB of tiny tiny files even with rm -rf /tmp/eth) 😄
Even though its done in the Preimageand PrefetchBlock, i still guess it counts to the overall time "handling" a block.
Right?

I guess storing it directly in memory, and forgetting it when done has its own set of problems, like using a ton of memory and problematic to find each blocks data, and it wouldnt serve as a cache either...

and just having one file for /tmp/eth/0xblock and /tmp/eth/json_block which you open once, then read/write to as long as the test.sh is running ...yeah that causes problems aswell.

just thinking out "loud".
please close if gibberish :)

Hacked on it until it worked, but I think there's type confusion between:

• RLP strings
• RLP lists
• hashes

and there's just length compares to deal with it

• #77
• #85
• Add the rollup driver logic to minigeth

Currently, the MIPS memory is merkleized by mipsevm (this is termed a checkpoint), and required nodes are uploaded to the MIPSMemory.sol contract (via the AddTrieNode function). MIPS execution on the EVM then reads from the trie whenever it needs to access MIPS memory.

The Merkle Patricia Trie logic that we use matches that used in Ethereum itself. It's very complex and brittle (e.g. it uses RLP encoding and various space-saving tricks). There is no reason to use this format for the MIPS memory (besides that it's already implemented in Go by geth).

The suggested replacement is a simple 16-branch hash trie. Each node is the hash of the concatenation of all of its children (or 0x0 if there is not children at a given slot). Leaves are 4 bytes MIPS words (left-padded with 28 0 bytes for hashing purposes in non-leave nodes).

Note that when merkleizing the memory, we only store memory locations that have been actually written. The rest is implicitly zero.

However, this is probably too inefficient. In particular preimages of normal nodes are 16*32 = 512 bytes, and every address read needs to traverse 8 nodes to get to the leaf depth. We probably want to reintroduce some compression techniques, but we want them vastly simpler than the MPT ones. Here's a suggestion:

• Node compression: Start with a 32 bytes index made of 16 uint16, whose value are to be interpreted as follows:

  • a value of 0x0000 indicates the absence of a child
  • another value indicates the index in the preimage where the 32 bytes node hash starts
  • (This makes nodes with two children 96 bytes instead of the previous 512 bytes.)

• Continuation nodes: if a sub-tree forms "a linked-list of nodes" (i.e. each node in the subtree has a single child), then we could replace the hash for this subtree by hash(full_address ++ leaf_mips_word). When getting the preimage for a node, we just have to check the length of the preimage to distinguish normal nodes from continuation nodes: continuation nodes are 8 bytes (address + value), while normal nodes are >= 96 bytes (32 byte sof index + at least 2 hash of 32 bytes each).

Someone has finally built out a simple library for using extcodecopy instead of sload for write-only storage. What great timing!

Using this library in place of bytes storage in the preimage oracle should be a very easy way to help with #16 .

By fixing the Go code to properly count BDS steps, we can avoid needing to disassemble the instructions in Python, and we should be able to make the Python fast.

Half the time is spend in btcec. 10% is in keccak.

github.com/btcsuite/btcd/btcec.(*fieldVal).SquareVal                             : 26.57%                                                                                 
github.com/btcsuite/btcd/btcec.(*fieldVal).Mul2                                  : 24.66%                                                                                 
golang.org/x/crypto/sha3.keccakF1600                                             : 11.23%                                                                                 
github.com/ethereum/go-ethereum/core/vm.codeBitmapInternal                       : 3.68%                                                                                  
github.com/btcsuite/btcd/btcec.(*fieldVal).Normalize                             : 3.03%                                                                                  
runtime.mallocgc                                                                 : 2.81%                                                                                  
github.com/ethereum/go-ethereum/core/vm.(*EVMInterpreter).Run                    : 1.61%                                                                                  
github.com/btcsuite/btcd/btcec.(*KoblitzCurve).addZ2EqualsOne                    : 1.46%                                                                                  
github.com/btcsuite/btcd/btcec.(*KoblitzCurve).doubleGeneric                     : 1.21%                                                                                  
runtime.heapBitsSetType                                                          : 1.09%  

with a heavier block this is less true

github.com/btcsuite/btcd/btcec.(*fieldVal).SquareVal                             : 17.67%                                                                     
github.com/btcsuite/btcd/btcec.(*fieldVal).Mul2                                  : 17.50%                                                                 
github.com/ethereum/go-ethereum/core/vm.codeBitmapInternal                       : 7.16%                                                                    
golang.org/x/crypto/sha3.keccakF1600                                             : 5.72%                                                                  
github.com/ethereum/go-ethereum/core/vm.(*EVMInterpreter).Run                    : 5.13%                                                        
runtime.mallocgc                                                                 : 4.33%                                                                                  
github.com/btcsuite/btcd/btcec.(*fieldVal).Normalize                             : 1.84%                                                                  
runtime.heapBitsSetType                                                          : 1.44%                                                                 
runtime.memmove                                                                  : 1.28%                                                                                  
github.com/ethereum/go-ethereum/core/vm.(*Memory).Set32                          : 1.21%  

What a waste of time on the CGO stuff