rearrange queried_values_by_layer for merkle.

[reviewable-StarkWare]

This change is 

[ilyalesokhin-starkware]

I passed test_wide_fib_prove_with_blake

[ilyalesokhin-starkware]

The merkle verifier takes queried_values_per_log_size rather then queried_values_per_column

I think I can reduce the structure further and just concatenate all the log sizes

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/verifier.rs line 148 at r1 (raw file):

                                .ok_or(MerkleVerificationError::ColumnValuesTooShort)
                        })
                        .collect::<Result<Vec<_>, _>>()?

The main benefit is coming from removing the reorganization here.

Code quote:

                    layer_queried_values
                        .iter_mut()
                        .map(|(_, ref mut column_queries)| {
                            column_queries
                                .next()
                                .ok_or(MerkleVerificationError::ColumnValuesTooShort)
                        })
                        .collect::<Result<Vec<_>, _>>()?

[ilyalesokhin-starkware]

crates/prover/src/core/fri.rs line 728 at r1 (raw file):

                .flatten()
                .copied()
                .collect();

Is there way to get the decommitment_values in the order that I want? instead of the reorg below?

Code quote:

            // Prepare values in the structure needed for merkle decommitment.
            let column_decommitment_values: SecureColumnByCoords<CpuBackend> = sparse_evaluation
                .subset_evals
                .iter()
                .flatten()
                .copied()
                .collect();

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/prover.rs line 52 at r1 (raw file):

            .into_iter()
            .sorted_by_key(|c| Reverse(c.len()))
            .peekable();

Actually, the assertion above is currently not true in general.

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/prover.rs line 52 at r1 (raw file):

Previously, andrewmilson (Andrew Milson) wrote…

Maybe we can remove the comment on the function "This function will panic if the columns are not sorted in descending order"

lol, didn't see it.

I actually do want to sort the columns in descending order but I'm not sure when to do it.

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/verifier.rs line 145 at r3 (raw file):

                } else {
                    // Otherwise, read them from the witness.
                    (&mut column_witness).take(n_columns_in_layer).collect_vec()

FYI, this is currently unreachable with n_columns_in_layer != 0 (ignoring tests)

Code quote:

(&mut column_witness).take(n_columns_in_layer).collect_vec()

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/verifier.rs line 149 at r2 (raw file):

Previously, andrewmilson (Andrew Milson) wrote…

Remove the assert? This branch is unreachable

Take can yield fewer elements than requested. https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.take

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/verifier.rs line 149 at r2 (raw file):

Previously, andrewmilson (Andrew Milson) wrote…

I mean the assert the line before should be removed

right, thanks.

[codecov-commenter]

Codecov Report

Attention: Patch coverage is 98.91304% with 1 line in your changes missing coverage. Please review.

Project coverage is 91.72%. Comparing base (c2ef3ac) to head (44550e7).

Files with missing lines	Patch %	Lines
...rates/prover/src/constraint_framework/component.rs	0.00%	1 Missing :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## dev #902 +/- ## ========================================== + Coverage 91.69% 91.72% +0.02% ========================================== Files 93 93 Lines 13164 13127 -37 Branches 13164 13127 -37 ========================================== - Hits 12071 12041 -30 + Misses 980 973 -7 Partials 113 113 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/prover.rs line 160 at r2 (raw file):

        // Reverse the queried values by layer so that queried_values_by_layer[i]
        // corresponds to the quiries for the layer whose log size is i.

Removed.

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/prover.rs line 52 at r1 (raw file):

Previously, andrewmilson (Andrew Milson) wrote…

What are you thinking at this stage? I thought it's easier to push the responsibility to the caller

I think we can skip the sorting in the Verifier if we know that the columns are sorted.

I'm not sure we will benefit from moving the sorting elsewhere.

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/verifier.rs line 57 at r4 (raw file):

Previously, andrewmilson (Andrew Milson) wrote…

Can make `MerkleProver::decommit` link to the function. Also should "Returns `Ok(())` if the decommitment is successfully verified." come before `# Arguments`?

I don't know our documentation convention. here returns is at the end: https://github.com/starkware-industries/stwo/blob/fee260c03cb8024e318bda6ff43577f3cba6fc1c/crates/prover/src/core/vcs/prover.rs#L75

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/verifier.rs line 188 at r4 (raw file):

Previously, andrewmilson (Andrew Milson) wrote…

Nit. The standard library uses lowercase without trailing punctuation for error messages. I tried to use the same in FRI. Perhaps we can apply same style to this type to be consistent?

The lack of . is inconsistent with the other errors.

[ilyalesokhin-starkware]

crates/prover/src/core/pcs/quotients.rs line 138 at r4 (raw file):

Previously, andrewmilson (Andrew Milson) wrote…

Alternatively

Why is it better?

[ilyalesokhin-starkware]

crates/prover/src/core/pcs/quotients.rs line 108 at r4 (raw file):

Previously, andrewmilson (Andrew Milson) wrote…

Previously fri_answers didn't have a notion of trees and just have a big list of columns. Perhaps to be consistent column_log_sizes should be removed and samples should be a TreeVec too? WDYT

Then I'd have to count how many samples have the same log size, right? feels more complicated.

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/verifier.rs line 81 at r4 (raw file):

Previously, andrewmilson (Andrew Milson) wrote…

nit

done

[ilyalesokhin-starkware]

crates/prover/src/core/vcs/prover.rs line 157 at r4 (raw file):

Previously, shaharsamocha7 wrote…

Don't we need the reverse? or this cancels with the reverse in MerkleHasher::verify?

It cancels out with a reverse that I've removed in the Verifier

[ilyalesokhin-starkware]

crates/prover/src/core/pcs/quotients.rs line 108 at r4 (raw file):

Previously, andrewmilson (Andrew Milson) wrote…

Don't you have to do it anyway? Samples are not ordered by log size globally. `samples` is currently just a TreeVec of samples flattened

I'm sorting the flattened sample list here, instead of sorting each TreeVec independently and taking the right number of sample from each.