Adding RAPs

[4l0n50]

This is just one idea and actually while writing I realized it might not work.

The idea is that the verifier could use the right random coins (right values in the authentication paths for commitment openings) when checking Air::evaluate_transition on the ood evaluation frame. The problem could be on the prover's side. When you extend the trace, I'm afraid you need to take in count the degree of the hash function used for computing the random coins. and if the coins are really random it seems it might not work.

[Nashtare]

So that would require using Rescue or another stark-friendly hash function for computing the commitments? Might be impractical at first, though needed if we want to integrate recursion.
When you say the right random coins, you mean the hash of the RAP rows seen as siblings right? I'm having trouble to see why we want the verifier to use them in evaluate_transition()? To check the consistency of the RAP columns shouldn't it be done on the side?

[4l0n50]

But with any hash function it will make the degree grow too much I think.

When you say the right random coins, you mean the hash of the RAP rows seen as siblings right?

yes

I'm having trouble to see why we want the verifier to use them in evaluate_transition()? To check the consistency of the RAP columns shouldn't it be done on the side?

because you should use the right hash when computing the RAPs column. otherwise how do you argue that the RAPs random coins are chosen after the non rap columns are committed

[Nashtare]

I was suggesting that instead of doing so, the prover commits first to the existing trace, then builds up the RAP columns and verifies their consistency along the first trace when checking the commitment consistency with the queried positions, but that falls back to doubling the number of authentication paths in the end, what we wanted to avoid in the first place

[4l0n50]

it seems unavoidable to double the authentication paths

[4l0n50]

And now I see why is unavoidable. Suppose you use variables X_1,...,X_n in you permutation argument (one variable per row). Let's start with n=1. That means that X_1 should be computed as the hash of all the columns over which the permutation argument is performed. But that also means that your commitment/merkle-tree has a subtree computed only from the non RAP columns. Since you also needs to commit to the RAP columns, on a separated tree, this means that opening a row now costs twice.
Initially we tried to have n equal to trace_length - n_copied_values by doing X_i = H(v_i) so that copied values share the same variable. But the problem is that the degree of the permutation argument explodes. Maybe there some reasonable trade off when adding variables