Parallelized Executions

[damip]

Parallelized Executions

General idea

The idea is to create a blockchain that runs transactions causing state changes in a parallelized way.
Block producers are responsible for packing the blocks with hints on how to schedule the execution of transactions across THREAD_COUNT parallel execution threads.

Block format

The block format is classical, except for execution hints. For every transaction in the block, the following header is added by the block producer:

[thread_index][gas_offset][gas_usage][access_list]

where:

• thread_index is the execution thread to which the execution of that transaction is bound.
• gas_offset is the CPU time (in terms of gas) at which the execution of that transaction starts in thread thread_index
• gas_usage is the exact amount of gas required for this execution
• access_list is a list of (resource_key, access_type) triplets listing the resources to which the execution accesses. access_type can take one of the following three values:
  • READ_ONLY: the resource is only ever read
  • READ_THEN_WRITE: the resource gets written after being read
  • WRITE_FIRST: the resource gets written without having been read beforehand

Block Execution

Executing a block happens in two passes.

Pass 1: Scheduling

First, the nodes iterate over all the transactions in the block to pre-process them. For each one they:

• check that the same transaction was not already pre-processed in this block
• check that the same transaction was not already executed in previous blocks
• check that thread_index < THREAD_COUNT
• check that gas_offset + gas_usage <= MAX_THREAD_GAS where MAX_THREAD_GAS is a constant defining the maximal amount of gas allocated to each thread
• check that all the previously pre-processed transactions in thread thread_index have both their gas_offset and gas_offset + gas_usage either strictly lower than the gas_offset of the transaction being processed, or both strictly higher than the gas_offset + gas_usage of the operation being pre-processed. This basically ensures that there are no overlaps between executions in a given thread.
• for each one of the already pre-processed transaction (A) belonging to other threads for which the execution times overlap that of the transaction being processed (B), check access list collisions:
  • if the execution of A ends before that of B (if they end at the same gas height, assume that the one in the lower-thread index ends first), for each resource R that is both in A's and B's access list, perform the following checks:
    • if R is accessed as either READ_THEN_WRITE or WRITE_FIRST by A while B accesses R as either READ_ONLY or READ_THEN_WRITE, consider the scheduling check as failed
  • if the execution of B ends before that of A, for each resource R that is both in A's and B's access list, perform the following checks:
    • if R is accessed as either READ_THEN_WRITE or WRITE_FIRST by B while A accesses R as either READ_ONLY or READ_THEN_WRITE, consider the scheduling check as failed

If any of those checks fail, abort the execution of the block transactions: the block producer has not properly scheduled their operations and won't benefit from any of their executions.

If all checks succeeded, for each thread, output the list of transactions to execute sorted by increasing gas_offset.

Pass 2: Executing

As a second step, for each 0 <= thread_index < THREAD_COUNT in parallel:

• for each transaction T in thread_index, sorted by increasing gas_offset:
  • wait for the execution of all transactions in other threads that verify (other.gas_offset + other.gas_usage, other.thread_index) < (T.gas_offset, T.thread_index) to finish
  • Execute T, track its access lists, and generate a list of candidate state changes caused by the execution of T
  • If during the execution of T or at the end of the execution of T the used gas or access lists do not match the declared ones, cancel the execution of T (and only that one). Discard the state changes caused by the execution of T and consider its execution finished (but the transaction not executed). The block producer does not get any rewards from it and the transaction can be re-included in future blocks.
  • If everything went OK:
    • wait for all transactions in other threads for which (other.gas_offset + other.gas_usage, other.thread_index) < (T.gas_offset + T.gas_usage, T.thread_index) to finish executing
    • apply the state changes caused by T to the current state. This includes a fee reward to the block producer. Ideally, part of the fee is systematically burned.
    • consider the execution of T finished (and transaction T as executed, so it can't be re-included in future blocks). If the execution failed for reasons that are not under the control of the block producer (eg. smart contract code panic), the execution is still considered as done ans the fees transferred.

Special case: parallel Argument-Of-Knowledge proof verification

General case

In this section we assume a block containing only transactions each made of a single STARK/SNARK proof verification causing a state update.

In the case of SNARK/STARK proof verification, the fundamental difference with the approach above is that each transaction is a proof verification that accesses resources as inputs and/or outputs, but expects a transaction-specified value for each resource it accesses as input, and outputs transaction-specified values in the resources it writes. A proof verification transaction cannot be executed if the values it uses as inputs do not have the exact values expected by the transaction when its execution starts.

There is only one thing the block producer needs to provide: the absolute order in which all the proof transactions in the block need to be executed one after the other, as if there was no parallelization.

The fact that all the proof verification transactions explicitly specify all the values they use as inputs and outputs allows verifying all the proof transactions of a block in parallel right away, even if they have a sequential execution order in practice.
During proof verification, declared gas limits are checked.

While all proofs are still being verified, validators can simulate applying the changes caused to the state by each proof transaction sequentially, ensuring that each transaction receives its expected input value (the block transactions are dropped if this check fails), and computing the total accumulated state changes caused by the block. This task is very lightweight compared to proof verification and can be done in parallel to proof verification.

The process for block production is more complicated as it requires deducing sequential dependencies among a list of proof transactions in order to deduce a valid absolute order of execution .

Here is an example assuming there are only two transactions T1 and T2 to include in the block. We assume that the two transactions are accessing the same resource R for which the initial state at the beginning of the block is R0:

T1 access to R	T2 access to R	Conditions on values	Constraints caused by the access to R
Read (Ri1)	Read(Ri2)	Ri1 != R0	T1 cannot be included
Read (Ri1)	Read(Ri2)	Ri2 != R0	T2 cannot be included
Read (Ri1)	Write(Ro2)	Ri1 != Ro2	T1 cannot be included after T2
Read (Ri1)	Write(Ro2)	Ri1 != R0	T1 cannot be included before T2
Read (Ri1)	Read(Ri2) && Write(Ro2)	Ri1 != R0	T1 cannot be included before T2
Read (Ri1)	Read(Ri2) && Write(Ro2)	Ro2 != Ri1	T1 cannot be included after T2
Read (Ri1)	Read(Ri2) && Write(Ro2)	Ri2 != R0	T2 cannot be included
Write (Ro1)	Read(Ri2) && Write(Ro2)	Ri2 != R0	T2 cannot be included before T1
Write (Ro1)	Read(Ri2) && Write(Ro2)	Ri2 != Ro1	T2 cannot be included after T1
Read(Ri1) && Write (Ro1)	Read(Ri2) && Write(Ro2)	Ri2 != Ro1	T2 cannot be included after T1
Read(Ri1) && Write (Ro1)	Read(Ri2) && Write(Ro2)	Ri1 != Ro2	T1 cannot be included after T2
Read(Ri1) && Write (Ro1)	Read(Ri2) && Write(Ro2)	Ri1 != R0	T1 cannot be included before T2
Read(Ri1) && Write (Ro1)	Read(Ri2) && Write(Ro2)	Ri2 != R0	T2 cannot be included before T1

(all other cases are deduced by reversing T1 and T2 in the table)

Note that the constraints caused by all value conditions of all resources R accumulate. For example, if access to resource R1 requires T1 to run strictly before T2 and access to R2 requires T2 to run strictly before T1, then it means that there is no suitable order for T1 and T2 and the two transactions can't co-exist in a block.

This example gives an intuition on only 2 transactions but generalizing it to more transactions requires heavier computation.

An idea to reduce the amount of ordering constraints

Sometimes the proven program does not really use the absolute value of an input, but more restricted information about it. In that case, it becomes possible to make the program inputs only depend on that subset of information, and accompany the provable program with a normal (non-provable) pre-processor program that extracts that information.

For example, if the provable program only accesses the resource Ri by checking if Ri > 1000, it could be rewritten as a normal non-proven pre-processor program that outputs the boolean Ri > 1000 and then the proven program simply takes this boolean as input. In that case, even if other transactions modify the absolute value of Ri, as long as it does not change the output of the pre-processor, it won't generate extra ordering constraints.

This could be pushed to its maximum in the following way:

• in the compiler that compiles the provable program, automatically detect the largest possible subprogram (up to a low gas limit to avoid breaking the scalability of STARKS/SNARKS verification) that only manipulates public inputs and constants, and that never interacts with private inputs
• extract that subprogram into a classical non-provable pre-processor program
• make the provable program directly depend on the outputs of the pre-processor only

This has the following consequences:

• less sequencing constraints (see above) allowing better packing of multiple proofs in the same block, even with resource access collisions
• faster proving and smaller proofs (the provable program is smaller, the trace is smaller) without loss of security (because only public input manipulation is extracted in clear)
• faster verification assuming that the extracted part of the program is not big enough to lose the benefits of the scalability of STARKS/SNARKS

Note that something similar could be done for outputs (but for security reasons, this should be done manually by the developer). For example, if a program seeks to increment a value from the state, instead of reading the full value, incrementing it and setting its new value as output, the program could only output the increment "delta" and a post-processor would read the previous value, increment it by "delta" and update it.

Here is an example program:

// proven program: expects fixed values for `public_counter`
def provable_program(public_counter, secret_increment) -> public_counter:
    counter_value = read(public_counter)
    if counter_value > 1000:
        delta = + read(secret_increment)
    else:
        delta = - read(secret_increment)
    new_counter_value = counter_value + delta
    write(public_counter, new_counter_value)

let's imagine that program was run twice in parallel by different people:

• before the block, public_counter = 100000
• one run T1 generated a proof assuming a public input public_counter == 100000 and secret_increment == 1 yielding an output public_counter == 100001
• another run T2 generated a proof assuming a public input public_counter == 100000 and secret_increment == 2 yielding an output public_counter == 100002

As described in the table above, we are in the case T1: Read(Ri1) && Write (Ro1) ; T2: Read(Ri2) && Write(Ro2) with Ri2 != Ro1 ( T2 cannot be included after T1 ) but also Ri1 != Ro2 ( T1 cannot be included after T2 ), hence T1 and T2 cannot co-exist in the same block. Only one of them can be included in the block, the other one will need to be discarded.

Now imagine we split the program in 3 parts:

// not proven program, executed by all validators in their VM
def preprocess(public_counter) -> public_threshold:
    counter_value = read(public_counter)
    public_threshold = (counter_value > 1000)

// proven program: expects fixed values for `public_threshold` and `delta`
def provable_program(public_threshold, secret_increment) -> delta:
    if read(public_threshold):
        delta = + read(secret_increment)
    else:
        delta = - read(secret_increment)

// not proven program, executed by all validators in their VM
def  postprocess(delta, public_counter):
    let new_counter_value = read(public_counter) + delta
    write(public_counter, new_counter_value)

the way this triplet is executed is :

• run preprocess in a VM to generate public_threshold to feed the public input of provable_program
  • if public_threshold ends up being different than the value assumed in the proof of execution of provable_program, then it means that the incompatibility persists
• verify the proof of provable_program that assumes a fixed value for public_threshold and outptus delta
• run postprocess in a VM to consume the delta output of provable_prog and increment the public_counter

Note that those 3 runs can all be done in parallel.

Getting back to our example with T1 and T2, we see that the execution of any one of them does not change the value of public_threshold for the other. This means that the incompatibility is completely lifted and both T1 and T2 can be included in the same block, and in any order !

Note that this example is trivial for illustrative purposes, but in the typical case provable_program is designed to read minimal information from its public inputs (eg. comparison booleans instead of absolute values), perform heavy tasks together with secret inputs, and output minimal information as well (eg. increments instead of new absolute values).