enhancement: skip structural witin commitment & PCS

[hero78119]

Purpose

This issue is for further enhancement to skip structural witin commitment & PCS.

Context

In current backend for dynamic non-uniform memory addr witin, it's a well-form MLE, and in lasso we called it structural table

ceno/ceno_zkvm/src/tables/ram/ram_impl.rs

Line 299 in cec7b82

let addr = cb.create_witin(|| "addr");

As verifier can evaluate structural table succinctly without rely on PCS.

Which also imply we can

• skip its commitment
• skip its PCS check

  ceno/ceno_zkvm/src/scheme/prover.rs

  Line 1040 in cec7b82

  // TODO implement mechanism to skip commitment

  )

For now, we already support verifier directly evaluated it.

ceno/ceno_zkvm/src/scheme/verifier.rs

Lines 724 to 735 in cec7b82

	SetTableAddrType::DynamicAddr(spec) => {
	let expected_eval = eval_wellform_address_vec(
	spec.offset as u64,
	WORD_SIZE as u64,
	&input_opening_point,
	);
	if expected_eval != proof.wits_in_evals[spec.addr_witin_id] {
	return Err(ZKVMError::VerifyError(
	"dynamic addr evaluate != expected_evals".into(),
	));
	}
	}

But as its a normal witin, in PCS we still do the commitment, and create/verify its PCS.

Proposed Methodology

One solution is to introduce a new expression type e.g. Structural polynomial type to represent this witin, similar to Expression::Constant or Expression::Fix. With this new type, we can make PCS skip its commitment & evaluation.

Similar idea proposed in #573

A soundness noted

We need to add "rw_hints_num_vars"

ceno/ceno_zkvm/src/scheme.rs

Line 61 in cec7b82

pub rw_hints_num_vars: Vec<usize>,

in transcript, as it's kind of circuit shape.
An add-on to #542

[matthiasgoergens]

Thanks for the detailed writeup.