Capstok — learn by doing

Why this matters

When an HE engineer says a scheme 'supports depth-12 circuits,' they almost always mean multiplicative depth 12 — the longest chain of multiplications from input to output, ignoring additions. Why do we count multiplications and not additions? Because in lattice HE, additions are nearly free in noise terms while multiplications are expensive. The depth count is the single most important quantity that determines the cost of an HE evaluation — it sets the modulus size, which sets the ring dimension, which sets the runtime and memory. Moreover, this isn't just bookkeeping. It changes how you write algorithms: a textbook algorithm with $\log n$ multiplicative depth might be brutally expensive, while a carefully restructured one with constant depth is cheap. Learning to read circuits by their multiplicative depth — and to rewrite them to reduce it — is the core algorithmic skill of HE programming.

Demo

The multiplicative depth of a circuit is the maximum number of multiplication gates on any input-to-output path. A polynomial like $a \cdot b \cdot c \cdot d$ has multiplicative depth 3 if computed left-to-right ( $((a \cdot b) \cdot c) \cdot d$ ) but depth 2 if computed as a tree ( $(a \cdot b) \cdot (c \cdot d)$ ). Reducing depth by re-associating is a free win in HE; reducing depth by replacing a multiplication with additions is the real game.

\mathrm{depth}_\times(C) = \max_{\text{path } p \in C} \#\{\text{mult gates on } p\}.\quad \text{Cost: } q \sim 2^{O(\mathrm{depth}_\times \cdot \log n)}.

Try it yourself

Run the snippet. The linear chain has depth 7, the tree has depth 3. Both compute $x^8$ . The tree fits in a smaller noise budget — that's the entire reason HE compilers re-associate.
Build the circuit for $x^{16}$ both ways and confirm linear depth 15 vs. tree depth 4. The gap grows; for $x^{2^k}$ the saving is vs .

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

In one paragraph, explain why HE engineers obsess over multiplicative depth and barely mention additive depth. Use the noise-growth picture from the previous task.

2. Why it works (the mechanism)

Walk me through how a circuit's multiplicative depth determines the ciphertext modulus $q$, which in turn determines the ring dimension $n$, which determines the cost of a single multiplication. Where does each link in the chain come from?

3. Advanced — application & what's next

I have a function $f$ that, written naively, has multiplicative depth 30, which is too deep for SHE. Walk me through three techniques to reduce depth: re-association, polynomial approximation of non-polynomial gates, and lookup-table evaluation. When does each apply?

References

// main.go
// Two equivalent computations of x^8, with very different multiplicative depths.
// We model a circuit as a tree and compute its multiplicative depth.
package main

import "fmt"

type NodeKind int

const (
	KindVar NodeKind = iota
	KindMul
	KindAdd
)

type Node struct {
	Kind NodeKind
	Name string // for Var
	A, B *Node  // for Mul/Add
}

func Var(name string) *Node { return &Node{Kind: KindVar, Name: name} }
func Mul(a, b *Node) *Node  { return &Node{Kind: KindMul, A: a, B: b} }
func Add(a, b *Node) *Node  { return &Node{Kind: KindAdd, A: a, B: b} }

func multDepth(n *Node) int {
	switch n.Kind {
	case KindVar:
		return 0
	case KindAdd:
		a, b := multDepth(n.A), multDepth(n.B)
		if a > b {
			return a
		}
		return b
	case KindMul:
		a, b := multDepth(n.A), multDepth(n.B)
		if a > b {
			return 1 + a
		}
		return 1 + b
	}
	return 0
}

func main() {
	x := Var("x")

	// Naive: x^8 = ((((((x*x)*x)*x)*x)*x)*x)*x
	linear := x
	for i := 0; i < 7; i++ {
		linear = Mul(linear, x)
	}

	// Tree: x^8 = ((x*x) * (x*x)) * ((x*x) * (x*x))
	x2 := Mul(x, x)
	x4 := Mul(x2, x2)
	tree := Mul(x4, x4)

	fmt.Println("x^8 linear chain — multiplicative depth:", multDepth(linear))
	fmt.Println("x^8 binary tree   — multiplicative depth:", multDepth(tree))
}

Run: go run main.go

Circuit depth and multiplicative depth