Alternatives to re-execution

The goal of blockchains

Blockchain technology has emerged to provide a decentralized and secure way to record and verify transactions across a distributed network of participants. The main objective is to eliminate the need for intermediaries, by enabling peer-to-peer transactions. This is achieved through cryptographic techniques that ensure the integrity of all the computations involved in the network, making it highly resistant to fraud and tampering.

One way to verify computations is re-execution. In this process, each node re-executes transactions so that the network reaches consensus. However, this approach can be inefficient, as it requires every node to perform the same computations, resulting in significant bottlenecks.

Could we do things better?

Other ways to prove, other ways to verify

Context

In mathematics, a proof is traditionally an object that can be checked step-by-step for correctness. A classic example is proving the irrationality of √2. To do this, you can assume it is rational, and after a series of steps, a contradiction is reached, which means the initial assumption is false, resulting in the conclusion that it is, in fact, irrational. In this way, we gain certainty about the result, but we need to follow all the steps to check it.

Alternatives

Some alternatives are Interactive Proofs (IPs) and Probabilistically Checkable Proofs (PCPs).

• IPs incorporate interaction and randomness. The prover engages in a conversation with a verifier to try to convince him. To do so, the verifier sends challenges, and then accepts or rejects the proofs.
• PCPs include randomness and probabilistic checking. These proofs are similar to traditional mathematical proofs, but the verifier can only read a small number of characters from the proof. Of course, the verifier doesn’t get certainty; he gets a probability of success, just as Shafi Goldwasser claims.

If we combine interaction, randomness, and probabilistic checking together we can create Interactive Probabilistically Checkable Proofs (Interactive PCPs), or Interactive oracles proofs (IOPs) (for more information you can see this lecture by Alessandro Chiesa).

All this development in research can be used to create various proof systems, where it is key that they satisfy these two properties: completeness (any true statement should have a convincing proof of its validity) and soundness (no false statement should have a convincing proof).

Example with polynomials

Let’s assume that a prover wants to convince a verifier that two specific polynomials of a known degree d are equal.

An interesting fact is that two distinct polynomials of degree d can intersect at most at d points (you can think of it like two straight lines, polynomials of degree 1, which can intersect at most at 1 point). Therefore, if the evaluation domain we are using is considerably larger than d, both polynomials will differ at almost every point.

To provide an example with concrete numbers: if d = 8 and the domain size = 10,007, at most, both polynomials will intersect at 8 points, and at the remaining points, they will differ. So, if the polynomials are distinct, the probability that the verifier randomly queries a point where the two polynomials intersect is less than 1%. The prover and verifier can leverage this fact and make as many queries as needed to perform the verification.

You can check this example in the following code using lambdaworks:

• d = 8
• domain size = 10,007
• queries = 3

In this example, various points were selected to perform interpolations and obtain the two polynomials, 7 of which are the same in both cases, differing by only 1.

#[cfg(test)]
mod tests {

    #[test]
    fn two_different_polynomials() {
        use lambdaworks_math::field::element::FieldElement;
        use lambdaworks_math::field::fields::u64_prime_field::U64PrimeField;
        use lambdaworks_math::polynomial::Polynomial;
        const ORDER: u64 = 10007;
        type F = U64PrimeField<ORDER>;
        type FE = FieldElement<F>;
        use rand::random;

        // Define the two polynomials:
        let p1 = Polynomial::interpolate(&[FE::new(0), FE::new(1), FE::new(2), FE::new(3), FE::new(4), FE::new(5), FE::new(6), FE::new(7)], &[FE::new(1), FE::new(1), FE::new(1), FE::new(1), FE::new(1), FE::new(1), FE::new(1), FE::new(2)]).unwrap();
        let p2 = Polynomial::interpolate(&[FE::new(0), FE::new(1), FE::new(2), FE::new(3), FE::new(4), FE::new(5), FE::new(6), FE::new(7)], &[FE::new(1), FE::new(1), FE::new(1), FE::new(1), FE::new(1), FE::new(1), FE::new(1), FE::new(3)]).unwrap();

        // Define the challenges:
        let challenge_1 = FieldElement::<F>::new(random());
        let challenge_2 = FieldElement::<F>::new(random());
        let challenge_3 = FieldElement::<F>::new(random());

        // Evaluations (p1):
        let evaluation_1_p1 = p1.evaluate(&challenge_1);
        let evaluation_2_p1 = p1.evaluate(&challenge_2);
        let evaluation_3_p1 = p1.evaluate(&challenge_3);

        // Evaluations (p2):
        let evaluation_1_p2 = p2.evaluate(&challenge_1);
        let evaluation_2_p2 = p2.evaluate(&challenge_2);
        let evaluation_3_p2 = p2.evaluate(&challenge_3);

        // Testing the results:
        assert_ne!(evaluation_1_p1, evaluation_1_p2);
        assert_ne!(evaluation_2_p1, evaluation_2_p2);
        assert_ne!(evaluation_3_p1, evaluation_3_p2);
    }
}

As can be seen, after performing the evaluations using the random challenges, the prover fails to convince the verifier that both polynomials are equal. Please note that the following code is designed to pass the test because the final comparisons use assert_ne!.

Conclusion

Re-execution fulfills the purpose of verifying calculations on blockchains, but there are more efficient techniques for that. Part of the mentioned mathematical tricks in the example with polynomials are used for low degree testing in the STARK protocol. However, in real-world protocols, the numbers involved are much larger.

At Aligned, we believe that replacing re-execution and eliminating bottlenecks with zero-knowledge (ZK) technology is vital for Ethereum's scalability, and we have the necessary infrastructure to perform the verifications.

Send proofs!

Stay tuned:  🐦 Twitter | 🗨️ Telegram | 👾 Discord | 🌐 Website | 📝 Manifesto