Optimism Bedrock Wrap-Up Series 4 [ENG]

Analyzing the Block Derivation Process

Onther aims to deliver valuable information for current developers interested in Optimism and the evolution of the Ethereum ecosystem.

Special Thanks to Theo Lee, and Austin Oh for their contributions to this post.

You can check the Korean version of this article here.

Fig. Illustration of Optimism (Source: OP LABS)

This post is the fourth installment of the ‘Optimism Bedrock Wrap-Up Series,’ comprising five planned articles by Onther. We will analyze the block derivation process where a batcher transaction submitted to L1 is transformed back into L2 blocks.

Given the interconnected nature of the series, we recommend reading the articles sequentially for a cohesive understanding.

Series 1. Overview of the Bedrock Upgrade: It provides an overview of the Bedrock upgrade, its components, and the smart contracts deployed within its layers.

Optimism Bedrock Wrap-Up Series 1 [ENG]

Series 2. Key Changes Since the Bedrock Upgrade: In this section, we aim to unravel the substantial changes introduced by the Bedrock upgrade, laying the groundwork for a comprehensive understanding to navigate the upcoming segments of the series.

Optimism Bedrock Wrap-Up Series 2 [ENG]

Series 3. Analysis of the Deposit/Withdrawal Process: We will conduct a step-by-step analysis of the deposit/withdrawal process, unraveling the core code logic within its layers.

Optimism Bedrock Wrap Up Series 3 [ENG]

Series 5. Roles and Behavior of Optimism Bedrock Components: We comprehensively examine the roles and operational logic of Op-Batcher and Op-Proposer as the final components of this series.

Optimism Bedrock Wrap-Up Series 5 [ENG]

The sequencer generates L2 blocks, and the batch submitter is tasked with compressing and dispatching the L2 block information to L1.

Block Derivation

The sequencer generates L2 blocks, and the batch submitter compresses and sends the generated L2 block information to L1. The process of reconstructing the L2 chain based on the information sent to L1 is termed ‘block derivation.’ This enables validators to perform sanity checks on the blocks generated by the sequencer. Currently, a centralized rollup-node operates the network, handling both roles and responsibilities.

Prerequisites for derivation include L2 blocks being generated at 2-second intervals (the block generation time) and ensuring synchronization of L2 block timestamps with those of L1. Synchronization doesn’t merely imply identical timestamps but guarantees a logical chronological order for the generated blocks in each chain. The Bedrock upgrade introduces some concepts crucial for achieving this, which we’ll explain before delving into the code-level analysis.

Sequencing Window

Figure: Example mapping of L1 and L2 blocks for each epoch with SWS set to 3.

In the mapping process, each L1 block is associated with a Sequencing Epoch, and linked to an L2 block. An Epoch encompasses multiple L2 blocks within a specified range. Each Sequencing Epoch is uniquely identified by an Epoch number, and within an Epoch, there is a one-to-one correspondence between an L2 block and an L1 block.

The range of these Sequencing Epochs is termed the Sequencing Window Size (SWS), to specify when each epoch is submitted and synchronized with L1 at specific intervals. Consequently, Epoch N corresponds to L1 block N, and the batch information of L2 blocks for Epoch N is defined between L1 block numbers N and N + SWS. In simpler terms, the L2 block information for Epoch N is stored in the L1 blocks between numbers N and N + SWS. Using the example above, if L2 blocks in Epoch 100 map to L1 blocks, assuming SWS is 3, they only map to blocks 100, 101, and 102.

All L2 blocks within an epoch share the block hash and timestamp of the corresponding L1 block. Additionally, the first block of the epoch includes all deposit transactions initiated through L1’s OpimismPortal.

Fig. Example of the first L2 block transaction in each epoch (source: optimistic.etherscan. optimistic.etherscan)

The provided screenshot illustrates the transaction log of the first block for two distinct L2 block epochs. Examining the 111899054th L2 block, the yellow-highlighted transaction at the bottom is the L1 Attributes Deposited Transaction, while the one just above it is the Relay Message for deposit transaction. The remaining green-colored transactions encompass various other L2 transactions executed within that block.

Contrastingly, in the 111687608th L2 block, there are no deposit transactions or transactions originating within L2, resulting in the creation of only one L1 Attributes Deposited Transaction in that block.

The batch information of L2 blocks related to a specific epoch can be submitted to any L1 block number within the Sequencing Window Size (SWS). To reconstruct an epoch, all the blocks within that epoch must be considered, and their batch information retrieved. In essence, the sequencing window mitigates uncertainty. Without it, the sequencer might append blocks to previous epochs or consume unnecessary resources in tracking specific transactions.

Now, let’s delve into how L2-generated blocks are processed and submitted to L1.

Batch Submission Architecture

Fig. Data transformation process for L2 blocks to be submitted to L1’s BatchInbox

Upon receiving an L1 transaction, the Sequencer generates L2 blocks, assembling multiple of them to form a sequencer batch. This batch is then transformed back into data, taking the shape of a ‘channel,’ which is further split into multiple channel frames. These frames are converted back into batcher transactions, ultimately submitted to L1’s BatchInbox by the batch submitter, completing the rollup process.

The distinction between an L2 block and a batch lies in the fact that an L2 block contains a state root, whereas a batch includes only transaction data such as the L2 block number or timestamp. Essentially, batches offer an efficient and transparent means of referencing from L1 to L2 blocks without the necessity for state information.

Batch Submission Wire Format

Submitting a batch is intricately tied to L2 chain derivation, resembling a reverse derivation. Essentially, L2 chain derivation seeks to reconstruct an L2 block for sanity-check purposes from a batcher transaction submitted to the BatchInbox.

Before delving into the code analysis, let’s explore the overall derivation process using the illustration provided by Optimism.

Fig. Diagram illustrating the block derivation process (Source: github link)

① Illustrates a batcher transaction. In the given example, all frames in the channel are ordered, but generally, they are mixed. However, the order doesn’t affect them as it is before the compression and encoding process. For instance, if A1 and B0 were swapped in the second transaction, it would have no impact on the result.

② The divided channel frames are reordered to reconstruct the channel.

③ Compressed batches are extracted again from the channel.

④ Transactions are extracted from each batch. (While batches and blocks have a 1:1 mapping, empty blocks may be inserted if there's a 'gap' between transactions in L1).

⑤ Represents the L1 attributes deposited transaction, recording information about the L1 block corresponding to the epoch of each L2 block. The first number (99) signifies the epoch number, and the second number (2) indicates the order within the epoch.

⑥ Represents a user-deposited transaction generated from an L1 deposit contract (OptimismPortal) event.

Sanity-Check

I previously mentioned ‘sanity-check’ as the purpose of Block Derivation. Initially, I believed that the Block Derivation process was intended to verify the correctness or detect tampering in previously created L2 blocks. However, since batches are created based on L2 blocks generated by the sequencer, it doesn’t seem logical to verify individual blocks or transactions.

Therefore, it is more understandable to perceive Block Derivation as a process of ensuring that the system hasn’t misconfigured the blocks between the forkchoice state (representing the initial form of the transaction) and the actual batch submitted to L1.
Another aspect is to detect if an L1 chain re-org has occurred, aiding in tracking the finality of the L1 block and providing core functionality to finalize the block type (refer to “Block Derivation in Rollup Nodes” in Series 2 for the finality of L2 blocks). This process ultimately determines whether an L2 block can be reorganized or not. Now, Let’s delve into this checking process in the code.

L2 Chain Derivation Pipeline

In this section, we’ll take a step-by-step look at the actual derivation process, where a batcher transaction submitted to L1 is re-created as an L2 chain through the derivation pipeline architecture.

Fig. Execution priority as opposed to data flow during the derivation pipeline.

In the figure above, the data flow is sequential, starting with step 1, where the batcher transaction submitted to L1 is converted back into L2 blocks. However, the execution priority is reversed from step 8(Engine Queue), which means that if there is no more data to process in each step, it requests the data from the previous step and receives the data to be converted in a step-by-step manner. In other words, function calls are called sequentially from the engine queue as the data is received and converted in each step. Therefore, if you want to know how a step was called, you can see what method was called in the next step, not the previous step.

①. L1 Traversal
The L1 Traversal phase only goes as far as reading the header information for the next L1 block.

Fig. l1_traveral.go/AdvanceL1Block (Source: github link)

AdvanceL1Block checks if the current L1 block hash matches the parent hash of the next L1 block, and if it does not, it means that an L1 re-org has occurred and returns a NewResetError.

If the parent hash matches, employ the FetchReceipts method to retrieve the receipts for the next L1 block. Then proceed to update the L1 system configuration using the UpdateSystemConfigWithL1Receipts function. Finally, update the header of the block to the L1Traversal structure.

②. L1 Retrieval
The L1 Retrieval step involves extracting batcher transaction data from the block header information fetched from L1 Traversal step. Two conditions must be met during extraction:

1. The recipient must match the BatchInbox address.
2. The sender must match the address of the batcher.

Fig. l1_retrieval.go/NextData (Source: github link), l1_traveral.go/NextL1Block (Source: github link)

The NextData function assesses whether to retrieve header information from the L1 block. If information is not available, it triggers the NextL1Block method within L1Traversal.

Conversely, if the block header information is available, it utilizes the OpenData method of dataSrc to access the context, next L1 block ID, and batcher contract address. Extracting batcher transaction data is facilitated by reading this information from the block header.

Fig. frame_queue.go/NextFrame (Source: github link), l1_retrieval.go/NextData (Source: github link),

Furthermore, the NextData method of the L1 Retrieval step is employed within the NextFrame function of the subsequent ‘Frame Queue’ step to transmit data. Similar to the other steps, identifying the method called in the ‘next’ step is straightforward by observing the ‘prev.’ field.

Here are a few more objects that assist in the L1 Retrieval step.

Fig. l1_retrieval.go/DataAvailabilitySource (Source: github link), calldata_source.go/OpenData, Next (Source: github link)

The DataSourceFactory takes as parameters the context.Context, eth.BlockID, and common.Address objects through the OpenData method called above and returns a Datalter. To do this, the OpenData method iterates over the next L1 block ID and batcher contract address and creates a DataSource using the NewDataSource function and the parameters passed in, returning a DataIter.

The Next method is then responsible for returning the next piece of data from the passed-in data. It checks to see if there is any data left to retrieve, if not, it fetches the next L1 block, and if there is, it fetches the next data. This returns the batcher transaction one by one.

③. Frame Queue
The Frame Queue decodes the batcher transaction into a channel frame, which is then plugged into the following step.

Fig. frame_queue.go/NextFrame (Source: github link),

The NextFrame method is also called within the NextData method of the Channel Bank step and is responsible for returning the next frame in the frame queue.

Initially, when no frames are present in the queue, the NextData function retrieves the batcher transaction prepared in the L1 Retrieval step. Subsequently, it decodes the batcher transaction into channel frames and populates them into frames using ParseFrames.

④. Channel Bank
List channel frames sequentially in the channel queue.

Fig. channel_bank.go/ChannelBank, NextFrame (Source: github link),

NextData first reads the data from the channel bank object using the Read method and passes the data to the channel bank. If there is no data left in the channel bank, it uses the channelBuilder’s NextFrame method to load data into the channel bank. The loaded data is collected in the channel queue and processed in FIFO (First In, First Out) order.

Here’s a more detailed look for the Read process.

Fig. channel_bank.go/Read() (Source: github link),

The Read method is responsible for reading the raw data of the first channel in the channel bank. The method first retrieves the most recent channel in the queue and checks for a timeout to ensure that the channel has readable data.

Once the channel is located and ready for reading, it is removed from the channels field and channelQueue field of the ChannelBank. Subsequently, all data in that channel is read using the io.ReadAll function.

If io.EOF is returned during the read process, the Frame Queue step acquires a new channel frame and inserts it into the channel. In such instances, the channel frame structure appears as follows:

Fig. frame.go/Frame (Source: github link)

Frame Structure.

• channel_id: The ID that identifies the channel.
• frame_number: Index of the frame in the channel.
• frame_data: Data of the channel frame.
• is_last: A flag indicating the last frame, 1 if it is the last frame or 0 otherwise.

Fig. channel_bank.go/IngestFrame (Source: github link)

IngestFrame initially examines the frame's channel_id value to determine if a channel with the same ID already exists in the current channel queue. If not, it generates a new channel using the NewChannel function and includes it in the channels field of the ChannelBank. Subsequently, it writes the newly created channel_id to the channelQueue field and adds the frame to the channel queue. Following this, the ChannelBank's prune method is executed.

Fig. channel_bank.go/prune (Source: github link)

The prune method prunes the channel bank so that it does not exceed the maximum size. It first calculates the total size of all the channels in the channels field of the ChannelBank. It then loops until the total size of the channels is less than or equal to the maximum channel bank size.

Each time the loop iterates, the method retrieves the most recent channel_id from the ChannelBank’s channelQueue field, retrieves the channel with that ID from the channels field, and removes that channel from both fields (MaxChannelBankSize: 100,000,000 bytes).

⑤. Channel Reader (Batch Decoding)
Get the channel from the Channel Bank, and go through the decompression and decoding process.

Fig. channel_in_reader.go/NextBatch (Source: github link)

The NextBatch method is invoked within the NextAttributes method of the Payload Attributes Derivation step and is tasked with reading the next batch from the channel. Initially, it checks whether the nextBatchFn field of the ChannelInReader is nil (indicating that the previous batch did not conclude). In such cases, it reads the next set of data and stores it in the channel. Conversely, if the nextBatchFn field is not nil, it locates the next batch in the channel and returns it.

The entity responsible for reading the batch is termed the Reader and is defined as a function. This is because handling the batch involves more than a simple copy; it necessitates decompression and decoding of the data. Accordingly, the BatcherReader function is outlined below.

Fig.channel.go/BatchReader (Source: github link)

The BatchReader function initiates the decompression phase by utilizing the zlib.NewReader function and an io.Reader object. Subsequently, it establishes an RLP reader through the rlp.NewStream function, incorporating the decompression phase to facilitate decompression. The function then proceeds to read each batch sequentially from the RLP reader based on the configured settings. While reading each batch, it undergoes decompression and decoding of the batch data using the rlpReader.Decode method. Ultimately, it returns the result by storing it in a BatchWithL1InclusionBlock object.

⑥. Batch Queue
BatchQueue reorders the next batch based on the timestamp and whether the header is safe/unsafe.

Fig. batch_queue.go/BatchQueue (Source: github link)

BatchQueue Structure.

• log: Used to log messages.
• config: An object that represents the shape or configuration of the BatchQueue.
• prev: A NextBatchProvider object, used to provide the next batch.
• origin: An eth.L1BlockRef object representing the reference of the L1 block.
• l1Blocks: Represents the L1 blocks.
• batches: A field that maps uint64(batch index) keys to BatchWithL1InclusionBlock object slices.

Fig. batch_queue.go/BatchQueue (Source: github link)

The NextBatch method within a BatchQueue structure is accountable for providing the next batch of data from the BatchQueue. Initially, it examines whether the origin of the BatchQueue object is later than the origin of the L2 safe head. This condition implies that the batch being processed is newer than the timestamp of the safe L2 head. If this holds true, it is deemed a safe batch, and the origin is advanced to load additional data into the batch queue.

⑦. Payload Attributes Derivation
Transform the batch imported in the preceding step into an instance of the Payload Attributes structure. Payload attributes encompass transaction and other block inputs, such as timestamp, fee, recipient, etc., which should be incorporated into the block.

Fig. attributes_queue.go/NextAttributes (Source: github link)

The NextAttributes method verifies whether the AttributesQueue's batch field is nil. If it is, it invokes the NextBatch method within the prev field to fetch the next batch.

Subsequently, it calls the createNextAttributes method of the AttributesQueue object to generate the payload attributes. This method receives parameters such as context.Context, BatchData, and eth.L2BlockRef, and returns PayloadAttributes.

Then, the createNextAttributes method then proceeds to create the payload attributes for the upcoming L2 block.

Fig. attributes_queue.go/createNextAttributes (Source: github link)

The createNextAttributes method is responsible for generating the next set of payload attributes from the batch data and L2 safe head. Creating new payload attributes is akin to adding a new queue to the AttributesQueue. The builder object in AttributesQueue utilizes the PreparePayloadAttributes method to obtain the payload attributes for the next L2 block. Subsequently, it captures the number of transactions and the timestamp information of the batch within the corresponding PayloadAttributes object. Finally, it generates and returns a new PayloadAttributes object.

⑧. Engine Queue
Transmit the payload attributes data from the preceding step to the execution engine for the creation of L2 blocks.

Fig. Rollup Node and Engine API interaction architecture (Source: github link)

To engage with the Execution engine, various APIs are employed, each delineated below:

• engine_forkchoiceUpdateV1: This API updates the chain head if it differs and directs the engine to construct an execution payload if the payload attributes are not null.
• engine_getPayloadV1: This API retrieves the previously constructed new execution payload.
• engine_newPayloadV1: This API executes the created execution payload to generate a block.

engine_queue.go/Step (Source: github link)

The Step() method utilizes several fields in the EngineQueue to guide the block generation process through the following steps:

1. If the needForkchoiceUpdate field is ‘true’, invoke the tryUpdateEngine method of EngineQueue to update the engine.
2. Check if the length of the EngineQueue’s unsafePayloads field is greater than zero, call tryNextUnsafePayload to process the next unsafe payload.
3. Ensure that the EngineQueue’s safeAttributes field is not nil. If it is, invoke the tryNextSafeAttributes method to process the next safe attribute.
4. Invoke the origin of the prev field to set the newOrigin variable to the origin of the previous block. Subsequently, call the verifyNewL1Origin method to confirm that the origin of the L2 unsafe head matches newOrigin. This is a verification process to ensure that the engine queue is processing the correct order of blocks for the new queue.
5. Call postProcessSafeL2 to validate that the latest L1 block being created aligns properly with the last L2 safe head.
6. Finally, execute tryFinalizePastL2Blocks to finalize the synchronized L2 blocks up to the current point and invoke NextAttributes to proceed with the next safe attributes.

Then, when a fork choice update occurs, the tryUpdateEngine method is executed to initiate a synchronization operation. This happens in the following situations.

• Updating an L2 block to the ‘safe’ state.
• Updating an L2 block to the ‘finalized’ state.
• Resetting the pipeline.

engine_queue.go/Step (Source: github link)

The tryUpdateEngine method initially verifies that the L2 unsafe head differs from the hash of the engine synchronization target. If they match, it constructs a ForkchoiceState object using the head block hash, safe block hash, and finalized block hash of the EngineQueue.

Subsequently, the ForkchoiceUpdate method is invoked on the engine field to update the engine to the current ForkchoiceState. The data requiring synchronization is validated, and the state of the engine field is synchronized with the L1 block. This can be conceptualized as managing the queue within the engine queue and processing transactions.

Next, if the most recent unsafe head retrieved from the L1 block precedes the safe head, the existing unsafe L2 chain is examined to determine if it aligns with the L2 input derived from the L1 data, and subsequently merged.

engine_queue.go/trySafeNextAttributes (Source: github link)

The tryNextSafeAttributes method attempts to retrieve the next safeAttributes from the engine queue and process it. Initially, it checks whether the safeAttributes field is ‘nil’ and also verifies if the EngineQueue's safeHead field is equal to the parent of the safeAttributes field. If the safeAttributes field is not ‘nil’ and the safeHead field is equal to the parent, it indicates that the unsafe head is ahead of the safe head, prompting a coalescence. In this context, merging implies that the most recent unsafe head matches the safe head, and this unsafe head is also considered safe, subsequently becoming the new safe head.

engine_queue.go/tryNextUnsafeAttributes (Source: github link)

The tryNextUnsafePayload method executes the following sequence of actions:

• It invokes Peek on the unsafePayloads field of EngineQueue to retrieve the most recent unsafePayload in the engine queue.
• Subsequently, it examines whether the number of blocks in that unsafePayload is greater than or less than the number of safe heads or unsafe heads. This verification checks for potential errors in making the unsafePayload an L2 block in the current queue.
• In the absence of errors, it calls NewPayload in the engine field to incorporate the most recent unsafePayload into the engine. The NewPayload method requires a context.Context and a payload as parameters, and it returns an *eth.Status and an error object.

engine_queue.go/tryNextUnsafeAttributes (Source: github link)

In the absence of errors during the insertion process, it assembles a ForkchoiceUpdate object using the head block hash, safe block hash, and finalized block hash as arguments. This object is then utilized to update the fork choice by invoking the ForkchoiceUpdate method of the engine field.

Ultimately, the ForkchoiceUpdate method requires context.Context, *eth.ForkchoiceState, and *eth.ForkchoiceUpdateOpts as parameters. It returns an *eth.ForkchoiceUpdateResult, contributing to the recreation of the L2 block.

Closing thoughts

In summary, we’ve delved into the process of transforming a batcher transaction submitted to L1 back into an L2 block, conducting sanity-checks at each step and examining the block type for the finality of the L2 block. Despite the introduction of new concepts, the fundamental objective remains the same: taking a batcher transaction submitted to L1 and reconstructing an L2 block — assembly in reverse of disassembly. Optimism adopts this approach to ensure data validity, with validators double-checking the process of submitting the L2-generated block to L1.

The upcoming fifth and final installment of the Optimism Bedrock Wrap Up series will comprehensively explore the roles of Op-Node, Op-Batcher, and Op-Proposer and their functionalities.

Reference:

https://blog.oplabs.co/heres-how-bedrock-will-bring-significantly-lower-fees-to-optimism-mainnet/

OP Mainnet Transactions Information | Optimism

OP Mainnet Transactions Information | Optimism

optimism/specs/derivation.md at develop · ethereum-optimism/optimism

optimism/op-node/rollup/derive/l1_traversal.go at develop · ethereum-optimism/optimism

optimism/op-node/rollup/derive/l1_retrieval.go at develop · ethereum-optimism/optimism

optimism/op-node/rollup/derive/calldata_source.go at develop · ethereum-optimism/optimism

optimism/op-node/rollup/derive/frame_queue.go at develop · ethereum-optimism/optimism

optimism/op-node/rollup/derive/channel_bank.go at develop · ethereum-optimism/optimism

optimism/op-node/rollup/derive/frame.go at develop · ethereum-optimism/optimism

optimism/op-node/rollup/derive/channel_in_reader.go at develop · ethereum-optimism/optimism

https://github.com/ethereum-optimism/optimism/blob/develop/op-batcher/batcher/channel.go?source=post_page-----6174256ea59b--------------------------------

optimism/op-node/rollup/derive/batch_queue.go at develop · ethereum-optimism/optimism

optimism/op-node/rollup/derive/attributes_queue.go at develop · ethereum-optimism/optimism

https://gamma.app/public/Optimism-Bedrock-1vcsrk7e5q1lcqu?mode=doc

optimism/op-node/rollup/derive/engine_queue.go at develop · ethereum-optimism/optimism