Read Part 1 and Part 2 before beginning Part 3 in the How STARKs Work series.
Expanding data, amplifying errors
Our STARK proof now consists of a long sequence of numbers that represent the execution steps of all the transactions in the batch we are processing. If any of these execution steps do not comply with the given constraints, it will be detectable in that part of the proof. But if we’re processing 1 million transactions, and each transaction involves multiple execution steps (say, a thousand on average), then we have a proof that includes 1 billion execution steps. We’d have to be very lucky to catch a single error. It could easily go unnoticed.
To make even a single error stand out and be noticed, our next step will be to amplify and expand the data. This will be done in such a way that invalid steps will cast their misalignment with constraints further across the proof.
This phase can be thought of as a very sophisticated version of check digits. Think of a check digit as a built-in security method for long identification numbers, like those found on books (ISBN), cars (VIN), or passports. To prevent typos or swapped numbers, the system runs the main string of digits through a specific mathematical formula. The result of that calculation is added at the end of the number as the “check digit.” If one of the digits is mistyped, the formula will not match the check digit, indicating an error.
For example:
Let’s assume the formula for the check digit of ID numbers is the sum of all digits, taken as the remainder after dividing by 10.
If my ID number is 123456, then 1+2+3+4+5+6=21. Dividing 21 by 10 gives a remainder of 1. That 1 is the check digit. Therefore, the full ID number would be 123456-1.
How does it catch an error?
If I type one wrong digit, the check digit won’t align mathematically. For example, if I accidentally type 123455-1, we get an error. Since 1+2+3+4+5+5=20, the check digit should be 0, not 1. The math doesn’t align.
This process won’t tell me which digit is wrong, but it will tell me that there is an error somewhere.
Of course, this is a simplified example used to explain a basic method for catching an error in a string of numbers. For the scale of data that STARKs process – often hundreds of millions of steps – we need a far more powerful, sophisticated, and secure version of this method.
To achieve this, we add many such “check digits” in carefully designed patterns. For the mathematicians and engineers reading this, we use an error-correcting code with desirable properties. For example, we may compute values such as:
- The sum of all numbers in the sequence
- The sum of every third number
- The sum of all even numbers
- The sum of the first half of the sequence
- And so on
At the end of this process, the sequence of numbers of our proof will contain both the data of the transactions that are being processed and the check digits that were appended afterward. It is worth noting that the appended sequence of check digits is much longer than the transaction data.
So far, the prover has processed all the transaction data by registering their execution steps, indicating their alignment with constraints, and applying error correcting methods to expose invalid steps, if they exist. However, we are aiming to process huge amounts of transactions, and our goal is to be as certain as possible that they are all valid. There’s more work to be done to ensure that.
Read the Part 4 to discover which additional mathematical steps help us do that.
