Skip to content

Latest commit

 

History

History
450 lines (331 loc) · 20.7 KB

les.md

File metadata and controls

450 lines (331 loc) · 20.7 KB
Raw

Light Ethereum Subprotocol (LES)

The Light Ethereum Subprotocol (LES) is the protocol used by "light" clients, which only download block headers as they appear and fetch other parts of the blockchain on-demand. They provide full functionality in terms of safely accessing the blockchain, but do not mine and therefore do not take part in the consensus process. Full and archive nodes can also support the 'les' protocol besides 'eth' in order to be able to serve light nodes.

The current protocol version is les/2. See end of document for a list of changes in past protocol versions. Some of the les protocol messages are similar to of the Ethereum Wire Protocol, with the addition of a few new fields.

Canonical Hash Trie

Canonical Hash Trie (CHT) structures are used by LES for quick initial syncing and secure on-demand retrieval of canonical hash mappings, block headers and total difficulty (TD) values.

A CHT is a Merkle trie (specifically 'Merkle Patricia Trie' as used for Ethereum state) that contains blockNumber -> [blockHash, TD] mappings where keys are binary big endian encoded 64 bit integers and values are RLP-encoded [hash, number] pairs.

CHTs are generated by LES servers for every 32768 blocks, CHT[i] containing data for blocks 0..i * 32768-1. If a client knows the root hash of CHT[i] and wants to fetch header number N (where N < i * 32768), it can obtain the header and the corresponding Merkle proof of the CHT with a GetHelperTrieProofs request.

CHTs are only generated after 2048 confirmations, making it sure they will not be changed by a chain reorg. In the current version of the light client there is a hard-coded [chtNumber, chtRoot] pair associated with the genesis block hash of both the mainnet and the testnet. A trustless validation algorithm is planned for later protocol versions.

BloomBits

The BloomBits data structure optimizes log searching by doing a bitwise transformation that makes it cheaper to retrieve bloom filter data relevant to a specific filter.

When searching in a long section of the block history, we are checking three specific bits of each bloom filter per queried address/topic. In order to do that, LES must retrieve a ~550 byte block header per filtered block.

The BloomBits structure optimizes bloom filter lookups through a "bitwise 90 degree rotation" of the bloom filters. Blocks are grouped into fixed length sections (section size for the LES BloomBits Trie is 32768 blocks), BloomBits[bitIdx][sectionIdx] is a 32768 bit (4096 byte) long bit vector that contains a single bit of each bloom filter from the block range sectionIdx*SectionSize ... (sectionIdx+1)*SectionSize-1. Since bloom filters are usually sparse, a simple data compression makes this structure even more efficient, especially for on-demand retrieval. By reading and binary AND-ing three BloomBits sections, we can filter for an address/topic in 32768 blocks at once ("1" bits in the binary AND result mean bloom matches).

Compression Algorithm

BloomBits data is stored in compressed form. The compression algorithm is optimized for sparse input data which contains a lot of zero bytes. Decompression requires knowledge of the decompressed data length.

The algorithm can be described with this pseudo-code:

if data only contains zeroes,
    CompressBytes(data) == nil
otherwise if len(data) <= 1,
    CompressBytes(data) == data
otherwise:
    CompressBytes(data) == append(CompressBytes(nonZeroBitset(data)), nonZeroBytes(data)...)
    where
      nonZeroBitset(data) is a bit vector with len(data) bits (MSB first):
          nonZeroBitset(data)[i/8] && (1 << (7-i%8)) != 0  if data[i] != 0
          len(nonZeroBitset(data)) == (len(data)+7)/8
      nonZeroBytes(data) contains the non-zero bytes of data in the same order

BloomBits Trie

In order to make this data structure retrievable on-demand for the light client, we put the generated vectors in a trie. Parts of this trie can be retrieved with the GetHelperTrieProofs message. Currently the trie root is part of the trusted syncing checkpoint but trustless validation of the BloomBits trie is part of the development plans. The trie consists of the compressed bit vectors as values stored at keys constructed from the the bloom bit index encoded as a 2-byte big endian, followed by the section index encoded as an 8-byte big endian. Since all-zero bit vectors have a zero length when compressed, these vectors are not added to the trie at all.

BloomBits tries are generated for each new section of transformed bloom filter data by adding the vectors belonging to the latest section index to the previous trie.

Client Side Flow Control

Any node which takes on a server role in the the LES protocol needs to be able to somehow limit the amount of work it does for each client peer during a given time period. They can always just serve requests slowly if they are overloaded, but it is beneficial to give some sort of flow control feedback to the clients. This way, clients could (and would have incentive to) behave nicely and not send requests too quickly in the first place (and then possibly timeout and resend while the server is still working on them). They could also distribute requests better between multiple servers they are connected to. And if clients can do this, servers can expect them to do this and drop them instantly if they break the flow control rules.

The Model

Let us assume that serving each request has a cost (depending on type and parameters) for the server. This cost is determined by the server, but it has an upper limit for any valid request. The server assigns a "buffer" for each client from which the cost of each request is deduced. The buffer has an upper limit (the "buffer limit") and a recharge rate (cost per second). The server can decide to recharge it more quickly at any time if it has more free resources, but there is a guaranteed minimum recharge rate. If a request is received that would drain the client's buffer below zero, the client has broken the flow control rules and is disconnected.

The Protocol

The server announces three parameters in the Status message:

  • "flowControl/BL": Buffer Limit, an integer value
  • "flowControl/MRR": Minimum Rate of Recharge, an integer value
  • "flowControl/MRC": Maximum Request Cost table. The value of this parameter is a table assigning cost values to every on-demand retrieval message in the LES protocol. The table is encoded as a list of integer triples: [[MsgCode, BaseCost, ReqCost], ...]

On the server side:

When a client connects, the server sets the initial Buffer Value (BV) of the client to BL and announces BL in Status. When a request is received from the client, it calculates the cost according to its own estimates (but not higher than MaxCost, which equals BaseCost + ReqCost * N, where N is the number of individual elements asked in the request), then deducts it from BV. If BV goes negative, drops the peer, otherwise starts serving the request. The reply message contains a BV value that is the previously calculated BV plus the amount recharged during the time spent serving. Note that since the server can always determine any cost up to MaxCost for a request (and a client should not assume otherwise), it can drop a client without even processing the message if it receives a message while BV < MaxCost because that's already a protocol breach.

On the client side:

The client always has a lowest estimate for its current BV, called BLE. It

  • sets BLE to BL received in Status
  • doesn't send any request to the server when BLE < MaxCost
  • deduces MaxCost when sending a request
  • recharges BLE at the rate of MRR when less than BL

When a reply message with a new BV value is received, it sets BLE to BV - Sum(MaxCost), summing the MaxCost values of requests sent after the one belonging to this reply.

Request ID

Every on-demand request message contains a reqID field, which is simply returned by the server in the corresponding reply message. This helps matching replies for requests on the client side so that each reply doesn't need to be matched against each pending request.

Protocol Messages

Status (0x00)

[[key_0, value_0], [key_1, value_1], ...]

Inform a peer of the sender's current LES state. This message should be sent just after the connection is established and prior to any other LES messages. The following keys are required (value types are noted after the key string):

  • "protocolVersion" P: is 1 for protocol version one.
  • "networkId" P: should be 0 for testnet, 1 for mainnet.
  • "headTd" P: Total Difficulty of the best chain. Integer, as found in block header.
  • "headHash" B_32: the hash of the best (i.e. highest TD) known block.
  • "headNum" P: the number of the best (i.e. highest TD) known block.
  • "genesisHash" B_32: the hash of the Genesis block.

There are several optional key/value pairs which can be set:

  • "announceType" P: set by clients, this field affects the Announce messages of the server. Allowed integer values are:
    • none (0): no Announce messages are sent, i.e. the client is not interested in announcements.
    • simple (1): Default. Announce messages use the les/1 format.
    • signed (2): there is a "sign" key in the key/value list of Announce messages. The associated value is a signature of an RLP encoded [headHash: B_32, headNumber: P, headTd: P] structure by the server's node key.
  • "serveHeaders" (empty value): present if the peer can serve header chain downloads.
  • "serveChainSince" P: present if the peer can serve Body/Receipts ODR requests starting from the given block number.
  • "serveStateSince" P: present if the peer can serve Proof/Code ODR requests starting from the given block number.
  • "txRelay" (no value): present if the peer can relay transactions to the ETH network.
  • "flowControl/BL", "flowControl/MRC", "flowControl/MRR": see Client Side Flow Control

Unknown keys should be ignored by both sides. This allows announcing additional capabilities while staying compatible with past protocol versions.

Announce (0x01)

[headHash: B_32, headNumber: P, headTd: P, reorgDepth: P, [key_0, value_0], [key_1, value_1], ...]

Announce a new chain head and optionally also a change to some of the values announced at handshake. A restrictive change of server capabilities (for example, an increase of "serveStateSince" due to state pruning) should be announced at least 10 seconds prior to actually restricting those capabilities in order to avoid asynchronous problems. Changes to unknown keys should be ignored. Changes to known keys that make no sense lead to disconnection.

Announcing a head with a lower or equal TD than previously announced or a head that the sending node later refuses to honor with a proceeding GetBlockHeaders message (with number and TD also matching) is considered bad form, and may lead to disconnection or reduce the reputation of the sending node.

The field reorgDepth contains the number of blocks to be rolled back from the last head announced by the same node in order to find the last common ancestor of the last and current heaviest chain. Adding this field helps the client to minimize the number of requests and the amount of bandwidth required to fetch new headers.

GetBlockHeaders (0x02)

[reqID: P, [block: {P, B_32}, maxHeaders: P, skip: P, reverse: P in {0, 1}]]

Require peer to return a BlockHeaders message. Reply must contain a number of block headers, of rising number when reverse is 0, falling when 1, skip blocks apart, beginning at block block (denoted by either number or hash) in the canonical chain, and with at most maxHeaders items.

BlockHeaders (0x03)

[reqID: P, BV: P, [blockHeader_0, blockHeader_1, ...]]

Reply to GetBlockHeaders. The items in the list (following the message ID) are block headers in the format described in the main Ethereum specification, previously asked for in a GetBlockHeaders message. The list may be empty if none of the requested block headers were available on the server side.

GetBlockBodies (0x04)

[reqID: P, [hash_0: B_32, hash_1: B_32, ...]]

Require peer to return a BlockBodies message. Specify the set of blocks that we're interested in with the hashes.

BlockBodies (0x05)

[reqID: P, BV: P, [[transactions_0, uncles_0] , ...]]

Reply to GetBlockBodies. The items in the list (following the message ID) are some of the blocks, minus the header, in the format described in the main Ethereum specification, previously asked for in a GetBlockBodies message.

GetReceipts (0x06)

[reqID: P, [hash_0: B_32, hash_1: B_32, ...]]

Require peer to return a Receipts message.

Receipts (0x07)

[reqID: P, BV: P, [[receipt_0, receipt_1, ...], ...]]

Provide a set of receipts which correspond to the block hashes previously asked for in GetReceipts.

GetProofs (0x08)

[reqID: P, [[blockhash: B_32, key: B_32, key2: B_32, fromLevel: P], ...]]

Require peer to return a Proofs message, containing one or more Merkle proofs, each proving the value of index key from the state trie of the given block (if key2 is empty), or the storage value of index key2 from the storage trie referenced in the account at key. If fromLevel is greater than zero, the given number of trie nodes closest to the root can be omitted from the proof.

This message was deprecated in les/2, use GetProofsV2 instead.

Proofs (0x09)

[reqID: P, BV: P, [[node_1, node_2, ...], ...]]

Return a set of Merkle proofs, each consisting of a set of nodes that must be processed in order to access the trie entry value (or prove the absence of an entry) requested in GetProofs.

GetContractCodes (0x0a)

[reqID: P, [[blockhash: B_32, key: B_32], ...]]

Require peer to return a ContractCodes message.

ContractCodes (0x0b)

[reqID: P, BV: P, [value_0: B, value_1: B, ...]]

Provide a set of contract codes which correspond to the block hashes and account keys previously asked in GetContractCodes.

GetHeaderProofs (0x0d)

[reqID: P, [[chtNumber: P, blockNumber: P, fromLevel: P], ...]]

Require peer to return a HeaderProofs message, containing one or more canonical block headers (of block number blockNumber) and corresponding Merkle proofs of the CHT (Canonical Hash Trie) identified by chtNumber. If fromLevel is greater than zero, the given number of trie nodes closest to the root can be omitted from the proof.

This message was deprecated in les/2, use GetHelperTrieProofs instead.

HeaderProofs (0x0e)

[reqID: P, BV: P, [[blockHeader, [node_1, node_2...]], ...]]

Return a set of structures, each containing a block header and a Merkle proof proving the header hash and belonging TD against a given CHT requested in GetHeaderProofs.

SendTx (0x0c)

[txdata_1, txdata_2, ...]

Require peer to add a set of transactions into its transaction pool and relay them to the ETH network.

This message was deprecated in les/2, use SendTxV2 instead.

GetProofsV2 (0x0f)

[reqID: P, [[blockhash: B_32, key: B_32, key2: B_32, fromLevel: P], ...]]

Require peer to return a ProofsV2 message, containing a single (and smallest possible) set of trie nodes that proves for each request the value of index key from the state trie of the given block (if key2 is empty), or the storage value of index key2 from the storage trie referenced in the account at key. If fromLevel is greater than zero, the given number of trie nodes closest to the root can be omitted from the proof.

ProofsV2 (0x10)

[reqID: P, BV: P, [node_1, node_2, ...]]

Return the smallest set of trie nodes required to access the trie entry value (or prove the absence of an entry) requested in GetProofsV2. This set will be called a proof set. Compared to Proofs, this message contains a single list of nodes satisfying all requested proofs. The list shouldn't contain duplicate nodes.

GetHelperTrieProofs (0x11)

[reqID: P, [[subType: P, sectionIdx: P, key: B, fromLevel: P, auxReq: P], ...]]

Require peer to return a HelperTrieProofs message, containing a proof set and optional auxiliary data for each request.

Note: this request is a generalization of the les/1 GetHeaderProofs message. It retrieves Merkle proofs from different types of "helper tries" which are generated for every fixed-length section of the canonical chain. subType identifies the helper trie that is being requested for the section marked by sectionIdx. key and fromLevel are interpreted like in case of proof requests.

If auxReq is greater than zero then auxiliary data is requested too. If auxReq is 1 then the root hash of the specified trie (according to the server) is returned and no trie nodes are added to the proof set. This special request will be required for trustless validation of helper tries. The interpretation of auxReq values greater than 1 is subject to subType.

The following subType integer values are allowed in les/2:

  • CHT (0): request a key from the Canonical Hash Trie. If auxReq is 2 then the belonging header is returned as auxData. key is the block number encoded as an 8-byte big endian. Note that the section size for CHTs has been raised to 32k instead of 4k blocks so for example a sectionIdx of 100 equals a chtNumber of 807 in case of the les/1 GetHeaderProofs message.
  • BloomBits (1): request a key from the BloomBits Trie. In this trie key is 10 bytes long, it consists of the bloom bit index encoded as a 2-byte big endian, followed by the section index encoded as an 8-byte big endian. The returned value is the corresponding compressed bloom bit vector.

HelperTrieProofs (0x12)

[reqID: P, BV: P, [[node_1, node_2...], [auxData_0, auxData_1, ...]]]

Return a proof set and a set of auxData requested in GetHelperTrieProofs. The length of the auxData list equals the number of requests with a non-zero auxReq.

SendTxV2 (0x13)

[reqID: P, [txdata_1, txdata_2, ...]]

Require peer to add a set of transactions into its transaction pool and relay them to the ETH network, then return a TxStatus message containing the status of the sent transactions.

GetTxStatus (0x14)

[reqID: P, [txHash_1, txHash_2, ...]]

Require peer to return a TxStatus message containing the status of the referenced transactions. This message is intended for inquiry about past transactions sent by the client. Note that the server is not required to make every transaction available indefinitely.

TxStatus (0x15)

[reqID: P, BV: P, [[status: P, data: B], ...]]

Return the current status of the sent/queried transactions. Possible status values are:

  • Unknown (0): transaction is unknown
  • Queued (1): transaction is queued (not processable yet)
  • Pending (2): transaction is pending (processable)
  • Included (3): transaction is already included in the canonical chain. data contains an RLP-encoded [blockHash: B_32, blockNumber: P, txIndex: P] structure.
  • Error (4): transaction sending failed. data contains a text error message.

Change Log

les/2 (November 2017)

Version 2 is fully backwards compatible with les/1 and added a few new messages.

  • The "announceType" key was added to the Status message.
  • The BloomBits Trie and associated messages GetHelperTrieProofs, HelperTrieProofs were added to facilitate server-assisted log search. les/1 clients would frequently download large ranges of receipts to search for specific logs.
  • Messages GetProofsV2, ProofsV2 were added to de-duplicate result nodes when requesting multiple proofs at the same time.
  • Messages SendTxV2, GetTxStatus and TxStatus were added to allow querying for past transactions and to enable user-lever error reporting for non-includable transactions at the time of submission.
  • The GetHeaderProofs, HeaderProofs, GetProofs, Proofs and SendTx messages from les/1 are deprecated but still supported in les/2.