Module challenges

Challenges are needed for the cross-table arguments, i.e., Permutation Arguments, Evaluation Arguments, and Lookup Arguments, as well as for the RAM Table’s Contiguity Argument.

There are three types of challenges:

• Weights. Weights are used to linearly combine multiple elements into one element. The resulting single element can then be used in a cross-table argument.
• Indeterminates. All cross-table arguments work by checking the equality of polynomials (or rational functions). Through the Schwartz-Zippel lemma, this equality check can be performed by evaluating the polynomials (or rational functions) in a single point. The challenges that are indeterminates are exactly this evaluation point. The polynomials (or rational functions) are never stored explicitly. Instead, they are directly evaluated at the point indicated by a challenge of “type” Indeterminate, giving rise to “running products”, “running evaluations”, et cetera.
• Terminals. The public input (respectively output) of the program is not stored in any table. Instead, the terminal of the Evaluation Argument is computed directly from the public input (respectively output) and the indeterminate.

Structs

• Challenges
  The Challenges struct holds the challenges used in Triton VM. The concrete challenges are known only at runtime. The challenges are indexed using enum ChallengeId. The Challenges struct is essentially a thin wrapper around an array of XFieldElements, providing convenience methods.