Safe transcript initialization API

[adr1anh]

We have until now deferred transcript/challenger initialization to the caller, as this made it easier to synchronize it with our recursive verifier. This left the public facing API for Lifted STARK quite fragile.

The goal is to provide a safe interface for prove/verify which would generate a fresh challenger and observe all necessary parameters and inputs.

This will require many documentation tweaks, ensuring that we point users to the safe method.

The non-trivial changes will probably be:

• Modifying the LiftedAir interface to provide an air_id for a stable ordering.
• Implementing a default mechanism for observing an Air in a transcript.

Context:

I think we should try to avoid putting this burden on the caller.

It is true that for both options, and especially for option A that is relevant to us, committing to the permutation $\pi$ is redundant, but I would rather pay for that redundancy than risk the caller shooting themselves in the foot.

This is a good point. I think we should look into a safe version of the API which properly bounds the transcript to all the required components.

Regarding the absorption of the permutation by default, I agree. It wouldn't be a big change, but needs proper documentation updates.

This could be non-breaking change, so I'd postpone until the next release (issue coming soon).

One question is how hard it would be to make AIR identity part of the statement and backend API, or in other words, to make air_id explicit in the prover- and verifier-side instance specifications. Once we have that, the design could look like this

1. The caller is free to pass the AIRs in any order.
2. Each prover-side instance carries an explicit stable air_id.
3. The backend computes each AIR's log trace height from the witness and sorts internally by (log_height, air_id).
4. From that point on, the backend uses this single canonical order everywhere.
5. The proof header stores the canonical ordered descriptors (air_id, log_height)
6. Those ordered descriptors are themselves absorbed into the Fiat–Shamir transcript, so AIR identity and ordering are backend-bound rather than caller-managed.
7. The verifier reads those descriptors, validates them, reconstructs the same canonical ordering, and then matches the caller-provided AIRs by air_id.

The usual way to treat heterogenous Airs is to use an enum-dispatch trait, so that they all have the same type (avoiding dynamic dispatch). The right approach is probably to add index field to the LiftedAir trait. This would be stable IDs we are looking for, and could be committed to in the backend.

I think this makes it easier to handle a Multi-Air configuration, with the possibility of having optional or duplicate traces (if that makes sense). In any case, this is very doable and we'll want to make sure these rough edges are properly handled.

Originally posted by @adr1anh in #969 (comment)

[adr1anh]

We could include a method LiftedAir::observe_into_challenger(airs: &[Self], challenger: &mut C), which would take the list of Airs in the same order as they are given as instances, and let the implementation decide what to observe. The default could do something like generate the SymbolicAir representation, walk the tree and write the

I would also change the validate function to check that the constraints touch exactly the number of columns accessed in the constraints. This makes sure that an Air cannot have unused columns, and ensures uniqueness.

[adr1anh]

We should wait until we have figured out what layout is needed by the recursive verifier in the multi-trace regime, since we could then use this safe API directly in miden-vm