Catch up on Parts 1, 2, and 3 of this series before reading Part 4.
We are explaining how a STARK proof can help one party (a Prover) to process a huge amount of information and convince everyone else that the information is valid and that its computation was done without cheating or errors.
Our steps so far were:
- Register the transaction steps while ensuring they comply with constraints
- Expand data and amplify errors with “check digits”
In order to trust that a computation involving a billion execution instructions was carried out correctly, we’ll take yet another step: apply more constraints, this time to the expanded data.
Checking the check digits
In the same way that we applied constraints to the steps of the transactions, we can now apply additional mathematical checks to verify that the appended values (these sophisticated check digits) also satisfy certain constraints. For example, we can check if the entry (namely, the check digit) representing the sum of all numbers is equal to the entry for the sum of the first half plus the entry for the sum of the second half of all numbers. They should correspond and be aligned, and if this constraint is not satisfied, we’ll know there’s an error somewhere in the proof. We can apply such constraints in various patterns on different parts of the amplified data.
One more example of what can be checked in this phase: recall the example where we checked the transfer of 1 STRK from Alice to Bob. That transfer included execution steps that verified the initial balances of Alice and Bob, the transfer amount, the updated balances, etc.
Now, assume we are processing 1 million transactions, all of which are transfers between many different parties and for many different sums. For 1 million transfers, we will have 1 million entries for each of the execution steps that are being registered:
- 1 million entries for the initial balance of the sender (let’s call them a1, a2, a3, etc.)
- 1 million entries for the initial balance of the receiver (let’s call them b1, b2, b3,etc.)
- 1 million entries for the transfer amount (we’ll call these c1, c2, c3, etc.)
- 1 million entries for the updated balance of the sender (d1, d2, d3, etc.)
- 1 million entries for the updated balance of the receiver (e1, e2, e3, etc.)
- Etc.
Each transfer must satisfy the same constraints that applied to the first transaction we examined, when Alice
transferred 1 STRK to Bob. For example:
- The total initial balances of the sender and receiver (A+B) must equal the total of their final balances (D+E).
- The sender’s initial balance minus the transfer amount (A-C) must equal their final balance (D).
- Etc.
These constraints will apply to transfer 1, transfer 2, transfer 3, and so on, for all 1 million transfers.
Furthermore, after processing all steps of every transfer and appending their check digits, we can now apply the same constraints on these check digits. If certain constraints can verify the validity of each single transfer separately, they can verify the validity of the total of the 1 million transfers. We start by summing all entries of the execution steps. For example:
- a’ will be the sum of all initial balances of the sending accounts (a1+a2+ a3+…)
- b’ will be the sum of all initial balances of the receiving accounts (b1+b2+ b3+…)
- d’ will be the sum of all updated balances of the sending accounts (d1+d2+ d3+…)
- e’ will be the sum of all updated balances of the receiving accounts (e1+e2+ e3+…)
Now, the sum of the total balances of all senders and receivers across all transfers must equal the sum of their final balances after the transfers, or in math: a’+b’=d’+e’!
In the same way that we applied constraints on the steps of a single transaction, we can apply more constraints on the appended check digits themselves. If any step, in any of the transactions, does not align with the constraints, it would cause misalignment in the total sum of each step category (initial balance of senders, final balance of senders, etc.)
(This process of checking the consistency of check digits was first discovered and used in the 1940s, when electronic communication exploded, and mathematicians like Claude Shannon were looking for ways to ensure a radio message was received correctly on the other end, even amid a lot of noise. The field of math and engineering that covers this is called Information Theory, and the objects used to fight noise are “error correcting codes”, which we use in our STARK construction.)
Important note: Making a long sequence even longer
The STARK proof, at this point, contains the data from all the transactions we’re proving, as well as the additional resulting check digits from all the math we applied to it. The Prover works extremely hard to process each transaction; in fact, harder than it would have had to work had we executed these transactions onchain. Why go to all that trouble?
Remember, our goal is to commit new transactions with the least onchain computational work possible to verify their validity. Remember, we want to save the trouble of every teacher grading all exams, and every node re-executing all transactions. Our goal is to let the public verify 1 million transactions with the equivalent computational work of processing 6 transactions.
The added, redundant information takes a tiny error in the original sequence, such as an invalid transfer amount, and repeatedly mixes it with a vast number of subsequent calculations and entries in various patterns. As a result, a small misalignment spreads throughout the entire proof, becoming amplified and impossible to miss.
If the Prover wanted to cheat and not get caught, it would need to start changing many more entries, and it would become harder and harder to make all those changes and keep the resulting entries consistent. By the time we’re done, will it still be the case that the entry for “sum all numbers” equals “sum first half” and “sum second half”?
For the particular check digits we use (for engineers, we use the Reed-Solomon code based on low-degree polynomials), we can prove mathematically that cheating in even one entry would make it impossible to make ends meet. Nearly every combination of check digits that we’ll inspect will not line up.
So now that our proof is an extremely long sequence of numbers, it’s time to shrink it. Part 5 will explain how and why.
