Optimize proof structure

[bobbinth]

Current situation

Right now, STARK proofs include spot checks against 2 Merkle trees (that's in addition to FRI proof). The trees are:

1. An evaluation tree that contains evaluations of P(x), S(x), B(x), and D(x).
2. A linear combination tree that contains linear combinations of P(x), S(x), B(x), and D(x).

A leaf of the evaluation Merkle tree has the following form:

╒══════ P(x) ═══════╕╒══════ S(x) ═══════╕╒══════ B(x) ═══════╕╒═══════ D(x) ═══════╕

 P0 P1 P2 P3 ..... Pw S0 S1 S2 S3 ..... Su B0 B1 B2 B3 ..... Bm D0 D1 D2 D3 ..... Dn 
├──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┤

where w is the number of mutable registers, u is the number of secret input registers, m is the number of mutable registers mentioned in boundary constraints, and n is the number of transition constraints.

This means that the size of the proof grows with the number of registers, number of secret inputs, and number of registers mentioned in boundary constraints, and number of transition constraints.

A leaf of the linear combination tree is just a single value that is a linear combination of all P, S, B, and D evaluations computed as follows:

1. The degree of linear combination is computed as (maxConstraintDegree - 1) * steps. For example, if the degree of transition constraint is 3, the the degree of linear combination would be 3*steps - steps = 2 * steps
2. Then, each polynomial is raised to a power that would increase its degree to match the degree of the linear combination. For example, since deg(P) = steps, we need to compute P^steps.
3. The root of the evaluation tree (eRoot) is used to to compute pseudo-random coefficients (k₀, k₁ etc.).
4. Finally, we combine all polynomials P, P^steps, S, S^steps, B, B^steps, D, D^steps using these coefficients.

Proposed solution

We start off by re-defining the structure of the evaluation Merkle tree. Instead of including evaluations of P(x), S(x), B(x), and D(x), it will now include only evaluations of P(x) and S(x). So, the leaf of the evaluation tree would look like this:

╒══════ P(x) ═══════╕╒══════ S(x) ═══════╕

 P0 P1 P2 P3 ..... Pw S0 S1 S2 S3 ..... Su
├──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┤

The methodology for building linear combination tree remains the same as before.

The verifier is still able to verify everything it was able to verify before. Here is the logic:

1. For each spot check, the verifier gets the values of P₀...P_w and S₀...S_u evaluations and checks Merkle proofs to make sure these values were in the evaluation tree.
2. Then, the verifier uses these values to compute B₀...B_m and D₀...D_n values using boundary and transition constraint relations. a. B(x) = (P(x) - I(x)) / Q(x) b. D(x) = Q(x) / Z(x)
3. Then, the verifier computes liner combination of P, S, B, and D values, and check the results against the root of the linear combination Merkle tree.