A simple demonstration of the sum check protocol

sum-check-protocol.cs

using System.Security.Cryptography;

Console.WriteLine
(
    """
    Hello!
    Here's a sum-check protocol demonstration.

    The sum-check protocol is an interactive proof system that allows a prover
    to convince a verifier that the sum of a multivariate polynomial over 
    all binary inputs is correct without the verifier computing the entire sum.
    It is particularly useful in scenarios where the verifier has limited computational 
    resources, compared to the prover. The protocol works by reducing the problem of verifying
    a large sum to verifying a smaller sum, and it does so in a way that ensures
    the verifier can be confident in the correctness of the original sum.

    Here's a high-level overview of how the sum-check protocol works:

    1. The prover and verifier agree on a polynomial f(x, y) that they will use to represent their sum.
    2. The prover selects a random value x and computes f(x, y1) and f(x, y2) - claiming that this is the sum of all values in the set.
    3. The prover sends these values to the verifier.
    4. The verifier selects a random value y and computes f(x1, y) and f(x2, y).
    5. The prover and the verifier interactively reduce the problem of verifying the large sum by verifying a smaller sum.
       This process continues until the problem is reduced to verifying the sum of a univariate polynomial.    
    """
);

public static class Field
{
    public const int Prime = 17;
    public static int Add(int a, int b) => (a + b) % Prime;
    public static int Multiply(int a, int b) => (a * b) % Prime;
}

public class Prover
{
    private int r1;
    public int[] GetRound1Polynomial() => [0, 1]; // g1(v1) = v1
    public int[] GetRound2Polynomial(int challenge)
    {
        r1 = challenge;
        return [0, 1]; // g2(v2) = r1 * v2
    }

    public int EvaluateFinal(int r2) => Field.Multiply(r1, r2);
}

public class Verifier
{
    private readonly int S = 1; // expected sum for f(v1, v2) = v1 * v2
    
    public bool VerifyRound1(int[] polynomial)
    {
        int sum = (EvaluatePolynomial(polynomial, 0) + EvaluatePolynomial(polynomial, 1)) % Field.Prime;
        return sum == S;
    }

    public bool VerifyRound2(int[] polynomial, int previousSum)
    {
        int sum = (EvaluatePolynomial(polynomial, 0) + EvaluatePolynomial(polynomial, 1)) % Field.Prime;
        return sum == previousSum;
    }

    public int EvaluatePolynomial(int[] coefficients, int x)
    {
        int result = 0;
        for (int i = coefficients.Length - 1; i >= 0; i--)
        {
            result = (result + coefficients[i] * (int)Math.Pow(x, i)) % Field.Prime;
        }

        return result;
    }

    public int GenerateChallenge() => RandomNumberGenerator.GetInt32(0, Field.Prime);
}

public partial class Program
{
    public static void Main()
    {
        Prover prover = new();
        Verifier verifier = new();

        // round 1
        int[] g1 = prover.GetRound1Polynomial();
        if(!verifier.VerifyRound1(g1))
        {
            Console.WriteLine("round 1 failed");
            return;
        }

        int r1 = verifier.GenerateChallenge();

        // round 2
        int[] g2 = prover.GetRound2Polynomial(r1);
        int prevSum = verifier.EvaluatePolynomial(g1, r1);
        if(!verifier.VerifyRound2(g2, prevSum))
        {
            Console.WriteLine("round 2 failed");
            return;
        }   

        int r2 = verifier.GenerateChallenge();

        // final check
        int expected = Field.Multiply(r1, r2);
        int actual = prover.EvaluateFinal(r2);
        Console.WriteLine(expected == actual ? "Verified" : "Rejected");        
    }
}