Circle Group

As discussed in the previous section, Mersenne prime fields \( \mathbb{F}_p \) lack a smooth subgroup whose order is a large power of two. This property makes such fields unsuitable for instantiating STARK protocols. To address this, we consider extensions of \( \mathbb{F}_p \) that have smooth subgroups, which are suitable for performing FFTs and implementing the FRI protocol.

For a field extension \( F \) of \( \mathbb{F}_p \), we define the circle curve \( C(F) \) as the set of points \( (x, y) \in F^2 \) satisfying the relation: \[ x^2 + y^2 = 1 \]

In Stwo implementation, a point on the circle is defined as follows:

pub struct CirclePoint<F> {
    pub x: F,
    pub y: F,
}

The set \( C(F) \) forms a cyclic group under the operation defined by: \[ (x,y) + (x', y') = (xx' - yy', xy' + x'y) \]

Here, the group is defined additively, which differs from the multiplicative notation used in the Circle STARKs paper. In this documentation, we adopt the additive notation for consistency with the implementation. The above group operation is implemented as:

    fn add(self, rhs: Self) -> Self::Output {
        let x = self.x.clone() * rhs.x.clone() - self.y.clone() * rhs.y.clone();
        let y = self.x * rhs.y + self.y * rhs.x;
        Self { x, y }
    }

The identity element in this group is \( (1, 0) \), implemented as:

    pub fn zero() -> Self {
        Self {
            x: F::one(),
            y: F::zero(),
        }
    }

Negation in the circle group corresponds to the conjugation map \( J \), defined by: \[ J(x, y) = (x, -y) \] This is same as complex conjugation in complex numbers. In Stwo, the conjugate of a CirclePoint is computed as:

    pub fn conjugate(&self) -> CirclePoint<F> {
        Self {
            x: self.x.clone(),
            y: -self.y.clone(),
        }
    }

The total number of points in the circle group \( C(F) \) is given by \( |F| + 1 \). Specifically, for \( C(\mathbb{F}_p) \), the number of points is \( p + 1 \), which, as discussed earlier, is a large power of two and can thus be used in STARK protocol instantiations. This result is proven in Lemma 1 of the Circle STARKs paper.

In Stwo implementation, the generator \( g \) of the group \( C(\mathbb{F}_p) \) is defined as: \[ g = (2, 1268011823) \] where \( p = 2^{31} -1\). Subgroups of \( C(\mathbb{F}_p) \) of size \( 2^n \) can be generated using the following function:

    pub fn subgroup_gen(n: u32) -> CirclePoint<F> {
        assert!(n <= M31_CIRCLE_LOG_ORDER); // M31_CIRCLE_LOG_ORDER = 31
        let s = 1 << (M31_CIRCLE_LOG_ORDER - n);
        M31_CIRCLE_GEN.mul(s) // M31_CIRCLE_GEN = g = (2, 1268011823)
    }

To generate a subgroup \( \langle g_n \rangle \) of size \( 2^n \), the function computes \( 2^{31 - n} \cdot g \), i.e. it applies the group law to the generator \( g \) with itself \( 2^{31 - n} \) times, as shown below:

    pub fn mul(&self, mut scalar: u128) -> CirclePoint<F> {
        let mut res = Self::zero();
        let mut cur = self.clone();
        while scalar > 0 {
            if scalar & 1 == 1 {
                res = res + cur.clone();
            }
            cur = cur.double();
            scalar >>= 1;
        }
        res
    }

Hence, the point \( 2^{31-n} \cdot g \) serves as a generator of a subgroup \( \langle g_n \rangle \) of order \( 2^n \).

Circle Domain

In a STARK protocol, the computation trace is interpolated as a low-degree polynomial over a domain using FFT. For Circle STARKs, this domain consists of points on the circle curve and is referred to as the circle domain. The circle domain \( D \) is constructed as the union of two disjoint cosets: \[ D = q + \langle g_{n-1} \rangle \cup -q + \langle g_{n-1} \rangle \] Here, \( \langle g_{n-1} \rangle \) is a subgroup of size \( 2^{n-1} \), and \( q \) is the coset offset. This union is also called the twin-coset. The second coset in the union can be viewed as the negation (or conjugation) of the first: \[ J(q + \langle g_{n-1} \rangle) = -q + \langle g_{n-1} \rangle \] Therefore, it suffices to store only the half coset \( q + \langle g_{n-1} \rangle \), and generate the full domain via its conjugates. The circle domain is defined in Stwo as:

pub struct CircleDomain {
    pub half_coset: Coset,
}

The following animation shows a circle domain of size 8. It is constructed from the half coset \( q + \langle g_2 \rangle \) of size 4 (shown as red points) and its negation \( -q + \langle g_2 \rangle \) (shown as blue points).

To iterate over all points in the circle domain, we can iterate over the half coset and its conjugates:

    pub fn iter(&self) -> CircleDomainIterator {
        self.half_coset
            .iter()
            .chain(self.half_coset.conjugate().iter())
    }

Canonic Coset

For a specific choice of offset \( q \), the twin-coset \( D \) becomes a coset of a larger subgroup. In particular, if \( q \) is a generator of a subgroup of order \( 2^{n+1} \), then: \[ D = q + \langle g_n \rangle = q + \langle g_{n-1} \rangle \cup -q + \langle g_{n-1} \rangle \] This result is proven in Proposition 1 of the Circle STARKs paper. Such domains are called standard position coset, or are referred to as canonic cosets. They are implemented as follows:

pub struct CanonicCoset {
    pub coset: Coset,
}

Here, CanonicCoset represents the full coset \( q + \langle g_n \rangle \), while CircleDomain is represented with its half coset \( q + \langle g_{n-1} \rangle \). Thus to compute the CircleDomain from the CanonicCoset, first calculate the half coset \( q + \langle g_{n-1} \rangle \), which will be used to initialize the CircleDomain as shown below:

    pub fn circle_domain(&self) -> CircleDomain {
        CircleDomain::new(self.half_coset())
    }

The following animation shows a canonic coset of size 8. It is constructed from the coset \( \langle g_3 \rangle \) of size 8 followed by an offset by \( q \), where \( q \) is the generator of subgroup \( \langle g_4 \rangle \).

We can verify whether a given CircleDomain is canonic by checking the step size of the half coset against the initial coset offset. In the CircleDomain implementation, only the half coset \( q + \langle g_{n-1} \rangle \) is explicitly stored. If CircleDomain is canonic, \( q \) must be a generator of the subgroup \( \langle g_{n+1} \rangle \), which has order \( 2^{n+1} \) i.e. \( q = 2^{31 - (n+1)} \cdot g \). Recall that the generator of the subgroup \( \langle g_{n-1} \rangle \) is \( 2^{31 - (n-1)} \cdot g \).

Thus, the step size between consecutive elements in the half coset is \( 2^{31 - (n-1)} \cdot g \), and the initial point is \( q = 2^{31 - (n+1)} \cdot g \). Therefore, the ratio between the step size and the initial coset offset is: \[ \frac{2^{31 - (n-1)}}{2^{31 - (n+1)}} = 2^2 = 4 \] This means that in a canonic coset, the step size is exactly four times the initial coset offset. This condition is used to check whether a CircleDomain is canonic, as shown below:

    pub fn is_canonic(&self) -> bool {
        self.half_coset.initial_index * 4 == self.half_coset.step_size
    }

In the next section, we will dive into polynomials defined over the circle.

stwo-book

Circle Group

Circle Domain

Canonic Coset