Data availability

Introduction

Starknet is a Validity Rollup, which means that after consolidating and proving a set of changes to Starknet’s state, it updates the latest proven state on Ethereum. Alongside the proof, it sends the formatted difference between the previous and new states, also known as state diff, allowing anyone monitoring Ethereum to use this data and reconstruct Starknet’s current state.

State diff format

Pre-v0.11.0

Before Starknet version 0.11.0, state diffs contained information on every contract whose storage was updated, along with additional information on contract deployments. Those differences were sent as part of the calldata of the transaction that registered the proof on Ethereum, in a uint256[] array that included:

  • The number of contracts that were deployed

  • The address and class hash of each deployed contract

  • The number of contracts whose storage was updated

  • For each contract whose storage was updated:

    • Its address

    • A uint256 value that encodes both the number of its storage updates and its updated nonce, defined as follows:

      \[\underbrace{0\cdots0}_{\text{128 bits}} | \underbrace{\text{new nonce}}_{\text{64 bits}} | {\underbrace{\text{# of storage updates}}_{\text{64 bits}}}_{\text{LSB}}\]

    • The key and new value for each storage update

This format is demonstrated by the following example:

[
  2, (1)
  2472939307328371039455977650994226407024607754063562993856224077254594995194, (2)
  1336043477925910602175429627555369551262229712266217887481529642650907574765, (3)
  1, (4)
  2019172390095051323869047481075102003731246132997057518965927979101413600827, (5)
  18446744073709551617, (6)
  5, (7)
  102, (8)
]
1 The number of deployed contracts
2 The address of the first, and only, contract whose state changed
3 The class hash of the first, and only, contract whose state changed
4 The number of contracts whose storage was updated
5 The address of the first, and only, contract whose storage was updated
6 The uint256 value that encodes the number of storage updates and updated nonce of the first, and only, contract whose storage was updated, which equals \(2^{64}+1 = 0^{128}|0^{63}1|0^{63}1\) and therefore:

  • One storage cell was updated

  • The updated nonce is 1
7 The key of the first, and only, storage update of the first, and only, contract whose storage was updated
8 The new value of the first, and only, storage update of the first, and only, contract whose storage was updated

v0.11.0

In Starknet version 0.11.0, state diffs changed to contain information on every contract whose storage was updated and additional information on contract deployments. This information was still sent as part of the calldata of the transaction that registered the proof on Ethereum, in a uint256[] array that included:

  • The number of contracts whose storage was updated

  • For contract whose storage was updated:

    • Its contract address

    • A single 32-byte word that includes its updated nonce and meta information about the storage updates, defined as follows:

      \[\underbrace{0\cdots0}_{\text{127 bits}}| \underbrace{\text{class information flag}}_{\text{1 bit}}| \underbrace{\text{new nonce}}_{\text{64 bits}}|{ \underbrace{\text{# of storage updates}}_{\text{64 bits}}}_{\text{LSB}}\]

      where the class information flag’s value is 1 if the contract was deployed or replaced and 0 otherwise (i.e., there were only storage updates). When set to 1, the new class hash occupies the next entry in the array

    • The key and new value for each storage update

  • The number of classes that were declared

  • The class hash and compiled class hash of each declared class

This format is demonstrated by the following example:

[
  1, (1)
  2019172390095051323869047481075102003731246132997057518965927979101413600827, (2)
  18446744073709551617, (3)
  100, (4)
  200, (5)
  1, (6)
  1351148242645005540004162531550805076995747746087542030095186557536641755046, (7)
  558404273560404778508455254030458021013656352466216690688595011803280448032 (8)
]
1 The number of contracts whose storage was updated
2 The address of the first, and only, contract whose storage changed
3 The 32-byte word that encodes the updated nonce and meta information about the storage updates of the first, and only, contract whose storage was updated, which equals \(2^{64}+1 = 0^{127}|0|0^{63}1|0^{63}1\) and therefore:

  • One storage cell was update

  • The new nonce is 1

  • The class information flag is 0, which means that the contract was not deployed or replaced and therefore the next word shouldn’t be treated as the class hash
4 The key of the first, and only, storage update of the first, and only, contract whose storage was updated
5 The new value of the first, and only, storage update of the first, and only, contract whose storage was updated These two elements, 100 and 200, encode the storage update, where the value of key 100 is set to 200.
6 The number of classes that were declared
7 The class hash of the first, and only, declared class
8 The compiled class hash of the first, and only, declared class

v0.13.1

In Starknet version 0.13.1, sending state diffs to Ethereum changed from using calldata to using either calldata or blobs. Under normal conditions, using blobs is default method, but in extreme situations where blob prices significantly exceed those of calldata, the Starknet sequencer can switch to use calldata instead.

See Data availability with EIP-4844 on the Starknet Community Forum or review an example blob published on Ethereum by the Starknet sequencer for more details.

The format for state diffs remains the same as in version 0.11.0, but the data sent to Ethereum changed to a Fast Fourier Transform (FFT) of the original data. To recover Starknet’s state diff based on blobs or calldata published onchain, an Inverse Fast Fourier Transform (IFFT) on the data must first be performed, afterwhich decoding can proceed as usual.

v0.13.3

In Starknet version 0.13.3, sending state diffs to Ethereum changed from sending raw state diffs to sending compressed state diffs. The employed compression scheme is a simple lookup table variant, where a list of 252-bit field elements is transformed into a (usually smaller) list of 252-bit field elements as follows:

  1. Unique field elements in the data are split into buckets of 15, 31, 62, 83, 125, and 252 bits (i.e. felts that require 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).

  2. Each bucket is packed according to its number of bits (e.g., the 31 bits bucket allows the packing of 8 elements into a single felt).

  3. A list of pointers whose length is the length of the original data is constructed, 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.

    The list of pointers 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.

  4. A list of repeating value pointers is constructed, by adding (bucket_index, index_in_bucket) for every repetition in the original data.

To illustrate the above, consider the following example: Let 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)

The final compressed list packs each bucket and each list individually and adds some necessary metadata.

This simple-to-write compression was chosen over the common Brotli or gzip compressions employed by other chains for similar purposes because the compression must be proven (i.e., either the compression or decompression must be implemented within the Starknet OS, and therefore its efficiency is crucial).

You can find a Python implementation of it in the cairo-lang repository.

To better lends itself to the new compression scheme, as well as allow its construction to be based on the state diff alone, the uncompressed encoding of contract diff headers also changed as follows:

\[| \underbrace{\text{new nonce (if changed)}}_{\text{64 bits}} | \underbrace{\text{# of storage updates}}_{\text{64 bits}} | \underbrace{\text{class information flag}}_{\text{1 bit}} | {\underbrace{\text{updates information flag}}_{\text{1 bit}}}_{\text{LSB}}\]

where:

  • The updates information flag is 0 if the number of updates is less than 256 (and therefore can fit in 8 bits), and 1 otherwise

  • The semantics of class information flag is unchanged (i.e., it indicates whether or not the class was replaced)

  • If the nonce of the contract is unchanged, the value of the new nonce is zero

    This definition can slightly deviate from the previous semantics, if an account contract was modified externally (e.g., via execute_from_outside). In this case, the contract’s nonce is unchanged, yet it appears in the state update (since its storage was updated). Pre-v0.13.3, the current nonce of the account would have appeared although it is unchanged, while in v0.13.3 the value of new nonce is zero. This change helps with making the encoding derivable solely from the state diff itself, without referring to the global state of the chain.

v0.13.4

In Starknet v0.13.4, a second layer, termed stateful compression, was added to the compression of state diffs.

Stateful compression is based on the observation that most parts that were “incompressible” by the previous compression — now termed stateless compression — are storage keys and contract addresses, which can be indexed based on their first occurrence in a state diff, thus encoding them with potentially much less than the full 32bytes.

To achieve this, a new system contract at address 0x2 was introduced, defined as follows:

  • Storage slot 0x0 of the contract is the value of a global counter, initialized to 128 in the beginning of the first block of v0.13.4.

  • Whenever a non-indexed storage key or contract address appears in a state diff, it is mapped to the current value of the counter, and the counter is increased.

    Storage keys that require at most 127 bits and addresses of system contracts (currently, 0x1 and 0x2) are not mapped and continue to be referred to directly.

  • The (uncompressed) state-diff includes the corresponding counter values from the value-to-index mapping rather than the original values.

As its name suggests, stateful compression introduces dependency between state diffs submitted to Ethereum. That is, state diffs of a given block cannot be decoded without knowing the state diffs of the previous blocks. This dependency is only relevant for post-v0.13.4 state diffs, while pre-v0.13.4 state diffs remain self-contained.

Starknet v0.13.4 introduces dependency between state diffs, making post-v0.13.4 state diffs non-decodable without knowledge of previous post-v0.13.4 state diffs.