Math Guide Mathematical foundations for Halo 2 and Zcash Orchard 7 Number theory for cryptography 9 Roots of unity and evaluation domains

8 Linear algebra over a field

Begin with the engineering problem that shapes the whole section. A prover holds a list of $n$ secret numbers—the intermediate values of some large computation, the wire values of an arithmetic circuit in the vocabulary of later volumes, with $n$ in the millions, say—and must hand a verifier a receipt for the list: a single short object that pins the list down, to be opened or argued about later. Two demands make the problem interesting. The receipt must be one element of some fixed algebraic structure, however large $n$ grows; and receipts must add—whoever holds the receipts for two lists, together with two scaling factors, must be able to compute the receipt for the scaled sum of the lists without ever seeing the lists themselves. The construction that meets both demands is disarmingly brief: fix $n$ public elements $G_{1},\dots,G_{n}$ of a suitable group, and issue for the list $(a_{1},\dots,a_{n})$ the single group element $[a_{1}]G_{1}+\dots+[a_{n}]G_{n}$ . Whether this can possibly work—what “receipts add” should mean exactly, how one group element can absorb $n$ secrets, and what price in ambiguity the compression exacts—are questions of linear algebra, and answering them is the business of this section.

Linear algebra is the study of vector spaces—collections of objects that can be added together and scaled by elements of a field—together with the structure-preserving maps between them. It is the computational backbone of the cryptography this monograph serves: commitments to vectors, the linear constraints that encode arithmetic circuits, the polynomial-evaluation arguments at the heart of the inner-product argument, and the Pedersen-style multiscalar multiplications of Halo 2 and Orchard are all, at bottom, statements about linear maps and (bi)linear forms over a finite field. The section develops the theory from the ground up, assuming only the notion of a field (4), and then specialises to the two settings that matter here: the coordinate space $F^{n}$ , in practice taken over a finite field $\mathbb{F}_{q}$ , and the “mixed” pairing between vectors of scalars and vectors of group elements.

The section also settles two debts contracted below it. Remark 5.5 promised that the linear structure of $F[X]$ —closure under addition and scaling, with the monomials as an infinite coordinate system—would be studied systematically in due course; the study happens here. And the proof of Theorem 6.9 borrowed, against a promissory note, exactly two facts about vector spaces: that a space with a finite spanning set has a basis, and that coordinates with respect to a basis are unique. The first is proved in Theorem 8.17; the second follows from linear independence, as recorded in Definition 8.14. These arguments use nothing from the theory of finite fields, so the note is honoured without circularity. Throughout, $F$ denotes an arbitrary field with identities $0$ and $1$ ; the field axioms of Definition 4.24 are used freely and without citation.

8.1 Vector spaces and subspaces

Definition 8.1 (Vector space).

Let $F$ be a field. A vector space over $F$ (an $F$ -vector space) is a set $V$ equipped with two operations, vector addition $+\colon V\times V\to V$ and scalar multiplication $\cdot\colon F\times V\to V$ , such that for all $u,v,w\in V$ and all $a,b\in F$ :

1.

$(V,+)$ is an abelian group: addition is associative and commutative, there is a zero vector $\mathbf{0}\in V$ with $v+\mathbf{0}=v$ , and every $v$ has an additive inverse $-v$ with $v+(-v)=\mathbf{0}$ ;
2.

scalar multiplication is compatible with the multiplication of $F$ : $a\cdot(b\cdot v)=(ab)\cdot v$ ;
3.

the identity of $F$ acts as the identity: $1\cdot v=v$ ;
4.

scalar multiplication distributes over vector addition: $a\cdot(u+v)=a\cdot u+a\cdot v$ ;
5.

scalar multiplication distributes over scalar addition: $(a+b)\cdot v=a\cdot v+b\cdot v$ .

The elements of $V$ are called vectors, the elements of $F$ scalars. We write $a v$ for $a\cdot v$ , and we allow the scalar $0\in F$ and the vector $\mathbf{0}\in V$ to share a symbol whenever context distinguishes them.

A few consequences of the axioms recur so often that we record them once and, thereafter, use them without comment.

Proposition 8.2.

Let $V$ be an $F$ -vector space, $v\in V$ , and $a\in F$ . Then:

1.

$0\cdot v=\mathbf{0}$ ;
2.

$a\cdot\mathbf{0}=\mathbf{0}$ ;
3.

$(-1)\cdot v=-v$ ;
4.

if $av=\mathbf{0}$ , then $a=0$ or $v=\mathbf{0}$ .

Proof.

(1) By distributivity over scalar addition, $0\cdot v=(0+0)\cdot v=0\cdot v+0\cdot v$ ; adding $-(0\cdot v)$ to both sides leaves $\mathbf{0}=0\cdot v$ .

(2) Likewise $a\cdot\mathbf{0}=a\cdot(\mathbf{0}+\mathbf{0})=a\cdot\mathbf{0}+a\cdot\mathbf{0}$ , and cancelling in the abelian group $(V,+)$ gives $a\cdot\mathbf{0}=\mathbf{0}$ .

(3) Using the identity axiom, distributivity, and (1),

v+(-1)\cdot v=1\cdot v+(-1)\cdot v=\bigl{(}1+(-1)\bigr{)}\cdot v=0\cdot v=% \mathbf{0},

so $(-1)\cdot v$ is the additive inverse of $v$ ; by uniqueness of inverses in a group, $(-1)\cdot v=-v$ .

(4) Suppose $av=\mathbf{0}$ and $a\neq 0$ . Since $F$ is a field, $a^{-1}$ exists, and by the identity and compatibility axioms

v=1\cdot v=(a^{-1}a)\cdot v=a^{-1}\cdot(av)=a^{-1}\cdot\mathbf{0}=\mathbf{0},

the last step by (2). □

Example 8.3 (The coordinate space $F^{n}$ ).

The single most important example is the coordinate space

F^{n}=\{\,(x_{1},\dots,x_{n}):x_{i}\in F\,\},

the set of $n$ -tuples of scalars, under componentwise operations:

(x_{1},\dots,x_{n})+(y_{1},\dots,y_{n})=(x_{1}+y_{1},\dots,x_{n}+y_{n}),\qquad a% \cdot(x_{1},\dots,x_{n})=(ax_{1},\dots,ax_{n}).

The zero vector is $(0,\dots,0)$ , and every axiom of 8.1 follows from the corresponding field axiom applied in each coordinate. The degenerate case $n=0$ is the trivial (or zero) vector space $\{\mathbf{0}\}$ , consisting of the empty tuple alone. As a standing convention we write vectors of $F^{n}$ in boldface and think of them as columns, $\mathbf{x}=(x_{1},\dots,x_{n})^{\mathsf{T}}$ .

Example 8.4 (Further examples).

1.

Polynomials. The polynomials $F[X]$ form an $F$ -vector space under addition and the scalar multiplication of Remark 5.5. So does the subset

$F[X]_{<n}=\{\,f\in F[X]:f=0\text{ or }\deg f<n\,\}$

of polynomials of degree less than $n$ : sums and scalar multiples of such polynomials again have degree less than $n$ (or are zero), by Proposition 5.7, so the operations restrict and the axioms are inherited. This space is exactly the setting in which polynomial commitment schemes operate.
2.

Functions. For any set $S$ , the set $F^{S}$ of all functions $S\to F$ is an $F$ -vector space under pointwise operations: $(f+g)(s)=f(s)+g(s)$ and $(af)(s)=a\,f(s)$ . Example 8.3 is the special case $S=\{1,\dots,n\}$ , a tuple being a function of its index.
3.

Matrices. The set $F^{m\times n}$ of $m\times n$ arrays of scalars is an $F$ -vector space under entrywise addition and scaling—the case of (2) in which $S$ is the grid of index pairs $(i,j)$ .
4.

Field extensions. If $F$ is a subfield of a larger field $K$ (§4), then $K$ is an $F$ -vector space: vector addition is the addition of $K$ , and scalar multiplication is the multiplication of $K$ restricted to pairs in $F\times K$ , so the axioms are instances of the field axioms of $K$ . The dimension of this vector space—in the sense of 8.17 below—is called the degree of the extension, written $[K:F]$ . For instance $\mathbb{C}$ is an $\mathbb{R}$ -vector space of dimension $2$ , with basis $1,i$ , so $[\mathbb{C}:\mathbb{R}]=2$ ; and the finite field $\mathbb{F}_{q}$ with $q=p^{k}$ is a $k$ -dimensional $\mathbb{F}_{p}$ -vector space, $[\mathbb{F}_{q}:\mathbb{F}_{p}]=k$ : this is precisely the structure on which the proof of Theorem 6.9 rested.

A vector space often contains smaller vector spaces sitting inside it, sharing its operations; the solution sets of homogeneous linear equations, the spans of the next subsection, and the kernels and images of linear maps are all of this kind.

Definition 8.5 (Subspace).

A subset $W\subseteq V$ of an $F$ -vector space $V$ is a (linear) subspace if $W$ is itself a vector space under the operations inherited from $V$ ; equivalently—as the next proposition makes precise—if and only if $W$ is nonempty and closed under the vector-space operations.

Proposition 8.6 (Subspace criterion).

A subset $W\subseteq V$ is a subspace if and only if

1.

$\mathbf{0}\in W$ ;
2.

$W$ is closed under addition: $u,v\in W$ implies $u+v\in W$ ; and
3.

$W$ is closed under scalar multiplication: $a\in F$ and $v\in W$ imply $av\in W$ .

Equivalently, $W$ is a subspace if and only if $W\neq\varnothing$ and $au+bv\in W$ for all $a,b\in F$ and $u,v\in W$ .

Proof.

If $W$ is a subspace, then (1)–(3) hold: closure (2) and (3) is what it means for the inherited operations to be operations on $W$ , and the zero vector of $W$ is the zero vector of $V$ , since a zero vector $\mathbf{0}_{W}$ of $W$ satisfies $\mathbf{0}_{W}+\mathbf{0}_{W}=\mathbf{0}_{W}$ , and cancelling in $V$ gives $\mathbf{0}_{W}=\mathbf{0}$ .

Conversely, suppose (1)–(3) hold. Closure makes the two operations well defined on $W$ . The additive inverse of any $v\in W$ is $(-1)v\in W$ , by (3) and Proposition 8.2(3). Every remaining axiom of 8.1 is a universally quantified identity—associativity, commutativity, compatibility, the two distributive laws, the action of $1$ —and each holds for all elements of $V$ , in particular for all elements of $W$ . Hence $W$ is a vector space.

For the two-scalar form: if $W$ is a subspace, then $au+bv\in W$ by (2) and (3) combined, and $W\ni\mathbf{0}$ is nonempty. Conversely, choosing $(a,b)=(1,1)$ recovers (2), choosing $(a,b)=(a,0)$ recovers (3) (using Proposition 8.2(1) to identify $0v$ ), and $\mathbf{0}=0v\in W$ for any $v$ in the nonempty $W$ , which is (1). □

Example 8.7.

In $F^{3}$ the set $W=\{\,(x_{1},x_{2},x_{3}):x_{1}+x_{2}+x_{3}=0\,\}$ is a subspace: it contains $\mathbf{0}$ , and if the coordinates of $\mathbf{x}$ and $\mathbf{y}$ each sum to $0$ , then those of $a\mathbf{x}+b\mathbf{y}$ sum to $a\cdot 0+b\cdot 0=0$ . By contrast $\{\,(x_{1},x_{2},x_{3}):x_{1}+x_{2}+x_{3}=1\,\}$ is not a subspace: it does not contain $\mathbf{0}$ . The same computation shows that the solution set of any single homogeneous linear equation $c_{1}x_{1}+\dots+c_{n}x_{n}=0$ (the $c_{i}$ fixed scalars) is a subspace of $F^{n}$ , and the solution set of a finite system of such equations, being an intersection of subspaces, is a subspace by the next proposition. These solution sets return shortly in structural guise, as the kernels of linear maps (8.18).

Proposition 8.8 (Intersections and sums).

Let $V$ be an $F$ -vector space.

1.

The intersection $\bigcap_{i\in I}W_{i}$ of an arbitrary family of subspaces of $V$ is a subspace.
2.

The sum $W_{1}+\dots+W_{k}=\{\,w_{1}+\dots+w_{k}:w_{j}\in W_{j}\,\}$ of finitely many subspaces is a subspace, and it is the smallest subspace of $V$ containing every $W_{j}$ .

The union of two subspaces is in general not a subspace.

Proof.

(1) Each $W_{i}$ contains $\mathbf{0}$ , so the intersection does. If $u, v$ lie in every $W_{i}$ and $a,b\in F$ , then $au+bv\in W_{i}$ for every $i$ by Proposition 8.6, hence $au+bv$ lies in the intersection, which is therefore a subspace by the same criterion.

(2) The sum contains $\mathbf{0}=\mathbf{0}+\dots+\mathbf{0}$ , and it contains each $W_{j}$ (take every other summand $\mathbf{0}$ ). For closure, take two elements $\sum_{j}w_{j}$ and $\sum_{j}w_{j}^{\prime}$ with $w_{j},w_{j}^{\prime}\in W_{j}$ , and scalars $a, b$ ; regrouping,

a\sum_{j}w_{j}+b\sum_{j}w_{j}^{\prime}=\sum_{j}\bigl{(}aw_{j}+bw_{j}^{\prime}% \bigr{)},

and $aw_{j}+bw_{j}^{\prime}\in W_{j}$ since $W_{j}$ is a subspace, so the combination lies in the sum. Finally, any subspace $U$ containing every $W_{j}$ contains each summand $w_{j}$ of any element of the sum, hence contains the element itself by closure under addition; so the sum is contained in $U$ , and is the smallest such subspace.

For the union, take $V=F^{2}$ (any field has $|F|>1$ , since $1\neq 0$ ) and the two axes $\{(x,0):x\in F\}$ and $\{(0,y):y\in F\}$ —subspaces by the criterion. Their union contains $(1,0)$ and $(0,1)$ but not the sum $(1,1)=(1,0)+(0,1)$ , since $(1,1)$ lies on neither axis; closure under addition fails. □

8.2 Linear combinations, span, and linear independence

The subspaces met so far were carved out by equations. The complementary way to produce a subspace is to build one up from chosen vectors, taking everything their repeated addition and scaling can reach.

Definition 8.9 (Linear combination and span).

Let $S\subseteq V$ . A linear combination of vectors in $S$ is any finite sum

a_{1}v_{1}+a_{2}v_{2}+\dots+a_{k}v_{k},\qquad a_{i}\in F,\ v_{i}\in S.

The span of $S$ , written $\operatorname{span}(S)$ or $\langle S\rangle$ , is the set of all linear combinations of finitely many vectors of $S$ ; by convention $\operatorname{span}(\varnothing)=\{\mathbf{0}\}$ . The set $S$ spans (or generates) $V$ if $\operatorname{span}(S)=V$ , and $V$ is finitely generated (synonymously, finite-dimensional) if some finite set spans it.

Proposition 8.10.

For any $S\subseteq V$ , the span $\operatorname{span}(S)$ is the smallest subspace of $V$ containing $S$ : it is a subspace, it contains $S$ , and it is contained in every subspace of $V$ that contains $S$ .

Proof.

The zero vector is the empty linear combination (or, for nonempty $S$ , the combination $0v$ ), and a sum of two linear combinations of vectors in $S$ , or a scalar multiple of one, is again such a linear combination—concatenate the lists and rescale the coefficients. By Proposition 8.6, $\operatorname{span}(S)$ is a subspace, and it contains each $v\in S$ as the combination $1\cdot v$ . If $W$ is any subspace containing $S$ , then closure under addition and scaling forces every linear combination of elements of $S$ into $W$ , by induction on the number of summands; hence $\operatorname{span}(S)\subseteq W$ . □

Definition 8.11 (Linear independence).

A finite list of vectors $v_{1},\dots,v_{k}\in V$ is linearly independent if the only way to express the zero vector as a linear combination of the list is with all coefficients zero:

a_{1}v_{1}+\dots+a_{k}v_{k}=\mathbf{0}\quad\Longrightarrow\quad a_{1}=\dots=a_% {k}=0.

Otherwise the list is linearly dependent, and a relation $\sum_{i}a_{i}v_{i}=\mathbf{0}$ with some $a_{i}\neq 0$ is called a dependence relation. An arbitrary—possibly infinite—set $S\subseteq V$ is linearly independent if every finite list of distinct vectors from $S$ is linearly independent.

Remark 8.12.

Linear independence captures non-redundancy: no vector of an independent list contributes anything the others already provide. In the smallest cases the definition unwinds to familiar statements. A single vector $v$ is independent if and only if $v\neq\mathbf{0}$ (Proposition 8.2(4)). Two vectors are dependent if and only if one is a scalar multiple of the other. In general, a list is dependent exactly when some vector in it lies in the span of the others—the content of the next lemma.

Lemma 8.13 (Dependence and redundancy).

A list $v_{1},\dots,v_{k}$ with $k\geq 1$ is linearly dependent if and only if some $v_{j}$ is a linear combination of the others. Moreover, if $v_{1},\dots,v_{k}$ is independent but $v_{1},\dots,v_{k},w$ is dependent, then $w\in\operatorname{span}(v_{1},\dots,v_{k})$ , and the coefficients expressing $w$ are unique.

Proof.

Suppose first that $v_{j}=\sum_{i\neq j}a_{i}v_{i}$ . Then

\sum_{i\neq j}a_{i}v_{i}+(-1)\,v_{j}=\mathbf{0}

is a dependence relation, its coefficient $-1$ on $v_{j}$ being nonzero (as $1\neq 0$ in a field). Conversely, given a dependence relation $\sum_{i}a_{i}v_{i}=\mathbf{0}$ with $a_{j}\neq 0$ , the field supplies $a_{j}^{-1}$ , and solving for $v_{j}$ gives $v_{j}=-a_{j}^{-1}\sum_{i\neq j}a_{i}v_{i}$ , a linear combination of the others.

For the second statement, take a dependence relation $\sum_{i}a_{i}v_{i}+bw=\mathbf{0}$ for the extended list. The coefficient $b$ cannot be $0$ : otherwise the relation would be a nontrivial relation among $v_{1},\dots,v_{k}$ alone, contradicting their independence. Hence $w=-b^{-1}\sum_{i}a_{i}v_{i}\in\operatorname{span}(v_{1},\dots,v_{k})$ . For uniqueness, suppose $w=\sum_{i}c_{i}v_{i}=\sum_{i}c_{i}^{\prime}v_{i}$ ; subtracting, $\sum_{i}(c_{i}-c_{i}^{\prime})v_{i}=\mathbf{0}$ , and independence forces $c_{i}=c_{i}^{\prime}$ for every $i$ . □

8.3 Bases, dimension, and linear maps

Spanning says a list reaches everything; independence says it carries no dead weight. A list with both properties is a coordinate system.

Definition 8.14 (Basis).

A basis of $V$ is a linearly independent set $B$ that spans $V$ . Every $v\in V$ is then a unique finite linear combination of elements of $B$ : existence because $B$ spans, uniqueness because two expressions subtract to a relation among finitely many distinct elements of the independent set (as in Lemma 8.13). For a finite basis $B=(b_{1},\dots,b_{n})$ , write

v=c_{1}b_{1}+\dots+c_{n}b_{n},\qquad[v]_{B}=(c_{1},\dots,c_{n}),

and call the scalars $c_{i}$ the coordinates of $v$ in $B$ .

Example 8.15 (The two bases in constant use).

The standard basis of $F^{n}$ is $e_{1},\dots,e_{n}$ , where $e_{i}$ has a $1$ in position $i$ and $0$ elsewhere. Both properties reduce to reading off coordinates: the combination $\sum_{i}c_{i}e_{i}$ is the tuple $(c_{1},\dots,c_{n})$ , so every vector is such a combination (spanning) and only the zero combination gives $\mathbf{0}$ (independence). The monomial basis of $F[X]_{<n}$ is $1,X,\dots,X^{n-1}$ : a polynomial of degree less than $n$ is, by construction, a linear combination of these monomials, and independence is the fact that polynomials are equal exactly when their coefficient sequences agree (Definition 5.1).

That all bases of a given space have the same length is not obvious; it rests on the following exchange principle, which lets an independent list consume a spanning list one slot at a time.

Lemma 8.16 (Steinitz exchange).

If $v_{1},\dots,v_{m}$ are linearly independent in $V$ and $w_{1},\dots,w_{n}$ span $V$ , then $m\leq n$ .

Proof.

We prove by induction on $k=0,1,\dots,m$ that, after a suitable renumbering of the $w_{j}$ , the hybrid list

v_{1},\dots,v_{k},w_{k+1},\dots,w_{n}

spans $V$ . The case $k=0$ is the hypothesis on the $w_{j}$ .

For the induction step, suppose the hybrid list at stage $k<m$ spans $V$ . In particular it expresses $v_{k+1}$ :

v_{k+1}=\sum_{i\leq k}a_{i}v_{i}+\sum_{j>k}c_{j}w_{j}.

Some coefficient $c_{j}$ with $j>k$ must be nonzero: were they all zero, $v_{k+1}$ would be a linear combination of $v_{1},\dots,v_{k}$ , and Lemma 8.13 would make the list $v_{1},\dots,v_{k+1}$ dependent, contradicting the independence of the $v_{i}$ . (This step silently requires a slot $j>k$ to exist, i.e. $k<n$ ; if instead $k=n$ , the hybrid list is $v_{1},\dots,v_{n}$ and the displayed equation already yields the same contradiction.) Renumber so that $c_{k+1}\neq 0$ , and solve for the displaced vector:

w_{k+1}=c_{k+1}^{-1}\Bigl{(}v_{k+1}-\sum_{i\leq k}a_{i}v_{i}-\sum_{j>k+1}c_{j}% w_{j}\Bigr{)}.

Every vector of the stage- $k$ list therefore lies in the span of the stage- $(k{+}1)$ list $v_{1},\dots,v_{k+1},\allowbreak w_{k+2},\dots,w_{n}$ —the $v_{i}$ and the remaining $w_{j}$ trivially, $w_{k+1}$ by the display—so by Proposition 8.10 the stage- $(k{+}1)$ list spans $V$ , completing the induction.

Each step trades one $w$ for one $v$ , so the process can run to $k=m$ only if there are at least $m$ slots to trade: $m\leq n$ . □

Theorem 8.17 (Dimension).

Let $V$ be a finitely generated $F$ -vector space. Then $V$ has a basis, and any two bases of $V$ have the same number of elements. This common number is the dimension $\dim_{F}V$ (written $\dim V$ when the field is clear). In particular $\dim_{F}F^{n}=n$ and $\dim_{F}F[X]_{<n}=n$ .

Proof.

Existence. Let $w_{1},\dots,w_{n}$ be a finite spanning list. While the list is dependent, Lemma 8.13 exhibits some $w_{j}$ in the span of the others; discarding it leaves the span unchanged, since any combination using $w_{j}$ can be rewritten without it (substitute and regroup, Proposition 8.10). Each discard shortens the list, so after at most $n$ discards the process halts at an independent spanning list—a basis. (If $V$ is the zero space, the process discards everything and halts at the empty list, a basis of $\{\mathbf{0}\}$ with $\operatorname{span}(\varnothing)=\{\mathbf{0}\}$ ; the dimension is $0$ .)

Invariance. Every basis is finite: if a basis contained more than the $n$ elements of a finite spanning list, any $n+1$ of its elements would contradict Lemma 8.16. Let $b_{1},\dots,b_{m}$ and $b_{1}^{\prime},\dots,b_{n}^{\prime}$ be bases. Applying Lemma 8.16 with the first list as the independent one and the second as the spanning one gives $m\leq n$ ; exchanging the roles gives $n\leq m$ . Hence $m=n$ .

The two named spaces have the explicit bases of Example 8.15, each of length $n$ . □

With coordinates in hand, the maps that respect the linear structure come next; they are the section’s real subject, for the Pedersen-style commitments developed in the series are such maps.

Definition 8.18 (Linear map, kernel, image).

A function $T\colon V\to W$ between $F$ -vector spaces is linear (an $F$ -linear map) if

T(au+bv)=a\,T(u)+b\,T(v)\qquad\text{for all }a,b\in F\text{ and }u,v\in V.

Its kernel and image are

\ker T=\{\,v\in V:T(v)=\mathbf{0}\,\}\subseteq V,\qquad\operatorname{im}T=\{\,% T(v):v\in V\,\}\subseteq W.

A bijective linear map is an isomorphism.

Three basic facts follow at once from the subspace criterion and linearity, and we verify them here once. First, taking $a=b=0$ gives $T(\mathbf{0})=\mathbf{0}$ , so $\mathbf{0}\in\ker T$ and $\mathbf{0}\in\operatorname{im}T$ . Second, both kernel and image are subspaces: if $u,v\in\ker T$ then $T(au+bv)=a\,T(u)+b\,T(v)=\mathbf{0}$ , and if $T(u),T(v)\in\operatorname{im}T$ then $a\,T(u)+b\,T(v)=T(au+bv)\in\operatorname{im}T$ ; Proposition 8.6 applies to each. Third, $T$ is injective if and only if $\ker T=\{\mathbf{0}\}$ : if $T(u)=T(v)$ , then $T(u-v)=\mathbf{0}$ by linearity, so a trivial kernel forces $u=v$ ; conversely an injective $T$ sends only $\mathbf{0}$ to $T(\mathbf{0})=\mathbf{0}$ . We also note that for fixed $V$ and $W$ the set $\operatorname{Hom}(V,W)$ of all linear maps $V\to W$ is itself an $F$ -vector space under the pointwise operations of Example 8.4(2)—a sum or scalar multiple of linear maps is linear, so $\operatorname{Hom}(V,W)$ is a subspace of the space of all functions $V\to W$ .

Theorem 8.19 (Rank–nullity).

Let $T\colon V\to W$ be a linear map with $V$ finite-dimensional. Then

\dim V=\dim\ker T+\dim\operatorname{im}T.

Proof.

The kernel is a subspace of the finite-dimensional $V$ , and is itself finite-dimensional: an independent list in $\ker T$ has length at most $\dim V$ by Lemma 8.16 (tested against a basis of $V$ , which spans), so a longest independent list $u_{1},\dots,u_{k}$ in $\ker T$ exists, and it spans $\ker T$ —any $u\in\ker T$ outside its span would extend it to a longer independent list by Lemma 8.13. Thus $u_{1},\dots,u_{k}$ is a basis of $\ker T$ .

Extend it to a basis of $V$ : while the current independent list fails to span $V$ , adjoin any vector outside its span—independence is preserved by Lemma 8.13—and the process terminates, again because independent lists cannot exceed $\dim V$ in length (Lemma 8.16 against any basis of $V$ ). Write the resulting basis as $u_{1},\dots,u_{k},v_{1},\dots,v_{r}$ , so that $\dim V=k+r$ .

We claim $T(v_{1}),\dots,T(v_{r})$ is a basis of $\operatorname{im}T$ ; the theorem follows, since then $\dim\operatorname{im}T=r$ and $\dim V=k+r=\dim\ker T+\dim\operatorname{im}T$ .

Spanning. Any element of $\operatorname{im}T$ is $T(v)$ for some $v=\sum_{i}a_{i}u_{i}+\sum_{j}c_{j}v_{j}$ , and linearity with $T(u_{i})=\mathbf{0}$ gives $T(v)=\sum_{j}c_{j}\,T(v_{j})$ .

Independence. Suppose $\sum_{j}c_{j}\,T(v_{j})=\mathbf{0}$ . By linearity $T\bigl{(}\sum_{j}c_{j}v_{j}\bigr{)}=\mathbf{0}$ , so $\sum_{j}c_{j}v_{j}\in\ker T$ , and expressing this kernel element in the kernel basis gives $\sum_{j}c_{j}v_{j}=\sum_{i}a_{i}u_{i}$ for some scalars $a_{i}$ . Rearranged, $\sum_{i}a_{i}u_{i}-\sum_{j}c_{j}v_{j}=\mathbf{0}$ is a linear relation among the combined basis of $V$ , whose independence forces every coefficient—in particular every $c_{j}$ —to vanish. □

Rank–nullity is the dimension-counting engine of the section. It shows at once that a linear map from a higher-dimensional space into a lower-dimensional one must have a nontrivial kernel—the image cannot have dimension exceeding the target’s, so the kernel absorbs the difference—and distinct inputs must therefore collide. That forced collision is exactly what makes vector commitments compressing and only computationally binding (Remark 8.29).

8.4 Bilinear forms and the inner product on $F^{n}$

The maps considered so far are linear in a single argument. Commitment and proof systems are pervaded by expressions linear in each of two arguments—above all the inner product between two vectors. Over $\mathbb{R}$ such products come wrapped in geometry: lengths, angles, positivity. Over the finite fields of cryptographic interest there is no ordering, hence no “positive” and no length; what survives, and what the applications actually use, is the bare algebra. The appropriate level of generality is therefore the bilinear form.

Definition 8.20 (Bilinear form).

A bilinear form on an $F$ -vector space $V$ is a function $\beta\colon V\times V\to F$ that is linear in each argument separately:

\beta(au+a^{\prime}u^{\prime},\,v)=a\,\beta(u,v)+a^{\prime}\,\beta(u^{\prime},% v),\qquad\beta(u,\,bv+b^{\prime}v^{\prime})=b\,\beta(u,v)+b^{\prime}\,\beta(u,% v^{\prime}),

for all $u,u^{\prime},v,v^{\prime}\in V$ and $a,a^{\prime},b,b^{\prime}\in F$ . The form is symmetric if $\beta(u,v)=\beta(v,u)$ for all $u, v$ , and nondegenerate if $\beta(u,v)=0$ for all $v$ implies $u=\mathbf{0}$ .

Relative to a fixed basis $b_{1},\dots,b_{n}$ of $V$ , a bilinear form is captured by finitely many scalars: expanding both arguments in the basis and applying bilinearity termwise, $\beta(u,v)=\sum_{i,j}\beta(b_{i},b_{j})\,[u]_{i}[v]_{j}$ , so $\beta$ is determined by—and represented by—the unique $n\times n$ array $M$ with entries $M_{ij}=\beta(b_{i},b_{j})$ , via $\beta(u,v)=[u]_{B}^{\mathsf{T}}M\,[v]_{B}$ in matrix shorthand. We record the representation for orientation but make no further use of it; only the special case with $M$ the identity array matters below.

Definition 8.21 (Standard inner product on $F^{n}$ ).

The standard inner product (or dot product) on $F^{n}$ is

\langle\mathbf{a},\,\mathbf{b}\rangle=\sum_{i=1}^{n}a_{i}b_{i}=\mathbf{a}^{% \mathsf{T}}\mathbf{b},\qquad\mathbf{a}=(a_{1},\dots,a_{n}),\ \mathbf{b}=(b_{1}% ,\dots,b_{n}).

Bilinearity holds because each term $a_{i}b_{i}$ is linear in each factor, and symmetry because multiplication in $F$ commutes; the representing array in the standard basis is the identity ( $\langle e_{i},\,e_{j}\rangle$ is $1$ if $i=j$ and $0$ otherwise). The form is nondegenerate: if $\langle\mathbf{a},\,\mathbf{b}\rangle=0$ for every $\mathbf{b}$ , then in particular $a_{i}=\langle\mathbf{a},\,e_{i}\rangle=0$ for each $i$ , so $\mathbf{a}=\mathbf{0}$ .

Remark 8.22 (No positivity over finite fields).

Over $\mathbb{R}$ the standard inner product is positive definite: $\langle\mathbf{a},\,\mathbf{a}\rangle=\sum_{i}a_{i}^{2}\geq 0$ , with equality only at $\mathbf{0}$ . Positivity is what yields the Euclidean norm $\lVert\mathbf{a}\rVert=\sqrt{\langle\mathbf{a},\,\mathbf{a}\rangle}$ and the Cauchy–Schwarz inequality $\lvert\langle\mathbf{a},\,\mathbf{b}\rangle\rvert\leq\lVert\mathbf{a}\rVert\,% \lVert\mathbf{b}\rVert$ —the geometric superstructure of real inner products. Over a finite field $\mathbb{F}_{q}$ there is no ordering compatible with the arithmetic, so “ $\geq 0$ ” is meaningless, and the superstructure collapses: there exist nonzero isotropic vectors $\mathbf{a}\neq\mathbf{0}$ with $\langle\mathbf{a},\,\mathbf{a}\rangle=0$ . Over $\mathbb{F}_{5}$ , for instance, the vector $\mathbf{a}=(1,2)$ has

\langle\mathbf{a},\,\mathbf{a}\rangle=1^{2}+2^{2}=1+4=5=0

in $\mathbb{F}_{5}$ . What survives the collapse are the algebraically robust properties: bilinearity, symmetry, and nondegeneracy. These are all that the arguments in proof systems rely on, which is why the loss of positivity costs the applications nothing.

Nondegeneracy is not a consolation prize; it powers a dictionary between vectors and the scalar-valued linear maps on them.

Proposition 8.23 (Functionals via the inner product).

For each $\mathbf{a}\in F^{n}$ , the map $\mathbf{b}\mapsto\langle\mathbf{a},\,\mathbf{b}\rangle$ is a linear map $F^{n}\to F$ (a linear functional). The assignment

F^{n}\longrightarrow\operatorname{Hom}(F^{n},F),\qquad\mathbf{a}\longmapsto% \langle\mathbf{a},\,\cdot\rangle\,,

is an isomorphism of $F$ -vector spaces onto the dual space $\operatorname{Hom}(F^{n},F)$ of all linear functionals on $F^{n}$ . In particular both spaces have dimension $n$ .

Proof.

Each $\langle\mathbf{a},\,\cdot\rangle$ is linear in $\mathbf{b}$ by bilinearity, and the assignment itself is linear in $\mathbf{a}$ for the same reason, mapping into the vector space $\operatorname{Hom}(F^{n},F)$ of 8.18. It is injective: if $\langle\mathbf{a},\,\cdot\rangle$ is the zero functional, then $\langle\mathbf{a},\,\mathbf{b}\rangle=0$ for every $\mathbf{b}$ , and nondegeneracy (8.21) gives $\mathbf{a}=\mathbf{0}$ , so the kernel is trivial. It is surjective: given a linear functional $\varphi$ , set $a_{i}=\varphi(e_{i})$ and $\mathbf{a}=(a_{1},\dots,a_{n})$ ; then for every $\mathbf{b}=\sum_{i}b_{i}e_{i}$ , linearity of $\varphi$ gives

\varphi(\mathbf{b})=\sum_{i}b_{i}\,\varphi(e_{i})=\sum_{i}a_{i}b_{i}=\langle% \mathbf{a},\,\mathbf{b}\rangle,

so $\varphi=\langle\mathbf{a},\,\cdot\rangle$ . A bijective linear map is an isomorphism, and $\dim\operatorname{Hom}(F^{n},F)=\dim F^{n}=n$ follows since an isomorphism carries a basis to a basis (its inverse is linear, and both directions preserve spanning and independence). □

Remark 8.24 (The dictionary in use).

Proposition 8.23 says that “a linear functional on $F^{n}$ ” and “a vector in $F^{n}$ ” are interchangeable: every linear way of producing one scalar from a vector is an inner product against a fixed vector, and conversely. The instance to keep in mind is polynomial evaluation. Fix a point $z\in F$ ; the map sending a polynomial to its value at $z$ is linear in the coefficients, so it must be an inner product against some fixed vector—and indeed, for $p\in F[X]_{<n}$ with coefficient vector $\mathbf{c}=(c_{0},c_{1},\dots,c_{n-1})$ ,

p(z)=c_{0}+c_{1}z+\dots+c_{n-1}z^{n-1}=\langle\mathbf{c},\,(1,z,z^{2},\dots,z^% {n-1})\rangle.

Evaluating a committed polynomial at a challenge point is therefore an inner-product claim about the committed coefficient vector; this is precisely the shape of statement an inner-product argument proves (8.32).

8.5 The mixed inner product with group elements

The commitments used in Halo 2 and Orchard pair a vector of scalars with a vector of group elements. We isolate the algebra here, working over an abstract group; the group of actual cryptographic interest—the points of an elliptic curve—is constructed in the elliptic-curve section later in the volume, and only its abelian-group structure is needed for everything proved below, so the results transfer verbatim.

Construction 8.25 (Scalar multiplication by $\mathbb{F}_{r}$ on a prime-order group).

Let $(\mathbb{G},+)$ be a finite abelian group of prime order $r$ , written additively with identity $\mathcal{O}$ . For an integer $a\in\mathbb{Z}$ and $G\in\mathbb{G}$ , write $[a]G$ for the $a$ -fold multiple of $G$ —the additive reading of the powers of §3: $[0]G=\mathcal{O}$ , $[a]G=G+\dots+G$ with $a$ summands for $a>0$ , and $[-a]G=-([a]G)$ . The brackets keep the scalar visually separate from the group element. The multiple $[a]G$ depends only on the residue of $a$ modulo $r$ : the order of $G$ divides $\lvert\mathbb{G}\rvert=r$ (Corollary 3.30), and $[a]G=[b]G$ whenever $a\equiv b\pmod{\operatorname{ord}(G)}$ (Proposition 3.12(2), read additively), so congruence modulo $r$ suffices. The operation therefore descends to scalars in the field $\mathbb{F}_{r}=\mathbb{Z}/r\mathbb{Z}$ (4.26): for $a\in\mathbb{F}_{r}$ and $G\in\mathbb{G}$ , define $[a]G$ using any integer representative of $a$ . It is this descended operation—group elements scaled by elements of a field—that the rest of the section uses.

Proposition 8.26 ( $\mathbb{G}$ as an $\mathbb{F}_{r}$ -vector space).

Let $\mathbb{G}$ be an abelian group of prime order $r$ , with the scalar multiplication of 8.25. Then $\mathbb{G}$ is an $\mathbb{F}_{r}$ -vector space of dimension $1$ ; any element $G\neq\mathcal{O}$ is a basis, and every element of $\mathbb{G}$ is $[a]G$ for a unique $a\in\mathbb{F}_{r}$ .

Proof.

The vector-space axioms are the standard laws of multiples. For integers $a, b$ , the identities $[a+b]G=[a]G+[b]G$ and $[a]\bigl{(}[b]G\bigr{)}=[ab]G$ are the exponent laws of §3 in additive notation, $[1]G=G$ is the definition, and $[a](G+H)=[a]G+[a]H$ holds in any abelian group: for $a>0$ it is the rearrangement of $a$ summands $G+H$ into $a$ summands $G$ followed by $a$ summands $H$ , legitimate by commutativity and associativity (formally, induction on $a$ ), and the cases $a\leq 0$ follow by negating. Each law respects reduction modulo $r$ by 8.25, so the four scalar axioms of 8.1 hold with scalars in $\mathbb{F}_{r}$ , and $(\mathbb{G},+)$ is an abelian group by hypothesis: $\mathbb{G}$ is an $\mathbb{F}_{r}$ -vector space.

Now let $G\neq\mathcal{O}$ . By Lagrange’s theorem (Theorem 3.29, via Corollary 3.30) the order of $G$ divides the prime $r$ , and it exceeds $1$ since $G$ is not the identity; hence $\operatorname{ord}(G)=r$ . The $r$ multiples $[0]G,[1]G,\dots,[r-1]G$ are then pairwise distinct (Proposition 3.12(2), additively: $[a]G=[b]G$ forces $a\equiv b\pmod{r}$ ), and $\mathbb{G}$ has exactly $r$ elements, so the multiples exhaust $\mathbb{G}$ . Thus $\{G\}$ spans; and it is independent, since $[a]G=\mathcal{O}$ forces $a=0$ in $\mathbb{F}_{r}$ , again because $\operatorname{ord}(G)=r$ . A one-element basis gives $\dim_{\mathbb{F}_{r}}\mathbb{G}=1$ , and the uniqueness of $a$ in $[a]G$ is the uniqueness of coordinates in a basis (8.14). □

Definition 8.27 (Mixed inner product, multiscalar multiplication).

Let $\mathbf{G}=(G_{1},\dots,G_{n})\in\mathbb{G}^{n}$ be a fixed tuple of group elements and $\mathbf{a}=(a_{1},\dots,a_{n})\in\mathbb{F}_{r}^{n}$ a vector of scalars. Their mixed inner product—in computational contexts a multiscalar multiplication (MSM), in cryptographic ones a Pedersen-style inner product—is the group element

\langle\mathbf{a},\,\mathbf{G}\rangle=\sum_{i=1}^{n}[a_{i}]\,G_{i}\in\mathbb{G}.

We reuse the angle-bracket notation of 8.21 deliberately; the type of the second argument—scalar vector or vector of group elements—determines which product is meant.

Proposition 8.28 (Bilinearity of the mixed product).

Fix $\mathbf{G}\in\mathbb{G}^{n}$ . The map $\mathbf{a}\mapsto\langle\mathbf{a},\,\mathbf{G}\rangle$ is $\mathbb{F}_{r}$ -linear from $\mathbb{F}_{r}^{n}$ to $\mathbb{G}$ :

\langle c\,\mathbf{a}+c^{\prime}\,\mathbf{a}^{\prime},\,\mathbf{G}\rangle=[c]% \langle\mathbf{a},\,\mathbf{G}\rangle+[c^{\prime}]\langle\mathbf{a}^{\prime},% \,\mathbf{G}\rangle\qquad\text{for all }c,c^{\prime}\in\mathbb{F}_{r}\text{ % and }\mathbf{a},\mathbf{a}^{\prime}\in\mathbb{F}_{r}^{n}.

Symmetrically, for fixed $\mathbf{a}\in\mathbb{F}_{r}^{n}$ the map $\mathbf{G}\mapsto\langle\mathbf{a},\,\mathbf{G}\rangle$ is a group homomorphism $\mathbb{G}^{n}\to\mathbb{G}$ , and is $\mathbb{F}_{r}$ -linear when $\mathbb{G}^{n}$ is viewed as an $\mathbb{F}_{r}$ -vector space (componentwise, as in Example 8.3 with $\mathbb{G}$ in place of $F$ ). Thus $\langle\cdot,\,\cdot\rangle\colon\mathbb{F}_{r}^{n}\times\mathbb{G}^{n}\to% \mathbb{G}$ is bilinear over $\mathbb{F}_{r}$ .

Proof.

Both statements are the vector-space laws of $\mathbb{G}$ (Proposition 8.26) applied componentwise. For the first,

\langle c\,\mathbf{a}+c^{\prime}\,\mathbf{a}^{\prime},\,\mathbf{G}\rangle=\sum% _{i}[\,ca_{i}+c^{\prime}a_{i}^{\prime}\,]\,G_{i}=\sum_{i}\bigl{(}[c][a_{i}]G_{% i}+[c^{\prime}][a_{i}^{\prime}]G_{i}\bigr{)}=[c]\sum_{i}[a_{i}]G_{i}+[c^{% \prime}]\sum_{i}[a_{i}^{\prime}]G_{i},

using $[a+b]G=[a]G+[b]G$ and $[ab]G=[a]([b]G)$ in each component and then regrouping the sum in the abelian group $\mathbb{G}$ . For the second, linearity in $\mathbf{G}$ follows by the symmetric computation on the other slot of the defining sum, using $[a](G+H)=[a]G+[a]H$ componentwise. □

Remark 8.29 (Why the mixed product is the right abstraction).

Read $\langle\mathbf{a},\,\mathbf{G}\rangle$ as a commitment to the scalar vector $\mathbf{a}$ under the public “basis” $\mathbf{G}$ —the receipt of the section’s opening problem. Proposition 8.28 is then exactly the homomorphic property that the problem demanded: the commitment to $c\,\mathbf{a}+c^{\prime}\,\mathbf{a}^{\prime}$ is the $[c]$ -, $[c^{\prime}]$ -scaled combination of the individual commitments, computable by anyone holding those commitments and the scalars $c,c^{\prime}$ , without knowledge of $\mathbf{a}$ or $\mathbf{a}^{\prime}$ . Provided the $G_{i}$ are chosen so that no party can exhibit a nontrivial relation $\sum_{i}[a_{i}]G_{i}=\mathcal{O}$ —a computational hypothesis, the discrete-logarithm hardness assumption, made precise in later volumes of this series—the commitment is binding: the map $\mathbf{a}\mapsto\langle\mathbf{a},\,\mathbf{G}\rangle$ is computationally injective, in the sense that no feasible computation produces two vectors with the same image. Genuinely injective it cannot be once $n\geq 2$ : the map is linear from the $n$ -dimensional $\mathbb{F}_{r}^{n}$ into the one-dimensional $\mathbb{G}$ (Proposition 8.26), so by rank–nullity (Theorem 8.19) its kernel has dimension at least $n-1$ . Collisions exist in abundance; binding is the claim that they cannot be found, a computational rather than information-theoretic statement. The classical Pedersen commitment to a single value $a$ with randomness $\rho$ is the special case $n=2$ , with $H\neq\mathcal{O}$ ,

[a]G+[\rho]H=\langle(a,\rho),\,(G,H)\rangle,

which is moreover perfectly hiding: for fixed $a$ , as $\rho$ ranges uniformly over $\mathbb{F}_{r}$ the term $[\rho]H$ ranges uniformly over $\mathbb{G}$ (it is a bijection of $\mathbb{G}$ , by unique representation in the basis $\{H\}$ ), so the commitment’s distribution is uniform and carries no information about $a$ .

8.6 How this machinery appears in commitment and proof systems

We close by drawing the threads together. Each point below is developed rigorously in later volumes of this series; the remarks here are descriptive, but the linear-algebraic content behind them is already proved in full.

Remark 8.30 (Witnesses, constraints, and assignments).

An arithmetic circuit over $\mathbb{F}_{q}$ becomes, after arithmetisation—the encoding of a computation as a system of polynomial constraints on the wire values—a collection of equations that the vector $\mathbf{z}\in\mathbb{F}_{q}^{N}$ of all wire values must satisfy. The linear part of such a system—the wiring (or “copy”) constraints of the PLONK family, which assert that certain wires carry equal values—consists of homogeneous linear equations in the entries of $\mathbf{z}$ , organised in practice as arrays of coefficients (one row per equation) acting on the assignment vector. Satisfying the linear constraints confines $\mathbf{z}$ to a subspace of $\mathbb{F}_{q}^{N}$ (Example 8.7), or, when public inputs fix some entries, to a translate $\mathbf{z}_{0}+W$ of one—an affine subspace. The multiplicative constraints are handled separately, by the polynomial machinery of the surrounding sections. Rank–nullity (Theorem 8.19) quantifies the degrees of freedom that remain after the linear constraints are imposed: the dimension of the witness space.

Remark 8.31 (Commitments as linear maps).

A Pedersen vector commitment $\mathbf{a}\mapsto\langle\mathbf{a},\,\mathbf{G}\rangle$ is a linear map $\mathbb{F}_{r}^{n}\to\mathbb{G}$ (Proposition 8.28), and its linearity is the source of every algebraic manipulation a verifier performs: taking known linear combinations of commitments, folding two commitment keys $\mathbf{G},\mathbf{G}^{\prime}$ into $\mathbf{G}+[x]\mathbf{G}^{\prime}$ under a challenge $x$ , and checking claimed openings by re-evaluating the same linear map. A polynomial commitment is the identical map applied to a coefficient vector, and an evaluation of the committed polynomial at a point $z$ is the scalar inner product $\langle\mathbf{c},\,(1,z,\dots,z^{n-1})\rangle$ (Remark 8.24).

Remark 8.32 (The inner-product relation).

The core statement an inner-product argument proves has the shape: “I know vectors $\mathbf{a},\mathbf{b}\in\mathbb{F}_{r}^{n}$ such that

P=\langle\mathbf{a},\,\mathbf{G}\rangle+\langle\mathbf{b},\,\mathbf{H}\rangle+% \bigl{[}\,\langle\mathbf{a},\,\mathbf{b}\rangle\,\bigr{]}U

for public $\mathbf{G},\mathbf{H}\in\mathbb{G}^{n}$ and $U\in\mathbb{G}$ .” Three of this section’s constructions meet in the one equation: two mixed inner products $\langle\mathbf{a},\,\mathbf{G}\rangle$ and $\langle\mathbf{b},\,\mathbf{H}\rangle$ , committing to the witness vectors; one scalar inner product $\langle\mathbf{a},\,\mathbf{b}\rangle$ , the value being argued; and the bilinearity of all three, which is what permits prover and verifier to fold a length- $n$ instance into a length- $n/2$ one and recurse. The argument’s soundness ultimately reduces to the nondegeneracy of these forms together with the hardness of finding kernel elements of the commitment map—exactly the linear-algebraic and computational facts assembled above.

The cheque drawn at the head of the section is now cashed. The receipt for a list $(a_{1},\dots,a_{n})$ of secrets is the mixed inner product $\langle\mathbf{a},\,\mathbf{G}\rangle=\sum_{i}[a_{i}]G_{i}$ : one group element, whatever the size of $n$ . “Receipts add” means precisely that the receipt map is linear, and that is the payoff theorem, Proposition 8.28. One element can absorb $n$ secrets only because the map compresses an $n$ -dimensional space into a one-dimensional one, and rank–nullity prices the compression exactly: a kernel of dimension at least $n-1$ , an unavoidable reservoir of collisions that Remark 8.29 tames computationally rather than absolutely.

In summary: vector spaces, bases and dimension, linear maps with their kernels and images governed by rank–nullity, bilinear forms, and the two flavours of inner product—scalar with scalar, scalar with group—constitute the linear-algebraic vocabulary for the cryptography ahead. Pedersen-style commitments are linear maps, and their polynomial evaluation openings assert inner products; nondegeneracy and dimension counting supply the relevant algebra. Other commitment constructions, such as hash-based commitments, need not be linear. The next section applies the machinery to the polynomial spaces $F[X]_{<n}$ over structured evaluation domains, and the section on elliptic curves constructs the group $\mathbb{G}$ that the mixed inner product has so far taken as abstract.