# Gnark's infinite loop call trace and explanation

As said in the [post](https://www.notamonadtutorial.com/how-to-use-the-consenyss-gnark-zero-knowledge-proof-library-and-disclosure-of-a-ddos-bug/) there is a bug in Gnark when using the low-level API for building an R1CS. The code that causes it is the following:

/* R1CS Building */

// (X * Y) == Z + 5
// X is secret
// Y is public
// Z is public
// 5 is constant
r1cs := cs_bn254.NewR1CS(1)

// Variables
_ = r1cs.AddPublicVariable("1") // the ONE_WIRE
Y := r1cs.AddPublicVariable("Y")
Z := r1cs.AddPublicVariable("Z")
X := r1cs.AddSecretVariable("X")

// Constants
FIVE := r1cs.FromInterface(5)
CONST_FIVE_TERM := r1cs.MakeTerm(&FIVE, 0)
CONST_FIVE_TERM.MarkConstant()

// Coefficients
COEFFICIENT_ONE := r1cs.FromInterface(1)

// Constraints
// (1 * X) * (1 * Y) == (1 * Z) + (5 * 1)
constraint := constraint.R1C{
    L: constraint.LinearExpression{r1cs.MakeTerm(&COEFFICIENT_ONE, X)}, // 1 * X
    R: constraint.LinearExpression{r1cs.MakeTerm(&COEFFICIENT_ONE, Y)}, // 1 * Y
    O: constraint.LinearExpression{
        r1cs.MakeTerm(&COEFFICIENT_ONE, Z)}, // 1 * Z 1
        CONST_FIVE_TERM, // 5
}
r1cs.AddConstraint(constraint)

...

This bug not only makes the execution to go into an infinite loop but it could use all the available memory! Here we present kind of an execution trace that leads to the bug's origin and what we understand is happening there.

## Path to the bug

First of all, we need to understand what `MarkConstant()` is doing. `MarkConstant()` is a method for `Term`s. `Term` represents a $\mathbb{coefficient} \cdot \mathbb{value}$ in a constraint system and it is defined as follows in the [`constraints/term.go` module](https://github.com/ConsenSys/gnark/blob/master/constraint/term.go#L22) (or `constraint` package):

type Term struct {
    CID, VID uint32
}

where `CID` is the coefficient ID that represents the index of the concrete coefficient of the term and `VID` is the value ID that represents the index of the concrete value of the term.

`MarkConstant()` basically sets `VID` to the max `uint32` value

func (t *Term) MarkConstant() {
    t.VID = math.MaxUint32
}

Then the API exposes another method to know if a given term is constant

func (t *Term) IsConstant() bool {
	return t.VID == math.MaxUint32
}

Now that we know what `MarkConstant()` does, it'd make more sense to say that the bug is caused because the `VID` is set to this high value. Let's see why.

Everything starts at `AddConstraint` in the [`r1cs.go` module](https://github.com/ConsenSys/gnark/blob/master/constraint/bn254/r1cs.go). It may look redundant but this function adds a constraint to a circuit and returns a constraint ID (`cID`)

func (cs *R1CS) AddConstraint(r1c constraint.R1C, debugInfo ...constraint.DebugInfo) int {
    profile.RecordConstraint()
    cs.Constraints = append(cs.Constraints, r1c)
    cID := len(cs.Constraints) - 1
    if len(debugInfo) == 1 {
        cs.DebugInfo = append(cs.DebugInfo, constraint.LogEntry(debugInfo[0]))
        cs.MDebug[cID] = len(cs.DebugInfo) - 1
    }

    cs.UpdateLevel(cID, &r1c)

    return cID
}

Everything runs correctly but the execution doesn't go beyond `UpdateLevel()`, which is a passthrough method that calls another `updateLevel` in the [`level_builder.go` module](https://github.com/ConsenSys/gnark/blob/master/constraint/level_builder.go)

func (r1cs *R1CSCore) UpdateLevel(cID int, c Iterable) {
    r1cs.updateLevel(cID, c)
}

where the real "update level" logic lies

func (system *System) updateLevel(cID int, c Iterable) {
    system.lbOutputs = system.lbOutputs[:0]
    system.lbHints = map[*Hint]struct{}{}
    level := -1
    wireIterator := c.WireIterator()
    for wID := wireIterator(); wID != -1; wID = wireIterator() {
        // iterate over all wires of the R1C
        system.processWire(uint32(wID), &level)
    }

    // level =  max(dependencies) + 1
    level++

    // mark output wire with level
    for _, wireID := range system.lbOutputs {
        for int(wireID) >= len(system.lbWireLevel) {
            // we didn't encounter this wire yet, we need to grow b.wireLevels
            system.lbWireLevel = append(system.lbWireLevel, -1)
        }
        system.lbWireLevel[wireID] = level
    }

    // we can't skip levels, so appending is fine.
    if level >= len(system.Levels) {
        system.Levels = append(system.Levels, []int{cID})
    } else {
        system.Levels[level] = append(system.Levels[level], cID)
    }
}

This is not the function where the infinite, it is `processWire` in this loop

for wID := wireIterator(); wID != -1; wID = wireIterator() {
    // iterate over all wires of the R1C
    system.processWire(uint32(wID), &level)
}

This `for` iterates successfully until the `wID` which corresponds to `VID` in the `wireIterator`, corresponds to the `VID` of the term that is set to be the max `uint32`. Let's get into `processWire`

func (system *System) processWire(wireID uint32, maxLevel *int) {
	if wireID < uint32(system.GetNbPublicVariables()+system.GetNbSecretVariables()) {
		return // ignore inputs
	}

	for int(wireID) >= len(system.lbWireLevel) {
		// we didn't encounter this wire yet, we need to grow b.wireLevels
		system.lbWireLevel = append(system.lbWireLevel, -1)
	}

	if system.lbWireLevel[wireID] != -1 {
		// we know how to solve this wire, it's a dependency
		if system.lbWireLevel[wireID] > *maxLevel {
			*maxLevel = system.lbWireLevel[wireID]
		}
		return
	}
	// we don't know how to solve this wire; it's either THE wire we have to solve or a hint.
	if h, ok := system.MHints[int(wireID)]; ok {
		// check that we didn't process that hint already; performance wise, if many wires in a
		// constraint are the output of the same hint, and input to parent hint are themselves
		// computed with a hint, we can suffer.
		// (nominal case: not too many different hints involved for a single constraint)
		if _, ok := system.lbHints[h]; ok {
			// skip
			return
		}
		system.lbHints[h] = struct{}{}

		for _, hwid := range h.Wires {
			system.lbOutputs = append(system.lbOutputs, uint32(hwid))
		}
		for _, in := range h.Inputs {
			for _, t := range in {
				if !t.IsConstant() {
					system.processWire(t.VID, maxLevel)
				}
			}
		}

		return
	}

	// it's the missing wire
	system.lbOutputs = append(system.lbOutputs, wireID)
}

It is a big function but our infinite loop lies in the first `for while` loop

for int(wireID) >= len(system.lbWireLevel) {
    // we didn't encounter this wire yet, we need to grow b.wireLevels
    system.lbWireLevel = append(system.lbWireLevel, -1)
}

At this point, if you would like to figure out by yourself why this is an infinite loop, remember that `wireID` is the max `uint32` value and consider that `len()` returns a value of type `int`.

## Why it loops infinitely and could consume your memory

If you didn't come to a conclusion, let me be your guest. This Golang `while` will loop infinitely because the condition won't be false because `len()` could never be able to return a value bigger than `wireID`. This is the reason for the infinite loop, and the reason for the memory usage is the line that is inside the `for`'s scope. It is appending a `-1` every iteration meaning a 4 to 8 byte memory usage increase every cycle.

With this said, you probably figured out that the bug could not only be caused because of marking a term as constant but also by setting a high `CID` for the term!

## Call Trace

flowchart 
    AC[AddConstraint] --> UL[UpdateLevel]
    UL[UpdateLevel] --> UL2[updateLevel]
    UL2[updateLevel] --> PW[processWire]