# Understanding Interactive Proof Systems and Sum Check Protocol: Part 2

In [Part 1](https://rac-sri.medium.com/understanding-interactive-proof-systems-and-sum-check-protocol-part-1-6afd9edc67ec), we covered the math, and the logic behind Sum-Check Protocol. In this part, we will be hacking up a quick Sum-Check protocol source code for demonstration.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1734898948897/ef303986-4acb-4b18-958c-24dbd3449bfa.jpeg align="left")

Prerequisites:

* Familiarity with [GoLang](https://go.dev/).
    
* Understanding of Interactive Proofs.
    
* Understanding of the maths behind Sum-Check Protocol (covered [here](https://rac-sri.medium.com/understanding-interactive-proof-systems-and-sum-check-protocol-part-1-6afd9edc67ec))
    

First, let's write some utils functions inside a file named **utils.go**

#### utils.go:

First, we write a helper function that returns the number of arguments taken by a function.

```plaintext
type FuncType func(...int) int

func Arity(f interface{}) int {
// Get the type of f, which should be a function.
fType := reflect.TypeOf(f)
if fType.Kind() != reflect.Func {
// Optionally, handle the case where f is not a function.
    return -1
}
// Return the number of input arguments.
return fType.NumIn()
}
```

Then we write a helper function, which takes an input n, and returns its binary vector, front-padded to pad length ( taken as input again ).

```plaintext
func ToBits(n int, padToLen int) []int {
binStr := strconv.FormatInt(int64(n), 2)

if len(binStr) > padToLen {
    padToLen = len(binStr)
}

v := make([]int, len(binStr))
for i, ch := range binStr {
    if ch == '1' {
        v[i] = 1
    } else {
    v[i] = 0
    }
}
diff := padToLen - len(v)

paddedV := make([]int, diff)
return append(paddedV, v...)
}
```

1. Binary Representation:
    

* The line `binStr := strconv.FormatInt(int64(n), 2)` converts the integer `n` into a binary string representation. For instance, if `n` is `6`, `binStr` will be `"110"`.
    

2\. Creating a Slice of Integers:

* The subsequent loop creates a slice `v` of integers where each element corresponds to a digit in the binary string. '1's in the binary string are represented as `1` in the slice, and '0's as `0`.
    

3\. Padding:

* The function then calculates `diff`, the difference between the desired length `padToLen` and the actual length of the binary representation. If the binary representation is shorter than `padToLen`, it needs to be padded with zeroes.
    
* `paddedV := make([]int, diff)` creates a slice of zeroes of length `diff`.
    
* Finally, the function returns a new slice that concatenates the padding and the binary representation slice (`append(paddedV, v...)`).
    

Lastly: We write a util function that returns the degree of j’th variable in g.

```plaintext
func DegJ(g FuncType, j int) int {
exp := 1
    for {
        args := make([]int, 1)
        for i := range args {
            if i == j {
            args[i] = 100
            } else {
            args[i] = 1
        }
    }
    
    out1 := g(args[0])
    
    args[0] = 1000
    
    out2 := g(args[0])
    
    // Consider a function f(x) = x²
    // To find the degree of x (assuming it's the second variable, so x = 1), the function would compare f(100) with f(1000).
    // If x is cubed (x³), the output should scale by 1000^ 3 / 100 ^ 3
    // when x changes from 100 to 1000. The function checks if this scaling holds to estimate the degree.
    if math.Abs(float64(out1)/math.Pow(100, float64(exp))-float64(out2)/math.Pow(1000, float64(exp))) < 1 {
        return exp
    } else if exp > 10 {
        panic("exp grew larger than 10")
    } else {
        exp++
    } 
    }
}
```

#### verifier.go:

This is where all the logic related to the verifier takes place.

Firstly we define the verifier as follows:

```plaintext
type Verifier struct {
    g FuncType
    gArity int // represents the number of inputs to polynomial
    H int // witness
    randomChallenges []int
    round int
    polynomials []FuncType
}

```

Now, we need a function that accepts polynomial sent by the prover:

```plaintext
func (v *Verifier) RecievePolynomials(polynomial FuncType) {
    v.polynomials = append(v.polynomials, polynomial)
}
```

Now we need a function, that can verify that the latest polynomial is a univariant polynomial of almost deg\_j(g) and that the relationship mentioned:

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1734898950115/8a328397-84a3-409e-bc2f-7e097e14dd03.png align="left")

For this, we write another function on the verifier struct:

```plaintext
func (v *Verifier) CheckLatestPolynomial() error {
    latestPoly := v.polynomials[len(v.polynomials)-1]
    degLatest := DegJ(latestPoly, 0)
    degMax := DegJ(v.g, v.round-1)
    
    if degLatest > degMax {
    return fmt.Errorf("Prover sent polynomial of degree %d greater than expected : %d", degLatest, degMax)
    }
    
    newSum := latestPoly(0) + latestPoly(1)
    
    var check int

    if v.round == 1 {
        check = v.H
    } else {
        check = v.polynomials[len(v.polynomials)-2](v.randomChallenges[len(v.randomChallenges)-1])
    }

    if check != newSum {
        return fmt.Errorf("Prover sent incorrect polynomials: %d, expected %d", newSum, check)
    }

    return nil
}
```

If you read [this](https://rac-sri.medium.com/understanding-interactive-proof-systems-and-sum-check-protocol-part-1-6afd9edc67ec), you will know that we also need to have a mechanism to generate a random number r and send it as a challenge to the prover. To achieve this:

```plaintext
func (v *Verifier) GetNewRandomValueAndSend(p *Prover) {
    rand.Seed(time.Now().UnixNano())
    v.randomChallenges = append(v.randomChallenges, rand.Intn(2))
    p.ReceiveChallenge(v.randomChallenges[len(v.randomChallenges)-1])
    v.round++
}
```

Now, lastly, there is the part where in the final step, the verifier has all the random challenges, and now it uses them to calculate the final value of g. This should match with the final function sₙ(Xn) sent by the prover. If the values match, the verifier accepts.

```plaintext
func (v *Verifier) EvaluateAndCheckGV() (bool, error) {
    if len(v.randomChallenges) != v.gArity-1 {
    return false, fmt.Errorf("Incorrect number of random challenges")
    }

    v.randomChallenges = append(v.randomChallenges, rand.Intn(2))
    gFinal := v.g(v.randomChallenges...)
    check := v.polynomials[len(v.polynomials)-1](v.randomChallenges[len(v.randomChallenges)-1])
    
    if gFinal != check {
        return false, fmt.Errorf("Prover sent incorrect final polynomials")
    }

    fmt.Println("VERIFIER ACCEPTS")
    return true, nil
}
```

And that’s it. We have a basic code ready for a verifier in a Sum-Check Protocol!

**prover.go:**

This is where all the logic related to the prover goes.

Firstly, we define the prover struct as follows:

```plaintext
type Prover struct {
    gArity int
    randomChallenges []int
    cachedPolynomials []FuncType
    round int
    H int
}
```

Now, remember in the Sum-Check protocol, a new polynomial is calculated at each interaction, where several variables = original arguments — round number.

The code iterates from `0` to `2^pad - 1`. In each iteration, `ToBits` is used to create a binary representation of the loop counter `i`, padded to `pad` bits. This binary slice is prepended with the first argument (`args[0]`), and then passed to the polynomial function `poly` .

This function dynamically generates inputs for the polynomial `poly`, combining a constant first argument with varying binary patterns, and aggregating the outputs, playing a key role in the sum-check protocol.

```plaintext
func (p *Prover) ComputeAndSendNextPolynomial(v *Verifier) {
    round := p.round
    poly := p.cachedPolynomials[len(p.cachedPolynomials)-1]
    
    gJ := func(args ...int) int {
    if len(args) == 0 {
        // Handle the case where no arguments are passed
        panic("gJ requires at least one argument")
    }
    pad := p.gArity - round
    var sum int
    for i := 0; i < (1 << pad); i++ {
        args := append([]int{args[0]}, ToBits(i, pad)...)
        sum += poly(args...)
    }
    return sum
    }
    
    v.RecievePolynomials(gJ)
    p.round++
}
```

The iteration process in the `gJ` the function is fundamental to the sum-check protocol, and it's designed to systematically evaluate a polynomial over all possible binary combinations of a certain length. Here's why we iterate this way:

1. Exhaustive Evaluation: The goal is to evaluate the polynomial `poly` for every possible combination of binary inputs. This ensures a thorough and complete assessment of the polynomial's behavior across its entire domain.
    
2. Binary Combinations: By iterating from 0 to 2^(pad−1) and converting these numbers to binary, we generate all possible combinations of binary digits of length `pad`. This is a standard way to cover all cases in binary representation.
    
3. Reducing Complexity Per Round: In each round of the sum-check protocol, one less variable is considered, reducing the computational complexity step by step. `pad` decreases with each round, reflecting this reduction.
    

Lastly, we need a function to receive challenges from the verifier:

```plaintext
func (p *Prover) ReceiveChallenge(challenge int) {
    p.randomChallenges = append(p.randomChallenges, challenge)
    p.CacheNext(challenge)
    fmt.Printf("Received challenge %d, initiating round %d\n", challenge, p.round)
}
```

where CacheNext is simply:

```plaintext
func (p *Prover) CacheNext(challenge int) {
    poly := p.cachedPolynomials[len(p.cachedPolynomials)-1]

    nextPoly := func(args ...int) int {
        return poly(append([]int{challenge}, args...)...)
    }

    p.cachedPolynomials = append(p.cachedPolynomials, nextPoly)
}
```

Now to run this protocol, we can define a simple **main.go** file with the following code to run the prover and the verifier:

```plaintext
type SumcheckProtocol struct {
    gArity int
    p *Prover
    v *Verifier
    round int
    done bool
}

// do the initialization
....

// Advance protocol by 1 round
func (s *SumcheckProtocol) AdvanceRound() {
    if s.done {
    panic("Sumcheck protocol is finished")
}

s.p.ComputeAndSendNextPolynomial(s.v)
s.v.CheckLatestPolynomial()

if s.round == s.gArity {
        // final round
        s.done, _ = s.v.EvaluateAndCheckGV()
    } else {
        s.v.GetNewRandomValueAndSend(s.p)
        s.round++
    }
}

// Advance protocol to the end
func (s *SumcheckProtocol) AdvanceToEnd(verbose bool) {
    for !s.done {
        if verbose {
        fmt.Println("Advance Output:", s)
    }
    s.AdvanceRound()
    }
}
```

Now time to test the protocol !!!  
To do this, we create a new file main\_test.go and add the following lines:

```plaintext
func TestSumcheck(t *testing.T) {

    g := func(args ...int) int {
    a := args[0]
    return a + a + a*a
    }

    protocol := NewSumcheckProtocol(g)
    fmt.Print(protocol)
    protocol.AdvanceToEnd(true)
    
    f := func(args ...int) int {
    a := args[0]
    return a*a*a + a + a
    }

    protocol = NewSumcheckProtocol(f)
    protocol.AdvanceToEnd(true)
    
    ff := func(args ...int) int {
    a := args[0]
    return a*a*a + a + a + a*a
    }
    protocol = NewSumcheckProtocol(ff)
    protocol.AdvanceToEnd(true)
}
```

And Hurray 🎉 🎉 🎉 🎉 !! You just wrote the Sum-Check protocol from scratch.

Here is the complete source code in the tutorial: [Github](https://github.com/rachit2501/Sumcheck-Protocol)

Lastly, connect with me on my socials: [Twitter](https://twitter.com/RacSri25), and [LinkedIn](https://www.linkedin.com/in/rachit-anand-srivastava/). Happy to talk about cryptography, blockchain, and any computer science topic in general.