In Part 1 of this series, we explained that instead of having thousands of computers re-execute all transactions, one party can do most of the work and prove to others that it was done correctly. The rest only need to run a simple check to verify that the transactions and the process are valid, and know they can safely commit to the resulting data. Let’s look under the hood of this magical protocol.
Generating a STARK proof
Registering transactions and executing steps
As we mentioned, the STARK protocol is operated by two parties: the Prover and the Verifier. In the first step of the process, the Prover will batch a big (huge) amount of transactions, and will write down their data.
Imagine a simple transaction: Alice sends 1 STRK token to Bob.
This transaction involves many small execution steps:
- Check Alice’s balance
- Verify her signature
- Subtract funds from Alice
- Add funds to Bob
- Etc.
The prover will encode these execution instructions step by step. For example:
- Positions A and B: The initial balances of Alice and Bob (100 and 50).
- Position C: The transfer amount from Alice to Bob (1 STRK).
- Positions D and E: The updated balances for Alice and Bob after the transaction (99 and 51).
- Etc.
Constraints
The way to ensure transactions’ validity, as well as their valid execution, starts in this phase. Every transaction must follow certain rules: balances must add up; transfer amounts must be reduced and added to accounts in a coherent and logical manner; balances of both accounts must be updated in accordance with the transfer amount; signatures must match, etc.
These conditions and rules are known as constraints. A transaction is processed correctly if, and only if, all constraints are satisfied.
A helpful analogy for understanding how constraints help us detect alignment or misalignment is a Sudoku puzzle. In Sudoku, the numbers you
fill in the puzzle must collectively satisfy specific rules: each row, column, and small square must contain all digits from 1 to 9, each appearing exactly once. When you fill in a ‘wrong’ number somewhere in the Sudoku puzzle, it will be easily detected once you look at the row, column, or square of that number. It will be immediately clear that a specific constraint is violated.
This doesn’t describe how STARKs actually work, but it’s a useful way to understand the idea of constraints.
How would these constraints work with our example of Alice making a transfer of 1 STRK to Bob? The data written in positions A, B, C, D, and E must satisfy defined constraints that were set to ensure the transaction is valid and that its execution will be done with integrity. For example:
- The total initial balances of Alice and Bob (A+B) must equal the total of their final balances (D+E).
- Bob’s initial balance plus the transfer amount (B+C) must equal his final balance (E).
- Alice’s initial balance minus the transfer amount (A-C) must equal her final balance (D).
- The transfer amount (C) must be positive and not exceed Alice’s balance.
If, for any reason, error or maliciousness, any of the data does not align with these constraints, it will show in this part of the proof.
For example, if someone tried to cheat and transfer 1 STRK to Bob without reducing it from Alice’s account, 2 constraints will be violated:
- Constraint 1 will be violated, because the total initial balances of Alice and Bob (A+B) will not be equal to the
total of their final balances (D+E). - Constraint 3 will also be violated because Alice’s initial balance minus the transfer amount (A-C) will not be equal
to her final balance (D).
After the Prover finishes registering all the steps of all transactions, we now have a long sequence of numbers representing the data that we want to process. The validity of the execution steps is confirmed through their compliance with the defined constraints. If an invalid transaction or step has infiltrated this sequence, its misalignment with the constraints will be evident. However, only at the specific relevant place in the sequence.
Can we ensure we’ll detect a single invalid step hiding among the millions (and even billions) of steps processed in a batch of 1 million transactions? We can’t. Yet. For that, we’ll need more math. Part 3 will cover this.
