> ## Documentation Index
> Fetch the complete documentation index at: https://starkware-9575960b-agent-options.mintlify.site/llms.txt
> Use this file to discover all available pages before exploring further.

# 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 S-two implementation, a point on the circle is defined as follows:

```rust
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](https://eprint.iacr.org/2024/278).
In this documentation, we adopt the additive notation for consistency with the implementation.
The above group operation is implemented as:

```rust
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:

```rust
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 S-two, the conjugate of a `CirclePoint` is computed as:

```rust,no_run,noplayground
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](https://eprint.iacr.org/2024/278).

In S-two 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:

```rust
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:

```rust
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 S-two as:

```rust,no_run,noplayground
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).

<video autoPlay loop muted playsInline src="https://mintcdn.com/starkware-9575960b-agent-options/nuOXaeznYw0ow3n4/learn/s-two/how-it-works/animations/vid_circle_domain.mp4?auto=format&n=nuOXaeznYw0ow3n4&q=85&s=d89e1b281d3ce52ff344024a0f62f8df" data-path="learn/s-two/how-it-works/animations/vid_circle_domain.mp4" />

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

```rust,no_run,noplayground
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 <a href="https://eprint.iacr.org/2024/278" target="_blank" rel="noopener noreferrer">Circle STARKs paper</a>.
Such domains are called *standard position coset*, or are referred to as *canonic cosets*.
They are implemented as follows:

```rust
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:

```rust
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$.

<video autoPlay loop muted src="https://mintcdn.com/starkware-9575960b-agent-options/nuOXaeznYw0ow3n4/learn/s-two/how-it-works/animations/vid_canonic_coset.mp4?auto=format&n=nuOXaeznYw0ow3n4&q=85&s=9c515d8614f85c5aabbb67e864aa3576" data-path="learn/s-two/how-it-works/animations/vid_canonic_coset.mp4" />

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:

```rust
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.