Meta: Stateful StateDiff (tracking issue)

[kpp]

Let's define:

• stateless statediff - is a diff with full information about all state changes in the batch.
• stateful statediff - is a diff with full information about all state changes in the batch given the previous state.

In other words:

prev_state: {K -> V} = ...
inputs = ...
new_state: {K -> V} = STF(prev_state, inputs)

stateless_state_diff: {K -> V} = new_state \ prev_state
stateful_state_diff: {K -> V} = [difference(key, stateless_state_diff[key], prev_state[key]))
                                                    for key in stateless_state_diff]

Where difference is defined as:

difference key new null = (key, NoCompression(x))
difference key new prev
  | new < prev = (index(key), Sub(prev - new))
  | new > prev = (index(key), Add(new - prev))
  | new <<< prev = (index(key), Transform(prev))
  | new >>> prev = (index(key), Transform(prev))
  | new == prev = unreachable

See https://docs.zksync.io/build/developer-reference/handling-pubdata-in-boojum for more details.

See https://github.com/code-423n4/2024-03-zksync/blob/main/docs/Smart%20contract%20Section/Handling%20pubdata.md#state-diffs-after-boojum-upgrade for more technical details.

See https://github.com/matter-labs/zksync-era/blob/main/core/lib/types/src/storage/writes/compression.rs.

See https://github.com/matter-labs/zksync-era/blob/main/core/lib/types/src/storage/writes/mod.rs.

Linked issues:

• R&D: Typed StateDiff + compression #1132
• R&D: Port zksync compression for repeated writes (values) #1505
• Stateful Statediff: Implement code_hash Compressor #1510
• StateDiff: collect consecutive state_diffs #1238
• Typed & Structured StorageManager #1247
• StateDiff Postprocessing - in zk or outside of zk? #1248
• Stateful Statediff: Implement Compressors' combination #1508
• Stateful Statediff: RepeatedWrites (compress keys) #1512
• Stateful Statediff: Optimize Compressor size for nonce diff #1520
• StateDiff: diff size calculation update #1820