Stateful Statediff: Optimize Compressor size for nonce diff

[kpp]

Introduction

This issue belongs to #1237.

Nonce has a very nice property: it's always increasing.

In Compressors we have a case for increasing-only diff: Add. Transform(0)/Add(0)/Sub(0) takes 1 byte, however Add(1) takes 2 bytes (metadata + increment itself). Due to the way of how we serialize Compressions we may pack Add(1..=31) into 1 byte instead of 2 bytes. And Add(1..=31) is a very common case for nonces.

The structure of a Compression is metadata byte + packed(U256) data. Metadata byte is: yyyyyxxx where xxx is type and yyyyy is the length of the data. 5 bits for length is enough because we encode U256 len (<= 31 elem length for Add/Sub/Transform, and NoCompression keeps no encoded len because it's assumed to be 32). Because xxx gives us 2^3=8 possible compression types and we use only 4: NoCompression=0, Add=1, Sub=2, Transform=3, there is a room to introduce a new Compression type: AddInlined.

Implementation

AddInlined type id is 4, and it can store an increment [0..31]. When serializing AddInlined we serialize increment=[0..31] inside metadata length (5 bits yyyyy) itself. No additional data(U256) is required to be serialized. Examples:

AddInlined(27) = (27 << 3) + 4 = `11011  100`.
AddInlined(5) = (5 << 3) + 4 =   `00101  100`.
AddInlined(31) = (31 << 3) + 4 = `11111  100`.
AddInlined(0) = (0 << 3) + 4 =   `00000  100`.

Impact

At first glance, it may seem like an insignificant optimization. But when key compression is implemented (#1512) the structure of an Account diff will be: [index(8) diff(balance) diff(nonce) diff(code_hash)].

Example 1

Let's say the tx is to transfer 3050891718 from a balance of 4283200000. The balance after is equal to 1232308282 and it is packed into 5 bytes. Code_hash is not changed so it takes 1 byte. The Account diff will take [8 5 diff(nonce) 1] bytes.

Without this optimization diff(nonce) = Add(1) = 2 bytes, with this optimization diff(nonce) = AddInlined(1) = 1 byte. Before total account diff is 8+5+2+1 = 16 bytes, after: 8+5+1+1 = 15 bytes. So it's a 6.25% improvement for DA footprint.

Example 2

Tx to transfer 181032 from a balance of 4283200000. Balance after = 4283018968. Balance diff = 4 bytes. Account diff size before = 15 bytes. After = 14 bytes. So it's a 6.67% improvement for DA footprint.