Skip to main content

Documentation Index

Fetch the complete documentation index at: https://docs.starknet.io/llms.txt

Use this file to discover all available pages before exploring further.

As discussed in the previous section, Mersenne prime field M31\textsf{M31} lacks 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 M31\textsf{M31} that have smooth subgroups, which are suitable for performing FFTs and implementing the FRI protocol. For a field extension FF of M31\textsf{M31}, we define the circle curve C(F)C(F) as the set of points (x,y)∈F2(x, y) \in F^2 satisfying the relation: x2+y2=1x^2 + y^2 = 1 In S-two implementation, a point on the circle is defined as follows: 
pub struct CirclePoint<F> {
    pub x: F,
    pub y: F,
}
The set C(F)C(F) forms a cyclic group under the operation defined by: (x,y)+(x′,y′)=(xx′−yy′,xy′+x′y)(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)(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 JJ, defined by: J(x,y)=(x,−y)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: 
    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)C(F) is given by ∣F∣+1|F| + 1. Specifically, for C(M31)C(\textsf{M31}), the number of points is P+1P + 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 S-two implementation, the generator gg of the group C(M31)C(\textsf{M31}) is defined as: g=(2,1268011823)g = (2, 1268011823) Subgroups of C(M31)C(\textsf{M31}) of size 2n2^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 ⟨gn⟩\langle g_n \rangle of size 2n2^n, the function computes 231−n⋅g2^{31 - n} \cdot g, i.e. it applies the group law to the generator gg with itself 231−n2^{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 231−n⋅g2^{31-n} \cdot g serves as a generator of a subgroup ⟨gn⟩\langle g_n \rangle of order 2n2^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 DnD_n of size 2n2^n is constructed as the union of two disjoint cosets: Dn=q+⟨gn−1⟩∪−q+⟨gn−1⟩D_n = q + \langle g_{n-1} \rangle \cup -q + \langle g_{n-1} \rangle Here, ⟨gn−1⟩\langle g_{n-1} \rangle is a subgroup of size 2n−12^{n-1}, and qq is the coset offset such that q≠−qq \neq -q. 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+⟨gn−1⟩)=−q+⟨gn−1⟩J(q + \langle g_{n-1} \rangle) = -q + \langle g_{n-1} \rangle Therefore, it suffices to store only the half coset q+⟨gn−1⟩q + \langle g_{n-1} \rangle, and generate the full domain via its conjugates. The circle domain is defined in S-two as: 
pub struct CircleDomain {
    pub half_coset: Coset,
}
The following figure shows a circle domain of size 8. It is constructed from the half coset q+⟨g2⟩q + \langle g_2 \rangle of size 4 (shown as red points) and its negation −q+⟨g2⟩-q + \langle g_2 \rangle (shown as blue points).
Figure 1: Circle Domain of size 8
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 qq, the twin-coset DnD_n becomes a coset of a larger subgroup. In particular, if qq is a generator of a subgroup of order 2n+12^{n+1}, then: Dn=q+⟨gn⟩=q+⟨gn−1⟩∪−q+⟨gn−1⟩D_n = 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+⟨gn⟩q + \langle g_n \rangle, while CircleDomain is represented with its half coset q+⟨gn−1⟩q + \langle g_{n-1} \rangle. Thus to compute the CircleDomain from the CanonicCoset, first calculate the half coset q+⟨gn−1⟩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 figure shows a canonic coset of size 8. It is constructed from the coset ⟨g3⟩\langle g_3 \rangle of size 8 followed by an offset by qq, where qq is the generator of subgroup ⟨g4⟩\langle g_4 \rangle.
Figure 2: Canonic Coset of size 8
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+⟨gn−1⟩q + \langle g_{n-1} \rangle is explicitly stored. If CircleDomain is canonic, qq must be a generator of the subgroup ⟨gn+1⟩\langle g_{n+1} \rangle, which has order 2n+12^{n+1} i.e. q=231−(n+1)⋅gq = 2^{31 - (n+1)} \cdot g. Recall that the generator of the subgroup ⟨gn−1⟩\langle g_{n-1} \rangle is 231−(n−1)⋅g2^{31 - (n-1)} \cdot g. Thus, the step size between consecutive elements in the half coset is 231−(n−1)⋅g2^{31 - (n-1)} \cdot g, and the initial point is q=231−(n+1)⋅gq = 2^{31 - (n+1)} \cdot g. Therefore, the ratio between the step size and the initial coset offset is: 231−(n−1)231−(n+1)=22=4\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.