Skip to content

Latest commit

 

History

History
91 lines (64 loc) · 6.88 KB

cip-13.md

File metadata and controls

91 lines (64 loc) · 6.88 KB
Raw
CIP No. Title Author Discussions Status Type Created
13
Employ Big-Endian MPT Keys
Thegaram <th307q@gmail.com>
Final
Spec Breaking
2020-07-27

Simple Summary

Simple Merkle Patricia Tries (or just MPTs) are used to calculate the transactions_root and deferred_receipts_root header fields and to provide the corresponding light node proofs. Currently, these keys are encoded as little-endian. This PR proposes to switch to a big-endian encoding.

Abstract

A block's transactions are stored in an MPT where the key is the block index and the value is the transaction hash. The root of this MPT is stored in the transactions_root header field. A similar approach is used for receipts.

The keys of this MPT are encoded as follows. We first find the smallest number of bytes B that can accommodate all keys. Then, we encode all keys as little-endian byte sequences of length B.

Example: If a block contains 300 transactions, then the keys are 0, 1, ..., 299. We need 2 bytes to represent 299 (B = 2). The keys are encoded as follows:

  0 --> [0x00, 0x00]
  1 --> [0x01, 0x00]
      ...
255 --> [0xff, 0x00]
256 --> [0x00, 0x01]
257 --> [0x01, 0x01]
      ...
299 --> [0x2b, 0x01]

This approach is counter-intuitive and not consistent with storage MPT (delta, snapshot) key encoding.

Motivation

Little- and big-endian key encodings are both reasonable and do not affect the correctness of the protocol. Different encodings might result in different proof sizes, given that the number of transactions in a block is limited.

As these implementation details might be exposed to node developers and potentially to dApp developers as well (if we add a cfx_getProofs RPC), it is better to aim for an intuitive and consistent encoding, which in this case is the big-endian one.

Specification

Going with the previous example of 300 transactions in a block, the encoding would work like this:

  0 --> [0x00, 0x00]
  1 --> [0x00, 0x01]
      ...
255 --> [0x00, 0xff]
256 --> [0x01, 0x00]
257 --> [0x01, 0x01]
      ...
299 --> [0x01, 0x2b]

Rationale

As little-endian keys work just fine, there might not be a consensus about the necessity of this change. The main use here is to make the protocol easier to understand. As we are in phase-2, with a planned hard fork and a new phase launch both on the horizon, I propose we do make this change.

Backwards Compatibility

This change updates the definition of transactions_root and deferred_receipts_root for blocks with more than 256 transactions. As the correctness of the transaction_root is a prerequisite of block validity (see 3.4.3 Well-formedness and 3.4.4 Block Header Validity in the spec), this is a breaking change. Please note that the intended behavior is not reflected in the current version of the specification.

We will enable this change in a hard fork of Oceanus.

Test Cases

The existing unit tests [1] and [2] demonstrate the current behavior. Along with the fix, these are updated as well.

Implementation

The fix is a single-line change. See the corresponding PR here.

Security Considerations

There are no obvious security implications of this change.

Copyright

Copyright and related rights waived via CC0.