Right now, STARK proofs include values for all P(x), B(x), and D(x) for all spot checks. Specifically, a leaf of the evaluation Merkle tree has the following form:
This means that the proof size grows with the number of registers w, number of registers mentioned in boundary constraints k, and number of transition constraints n.
While we can't do anything about w (we have to include all evaluations of P(x) into the proof), it seems that we should be able to get away with including only linear combinations of B(x) and D(x).
However, to compute a linear combination, we need a source of randomness, and at the time we build a Merkle tree of evaluations, we don't have anything "random" (once it is built, we use the root of the evaluation Merkle tree as the source of randomness).
One approach to address this could be:
Include only P(x) evaluations in the evaluation Merkle tree.
Use the root of the tree to compute random linear combinations of B(x) and D(x).
Put the random linear combinations into another Merkle tree.
If we can re-purpose the tree we use to prove correctness of random linear combination for low degree proof, than this will come at almost no extra cost.
Right now, STARK proofs include values for all P(x), B(x), and D(x) for all spot checks. Specifically, a leaf of the evaluation Merkle tree has the following form:
This means that the proof size grows with the number of registers
w
, number of registers mentioned in boundary constraintsk
, and number of transition constraintsn
.While we can't do anything about
w
(we have to include all evaluations of P(x) into the proof), it seems that we should be able to get away with including only linear combinations of B(x) and D(x).However, to compute a linear combination, we need a source of randomness, and at the time we build a Merkle tree of evaluations, we don't have anything "random" (once it is built, we use the root of the evaluation Merkle tree as the source of randomness).
One approach to address this could be:
If we can re-purpose the tree we use to prove correctness of random linear combination for low degree proof, than this will come at almost no extra cost.