A new version of Mina Docs is coming soon! This page will be rewritten.
Scan State
The scan state is a data structure that allows decoupling the production of transaction SNARKs from block producers to snark workers.
As the block producers no longer have to produce these transaction SNARKs, the block production time may remain constant regardless of the transaction throughput. Additionally, the scan state data structure allows the transaction SNARK proof generation to be parallelized and completed by multiple competing snark workers.
The scan state is comprised of a forest of full-binary trees where each node in the tree is a job to be completed by a snark worker. The scan state periodically returns a single proof from the top of a tree that attests to the correctness of all transactions at the base of the tree.
The block producers include the emitted ledger proof in the blockchain SNARK they generate that proves both the chain's current state is valid and attests to the validity of all transactions included in the snarked ledger.
As a result, block times may remain constant regardless of the transaction throughput, with the scan state capable of adjusting to match a desired transaction throughput.
In a steady-state, when all slots are filled, and all the required proofs are completed, a ledger proof would be emitted every block.
Including transactions
A block producer when constructing a block may include transactions up to the maximum defined by the scan state constants. By including transactions, they can pick up any available transaction fees and pay themselves a coinbase reward. Each transaction they add are transformed to new base jobs and added to the scan state.
For every transaction added, a block producer must include an equivalent amount of completed snark work that corresponds to a sequence of jobs that already exist in the scan state. These completed jobs, when added to scan state, create new merge jobs except when it is for the root node, in which case the proof is simply returned as a result.
The block producer, rather than completing the work themselves, may purchase the completed work from any snark workers from bids available in the snark pool.
Scan state constants
The following constants dictate the structure and behavior of the scan state:
- transaction_capacity_log_2
- work_delay
The transaction_capacity_log_2 constant defines the maximum number of transactions that can be included in a block:
max_no_of_transactions = 2^{transaction_capacity_log_2}
The work delay ensures there is enough time for the snark work to be completed by the snark workers. If there are no completed proofs available, the block producer cannot include any transactions. Using the work delay, the maximum number of trees that may exist in the scan state is defined by:
max_number_of_trees = (transaction_capacity_log_2 + 1) * (work_delay + 1) + 1
The maximum number of proofs that may be included per block is defined by:
max_number_of_proofs = 2^{transaction\_capacity_log_2 + 1} - 1
These scan state constraints ensure that only a single proof can be emitted per block and that the merge node that is to be updated after adding proofs corresponding to its children is always empty.
While the maximum number of transactions may be fixed, this may adjust dynamically such that it adjusts to the transaction throughput. As such, the scan state can handle an unlimited transaction throughput, albeit at the cost of increasing (logarithmically) the transaction proof latency.
Example
Consider a scan state with max_no_of_transactions = 4, and work_delay = 1. Accordingly, this means there can be a maximum amount of work to complete equal to 7 and a maximum number of 7 trees. At genesis, the scan state is empty.
Block 1: A block producer includes four transactions into the scan state labeled B1. These transactions fill the base of the first tree.
Block 2: At the second block, a block producer adds another four transactions (B2). These are added to a second tree, once again filling the base. There are no proofs required due to the work delay of 1 block.
Block 3: At the third block, a block producer adds four B3 transactions to the third tree but must include four proofs for the first tree. As a result of including these completed base proofs, two new M3 merge jobs are created.
B or M indicates a base or merge job, with the number indicating the sequence order of being added to the scan state.
Block 4: For the fourth block, a block producer adds another four transactions (B4) to the base of the fourth tree. They must include four proofs corresponding to the work added in block 2. Again, two M4 merge jobs are created as a result.
Any pending work (displayed in orange) is work for the snark workers to complete. The snark workers submit completed work to the snark pool. Multiple snark workers may complete the work, but only the lowest fee remains in the snark pool that may be purchased by the block producers.
Block 5: In the fifth block, another four transactions are included to fill the base of tree five (B5), and six proofs must be included (B3s and M3s). The M3 merge jobs result in a final pending merge job for the first tree (M5).
Block 6: In the sixth block, another four transactions (B6) are added, filling the base of the sixth tree. Six proofs are included (B4 and M4), and three new merge jobs are created (M6).
Block 7: In the seventh block, a further four transactions (B7) are added by the block producer filling the base of the seventh tree. Seven trees are the maximum number of trees according to the specified scan state constants. The maximum number of proofs (7) are included (B5 and M5). These included proofs create three new merge jobs (M7), and additionally, the top M5 proof is emitted from the scan state.
The proof that is emitted from the first tree is the ledger proof corresponding to the transactions added in block 1. The contents of the tree are then removed to create space for additional transactions.
Block 8: In the eighth block, the block producer adds two transactions (B8) and includes 4 (B6) proofs. These included proofs result in two new merge jobs (M8). Note that only four proofs are required for adding two transactions.
Snark work is bundled into a work package typically containing two workIds, with the exception of the final root proof of a tree. Prorated work for a transaction is two proofs, so this ensures the equality of transactions included and snark work to be purchased.
Block 9: In the ninth block, the block producer adds three transactions (B9). Three proofs (M6) are required for the slots to be occupied in the currently unfilled tree. Four proofs were added in the previous block, and therefore only three more needs to be done (given the maximum work is 7). The M6 proof from tree two is returned as the ledger proof. The third B9 transaction goes into the now empty tree, and two B7 proofs are added.
Block 10: In block ten, the block producer adds four transactions and, as a result, includes seven proofs (B7, M7, and two B8s).
Block 11: In the eleventh block, the block producer adds three transactions (B11) and completes five proofs (B9, B9, M8, M8, M9) in that order. In addition, the M9 ledger proof is returned from the fourth tree.
View the contents of the scan state using the mina advanced snark-job-list command.
Integration with the Snark Pool
Newly added jobs to the scan state are pending jobs for snark workers to complete. Snark workers complete the required transaction SNARKs, submitting bids for their completed work. When a node receives and validates the completed work, they will add to their local snark pool if it is valid and the lowest fee for the required work. The work will also be gossiped to other peers in the network.
While multiple snark workers can complete the same work, only the lowest fee is included in the snark pool.
When a block producer includes completed proofs into a block to offset any transactions they add, they may purchase the corresponding work from the snark pool. For example, continuing the example above consider the next block (12). If the block producer wants to add three transactions, comprising a coinbase, a user payment, and a fee transfer to the snark worker, they need to purchase three completed snark work. This corresponds to the 6 B9, B10s, M9, and M10 (from the seventh tree) proofs, as each snark work includes two workIds.
During the time the block is generated, the snark pool may include completed work in addition to the best bids for the required jobs (0.025, 0.165, 0.1 and 0.5) respectively, in the example).
A block producer will consider the price of available work before selecting transactions. The first transaction a block producer will add will be the coinbase transaction for which there is the coinbase reward. If transaction fees do not cover the snark work fees required for them to be included, they would not be added. A block producer will never purchase work if it is not economical to do so.
In the case where there is no completed snark work available to purchase in the order required, then the corresponding transactions will not be included in a block. This may result in an empty block, but also for the case where no transactions can be added (including a coinbase transaction), there will be no reward for the block producer.
The current snark pool is visible via GraphQL or the CLI via the mina advanced snark-pool command.