Related type: TraitsResolver TraitsResolver helps to find the implementation for a given trait function and concrete type arguments. TraitsResolver has a function resolve_trait_function_reference (see below) for a given polynomial reference, it resolves its trait one of the input to this polynomialReference, using fibo_no_public example, PolynomialReference looks like: Understanding the remove_trait_impls Function in Rust This post explains the remove_trait_impls function, its purpose, and how it works step-by-step. Function Overview /// Update the data structure after a certain set of trait impls have been removed. /// This just updates the `index` fields. /// Assumes that `to_remove` is sorted. pub fn remove_trait_impls(&mut self, to_remove: &[usize]) { for map in self.impls.values_mut() { *map = map .drain() .filter_map(|(type_args, mut impl_data)| { match to_remove.binary_search(&impl_data.index) { Ok(_) => None, Err(index) => { // `index` is the number of removed elements before this one. impl_data.index -= index; Some((type_args, impl_data)) } } }) .collect(); } } Purpose of the …

Following the first post: Circle STARK: Understanding Circle Group’s Operation as Rotation The goal of this post is to explain 2-adic FFT on circle domain. why FFT? In STARK, there are two cases where FFT is used: transform a polynomial from its evaluation form to its coefficients form. FRI, where the “split and fold” idea comes from FFT The first use case happens when a trace is considered as the evaluations of a polynomial on trace domain, we need to use FFT to get the coefficient form of this polynomial, and then evaluate this polynomial on trace evaluation domain. What is the requirement for a circle domain where FFT can be applied? For both cases to work, the underlying domain where FFT is applied on, needs to satisfy some requirements. In cyclic group generated from prime field, we know the group order needs to be smooth. but what about FFT …

A Rust program is compiled to ELF, using traditional compiler (as ELF is not only used for ZKVM, but also for embedded system as well, this step is pretty much standard) instruction explanation: ADD, value1 stored in address xD, added this value by 5 and store the value in x29 Understanding RISC-V Emulator Execution Process This post explains how a RISC-V emulator or runtime executes a program, specifically one in the ELF (Executable and Linkable Format) file format, which contains machine instructions. 1. Execution Process When the ELF file is ready to run, the emulator or runtime starts executing each instruction in sequence. The program counter (PC) is used to track the next instruction to execute. The PC is simply a numeric value that points to the current instruction in the ELF file. 2. Program Counter (PC) The PC initializes at a start address, guiding the runtime on where to …

Table of Contents What is Runtime? Runtime Environment Runtime Systems Runtime Errors Runtime Libraries Examples in Context What is a Processor? What is a CPU? Key Difference Between Processor and CPU Analogy What is Runtime? Runtime refers to the period when a program is actively running or executing on a computer. In software development, it represents the phase during which the program instructions are loaded into memory and executed by the processor, as opposed to compile time (when the source code is being translated into machine code). Runtime Environment The runtime environment refers to the software and hardware infrastructure that supports the execution of a program. For example: Operating System (OS): Provides system resources like memory and CPU. Virtual Machines (VMs): Java programs, for instance, run in the Java Runtime Environment (JRE). Runtime Systems These are tools and services that programs use during execution, such as: Garbage Collection: Automatically manages …

The goal of this blog is to explain circle group without complex mathematical definitions. However, this approach is not rigorous, it serves more like a intuition of understanding the geometry of a circle group. Before diving into the blog, may you need some pre-readings like Exploring circle STARKs or Yet another circle STARK tutorial What we care most about a group A group \(G\) is a set equipped with a binary operation \( \cdot\), denoted as (𝐺,⋅), the set satisfies the closure, associativity properties, and it has identity element and inverse elements. FRI is working on a cyclic group. A cyclic group is a group that can be generated by a single element, called a generator. This means that every element in the group can be generated by applying the group operation on the generator multiple times. Now we see circle group is used as the cyclic group in STARK, …

Using multiplicative group of size 16 to demonstrate the concept of coset. Start with STARK context: suppose we have a trace \([1,2,3,4]\) , and we want to prove \(f(x)+1=f(gx)\) \(g\) is the group generator for cyclic group of size 4, the same size of the trace. generate group of size the same as the trace, namely 4 we will generate a group from a bigger multiplicative group of size 16, its group generator: \(w\) , this bigger group looks like: \([w^0,w^1,w^2,w^3,w^4,w^5,w^6,w^7,w^8,w^9,w^{10}, w^{11},w^{12},w^{13},w^{14},w^{15}]\) choose group generator for trace evaluation domain to generate a group of size 4 out from this group of size 16, we can set the generator to be \(g=w^4\), and the trace evaluation domain becomes: \([w^0,w^4,w^8,w^{12}]\) our trace polynomial in this setting, satisfy \(f(x)+1=f(w^4x)\) (as \(g=w^4\)) it will be interpolate to a polynomial \(f(w^0)=1,f(w^4)=2,f(w^8)=3,f(w^{12})=4 \) Expand the trace evaluation domain now using blowup factor 2, we then need …