# How does arithmetization work?

Arithmetization turns a computation into algebra: its steps go into a table, each column becomes a polynomial, and the rules become polynomial equations. STARKs use this form and call it an AIR.

Also called Arithmetisation.

## From program to table

A computation runs step by step, and each step is recorded as a row of numbers. The whole run becomes a table of numbers called an execution trace.

Each column holds one value that changes from step to step, such as a counter or a running total.

## From table to polynomials

Each column is turned into a polynomial over a finite field, so that the column's values are the polynomial's outputs at fixed points. The rules that every step must follow become polynomial equations.

A table that breaks a rule at any step makes one of these equations fail, so proving the equations proves the run.

## AIR, the STARK form

STARKs express the rules as an AIR, which stands for algebraic intermediate representation. An AIR is a system of polynomials that models the machine running the computation, and a valid trace is one whose values satisfy that system.

STARKs then use FRI to check that these polynomials stay below a set degree.

## In Redacted

In bunker mode, an action becomes a table of steps, and each column of that table is stretched into a polynomial.

More: [Bunker mode](https://redacted.gg/docs/using-redacted/bunker-mode.md)

## Related terms

- [STARK](https://redacted.gg/glossary/stark.md): A STARK is a short proof that a long computation was done correctly, which anyone can check quickly. It is built from hash functions alone, so it needs no trusted setup and no elliptic curves, and it can keep the inputs secret.
- [Finite field](https://redacted.gg/glossary/finite-field.md): A finite field is a set with a fixed number of elements, where addition, subtraction, multiplication and division by a nonzero element always stay inside the set. STARKs do their arithmetic in one.
- [Polynomial commitment](https://redacted.gg/glossary/polynomial-commitment.md): A polynomial commitment is a short value that binds a prover to one polynomial. Later the prover can prove the polynomial's value at any chosen point, and the verifier checks that proof against the short value.
- [FRI](https://redacted.gg/glossary/fri.md): FRI is the low-degree test used in STARKs. It checks that committed values come from a polynomial of low degree by halving the problem round after round and testing a few random points, and it rests only on hash functions.
- [Zero-knowledge proof](https://redacted.gg/glossary/zero-knowledge-proof.md): A zero-knowledge proof lets someone prove that a statement is true without revealing anything else, for example that they own funds and may spend them, without showing which funds or who they are.
- [Prover and verifier](https://redacted.gg/glossary/prover-and-verifier.md): In a proof system, the prover makes a claim and builds a proof, and the verifier checks that proof. The verifier accepts only a valid proof, so the prover's claim does not have to be trusted.

Sources: [The Cambrian explosion of cryptographic proofs, StarkWare](https://starkware.co/integrity-matters-blog/cambrian-explosion-of-cryptographic-proofs/), [Builtins and Dynamic Layouts, StarkWare](https://starkware.co/blog/builtins-and-dynamic-layouts/)
---

Page: https://redacted.gg/glossary/arithmetization/