perf(precompiles-prover): translate_uint/translate_ec re-traverse shared DAG subgraphs exponentially, causing trace duplication
- 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.