Precompile logging implementation

[adr1anh]

The current precompile handlers are not yet sound since there is no proper mechanism in the VM for keeping track of all precompile calls that were requested from the host. A correct implementation would

1. Get the non-deterministic result from the host (e.g. a keccak hash of data stored in memory).
2. Compute a commitment to the call-data required to recompute the result (e.g. the hash pre-image and claimed output). The pre-image is stored in the AdviceProvider.
3. Log the call by accumulating the call-data commitments
4. Output a commitment to the call-data of all precompile calls, alongside the usual public inputs.
5. Pack call-data in the VM proof, and update the verifier to
   1. Verify the correctness of each precompile call
   2. Recompute the call-data commitment, ensuring it equals the commitment output by the VM

This issue revolves around point 3. and 4. which we are planning on implementing as two kernel procedures.

log_calldata

The implementation itself is rather straightforward. The procedure is called by a precompile wrapper which will have emitted the handler event, and them computed the CALL_DATA commitment. It will then absorb the commitment into a running sponge from which we can extract a commitment to the list of all precompile calls.

use.std::crypto::hashes::rpo

const.PRECOMPILE_SPONGE_PTR=0 #?

#! Inputs: [CALL_DATA, ...]
#! Outputs: [CALL_DATA, ...]
export.log_calldata
	# Load the running capacit 
	padw memloadw.PRECOMPILE_SPONGE_PTR
	# => [C, CALL_DATA]
	
	# Prepare sponge state
	swapw padw
	# => [ZERO, CALL_DATA, C]
	
	# Absorb into sponge and extract next state
	hperm dropw dropw
	# => [C']
	
	# Write the next state to memory
	mem_storew.PRECOMPILE_SPONGE_PTR
end

The main issue with this implementation is the reliance on a well-known address, which may only be written to by this specific kernel procedure. If this address was maliciously overwritten with [0, 0, 0, 0], any previously logged call-data would be discarded and no longer need to be verified.

Given that a kernel is considered "trusted", we can use an address in the kernel memory, and specify that no other procedure may write to it. It does not seem like this is statically enforceable.

The other issue is that any precompile wrapper is now tied to this specific procedure, since it must be explicitly called. We would have to update our standard library whenever this procedure changes (unlikely). If we were to transition to a different way of handling precompiles, the wrappers themselves will likely also need to be updated.

On the other hand, the wrapper implementation expects the logging procedure to behave in this specific way. Therefore, we could even inline the logging procedure, though this makes it harder to enforce any restriction of the sponge state memory address.

For now, the best solution seems to be to make log_calldata a kernel procedure, which should be included if any precompiles are actually called.

Prolog and Epilog

Once all precompiles have been logged/absorbed into the sponge, the VM will have to output the squeezed digest as an additional public output. The natural way to do this is to return it in the final stack. This will require existing kernels and their supporting implementations to change the way they return their outputs. At least 4 elements will be reserved for the call-data commitment, leaving only 12 slots for the application. Existing outputs will need to be compressed using Rpo if they exceed this new bound.

Concretely, a kernel will need to initialize and finalize the sponge. In the prolog, it must ensure the sponge is set to [0,0,0,0]. In the epilog, it will need to extract the final digest and push it to the top of the stack.

We would likely want to provide basic implementations of these procedures that kernel writers can embed in their program. While our VM doesn't have a mechanism/specification to define pro/epilog procedures, the precompile framework now implicitly requires one.

Alternative construction

Many of the issues we describe above could be solved purely at the VM level without any impact on existing applications, using an additional bus interaction.

At a high-level, this would involve adding a log_calldata opcode to the VM. Its signature would be the same as the procedure described above. The capacity portion of the sponge would live in the bus and would be updated whenever the instruction is called.

Under the hood, it would enforce the following constraints with a stack containing the following data.
`[CAP_PREV, CAP_NEXT, CALL_DATA]

• bus.remove([BUS_LABEL, CAP_PREV])
• [_, _, CAP_NEXT] = Perm(ZERO, CALL_DATA, CAP_PREV)
• bus.insert([BUS_LABEL, CAP_NEXT])

First, we would need to load CAP_PREV, and CAP_NEXT from the advice stack. We then remove the previous sponge state from the bus, assert the validity of the next state by invoking the Rpo permutation, and placing the resulting state back into the bus. Finally, the auxiliary capacity words are dropped, returning the stack to its original state.

The bus would be initialized and finalized using variable-length public inputs. The verifier, given some initial and final capacity states CAP_INIT and CAP_FINAL would manually add and remove the messages [BUS_LABEL, CAP_INIT] and [BUS_LABEL, CAP_FINAL].

Overall, this puts the entire logic within the VM and solves most of the issues outlined above

• Precompile handling is independent of the kernel.
• Precompile wrapper procedures no longer do not change if the logging procedure is updated.
• We no longer need a reserved memory address.
• The output stack is not shrunk.
• Prolog and epilog are handled entirely by the verifier.

Another nice feature is that the sponge state can be shared between two VM executions. In the first program, we initialize the capacity as the zero word, but initialize the bus of the second execution with the output state of the first.

The main complications here are

• Allocating one of the remaining VM opcodes to this use case.
• Finding an existing auxiliary column with the capacity for an extra request and response.
• Being able to call the hasher chiplet in this specific way (i.e. ignoring the rate portion of the permutation result).

The main advantage of this approach is that we would be able to work on this feature in the background without affecting downstream users of the VM.

Summary and questions

With this approach, most of the work of managing precompiles is delegated to the kernel. This somewhat simplifies the VM but will require upstream users to adapt their code and make sure their kernels are correctly implemented.

The questions we would like to answer in order to continue are

• Which address in the kernel memory can we allocate specifically to precompiles?
• Should we standardize a mechanism to define prologs and epilogs in kernels?
• How much effort is required by applications to change their stack output representation?
• Would the alternative solution make sense given the current VM design, and current engineering time constraints?

[bobbinth]

Thank you for writing this up! Some comments/questions:

Kernel-based approach

I was thinking that the log_calldata procedure would be slightly different in the following ways:

1. The inputs would be [PRECOMPILE_LABEL, HASH_OF_CALL_DATA]. In the way you've described it, would "precompile label" not be needed? Or would it be somehow encoded in the calldata?
2. The procedure would keep track of logged precompiles as a list in memory. Basically, we'd have something like precompile_segment_ptr and every time log_calldata is called, we'd append the new entry to this list (unless, an identical entry already existed in the list).

Then, in the epilogue, we'd compute the hash of all the precompile calls. Here, the kernel implementer would have two options:

1. Output the hash of the precompile calls via the stack (the naive implementation).
2. Use recursive verifier to verify the proof proving that all precompiles were executed correctly. In this case, no need to output the hash via the stack (this is the longer-term implementation).

So, basically, it would be up to the kernel implementer (e.g., to us in miden-base) to decide which of the approaches to take.

Tracking just the sponge state does allow us to save on memory, but also makes it difficult to handle duplicate requests (e.g., computing the same hash twice) - but maybe I'm missing a way to do this?

Alternative construction

I think this would work, but in addition to the questions you've outlined, a coupe more:

1. Similar to the question in kernel-based construction: would we be able to "de-duplicate" identical requests somehow? Maybe instead of tracking the sponge state, we could track each request individually, and use a logup column?
2. In the longer term approach, when we'd want to verify the pre-compile proof recursively, we'd probably need another instruction to "remove" the final sponge state from the bus, right? Or is there some other way to handle this?

---

To answer some of the questions:

Which address in the kernel memory can we allocate specifically to precompiles?

If we do this statically, we can just assume that address 0 always contains the precompile_segment_ptr for kernels that want to enable precompiles. This can be a simplifying assumption, and we can solve how to allocate the segment dynamically as a part of a broader issue for dynamic memory allocations (don't know exactly how yet).

Should we standardize a mechanism to define prologs and epilogs in kernels?

There isn't really anything we'd need for the prologue - except for initializing address 0 with some value - but this would be done by specific kernels.

For the epilogue, assuming we go with tracking all calls in memory, we'd just need one procedure that computes the hash of the precompile segment - (and that could be done using our existing standard library procedures).

For the longer-term solution, we can probably provide a procedure that does the following:

1. Computes the hash of the calldata log.
2. Emits an event to get the proof for all deferred computations.
3. Calls the recursive verifier to verify this proof.

How much effort is required by applications to change their stack output representation?

I'm not too concerned about this as I'm viewing returning of the hash of the pre-compile log via the stack as a short-term solution (and maybe we could skip this entirely, if we can get to the longer-term solution by mainnet).

Would the alternative solution make sense given the current VM design, and current engineering time constraints?

I think the alternative solution could be very nice, provided we can answer some of the outstanding questions. To re-state some of them:

1. Could we (or do we need to) deal with redundant precompile requests?
2. Could we re-use an existing auxiliary column, or would we need to add a new one? (this would probably be difficult to answer until we have a good idea of how the multi-table design will look like).
3. How many extra instructions would we need? I don't think 1 is enough, but would 2 be sufficient? (if we can do it with 2 extra instructions, I think it would be worth it).
   a. I'm specifically thinking of a longer-term solution here when we'd be verifying the recursive proof in the epilogue and wouldn't need to use variable length public inputs for the aux column constraints.