Prerequisites: The definition and intuition of a transaction’s scope from the point of view of a vprog, roughly: “the historical dependency subgraph a vprog must execute to validate a new transaction”. (see prvs post)
Why do txn scopes require special treatment?
In general, when a composing transaction interacts with a vprog, the vprog must be able to check its validity not only from its own perspective but also from that of other vprogs it interacts with. Typically, this validity check is a special case of the broader requirement that a vprog must maintain independence by executing any transaction that creates direct or indirect dependencies on its state, and that transactions must gas‑pay for this.
A preface note on the importance of gas-payment
Gas‑payment refers to the metering of a transaction’s resource consumption, simply the definition of its resource consumption. This is distinct from the actual transaction fee mechanism in KAS (clarification of this - in a separate post).
A transaction causing a vprog to consume resources without gas‑paying for it is not merely economically, rather indicates a design flaw. It means vprog sovereignty and independence are violated. Therefore, the critical reader of our vprog design should look for bugs of the form “here’s a scenario where vprog vp_i was compelled to execute computation or allocate storage without being gas‑paid for it,” or otherwise be convinced the design is sound. I argue this condition is both necessary and sufficient.
Cross‑vprog scope independence
In our design, a transaction tx_1 gas‑pays vp_j for the computation of scope(tx_1, vp_j). See Michael’s post linked above. Yet it is not immediately clear whether the design guarantees that either (1) vp_i does not need to compute scope(tx_1, vp_j), or (2) vp_i is gas‑paid for it. Indeed, tx_1 could in principle be invalid due to insufficient gas funding for its vp_j‑scope, which (eg due of atomicity) must invalidate it also from the perspective of vp_i. Does this imply a bug?
To ensure soundness, we design for condition (1), by making a transaction’s vp_j‑scope fully determined from the object DAG’s topology, itself determined from transaction declarations. This follows from the definition of scopes. But what guarantees that the object DAG’s topology is unambiguous? We need to ensure that if a transaction declares a read and a write, the implied vertices always materialize and add to the object DAG as expected.
Read failures
Read operations create no dependency, so they can fail only if the transaction aborted, was gas‑drained, or simply did not include the read command. To prevent such scenarios, we enforce a meta‑instruction that fetches and reads all declared read accounts. Thus, a vprog computes a txn’s scope and reads its read-declared accounts before it considers the txn’s actual instructions.
What happens if this meta-instruction is not sufficiently gas-funded by the txn? Such a scenario must be easily discernible from txn+object DAG meta data, and indeed is, by using gas-commitments: The txn specifies in metadata its local gas and scope gas, namely, the max amount of gas its own computation consumes, and the max amount of gas its scope computation consumes from a vprog it writes to. Checking if the txn sufficiently funds all scope computations is now immediate: Traverse its scope wrt any involved (written to) vprog, add all the local-gas fields, and if those are equal to or less than the txn’s scope-gas commitment, the txn is sufficiently funded
Write failures
In prvs design posts we referred to the “state vertex of an account” as the output of the latest txn declaring a write to that account, the maximal vertex in the object DAG with this account ID. This definition is unambiguous from the pov of the vprog owning the account, but could be ambiguous from the perspective of other vprogs that were not required to execute it.
If the txn requires both read and write access then the challenge is addressable via the same construction that disambiguated read success. Namely, the txn is preceded with a meta instruction to read all of the account data, including the to-be-written account. We then define that the txn creates a new state vertex for this account, regardless of whether its write succeeded or failed; a write failure reduces to the new account state vertex holding the same value is its predecessor.
How to treat write-only access
How should write‑only declarations be treated? Michael et al. suggest forbidding it: all writable accounts must also be declared readable (w(x) ⊆ r(x)). Their rationale is that there is only a handful of cases where a txn will want to override the entire data inside an account regardless of its prvs data.
The classic example would be an oracle updating a pair’s price without any dependence on its prvs value. Assuming the oracle’s txn indeed overrides the entire account data, it does not require any read access. With their proposed forcing rule, txns that read the oracle account will need to commit to a large scope: If the oracle updated the account 100 times within one (validity proof) epoch, txns that read oracle data (and write to other vprogs) will need to commit to a scope 100 x larger than needed.
Their counterargument is that oracle-like txns, and specifically those that override the entire account data, are rare and do not justify complicating the design. Such real world considerations are nauseating and should be looked down upon. Instead, I argue we can add an optional field to account ID, representing its sequence index (the nth write to it). This allows write‑only txns to reduce scope size. By extension, txns that read such accounts, too, can reduce their scope by declaring not only the plain account ID they wish to read from but also its sequencing index field (or a lower bound over it!). The txn issuer’s wallet can easily discern this (lower bound on the) index, but other vprogs need not trust it: vprogs execute the reduced txn scope and in case of a write-failure the txn’s value is considered null by all vprog (including the originating one). This “concession” allows third party vprogs to trustlessly process these txns with their reduced scopes. Upon interest I will elaborate on the soundness of this proposal, though something tells me the demand for this would be somewhat limited in scope.
Motivation to enshrine the object DAG in L1
The design ensures txn scopes are inferable from the object DAG topology plus metadata.
In principle, this assertion satisfies the soundness requirement. In practice, however, inferring the object DAG structure can complicate eg by txns that were legally mined yet whose gas-commitments were insufficient to fund their scopes across all involved vprogs.
Therefore, we are currently leaning towards enshrining the object DAG in L1 consensus, by labeling txns with insufficient gas commitments as off DAG (non members of the object DAG), and maintaining in consensus the object DAG’s structure (@michaelsutton @FreshAir08 I think it is not necessary to enforce this on the block or merging block level; the UX will anyways be complicated due to multileaderness).
While such a route will require additional metadata processing, it can be shown to keep L1 agnostic to txn execution and txn (non meta) data, and to incur a negligible overhead to consensus nodes. Nodes will only need to monitor the skeleton of the object DAG, via read-write declarations and gas commitments, and vprogs will be able to rely on L1’s verified data structure in their covenant proofs.
End Notes
-
“vprog” technically refers to the stateless logic owning a set of accounts. It is frequently used also as an intuitive shorthand for stateful nodes of the vprog, nodes that choose to continuously monitor its total state.
-
Our architecture is inspired by Solana, and also Sui, in that txns statically declare dependencies. We ruled out Aptos-like dynamic dependency detection, precisely because txn dependencies, or scopes, are then not discernble without full execution of all vprog txns. This compromises on vprog sovereignty and state growth independence, and reduces the system to one fat L2.
-
Unlike Solana’s batch treatment, we assume an underlying sequencer that prioritizes txns in order. This L1 based ordering prevents deadlocks, cyclic dependencies. Understanding how our “linear” design is still parallelism-friendly is a topic for another day.
-
Also unlike Solana, our design represents account states in a UTXO-like structure. In particular, token transfers which in Solana are writable only would require read-and-write declarations in our system.
-
@FreshAir08 assisted with much of this post but I don’t know that he’s particularly proud of it.