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 a, denote a vector. Variables not in bold, like v, denote a scalar. The operator ∘ is the Hadamard product (elementwise multiplication) of two vectors, i.e. [a1,…,an]∘[b1,…,bn]=[a1b1,…,anbn]. 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 1 vector is a vector of all ones, i.e. [1,1,…,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 ⟨a+b,c⟩. We can split this up into the sum of two inner products:
⟨a+b,c⟩=⟨a,c⟩+⟨b,c⟩
Proof:
The lhs can be written as
i=1∑n(ai+bi)ci
The rhs can be written as
i=1∑naici+i=1∑ncibi=i=1∑n(aici+cibi)=i=1∑n(ai+bi)ci
Rule 2: Inner products with common terms can be combined
The two inner products on the lhs below have a common vector of c. Therefore, they can be combined:
⟨a,c⟩+⟨b,c⟩=⟨a+b,c⟩
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 1 vector with the Hadamard product of the original vectors:
⟨a,b⟩=⟨1,a∘b⟩
Proof:
⟨a,b⟩⟨1,a∘b⟩i=1∑naibi=i=1∑naibi=i=1∑n1∗(aibi)=i=1∑n1∗(aibi)
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 ⟨x,b+c⟩ and an inner product ⟨y,b⟩, 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
⟨x,b+c⟩+⟨y,b⟩=v
can be written as
⟨x+y,b+c⟩=v+⟨y,c⟩
In the above scenario, we can add ⟨y,c⟩ to both sides.
⟨x,b+c⟩+⟨y,b⟩+⟨y,c⟩⟨x,b+c⟩+⟨y,b⟩+⟨y,c⟩=v+⟨y,c⟩=v+⟨y,c⟩
We now have common y terms we can combine using Rule 2:
⟨x,b+c⟩+⟨y,b⟩+⟨y,c⟩⟨x,b+c⟩+⟨y,b+c⟩⟨x,b+c⟩+⟨y,b+c⟩=v+⟨y,c⟩=v+⟨y,c⟩=v+⟨y,c⟩
Now that we have forced the two inner products to have common term ⟨b+c⟩ on the lhs, we can combine them into one vector using Rule 2 again:
⟨x,b+c⟩+⟨y,b+c⟩⟨x+y,b+c⟩⟨x+y,b+c⟩=v+⟨y,c⟩=v+⟨y,c⟩=v+⟨y,c⟩
Therefore,
⟨x,b+c⟩+⟨y,b⟩=v
can be rewritten as
⟨x+y,b+c⟩=v+⟨y,c⟩
We can add ⟨a1,b1⟩+⟨a2,b2⟩ (which have no vectors in common) and obtain:
⟨a1,b1⟩+⟨a2,b2⟩=⟨a1+a2,b1+b2⟩−⟨a1,b2⟩−⟨a2,b1⟩
Proof:
⟨a1,b1⟩+⟨a2,b2⟩⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩+⟨a2,b1⟩⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩+⟨a2,b1⟩⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩+⟨a2,b1⟩⟨a1,b1⟩+⟨a2,b2⟩=⟨a1,b1⟩+⟨a2,b2⟩=⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩=⟨a1,b1⟩+⟨a1+a2,b2⟩=⟨a1,b1⟩+⟨a1+a2,b2⟩+⟨a2,b1⟩=⟨a1+a2,b1⟩+⟨a1+a2,b2⟩=⟨a1+a2,b1+b2⟩=⟨a1+a2,b1+b2⟩−⟨a1,b2⟩−⟨a2,b1⟩add ⟨a1,b2⟩ to both sidescombine b2 termsadd ⟨a2,b1⟩ to both sidescombine b1 termscombine right-hand sidesubtract ⟨a1,b2⟩+⟨a2,b1⟩
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⋅⟨a,b⟩=⟨z⋅a,b⟩=⟨a,z⋅b⟩
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.