0xMiden / 0xMiden/protocol

Avoid transaction re-execution during proving

Open
#3,852 0 comments 0 reactions 0 assignees View on GitHub
rust
Dominant language
Rust
Stars
132
Forks
167
Avg merge
1d 23h
Merged PRs (30d)
110

Description

Today a transaction is executed twice: once in [`TransactionExecutor::execute_transaction`](https://github.com/0xMiden/protocol/blob/07608d5bb9c50bdf27c14126d50c5a61322f4984/crates/miden-tx/src/executor/mod.rs#L208) and again in [`LocalTransactionProver::prove`](https://github.com/0xMiden/protocol/blob/07608d5bb9c50bdf27c14126d50c5a61322f4984/crates/miden-tx/src/prover/mod.rs#L106), which rebuilds the processor from `TransactionInputs` and runs the kernel from scratch. Assuming the long-term goal is still to avoid re-execution during proving, the executor should produce the `ExecutionWitness` directly, and the prover should only build the trace and generate the proof from it.

Batches and blocks already work this way: [`ExecutedBatch`](https://github.com/0xMiden/protocol/blob/07608d5bb9c50bdf27c14126d50c5a61322f4984/crates/miden-tx-batch/src/executed_batch.rs#L7-L16) and [`ExecutedBlock`](https://github.com/0xMiden/protocol/blob/07608d5bb9c50bdf27c14126d50c5a61322f4984/crates/miden-block-prover/src/executed_block.rs#L14) carry an `ExecutionWitness` produced by `FastProcessor::execute_for_proving_sync`, so their provers never re-execute. Transactions are the remaining case.

## Blocker

The `ProgramExecutor` abstraction only offers `execute`, which returns an `ExecutionOutput` and not an `ExecutionWitness`. The capability itself is not missing: `FastProcessor` has `execute_for_proving` in an async and a sync version, and the batch and block executors already use it. It is just not reachable through the `EXEC: ProgramExecutor` bound that `TransactionExecutor` is generic over.

## Options

- Introduce two versions of `ExecutedTransaction`, one with an `ExecutionWitness` and one without (an `Option` field is not the way to model this I think), plus a separate `TransactionExecutor` API that returns the witness-carrying variant.
- Always return an `ExecutionWitness` from `ProgramExecutor::execute`. Requires a VM change.

The first option is unattractive because it makes the API more confusing, and there should be one simple execute API. Whether the second option is practical isn't fully clear, but if it is, that would be ideal in my mind.

## Related

- [#3835](https://github.com/0xMiden/protocol/issues/3835) fixes precompile claim deferral in the prover but keeps the re-execution.
- [#2293](https://github.com/0xMiden/protocol/issues/2293) adds an explicit re-execution API for other callers and notes that proving-time re-execution should go away once the VM APIs allow it.
- [0xMiden/miden-vm#3750](https://github.com/0xMiden/miden-vm/issues/3750) consumes a serialized `ExecutionWitness` in a proving service, which assumes the witness is produced at execution time.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.