Proof size should not depend on the number of boundary and transition constraints #5

Open
opened this issue May 29, 2019 · 0 comments

Projects
None yet
Contributor

bobbinth commented May 29, 2019

 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: ``````╒══════ P(x) ═══════╕╒══════ B(x) ═══════╕╒═══════ D(x) ═══════╕ P0 P1 P2 P3 ..... Pw B0 B1 B2 B3 ..... Bk D0 D1 D2 D3 ..... Dn ├──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┤ `````` 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.

Closed