The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

8 Linear algebra over a field

This section develops linear algebra from the axioms, assuming only the notion of a field (4): vector spaces, whose elements can be added and scaled by elements of a field; bases and dimension (Theorem 8.17); linear maps and rank–nullity (Theorem 8.19); bilinear forms and the standard inner product on the coordinate space Fn, in practice over a finite field 𝔽q; and the mixed inner product of a vector of scalars with a vector of group elements. For fixed public elements G1,…,Gn of a suitable group, the mixed inner product [a1]G1+⋯+[an]Gn is the Pedersen-style commitment of Halo 2 and Orchard to a list (a1,…,an) of secrets, such as the wire values (intermediate values) of an arithmetic circuit, with n possibly in the millions: a single group element, independent of n, that computationally determines the list, can later be opened or reasoned about, and is additively homomorphic. Remark 8.29 derives the homomorphic property and the collisions that this compression necessarily introduces. Commitments of other kinds, such as hash-based ones, need not be linear. The next section applies these results to the polynomial spaces F[X]<n over structured evaluation domains.

The section also discharges two deferrals. Remark 5.5 left to it the linear structure of F[X], with the monomials as an infinite coordinate system. The proof of Theorem 6.10 used two facts without proof: a space with a finite spanning set has a basis, proved in Theorem 8.17, and coordinates in a basis are unique, which follows from linear independence (Definition 8.14). Neither argument uses finite fields, so no circularity arises. Throughout, F denotes an arbitrary field with identities 0 and 1; the field axioms of Definition 4.24 are used 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 +:V×V→V and scalar multiplication ⋅:F×V→V, such that for all u,v,w∈V and all a,b∈F:

  1. 1.

    (V,+) is an abelian group: addition is associative and commutative, there is a zero vector 𝟎∈V with v+𝟎=v, and every v has an additive inverse −v with v+(−v)=𝟎;

  2. 2.

    scalar multiplication is compatible with the multiplication of F: a⋅(b⋅v)=(ab)⋅v;

  3. 3.

    the identity of F acts as the identity: 1⋅v=v;

  4. 4.

    scalar multiplication distributes over vector addition: a⋅(u+v)=a⋅u+a⋅v;

  5. 5.

    scalar multiplication distributes over scalar addition: (a+b)⋅v=a⋅v+b⋅v.

The elements of V are called vectors, the elements of F scalars. We write av for a⋅v, and we allow the scalar 0∈F and the vector 𝟎∈V to share a symbol whenever context distinguishes them.

The following consequences of the axioms are used hereafter without citation.

Proposition 8.2.

Let V be an F-vector space, v∈V, and a∈F. Then:

  1. 1.

    0⋅v=𝟎;

  2. 2.

    a⋅𝟎=𝟎;

  3. 3.

    (−1)⋅v=−v;

  4. 4.

    if av=𝟎, then a=0 or v=𝟎.

Proof.

(1) By distributivity over scalar addition, 0⋅v=(0+0)⋅v=0⋅v+0⋅v; adding −(0⋅v) to both sides leaves 𝟎=0⋅v.

(2) Likewise a⋅𝟎=a⋅(𝟎+𝟎)=a⋅𝟎+a⋅𝟎, and cancelling in the abelian group (V,+) gives a⋅𝟎=𝟎.

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

v+(−1)⋅v=1⋅v+(−1)⋅v=(1+(−1))⋅v=0⋅v=𝟎,

so (−1)⋅v is the additive inverse of v; by uniqueness of inverses in a group, (−1)⋅v=−v.

(4) Suppose av=𝟎 and a≠0. Since F is a field, a−1 exists, and by the identity and compatibility axioms

v=1⋅v=(a−1⁢a)⋅v=a−1⋅(a⁢v)=a−1⋅𝟎=𝟎,

the last step by (2). □

Example 8.3 (The coordinate space Fn).

The principal example is the coordinate space

Fn={(x1,…,xn):xi∈F},

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

(x1,…,xn)+(y1,…,yn)=(x1+y1,…,xn+yn),a⋅(x1,…,xn)=(a⁢x1,…,a⁢xn).

The zero vector is (0,…,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 {𝟎}, consisting of the empty tuple alone. As a standing convention we write vectors of Fn in boldface and regard them as columns, 𝐱=(x1,…,xn)𝖳.

Example 8.4 (Further examples).
  1. 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∈F⁢[X]:f=0⁢ 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. Polynomial commitment schemes operate on this space.

  2. 2.

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

  3. 3.

    Matrices. The set Fm×n of m×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. 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×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 ℂ is an ℝ-vector space of dimension 2, with basis 1,i, so [ℂ:ℝ]=2; and the finite field 𝔽q with q=pk is a k-dimensional 𝔽p-vector space, [𝔽q:𝔽p]=k, which is the structure used in the proof of Theorem 6.10.

Definition 8.5 (Subspace).

A subset W⊆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⊆V is a subspace if and only if

  1. 1.

    𝟎∈W;

  2. 2.

    W is closed under addition: u,v∈W implies u+v∈W; and

  3. 3.

    W is closed under scalar multiplication: a∈F and v∈W imply av∈W.

Equivalently, W is a subspace if and only if W≠∅ and au+bv∈W for all a,b∈F and u,v∈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 𝟎W of W satisfies 𝟎W+𝟎W=𝟎W, and cancelling in V gives 𝟎W=𝟎.

Conversely, suppose (1)–(3) hold. Closure makes the two operations well defined on W. The additive inverse of any v∈W is (−1)v∈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∈W by (2) and (3) combined, and W∋𝟎 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 𝟎=0v∈W for any v in the nonempty W, which is (1). □

Example 8.7.

In F3 the set W={(x1,x2,x3):x1+x2+x3=0} is a subspace: it contains 𝟎, and if the coordinates of 𝐱 and 𝐲 each sum to 0, then those of a𝐱+b𝐲 sum to a⋅0+b⋅0=0. By contrast {(x1,x2,x3):x1+x2+x3=1} is not a subspace: it does not contain 𝟎. The same computation shows that the solution set of any single homogeneous linear equation c1x1+⋯+cnxn=0 (the ci fixed scalars) is a subspace of Fn, 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 are the kernels of linear maps (8.18).

Proposition 8.8 (Intersections and sums).

Let V be an F-vector space.

  1. 1.

    The intersection ⋂i∈IWi of an arbitrary family of subspaces of V is a subspace.

  2. 2.

    The sum W1+⋯+Wk={w1+⋯+wk:wj∈Wj} of finitely many subspaces is a subspace, and it is the smallest subspace of V containing every Wj.

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

Proof.

(1) Each Wi contains 𝟎, so the intersection does. If u,v lie in every Wi and a,b∈F, then au+bv∈Wi 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 𝟎=𝟎+⋯+𝟎, and it contains each Wj (take every other summand 𝟎). For closure, take two elements ∑jwj and ∑jw′j with wj,w′j∈Wj, and scalars a,b; regrouping,

a⁢∑jwj+b⁢∑jw′j=∑j(a⁢wj+b⁢w′j),

and awj+bw′j∈Wj since Wj is a subspace, so the combination lies in the sum. Finally, any subspace U containing every Wj contains each summand wj 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=F2 (any field has |F|>1, since 1≠0) and the two axes {(x,0):x∈F} and {(0,y):y∈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

Besides being cut out by equations, a subspace can be generated by a set of vectors, as the set of all vectors obtained from them by addition and scaling.

Definition 8.9 (Linear combination and span).

Let S⊆V. A linear combination of vectors in S is any finite sum

a1⁢v1+a2⁢v2+⋯+ak⁢vk,ai∈F,vi∈S.

The span of S, written span(S) or ⟨S⟩, is the set of all linear combinations of finitely many vectors of S; by convention span(∅)={𝟎}. The set S spans (or generates) V if span(S)=V, and V is finitely generated (synonymously, finite-dimensional) if some finite set spans it.

Proposition 8.10.

For any S⊆V, the span 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, span(S) is a subspace, and it contains each v∈S as the combination 1⋅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 span(S)⊆W. □

Definition 8.11 (Linear independence).

A finite list of vectors v1,…,vk∈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:

a1⁢v1+⋯+ak⁢vk=𝟎⟹a1=⋯=ak=0.

Otherwise the list is linearly dependent, and a relation ∑iaivi=𝟎 with some ai≠0 is called a dependence relation. An arbitrary—possibly infinite—set S⊆V is linearly independent if every finite list of distinct vectors from S is linearly independent.

Remark 8.12.

Linear independence expresses non-redundancy: a list is dependent exactly when some vector in it lies in the span of the others, which is the content of the next lemma. A single vector v is independent if and only if v≠𝟎 (Proposition 8.2(4)); two vectors are dependent if and only if one is a scalar multiple of the other.

Lemma 8.13 (Dependence and redundancy).

A list v1,…,vk with k≥1 is linearly dependent if and only if some vj is a linear combination of the others. Moreover, if v1,…,vk is independent but v1,…,vk,w is dependent, then w∈span(v1,…,vk), and the coefficients expressing w are unique.

Proof.

Suppose first that vj=∑i≠jaivi. Then

∑i≠jai⁢vi+(−1)⁢vj=𝟎

is a dependence relation, its coefficient −1 on vj being nonzero (as 1≠0 in a field). Conversely, given a dependence relation ∑iaivi=𝟎 with aj≠0, the field supplies aj−1, and solving for vj gives vj=−aj−1∑i≠jaivi, a linear combination of the others.

For the second statement, take a dependence relation ∑iaivi+bw=𝟎 for the extended list. The coefficient b cannot be 0: otherwise the relation would be a nontrivial relation among v1,…,vk alone, contradicting their independence. Hence w=−b−1∑iaivi∈span(v1,…,vk). For uniqueness, suppose w=∑icivi=∑ic′ivi; subtracting, ∑i(ci−c′i)vi=𝟎, and independence forces ci=c′i for every i. □

8.3 Bases, dimension, and linear maps

Definition 8.14 (Basis).

A basis of V is a linearly independent set B that spans V. Every v∈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=(b1,…,bn), write

v=c1⁢b1+⋯+cn⁢bn,[v]B=(c1,…,cn),

and call the scalars ci the coordinates of v in B.

Example 8.15 (The standard and monomial bases).

The standard basis of Fn is e1,…,en, where ei has a 1 in position i and 0 elsewhere. Both properties reduce to reading off coordinates: the combination ∑iciei is the tuple (c1,…,cn), so every vector is such a combination (spanning) and only the zero combination gives 𝟎 (independence). The monomial basis of F[X]<n is 1,X,…,Xn−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 space have the same length rests on the following lemma, whose proof replaces the vectors of a spanning list, one at a time, by the vectors of an independent list.

Lemma 8.16 (Steinitz exchange).

If v1,…,vm are linearly independent in V and w1,…,wn span V, then m≤n.

Proof.

We prove by induction on k=0,1,…,m that, after a suitable renumbering of the wj, the hybrid list

v1,…,vk,wk+1,…,wn

spans V. The case k=0 is the hypothesis on the wj.

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

vk+1=∑i≤kai⁢vi+∑j>kcj⁢wj.

Some coefficient cj with j>k must be nonzero: were they all zero, vk+1 would be a linear combination of v1,…,vk, and Lemma 8.13 would make the list v1,…,vk+1 dependent, contradicting the independence of the vi. (This step requires a slot j>k to exist, i.e. k<n; if instead k=n, the hybrid list is v1,…,vn and the displayed equation already yields the same contradiction.) Renumber so that ck+1≠0, and solve for the displaced vector:

wk+1=ck+1−1⁢(vk+1−∑i≤kai⁢vi−∑j>k+1cj⁢wj).

Every vector of the stage-k list therefore lies in the span of the stage-(k+1) list v1,…,vk+1,wk+2,…,wn —the vi and the remaining wj trivially, wk+1 by the display—so by Proposition 8.10 the stage-(k+1) list spans V, completing the induction.

Each step replaces one w by one v, so the induction reaches k=m only if there are at least m slots to replace: m≤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 dimFV (written dimV when the field is clear). In particular dimFFn=n and dimFF[X]<n=n.

Proof.

Existence. Let w1,…,wn be a finite spanning list. While the list is dependent, Lemma 8.13 exhibits some wj in the span of the others; discarding it leaves the span unchanged, since any combination using wj 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 {𝟎} with span(∅)={𝟎}; 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 b1,…,bm and b′1,…,b′n be bases. Applying Lemma 8.16 with the first list as the independent one and the second as the spanning one gives m≤n; exchanging the roles gives n≤m. Hence m=n.

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

Linear maps are the functions between vector spaces that preserve the linear structure; the Pedersen-style commitments of the series are such maps.

Definition 8.18 (Linear map, kernel, image).

A function T:V→W between F-vector spaces is linear (an F-linear map) if

T⁢(a⁢u+b⁢v)=a⁢T⁢(u)+b⁢T⁢(v)for all ⁢a,b∈F⁢ and ⁢u,v∈V.

Its kernel and image are

ker⁡T={v∈V:T⁢(v)=𝟎}⊆V,im⁡T={T⁢(v):v∈V}⊆W.

A bijective linear map is an isomorphism.

Three basic facts follow from the subspace criterion and linearity. First, taking a=b=0 gives T(𝟎)=𝟎, so 𝟎∈kerT and 𝟎∈imT. Second, both kernel and image are subspaces: if u,v∈kerT then T(au+bv)=aT(u)+bT(v)=𝟎, and if T(u),T(v)∈imT then aT(u)+bT(v)=T(au+bv)∈imT; Proposition 8.6 applies to each. Third, T is injective if and only if kerT={𝟎}: if T(u)=T(v), then T(u−v)=𝟎 by linearity, so a trivial kernel forces u=v; conversely an injective T sends only 𝟎 to T(𝟎)=𝟎. Moreover, for fixed V and W the set Hom(V,W) of all linear maps V→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 Hom(V,W) is a subspace of the space of all functions V→W.

Theorem 8.19 (Rank–nullity).

Let T:V→W be a linear map with V finite-dimensional. Then

dimV=dimker⁡T+dimim⁡T.
Proof.

The kernel is a subspace of the finite-dimensional V, and is itself finite-dimensional: an independent list in kerT has length at most dimV by Lemma 8.16 (tested against a basis of V, which spans), so a longest independent list u1,…,uk in kerT exists, and it spans kerT —any u∈kerT outside its span would extend it to a longer independent list by Lemma 8.13. Thus u1,…,uk is a basis of kerT.

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 dimV in length (Lemma 8.16 against any basis of V). Write the resulting basis as u1,…,uk,v1,…,vr, so that dimV=k+r.

We claim T(v1),…,T(vr) is a basis of imT; the theorem follows, since then dimimT=r and dimV=k+r=dimkerT+dimimT.

Spanning. Any element of imT is T(v) for some v=∑iaiui+∑jcjvj, and linearity with T(ui)=𝟎 gives T(v)=∑jcjT(vj).

Independence. Suppose ∑jcjT(vj)=𝟎. By linearity T(∑jcjvj)=𝟎, so ∑jcjvj∈kerT, and expressing this kernel element in the kernel basis gives ∑jcjvj=∑iaiui for some scalars ai. Rearranged, ∑iaiui−∑jcjvj=𝟎 is a linear relation among the combined basis of V, whose independence forces every coefficient—in particular every cj—to vanish. □

Rank–nullity implies that a linear map from a higher-dimensional space into a lower-dimensional one has a nontrivial kernel—the image has dimension at most that of the target, so the kernel has dimension at least the difference—and therefore that distinct inputs collide. This collision is what makes vector commitments compressing and only computationally binding (Remark 8.29).

8.4 Bilinear forms and the inner product on Fn

Commitment and proof systems use expressions linear in each of two arguments, chiefly the inner product of two vectors. Over a finite field such a product has no length, angle or positivity, and the applications use only its algebraic properties, which the bilinear form captures.

Definition 8.20 (Bilinear form).

A bilinear form on an F-vector space V is a function β:V×V→F that is linear in each argument separately:

β⁢(a⁢u+a′⁢u′,v)=a⁢β⁢(u,v)+a′⁢β⁢(u′,v),β⁢(u,b⁢v+b′⁢v′)=b⁢β⁢(u,v)+b′⁢β⁢(u,v′),

for all u,u′,v,v′∈V and a,a′,b,b′∈F. The form is symmetric if β(u,v)=β(v,u) for all u,v, and nondegenerate if β(u,v)=0 for all v implies u=𝟎.

Relative to a fixed basis b1,…,bn of V, a bilinear form is determined by finitely many scalars: expanding both arguments in the basis and applying bilinearity termwise, β(u,v)=∑i,jβ(bi,bj)[u]i[v]j, so β is represented by the unique n×n array M with entries Mi⁢j=β(bi,bj), via β(u,v)=[u]B𝖳M[v]B in matrix shorthand. The representation is not used further; only the special case with M the identity array is needed below.

Definition 8.21 (Standard inner product on Fn).

The standard inner product (or dot product) on Fn is

⟨𝐚,𝐛⟩=∑i=1nai⁢bi=𝐚𝖳⁢𝐛,𝐚=(a1,…,an),𝐛=(b1,…,bn).

Bilinearity holds because each term aibi is linear in each factor, and symmetry because multiplication in F commutes; the representing array in the standard basis is the identity (⟨ei,ej⟩ is 1 if i=j and 0 otherwise). The form is nondegenerate: if ⟨𝐚,𝐛⟩=0 for every 𝐛, then in particular ai=⟨𝐚,ei⟩=0 for each i, so 𝐚=𝟎.

Remark 8.22 (No positivity over finite fields).

Over ℝ the standard inner product is positive definite: ⟨𝐚,𝐚⟩=∑iai2≥0, with equality only at 𝟎. Positivity is what yields the Euclidean norm ∥𝐚∥=⟨𝐚,𝐚⟩ and the Cauchy–Schwarz inequality |⟨𝐚,𝐛⟩|≤∥𝐚∥∥𝐛∥—the geometric structure of real inner products. Over a finite field 𝔽q there is no ordering compatible with the arithmetic, so “≥0” is meaningless, and this structure is lost: there exist nonzero isotropic vectors 𝐚≠𝟎 with ⟨𝐚,𝐚⟩=0. Over 𝔽5, for instance, the vector 𝐚=(1,2) has

⟨𝐚,𝐚⟩=12+22=1+4=5=0

in 𝔽5. The arguments of proof systems use only the algebraic properties that remain—bilinearity, symmetry, and nondegeneracy—so the absence of positivity does not affect them.

Nondegeneracy identifies vectors with the scalar-valued linear maps on them.

Proposition 8.23 (Functionals via the inner product).

For each 𝐚∈Fn, the map 𝐛↦⟨𝐚,𝐛⟩ is a linear map Fn→F (a linear functional). The assignment

Fn⟶Hom⁡(Fn,F),𝐚⟼⟨𝐚,⋅⟩,

is an isomorphism of F-vector spaces onto the dual space Hom(Fn,F) of all linear functionals on Fn. In particular both spaces have dimension n.

Proof.

Each ⟨𝐚,⋅⟩ is linear in 𝐛 by bilinearity, and the assignment itself is linear in 𝐚 for the same reason, mapping into the vector space Hom(Fn,F) of 8.18. It is injective: if ⟨𝐚,⋅⟩ is the zero functional, then ⟨𝐚,𝐛⟩=0 for every 𝐛, and nondegeneracy (8.21) gives 𝐚=𝟎, so the kernel is trivial. It is surjective: given a linear functional φ, set ai=φ(ei) and 𝐚=(a1,…,an); then for every 𝐛=∑ibiei, linearity of φ gives

φ⁢(𝐛)=∑ibi⁢φ⁢(ei)=∑iai⁢bi=⟨𝐚,𝐛⟩,

so φ=⟨𝐚,⋅⟩. A bijective linear map is an isomorphism, and dimHom(Fn,F)=dimFn=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 (Polynomial evaluation as an inner product).

By Proposition 8.23, the notions “a linear functional on Fn” and “a vector in Fn” are interchangeable. For a fixed point z∈F, the map sending a polynomial to its value at z is linear in the coefficients, hence an inner product against a fixed vector: for p∈F[X]<n with coefficient vector 𝐜=(c0,c1,…,cn−1),

p⁢(z)=c0+c1⁢z+⋯+cn−1⁢zn−1=⟨𝐜,(1,z,z2,…,zn−1)⟩.

Evaluating a committed polynomial at a challenge point is therefore an inner-product claim about the committed coefficient vector, which is the form of statement an inner-product argument proves (8.32).

8.5 The mixed inner product with group elements

The commitments of Halo 2 and Orchard pair a vector of scalars with a vector of group elements. This subsection develops their algebra over an abstract abelian group; the group used in practice, the points of an elliptic curve, is constructed in the elliptic-curve section later in the volume, and the results apply to it unchanged.

Construction 8.25 (Scalar multiplication by 𝔽r on a prime-order group).

Let (𝔾,+) be a finite abelian group of prime order r, written additively with identity 𝒪. For an integer a∈ℤ and G∈𝔾, write [a]G for the a-fold multiple of G—the additive reading of the powers of §3: [0]G=𝒪, [a]G=G+⋯+G with a summands for a>0, and [−a]G=−([a]G). The brackets separate the scalar notationally from the group element. The multiple [a]G depends only on the residue of a modulo r: the order of G divides |𝔾|=r (Corollary 3.30), and [a]G=[b]G whenever a≡b(modord(G)) (Proposition 3.12(2), read additively), so congruence modulo r suffices. The operation therefore descends to scalars in the field 𝔽r=ℤ/rℤ (4.26): for a∈𝔽r and G∈𝔾, define [a]G using any integer representative of a. The rest of the section uses this descended operation, which scales group elements by elements of a field.

Proposition 8.26 (𝔾 as an 𝔽r-vector space).

Let 𝔾 be an abelian group of prime order r, with the scalar multiplication of 8.25. Then 𝔾 is an 𝔽r-vector space of dimension 1; any element G≠𝒪 is a basis, and every element of 𝔾 is [a]G for a unique a∈𝔽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]([b]G)=[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, valid by commutativity and associativity (formally, induction on a), and the cases a≤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 𝔽r, and (𝔾,+) is an abelian group by hypothesis: 𝔾 is an 𝔽r-vector space.

Now let G≠𝒪. 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 ord(G)=r. The r multiples [0]G,[1]G,…,[r−1]G are then pairwise distinct (Proposition 3.12(2), additively: [a]G=[b]G forces a≡b(modr)), and 𝔾 has exactly r elements, so the multiples exhaust 𝔾. Thus {G} spans; and it is independent, since [a]G=𝒪 forces a=0 in 𝔽r, again because ord(G)=r. A one-element basis gives dim𝔽r𝔾=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 𝐆=(G1,…,Gn)∈𝔾n be a fixed tuple of group elements and 𝐚=(a1,…,an)∈𝔽rn 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

⟨𝐚,𝐆⟩=∑i=1n[ai]⁢Gi∈𝔾.

The angle-bracket notation of 8.21 is reused; 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 𝐆∈𝔾n. The map 𝐚↦⟨𝐚,𝐆⟩ is 𝔽r-linear from 𝔽rn to 𝔾:

⟨c⁢𝐚+c′⁢𝐚′,𝐆⟩=[c]⁢⟨𝐚,𝐆⟩+[c′]⁢⟨𝐚′,𝐆⟩for all ⁢c,c′∈𝔽r⁢ and ⁢𝐚,𝐚′∈𝔽rn.

Symmetrically, for fixed 𝐚∈𝔽rn the map 𝐆↦⟨𝐚,𝐆⟩ is a group homomorphism 𝔾n→𝔾, and is 𝔽r-linear when 𝔾n is viewed as an 𝔽r-vector space (componentwise, as in Example 8.3 with 𝔾 in place of F). Thus ⟨⋅,⋅⟩:𝔽rn×𝔾n→𝔾 is bilinear over 𝔽r.

Proof.

Both statements are the vector-space laws of 𝔾 (Proposition 8.26) applied componentwise. For the first,

⟨c⁢𝐚+c′⁢𝐚′,𝐆⟩=∑i[c⁢ai+c′⁢a′i]⁢Gi=∑i([c]⁢[ai]⁢Gi+[c′]⁢[a′i]⁢Gi)=[c]⁢∑i[ai]⁢Gi+[c′]⁢∑i[a′i]⁢Gi,

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 𝔾. For the second, linearity in 𝐆 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 (The mixed product as a commitment).

The element ⟨𝐚,𝐆⟩ is a commitment to the scalar vector 𝐚 under the public “basis” 𝐆, as at the opening of the section. Proposition 8.28 is its homomorphic property: the commitment to c𝐚+c′𝐚′ is the [c]-, [c′]-scaled combination of the individual commitments, computable by anyone holding those commitments and the scalars c,c′, without knowledge of 𝐚 or 𝐚′. Provided the Gi are chosen so that no party can exhibit a nontrivial relation ∑i[ai]Gi=𝒪—a computational hypothesis, the discrete-logarithm hardness assumption, made precise in later volumes of this series—the commitment is binding: the map 𝐚↦⟨𝐚,𝐆⟩ is computationally injective, in the sense that no feasible computation produces two vectors with the same image. The map is not injective once n≥2: it is linear from the n-dimensional 𝔽rn into the one-dimensional 𝔾 (Proposition 8.26), so by rank–nullity (Theorem 8.19) its kernel has dimension at least n−1. Collisions therefore exist in large number; binding asserts only that they cannot be found, a computational rather than information-theoretic statement. The classical Pedersen commitment to a single value a with randomness ρ is the special case n=2, with H≠𝒪,

[a]⁢G+[ρ]⁢H=⟨(a,ρ),(G,H)⟩,

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

8.6 Linear algebra in commitment and proof systems

The following remarks locate the preceding results in commitment and proof systems. They are descriptive; later volumes develop each point rigorously.

Remark 8.30 (Witnesses, constraints, and assignments).

An arithmetic circuit over 𝔽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 𝐳∈𝔽qN 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 𝐳, organised in practice as arrays of coefficients (one row per equation) acting on the assignment vector. Satisfying the linear constraints confines 𝐳 to a subspace of 𝔽qN (Example 8.7), or, when public inputs fix some entries, to a translate 𝐳0+W of one—an affine subspace. The multiplicative constraints are handled separately, by the polynomial methods 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 𝐚↦⟨𝐚,𝐆⟩ is a linear map 𝔽rn→𝔾 (Proposition 8.28), and every algebraic manipulation a verifier performs rests on this linearity: taking known linear combinations of commitments, folding two commitment keys 𝐆,𝐆′ into 𝐆+[x]𝐆′ under a challenge x, and checking claimed openings by re-evaluating the same linear map. A polynomial commitment is the same map applied to a coefficient vector, and an evaluation of the committed polynomial at a point z is the scalar inner product ⟨𝐜,(1,z,…,zn−1)⟩ (Remark 8.24).

Remark 8.32 (The inner-product relation).

The core statement an inner-product argument proves has the form: “I know vectors 𝐚,𝐛∈𝔽rn such that

P=⟨𝐚,𝐆⟩+⟨𝐛,𝐇⟩+[⟨𝐚,𝐛⟩]⁢U

for public 𝐆,𝐇∈𝔾n and U∈𝔾.” The equation combines three of this section’s constructions: two mixed inner products ⟨𝐚,𝐆⟩ and ⟨𝐛,𝐇⟩, committing to the witness vectors; one scalar inner product ⟨𝐚,𝐛⟩, 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 soundness of the argument reduces to the nondegeneracy of these forms together with the hardness of finding kernel elements of the commitment map.