Expand description
Compact delta encoding and reconstruction for Ethereum validator balances.
This module computes compact binary deltas between two validator balance snapshots and applies those deltas to reconstruct the target snapshot.
The encoding is specialized for Ethereum beacon-chain balances, where most validators either retain the same balance or change by a relatively small amount between consecutive states.
§Encoding
For each balance in the portion shared by the base and target snapshots, the delta records one of four states using a packed two-bit tag:
SET_NO_CHANGE— the balance is unchanged;SET_TO_ZERO— the target balance is zero;SET_TO_DIFF— the target is reconstructed by applying a signed difference to the base balance;SET_TO_TARGET_VALUE— the target balance is stored explicitly.
Changed balances whose difference fits in an i32 are normally encoded as
signed differences. The most frequently occurring difference is selected as
the BalancesDiff::mode, and encoded differences store only the
difference relative to that mode.
Signed corrected differences are encoded as zig-zag integers followed by a variable-length integer encoding. This makes small and frequently occurring changes inexpensive to store.
Differences that do not fit in an i32 are encoded as explicit target
values.
Balances that exist only in the target snapshot are stored in
BalancesDiff::appended_balances.
§Two-pass encoding
diff_balances_iter cannot require its input iterators to implement
Clone. It therefore performs the diff in two logical passes:
- the common portion of the iterators is consumed into a compact intermediate list of changes;
- the statistical mode is selected and the changes are encoded.
Any remaining items in the target iterator are treated as newly appended balances.
§Iterator API
diff_balances is the convenience API for contiguous balance slices.
diff_balances_iter is intended for consensus clients whose balances are
stored in persistent lists, trees, or other non-contiguous structures.
The iterator API avoids requiring the caller to materialize the complete balance registry as a flat buffer.
§Reconstruction
apply_balances and apply_balances_iter mutate the supplied balance
collection in place.
The supplied collection must represent the base snapshot from which the delta was generated. After successful application, it contains the target balances.
Existing balances are updated in place. Target balances that extend beyond the base snapshot are appended from the delta.
§Complexity
diff_balances and diff_balances_iter run in:
O(n)where n is the number of balances in the common portion of the snapshots.
Delta generation additionally requires storage proportional to the number of changed balances:
O(k)where k is the number of changed balances.
apply_balances and apply_balances_iter run in:
O(n + a)where n is the number of balances represented by the tag vector and a
is the number of appended balances.
Reconstruction operates in place and does not require allocating a second balance buffer.
§Serialization
BalancesDiff is designed to be serialized using rkyv and can then be
passed to a general-purpose compressor such as zstd.
The delta representation itself is independent of the serialization and compression layer.
§Delta validity
Applying a delta assumes that the supplied base collection corresponds to the base snapshot used to create the delta. The application functions do not independently verify the original balance values.
In particular, a SET_TO_DIFF entry applies its decoded difference to the
current value in the supplied target collection. Applying the same delta to
a different base snapshot therefore does not generally produce the intended
target snapshot.
Functions§
- apply_
balances - Applies a balance delta to a contiguous balance vector in place.
- apply_
balances_ iter - Applies a balance delta to a mutable balance collection in place.
- diff_
balances - Computes a compact balance delta between two contiguous balance slices.
- diff_
balances_ iter - Computes a compact balance delta between two balance iterators.