Mill, or mill.hoon, is the execution engine for Uqbar. At a high level, it takes the current state of a town (a "shard" of our rollup) along with a set of transactions (referred to in code as eggs) and creates a state transition which can be applied to that town. Here, I will document the specifics of this process and explore implementation choices available to us.
It's important to note that our current implementation of the execution engine can be modified in some ways by Sequencers. The result of an individual transaction must be ZK-verified, that is, the sequencer must generate hints to prove the computation was performed correctly, but the overall state transition can be composed of these results in many ways. A Sequencer therefore has the ability to exclude or order transactions in ways they see fit (with the potential, here, for MEV extraction). The implementation choices made outside of the "must-prove" portion of mill.hoon are made for performance, not validity, and can be iterated on in the future. We must find social/reputational solutions to improve the experience of users in terms of reducing MEV/exploitation by Sequencers, and the permissionless nature of sequencing guarantees viability of such solutions.
mill.hoon can best be read in order -- the file has been structured to follow the logical flow of the code. +mill-all is the call site used by external processes, specifically Sequencers. It takes in a state (a map of id->grain plus a map of addresses->nonces) and a set of eggs to apply to this state in a parallel fashion. To do this, we first sort the eggs by rate, the multiplier set by a caller that is applied to their gas spend to determine the final cost, in Uqbar tokens.
Then, we repeatedly call pass to perform parallel "passes" across the state. Within each "pass", transactions are not permitted create overlapping side effects. A side effect is defined as the alteration, creation, or deletion ("burn") of a grain. Parallel execution here is performed optimistically -- we run +mill on an egg, then check if the resulting side effects overlap with the current state diff of the pass. If they do, we reject the egg and push it to the next pass. Prioritization by gas rate is preserved through passes by reversing the rejected list after its construction in each pass. If the execution of an egg is not successful it is never pushed to a future pass.
+mill processes a single egg (perhaps it should be renamed to hatch?). The egg is first validated for basic correctness: is the signature valid? is the nonce correct? does the attached zigs account contain enough tokens to cover the given budget*feerate?
An error code is returned for each egg based on the result of execution in +mill. This code is inserted into the status field and ultimately is reflected in the state transition which contains the list of completed transactions.
Once the basic validation checks are complete, +mill passes the egg to +work in the +farm door, where actual contract execution is performed along with validation checks of the resulting side effects.
Transactions on Uqbar are paid in zigs, a native token. Zigs is a placeholder name but seems possible as the final term. Zigs will fully comport to a common token standard and exist alongside every other facet of chain state inside grains, so there will be no need for "wrapped zigs" or other such constructions. However, the zigs contract has a special place in the execution engine because gas fees are extracted from accounts and paid to Sequencers directly in mill.hoon. The address of the zigs contract is stored directly in smart.hoon and the contract itself must be audited alongside the execution engine.
The gas fees in a single pass are accumulated and paid in a single state modification at the end of the pass, inside +mill-all. Since this payment only adds to a token balance it cannot be invalidated by a previous state modification, according to the logic in the zigs contract. This means it can be done regardless of the state diffs already present in the pass.
However, gas fees must be extracted from the caller's account inside the state diff for a single egg, because other transactions could potentially make this spend invalid. Thus, the +charge arm is invoked inside +mill for each egg.
Since this means that each egg side effect set is guaranteed to include a change to the grain holding their zigs token balance, +mill-all keeps a set of callers inside each parallel pass and automatically kicks sequential eggs from the same caller to subsequent passes.
All gas payment logic is contained in the +tax arm. +audit confirms whether a caller can afford the maximum cost they've allocated with budget and rate. +charge extracts the calculated fee from their token balance. +pay rewards these fees to the Sequencer's zigs account. Note that if a Sequencer's address does not yet have a zigs account, +pay creates one for them.
An egg is shuttled through +farm, starting in +work, which produces the set of items eventually expected out of +mill: hints for the prover, side effects, events (crow), remaining budget, and an error code.
We run the contract nock acquired in +germinate in +weed. But in order to support continuation calls, we need to wrap this call site in a recursive structure. This is +grow.
+grow takes the data prepared in +incubate and executes the first caller-defined contract call. Then, it either returns the result of that call if it is a rooster (a set of side effects), or performs the calls in the hen (a list of calls, plus any intermediate side effects). Between each of these calls, any intermediate side effects are validated by +harvest to make sure they are legitimate state modifications.
Continuation calls can make use of the intermediate side effects generated by previous calls in the stack. This can be thought of as a depth-first exploration of calls generated by the initial egg. Eventually, the full set of side effects after the complete exploration is returned and validated inside the parallel pass structure.
This arm takes a set of side effects and asserts that they do not break Uqbar's defined rule set. Note that there are three categories of side effects: changes, creations, and deletions. If the rules in +harvest are followed, the changes and creations are merged and returned as a diff. Burns, or deletions, must be tracked separately and removed from state for the next call. If these validation checks fail at any time, whether at the final rooster result of an egg or inside an intermediate hen call, the entire transaction will fail and no side effects will be generated.
mill.hoon should continue to be refined, while being kept as simple as possible. We must also soon determine exactly what portion of the logic must be run through zink so as to prove correctness. All of the logic in +grow must certainly be proven correct, and possibly more. We should also examine grain burns more closely to make sure that they can be safely used to transfer assets between towns. This will probably require logic be inserted into mill that manages the reinstantiation of burned grain on the new town and changes ID/lord/etc accordingly.