To the memories of Jacob Feldman and Gian-Carlo Rota

# A spectral theory for combinatorial dynamics

James Propp  University of Massachusetts Lowell
Department of Mathematical Sciences https://jamespropp.org

###### Abstract.

This article proposes a framework for the study of periodic maps $T$ from a
(typically finite) set $X$ to itself when the set $X$ is equipped with one or
more real- or complex-valued functions. The main idea, inspired by the time-
evolution operator construction from ergodic theory, is the introduction of a
vector space that contains the given functions and is closed under composition
with $T$, along with a time-evolution operator on that vector space. I show
that the invariant functions and 0-mesic functions span complementary
subspaces associated respectively with the eigenvalue 1 and the other
eigenvalues. Alongside other examples, I give an explicit description of the
spectrum of the evolution operator when $X$ is the set of $k$-element
multisets with elements in $\\{0,1,\dots,n-1\\}$, $T$ increments each element
of a multiset by 1 mod $n$, and $g_{i}:X\rightarrow\mathbb{R}$ (with $1\leq
i\leq k$) maps a multiset to its $i$th smallest element.

###### Key words and phrases:

combinatorics, dynamics, invariant, homomesy, spectrum, ergodic

###### 1991 Mathematics Subject Classification:

05E18, 06A07; need to fix this

##  1\. Introduction

Recent work in dynamical algebraic combinatorics has paid a great deal of
attention to homomesies: numerical functions on a dynamical system with the
property that the average of the function over an orbit doesn’t depend on
which orbit one takes. Missing from this work is attention to invariants:
quantities that are constant on orbits. It would be conceptually helpful to
bring homomesies and invariants into a uniform framework. The article [PR]
that introduced the concept of homomesy provided this framework in the special
case of linear actions (see section 2.4 of that article), but most actions of
interest to combinatorialists are nonlinear (piecewise linear, birational, or
purely combinatorial). Here I introduce a vector space that may be the proper
setting for a unified treatment of homomesies and invariants; a periodic
action induces a diagonalizable linear map on the vector space, and the
spectrum of the map carries dynamical information about homomesies and
invariants for the action and its powers.

##  2\. Linearization

Given a set $X$, an invertible map $T$ from $X$ to itself satisfying
$T^{n}={\rm Id}_{X}$ (that is, $T^{n}(x)=x$ for all $x\in X$) with $n\geq 1$,
and a collection of functions $g_{1},\dots,g_{k}$ from $X$ to $\mathbb{C}$,
let $V$ be the linear span of all functions of the form $g_{i}\circ T^{j}$
with $1\leq i\leq k$, $0\leq j<n$. I will sometimes refer to the $g_{i}$’s as
statistics (or sometimes as the “original” statistics as opposed to the time-
shifted statistics $g_{i}\circ T^{j}$). $V$ is a finite-dimensional space of
dimension at most $kn$.

The role played by the $g_{i}$’s is crucial, much as the choice of an algebra
of measurable sets is crucial in ergodic theory. When we enlarge our set of
initial statistics we potentially enlarge $V$, and when we restrict our set of
initial statistics we potentially reduce $V$. As an extreme case, if our
collection of statistics is empty, $V$ is 0-dimensional regardless of the
dynamics of the map $T$.

For all $f\in V$ define $Uf\in V$ by $(Uf)(x)=f(T(x))$. We will call the
action of $U$ on $V$ the linearization of the original action of $T$ on $X$.
It is easy to check that $U$ sends $V$ to itself (e.g., $U$ sends $g_{i}\circ
T^{j}$ to $g_{i}\circ T^{j+1}$, which in the case $j=n-1$ is $g_{i}$); that
$U$ is linear; that $U^{n}$ is the identity map on $V$; and that $U$ has
inverse $U^{n-1}$. $V$ is the dynamical span of $g_{1},\dots,g_{k}$ in the
sense that it is the smallest vector space that contains $g_{1},\dots,g_{k}$
and is closed under the action of $U$. We will also call $V$ the dynamical
closure of the linear span of $g_{1},\dots,g_{k}$. The function $g_{i}\circ
T^{j}$ can also be written as $U^{j}g_{i}$.

Let us say that a function $f\in V$ is homomesic if
$\frac{1}{n}\sum_{j=0}^{n-1}U^{j}f$ is a constant function, and more
specifically c-mesic if $\frac{1}{n}\sum_{j=0}^{n-1}U^{j}f=c$ for all $x\in
X$, that is, if $\frac{1}{n}\sum_{j=0}^{n-1}f(T^{j}x)=c$ for all $x\in X$. Let
us say that a function $f\in V$ is invariant if $Uf=f$, that is, if
$f(Tx)=f(x)$ for all $x\in X$.

When $X$ is finite (as it will be except in sections 5 and 6) we create an
$|X|$-by-$kn$ matrix $M$ whose rows correspond to elements $x\in X$ (the order
in which the elements of $X$ are listed is unimportant) and whose columns from
left to right correspond to the respective functions
$g_{1},\dots,g_{k},Ug_{1},\dots,Ug_{k},\dots,U^{n-1}g_{1},\dots,U^{n-1}g_{k}$,
where the entry in the $x$ row and the $U^{j}g_{i}$ column is
$(U^{j}g_{i})(x)=g_{i}(T^{j}x)$; call $M$ the presenting matrix of $U$, and
note that $V$ can be identified with the span of the columns of $M$. In
particular, $\dim V$ is the rank of $M$.

Since $U^{n}=I$ (the identity map from $V$ to itself), $U$ is a diagonalizable
operator on $V$ whose eigenvalues are $n$th roots of unity; there exists a
basis for $V$ whose elements are eigenvectors for $U$. (Typically our
statistics are real-valued, but if we want to look at the eigenspaces
associated with eigenvalues other than 1 and $-1$ we need to treat $V$ as a
vector space over $\mathbb{C}$.) Let $V_{1}$ be the span of the 1-eigenvectors
(i.e., the nonzero elements $f\in V$ satisfying $Uf=1f=f$) and let
$V_{1}^{\perp}$ be the span of the other (non-unital) eigenvectors, so that
$V=V_{1}\oplus V_{1}^{\perp}$ and $\dim V$ = $\dim V_{1}+\dim V_{1}^{\perp}$.
(Note that despite the notation no inner product is involved; that is,
$V_{1}^{\perp}$ is a complement but not an orthocomplement.)

######  Proposition 1.

$V_{1}$ is the space of invariants and $V_{1}^{\perp}$ is the space of
0-mesies.

######  Proof 2.1.

If $f\in V_{1}$ then $Uf=1f=f$ and vice versa; hence $V_{1}$ is the space of
invariants. If $f\in V_{1}^{\perp}$ so that $f$ is in the span of the non-
unital eigenvectors then $f+Uf+U^{2}f+\cdots+U^{n-1}f=0$ (since in the case
where $f$ is a $\zeta$-eigenvector with $\zeta\neq 1$ we have
$f+Uf+U^{2}f+\cdots+U^{n-1}f=(1+\zeta+\zeta^{2}+\cdots+\zeta^{n-1})f=0f$).
Conversely, given $f$ satisfying $f+Uf+U^{2}f+\cdots+U^{n-1}f=0$, if we write
$f=f_{1}+f_{2}$ with $f_{1}\in V_{1}$ and $f_{2}\in V_{1}^{\perp}$ and we
apply $I+U+U^{2}+\cdots+U^{n-1}$ to $f_{1}+f_{2}$, we get $nf_{1}$, which can
only vanish if $f_{1}$ does, implying $f\in V_{1}^{\perp}$.

It follows that the multiplicity of 1 as an eigenvalue of $U$ gives the number
of linearly independent invariants in $V$ while the sum of the multiplicities
of the non-unital eigenvalues of $U$ gives the number of linearly independent
0-mesies in $V$. It is easy to show that every homomesic function $f$ can be
written uniquely as the sum of a constant function and a 0-mesic function,
specifically the constant function $g=(1/n)(f+Uf+U^{2}f+...+U^{n-1}f)$ and the
0-mesic function $h=f-g$.

In view of the complementary nature of $V_{1}$ and $V_{1}^{\perp}$, it might
be appropriate to refer to the elements of $V_{1}^{\perp}$ as “coinvariants”
rather than 0-mesies, but this word is already in use with a different
meaning. Another term for elements of $V_{1}^{\perp}$ that seems apt is
“survariants”, which has no existing meaning and in some ways seems preferable
to “0-mesies”; however, the terms “homomesy” and “homomesic” seem to have been
adopted to the point where a change in nomenclature might be confusing.

It is possible for $V_{1}$ to be trivial; for instance, if $X=\\{1,-1\\}$ with
$T(x)=-x$ of order $n=2$ equipped with the identity statistic $g_{1}(x)=x$,
then $V$ is 1-dimensional with $\dim V_{1}=0$ and $\dim V_{1}^{\perp}=1$.
However, for all examples considered in this paper $V_{1}$ will contain the
constant functions and hence have dimension $\geq 1$. As long as there is at
least one homomesic function $f$ that is not a 0-mesic, the nonzero constant
function $\sum_{j=0}^{n-1}U^{j}f$ is in $V$, so that the constant functions
form a 1-dimensional subspace of $V_{1}$.

I proceed to give alternative characterizations of $V_{1}$ and
$V_{1}^{\perp}$.

######  Proposition 2.

$f\in V_{1}$ if and only if there exists $g\in V$ with
$f=g+Ug+U^{2}g+\cdots+U^{n-1}g$.

######  Proof 2.2.

If $f=g+Ug+U^{2}g+\cdots+U^{n-1}g$ then $Uf=Ug+U^{2}g+U^{3}g+\cdots+U^{n}g=f$
(since $U^{n}g=g$), so $f\in V_{1}$. Conversely, suppose $f$ is in $V_{1}$.
Then putting $g=(1/n)f$ we have $f=g+Ug+U^{2}g+\cdots+U^{n-1}g$.

Consequently, the space of invariants is spanned by the sums
$f_{i}:=g_{i}+Ug_{i}+\cdots+U^{n-1}g_{i}$; call these the spanning invariants.
Since these $k$ functions span $V_{1}$, $\dim V_{1}\leq k$. If we divide the
presenting matrix into $n$ blocks of width $k$ and sum those blocks, we obtain
a matrix $M_{1}$ whose column span is $V_{1}$.

I next generalize Proposition 2 to eigenfunctions, exploiting the discrete
Fourier transform. Given $\zeta\in\mathbb{C}$ with $\zeta^{n}=1$, let
$V_{\zeta}$ be the space of $f\in V$ with $Uf=\zeta f$ (or equivalently
$\bar{\zeta}Uf=f$), so that $V_{1}^{\perp}$ is the direct sum of the spaces
$V_{\zeta}$ with $\zeta\neq 1$.

######  Proposition 3.

For $\zeta^{n}=1$, $f\in V_{\zeta}$ if and only if there exists $g\in V$ with
$f=g+\bar{\zeta}Ug+\cdots+\bar{\zeta}^{n-1}U^{n-1}g$.

######  Proof 2.3.

The proof of Proposition 2 applies to any linear operator $U^{\prime}$ on the
$\mathbb{C}$-vector space $V$ that satisfies $(U^{\prime})^{n}=I$, and in
particular applies to $U^{\prime}=\overline{\zeta}U$.

Consequently, the $\zeta$-eigenspace is spanned by the functions
$g_{i}+\bar{\zeta}Ug_{i}+\cdots+\bar{\zeta}^{n-1}U^{n-1}g_{i}$; let us call
these the spanning $\zeta$-eigenfunctions. We have $\dim V_{\zeta}\leq k$. If
we take the blocks discussed following the proof of Proposition 2 and sum them
with respective coefficients $1,\bar{\zeta},\bar{\zeta}^{2},\dots$, we obtain
a matrix $M_{\zeta}$ whose column span is $V_{\zeta}$.

I provide an alternate characterization of the elements of
$V_{1}^{\perp}=\bigoplus_{\zeta^{n}=1,\ \zeta\neq 1}V_{\zeta}$:

######  Proposition 4.

$f\in V_{1}^{\perp}$ if and only if there exists $g\in V$ with $f=g-Ug$.

(Note that we could just as well have used $Ug-g$ as $g$. A function of the
form $Ug-g$ is called a coboundary in dynamical system theory; it measures the
increase in $g$ from one moment to the next.)

######  Proof 2.4.

If $f=g-Ug$, then
$f+Uf+\cdots+U^{n-1}f=(g-Ug)+(Ug-U^{2}g)+\cdots+(U^{n-1}g-U^{n}g)=g-U^{n}g=0$
(since $U^{n}g=g$), so $f$ is 0-mesic and belongs to $V_{1}^{\perp}$.
Conversely, suppose $f$ is in $V_{1}^{\perp}$. Let
$h=1f+2Uf+3U^{2}f+\cdots+nU^{n-1}f$. Then

$\displaystyle h-Uh$ $\displaystyle=$ $\displaystyle\ \
(1U^{0}f+2U^{1}f+3U^{2}f+\cdots+(n-1)U^{n-2}f+nU^{n-1}f)$
$\displaystyle-(1U^{1}f+2U^{2}f+3U^{3}f+\cdots+(n-1)U^{n-1}f+nU^{n}f)$
$\displaystyle=$ $\displaystyle(U^{0}f+U^{1}f+U^{2}f+\cdots+U^{n-1}f)-nU^{n}f$
$\displaystyle=$ $\displaystyle 0-nf\ \ \mbox{(because $f$ is 0-mesic and
$U^{n}f=f$)}$ $\displaystyle=$ $\displaystyle-nf,$

so putting $g=-(1/n)h$ we have $f=g-Ug$.

If we are interested in counting all nonunital eigenvalues (with
multiplicity), we can just take the rank of the matrix $M-M^{\prime}$ where
$M$ is the presenting matrix and $M^{\prime}$ is obtained from $M$ by
cyclically shifting the columns $k$ positions to the right.

It should be stressed that in the framework being proposed here, 0-mesies can
be seen either as coboundaries of arbitrary functions or as combinations of
eigenfunctions of the time-evolution operator $U$. In particular, real
0-mesies can occur as combinations of complex eigenfunctions.

It may be helpful to note that the 0-mesies form the kernel of
$I+U+U^{2}+\cdots+U^{n-1}$, which Proposition 4 identifies as the image of
$I-U$; likewise, the invariants form the kernel of $I-U$, which Proposition 2
identifies as the image of $I+U+U^{2}+\cdots+U^{n-1}$; and more generally the
$\zeta$-eigenfunctions form the kernel of $I-\bar{\zeta}U$, which Proposition
3 identifies as the image of
$I+\bar{\zeta}U+\bar{\zeta}^{2}U^{2}+\cdots+\bar{\zeta}^{n-1}U^{n-1}$. In each
case we have a short exact sequence of vector spaces. Two function
$g_{1},g_{2}$ give rise to the same element of $V_{1}$ via Proposition 2 iff
they differ by an element of $V_{1}^{\perp}$, and two function $g_{1},g_{2}$
give rise to the same element of $V_{1}^{\perp}$ via Proposition 4 iff they
differ by an element of $V_{1}$.

Let us define $V^{(0)}$ as the intersection of $V_{1}^{\perp}$ with the span
of $g_{1},\dots,g_{k}$. There is a sense in which $V^{(0)}$ determines
$V_{1}^{\perp}$, namely, the linear combination
$\sum_{i,j}a_{i,j}\,U^{j}g_{i}$ is in $V_{1}^{\perp}$ if and only if the
linear combination $\sum_{i,j}a_{i,j}g_{i}$ (in which $U^{j}g_{i}$ is replaced
by $g_{i}$) is in $V_{1}^{\perp}$. That is because every function of the form
$U^{j}g-g$ is a coboundary (note that
$U^{j}g-g=U(g+Ug+\dots+U^{j-1}g)-(g+Ug+\dots+U^{j-1}g)$).

The sum of the multiplicities of the non-unital eigenvalues (that is, the
eigenvalues unequal to 1) gives us the dimension of the space of 0-mesies. The
dynamical significance of the specific multiplicities of individual non-unital
eigenvalues is subtler. For every $d$ dividing $n$, the sum of the
multiplicities of the eigenvalues $\zeta$ satisfying $\zeta^{d}=1$ is the
dimension of the space of invariants of $T^{d}$, while the sum of the
multiplicities of those $\zeta$ with $\zeta^{d}\neq 1$ is the dimension of the
space of 0-mesies of $T^{d}$. Additional meaning of the multiplicities appears
if, in the spirit of classical invariant theory, one extends $V$ to a ring
$R$, introducing statistics that are products of the $g_{i}$’s. Invariant
functions in the ring $R$ can arise from noninvariant eigenfunctions in $V$
associated with complex eigenvalues whose product is 1; see the paragraph
following the proof of Proposition 5. However, it should be noted that the
ring $R$ need not be graded by polynomial degree; e.g., in the example treated
in Proposition 5, each $g_{i}$ takes values in $\\{0,1\\}$ and hence satisfies
$g_{i}^{2}=g_{i}$. Also note that when the set $X$ is finite, the ring $R$
(being a set of functions with domain $X$), viewed as a vector space, must be
finite-dimensional.

##  3\. Example: Rowmotion in a Chain

Fix $n,k\geq 2$ and let $X_{n,k}$ be the set of $k$-element multisets with
elements belonging to $\\{0,1,\dots,n-1\\}$. Let us denote a generic element
of $X_{n,k}$ by $x=(x_{1},x_{2},\dots,x_{k})$ with $x_{1}\leq
x_{2}\leq\cdots\leq x_{k}$. We can represent an element of $X_{n,k}$ by
writing down its elements with appropriate multiplicities, in weakly
increasing order, with parentheses and intervening commas omitted. For
instance, $X_{3,3}=\\{000,001,002,011,012,022,111,112,122,222\\}$. I will use
superscripts to indicate repetition, e.g., I write
$X_{n,k}=\\{0^{k},0^{k-1}1,\dots,(n-1)^{k}\\}$. It is well-known that
$|X_{n,k}|={n+k-1\choose k}$.

Given $x=(x_{1},x_{2},\dots,x_{k})$, put $x_{0}=0$ and $x_{k+1}=n-1$, and for
$1\leq i\leq k$ define the reflections $\rho_{i}:X_{n,k}\rightarrow X_{n,k}$
by $\rho_{i}(x)=x^{\prime}$ where $x^{\prime}_{i}=x_{i-1}+x_{i+1}-x_{i}$ and
$x^{\prime}_{j}=x_{j}$ for all $j\neq i$. The $\rho_{i}$’s satisfy the Coxeter
relations $\rho_{i}^{2}=1$, $(\rho_{i}\rho_{i+1})^{3}=1$, and
$(\rho_{i}\rho_{j})^{2}=1$ for $|i-j|>1$, and thus form a representation of
the Coxeter group $A_{k}$.

Any product of all the $\rho_{i}$’s, each taken one at a time, is a Coxeter
element $\gamma$ satisfying $\gamma^{k+1}=1$. For convenience, we take
$\gamma_{n,k}=\rho_{k}\circ\cdots\circ\rho_{1}$ which updates entries from
left to right. For instance, $\gamma_{3,3}$ sends 000 to 002 to 022 to 222 to
000 and sends 001 to 012 to 122 to 111 to 001 and sends 011 to 112 to 011. We
have $\gamma_{n,k}(x)=x^{\prime}$ where
$x^{\prime}_{i}=x^{\prime}_{i-1}+x_{i+1}-x_{i}$; that is, the new value in
location $i$ equals the new value in location $i-1$ plus the old value in
location $i+1$ minus the old value in location $i$. The operation $\gamma$ can
be seen as a special case of piecwise-linear rowmotion on the order polytope
of a product of two chains in the case where one of the chains is of length 1.
For more on piecewise-linear rowmotion, see [EP2] and section 5 of this
article.

For $x=(x_{1},x_{2},\dots,x_{k})$ and $0\leq i\leq k+1$ let $g_{i}(x)=x_{i}$,
so that for instance $g_{1}(001)=0$, $g_{2}(001)=0$, and $g_{3}(001)=1$. The
maps $g_{i}:X\rightarrow\mathbb{R}$ ($1\leq i\leq k$) and $T:X\rightarrow X$
are all linear with respect to $x_{0},\dots,x_{k+1}$ so the dynamical span $V$
of $g_{1},\dots,g_{k}$ is easy to determine; it is spanned by
$g_{1},\dots,g_{k}$ along with the constant functions. Define $U$ as above.
The relation $x^{\prime}_{i}=x^{\prime}_{i-1}+x_{i+1}-x_{i}$ gives
$Ug_{i}=Ug_{i-1}+g_{i+1}-g_{i}$. If we apply $U^{j}$ to the preceding relation
and sum as $j$ goes from $0$ to $k$, we find that the orbit-averages of
$g_{i-1}$, $g_{i}$, and $g_{i+1}$ are in arithmetic progression. Since the
orbit-averages of $g_{0}$ and $g_{k+1}$ are 0 and $n-1$ respectively, we see
that $g_{i}$ is $c_{i}$-mesic with $c_{i}=i\frac{n-1}{k+1}$. The $k$ functions
$g_{i}-c_{i}$ ($1\leq i\leq k$) are the 0-mesies of this action while the
constant functions are the only invariants; together they span the full
$(k+1)$-dimensional vector space dynamically spanned by the $g_{i}$’s. The
action of $U$ on this space is a simple rotation whose spectrum assigns
multiplicity 1 to each $k+1$st root of 1. Concretely, $U$ acts as a cyclic
rotation on the functions $g_{1}-g_{0}$, $g_{2}-g_{1}$, …, $g_{k+1}-g_{k}$.

##  4\. Example: Multiset Rotation

Fix $n,k\geq 2$, and define $X_{n,k}$ as in section 3.

Let us define the rotation operator $T_{n,k}:X_{n,k}\rightarrow X_{n,k}$ that
increments each element of $x$ by 1 mod $n$, sending $i$ to $i+1$ for $i<n-1$
and sending $n-1$ to 0; for instance, $T_{3,3}(001)=112$ and
$T_{3,3}(112)=022$ (note that the 2 in 112 has become a 0 and has moved to the
left). It is obvious that $T_{n,k}^{n}$ is the identity on $X_{n,k}$. In
contexts where it is safe to do so without confusion, I will omit subscripts
on $X$ and $T$. Let $g_{i}(x)$ denote the $i$th smallest element of $x$ as
before, and let $U_{n,k}$ denote the time-evolution operator for the action
$f\mapsto f\circ T_{n,k}$ on the dynamical closure of the linear span of
$g_{1},\dots,g_{k}$.

It has been known for several years, as part of the unwritten lore of
dynamical algebraic combinatorics, that $g_{i}+g_{j}$ takes average value
$n-1$ on each orbit of $T$ whenever $i+j=k+1$ (including the case
$i=j=(k+1)/2$ when $k$ is odd). When we pass to the dynamical span we find the
invariants that were “missing” from earlier treatments of this example.

The case $n=2$ behaves differently than the general case, so we give it
separate consideration. Here the possible eigenvalues are $1$ and $-1$.

######  Proposition 5.

The multiplicities of the eigenvalues $1$ and $-1$ in the spectrum of
$U_{2,k}$ are $\lceil(k+1)/2\rceil$ and $\lfloor(k+1)/2\rfloor$ respectively.

######  Proof 4.1.

$X$ has $k+1$ elements; if $k$ is odd, $X$ consists of $(k+1)/2$ orbits of
size 2, and if $k$ is even, $X$ consists of $k/2$ orbits of size 2 and the
fixed point $0^{k/2}1^{k/2}$. Here I show the presenting matrix for $k=3$
whose columns correspond to the six functions $g_{1}$, $g_{2}$, $g_{3}$,
$Ug_{1}$, $Ug_{2}$, and $Ug_{3}$, and the presenting matrix for $k=4$ whose
columns correspond to the eight functions $g_{1}$, $g_{2}$, $g_{3}$, $g_{4}$,
$Ug_{1}$, $Ug_{2}$, $Ug_{3}$, and $Ug_{4}$:

$\left(\begin{array}[]{ccccccc}\,0&\,0&\,0&&\,1&\,1&\,1\\\ 0&0&1&&0&1&1\\\
0&1&1&&0&0&1\\\ 1&1&1&&0&0&0\end{array}\right)$
$\left(\begin{array}[]{ccccccccc}\,0&\,0&\,0&\,0&&\,1&\,1&\,1&\,1\\\
0&0&0&1&&0&1&1&1\\\ 0&0&1&1&&0&0&1&1\\\ 0&1&1&1&&0&0&0&1\\\
1&1&1&1&&0&0&0&0\end{array}\right)$

It is easy to see that for general $k$ the $k+1$ rows of the presenting matrix
are linearly independent, so that the matrix has rank $k+1$, which implies
that the dynamical span of the original vector space (the column-span of the
matrix) is $(k+1)$-dimensional. If we add the left half of the $(k+1)$-by-$2k$
presenting matrix to the right half, we get a matrix whose columns correspond
to the spanning invariants $g_{1}+Ug_{1}$, $g_{2}+Ug_{2},\dots$ and therefore
span the space of invariants. In the cases $k=3$ and $k=4$, these matrices are

$\left(\begin{array}[]{ccc}\,0&\,0&\,0\\\ 0&0&1\\\ 0&1&1\\\
1&1&1\end{array}\right)+\left(\begin{array}[]{ccc}\,1&\,1&\,1\\\ 0&1&1\\\
0&0&1\\\ 0&0&0\end{array}\right)=\left(\begin{array}[]{ccc}\,1&\,1&\,1\\\
0&1&2\\\ 0&1&2\\\ 1&1&1\end{array}\right)$

and

$\left(\begin{array}[]{cccc}\,0&\,0&\,0&\,0\\\ 0&0&0&1\\\ 0&0&1&1\\\
0&1&1&1\\\
1&1&1&1\end{array}\right)+\left(\begin{array}[]{cccc}\,1&\,1&\,1&\,1\\\
0&1&1&1\\\ 0&0&1&1\\\ 0&0&0&1\\\
0&0&0&0\end{array}\right)=\left(\begin{array}[]{cccc}\,1&\,1&\,1&\,1\\\
0&1&1&2\\\ 0&0&2&2\\\ 0&1&1&2\\\ 1&1&1&1\end{array}\right)$

For general $k$, the first $\lceil(k+1)/2\rceil$ rows of the matrix are
linearly independent and the remaining rows repeat earlier rows, so the rank
is $\lceil(k+1)/2\rceil$, so $\dim V_{1}=\lceil(k+1)/2\rceil$ as claimed. To
find $\dim V_{1}^{\perp}=\dim V_{-1}$, we subtract the two half-matrices
instead of adding, obtaining

$\left(\begin{array}[]{ccc}\,0&\,0&\,0\\\ 0&0&1\\\ 0&1&1\\\
1&1&1\end{array}\right)-\left(\begin{array}[]{ccc}\,1&\,1&\,1\\\ 0&1&1\\\
0&0&1\\\ 0&0&0\end{array}\right)=\left(\begin{array}[]{rrr}-1&-1&-1\\\
0&-1&0\\\ 0&1&0\\\ 1&1&1\end{array}\right)$

and

$\left(\begin{array}[]{cccc}\,0&\,0&\,0&\,0\\\ 0&0&0&1\\\ 0&0&1&1\\\
0&1&1&1\\\
1&1&1&1\end{array}\right)-\left(\begin{array}[]{cccc}\,1&\,1&\,1&\,1\\\
0&1&1&1\\\ 0&0&1&1\\\ 0&0&0&1\\\
0&0&0&0\end{array}\right)=\left(\begin{array}[]{rrrr}-1&-1&-1&-1\\\
0&-1&-1&0\\\ 0&0&0&0\\\ 0&1&1&0\\\ 1&1&1&1\end{array}\right)$

in the cases $k=3$ and $k=4$. The first $\lfloor(k+1)/2\rfloor$ rows of the
matrix are linearly independent and each of the remaining rows is either the
zero vector or the negative of an earlier row, so the rank is
$\lfloor(k+1)/2\rfloor$, so $\dim V_{-1}=\lfloor(k+1)/2\rfloor$ as claimed.

Following up on my earlier remark about invariant theory at the end of section
2, let us pause to consider the quadratic invariant
$(g_{1}+...+g_{k})(Ug_{1}+...+Ug_{k})$, equal to the number of 1’s in $x$
times the number of 1’s in $Tx$ (or, equivalently, the number of 0’s in $x$
times the number of 1’s in $x$). If for all $i$ we put
$s_{i}=(g_{i}+Ug_{i})/2$ (an eigenfunction for the eigenvalue 1) and
$a_{i}=(g_{i}-Ug_{i})/2$ (an eigenfunction for the eigenvalue $-1$) so that
$g_{i}=s_{i}+a_{i}$ and $Ug_{i}=s_{i}-a_{i}$, then putting $S=s_{1}+...+s_{k}$
and $A=a_{1}+...+a_{k}$ we see that the quadratic invariant equals
$(S+A)(S-A)=S^{2}-A^{2}$. This representation shows us explicitly how the
quadratic invariant arises from all the possible pairs of eigenfunction
$s_{i},s_{j}$ with the eigenvalue $1$ and all the possible pairs of
eigenfunction $a_{i},a_{j}$ with the eigenvalue $-1$.

We now consider $n>2$.

######  Proposition 6.

For $n>2$, the multiplicity of the eigenvalue $\zeta$ in the spectrum of
$U_{n,k}$ is $\lfloor k/2\rfloor+1$ when $\zeta=1$ and $k$ when $\zeta\neq 1$.

######  Proof 4.2.

I prove the second claim first. Given $\zeta\neq 1$ with $\zeta^{n}=1$, define
$h_{i}=g_{i}+\bar{\zeta}Ug_{i}+\bar{\zeta}^{2}U^{2}g_{i}+\cdots+\bar{\zeta}^{n-1}U^{n-1}g_{i}$
for $1\leq i\leq k$ (the spanning $\zeta$-eigenfunctions; see Proposition 3).
Since these functions span $V_{\zeta}$, $\dim V_{\zeta}\leq k$. To prove the
reverse inequality and thereby prove equality it suffices to find a
$k$-element subset of $X$, call it $Y=\\{y^{(1)},\dots,y^{(k)}\\}$, so that
the vectors $(g_{i}(y^{(1)}),\dots,g_{i}(y^{(k)}))^{t}$ (with $1\leq i\leq k$)
are linearly independent; that is, we need the $k$-by-$k$ matrix $M$ whose
$i,j$th entry is $g_{i}(y^{(j)})$ to be nonsingular. Let
$y^{(j)}=0^{k-j+1}1^{j-1}$. Then $M$ has only four distinct entries:

$\displaystyle W$ $\displaystyle=$ $\displaystyle
0+1{\zeta}+2{\zeta}^{2}+\cdots+(n-2){\zeta}^{n-2}+0{\zeta}^{n-1}$
$\displaystyle N$ $\displaystyle=$ $\displaystyle
0+1{\zeta}+2{\zeta}^{2}+\cdots+(n-2){\zeta}^{n-2}+(n-1){\zeta}^{n-1}$
$\displaystyle S$ $\displaystyle=$ $\displaystyle
1+2{\zeta}+3{\zeta}^{2}+\cdots+(n-1){\zeta}^{n-2}+0{\zeta}^{n-1}$
$\displaystyle E$ $\displaystyle=$ $\displaystyle
1+2{\zeta}+3{\zeta}^{2}+\cdots+(n-1){\zeta}^{n-2}+(n-1){\zeta}^{n-1}$

(For later use, note that

$\displaystyle(1-{\zeta})(S-N)$ $\displaystyle=$
$\displaystyle(1-{\zeta})(1+{\zeta}+{\zeta}^{2}+\cdots+{\zeta}^{n-2}-(n-1){\zeta}^{n-1})$
$\displaystyle=$ $\displaystyle
1-{\zeta}^{n-1}-(n-1){\zeta}^{n-1}+(n-1){\zeta}^{n}$ $\displaystyle=$
$\displaystyle n(1-{\zeta}^{n-1})$

which is nonvanishing for all $n>1$ and that

$\displaystyle(1-{\zeta})(E-W)$ $\displaystyle=$
$\displaystyle(1-{\zeta})(1+{\zeta}+{\zeta}^{2}+\cdots+{\zeta}^{n-2}+(n-1){\zeta}^{n-1})$
$\displaystyle=$ $\displaystyle
1-{\zeta}^{n-1}+(n-1){\zeta}^{n-1}-(n-1){\zeta}^{n}$ $\displaystyle=$
$\displaystyle(n-2)({\zeta}^{n-1}-1)$

which vanishes for $n=2$ and is nonvanishing for $n>2$.)

When $k$ is odd, $M$ has the form illustrated below for $k=3$ and $k=5$.

$\left(\begin{array}[]{ccc}N&N&N\\\ W&N&E\\\ W&S&E\end{array}\right)\ \ \ \
\left(\begin{array}[]{ccccc}N&N&N&N&N\\\ W&N&N&N&E\\\ W&W&N&E&E\\\
W&W&S&E&E\\\ W&S&S&S&E\end{array}\right)$

Note that each matrix is split by diagonal and antidiagonal lines into four
zones, each of which has all entries equal. Similarly, when $k$ is even, $M$
has the form illustrated below for $k=4$ and $k=6$.

$\left(\begin{array}[]{cccc}N&N&N&N\\\ W&N&N&E\\\ W&W&E&E\\\
W&S&S&E\end{array}\right)\ \ \ \ \left(\begin{array}[]{cccccc}N&N&N&N&N&N\\\
W&N&N&N&N&E\\\ W&W&N&N&E&E\\\ W&W&W&E&E&E\\\ W&W&S&S&E&E\\\
W&S&S&S&S&E\end{array}\right)$

Let $D_{k}(N,E,S,W)$ denote the determinant of the $k$-by-$k$ matrix of the
above form, where for now $N,E,S,W$ are to be treated as formal
indeterminates. There are many ways to evaluate these determinants, but my
favorite is the following argument, communicated to me by Joe Buhler. If we
subtract $W/E$ times the last column from the first column, so that the only
nonvanishing entry in the first column is $N-(E/W)N=N(E-W)/E$, we obtain the
recurrence

$D_{k}(N,E,S,W)=(N(E-W)/E)\ D_{k-1}(E,S,W,N)$

(where the cyclic rotation of the arguments corresponds to 90 degree rotation
of the submatrix). With this recurrence and the initial condition
$D_{2}(N,E,S,W)=N(E-W)$ it is easy to prove the general formula

$D_{2i+r}(N,E,S,W)=\left\\{\begin{array}[]{ll}(-1)^{i}N(N-S)^{i-1}(W-E)^{i}&\mbox{if
$r=0$,}\\\ (-1)^{i}N(N-S)^{i}(W-E)^{i}&\mbox{if $r=1$}\end{array}\right.$

by induction. When $\zeta\neq 1$ we have $N-S\neq 0$ and $W-E\neq 0$ as noted
earlier so $D_{k}(N,E,S,W)\neq 0$, proving that the matrix is nonsingular as
claimed. (This is the part of the proof that assumes $n>2$; we have $W=E$ when
$n=2$.)

It remains to consider $\zeta=1$. In this case we have $N=S$ so the matrix is
singular. Indeed, the last $\lfloor(k-1)/2\rfloor$ rows of $M$ coincide with
earlier rows, showing that the corank is at least $\lfloor(k-1)/2\rfloor$, or
equivalently that the rank is at most $\lceil(k+1)/2\rceil=\lfloor
k/2\rfloor+1$. But it is easy to see that the first $\lfloor k/2\rfloor+1$
rows of $M$ are linearly independent, so equality holds, as claimed.

This proof was greatly facilitated by the fact that we did not need to work in
a basis, but were able to find a manageable spanning set of vectors.

It is worth noting that all the non-unital eigenvalues in our example have
equal multiplicity. Of course, the rationality of the entries of the matrix
implies that two Galois-conjugate roots of 1 (i.e., roots that are primitive
$m$th roots for the same $m$) must have the same multiplicity, but a priori
roots that are not Galois-conjugate could have different multiplicities.
Indeed, consider the rotation action $T_{4,2}$ restricted to multisets in
which all elements are distinct; this set consists of the six elements 01, 02,
03, 12, 13, and 23, and rotation sends sends 01 to 12 to 23 to 03 to 01 and
sends 02 to 13 to 02. The interested reader can verify that 1 has multiplicity
2, $-1$ has multiplicity 2, and $i$ and $-i$ each have multiplicity 1, so in
this case the non-unital eigenvalues do not all have the same multiplicity.

##  5\. Example: Rowmotion on a product of two chains

Recall from [S1] the definitions of a partially ordered set $P$, order ideals
(or downsets), filters (or upsets), and antichains, and from [S2] and [EP1]
the definitions of the order polytope ${\mathcal{O}}(P)$, reverse order
polytope $\tilde{{\mathcal{O}}}(P)$, and chain polytope ${\mathcal{A}}(P)$ of
a poset. For notation, I remind the reader that the order polytope of a finite
poset $P$ is the set of order-preserving maps $\lambda:P\rightarrow[0,1]$,
viewed as a subset of $\mathbb{R}^{|P|}$ in the natural way. Put
$X={\mathcal{O}}(P)$, $Y={\mathcal{A}}(P)$, $Z=\tilde{{\mathcal{O}}}(P)$, and
$T=\rho_{{\mathcal{P}}}$. Piecewise-linear rowmotion $\rho_{{\mathcal{P}}}$
(defined in [EP2]) is a volume-preserving invertible map from the order
polytope to itself related to Striker and Williams’ original definition of
rowmotion for order ideals [SW]. When $P$ is $[a]\times[b]$,
$\rho_{{\mathcal{P}}}$ is of order $n:=a+b$. For each $p\in P$, define the
evaluation statistic $1_{p}(\lambda)=\lambda(p)\in[0,1]$, so that we have
statistics of the form $1_{p}\circ T^{j}$ ($0\leq j\leq n-1$, $p\in P$)
spanning a vector space $V$ of dimension at most $nab$. Let $U$ be the time-
evolution operator on the space $V$ sending $f\in V$ to $f\circ T\in V$.

Einstein and Propp, in unpublished work that was later generalized by Joseph
and Roby (see sections 4 and 6 of the September 1, 2018 version of [EP1] and
Theorem 5.12 in [JR]), showed that piecewise-linear rowmotion, although
originally defined as a composition of piecewise-linear involutions (toggle
operators), can be obtained as a composition of three transfer operators
$\nabla:X\rightarrow Y$, $\Delta^{-1}:Y\rightarrow Z$, and
$\Theta:Z\rightarrow X$, mirroring the original definition of rowmotion in the
work of Brouwer and Schrijver [BS]. My goal in this section is to assert that
linearization is “functorial” in the sense that the linearization of
piecewise-linear rowmotion can be expressed as a composition of three
linearized transfer operators. It is not my goal here to prove this assertion
nor even to make the assertion plausible; I merely aim to make the content of
the assertion clear by demonstrating it in the case $a=b=2$ (the simplest case
in which the piecewise-linear map $T$ is not merely linear or affine).

In the transfer operator formulation, $\rho_{{\mathcal{P}}}$ for an arbitrary
finite poset $P$ is expressed as the composition
$\Theta\circ\Delta^{-1}\circ\nabla$ where $\nabla$ (down-transfer) is a
piecewise-linear map from $X$ to $Y$, $\Delta^{-1}$ (inverse up-transfer) is a
piecewise-linear map from $Y$ to $Z$, and $\Theta$ (complementation) is an
affine map from $Z$ back to $X$. In the case $a=b=2$, for $x\in X$ put
$y=\nabla(x)$, $z=\Delta^{-1}(y)$, and $x^{\prime}=\Theta(z)$ so that
$Tx=x^{\prime}$. Explicitly,

$\displaystyle\nabla(x_{1},x_{2},x_{3},x_{4})$ $\displaystyle=$
$\displaystyle(x_{1}-0,\>x_{2}-x_{1},\>x_{3}-x_{1},\>x_{4}-\max(x_{2},x_{3})),$
$\displaystyle\Delta^{-1}(y_{1},y_{2},y_{3},y_{4})$ $\displaystyle=$
$\displaystyle(y_{1}+\max(y_{2},y_{3})+y_{4},\>y_{2}+y_{4},\>y_{3}+y_{4},\>y_{4}),\
\mbox{and}$ $\displaystyle\Theta(z_{1},z_{2},z_{3},z_{4})$ $\displaystyle=$
$\displaystyle(1-z_{1},\>1-z_{2},\>1-z_{3},\>1-z_{4}).$

To reduce the complexity of the notation let us use $x_{1},x_{2},x_{3},x_{4}$
to denote the coordinate functions mapping $X$ to $\mathbb{R}$, and likewise
for the $y$ and $z$ variables. The dynamical closure of
$x_{1},x_{2},x_{3},x_{4}$ in $X$ under the action of
$\Theta\circ\Delta^{-1}\circ\nabla$ is 6-dimensional, with additional basis
functions $x_{5}=\max(x_{2},x_{3})$ and the constant function $x_{6}=1$. The
dynamical closure of $y_{1},y_{2},y_{3},y_{4}$ in $Y$ under the action of
$\nabla\circ\Theta\circ\Delta^{-1}$ is 6-dimensional, with additional basis
functions $y_{5}=\max(y_{2},y_{3})$ and $y_{6}=1$. The dynamical closure of
$z_{1},z_{2},z_{3},z_{4}$ in $Z$ under the action of
$\Delta^{-1}\circ\nabla\circ\Theta$ is 6-dimensional, with additional basis
functions $z_{5}=\max(z_{2},z_{3})$ and $z_{6}=1$. With these extra variables
we have

$\displaystyle U_{\nabla}(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})$
$\displaystyle=$
$\displaystyle(x_{1},\,x_{2}\\!-\\!x_{1},\,x_{3}\\!-\\!x_{1},\,x_{4}\\!-\\!x_{5},\,x_{5}\\!-\\!x_{1},\,x_{6}),$
$\displaystyle U_{\Delta^{-1}}(y_{1},y_{2},y_{3},y_{4},y_{5},y_{6})$
$\displaystyle=$
$\displaystyle(y_{1}\\!+\\!y_{4}\\!+\\!y_{5},\,y_{2}\\!+\\!y_{4},\,y_{3}\\!+\\!y_{4},\,y_{4},\,y_{4}\\!+\\!y_{5},\,y_{6}),\
\mbox{and}$ $\displaystyle U_{\Theta}(z_{1},z_{2},z_{3},z_{4},z_{5},z_{6})$
$\displaystyle=$
$\displaystyle(z_{6}\\!-\\!z_{1},\,z_{6}\\!-\\!z_{2},\,z_{6}\\!-\\!z_{3},\,z_{6}\\!-\\!z_{4},\,z_{5}\\!+\\!z_{6}\\!-\\!z_{2}\\!-\\!z_{3},\,z_{6})$

which demonstrates linear relations among all the quantities. (Those who wish
to check the formulas should be mindful that at one point one needs to use the
identity $\max(s,t)+\min(s,t)=s+t$.) Note that
$U_{\Theta\circ\Delta^{-1}\circ\nabla}=U_{\nabla}\,U_{\Delta^{-1}}\,U_{\Theta}$.

A similar picture prevails for birational rowmotion (see [EP2]), where now the
monoid is multiplicative rather than additive, along the lines of the example
presented in the next section.

##  6\. Example: The Lyness 5-cycle

Here I revisit an example from section 2.6 of [PR]. The Lyness 5-cycle (the
smallest nontrivial cluster algebra) exhibits a non-obvious homomesy: if $X$
is the set of all $(x,y)$ in $\mathbb{R}^{2}$ with $x$, $y$, $x+1$, $y+1$, and
$x+y+1$ all nonzero, and $T:X\rightarrow X$ is the period-5 map sending
$(x,y)$ to $(y,(y+1)/x)$, and $g:X\rightarrow\mathbb{R}$ is the map sending
$(x,y)$ to $\log|x^{-1}+x^{-2}|$, then $g$ is 0-mesic.

To fit this into the proposed framework, let us use the multiplicative monoid
generated by the functions $x$, $y$, $x+1$, $y+1$, and $x+y+1$; technically
this is not a vector space unless we allow fractional exponents, but for
present purposes this turns out not to matter. The map $T$ sends
$x^{a}y^{b}(x+1)^{c}(y+1)^{d}(x+y+1)^{e}$ to
$x^{a^{\prime}}y^{b^{\prime}}(x+1)^{c^{\prime}}(y+1)^{d^{\prime}}(x+y+1)^{e^{\prime}}$
where

$\left(a^{\prime}\ b^{\prime}\ c^{\prime}\ d^{\prime}\
e^{\prime}\right)=\left(a\ b\ c\ d\ e\right)\left(\begin{array}[]{rrrrr}0&\
-1&\ \ \ 0&\ -1&\ -1\\\ 1&0&0&0&0\\\ 0&0&0&0&1\\\ 0&1&1&0&1\\\
0&0&0&1&0\end{array}\right).$

This 5-by-5 matrix $M$ satisfies $M^{5}=I$, and each of the 5th roots of unity
occurs in the spectrum with multiplicity 1.

The Lyness 5-cycle is associated with four-row frieze patterns. The above
analysis can also be applied to frieze patterns with more than four rows; the
details differ slightly according to whether the number of rows is odd or
even. The eigenvalues still have dynamical meaning, inasmuch as they determine
the dimensionalities of spaces of invariants for powers of the shift-map;
however, the eigenvalues do not appear to be associated with anything like
eigenvectors, since it is unclear how to to make sense of expressions like
$x^{\alpha}y^{\beta}(x+1)^{\gamma}(y+1)^{\delta}(x+y+1)^{\epsilon}$ when
$\alpha,\beta,\gamma,\delta,\epsilon$ are algebraic numbers.

##  7\. Flatness

I have already remarked that, for a map $T$ of period $n$, the rationality of
the entries of the presenting matrix implies that two Galois-conjugate $n$th
roots of 1 must have the same multiplicity. When $n$ is prime, this implies
that all non-unital eigenvalues have the same multiplicity, but when $n$ is
composite, the function that maps eigenvalues to multiplicities (hereafter the
spectral multiplicity function) could a priori be far from constant. It is
therefore somewhat surprising that for many examples, the spectral
multiplicity function is “flat” in a logarithmic sense, meaning that its
values are bounded by constant multiples of one another. For instance, in
Proposition 4.1 the multiplicity takes on two values whose ratio approaches 1
as $k$ gets large, while in Proposition 4.2 the multiplicity takes on two
values whose ratio approaches 2 as $k$ gets large.

I do not have a quantitative conjecture, but I suggest that this phenomenon –
the flatness of the spectral multiplicity function – might apply in many
situations. To the extent that this flatness is prevalent, it would provide a
loose explanation for the relative paucity of invariants in comparison with
homomesies. For, if the multiplicities of distinct eigenvalues always have
ratio between $1/c$ and $c$ (with $c>1$), then the multiplicity of 1 divided
by the sum of all the multiplicities must also be between $1/c$ and $c$,
implying that $\dim V/\dim V_{1}^{\perp}$ is between $n/c$ and $nc$. That is,
homomesies outnumber invariants roughly by a factor of $n-1$.

Acknowledgments: The author thanks Joe Buhler, David Einstein, Darij Grinberg,
Michael Joseph, and Tom Roby for helpful suggestions.

References

[BS] Andries Brouwer and Alexander Schrijver, On the period of an operator,
defined on antichains. Math. Centrum report ZW 24/74 (1974).

[EP1] David Einstein and James Propp, Combinatorial, piecewise-linear, and
birational homomesy for products of two chains. Preprint;
https://arxiv.org/abs/1310.5294.

[EP2] David Einstein and James Propp, Combinatorial, piecewise-linear, and
birational homomesy for products of two chains. To appear in Algebraic
Combinatorics.

[JR] Michael Joseph and Tom Roby, Birational and noncommutative lifts of
antichain toggling and rowmotion. To appear in Algebraic Combinatorics.

[PR] James Propp and Tom Roby, Homomesy in Products of Two Chains. Electronic
Journal of Combinatorics, Volume 22, Issue 3 (2015), article P3.4.

[S1] Richard Stanley, Enumerative Combinatorics, vol 1.

[S2] Richard Stanley, Two Poset Polytopes. Discrete Comput. Geom. 1 (1986),
no. 1, 9–23.

[SW] Jessica Striker and Nathan Williams, Promotion and rowmotion. European
Journal of Combinatorics 33 (2012), 1919–1942.


# Proof of Deep Learning: Approaches, Challenges, and Future Directions

Mahmoud Salhab  Department of Computer Science and Mathematics
Lebanese American University
Beirut, Lebanon
<EMAIL_ADDRESS>Khaleel Mershad  Department of Computer Science and
Mathematics
Lebanese American University
Beirut, Lebanon
<EMAIL_ADDRESS>
###### Abstract

The rise of computational power has led to unprecedented performance gains for
deep learning models. As more data becomes available and model architectures
become more complex, the need for more computational power increases. On the
other hand, since the introduction of Bitcoin as the first cryptocurrency and
the establishment of the concept of blockchain as a distributed ledger, many
variants and approaches have been proposed. However, many of them have one
thing in common, which is the Proof of Work (PoW) consensus mechanism. PoW is
mainly used to support the process of new block generation. While PoW has
proven its robustness, its main drawback is that it requires a significant
amount of processing power to maintain the security and integrity of the
blockchain. This is due to applying brute force to solve a hashing puzzle. To
utilize the computational power available in useful and meaningful work while
keeping the blockchain secure, many techniques have been proposed, one of
which is known as Proof of Deep Learning (PoDL). PoDL is a consensus mechanism
that uses the process of training a deep learning model as proof of work to
add new blocks to the blockchain. In this paper, we survey the various
approaches for PoDL. We discuss the different types of PoDL algorithms, their
advantages and disadvantages, and their potential applications. We also
discuss the challenges of implementing PoDL and future research directions.

###### Index Terms:

Proof-of-Work, consensus mechanism, Proof-of-Deep-Learning, machine learning,
blockchain.

##  I Introduction

Blockchain technology at its core is a type of distributed ledger that enables
multiple users to achieve consensus without the need for a central authority.
Additionally, it ensures the immutability of the stored records, thereby
providing tamper-proofness. Bitcoin [8] is the most famous application that
uses Proof of Work (PoW) as its consensus mechanism. The consensus algorithm
is a crucial component of a blockchain network system. It helps make the
system decentralized, transparent, auditable, secure, and tamper-resistant.
The algorithm works by offering incentives to users who participate in the
network, ensuring that everyone follows the rules and works towards the same
goal [37].

Miners of Bitcoin consume a lot of computational resources due to the large
amount of hash calculation required by PoW [29, 28]. According to [1] the
annual electrical energy consumed by the Bitcoin network is estimated to be
87.2 TWh as of 2019, which is similar to the consumption of a country such as
Belgium. To mitigate the amount of energy required, various solutions have
been proposed, such as using an Application-Specific Integrated Circuit (ASIC)
machine [33], using different consensus algorithms instead of PoW, such as
Proof of Stake (PoS) [28], Proof of Activity (PoA) [46], and Proof of Useful
Work (PoUW) [33].

After the introduction of the PoUW concept, which aims to utilize
computational power and wasted resources for solving hash puzzles in the PoW
algorithm, researchers have been exploring ways to employ these resources to
do useful things. For example, Primecoin [35] is a type of altcoin that
utilizes a unique mining process where miners are required to find a specific
prime number sequence known as Cunningham chains, as an alternative to the
usual hash puzzles. While the discovery of Cunningham chains through this
mining process holds mathematical and research significance, its practical
applications in the real world remain uncertain [12]. Similarly, the Proof of
Exercise (PoX) is a proposed mechanism outlined in [36] that falls under the
PoUW category, requiring miners to perform specific exercises and provide
proof of their outcomes. However, one significant limitation of the PoX
mechanism is its reliance on an outsourced centralized board, which diminishes
the decentralization feature of the blockchain.

To develop high-performance deep learning (DL) models, significant
computational and memory resources are often required [19, 34]. To address
this, researchers have proposed a novel approach that involves utilizing the
computational power traditionally used for proof of work in blockchain to
instead be used for training DL models. The supervised training of DL models
is used to secure the blockchain in the Proof of Deep Learning [11]. However,
the model proposed in [11] relies heavily on the integrity of the data
provider. The authors in [2] surveyed the benefits of integrating deep
learning and blockchain for data security, automatic decision-making,
cumulative judgments, and enhanced robustness. They also touched on the
concept of proof of deep learning but did not go into much detail.

In this study, we explore the nascent idea of using deep learning as a proof
of work, which is still in its formative years and has a lot of potential for
growth. Our research delves into the latest advances in this field and
examines the various types of PoDL algorithms, including their benefits,
drawbacks, and potential applications. Furthermore, we investigate the
obstacles associated with implementing PoDL and identify potential areas for
future research. To the best of our knowledge, this is the first paper that
provides a comprehensive overview of the latest advances in PoDL. The paper is
intended to be a valuable resource for researchers who are interested in
learning more about this rapidly evolving field.

The paper is structured as follows: we start in section II by giving a high-
level background of the blockchain and deep learning. In Section III, we delve
into the details of PoDL. Following this, Section IV examines the challenges
associated with PoDL systems. In Section V, we discuss the current state and
potential future directions of PoDL. Finally, we summarize our findings and
conclude the paper in Section VI.

##  II Background

###  II-A Cryptocurrencies and Blockchain

The blockchain is a distributed network of interconnected nodes that operate
in a peer-to-peer manner, enabling the transfer of digital assets without the
need for any intermediaries [3]. Blockchain was originally built to support
the work of the most famous cryptocurrency, Bitcoin [4].

Blockchain is a publicly distributed ledger that comprises a chain of blocks
that store transactions. The chain expands continuously when a new block is
added to it [5]. All the transactions are processed in a decentralized way,
which eliminates the need to have intermediaries to validate and verify them
[6].

Decentralization, transparency, immutability, and auditability are among the
essential features of blockchain technology, as outlined in [7].

In the Bitcoin blockchain, the system comprises a list of blocks where each
block consists of three main items [8]:

  * •

Merkle Tree represents the transaction data.

  * •

The previous block’s cryptographic hash, except for the first block (the
”Genesis Block”) where it is hard coded.

  * •

A nonce number used for consensus and validation.

For a blockchain to be considered valid, all of its blocks must be valid. A
block, in turn, is considered valid if:

  * •

Each transaction in the block is valid.

  * •

Contains the hash of the previous block (except for the first block).

  * •

The hash of the entire block (the hash of the concatenation of the nonce, the
hash of the previous block, and the Merkel tree) is less than a pre-defined
value which is called the target difficulty.

The target difficulty of a blockchain is frequently updated to maintain a
consistent block generation rate (for example, 10 minutes in Bitcoin ) based
on the network hash rate [8].

Bitcoin leverages the Hashcash algorithm [43], which entails the miners
competing to validate a block by solving a hash puzzle. Miners compete to find
the nonce value that meets the target difficulty. The hash function SHA-256 is
utilized in Bitcoin due to its puzzle-friendliness property [33].

The process of hash puzzle solving which is known as Proof of Work (PoW) is
expensive and requires substantial computational power as well as specialized
hardware. All miners compete to propose the next block, and the first node
that solves the puzzle will be compensated for its effort. The reward will be
in the form of bitcoins, where the winner node receives two types of fees,
which are [44]:

  * •

Transaction fees: These fees are paid by the creators of the block
transactions to the miners.

  * •

Block reward: The miner of the block mints a number of bitcoins, which
decreases over time.

In the absence of a central node that everybody trusts to ensure that all
nodes have the same ledger, there is a need for a process where nodes agree on
the truth in such a trustless distributed network. In blockchain, this process
is known as consensus, below are some of the conventional methods for
achieving consensus in the blockchain:

  * •

Proof of Work (PoW): Participants, also known as miners, will do an exhaustive
search (i.e. brute force) to find the best nonce value that meets the target
hash. Once it’s found, the node that solved the puzzle will disseminate the
block throughout the network, and then the block will be validated. Once it’s
validated, it will be added to the blockchain. The primary apprehension with
the PoW approach is that miners are required to expend substantial resources
in order to solve the puzzle and generate a block.

  * •

Proof of Stake (PoS): In this method, miners don’t have to solve a
mathematical puzzle, hence it’s computationally efficient. The validation is
done by selecting specific nodes for block validation. The chance of being
selected is mainly correlated with the stake or the wealth of the node.

  * •

Delegated proof-of-stake (DPoS): In this elective consensus process, nodes
that hold a stake in the network have the option to delegate transaction
validation to another node through a voting process.

  * •

Byzantine Fault Tolerance: Involves a group of nodes agreeing on a collective
course of action such as validating a transaction, and was developed based on
research on the Byzantine fault [39].

  * •

Proof of Authority: Similar to BFT, PoA involves delegating specific nodes in
the network with authoritative control to achieve consensus based on majority
votes when validating a block.

  * •

Proof of Elapsed Time: Similar to PoA, PoET chooses a leader to generate new
blocks in the blockchain by linking response time to a timer and selecting the
node with the shortest expiration time as the leader.

  * •

Proof of Burn: Requires validators to spend or burn their coins to create a
new block and receive a reward. This process enhances the validator’s stake in
the network, while also reducing the number of coins in circulation and
increasing the value of the remaining coins due to the coin-burning mechanism.

  * •

Proof of Importance: Similar to PoA, this consensus mechanism selects
validating nodes based on their stake in the network, but in this case, the
stake is determined by their history of successful transactions and
validations.

  * •

Proof of Capacity: Also known as Proof of Space or Proof of Storage, it
operates as an alternative to PoW by storing all possible nonce values on the
hard drives of participating nodes.

###  II-B Deep Learning

As a result of the increase in computational power and data accessibility,
deep learning [32] has experienced significant achievements across a range of
application domains.

There are four categories into which various forms of deep learning can be
grouped, as noted by [47]:

  * •

Deep Supervised Learning, which utilizes labeled data for training purposes.

  * •

Deep Semi-supervised Learning, which operates on partially labeled data.

  * •

Deep Unsupervised Learning, which does not rely on labeled data during the
training process.

  * •

Deep Reinforcement Learning, which is a technique used for learning in
unfamiliar environments.

Given a model that maps input features X to target Y, where X represents the
input data and Y is the target or the label of X, which can be continuous in
the case of regression tasks and discrete in the case of classification tasks.
Different optimization methods, such as SGD, Adagrad, AdaDelta, RMSprop, and
Adam can be used to train the model on the given data [48]. These optimization
techniques are used to minimize an objective function, which measures how good
the model’s predictions are. It is important to note that this function must
be differentiable, as these optimization methods use gradients to
minimize/maximize the objective function.

The training process is done by iteratively performing the below steps:

  1. 1.

The neural network processes input data, generates predictions and produces
outputs by applying weights to the input and activating functions.

  2. 2.

The cost function evaluates the disparity between the predicted and actual
outputs. This is used as a measure of how well the neural network is
performing.

  3. 3.

Gradients are calculated using the cost function. These gradients are used to
update the weights in the neural network.

  4. 4.

In the backward pass, the gradients calculated in step 3 are utilized for
updating the weights of the neural network, which assists in enhancing the
network’s performance. This process is repeated many times until the network
reaches an acceptable level of accuracy.

Training a model on a large dataset can be challenging as it may not be
feasible to pass the entire dataset at once. Therefore, the dataset is split
into smaller batches that can be used iteratively to train the model. An epoch
refers to the point where all batches have passed through the model once
during the training process. Typically, model training involves multiple
epochs rather than a single epoch.

In order to prevent overfitting where the model memorizes the training data,
it is essential to split the data into training and testing sets. In practical
scenarios, this data is further split into three sets:

  * •

Training set: This is the data that the model will be trained on.

  * •

Validation set: Used during the training process to select the parameters that
lead to the best performance.

  * •

Test set: Used to test the actual model performance.

The training and validation data are utilized to train the model and fine-tune
the hyperparameters. On the other hand, the test data is leveraged to evaluate
how the model performs on unseen data.

A diverse set of metrics are available for evaluating the efficacy of models,
such as Accuracy, Precision, Recall, and F1-score, among others.

##  III Proof of Deep Learning (PoDL)

In this section, we present a summary of how PoDL operates and the key
participants involved in the PoDL-based network. We conducted a thorough
investigation of existing research and examined the strategies employed to
address the following aspects:

  * •

Approaches for rewarding honest mining participants.

  * •

Methodologies for task initiation and model submission.

  * •

Block validation and acceptance criteria, along with techniques for verifying
the entire blockchain.

  * •

Techniques employed to handle short model training time and enable incremental
training across blocks.

  * •

Approaches used to tackle challenges such as double spending, self-publishing,
data privacy, and model size.

The original PoW technique requires nodes to compete to find out a nonce value
in such a way that the resulting block hash meets certain criteria. This
process is computationally expensive and does not utilize the computational
resources for useful operations. To address this issue, PoDL was proposed. In
PoDL, nodes compete to train deep learning models and use trained models as
evidence of the work they’ve done. This results in utilizing the computational
resources as well as making the blockchain robust against tampering by making
it computationally infeasible for malicious nodes to tamper with any block.

Figure 1: Proof of deep learning (PoDL) Workflow.

Most of the proposed techniques such as in [10, 11, 12, 13, 14, 15, 16, 17]
rely on three main participants for achieving consensus in PoDL, which are:

  * •

Miners: The nodes within the network contend with one another to append new
blocks onto the chain. In the original PoW consensus mechanism, miners compete
to resolve a computationally difficult hash puzzle. In the PoDL consensus
mechanism, miners contend to submit trained models as proof of work. For this
reason, some researchers refer to them as ”trainers” (e.g., [10]).

  * •

Full nodes: These nodes uphold the blockchain and authenticate the work of
miners by scrutinizing their performance (e.g., accuracy, precision, recall,
etc. of the submitted models). Some researchers such as in [10] call these
nodes ”validators” because they handle the validation of the submitted models.

  * •

Task/Data publishers: These are the nodes in the network that are responsible
for publishing machine learning training tasks to the network. For this
reason, some researchers refer to them as ”suppliers” (e.g., [10]) while
others call them ”model requesters” such as in [11]. These tasks include the
training data, testing data, metrics, the minimum threshold for each metric,
the model architecture to be trained, and any other hyper-parameters.

PoDL was originally proposed in [11] as a method for training deep learning
models on decentralized networks. The workflow of PoDL can be divided into
seven phases:

  1. 1.

Training data release: The data publisher releases the training data,
hyperparameters, pre-trained model (if any), and any other necessary
requirements for conducting the training to all miners.

  2. 2.

Training: The miners train the released model (if there is any) on the
released training data.

  3. 3.

Block header submission: Once the miners finish the training, they compute the
value of the hash of the trained parameters for the model and then send the
header of the block to the full nodes.

  4. 4.

Testing data release: The data publisher releases the test data (or part of
it) to all nodes.

  5. 5.

Assessing model performance: The nodes then utilize the test data to calculate
the trained model’s accuracy.

  6. 6.

Model submission: Once the nodes have finished calculating the accuracy; the
trained model, together with the block, is submitted for validation.

  7. 7.

Block selection: The validators then assess the submitted models’ accuracy and
sort the models based on their accuracy. Once that is done, the validators
then accept the first model with the highest accuracy. In the event of a tie,
the first block sent will be chosen, or some researchers prefer to choose the
smallest model size, as in [10].

Figure 1 illustrates an overview of the workflow described above from the task
generation by the task publisher till the block gets added to the blockchain
by the full nodes.

###  III-A Design of Reward

In the original PoW-based blockchain, the miners are rewarded with transaction
fees and block rewards for successfully solving a computationally difficult
puzzle [30].

In PoDL, several approaches for reward distributions have been proposed. For
example, in [10], the authors proposed a PoDL blockchain where miners are
rewarded by task publishers for training the best-performing model for a given
task. The PoDL blockchain validators are compensated equally with a
transaction fee provided by the task publisher as well as new WekaCoins. The
proposed method also prevents the task publisher from participating in the
competition by training on the test data. This is because the task publisher
would have to pay for both itself and the validators, which is infeasible from
the task publisher’s point of view.

In [16], the authors designed a reward mechanism that incentivizes miners to
train models for task publishers. In this system, task publishers pay miners
to train a model on their data. The miners are rewarded with the publisher’s
payment. No new coins are generated in this process, which prevents the task
publisher from participating in the competition.

###  III-B Task initiation process

Task initiation is the process of requesting a model to be trained on a
specific dataset. In [10], researchers proposed a special transaction called a
“task publication transaction” while in [17] the authors call it “data
transaction”. In this transaction, the task publisher proposes a challenge to
train a model. This transaction contains the information required to complete
the task, such as the dataset, the desired performance, and the reward for
completing the task.

Once the task transaction is ready to be instantiated, it is important to
digitally sign both the transaction and the data [10]. This will prevent any
malicious intermediary in the network from manipulating the data to make other
nodes perform maliciously. For example, an attacker could modify the data in a
way that causes other nodes to train on incorrect data. This would waste the
resources of the other nodes and increase the attacker’s chance of winning the
next block.

###  III-C Model submission process

Once a miner node completes the training process, to inform the network that a
trained model is ready, the authors in [10] used a special transaction called
“model transaction” wherein the trainer puts forth a solution for a specific
task. The model transaction is digitally signed to prevent any manipulation by
intermediaries. This is similar to the task initiation transaction, which is
also digitally signed. The digital signatures ensure that the transactions
have not been tampered with, and that they are created by an authorized
sender. This contributes to the fairness and integrity of the competition
data[31].

###  III-D Validation and Block Acceptance Criteria

In the original PoW-based blockchain, the first miner that proposes a valid
block will get its block appended to the blockchain [8]. The work acceptance
criterion in PoDL is dependent on the metrics specified by the task publisher.
Once the task publisher releases the testing data, the miners then send the
calculated metrics, together with the model, to the full nodes. The latter
check the metrics and sort all of the submitted models by accuracy. The most
accurate model is then accepted by the full nodes. Furthermore, to ensure that
no node steals a trained model from other nodes during the model submission
process, all nodes are first required to submit the header of the block that
includes the hash of the model parameters as well as the result in some cases.
This ensures that even if a node steals a trained model from another, when it
submits the stolen model, the validator will check the submitted header as
well as the model, by passing the test set to the model and checking if they
match their claimed results in the header of the block, as well as the model
parameters’ hash. If it is not matched or if the miner submits a trained model
without submitting the block header, the block will be rejected. Additionally,
since the test data is published after the block header is submitted by the
miners, the resulting model trained on the test data by any node will result
in an invalid claim between the actual model results and the claimed ones in
the block header [18].

In [13], an extra layer called the secure mapping layer (SML) was used to
prevent model theft. This layer allows nodes to share their models in the
network without having to submit the block header beforehand as mentioned
above, since the SML is treated as part of the model. The SML takes the input
data concatenated with the current and the previous block hashes as input to
the model. Consequently, the input features of the model are dependent on
miner information due to the coinbase. Thus, the act of model stealing can
negatively impact model performance, as the node attempting to steal the model
would introduce unseen features during training, leading to poor performance.

###  III-E Short time training handling and incremental training

In many blockchain systems, the pace of block creation is fixed. For example,
every 10 minutes, the Bitcoin network generates a new block [8]. However,
complex deep learning models can take days or even weeks to train, especially
if the model and the data will be trained on is large or the desired accuracy
is high. As a result, miners may not be able to complete more than a single
epoch of training during this time period. This can lead to low-accuracy
models, as miners are not able to train their models on enough data or for
longer periods of time.

In order to address this issue, researchers have proposed a number of
solutions. One approach proposed in [11] and adopted in [18] is to allow
miners to train their models over multiple blocks. In this approach, the task
publisher does not gather the trained model unless the accuracy of the model
does not vary throughout a number of blocks. This ensures that miners have
enough time to train their models on enough data to achieve the desired
accuracy. However, there is a potential for cheating in this approach. Since
the task publisher will expose the test data to mine the first block, it is
possible for a malicious node to deceive by training the model on data from
the test set and achieve the highest accuracy in the next block. To prevent
this, it is important for the task publisher to publish a fresh and new test
set for each block. This allows validators to validate the work over each
block. Miners keep training their models on the same training set, but they
are evaluated on a fresh test set each time. This helps to ensure that miners
are not cheating by training their models to the current testing data.

In [14], the authors used a similar approach, but instead of blindly relying
on the accuracy to settle and not change for a certain number of blocks, they
used short-term target accuracy and desired accuracy. The desired accuracy
takes longer to achieve than the block generation rate, and it is achieved by
incremental improvements based on short-term goals. These short-term targets
can be achieved within a pre-defined time window that is less than or equal to
the block generation rate. The short-term targets are based on the results of
the last task. For example, if the last task achieved 90% accuracy while the
desired accuracy is 95%, the next short target might be 92%.

Other researchers have made assumptions in their designs that prioritize the
block generation rate over the model training. For example, in [12, 15], the
authors prioritize the block generation rate by assuming that the model
training can be interrupted. This assumption is based on the fact that many
machine learning models are trained using gradient-based optimization, which
can be interrupted without losing much progress as long as the miners save the
best checkpoint.

###  III-F Double Spending Prevention

Double spending happens when an amount of money is spent more than once, and
the transaction is successfully processed for each spending. This is done by
transferring a certain amount of coins (in the case of cryptocurrencies) to
user A, and then transferring the same amount to user B [27, 26]. Double
spending attacks are deterred by the block acceptance policy mentioned
previously, where only the block created by the trainer that trained the
highest accurate model is accepted by the validators. The authors in [11] used
the same techniques and found that double spending is unlikely to occur when
the majority (i.e., 51%) of full nodes are controlled or owned by a single
entity. This is because the global optimum is not known in advance, so when
only the most accurate models are accepted, it becomes difficult to improve
upon the best-performing model. Their claim is supported by the fact that the
model’s accuracy is dependent on randomly chosen hyperparameters and initial
weights.

In DLchain [14], an attacker can launch a double spending attack by forking
the blockchain several blocks behind and then building a longer chain above
that forked block. However, this attack is unlikely to be successful because
the honest miners will be able to build a longer chain on top of the main
chain faster than the attacker can; this is similar to the analysis conducted
in the original Bitcoin paper [8]. As a consequence, the attacker will never
be able to successfully double-spend any transactions.

The authors in [10, 12, 13, 16] did not consider a double spending attack that
could be carried out by utilizing the test data released by the task
publisher. Since the test data is released to the network by the task
publisher to allow the validators to validate the results, a malicious node
could perform a double-spending attack via training a model on data from the
test set. The number of examples in the test set is always substantially less
than the training data, so the computational resources needed to train the
model on it are negligible. If the attacker can create a fork in the
blockchain, the block generation on the fork chain will be faster than the
honest miners who generate blocks on the primary chain. Furthermore, if the
intruder controls the majority of the network’s nodes, this becomes critical.
This kind of attack is also possible even if the training process is carried
out over multiple blocks. In this case, the attacker might only train on a
subset of the test data, to ensure that the test result is higher than the
best-performing model. To prevent such an attack from happening, the authors
in [11] mandated that all models submitted to the competition must be
reproducible. This means that in order to verify the block, any full node has
to be willing to retrain the winning model on the training set.

###  III-G Blockchain verification

In the original blockchain proposed by Nakamoto [8], the blockchain can be
validated by verifying the proof of work by recalculating the hash of each
block.

In PoDL, to check the validity of the entire blockchain (e.g., by the newcomer
full nodes), full nodes require access to the trained model as well as the
data to validate the blockchain. This is done by checking the blockchain block
by block. For each block, the node checks the claimed accuracy, the trained
model by the winner miner, and the generated block. To make the verification
process easy for any new node, it is necessary for the task publisher and full
nodes to upload the required data and models so that new full nodes can
download them. This approach was adopted by several authors such as in [12,
15].

In addition to the above criteria, in the approach proposed in [11], the
miners are required to provide all the parameters and configurations used,
such as hyperparameters, initial weights, number of epochs, etc. This is to
give the full nodes the flexibility and ability to verify their work by
reproducing and retraining the model.

###  III-H Model size handling

Deep learning models can vary in size from a few kilobytes to several
gigabytes. Storing these model parameters can be storage-consuming. However,
there are a variety of methods that can be used to minimize the total storage
required such as:

  * •

Model compression: Many techniques have been used to minimize the trained
model size without impacting the accuracy of the models such as in [20, 21,
22, 23, 24, 25].

  * •

Limiting the model size: The miners or task publishers are limited to a
certain model size (e.g. 10MB/model in [20, 21]). This can help to reduce the
overall storage needed.

  * •

Removing low-performing models: This can be done if the model training process
is done over multiple blocks. If a model is not performing well, it can be
removed without jeopardizing the integrity of the blockchain. This is because
the tamper-proofing of the blockchain is guaranteed by the high-accuracy
models. This approach was used in [11, 12, 15].

###  III-I Data privacy

According to [38], individuals have the right to regulate the collection,
utilization, and distribution of their personal information, which is also
known as data privacy, data protection, or information privacy.

The training and testing data published by the task publisher may contain
sensitive information. The authors in [13] proposed a solution to this problem
by using data encryption. They utilized two forms of ciphertexts which are: 1)
inner-product functional encryption (IPFE) [40] and 2) IPFE with function-
hiding (IPFE-FH) [41]. It serves to secure the privacy of data and prevent it
from being abused.

###  III-J Selfish Publisher Attack

This kind of attack was first discussed in [14]. Since the identities of the
miners and the task publisher are not known, there is nothing to prevent the
task publisher from participating as a miner node.

This attack is common when the training process is done over multiple blocks
and the desired accuracy is achieved by setting short-term goals for each
block. The attack is carried out when the task publisher has already
pretrained a model in order to win the block reward. The publisher can carry
out the attack in two different ways:

  1. 1.

Set the short-term goal to be easy to win the reward using its pre-trained
model.

  2. 2.

Set the short-term goal to a high value in such a way the training takes a
long time to reach the desired target, and the publisher can generate valid
blocks with its pre-trained model.

For the first attack, the authors in [14] solved it by discarding the blocks.
This is because too short block intervals of block generation indicate that
the difficulty of the task is low.

The second attack is very difficult to carry out after reaching a certain
accuracy. This is because there is competition between nodes, and the attacker
must produce a well-trained model that requires resources to achieve. As a
result, it may be infeasible to carry out the attack.

If task publishers pay nothing or only a small amount of money for the
submitted tasks and there is a block reward and transaction fees, this type of
attack may be feasible. However, section III-A discusses how the reward
structure can be designed to prevent such attacks.

##  IV PoDL Challenges

The authors in [42] studied the challenges of proof-of-useful-work (PoUW)
systems. These challenges can be summarized and reflected in PoDL as follows:

  * •

Block sensitivity and non-reusability: Without these properties, it would be
possible to pre-calculate future blocks using existing proofs-of-work. To
retain block sensitivity, the hash from the preceding block must be used in
the current block. To retain non-reusability, it is necessary to bind the
validity of a PoW to the block it validates.

  * •

Adjustable problem hardness: The hardness of the given problems can be
adjusted to meet the target difficulty, ensuring a consistent block generation
rate. This is crucial in PoDL, as having a large dataset with complex models,
the best-performing node -in terms of its computational power- may not be able
to complete a short-term goal, or even complete a single epoch.

  * •

Fast verification: A full node needs to have the capability to quickly verify
the validity of a block proposed by the miners. This is done by checking the
proof-of-work done by the miners. In the case of PoDL, if the full nodes are
going to retrain the model to verify the work done, it might not be a good
idea. This is because having a complex model and large data may lead to
slowing down the verification process, which in turn allows attackers to
perform spam attacks on the network.

  * •

Problem is parallelizable: miners should utilize their full computational
power to propose the next block. In PoDL, this can be done by utilizing
vectorization to optimize and speed up the training process.

##  V Discussion and Future Directions

Even though PoDL is a growing field of interest in the research community, and
not that much work has been done in that field, it’s promising as it, on one
hand, can maintain the immutability and security of the blockchain network,
while on the other hand, it makes the process more efficient and helps in the
development of other fields such as AI.

PoDL enables researchers and developers to submit a training task and get the
results without the need for manually setting up a training environment on the
cloud or internal infrastructure. It benefits both parties the researcher and
developer on one hand and the miners and the blockchain on the other hand, by
providing a trained model to researchers/developers and compensating miners
for their work, thereby aiding the blockchain network’s security. Furthermore,
researchers and developers can conduct numerous experiments with various model
architectures and hyperparameters utilizing the blockchain network. Different
nodes can execute a diverse set of experiments, saving individuals time and
resources.

Despite the progress that has been made, and the advantages that PoDL brings,
there is still a lot of work to be done to improve the current systems. Here
are some of the aspects that need further investigation and research:

  * •

Data privacy: As we mentioned earlier, data may contain sensitive information.
However, not much work has been done in this area to protect the submitted
data by the task publisher.

  * •

Double spending attack: As we mentioned in our work, there is still no fully
mature system that prevents such attacks from happening. As mentioned earlier,
an attacker could use the test data and train the model on it to perform a
double spending attack by creating a fork in the blockchain.

  * •

Continuous task suppliers: It is critical to have a continuous stream of tasks
that can be published to the miners to train models. If there are no tasks,
the network will be jeopardized.

  * •

ASIC hardware: The Application-Specific Integrated Circuit (ASIC) hardware is
a chip created for a specific task. In cryptocurrency mining, ASICs are
preferred over general-purpose CPUs and GPUs as they offer better efficiency.
However, there is limited research on the impact of ASIC hardware designed for
Bitcoin on PoDL. It may be necessary to use new hardware like Tensor
Processing Units (TPUs) for PoDL [11].

  * •

Collusion prevention: Strategies must be applied to prevent malicious
collaboration among the primary participants of the network - validators,
trainers, and suppliers.

##  VI Conclusion

In this work, we reviewed the latest approaches for PoDL as an example of
PoUW. We have discussed the workflow of different PoDL algorithms and their
advantages and disadvantages, the network participants, and their
interactions. We have also discussed the challenges of implementing PoDL and
future research directions.

PoDL is a promising new consensus mechanism that has the potential to shift
the resources used in the Proof of Work (PoW) to be more useful. However, some
challenges must still be overcome before PoDL can be widely used. One
challenge is that PoDL requires the model publishers to continuously provide
the network with new tasks. Another challenge is data privacy.

Despite these challenges, PoDL is a promising new technology, and we believe
that PoDL has the potential to make PoW-based blockchains more efficient.

## References

  * [1] A. de Vries, “Bitcoin’s energy consumption is underestimated: A market dynamics approach,” Energy Research & Social Science, vol. 70, p. 101721, 2020, doi: https://doi.org/10.1016/j.erss.2020.101721.
  * [2] M. Shafay, R. W. Ahmad, K. Salah, I. Yaqoob, R. Jayaraman, and M. Omar, “Blockchain for deep learning: review and open challenges,” Cluster Computing, vol. 26, no. 1, pp. 197–221, Feb. 2023, doi: 10.1007/s10586-022-03582-7.
  * [3] T. Aste, P. Tasca, and T. Di Matteo, “Blockchain technologies: The foreseeable impact on society and industry,” 2017.
  * [4] A. A. Monrat, O. Schelén and K. Andersson, ”A Survey of Blockchain From the Perspectives of Applications, Challenges, and Opportunities,” in IEEE Access, vol. 7, pp. 117134-117151, 2019, doi: 10.1109/ACCESS.2019.2936094.
  * [5] K. Salah, M. H. U. Rehman, N. Nizamuddin and A. Al-Fuqaha, ”Blockchain for AI: Review and Open Research Challenges,” in IEEE Access, vol. 7, pp. 10127-10149, 2019, doi: 10.1109/ACCESS.2018.2890507.
  * [6] A. Litke, D. Anagnostopoulos, and T. Varvarigou, “Blockchains for supply chain management: Architectural elements and challenges towards a global scale deployment,” Logistics, vol. 3, no. 1, p. 5, 2019.
  * [7] M. Kouhizadeh and J. Sarkis, “Blockchain practices, potentials, and perspectives in greening supply chains,” Sustainability, vol. 10, no. 10, p. 3652, 2018.
  * [8] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” Decentralized business review, p. 21260, 2008.
  * [9] A. Baldominos and Y. Saez, ‘Coin.AI: A proof-of-useful-work scheme for blockchain-based distributed deep learning’, arXiv [cs.NE], 23-Mar-2019.
  * [10] F. Bravo-Marquez, S. Reeves and M. Ugarte, ”Proof-of-Learning: A Blockchain Consensus Mechanism Based on Machine Learning Competitions,” 2019 IEEE International Conference on Decentralized Applications and Infrastructures (DAPPCON), Newark, CA, USA, 2019, pp. 119-124, doi: 10.1109/DAPPCON.2019.00023.
  * [11] C. Chenli, B. Li, Y. Shi and T. Jung, ”Energy-recycling Blockchain with Proof-of-Deep-Learning,” 2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), Seoul, Korea (South), 2019, pp. 19-23, doi: 10.1109/BLOC.2019.8751419.
  * [12] B. Li, C. Chenli, X. Xu, Y. Shi, and T. Jung, ‘DLBC: A deep learning-based consensus in blockchains for deep learning services’, arXiv [cs.DC], 15-Apr-2019.
  * [13] Y. Liu, Y. Lan, B. Li, C. Miao, and Z. Tian, ‘Proof of Learning (PoLe): Empowering neural network training with consensus building on blockchains’, Computer Networks, vol. 201, p. 108594, Dec. 2021.
  * [14] C. Chenli, B. Li, and T. Jung, “DLchain: Blockchain with Deep Learning as Proof-of-Useful-Work,” in Services – SERVICES 2020, 2020, pp. 43–60.
  * [15] B. Li, C. Chenli, X. Xu, T. Jung, and Y. Shi, “Exploiting Computation Power of Blockchain for Biomedical Image Segmentation,” Jun. 2019.
  * [16] A. Merlina, “BlockML: a useful proof of work system based on machine learning tasks,” Dec. 2019, pp. 6–8. doi: 10.1145/3366624.3368156.
  * [17] A. Mittal and S. Aggarwal, “Hyperparameter Optimization Using Sustainable Proof of Work in Blockchain,” Frontiers in Blockchain, vol. 3, 2020, doi: 10.3389/fbloc.2020.00023.
  * [18] X. Luo, P. Yang, W. Wang, Y. Gao, and M. Yuan, “S-PoDL: A two-stage computational-efficient consensus mechanism for blockchain-enabled multi-access edge computing,” Physical Communication, vol. 46, p. 101338, 2021, doi: https://doi.org/10.1016/j.phycom.2021.101338.
  * [19] H. Jia et al., Proof-of-Learning: Definitions and Practice. 2021.
  * [20] S. Han, H. Mao, and W. J. Dally, Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding. 2016.
  * [21] Y. Gong, L. Liu, M. Yang, and L. Bourdev, Compressing Deep Convolutional Networks using Vector Quantization. 2014.
  * [22] P. Nakkiran, R. Álvarez, R. Prabhavalkar, and C. Parada, “Compressing deep neural networks using a rank-constrained topology,” 2015.
  * [23] R. Gheissari, E. Lubetzky, and Y. Peres, Concentration inequalities for polynomials of contracting Ising models. 2017.
  * [24] Y. Liu and M. K. Ng, “Deep neural network compression by Tucker decomposition with nonlinear response,” Knowledge-Based Systems, vol. 241, p. 108171, 2022, doi: https://doi.org/10.1016/j.knosys.2022.108171.
  * [25] X.-Y. Liu, Y. Fang, L. Yang, Z. Li, and A. Walid, “Chapter 9 - High-performance tensor decompositions for compressing and accelerating deep neural networks,” in Tensors for Data Processing, Y. Liu, Ed. Academic Press, 2022, pp. 293–340. doi: https://doi.org/10.1016/B978-0-12-824447-0.00015-7.
  * [26] A. Kaushik, A. Choudhary, C. Ektare, D. Thomas and S. Akram, ”Blockchain — Literature survey,” 2017 2nd IEEE International Conference on Recent Trends in Electronics, Information & Communication Technology (RTEICT), Bangalore, India, 2017, pp. 2145-2148, doi: 10.1109/RTEICT.2017.8256979.
  * [27] H. T. M. Gamage, H. D. Weerasinghe, and N. G. J. Dias, “A Survey on Blockchain Technology Concepts, Applications, and Issues,” SN Computer Science, vol. 1, no. 2, p. 114, Apr. 2020, doi: 10.1007/s42979-020-00123-0.
  * [28] F. Saleh, “Blockchain without waste: Proof-of-stake,” The Review of financial studies, vol. 34, no. 3, pp. 1156–1190, 2021.
  * [29] G. Ramezan and C. Leung, ”Analysis of Proof-of-Work-Based Blockchains Under an Adaptive Double-Spend Attack,” in IEEE Transactions on Industrial Informatics, vol. 16, no. 11, pp. 7035-7045, Nov. 2020, doi: 10.1109/TII.2020.2977689.
  * [30] S. Yoo, ”Analysis and Design of an Incentive Scheme for a Proof-of-Work Blockchain.” Order No. 28722682, University of California, Los Angeles, United States – California, 2021.
  * [31] W. Fang, W. Chen, W. Zhang, J. Pei, W. Gao, and G. Wang, “Digital signature scheme for information non-repudiation in blockchain: a state of the art review,” EURASIP Journal on Wireless Communications and Networking, vol. 2020, no. 1, pp. 1–15, 2020.
  * [32] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” nature, vol. 521, no. 7553, pp. 436–444, 2015.
  * [33] A. Narayanan, J. Bonneau, E. Felten, A. Miller, and S. Goldfeder, Bitcoin and cryptocurrency technologies: a comprehensive introduction. Princeton University Press, 2016.
  * [34] X. Xu et al., “Scaling for edge inference of deep neural networks,” Nature Electronics, vol. 1, no. 4, pp. 216–222, Apr. 2018, doi: 10.1038/s41928-018-0059-3.
  * [35] S. King, “Primecoin: Cryptocurrency with prime number proof-of-work,” July 7th, vol. 1, no. 6, 2013.
  * [36] A. Shoker, “Brief announcement: Sustainable blockchains through proof of exercise,” in Proceedings of the 2018 ACM symposium on principles of distributed computing, 2018, pp. 269–271.
  * [37] G.-T. Nguyen and K. Kim, “A survey about consensus algorithms used in blockchain,” Journal of Information processing systems, vol. 14, no. 1, pp. 101–128, 2018.
  * [38] W. W. Lee, W. Zankl, and H. Chang, “An ethical approach to data privacy protection,” 2016.
  * [39] L. Lamport, R. Shostak, and M. Pease, “The Byzantine generals problem,” in Concurrency: the works of leslie lamport, 2019, pp. 203–226.
  * [40] M. Abdalla, F. Bourse, A. De Caro, and D. Pointcheval, “Simple Functional Encryption Schemes for Inner Products,” in Public-Key Cryptography – PKC 2015, 2015, pp. 733–751.
  * [41] P. Datta, R. Dutta, and S. Mukhopadhyay, “Functional Encryption for Inner Product with Full Function Privacy,” in Public-Key Cryptography – PKC 2016, 2016, pp. 164–195.
  * [42] F. Hoffmann, Challenges of Proof-of-Useful-Work (PoUW). 2022.
  * [43] A. Back and others, “Hashcash-a denial of service counter-measure,” 2002.
  * [44] O. Schrijvers, J. Bonneau, D. Boneh, and T. Roughgarden, “Incentive compatibility of bitcoin mining pool reward functions,” in Financial Cryptography and Data Security: 20th International Conference, FC 2016, Christ Church, Barbados, February 22–26, 2016, Revised Selected Papers 20, 2017, pp. 477–498.
  * [45] S. Ahamad, M. Nair, and B. Varghese, “A survey on crypto currencies,” in 4th International Conference on Advances in Computer Science, AETACS, 2013, pp. 42–48.
  * [46] I. Bentov, C. Lee, A. Mizrahi, and M. Rosenfeld, “Proof of activity: Extending bitcoin’s proof of work via proof of stake [extended abstract] y,” ACM SIGMETRICS Performance Evaluation Review, vol. 42, no. 3, pp. 34–37, 2014.
  * [47] M. Z. Alom et al., “A state-of-the-art survey on deep learning theory and architectures,” electronics, vol. 8, no. 3, p. 292, 2019.
  * [48] S. Ruder, An overview of gradient descent optimization algorithms. 2017.