Missing authentication of a_values in the FRI rounds? about triton-vm

[jan-ferdinand]

Thanks for the question!

The indices are deterministically, pseudo-randomly sampled using the Fiat-Shamir heuristic. The transcript at the point of index sampling contains the commitments to all the polynomials in all the rounds of FRI. Given the indices for round $n$, deriving the indices for round $n+1$ is deterministic as well.

Because the verifier computes the indices itself, no further authentication of the correctness is necessary; in a sense, computing them implies verification they were computed correctly.

[jan-ferdinand]

Perhaps some of the confusion comes from the name of the method enqueue_auth_pairs? The “pair” in that method's name does not refer to (indices, polynomial_evaluations_at_indices) but to (authentication_paths, polynomial_evaluations_at_indices).

[aszepieniec]

The issue that Yuncong is alluding to is (I think) the following:

• In traditional FRI, the colinearity check in every round of FRI is the same: look up the points A, B, C in their respective codewords (or Merkle trees) and verify colinearity.
• In TritonVM's FRI, the colinearity check of intermediate rounds is different: the points A do not need to be looked up because they were computed as C from the previous round.

It is not obvious that this variant as as secure as traditional FRI. However, I don't see how to attack it either.

The case where the TritonVM FRI verifier accepts but the traditional FRI verifier rejects implies A = C but for some reason this value disagrees with some codeword (or Merkle leaf) in an intermediate round. This would imply that the claim is true (the first codeword does have a low degree interpolant) but the malicious prover produces a faulty proof in order to trigger this disparity.

[jan-ferdinand]

Yuncong, apologies for reading your question incorrectly; for some reason, I thought you were talking about the indices, not the partially revealed codewords (or “values”).

Alan has summarized the difference beautifully. In addition to his justification, I can offer this picture of a proof sketch we did back we changed our FRI to what you describe above:

It's possibly not the cleanest way to write things up, but maybe it's convincing enough or can be used to construct something convincing; if the former, I'd be interested in creating the latter.

[jan-ferdinand]

Note that with the merging of #226 (61073e2), the code for FRI looks quite different but behaves as before. Notably, it should be a lot more explicit that the partial codeword “a” (what used to be called “a_values”) of the last round is computed, not received:

triton-vm/triton-vm/src/fri.rs

Lines 293 to 298 in 61073e2

	fn compute_last_round_folded_partial_codeword(&mut self) -> Result<()> {
	self.sample_first_round_colinearity_check_indices();
	self.receive_authentic_partially_revealed_codewords()?;
	self.successively_fold_partial_codeword_of_each_round();
	Ok(())
	}

Furthermore, the code now spells out more explicitly which partial codewords are received and authenticated:

triton-vm/triton-vm/src/fri.rs

Lines 307 to 317 in 61073e2

	fn receive_authentic_partially_revealed_codewords(&mut self) -> Result<()> {
	let auth_structure = self.receive_partial_codeword_a_for_first_round()?;
	self.authenticate_partial_codeword_a_for_first_round(&auth_structure)?;
	let num_rounds_that_have_a_next_round = self.rounds.len() - 1;
	for round_number in 0..num_rounds_that_have_a_next_round {
	let auth_structure = self.receive_partial_codeword_b_for_round(round_number)?;
	self.authenticate_partial_codeword_b_for_round(round_number, &auth_structure)?;
	}
	Ok(())
	}

I'm aware none of this resolves the primary question (“Is it sound to compute the folded partial codeword instead of receiving, authenticating, and verifying it?”) but simply wanted to point out that even though the code has changed drastically, the behavior has not.