Standalone engine

[joshuajbouw]

Requirements

NOTE: Current state of this document is that the changes to Sputnik EVM are clear. The why of the Engine standalone is in. The storage aspect is clear. The FFI interfaces are still WIP.

The purpose of this change is to add geth-like [debug_traceTransaction] logic to Sputnik EVM (rust-blockchain/evm). On top of that the ability to run a standalone engine that is able to keep in sync with the network EVM.

Why this is an important change is that it is absolutely necessary for this logic for both Block Scout and Etherscan's upcoming block explorer for Aurora.

On Sputnik EVM, this is a relatively straight forward change.

rust-engine-standalone

The heart and bulk of what we need to do is here. We need to create a new library.

It needs to consist of a few parts in order to accomplish our described goals:

• An FFI interface
• Requires the same EVM wrapper over Sputnik EVM that we use for the engine, with tracing feature enabled.
• Able to take the tracing from Sputnik EVM and translate it into a simple geth-like struct.
• Holds its own state of the network EVM.
• It must have the ability to sync, and return what block it is currently on so that the Relayer is able to help get it caught up.
• It must be able to keep in sync with NEAR. However, its initial state should be added from the relayer with an initial sync.

Design

The purpose of the rust-engine-standalone is to enable the ability to run a local instance of a 1:1 compatible EVM to our Engine.

What this solves is the ability to be able to re-run transactions through a local instance of the EVM which carries its own state. This enables key features that partners of ours such as Etherscan to use methods such as debug_traceTransaction. For now, enabling everything to unblock our partner is the sole focus of this project.

FFI Interface

In regards as to why FFI was chosen over other methods is for a few reasons. Firstly, we didn't want to run it as a service with a websocket. Also, we didn't want to run it as a CLI as that would have us create quite a bit of infrastructure to run. In the end, given the requirements, WASM and FFI were the two most liekly best choices. WASM would do great in a Javascript context for instance. However, to ensure maximum compatibility, FFI was ultimately chosen.

We need to be mindful that errors could possibly crash the Relayer which would be absolutely devasting. We can not afford any downtime. For that reason, we need to route all possible panic!s to be handled in another way which prevents a crash.

FFI Methods

WIP, the general idea is very straight forward. However, there is a bit more that needs to be expanded upon here. For example, of course we just need a simple trace function that takes in a transaction ID and spits out the return of the geth-like tracer as Javascript. Also, the methods that will pass the current blocks with just Aurora information to keep the standalone in sync with the network.

Arto had mentioned that we should do the FFI in C, however Rust is perfectly capable of doing C compatible FFI in with the libc crate. This does still need to be explored if we should just do it in Rust, or in C, or both.

The examples below will be simply in Rust.

Below, the trace_transaction method must take in a transaction hash and return a TransactionTrace. The method must be able to replay a transaction with the current state in the exact same manner it was initially executed. It also must return a TransactionTrace which is defined below.

// Debug methods

/// Takes in a transaction hash and returns a `TransactionTrace`.
#[no_mangle]
pub extern "C" fn trace_transaction(tx_hash: *const [u8; 32]) -> TransactionTrace; // TransactionTrace defined below

// Storage getters

/// Gets the nonce of an Ethereum address at a given block.
/// Returns 0 on success, 1 on failure (block hash not found); the nonce variable is overwritten
/// with the requested nonce iff 0 is returned.
#[no_mangle]
pub extern "C" fn get_nonce(block_hash: *const [u8; 32], address: *const [u8; 20], nonce_out: &mut u64) -> u8;

/// Gets the balance of an Ethereum address at a given block.
/// Returns 0 on success, 1 on failure (block hash not found); the balance variable is overwritten
/// with the requested balance (big endian encoded) iff 0 is returned.
#[no_mangle]
pub extern "C" fn get_balance(block_hash: *const [u8; 32], address: *const [u8; 20], balance_out: &mut [u8; 32]) -> u8;

/// Returns the size of the EVM bytecode (in bytes) for the specified account at a given block.
/// Returns 0 on success, 1 on failure (block hash not found); the size variable is overwritten
/// with the requested balance (big endian encoded) iff 0 is returned.
#[no_mangle]
pub extern "C" fn get_code_size(block_hash: *const [u8; 32], address: *const [u8; 20], size_out: &u32) -> u8;

/// Returns the byte slice with the code for the specified account at a given block.
/// Returns 0 on success, 1 on failure (block hash not found); the code variable is overwritten
/// with the requested balance (big endian encoded) iff 0 is returned. The size of the output slice
/// needed should be determined from `get_code_size`.
#[no_mangle]
pub extern "C" fn get_code(block_hash: *const [u8; 32], address: *const [u8; 20], code_out: &mut [u8]) -> u8;

/// Gets the state value for the provided address and key values at a given block.
/// Returns 0 on success, 1 on failure (block hash not found); the value variable is overwritten
/// with the requested balance (big endian encoded) iff 0 is returned.
#[no_mangle]
pub extern "C" fn get_state(block_hash: *const [u8; 32], address: *const [u8; 20], key: *const [u8; 32], value_out: &mut [u8; 32]) -> u8;

// Storage setters

/// Submit a transaction which was included in the given block. The transaction is RPL encoded.
/// This will update the storage to include the transaction, the diff it generated, and other state metadata (see storage details).
/// The return value is 0 on success. Non-zero return values will correspond to different errors that may occur (exact errors TBD).
#[no_mangle]
fn submit_transaction(block_hash: *const [u8; 32], block_height: u64, transaction: &[u8], tx_position: u16) -> u8;

geth-like Tracer

From the following design, it should be used with the FFI returns as Javascript, based on the JavaScript-based tracing section of the debug_traceTransaction documentation.

#[repr(C)]
pub struct TraceLog {
    depth: u32,
    error: String,
    gas: u32,
    gas_cost: u32,
    memory: Vec<[u8; 32]>, // Bound memory
    opcode: u8, // opcode as byte
    program_counter: u32,
    stack: Vec<[u8; 32]>, // Local stack
    storage: Map<[u8; 32], [u8; 32]>, // As BTreeMap or whatever is efficient
}

#[repr(C)]
pub struct TransactionTrace {
    gas: u32,
    return: String,
    logs: Vec<TraceLog>,
}

Storage implementation

The standalone engine will have its own storage implementation. The goal of this storage layer is to efficiently represent the EVM state from block to block. Here we describe a proposal for how the storage should be implemented.

I propose we use RocksDB as the underlying database. RocksDB is a key-value store with sorted keys to allow efficient range queries. Therefore the key layout is important. I propose we have the following key layout:

1. First byte is a version number (this will allow easy state migrations if needed). For now we will assume the version is 0.
2. Second byte is a column indicator. This allows iterating over specific data to be easy and efficient. The columns involved are detailed below.
3. Remaining bytes (if any) are data specific to the index of the values stored in that column. For example, a balances column for a specific block would have the block hash and address as the remaining bytes in the key (and obviously the balance as the value associated with that key).

I propose the database contain the following columns indicators (given in hex):

1. 00 = Block Hash. The index is 64-bit block height, the value is the block hash at that hight (for the block in the canonical chain). Note: most other information will be indexed by block hash so that if a re-org occurs then those columns do not need modifications, only additions. This column will need to be modified with the new hashes at each height. The column indexed by transaction hash (02) will also need to be modified.
2. 01 = Block Height. The index is the 32-byte block hash, the value is the block height. Note: this column does not need to change in the case of a re-org because each block remains at its associated height, it just may no longer be part of the canonical chain.
3. 02 = Transaction Position. The index is a 32-byte transaction hash, the value is (BlockHash, u16), which represents the block and position in that block where the transaction was included. If the transaction was included in multiple blocks, then the one which is in the canonical chain is given as the value. This means this column must be modified in the case of a re-org.
4. 03 = Transaction Hash. The index is a 32-byte block hash + a 16-bit position index, the value is a transaction hash. This allows looking up the transactions which were included in a given block.
5. 04 = Diff. The index is a 32-byte block hash + a 16-bit position index, the value is the state diff the transaction executed in that block at that position caused. A state diff has the same data as is produced by a transaction execution in SputnikVM. These state diffs can be used to derive the state at any transaction from some sparse snapshots.
6. 05 = Balances. The index is a 32-byte block hash + a 20-byte address, the value is the 256-bit ETH balance. Only non-zero balances are stored. The purpose of this column is to provide a part of the state snapshot at a given block. This column will not be populated for all blocks, only a subset (say every 50 blocks), and state for other blocks will be derived from these snapshots using diffs.
7. 06 = Nonces. The index is a 32-byte block hash + a 20-byte address, the value is the 256-bit ETH nonce. Only non-zero nonces are stored. Just like the balances column, the purpose of this is occasional snapshotting of the state.
8. 07 = code. The index is a 32-byte block hash + a 20-byte address, the value is the EVM bytecode deployed at that address. Only non-zero values are stored. Just like the previous two column, the purpose of this is occasional snapshotting of the state.
9. 08 = Storage. The index is a 32-byte block hash + a 20-byte address + a 32-byte storage key, the value is a [u8; 32]. Only non-zero values are stored. Just like the previous three columns, this is used for snapshotting.

High level storage interface

The interface to interact with this storage layer will be as follows:

// getters

struct State<'a> { ... }
impl State {
    fn get_nonce(&self, address: Address) -> U256;
    fn get_balance(&self, address: Address) -> Wei;
    fn get_storage_at(&self, address: Address, key: H256) -> H256;
}

struct BasicAccountInfo {
    balance: Wei,
    nonce: U256,
    has_code: bool,
}

impl Storage {

    /// Returns an object able to get values from the pre-state of the given block + transaction index.
    /// (Pre-state means the transactions _at_ the given index has not yet been applied).
    fn get_state<'a>(&'a self, block_hash: H256, tx_position: u16) -> Result<State<'a>, Error>;

    /// Return all non-empty accounts in the post-state of the given block
    fn get_accounts(&self, block_hash: H256) -> Result<Map<Address, BasicAccountInfo>, Error>;
    
    /// Returns all accounts that were modified in some way by transactions in blocks between
    /// the two given blocks. Returns an error if the blocks are no in the canonical chain.
    /// The information returned is that of the post-state of the given end block.
    fn get_changed_accounts(&self, start_block_hash: H256, end_block_hash: H256) -> Result<Map<Address, BasicAccountInfo>, Error>;
}

// setters

struct AccountInfo {
    balance: Wei,
    nonce: U256,
    code: Vec<u8>,
    storage: Map<H256, H256>,
}

impl Storage {

    /// Consumes a NEAR transaction and updates the storage; requires the engine to get
    /// the diff from executing the transaction.
    fn submit_transaction(&mut self, block_hash: H256, block_height: u64, tx: Transaction, tx_position: u16, engine: &Engine) -> Result<(), Error>;

    /// Bootstrap the state by directly submitting a snapshot for some block
    /// (can then apply transactions to this state to get future states)
    fn submit_snapshot(&mut self, block_hash: H256, state: Map<Address, AccountInfo>)
    
}

Example Recipies of the storage

Replay given transaction

1. Look up what block the tx was executed in using column 02.
2. Look up the height of this block using column 01.
3. Check the hash at this height in column 00 matches the hash where the tx is executed (ie the tx was included in the canonical chain). If it was not then throw an error. TODO: we could probably support replay of orphaned transactions, but finding the right snapshot to start from would be much more computationally intensive, and I think this is probably a rare enough use case that it is ok to not support it initially.
4. Look up the blockhash for the closest snapshot prior to the height where the tx was executed. If we have some very regular scheme for snapshotting (eg every 50 blocks), it is easy to determine which height the snapshot would be at and get the hash from column 00. Note: this does rely on the transaction being included in the canonical chain.
5. Look up the diffs for all the transactions in all the blocks between the snapshot and the target transaction. Merge these into a single diff (this can be done because there is a natural algebra of diffs).
6. To look up any value in the state during the transaction replay (eg a balance or nonce), find it in the snapshot and modify based on the merged diff if needed.

Tracking addresses and balances

Getting a list of addresses with non-zero nonce (or really any nonce) bound is trivial by simply iterating over some block in column 06. Similarly for balances with column 05. Moreover, the diffs could be used to see only the new accounts and balances between two blocks. This could be useful for analytics or more advanced relayer rate-limiting.

Sync

It is important to be able to keep the storage up to date with the NEAR network. When starting the system for the first time we can bootstrap a storage snapshot (eg by consuming the JSON dump from contract state library). Once we have an initial snapshot, we can update the state by consuming a stream of new information from a NEAR RPC node directly. The NEAR indexer framework is a library which is designed for exactly this purpose. To populate the diffs the standalone engine would need to execute all transactions targeting aurora locally, therefore the transaction outcomes from NEAR are not important. We only need to know what blocks included transactions that target aurora.

Relayer

On the relayer side it needs to be able to run the wasm compiled code of the new code. The compiled uses the same backend and EVM with precompiles AS the engine. We simply would need to pass the transaction hash and return the trace in full as described above in the FFI methods above with the method trace_transaction.

On the relayer, it must be able to provide the full capability fullfilling the JavaScript-based tracing requires as mentions in the debug_traceTransaction documention in geth.

Of course as geth is written in Go, and our relayer implementation is in Typescript, keeping it all in Typescript should be fine and sufficient especially given our means which are more Javascript orientated.

Additionally, the relayer must pass the ongoing state changes to the standalone also described with the methods above in FFI methods. This will keep the standalone in sync.

Sputnik EVM

In the Sputnik EVM library there already exists a tracer however it does not have all the complete data required for geth-style tracing.

With the two events Step and StepResult, both can be combined into a single trace. However, there are parts that are missing that should be added in order fulfil the requirements.

Note that there are multiple Steps and a single StepResult per trace.

In geth, the object is similar to the below as follows:

{
  gas: integer,
  returnValue: string,
  structLogs: [{
    depth: integer,
    error: string,
    gas: integer,
    gasCost: integer,
    memory: [String], // vector of 32 bytes as strings
    op: string, // Opcode by name i.e, "PUSH1"
    pc: integer,
    stack: [String], // vector of 32 bytes as strings,
    storage: {key: string}, // keys are 32 bytes, to strings
  }] // structLog per execution
}

For reference, you can look at debug_traceTransaction example section.

Sputnik EVM Tracing Status

For a similar data structure we can pull most of what we need from the Sputnik EVM tracing itself. However, it is missing some key details which need to be added. The current status of what we can pull from the existing tracing in EVM is as follows.

The main trace object is as follows:

geth	Sputnik EVM StepResult
gas	Needs to be added
returnValue	StepResult::return_value
structLogs	Vector of log objects below

Log objects:

geth	Sputnik EVM Step
error	From Step::position if there is an error
depth	Needs to be computed
gas	From Gasometer tracing
gascost	Needs to be added
memory	Step::memory
op	Step::opcode
pc	From Step::position, if there isn't an error.
stack	Step::stack

From the above, we can create a similar structure in Rust on our new rust-engine-standalone library.

Tasks

Additions to Step

• Compute depth from how many calls there are, starting from 1, incrementing for each sub-call (CALL / CREATE)
• Add gas
• Add gas cost
• Add program

Aurora Engine

Right now there isn't anything we need to change on the engine itself.

[artob]

Arto had mentioned that we should do the FFI in C, however Rust is perfectly capable of doing Rust. This does still need to be explored if we should just do it in Rust, or in C, or both.

No, I had mentioned that FFIs are necessarily designed in terms of the C ABI. That is, all function signatures, data types, and data structures used in the FFI layer must be C-compatible so that they can be consumed on the other side of the FFI.

[joshuajbouw]

See libc and FFI in Rust: https://doc.rust-lang.org/nomicon/ffi.html

I'm updating to use the C interfaces and compatibility for everything. As well as writing up an example.

[joshuajbouw]

Ok, these were updated.

[mfornet]

/// Bootstrap the state by directly submitting a snapshot for some block
/// (can then apply transactions to this state to get future states)
fn submit_snapshot(&mut self, block_hash: H256, state: Map<Address, AccountInfo>)

This is an expensive operation (it is ok doing it occasionally) but beware the current size of the state used by aurora is 111MB, and it will only increase.

With that in mind, doing a snapshot every 50 blocks (roughly 50 seconds) means we will be storing >100Mb every 50 seconds. We should not be doing snapshots too often, or rather doing them only once at startup, and after that relay only on updates from the sync tool (indexer). This however, open new questions about how to efficiently access the state. In columns 4..8 we should only store values after they changed.

To access a particular value of the state we can run a lower bound. However, this means we need to start indexing by height rather than by hash, and extra care must be taken with reorgs. To avoid reorgs all-together we can establish that only finalised state will be added to these columns.

Note: To replay a tx, a persistent version of all state must be accessible, even the state that is not modified by the tx, given that it can be queried anyway.

Look up the blockhash for the closest snapshot prior to the height where the tx was executed. If we have some very regular scheme for snapshotting (eg every 50 blocks), it is easy to determine which height the snapshot would be at and get the hash from column 00.

If the field is indexed by height, lower bound can be used instead.

---

Motivation for tracer field in debug_traceTransaction

Logs in a transaction can be computed efficiently without cloning, i.e. one log can be derived from the previous log by performing small number of operations. Cloning a log, means the stack and memory will be duplicated per log which can be inefficient, regarding the overhead created for storing, buffering and communicating this data.

The main goal of having a tracer field, is to allow the user aggregate only the information they need, in parallel while logs are computed in place. This can be a significant advantage for large txs, or too frequent queries (as expected from an explorer)

[joshuajbouw]

/// Bootstrap the state by directly submitting a snapshot for some block
/// (can then apply transactions to this state to get future states)
fn submit_snapshot(&mut self, block_hash: H256, state: Map<Address, AccountInfo>)

This is an expensive operation (it is ok doing it occasionally) but beware the current size of the state used by aurora is 111MB, and it will only increase.

That is correct, and its only going to get bigger. We are looking into better methods of doing this without having to do it in the FFI. I.e, some dump of data that is in an expected file location which it is able to pick up on, read, and parse into the storage.

I'll update to reflect that later, once we get there as an requirement would be to talk to infrastructure team and figure out what kind of dumps we can get, and not just the state, but also blocks.

Motivation for tracer field in debug_traceTransaction

Logs in a transaction can be computed efficiently without cloning, i.e. one log can be derived from the previous log by performing small number of operations. Cloning a log, means the stack and memory will be duplicated per log which can be inefficient, regarding the overhead created for storing, buffering and communicating this data.

The main goal of having a tracer field, is to allow the user aggregate only the information they need, in parallel while logs are computed in place. This can be a significant advantage for large txs, or too frequent queries (as expected from an explorer)

We don't want to clone the stack and memory, and duplicate it per log. That would be quite wasteful.