1
$\begingroup$

The STARK paper says

Our ZK-STARK uses a separate Reed-Solomon codeword for each register, leading to w many codewords, each of lower degree n · c. At first glance this tradeoff may seem wasteful, because we now have to solve an RPT problem for each of these w codewords. However, the interaction and use of randomness allowed by the IOP model once again come to our aid: it suffices to solve a single RPT problem, applied to a random linear combination of all w codewords.

My understanding is that

  1. The prover sends an oracle containing a trace of each register, purportedly encoded as a codeword.
  2. The verifier picks a random coefficient for each register.
  3. The prover sends an oracle which purportedly contains the linear combination of these register traces, using the coefficients from #2.
  4. The verifier somehow tests for consistency between the two oracles.

And then there's an IOPP to convince the verifier that the linear combination is close to a codeword. If so, then each register's trace is close to a codeword with high probability.

My question is, how does the consistency test (#4) work? If the verifier was already convinced that each register trace was a codeword, then the verifier would know that either the linear combination was correct, or it was incorrect at many indices. So they could test for consistency at a small number of indices, and if those were correct, the entire linear combination must be correct with high probability.

But in this context, it seems like the above technique wouldn't help, since the verifier is not yet convinced that each register trace is close to a codeword. So how does the verifier test that the purported linear combination is correct?

$\endgroup$

1 Answer 1

1
$\begingroup$

The prover does not send another oracle as you suggest in #3. Rather, both parties invoke the FRI protocol for the function that is the random linear combination (random coefficients selected in #2). Now, every query to the function you refer to in #3 is answered by querying all oracles #1 and computing the linear combination #2 (which is something the verifier does). Thus, the soundness error for this function is 0 and there's perfect consistency, by construction.

$\endgroup$
1
  • $\begingroup$ Thank you for explaining. If I understood correctly, it seems like the overall query count would be the same if RPT was done per-register, but doing one RPT on the combination must be faster? $\endgroup$ Commented Apr 7, 2019 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.