Shifted Value Indices

A shifted value index is basically a witness component that has been shifted in a prescribed way by a prescribed amount. They will feature essentially in our constraints, which we describe after this. Here, we specify them in detail.

Shift Types

We support three shift types, logical left, logical right, and arithmetic right. We write these symbolically as $\{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$

Our shift operations do what they sound like. Each acts exclusively on 64-bit words; we allow shift amounts $s \in \{0, \ldots , 63\}$. Logical leftshift shifts towards the more-significant end, zero-filling; logical rightshift shifts towards the less-significant end. Arithmetic rightshift "sign-extends"; whatever the most-significant (63^rd) bit is will be "dragged" or populated rightwards.

Prover Data

Our system's runtime-dependent, prover-supplied data will be a long array of 64-bit words. This data will be made up of three "stretches": the constant part, the input–output part, and the witness part. Both the constant and input–output parts will be "visible" to the verifier, and will made to exactly match public data known to the verifier. The input–output part can be thought of as the "statement"; it will change from proof to proof, but will be visible to the verifier. The prover's witness data will impact the verifier's runtime only polylogarithmically.

The lengths of three these stretches will be fixed at compile-time; we can write $n_\text{const}$, $n_\text{inout}$, and $n_\text{witness}$ for these lengths. We will write $w$ for the concatenation of all three of these stretches. The total length of $w$ will thus be $n_\text{words} \coloneqq n_\text{const} + n_\text{inout} + n_\text{witness}$. Thus each element $y \in \{0, \ldots , n_\text{words} - 1\}$ will index into an element of prover data. We will write $w[y]$ for the $y$^th prover word.

Throughout, we use the term "prover data", and not "witness", for $w$, since only part of the prover data will consist of the witness. But intuitively, $w$ is witness-like.

Shifted Value Indices

A shifted value index is a triple consisting of an index $y \in \{0, \ldots , n_\text{words} - 1\}$, a shift type $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$, and a shift amount $s \in \{0, \ldots , 63\}$. We can write each such thing like $(y, \text{op}, s)$. Each shifted value index lives in the set

Each shifted value index represents a component of the prover's data, a shift operation or type, and a shift amount.

For example, the shifted value index $(55, \mathsf{sll}, 10)$ represents w[55] << 10, "the 55^th component of runtime-dependent data, shifted left by 10 steps".