Contact: Aurel
The goal of this “Bus” design is to provide efficient lookups and cross-circuit calls, but also a flexibility in circuit design that allows high resource utilization.
Indeed, the target application is Scroll’s zkEVM. A VM must support any stream of instructions, where each instruction needs many lookups as well as calls to sub-circuits, but different ones. Suppose lookup arguments are allocated to support the worst-case of each opcode for each table. This is very costly, while the lookups are under-utilized by most instructions.
With a bus approach, any given location in a circuit is able to dynamically lookup into any table, or to call any circuit, or to answer a call. This makes the current design more efficient, and it enables an even more modular design in the future.
Meanwhile, the current Plookup protocol uses a lot of witness, which can be replaced with a lighter method (~75% less witness).
Moreover, a call to a sub-circuit is a one-to-one communication, which does not need the lookup effect (one-to-many). Also called a shuffle. This is cheaper because there is no need to witness the multiplicities.
Finally, the current lookup approach is limited by the column height. Instead, multiple sub-circuits for the same function can be connected to the same bus, to scale the capacity of this function. E.g., there can be multiple Poseidon circuits. Similarly, a lookup table can be larger than a column, by splitting it into chunks, all available on the same bus.
Semantics first:
A $message$ represents a true fact, to be communicated from the circuit or table that verified it, to the circuit that needs it to be true. The encoding of messages can be very flexible, like so:
Message structure:
Example, range check lookup:
Example, call to a hasher circuit:
$[TYPE\_TAG, field_0, field_1, ...]$
$[BYTE, 12]$
$[HASH, inputs, output]$
Messages can be sent one-to-one, or they can be entries of a lookup table. A bus operation is represented by a $count$ like so:
Receive: $count = -1$
This means to receive a message, with the expectation that it carries a true fact. This can be a cross-circuit call answered by a Send, or a lookup query answered by a Send-To-Lookups.
Send: $count = 1$
This means to send a message, with the responsibility to verify that it states a true fact, and the expectation that it is received exactly once somewhere else.
Send-To-Lookups: $count = number\ of\ receives$
This means the message is an entry of a lookup table, with the responsibility that it is a true fact. It can be received any number of times. This number is the $count$, set by the prover as advice. Also called multiplicity.
No-Op: $count = 0$
This means there is nothing to send or receive at this location. The message does not have to be valid. Therefore, operations can be conditional.
Example: the Execution circuit calls the State circuit.
Example: the Execution circuit lookups into a fixed table.
The bus operations are consistent if the following holds:
$$ \sum_i^N \sum_k^K \frac {count_{i,k}} {compress_\beta(message_{i,k})} = 0 $$