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 F n , in practice
over a finite field F q ; and the mixed inner product of a vector of
scalars with a vector of group elements. For fixed public elements
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.
Let F be a field. A vector space over F (an
F -vector space) is a set V equipped with two operations,
vector addition
scalar multiplication is compatible with the multiplication of
F :
the identity of F acts as the identity:
scalar multiplication distributes over vector addition:
scalar multiplication distributes over scalar addition:
The elements of V are called vectors, the elements of F
scalars. We write a v for
The following consequences of the axioms are used hereafter without citation.
Let V be an F -vector space,
if
(1) By distributivity over scalar addition,
(2) Likewise
(3) Using the identity axiom, distributivity, and (1),
| v + (− 1) ⋅ v = 1 ⋅ v + (− 1) ⋅ v = (1 + (− 1)) ⋅ v = 0 ⋅ v = 0, |
so
(4) Suppose
| v = 1 ⋅ v = (a − 1 a) ⋅ v = a − 1 ⋅ (a v) = a − 1 ⋅ 0 = 0, |
the last step by (2). □
The principal example is the coordinate space
| F n = { (x 1, ..., x n) : x i ∈ F }, |
the set of n -tuples of scalars, under componentwise operations:
| (x 1, ..., x n) + (y 1, ..., y n) = (x 1 + y 1, ..., x n + y n), a ⋅ (x 1, ..., x n) = (a x 1, ..., a x n) . |
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
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.
Functions. For any set S , the set F S of all
functions
Matrices. The set F m × n of
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
A subset
A subset
W is closed under addition:
W is closed under scalar multiplication:
Equivalently, W is a subspace if and only if
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 0 W of W satisfies
Conversely, suppose (1)–(3) hold. Closure makes the two operations well
defined on W . The additive inverse of any
For the two-scalar form: if W is a subspace, then
In F 3 the set
Let V be an F -vector space.
The intersection ⋂ i ∈ I W i of an arbitrary family of subspaces of V is a subspace.
The sum
The union of two subspaces is in general not a subspace.
(1) Each W i contains 0 , so the intersection does. If
(2) The sum contains
| a ∑ j w j + b ∑ j w j ′ = ∑ j (a w j + b w j ′), |
and
For the union, take
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.
Let
| a 1 v 1 + a 2 v 2 + ⋯ + a k v k, a i ∈ F, v i ∈ 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
For any
The zero vector is the empty linear combination (or, for nonempty S ,
the combination 0 v ), 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
A finite list of vectors
| a 1 v 1 + ⋯ + a k v k = 0 ⟹ a 1 = ⋯ = a k = 0 . |
Otherwise the list is linearly dependent, and a relation
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
A list
Suppose first that
| ∑ i ≠ j a i v i + (− 1) v j = 0 |
is a dependence relation, its coefficient − 1 on v j being
nonzero (as
For the second statement, take a dependence relation
A basis of V is a linearly independent set B that spans
V . Every
| v = c 1 b 1 + ⋯ + c n b n, [v] B = (c 1, ..., c n), |
and call the scalars c i the coordinates of v in B .
The standard basis of F n is
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.
If
We prove by induction on
| v 1, ..., v k, w k + 1, ..., w n |
spans V . The case
For the induction step, suppose the hybrid list at stage
| v k + 1 = ∑ i ≤ k a i v i + ∑ j > k c j w j . |
Some coefficient c j with
| w k + 1 = c k + 1 − 1 (v k + 1 − ∑ i ≤ k a i v i − ∑ j > k + 1 c j w j) . |
Every vector of the stage- k list therefore lies in the span of the
stage-
Each step replaces one w by one v , so the induction reaches
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
Existence. Let
Invariance. Every basis is finite: if a basis contained more than
the n elements of a finite spanning list, any
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.
A function
| 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) = 0 } ⊆ 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
Let
| dim V = dim ker T + dim im T . |
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
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
We claim
Spanning. Any element of im T is T (v) for some
Independence. Suppose
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).
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.
A bilinear form on an F -vector space V is a function
| β (a u + a ′ u ′, v) = a β (u, v) + a ′ β (u ′, v), β (u, b v + b ′ v ′) = b β (u, v) + b ′ β (u, v ′), |
for all
Relative to a fixed basis
The standard inner product (or dot product) on F n is
| ⟨ a, b ⟩ = ∑ i = 1 n a i b i = a T b, a = (a 1, ..., a n), b = (b 1, ..., 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
( ⟨ e i, e j ⟩ is 1 if
Over R the standard inner product is positive definite:
| ⟨ a, a ⟩ = 1 2 + 2 2 = 1 + 4 = 5 = 0 |
in F 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.
For each
| F n ⟶ Hom (F n, F), a ⟼ ⟨ a, ⋅ ⟩, |
is an isomorphism of F -vector spaces onto the dual space Hom (F n, F) of all linear functionals on F n . In particular both spaces have dimension n .
Each
| φ (b) = ∑ i b i φ (e i) = ∑ i a i b i = ⟨ a, b ⟩, |
so
By Proposition 8.23, the notions “a linear
functional on F n ” and “a vector in F n ” are interchangeable.
For a fixed point
| p (z) = c 0 + c 1 z + ⋯ + c n − 1 z n − 1 = ⟨ c, (1, z, z 2, ..., z n − 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).
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.
Let
Let G be an abelian group of prime order r , with the scalar
multiplication of 8.25. Then G is an
F r -vector space of dimension 1 ; any element
The vector-space axioms are the standard laws of multiples. For
integers
Now let
Let
| ⟨ a, G ⟩ = ∑ i = 1 n [a i] G i ∈ G . |
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.
Fix
| ⟨ c a + c ′ a ′, G ⟩ = [c] ⟨ a, G ⟩ + [c ′] ⟨ a ′, G ⟩ for all c, c ′ ∈ F r and a, a ′ ∈ F r n . |
Symmetrically, for fixed
Both statements are the vector-space laws of G (Proposition 8.26) applied componentwise. For the first,
| ⟨ c a + c ′ a ′, G ⟩ = ∑ i [c a i + c ′ a i ′] G i = ∑ i ([c] [a i] G i + [c ′] [a i ′] G i) = [c] ∑ i [a i] G i + [c ′] ∑ i [a i ′] G i, |
using
The element ⟨ a, G ⟩ is a commitment to the
scalar vector a under the public “basis”
G , as at the opening of the section.
Proposition 8.28 is its homomorphic
property: the commitment
to
| [a] G + [ρ] H = ⟨ (a, ρ), (G, H) ⟩, |
which is moreover perfectly hiding: for fixed a , as ρ ranges uniformly over F r the term [ρ] H ranges uniformly over G (it is a bijection of G , by unique representation in the basis { H } ), so the commitment’s distribution is uniform and carries no information about a .
The following remarks locate the preceding results in commitment and proof systems. They are descriptive; later volumes develop each point rigorously.
An arithmetic circuit over 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
A Pedersen vector commitment
The core statement an inner-product argument proves has the form:
“I know vectors
| P = ⟨ a, G ⟩ + ⟨ b, H ⟩ + [⟨ a, b ⟩] U |
for public