Starknet v0.13.3

[FeedTheFed]

Starknet v0.13.3

TL;DR
Introduction
Squashing discount factor
State diff compression
DA format
Blob gas prices on Starknet
Future plans for blob prices on Starknet
Summary

TL;DR

Blob gas on Starknet is now 5x cheaper!

Live on Testnet and expected this week on Mainnet.

Introduction

As mentioned in the fall roadmap update, given the recent rise in blob traffic (see figure below, stabilizing around the target blob-rate), we’re releasing a version that is focused on reducing Starknet’s L1 blob footprint.

This goal is achieved by compressing the state diffs before submitting them to L1. In addition, we will squash more L2 blocks together, reducing the amount of data that reaches L1. Squashing and compression result in a factor of 5x discount for users on data gas (aka blob gas). In the following section we elaborate on squashing, our compression scheme, and why this discount factor is justified.

Squashing discount factor

Up until now, a transaction paid for its contribution to the state-diff as if it was the sole transaction in the block. That is, there was no accounting for state-diff squashing across the block or the sequence of blocks whose associated state update is submitted to L1. For example, if the Starknet sequencer submitted a state update for blocks 100 to 110, and key 1000 was changed by 10 transactions within that block range, then each of the 10 transactions pays full price for the key update, while the sequencer only submits one update to L1.

As of Starknet v0.13.3, users will pay for the expected marginal contribution of their transaction to the blobs sent to L1. This estimate will include a discount factor that, on average, accounts for shared updates within a block range.

Looking at recent Starknet mainnet traffic, squashing justifies a discount factor of ~ 4x. This number corresponds to the average ratio between sent words by the sequencer to paid words by incoming transactions (assuming state diffs are squashed until the squashed diff reaches six blobs worth of data).

State diff compression

As of Starknet v0.13.3, we will submit compressed state diffs to L1. In accordance with the goal of charging the users per their marginal contribution to the state diffs, we’re introducing an additional 25% discount factor on top of the squashing discount, which brings out to 5x cheaper blob gas. The factor is determined by examining the compressibility of recent mainnet state diffs. Note that the true effect of compression is only revealed upon finalizing the state update, while the fee must be determined after each transaction, and hence some kind of estimate is needed. For now, we opted for the simple fixed-rate compression discount.

The employed compression scheme is a simple lookup table variant. We transform a list of 252-bit field elements to a (usually smaller) list of 252-bit field elements as follows:

• Unique field elements in the data are split into buckets of 15, 31, 62, 83, 125, and 252 bits (i.e. felts that take less than 15 bits go into the 15 bits bucket, felts that require 16 to 31 bits go into the 31 bits bucket and so on)
• Each bucket is packed according to its number of bits, for example, the 31bits bucket allows the packing of 8 elements into a single felt.
• We construct a list of pointers whose length is the length of the original data, where the i’th pointer is the bucket of the i’th element if the i’th element is a first occurrence, or a special index that indicates a repetition otherwise. This list can be packed to ~ 1/84 of the original list length since we only need 3 bits to indicate the bucket and we can fit 84 of those into a felt.
• We construct a list of repeating value pointers, by adding (bucket_index, index_in_bucket) for every repetition in the original data

To illustrate the above, consider the following example: Let the indices 0,1, …, 5 correspond to buckets 252, 125, …, 15, and let 6 denote a special bucket of repetitions. For the data list [2^250, 10, 100, 2^63, 2^63+1, 10, 100], we construct the following:

• Bucket 252: [2^250]
• Bucket 83: [2^63, 2^63+1]
• Bucket 15: [10, 100]
• Pointers: [0, 5, 5, 3, 3, 6, 6]
• Repeating value pointers: [(5, 0), (5, 1)] - we have two repetitions, the first for 10 which is the first element in bucket index 5, and the second for 100 which is the second element in the same bucket

Clearly, the buckets, pointers list, and repeating value pointers list allow us to reconstruct the original data. The final compressed list packs each bucket and each list individually and adds some necessary metadata. You can find a Python implementation of this compression in the cairo-lang repository.

Note that we opted for simple-to-write compression and did not choose the common Brotli or gzip employed by other chains for similar purposes because the compression must be proven. That is, either the compression or decompression must be implemented within the Starknet OS, and therefore efficiency is crucial.

DA format

The (uncompressed) encoding of state diffs slightly changes in Starknet v0.13.3. The motivation for the change is two-fold:

• Having an encoding that better lends itself to our new compression scheme by reducing the bit-length of the header felts appearing after every state update.
• Allowing the construction of this encoding to be based on the state diff alone, without accessing the global state of the chain (see more details below)

In Starknet v0.13.2, the diffs of every contract start with the following header felt:

Where flag indicates whether or not the class of the contract was replaced.

In v0.13.3, the header will change to:

Where:

• The semantics of flag is unchanged, it indicates whether or not the class was replaced
• n_updates_len is 0 if the number of updates is < 256 (hence can fit in 8 bits), and 1 otherwise
• n_updates can spread over 8 or 64 bits, depending on n_updates_len
• If the nonce of the contract is unchanged, the value of new_nonce is zero. Note that this slightly deviates from the previous semantics. If for example an account contract (only accounts have non-zero nonces) was modified externally, e.g. via execute_from_outside, then its nonce is unchanged, yet it appears in the state update since some storage variable was updated. In v0.13.2, the current nonce of the account would have appeared although it is unchanged, while in v0.13.3 the value of new_nonce is 0. This change helps with making our encoding derivable solely from the state diff itself, without referring to the global state of the chain.

Note that only the header felt for each contract update changes while all other parts of the encoding remain unchanged, and that blobs sent on-chain will carry a compressed version of this encoding.

Blob gas prices on Starknet

Throughout Starknet 0.13.3, the discount factor will be implicitly reflected in the data gas (aka blob gas) price. That is, no code will change in the execution engine for fee computation, but rather the data gas price on Starknet blocks will be divided by the discount factor. Compared to the blob gas price on Ethereum, the price on Starknet is:

• Smoothed by averaging over the last hour (sampled every minute) to account for the time gap between transaction fee payment and posting the blobs on L1
• Divided by a discount factor of 5 to account for squashing and compression

This may change in the future as the compression discount will take into account the compressibility of the transaction’s data.

Future plans for blob prices on Starknet

This version is by no means the last step in making blob-usage on Starknet as cheap as possible. In Starknet v0.13.4 we plan to introduce another layer of compression, which we refer to as “stateful compression”. The majority of the incompressible parts of the state-diff are storage keys (which are usually the result of hashes and hence require the full 252 bits to represent), contract addresses, and class hashes. Stateful compression is based on the observation that we can index those based on their first occurrence in a state-diff, and refer to subsequent updates by the index rather than the full key or contract address, hopefully saving many bits.

Summary

Thanks to squashing and stateless compression, the next Starknet version reduces blob gas costs by a factor of 5x. Stateful compression is expected to give us a further discount, guaranteeing that Starknet fees remain attractive even with increases in blob consumption on Ethereum.