Inner Product Algebra

In this article, we give some useful algebraic tricks for inner products that will be useful in deriving range proofs (and encoding circuits as inner products) later. Each rule will be accompanied by a simple proof.

Notation

Variables in bold, like $\mathbf{a}$, denote a vector. Variables not in bold, like $v$, denote a scalar. The operator $\circ$ is the Hadamard product (elementwise multiplication) of two vectors, i.e. $[a_1, \dots, a_n]\circ[b_1, \dots, b_n] = [a_1b_1, \dots, a_nb_n]$. We use the shorthand “lhs” and “rhs” to refer to the “left-hand side” and “right-hand side” of an equation, respectively. A “summand” is an element of an addition, e.g. if $a + b = c$, then $a$ and $b$ would be called summands. The $\mathbf{1}$ vector is a vector of all ones, i.e. $[1, 1, \dots, 1]$. All vectors are implied to be of the same length $n$ unless otherwise stated.

Rule 1: An inner product where one of the vectors is a sum of vectors can be expanded

Suppose we’re calculating an inner product where one of the vectors is a sum of two vectors – for example $\langle\mathbf{a} + \mathbf{b}, \mathbf{c}\rangle$. We can split this up into the sum of two inner products: $\langle \mathbf{a} + \mathbf{b}, \mathbf{c} \rangle = \langle \mathbf{a}, \mathbf{c}\rangle + \langle \mathbf{b}, \mathbf{c} \rangle$

Proof: The lhs can be written as $$ \sum_{i=1}^n(a_i+b_i)c_i $$

The rhs can be written as

$$ \begin{align*} \sum_{i=1}^na_ic_i+\sum_{i=1}^nc_ib_i &=\sum_{i=1}^n(a_ic_i+c_ib_i) \\ &=\sum_{i=1}^n(a_i+b_i)c_i \end{align*} $$

Rule 2: Inner products with common terms can be combined

The two inner products on the lhs below have a common vector of $\mathbf{c}$. Therefore, they can be combined: $$\langle \mathbf{a}, \mathbf{c}\rangle + \langle \mathbf{b}, \mathbf{c} \rangle = \langle \mathbf{a} + \mathbf{b}, \mathbf{c} \rangle$$

This is really Rule 1 with the lhs and the rhs swapped.

The proof is the same as Rule 1.

Rule 3: Moving vectors to the other side of the inner product

An inner product can be re-written as the $\mathbf{1}$ vector with the Hadamard product of the original vectors: $$\langle \mathbf{a}, \mathbf{b} \rangle= \langle \mathbf{1}, \mathbf{a\circ b} \rangle$$

Proof:

$$\begin{align*} \langle \mathbf{a}, \mathbf{b} \rangle&=\sum_{i=1}^na_ib_i \\ \langle \mathbf{1}, \mathbf{a\circ b} \rangle&=\sum_{i=1}^n1*(a_ib_i)\\ \sum_{i=1}^na_ib_i &= \sum_{i=1}^n1*(a_ib_i)\\ \end{align*}$$

Rule 4: We can add vectors to one of the terms of the inner product to force two inner products to have common terms

Suppose we’re adding an inner product $\langle\mathbf{x}, \mathbf{b}+\mathbf{c}\rangle$ and an inner product $\langle\mathbf{y}, \mathbf{b}\rangle$, and the sum of the inner products is $v$. Note that they have different components, so we can’t add them with Rule 2. Nevertheless, the following equality

$$\langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle = v$$

can be written as

$$\langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle = v + \langle\mathbf{y},\mathbf{c}\rangle$$

In the above scenario, we can add $\langle\mathbf{y},\mathbf{c}\rangle$ to both sides.

$$\begin{align*} \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle + \boxed{\langle\mathbf{y},\mathbf{c}\rangle}&= v + \boxed{\langle\mathbf{y},\mathbf{c}\rangle}\\ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle + \langle\mathbf{y},\mathbf{c}\rangle&= v + \langle\mathbf{y},\mathbf{c}\rangle \end{align*}$$

We now have common $\mathbf{y}$ terms we can combine using Rule 2:

$$\begin{align*} \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{\fbox{y}}, \mathbf{b}\rangle + \langle\mathbf{\fbox{y}},\mathbf{c}\rangle&= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{\fbox{y}}, \mathbf{b} + \mathbf{c}\rangle &= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle &= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \end{align*}$$

Now that we have forced the two inner products to have common term $\langle \mathbf{b} + \mathbf{c} \rangle$ on the lhs, we can combine them into one vector using Rule 2 again:

$$\begin{align*} \langle \mathbf{x}, \boxed{\mathbf{b} + \mathbf{c}}\rangle + \langle \mathbf{y}, \boxed{\mathbf{b} + \mathbf{c}}\rangle &= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \langle \mathbf{x} + \mathbf{y}, \boxed{\mathbf{b} + \mathbf{c}}\rangle &= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle &= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \end{align*}$$

Therefore,

$$\langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle = v$$

can be rewritten as

$$\langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle = v + \langle\mathbf{y},\mathbf{c}\rangle$$

Rule 5: Adding two inner products with unrelated vectors

We can add $\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle$ (which have no vectors in common) and obtain:

$$\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle=\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_1+\mathbf{b}_2\rangle-\langle\mathbf{a_1},\mathbf{b_2}\rangle-\langle\mathbf{a_2},\mathbf{b_1}\rangle$$

Proof:

$$\begin{align*} \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle&=\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle&=\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle&&\text{add }\langle\mathbf{a}_1,\mathbf{b}_2\rangle \text{ to both sides}\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle&=\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_2\rangle&&\text{combine }\mathbf{b}_2 \text{ terms}\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle+\langle\mathbf{a}_2,\mathbf{b}_1\rangle&=\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_2,\mathbf{b}_1\rangle&&\text{add }\langle\mathbf{a}_2,\mathbf{b}_1\rangle\text{ to both sides}\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle+\langle\mathbf{a}_2,\mathbf{b}_1\rangle&=\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_1\rangle+\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_2\rangle&&\text{combine }\mathbf{b}_1\text{ terms}\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle+\langle\mathbf{a}_2,\mathbf{b}_1\rangle&=\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_1+\mathbf{b}_2\rangle&&\text{combine right-hand side}\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle&=\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_1+\mathbf{b}_2\rangle-\langle\mathbf{a}_1,\mathbf{b}_2\rangle-\langle\mathbf{a}_2,\mathbf{b}_1\rangle&&\text{subtract }\langle\mathbf{a}_1,\mathbf{b}_2\rangle+\langle\mathbf{a}_2,\mathbf{b}_1\rangle \end{align*}$$

The proof illustrates that it may be handy sometimes to be creative about finding inner products to add to both sides of the equation.

Rule 6: Scalars can be brought inside and outside of an inner product

$z\cdot\langle\mathbf{a},\mathbf{b}\rangle = \langle z\cdot\mathbf{a},\mathbf{b}\rangle = \langle\mathbf{a},z\cdot\mathbf{b}\rangle$

The proof for this statement is left as an exercise for the reader. As a hint, constant terms can be brought in and out of a summation.

This tutorial is part of our series on ZK Bulletproofs.

Public and Private Inputs

Public and Private Inputs A public input in Circom is a signal in the witness that will be revealed to the verifier. For example, suppose we want to create a ZK proof that states: “we know the input to a hash that produced 0x492c…9254.” To make this claim meaningful, the value 0x492c…9254 (the target hash […]

Circle FFT — Part 1: Building the Circle Domain

Circle FFT — Part 1: Building the Circle Domain Circle STARKs is a new zk-STARK scheme that has been implemented in Stwo and Plonky3, and it has been adopted by several zkVM projects. Its key innovation lies in enabling the use of small 32-bit fields (Mersenne prime $2^{31}-1$) while still maintaining the mathematical properties needed for efficient FFT operations. […]

Multiplicative Subgroups and Primitive Elements

Multiplicative Subgroups and Primitive Elements Introduction This chapter continues our study of group theory by exploring subgroups and generators. The concept of a primitive element will be introduced at the end. We assume you are already familiar with the definition of a group. If you need a refresher, check out this article. To build intuition, […]

Square and Multiply Algorithm

Square and Multiply Algorithm The square and multiply algorithm computes integer exponents in $\mathcal{O}(\log n)$ (logarithmic time). The naive way to compute an exponent $x^n$ is to multiply $x$ by itself, $n$ times, which would require $\mathcal{O}(n)$ time to compute. Suppose we want to compute $x^{20}$. Instead of multiplying $x$ with itself 20 times, we […]

Opportunities

Looking for an audit?

Leverage our extensive network of top security specialists.

Get A Quote
Applied ZK Engineer

Join us to build the privacy layer bringing real-world assets on-chain tackling the toughest problems in zero-knowledge and traditional finance.

Learn More
Developer Relations Engineer

A team of ecosystem builders on a mission to scale decentralized tech driven by a fast, parallel EVM Layer 1 blockchain built for powerful dApps.

Learn More
Anchor Engineer (Solidity)

Founding smart contract engineer role to build core protocols connecting on-chain yield with real-world assets.

Learn More