0xMiden / 0xMiden/miden-vm

perf(precompiles-prover): translate_uint/translate_ec re-traverse shared DAG subgraphs exponentially, causing trace duplication

Aperta
#3,787 2 commenti 0 reazioni 1 assegnatario Rivendicata da @adr1anh Vedi su GitHub
Lingua principale
Rust
Stelle
772
Fork
352
Merge medio
1g 12h
PR unite (30g)
93

Descrizione

### Packages versions

next branch (post-v0.32.0), crates/precompiles-prover

### Bug description

`translate_uint` and `translate_ec` in `DeferredSessionBuilder` perform iterative post-order traversal without a visited/memo set. When the same digest appears as a shared subgraph node (diamond-shaped DAG or any common subexpression), the traversal re-expands the entire subtree beneath it on every visit O(2^D) work for depth D.

`translate_truthy` has the same structural issue with an additional consequence: every re-visit of a shared leaf calls back into `translate_truthy_leaf`, which invokes `self.session.keccak(...)`, `self.session.uint_is(...)`, or `self.session.ec_is(...)`. Each call appends **new rows** to the STARK trace so a shared truthy subgraph of depth D causes 2^D leaf translations, each emitting duplicate trace rows. This produces an incorrect trace and eventual proof failure.

The code already has a TODO acknowledging this gap:

```rust
// TODO: Add translator-level value caches if repeated traversal becomes measurable. Truthy
// handles must remain uncached because they are linear session handles consumed by folds.
```

`TranslatedUint` and `TranslatedEc` are both `Copy` types with no linearity constraint and can be safely memoized in a `BTreeMap` memo table.

Affected: `crates/precompiles-prover/src/deferred/session.rs` `translate_uint`, `translate_ec`, `translate_truthy_leaf`.

### How can this be reproduced?

Build a `DeferredState` where the same uint or EC node digest appears in two different places in the expression tree (a diamond DAG). Call `session_from_deferred_state`. The shared subtree is translated N times instead of once, and for truthy equality leaves, the session trace grows proportionally to re-visits rather than unique nodes.

### Relevant log output

```shell

```

Guida per i contributori

Apri la guida per i contributori

Valutazione

Questa issue non è ancora stata valutata.

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.