Introduction
In an atomic synchronous composability model, a single transaction may invoke execution in several logic zones (conceptually, smart contracts or rollups). A priori, synchronous composability ambitions appear to be at odds with ZK execution scaling—if provers and verifiers are forced to ZK prove and verify such involved transactions as a whole, the separation to distinct and independent logic zones will effectively collapse to a single monolithic design.
This post outlines a proof of concept for how provers of various logic zones can cumulatively create proofs for multi logic zone transactions, while each is only required to provide proofs limited to executions of code in their respective logic zone. This consists an initial but essential step to potentially prevent the aforementioned collapse.
The main idea is stitching in a coherent manner several heterogenous zk proofs. In that regard, the framework bears some resemblance to works like legosnarks, but unlike those, merely uses Snark in a black box manner.
Subtransactions
In our setting, multiple logic zones execute within a single transaction, sequentially calling on one another, where the initial logic zone and its input arguments are determined by the transaction’s contents. Each zone maintains its own internal state, isolated from others, which can neither read from nor write to it.
The execution trace derived from the above can be broken into continuous segments I refer to as subtransactions. Each subtransaction represents a continuous block of execution in one logic zone and is executed in a strict sequence, with a call stack managing the flow between them. To account for atomicity, the call stack is extended with a special element \bot, that when pushed to the stack denotes that the transaction as a whole has failed.
A subtransaction can be categorized by three elements:
Inputs:
- The internal state of the logic zone executed, at the outset of the subtransaction.
- The input call stack, with the executed logic zone and the current local variables (possibly including a program counter) stored as a pair at the stack’s top. This call stack allows managing proper context switching between the subtransactions.
Outputs:
- The updated internal state of the executed logic zone, after execution of the subtransaction.
- The output call stack, capturing any changes made to the call stack as a result of a call to a new logic zone (update of the top’s local variables, and a push of a new pair to the stack consisting of the called logic zone, and the local variables initialized by the call’s arguments) or a return from one (A pop of the current element of the stack, and an extension of the new top’s local variables with a new variable denoting the return value).
Ordinal Number:
A subtransaction is assigned an index representing its position in the overall sequence of execution. This explicit ordering will be useful for efficiently stitching subtransactions together.
Zero-Knowledge Proof Messages
A proof message is constructed as a tuple
(index, inputs, outputs, \pi),
conceptually representing a subtransaction’s execution.
Namely:
- index: ordinal number i of the subtransaction.
- inputs: The starting inputs, including the executed logic zone’s internal state and the input call stack.
- outputs: The resulting outputs, including the updated internal state and the output call stack.
- \pi: a zero-knowledge proof demonstrating that, given these inputs, a subtransaction with index i correctly produces the specified outputs.
The logic zone responsible for executing the subtransaction, as well as the next logic zone in line, are implicitly identified within the call stack data.
Proofs can be internally valid (i.e. \pi verifies the subtransaction as stated correctly) even if they do not represent a computation that occurs at the transaction’s proper execution trace. Proofs hence need be treated as conditional, and not finalized until they are “stitched” (see below) together with others up to the transaction’s conclusion.
Proving Conditional Proofs
Provers each specialize in a designated logic zone and produce proofs for its corresponding subtransactions.
To generate a proof of a certain subtransaction’s execution, a prover needs to have the inputs of that subtransaction. These intermediary values may depend on the results of subtransactions in other logic zones. Provers could acquire the results of these intermediary computations, in one of two ways:
- Communicate intermediary results of subtransactions with each other via an offchain provers’ network.
- Execute (but not prove) subtransactions of other logic zones in order to derive the intermediary results they require by themselves.
Proofs Stitching
All proof messages, once submitted and verified, are stored in a public database. They are assumed to be submitted in an unordered manner. To finalize a transaction, a sequence of proofs need to be sequentially stitched with each other, in a manner such that the outputs and inputs are consistent, from the initial subtransaction and the global state on all associated logic zones at its inception, until either the stack is empty, or alternatively, a \bot has been pushed to it.
An implementation for stitching is given below.
class TransactionStitcher:
FAILURE_SIGN = '⊥'
class StitchedChain:
def __init__(self, initial_call_stack, initial_states):
"""
:param initial_call_stack: The initial call stack object. It must include a field
'currentLogicZone' that identifies the active logic zone.
:param initial_states: A dict mapping each logic zone to its internal state at transaction inception.
"""
self.proof_list = [] # List of proofs in forward order.
self.latest_writes = dict(initial_states) # zone -> internal state (latest updates)
self.current_call_stack = initial_call_stack # The current call stack.
def __init__(self, initial_stack, initial_states):
"""
:param initial_stack: The initial call stack (an object with a field 'currentLogicZone').
:param initial_states: A dict mapping each logic zone to its initial internal state.
"""
# proofs_by_index maps an index to a dict:
# key: (internalState, callStack) from the proof's inputs, value: the proof.
self.proofs_by_index = {}
self.stitched_chain = self.StitchedChain(initial_stack, initial_states)
self.initial_states = dict(initial_states) # For failure case.
# --- Main Method ---
def submit_proof_message(self, proof):
"""
Processes a new publicly verified proof by storing it by index and attempting
to extend the active forward-growing chain.
Outputs the result of the transaction if it can be fully stitched together
:param proof: A dictionary representing a proof with keys:
- 'index': int, the subtransaction's ordinal index.
- 'inputs': dict with keys:
'callStack': an object with a field 'currentLogicZone',
'internalState': the state of the active logic zone at the start.
- 'outputs': dict with keys:
'callStack': an object (same structure as inputs['callStack']),
'internalState': the updated state after execution.
- 'π': the zero-knowledge proof data (not used in stitching logic).
- 'callstack': an object representing the call stack; it must include a field
'currentLogicZone'.
"""
self.store_proof(proof)
while True:
candidate = self.lookup_candidate()
if candidate:
self.extend_chain_with_candidate(candidate)
if self.is_candidate_ending(candidate):
if self.is_failure(candidate['outputs']['callStack']):
return self.initial_states # Failure: return initial state.
else:
return self.stitched_chain.latest_writes # Success: return latest writes.
else:
break
return None
# --- Helper Functions ---
def is_empty(self, call_stack):
"""
Determine if the call stack is empty.
(Implementation left out – should return True if call_stack represents an empty stack.)
"""
pass
def is_failure(self, call_stack):
"""
Determine if the call stack signals failure (i.e. contains FAILURE_SIGN as the logic zone at the top).
(Implementation left out.)
"""
pass
def is_candidate_ending(self, proof):
"""
Returns True if the proof's output call stack indicates termination:
either an empty call stack (success) or a failure signal.
"""
cs = proof['outputs']['callStack']
return self.is_empty(cs) or self.is_failure(cs)
def get_candidate_key(self, proof):
"""
Returns a tuple (internalState, callStack) from the proof's inputs for dictionary lookup.
"""
return (proof['inputs']['internalState'], proof['inputs']['callStack'])
def store_proof(self, proof):
"""
Stores the proof in the proofs_by_index dictionary.
"""
index = proof['index']
key = self.get_candidate_key(proof)
self.proofs_by_index.setdefault(index, {})[key] = proof
def lookup_candidate(self):
"""
Looks up and returns a candidate proof for the next index using the expected inputs,
or returns None if no candidate exists.
"""
active_zone = self.stitched_chain.current_call_stack.currentLogicZone
expected_state = self.stitched_chain.latest_writes.get(active_zone)
expected_stack = self.stitched_chain.current_call_stack
next_index = len(self.stitched_chain.proof_list) + 1
candidate_key = (expected_state, expected_stack)
return self.proofs_by_index.get(next_index, {}).get(candidate_key, None)
def extend_chain_with_candidate(self, candidate):
"""
Extends the stitched chain with the given candidate proof and updates the chain's state.
"""
self.stitched_chain.proof_list.append(candidate)
self.stitched_chain.current_call_stack = candidate['outputs']['callStack']
active_zone = self.stitched_chain.current_call_stack.currentLogicZone
self.stitched_chain.latest_writes[active_zone] = candidate['outputs']['internalState']
Final Notes
- The precise identity of TransactionStitcher in the ecosystem remains to be finalized. It could be invoked within each logic zone separately, at a single stitching specialized logic zone, or even delegated to the L1. Regardless, it must be aware of the standard used to encode data (inputs and outputs) in proof messages.
- Whole transactions could be proven ahead of time and stitched together in a similar manner. Transactions notably form a dependency DAG between themselves according to their associated logic zones. Two branches of this DAG could potentially advance themselves independently of the other.
- Proof messages of the same logic zones will likely be submitted by provers in batches (likely even including messages from several transactions). Parsimonious encoding of these batches, and correspondingly decoding their contents, warrants more detailed discussion.
- A more general setting could consider parallelizable calls within the transaction. Such intra-transaction parallelism opens up various questions on data races prevention, determinism, and read and write permissions, which at the moment do not appear justified from a practical perspective.
- Challenge for the reader: does a proof message truly must commit to the index of the subtransaction? does it need the state of the stack in its entirety?