Skip to content

Latest commit

 

History

History
415 lines (319 loc) · 20.7 KB

snap.md

File metadata and controls

415 lines (319 loc) · 20.7 KB
Raw

Ethereum Snapshot Protocol (SNAP)

The snap protocol runs on top of RLPx, facilitating the exchange of Ethereum state snapshots between peers. The protocol is an optional extension for peers supporting (or caring about) the dynamic snapshot format.

The current version is snap/1.

Overview

The snap protocol is designed for semi real-time data retrieval. It's goal is to make dynamic snapshots of recent states available for peers. The snap protocol does not take part in chain maintenance (block and transaction propagation); and it is meant to be run side-by-side with the eth protocol, not standalone (e.g. chain progression is announced via eth).

The protocol itself is simplistic by design (take note, the supporting implementation is everything but simple). In its crux, snap supports retrieving a contiguous segment of accounts from the Ethereum state trie, or a contiguous segment of storage slots from one particular storage trie. Both replies are Merkle proven for immediate verification. In addition batches of bytecodes can also be retrieved similarly to the eth protocol.

The synchronization mechanism the protocol enables is for peers to retrieve and verify all the account and storage data without downloading intermediate Merkle trie nodes. The final state trie is reassembled locally. An additional complexity nodes must be aware of, is that state is ephemeral and moves with the chain, so syncers need to support reassembling partially consistent state segments. This is supported by trie node retrieval similar to eth, which can be used to heal trie inconsistencies (more on this later).

The snap protocol permits downloading the entire Ethereum state without having to download all the intermediate Merkle proofs, which can be regenerated locally. This reduces the networking load enormously:

  • Ingress bandwidth is reduced from O(accounts * log account + SUM(states * log states)) (Merkle trie nodes) to O(accounts + SUM(states)) (actual state data).
  • Egress bandwidth is reduced from O(accounts * log account + SUM(states * log states)) * 32 bytes (Merkle trie node hashes) to O(accounts + SUM(states)) / 100000 bytes (number of 100KB chucks to cover the state).
  • Round trip time is reduced from O(accounts * log account + SUM(states * log states)) / 384 (states retrieval packets) to O(accounts + SUM(states)) / 100000 bytes (number of 100KB chucks to cover the state).

Expected results

To put some numbers on the above abstract orders of magnitudes, synchronizing Ethereum mainnet state (i.e. ignoring blocks and receipts, as those are the same) with eth vs. the snap protocol:

Block ~#11,177,000:

  • Accounts: 107,598,788 @ 19.70GiB
  • Byte codes: 319,654 @ 1.48GiB
  • Storage slots: 365,787,020 @ 49.88GiB
  • Trie nodes: 617,045,138
Time Upload Download Packets Serving disk reads*
eth 10h50m 20.38GB 43.8GB 1607M 15.68TB
snap 2h6m 0.15GB 20.44GB 0.099M 0.096TB
-80.6% -99.26% -53.33% -99.993% -99.39%

*Also accounts for other peer requests during the time span.

Post snap state heal:

  • Additional trie nodes: 541,260 @ 160.44MiB
  • Additional byte codes: 34 @ 234.98KiB

Relation to eth

The snap protocol is a dependent satellite of eth (i.e. to run snap, you need to run eth too), not a fully standalone protocol. This is a deliberate design decision:

  • snap is meant to be a bootstrap aid for newly joining full nodes. By enforcing all snap peers to also speak eth, we can avoid non-full nodes from lingering attached to snap indefinitely.
  • eth already contains well established chain and fork negotiation mechanisms, as well as remote peer staleness detection during sync. By running both protocols side-by-side, snap can benefit of all these mechanisms without having to duplicate them.

This satellite status may be changed later, but it's better to launch with a more restricted protocol first and then expand if need be vs. trying to withdraw depended-upon features.

The snap protocol is not an extension / next version of eth as it relies on the availability of a snapshot acceleration structure that can iterate accounts and storage slots linearly. Its purpose is also one specific sync method that might not be suitable for all clients. Keeping snap as a separate protocol permits every client to decide to pursue it or not, without hindering their capacity to participate in the eth protocol.

Synchronization algorithm

The crux of the snapshot synchronization is making contiguous ranges of accounts and storage slots available for remote retrieval. The sort order is the same as the state trie iteration order, which makes it possible to not only request N subsequent accounts, but also to Merkle prove them. Some important properties of this simple algorithm:

  • Opposed to fast sync, we only need to transfer the useful leaf data from the state trie and can reconstruct internal nodes locally.
  • Opposed to warp sync, we can download small chunks of accounts and storage slots and immediately verify their Merkle proofs, making junk attacks impossible.
  • Opposed to warp sync, random account ranges can be retrieved, thus synchronization concurrency is totally dependent on client implementation and is not forced by the protocol.

The gotcha of the snapshot synchronization is that serving nodes need to be able to provide fast iterable access to the state of the most recent N (128) blocks. Iterating the Merkle trie itself might be functional, but it's not viable (iterating the state trie at the time of writing takes 9h 30m on an idle machine). Geth introduced support for dynamic snapshots, which allows iterating all the accounts in 7m (see blog for more). Some important properties of the dynamic snapshots:

  • Serving a contiguous range of accounts or storage slots take O(n) operations, and more importantly, it's the same for disk access too, being stored contiguously on disk (not counting the database read amplification).
  • Maintaining a live dynamic snapshot means:
    • Opposed to warp sync, syncing nodes can always get the latest data, thus they don't need to process days' worth of blocks afterwards.
    • Opposed to warp sync, there is no pre-computation to generate a snapshot (it's updated live), so there's no periodic burden on the nodes to iterate the tries (there it an initial burden to create the first snapshot after sync though).
    • Providing access to 128 recent snapshots permits O(1) direct access to any account and state, which can be used during EVM execution for SLOAD.

The caveat of the snapshot synchronization is that as with fast sync (and opposed to warp sync), the available data constantly moves (as new blocks arrive). The probability of finishing sync before the 128 block window (15m) moves out is asymptotically zero. This is not a problem, because we can self-heal. It is fine to import state snapshot chunks from different tries, because the inconsistencies can be fixed by running a fast-sync-style-state-sync on top of the assembled semi-correct state afterwards. Some important properties of the self-healing:

  • Synchronization can be aborted at any time and resumed later. It might cause self-healing to run longer, but it will fix the data either way.
  • Synchronization on slow connections is guaranteed to finish too (as long as the node can download data faster than it's being produced by the network), the data cannot disappear from the network (opposed to warp sync).

Data format

The accounts in the snap protocol are analogous to the Ethereum RLP consensus encoding (same fields, same order), but in a slim format:

  • The code hash is empty list instead of Keccak256("")
  • The root hash is empty list instead of Hash(<empty trie>)

This is done to avoid having to transfer the same 32+32 bytes for all plain accounts over the network.

Protocol Messages

GetAccountRange (0x00)

[reqID: P, rootHash: B_32, startingHash: B_32, limitHash: B_32, responseBytes: P]

Requests an unknown number of accounts from a given account trie, starting at the specified account hash and capped by the maximum allowed response size in bytes. The intended purpose of this message is to fetch a large number of subsequent accounts from a remote node and reconstruct a state subtrie locally.

  • reqID: Request ID to match up responses with
  • rootHash: Root hash of the account trie to serve
  • startingHash: Account hash of the first to retrieve
  • limitHash: Account hash after which to stop serving data
  • responseBytes: Soft limit at which to stop returning data

Notes:

  • Nodes must always respond to the query.
  • If the node does not have the state for the requested state root, it must return an empty reply. It is the responsibility of the caller to query an state not older than 128 blocks.
  • The responding node is allowed to return less data than requested (own QoS limits), but the node must return at least one account. If no accounts exist between startingHash and limitHash, then the first (if any) account after limitHash must be provided.
  • The responding node must Merkle prove the starting hash (even if it does not exist) and the last returned account (if any exists after the starting hash).

Rationale:

  • The starting account is identified deliberately by hash and not by address. As the accounts in the Ethereum Merkle trie are sorted by hash, the address is irrelevant. In addition, there is no consensus requirement for full nodes to be aware of the address pre-images.
  • The response is capped by byte size and not by number of accounts, because it makes the network traffic more deterministic. As the state density is unknowable, it's also impossible to delimit the query with an ending hash.

Caveats:

  • When requesting accounts from a starting hash, malicious nodes may skip ahead and return a gapped reply. Such a reply would cause sync to finish early with a lot of missing data. Proof of non-existence for the starting hash prevents this attack, completely covering the range from start to end.
  • No special signaling is needed if there are no more accounts after the last returned one, as the attached Merkle proof for the last account will have all trie nodes right of the proven path zero.

AccountRange (0x01)

[reqID: P, accounts: [[accHash: B_32, accBody: B], ...], proof: [node_1: B, node_2, ...]]

Returns a number of consecutive accounts and the Merkle proofs for the entire range (boundary proofs). The left-side proof must be for the requested origin hash (even if an associated account does not exist) and the right-side proof must be for the last returned account.

  • reqID: ID of the request this is a response for
  • accounts: List of consecutive accounts from the trie
    • accHash: Hash of the account address (trie path)
    • accBody: Account body in slim format
  • proof: List of trie nodes proving the account range

Notes:

  • If the account range is the entire state (requested origin was 0x00..0 and all accounts fit into the response), no proofs should be sent along the response. This is unlikely for accounts, but since it's a common situation for storage slots, this clause keeps the behavior the same across both.

GetStorageRanges (0x02)

[reqID: P, rootHash: B_32, accountHashes: [B_32], startingHash: B, limitHash: B, responseBytes: P]

Requests the storage slots of multiple accounts' storage tries. Since certain contracts have huge state, the method can also request storage slots from a single account, starting at a specific storage key hash. The intended purpose of this message is to fetch a large number of subsequent storage slots from a remote node and reconstruct a state subtrie locally.

  • reqID: Request ID to match up responses with
  • rootHash: Root hash of the account trie to serve
  • accountHashes: Account hashes of the storage tries to serve
  • startingHash: Storage slot hash of the first to retrieve
  • limitHash: Storage slot hash after which to stop serving
  • responseBytes: Soft limit at which to stop returning data

Notes:

  • Nodes must always respond to the query.
  • If the node does not have the state for the requested state root or for any requested account hash, it must return an empty reply. It is the responsibility of the caller to query an state not older than 128 blocks; and the caller is expected to only ever query existing accounts.
  • The responding node is allowed to return less data than requested (serving QoS limits), but the node must return at least one slot, unless none exists.
  • If multiple accounts' storage is requested, serving nodes should reply with the entire storage ranges (thus no Merkle proofs needed), up to the first contract which exceeds the packet limit. If the last included storage range does not fit entirely, a Merkle proof must be attached to that and only that.
  • If a single account's storage is requested, serving nodes should only return slots starting with the requested starting hash, up to the last one or until the packet fills up. It the entire storage range is not being returned, a Merkle proof must be attached.
  • If a proof is attached, the responding node must Merkle prove the starting hash (even if it does not exist) and the last returned slot (if any exists after the starting hash).

Rationale:

  • The response is capped by byte size and not by number of slots, because it makes the network traffic more deterministic.
  • The request supports querying multiple contracts at the same time as most storage tries are in the order of 100s of bytes. Querying these individually would produce a lot of network round trips.

Caveats:

  • When requesting storage slots from a starting hash, malicious nodes may skip ahead and return a prefix-gapped reply. Such a reply would cause sync to finish early with a lot of missing data. Proof of non-existence for the starting hash prevents this attack, completely covering the range from start to end.
  • Although serving nodes should respect the response limit requested by the caller, it is valuable to slightly force the limit (consider it soft only) when adding the last contract to avoid having to split it and prove it.
  • No special signaling is needed if there are no more slots after the last returned one, as the attached Merkle proof for the last account will have all trie nodes right of the proven path zero.

StorageRanges (0x03)

[reqID: P, slots: [[[slotHash: B_32, slotData: B], ...], ...], proof: [node_1: B, node_2, ...]]

Returns a number of consecutive storage slots for the requested account (i.e. list of list of slots) and optionally the Merkle proofs for the last range (boundary proofs) if it only partially covers the storage trie. The left-side proof must be for the requested origin slots (even if it does not exist) and the right-side proof must be for the last returned slots.

  • reqID: ID of the request this is a response for
  • slots: List of list of consecutive slots from the trie (one list per account)
    • slotHash: Hash of the storage slot key (trie path)
    • slotData: Data content of the slot
  • proof: List of trie nodes proving the slot range

Notes:

  • If the slot range is the entire storage state, no proofs will be sent along the response.

GetByteCodes (0x04)

[reqID: P, hashes: [hash1: B_32, hash2: B_32, ...], bytes: P]

Requests a number of contract byte-codes by hash. This is analogous to the eth/63 GetNodeData, but restricted to only bytecode to break the generality that causes issues with database optimizations. The intended purpose of this request is to allow retrieving the code associated with accounts retrieved via GetAccountRange, but it's needed during healing too.

  • reqID: Request ID to match up responses with
  • hashes: Code hashes to retrieve the code for
  • bytes: Soft limit at which to stop returning data

This functionality was duplicated into snap from eth/65 to permit eth long term to become a chain maintenance protocol only and move synchronization primitives out into satellite protocols only.

Notes:

  • Nodes must always respond to the query.
  • The returned codes must be in the request order.
  • The responding node is allowed to return less data than requested (serving QoS limits), but the node must return at least one bytecode, unless none requested are available, in which case it must answer with an empty response.
  • If a bytecode is unavailable, the node must skip that slot and proceed to the next one. The node must not return nil or other placeholders.

Rationale:

  • The response is capped by byte size and not by number of slots, because it makes the network traffic more deterministic, as contract sizes can vary randomly up to 24KB with current consensus rules.
  • By retaining the original request order and skipping unavailable bytecodes, the requesting node can differentiate between unavailable data (gaps in the hashes) and QoS limitations (missing suffix).

Caveats:

  • Implementations are free to request as many or as few bytecodes in a single request, but they should keep in mind that requesting too few results in wasted time due to network latency; but requesting too many results in wasted bandwidth if the response doesn't fit. Average (unique) contract size on mainnet is about 5-6KB, so bytes / 6KB is a good heuristic for the number of codes to request in a single packet (e.g. for 512KB desired response size, 80-100 bytecodes per request is a good choice).

ByteCodes (0x05)

[reqID: P, codes: [code1: B, code2: B, ...]]

Returns a number of requested contract codes. The order is the same as in the request, but there might be gaps if not all codes are available or there might be fewer is QoS limits are reached.

GetTrieNodes (0x06)

[reqID: P, rootHash: B_32, paths: [[accPath: B, slotPath1: B, slotPath2: B, ...]...], bytes: P]

Requests a number of state (either account or storage) Merkle trie nodes by path. This is analogous in functionality to the eth/63 GetNodeData, but restricted to only tries and queried by path, to break the generality that causes issues with database optimizations.

  • reqID: Request ID to match up responses with
  • rootHash: Root hash of the account trie to serve
  • paths: Trie paths to retrieve the nodes for, grouped by account
  • bytes: Soft limit at which to stop returning data

The paths is one array of trie node paths to retrieve per account (i.e. list of list of paths). Each list in the array special cases the first element as the path in the account trie and the remaining elements as paths in the storage trie. To address an account node, the inner list should have a length of 1 consisting of only the account path. Partial paths (<32 bytes) should be compact encoded per the Ethereum wire protocol, full paths should be plain binary encoded.

This functionality was mutated into snap from eth/65 to permit eth long term to become a chain maintenance protocol only and move synchronization primitives out into satellite protocols only.

Notes:

  • Nodes must always respond to the query.
  • The returned nodes must be in the request order.
  • If the node does not have the state for the requested state root or for any requested account paths, it must return an empty reply. It is the responsibility of the caller to query an state not older than 128 blocks; and the caller is expected to only ever query existing trie nodes.
  • The responding node is allowed to return less data than requested (serving QoS limits), but the node must return at least one trie node.

Rationale:

  • The response is capped by byte size and not by number of slots, because it makes the network traffic more deterministic. Although opposed to the previous request types (accounts, slots, codes), trie nodes are relatively deterministic (100-500B), the protocol remains cleaner if all packets follow the same traffic shaping rules.
  • A naive way to represent trie nodes would be a simple list of account || storage path segments concatenated, but that would be very wasteful on the network as it would duplicate the account hash for every storage trie node.

TrieNodes (0x07)

[reqID: P, nodes: [node1: B, node2: B, ...]]

Returns a number of requested state trie nodes. The order is the same as in the request, but there might be fewer is QoS limits are reached.

Change Log

snap/1 (November 2020)

Version 1 was the introduction of the snapshot protocol.