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, 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
• 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, unless no account exists in the
  requested range.
• 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 gaped 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, 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
• 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.