Preserving the Same Ledger Under Parallel Execution

Suppose the starting ledger state, the transactions to execute, and their order are fixed. One node executes those transactions one at a time. Another divides the work into tasks and executes several at once. What must remain the same for both nodes to produce the same ledger?

Tasks that start together can finish in different orders. If a later transaction is applied to the ledger first simply because it finishes first, the transaction order or execution results may differ between nodes. But if every transaction must wait for the previous one to finish before it can start, even unrelated computations cannot run together.

The validation structure of Native Programs describes how a transaction makes the state it will use and its proposed changes explicit in advance. That information also helps determine which transactions can execute together. Here, we will look at how to produce the same result as executing transactions one by one in a fixed order, even when their computations finish in a different order.

Split 100 units into two branches, then join them again

A holds 100 units of an asset and wants to send 20 to B and 10 to C. In Nigo, a record called a StateCell can hold an asset's owner and quantity. A transaction expresses a transfer by consuming existing records and creating new ones.

For this example, assume the Native Asset permits direct transfers by its owner and A signs all four transactions. There is no additional issuance or burning, and the fee amount is zero. Assume the block also has enough execution capacity to include all four transactions. To make the dependencies visible, we divide the transfer into four transactions:

1. Split: Consume A's 100 and create a left record holding 60 and a right record holding 40, both owned by A.
2. Send to B: Consume the left 60, give 20 to B, and leave 40 for A.
3. Send to C: Consume the right 40, give 10 to C, and leave 30 for A.
4. Join the remainder: Consume A's remaining 40 and 30 from the two transfers and create a record holding 70 for A.

The final state is A=70, B=20, C=10, still totaling 100. B's 20 and C's 10 remain in place; the final transaction does not consume them. The right 40 created by ① and the left remainder of 40 created by ② have the same quantity, but they are different records.

Fix the candidate transaction order as ① → ② → ③ → ④. Transactions ② and ③ use different inputs created by ①, so both transfers can be computed together once ①'s result is ready. Transaction ④ uses the remainders from both transfers and must wait for both results.

An arrow means that the later transaction needs a result from the earlier one. Transactions ② and ③ can be computed together. The 20 sent to B and the 10 sent to C remain in their own records and do not join at ④.

This example shows a dependency structure that splits an earlier result into two branches and joins them again. It does not mean a wallet must divide every transfer into four transactions this way.

Transactions can be independent even with the same owner

Transactions ② and ③ both transfer A's assets. If we assume they modify the same state just because they have the same owner, we miss an opportunity to execute them together. Nor can we assume they are independent just because their recipients, B and C, differ. Both transactions might try to consume the same input record.

To determine independence, we need to know which records each transaction reads, consumes, or creates. Core, the layer that checks ledger rules for each transaction, interprets the transaction's meaning and provides this access scope. The block execution layer then establishes dependencies between transactions. If a later transaction reads or consumes an earlier transaction's output, it needs that earlier result. If two transactions try to change the same record, or one changes a record the other reads, their order must be respected.

Reading the same record does not by itself create a conflict. Even if ② and ③ read the same asset policy, neither needs to wait because of that shared read as long as neither changes the policy. The two branches in our example also consume and create different asset records. Assume they share no other records they change, including records needed for fee processing.

The situation changes if both transactions try to consume the left 60. An input cannot be used again once consumed, so both cannot succeed. Putting them in order does not make both requests valid. Transactions still need to be validated, independently of whether execution is parallel.

The access scope extends beyond the transfer's obvious inputs and outputs. Asset policies, fee processing, and even a lookup that finds “this record does not exist yet” can affect the result. A Native Program can change fee-related records even when it rejects an operation during execution, so the scope must cover accesses on both success and failure paths. Looking only at the success path is not enough to establish independence.

Read the same base state and collect changes separately

Even after identifying transactions that can run together, we cannot let multiple tasks modify the same store directly. If one task reads a partially applied result from another, their relative execution speeds become part of the transaction's input.

In Nigo's parallel path, tasks in the same group read a fixed base state. Each task reads that state and collects its own changes in a separate temporary workspace. This workspace, which layers uncommitted changes over existing state, is called an overlay. It does not require each task to copy the entire ledger.

In our example, the 60 and 40 created by ① are first applied to the temporary state of the parallel attempt. Transactions ② and ③ then compute against that state together. The task for ② records consumption of the left 60 and creation of A's 40 and B's 20. The task for ③ records consumption of the right 40 and creation of A's 30 and C's 10. Neither modifies the other's workspace or reads the other's intermediate state.

Once both results have been validated, they are collected into the temporary state used by subsequent computations. Only then can ④ use A's two remaining records as inputs to create 70. Making an earlier result available to a later transaction is different from committing that result to the database. The state at this stage consists of provisional results collected for the parallel attempt.

Tasks must not see different execution environments either. The block height and timestamp, fee rules, and rules for interpreting Native Programs are also fixed for execution of the same block. This separates asset and approval state that changes between transactions from the common rules governing execution of the block.

Finishing first does not move a transaction to the front

Suppose ③ finishes before ②. Its result is stored in its assigned position. The order of completion does not change the original candidate order of ① → ② → ③ → ④.

When results computed along the dependencies are applied to the final block state, they follow the fixed candidate order. On the normal path in our example, ①'s split, ②'s transfer to B, ③'s transfer to C, and ④'s join are applied in that order. The computations for ② and ③ can overlap while their effect on the ledger remains the same as sequential execution.

That equivalence means more than matching final balances. The same transactions must be included in the block. Receipts, the execution records that capture success or failure, and events must appear in the same order. The same cells must be consumed and created. The state root, a hash representing the final state, and the block hash must not change with the number of execution tasks or their order of completion.

To check this equivalence, Nigo also has a verification path that executes the same request sequentially and in parallel, then compares the results. This path always adopts the sequential result, regardless of the comparison outcome.

Execution limits make the need for candidate order even clearer. Earlier, we assumed there was enough capacity to include all four transactions. If there is only room for some of them, a transaction cannot earn an earlier place in the block simply by finishing its parallel computation first. The node accounts for cumulative execution usage, or gas, in candidate order and decides which transactions to include or defer. A zero fee amount does not remove the separate limit on execution usage.

A computed result may therefore be left out of the final block. This is another reason not to persist changes as soon as they have been computed in a temporary workspace. Finalization and storage of the adopted block result happen later through the common processing path.

Reassess the plan when actual access differs from expected access

A parallel plan depends on an accurate access scope. Suppose a bug in access analysis or execution causes ② to change the right record, even though the analysis said it would use only the left input. The original decision to compute ② and ③ independently would then be wrong.

Nigo tracks the records read and written during actual execution and checks that they fall within the declared scope. This includes records that a task tried to read but that did not exist. It also checks that a task's returned state changes match its actual writes, that its execution result belongs to the correct transaction, and that the program and block execution rules match those used in the plan. A prior decision that tasks can run together is not enough to accept their results unchecked.

If this validation fails, or a parallel task is interrupted or times out, the entire parallel attempt for the block is discarded. Sequential execution starts again from the original, unchanged state with the same candidate list. Keeping some task results and continuing with the rest could retain changes based on faulty analysis. Returning to the original state lets the existing sequential execution rules determine the result again.

This is not how every transaction failure is handled. For example, if a Native Program returns revert because its conditions for an operation are not met, the operation's changes are canceled, while the prescribed fee changes and a failure receipt can remain as a valid execution result. If that result respects the access scope and execution rules, the program's rejection does not by itself invalidate the entire parallel attempt. Deferring a later transaction because of the block's cumulative gas limit is also a normal result-selection decision.

Falling back to sequential execution is a safeguard for cases where the node cannot trust its internal parallel attempt. It does not, by itself, make a transaction or block invalid. The sequential path's rules determine transaction validity and the final disposition.

Some boundaries still require sequential execution

Nigo currently treats ordinary EVM transactions as boundaries that require sequential execution. It is difficult to determine which storage values a contract will read and which other contracts it will call during execution from an explicit list of cells alone. Operations that change the system's governing state, such as registering an asset or installing or updating a program, are also handled at these boundaries.

When such a transaction appears, the preceding parallel segment is completed and the transaction executes sequentially against the updated state. Later transactions are grouped again using the state that includes its result. A transaction whose access scope cannot be established is not treated as “a transaction that touches no state” and allowed to run alongside others.

If one of these sequential boundaries appeared between ② and ③ in our example, the two transfers would not belong to the same parallel segment. Separate asset inputs do not allow transactions to run together across every boundary in a block.

Native Programs provide a basis for analyzing parallel execution because they receive the state they need explicitly. Their actual access scope and the governing program and policy rules still need to be checked. Using a particular program name does not automatically make a transaction eligible for parallel execution.

Assigning work while preserving the result

The two transfers in our example can be computed together because they use separate inputs, while the join must wait for both results. Each task collects its changes separately against a fixed base state, and its actual accesses and results are validated. Final application follows candidate order, leaving A=70, B=20, C=10 and the corresponding records.

Parallelism here is a way for each node to arrange its computations. Given the same input state and transaction order, the block result must remain the same even when the number of tasks and their completion order differ.

There is more than one way to assign work while meeting those conditions. Must a successor that needs only a fast transaction's result also wait for a slow transaction in the same group? We could instead assign a transaction as soon as it is ready, or let the current worker continue directly with it. The next article expresses these dependencies as a DAG and compares three ways to assign work for the same graph.