Toward Equilibria and Solvability of Blockchain Pooling Strategies: A Topological Approach

Due to the severe competition for block mining, blockchain miners form coalitions, or pools, to amortize the cost. The point is to share the reward and transaction fee with fellow miners in the same pool in a more continuous manner rather than risking a long period of a solo mining before getting anything back, although the latter indicating a high reward with a probability. The motivation of pooling together in blockchains is well-justified and at goodwill; In a perfect world, every pool and miner is a good citizen and behaves as expected.

However, in the real world, there is nothing preventing one or more pools from sending a spy miner over to other pools. The rationale is also justifiable as follows: if the spy can hide its local mining results, then the target pool will be less competitive and has a lower chance of winning the race of mining blocks. There is a downside of this attack, however: the pool which sends out spies is also less competitive in the sense that its own computational power is cut down. It is then not hard to see that such a dilemma might significantly affect the pooling strategies, for example, whether to launch the infiltrating attack, if so, what is the percentage of computation power should be devoted to the attack, and so on.

It then becomes a natural question to ask whether such attacks among pools might reach a stable status: pools will not launch more attacks or withdraw existing attacks—no more spies moving around, which is called an equilibrium. One of the pioneering works for this matter appeared in (Eyal, 2015), which shows: (i) no-attack is not an equilibrium: all pools are rational and would not miss the opportunity to legally impair other pools; (ii) a blockchain of two pools does have a Nash equilibrium; and (iii) a blockchain of $q>2$ pools of an equal number of miners also has an equilibrium.

One key question in game theory is whether there exists an equilibrium among rational players who would not change her decision even if the decision is sub-optimal—usually implying that her utility is not maximal. The main reason for not switching to a higher-return decision is due to the possibility of a “very bad” outcome. Quantitatively, the players calculate the expectation—a weighted average over all the possible decisions in the simplest form—and make their decisions that might not be the absolutely highest-return one.

The well-known Nash equilibrium is one such decision, or the so-called solution concept, in the literature of game theory. Informally, the Nash equilibrium has a two-fold meaning. First, the existence of Nash equilibrium states that if an individual player has a finite number of strategies, then there must exist an equilibrium among a finite number of such players. Second, the Nash equilibrium of multi-player decisions, as any other solution concepts of equilibrium, once reached, would not change unless the assumptions are invalidated. One strong assumption of Nash equilibrium is the isolation of individual players: the players in the game will simply behave as an entity, and no collaboration is allowed. This assumption covers many interesting problems, but obviously, not all. The problems targeted by Nash equilibrium and its variant are called non-cooperative games.

When players are allowed to collaborate, i.e., to form coalitions to work together for higher utility returns, the game then becomes a cooperative game, or better known as a coalitional game in the literature of game theory. Although coalitional games share very similar objectives and challenges as non-cooperative games, the solution concepts look quite different. For instance, the equilibrium counterpart in coalitional games is called a core, which does not always exist. Some approximations to the core do exist, such as the bargaining set, but in general, a coalitional game’s equilibrium point, from existence to calculation, remains a very challenging problem.

We review the basics in point-set topology in this section. In the literature, it is also called general topology. Point-set topology focuses on the abstraction of relationships among elements in a set, without constraints about the corresponding geometric objects. Because the relationships are all defined, in an axiomatic manner, over the abstraction of elements and sets, the properties and theorems are applied to other branches of topology. A detailed introduction to point-set topology can be found in textbooks such as (Munkres, 2000). The definitions we list below are by no means exhaustive; we only sketch the ones that will be used in later chapters. We assume the readers are familiar with basic set-theoretical terms.

• •

  Topological Space. Let $S$ be a set. A set $\mathcal{T}$ of subsets of $S$ is called a topology of $S$ as long as $\emptyset\in\mathcal{T}$ and $S\in\mathcal{T}$. The tuple $(\mathcal{T},S)$ is called the topological space of $S$. If $\mathcal{T}=\{\emptyset,S\}$, then $\mathcal{T}$ is called a trivial topology of $S$. If the context is clear, we also call the topology induced by $S$ topology $S$.

• •

  Discrete Topological Space. Let $\mathcal{T}$ be a topology of set $S$. If for any subset $S^{\prime}\subseteq S$ we have $S^{\prime}\in\mathcal{T}$, then $\mathcal{T}$ is called a discrete topology of $S$. Essentially, all the elements in $S$ are singleton elements in $\mathcal{T}$; also, any combination of those singleton elements are also in $\mathcal{T}$.

• •

  Open Set. Let $\mathcal{T}$ be a topology of $S$. Any element $O\in\mathcal{T}$ is called an open set. The complement set $S\setminus O$ is called a closed set.

• •

  Continuous Functions. Let $f$ be a function from topology $\mathcal{A}$ to topology $\mathcal{B}$, $f:\mathcal{A}\rightarrow\mathcal{B}$. We call $f$ a continuous function if for every open set $O^{\prime}\in\mathcal{B}$, there exists an open set $O\in\mathcal{A}$ such that $f(O)=O^{\prime}$.

• •

  Injective, Surjective, and Bijective Functions. Let $f$ be a function from domain set $A$ to image set $B$, $f:A\rightarrow B$. If for any $a\in A$, $a^{\prime}\in A$, and $a\neq a^{\prime}$, we have $f(a)\neq f(a^{\prime})$, then $f$ is injective. If for every $b\in B$, there is an element $a\in A$ such that $f(a)=b$, then $f$ is surjective. If $f$ is both injective and surjective, then $f$ is bijective.

• •

  Homeomorphism. Let $f$ be a function from topology $\mathcal{A}$ to topology $\mathcal{B}$, $f:\mathcal{A}\rightarrow\mathcal{B}$. If $f$ is both bijective and continuous, then $f$ is called a homeomorphism of $\mathcal{A}$ and $\mathcal{B}$, and $\mathcal{A}$ is called homeomophic to $\mathcal{B}$.

In contrast to point-set topology, algebraic topology is more concerned with the underlying geometric realizations and algebraic structures. One approach to study the geometric objects is to decompose them into smaller pieces, the so-called triangulation, which does not necessarily break the object down into triangles but cells. If we restrict the shape of a cell to a polyhedron, i.e., only points and lines, then the geometric object can be depicted as a discrete approximation. Each of these polyhedron cells is then called a simplex, and the whole object is called a simplicial complex. It turns out that these concepts can also be defined in a set-theoretic context, as we will see shortly. A delicate and beautiful theory, namely algebraic topology, has been built upon these simple yet powerful definitions, and this is where we start our review. As point-set topology, we only list the concepts and notations of algebraic topology that will be used in later chapters of this paper; a more complete and rigorous review of algebraic topology can be found in textbooks such as (Munkres, 1984).

• •

  Simplicial Complex, Simplex. Let $S$ be a set. Each element $v\in S$ is called a vertex. A simplicial complex $\mathcal{C}$ is a set of subsets of $S$ if (i) all the vertices are singleton elements in $\mathcal{C}$ and (ii) for every $X\in\mathcal{C}$, all subsets of $X$ are also in $\mathcal{C}$. Each element $\sigma\in\mathcal{C}$ is called a simplex. In the remaining of the paper, we call a simplicial complex a complex if no ambiguity may arise.

• •

  Face, Proper Face, Facet. A face $\tau$ of simplex $\sigma$ if $\tau\subseteq\sigma$. A proper face $\tau$ of simplex $\sigma$ if $\tau\subset\sigma$. A simplex $\sigma$ is a facet of a complex $\mathcal{C}$ if $\sigma$ is not a proper face of any other simplices in $\mathcal{C}$.

• •

  Vertex Map. Give two complexes $\mathcal{A}$ and $\mathcal{B}$, a vertex map is a function $\varphi:V(\mathcal{A})\rightarrow V(\mathcal{B})$, where $V(\cdot)$ returns the set of vertices. Note that we do not impose any additional properties of the function $\varphi$; For example, it is allowed to map two distinct vertices from $\mathcal{A}$ to the same vertex in $\mathcal{B}$.

• •

  Simplicial Map. A vertex map $\varphi$ from $V(\mathcal{A})$ to $V(\mathcal{B})$ is called a simplicial map it carries any simplex from $\mathcal{A}$ to a simplex in $\mathcal{B}$. That is, if $\{a_{0},\ldots,a_{n}\}$ is a simplex in $\mathcal{A}$, then $\{\varphi(a_{0}),\ldots,\varphi(a_{n})\}$ is a simplex in $\mathcal{B}$.

• •

  Carrier Map. A carrier map $\Phi$ maps each simplex in complex $\mathcal{A}$ to a subset of complex $\mathcal{B}$, usually called a subcomplex all of which constitute a powerset denoted $2^{\mathcal{B}}$. To this end, the carrier map is often written as $\Phi:\mathcal{A}\rightarrow 2^{\mathcal{B}}$.

• •

  Dimension of Simplices and Complexes $(\mathtt{dim})$. The dimension of a simplex $\sigma$ is defined as the number of its vertices minus 1: $\mathtt{dim}(\sigma)=|\sigma|-1$. The reason why this is so defined is due to the geometric intuition: a two-vertex simplex can be geometrically viewed as a 1-dimensional line segment, a three-vertex simplex can be geometrically viewed as a 2-dimensional triangle, and so on. The dimension of a complex $\mathcal{C}$ is defined as the dimension of the highest-dimensional simplices in the complex. That is, $\mathtt{dim}(\mathcal{C})=\text{sup}\{\mathtt{dim}(\sigma):\sigma\in\mathcal{C}\}$.

• •

  Skeleton of Complexes $(\mathtt{skel}^{k})$. A $k$-skeleton of complex $\mathcal{C}$ is a set of simplices in $\mathcal{C}$ whose dimension is up to $k$. That is, $\mathtt{skel}^{k}\mathcal{C}=\{\sigma\in\mathcal{C}:\mathtt{dim}(\sigma)\leq k\}$. Following this definition, the vertices of a complex is just its 0-skeleton: $V(\mathcal{C})=\mathtt{skel}^{0}\mathcal{C}$.

• •

  Connectivity. This is one of the most important topological properties in the sense that two topological spaces cannot be equivalent (i.e., homeomorphic) if they exhibit different levels of connectivity. The most widely-used property, also the one used in later chapters of this paper, is called path-connected, which has a similar definition as graph theory. A complex $\mathcal{C}$ is called path-connected if any two vertices can be connected through a sequence of 1-dimensional simplices. If the context is clear, we simply call a complex connected if it is path-connected. Strictly speaking, path-connectivity is at the degree 0 of the connectivity spectrum, namely 0-connectivity. There is higher-degree connectivity: a $k$-connectivity indicates that a $(k+1)$-dimensional ball can be continuously mapped to the complex—there is no $(k+1)$-dimensional “holes” in the complex.

• •

  Subdivision $(\mathtt{div})$. Subdivision refers to finer decomposition of a given simplex, denoted $\mathtt{div}(\cdot)$, such that a new set of simplices are generated, and all of them constitute a new complex. Two of the most popular subdivisions are Barycentric subdivision and Chromatic subdivision. Barycentric subdivision ($\mathtt{Bary}(\cdot)$) simply takes the Barycentric center of a specific lower-dimensional skeleton, joins the center to existing vertices, and repeats this procedure on all levels of skeletons. Chromatic subdivision ($\mathtt{Ch}(\cdot)$) extends the Barycentric subdivision by introducing joint-centers such that the new vertices cannot directly share a lower-dimensional simplex with existing vertices, which turns to be very useful in tasks related to graph coloring.

• •

  Joining Complexes (*). In addition to dividing existing simplices, we are also able to “glue” together existing complexes through joining. Given two complexes $\mathcal{A}$ and $\mathcal{B}$, the joining of two is a new complex with all the simplices from $\mathcal{A}$ and $\mathcal{B}$. Formally, we say $\mathcal{A}*\mathcal{B}=\{\sigma\cup\tau:\sigma\in\mathcal{A},\tau\in\mathcal{B}\}$. This definition can be extended to simplices as well; for example, the join of a vertex and a complex is a new complex with the original vertex, the original complex, and all the edges (i.e., 1-dimensional simplices) between the original vertex and every vertex of the original complex.

Assume there are $q$ pools, where $q\in\mathbb{Z}^{+}$, $q\geq 2$. We call the size Two pools are said to be equal if they have the same number of nodes, namely, size. Let the size of each pool be $(n+1)$, $n\in\mathbb{Z}^{+}$, $n\geq 1$. Each of $q$ pools is a thus a $n$-simplex, and the input complex $\mathcal{I}$ has $q$ disconnected $n$-simplices, i.e., components: there is no 1- or higher-dimensional simplex among any pair of these components. These $n$-simplices are disconnected from each other because they know nothing about others.

The output complex is defined as follows. Each vertex $v$ in $\mathcal{O}$ is a tuple $(p_{i}^{j},k)$, where $p_{i}^{j}$ is the same as Def. 3.1 and $k$ denotes the $k$-th pool, $1\leq k\leq q$. Note that, by such definition, even if $p_{i}^{j}$ does not change its originally assigned pool, the vertex will still change the value from $\bot$ to $k$.

Because our goal is to find an equilibrium, each node $p_{i}^{j}$ cannot be intersected by two or more simplices in $\mathcal{O}$. That is, if $(p_{i}^{j},k)\in\sigma\in\mathcal{O}$ and $(p_{i}^{j},k)\in\tau\in\mathcal{O}$, then $\sigma=\tau$. It follows that the output complex $\mathcal{O}$ is a disconnected complex of $N$-simplices where $N=q\cdot(n+1)-1$. For any $N$-simplex in $\sigma\in\mathcal{O}$, we have

where $[n]$ denotes the set $\{0,\ldots,n\}$. Similarly, we have

Now we are ready to define the carrier map $\Delta$ from complex $\mathcal{I}$ to $\mathcal{O}$, that is, $\Delta:\mathcal{I}\rightarrow 2^{\mathcal{O}}$. Essentially, $\Delta$ “deforms” a simplex $\sigma\in\mathcal{I}$ into one possible simplex in a subset of $\mathcal{O}$, i.e., a subcomplex $\mathcal{S}\subseteq\mathcal{O}$ in a monotonic way. By monotinic, we require that adding more vertices or higher-dimensional simplices into $\sigma$ would only enlarge the subcomplex $\mathcal{S}$. If we can successfully construct a carrier map $\Delta$, or prove that such carrier map exists, then we are guaranteed the existence of an equilibrium.

The problem of assigning pools to miners is thus represented as a triple $(\mathcal{I},\mathcal{O},\Delta)$. In the remainder of this section, we will discuss how to find or construct $\Delta$, if it exists.

In the literature of algebraic topology, we usually face two types of problems: (i) To demonstrate that two topological spaces are “equivalent” up to continuous deformation—retaining the topological properties or the so-called topological invariant, and (ii) To prove that two topological spaces cannot be equivalent. For the first type of problem, we can either construct an explicit continuous function to map from the first space to the other or show that both spaces are homeomorphic in the sense that their underlying algebraic structures (e.g., groups, fields) are homomorphic. For the second type of problem, we are left with the only option of showing that the underlying algebraic structures are not homomorphic.

Our strategy to find the equilibrium for equal pools is as follows.

1. (1)

   We will construct a continuous function, i.e., a simplicial map $\varphi$ from a specific $n$-simplex $\sigma\in\mathcal{I}$ to a $N$-simplex $\tau\in\mathcal{O}$. That is, $\varphi:\mathcal{I}\rightarrow\mathcal{O}$.

2. (2)

   We will show that all the $n$-simplices in $\mathcal{I}$ are homeomorphic, such that the simplicial map is applicable to all the simplices in $\mathcal{I}$.

3. (3)

   Finally, we will prove that for any $\sigma\in\mathcal{I}$, the corresponding simplices in $\mathcal{O}$ constitute a connected subcomplex:

   $$\displaystyle\bigcup_{\sigma\in\mathcal{I}}\varphi(\sigma)\subseteq\mathcal{O}.$$

First, we will rephrase the well-known results of game-theoretic blockchains in the context of algebraic topology. Eyal (Eyal, 2015) showed that a no-attack strategy is not a Nash equilibrium in blockchain pools. That is to say, in the output complex $\mathcal{O}$, a connected component, which is itself a simplex, cannot have all of its nodes staying in their originally assigned pool. We thus have our first constraint on the simplices in $\mathcal{O}$, as stated in the following lemma.

Recall that a simplicial map is an extended vertex map: not only does the map apply to $0$-simplices (i.e., vertices), but also to any $k$-simplices, $0\leq k\leq n$. That is, we need to show that there exists a map from $\mathcal{I}$ to $\mathcal{O}$ such that any simplex of dimension $d$ has a corresponding $d$-dimensional simplex in $\mathcal{O}$. Formally, we will have the following result.

Intuitively speaking, Protocol 3.4 states that it is possible to merge multiple initial pool-local views into a coherent view in the final pool assignment. Next, we will show that this property is invariant as long as the pools are kept equal in the input.

In this section, we will show that all the $n$-simplices in $\mathcal{I}$ are homeomorphic, meaning that all these components are essentially equivalent in the sense that one component can deform into another with continuous functions. This property will be crucial when we prove that more than one equilibrium must exist in an equal-pool blockchain network later in §3.6. The remainder of this section will demonstrate that if $\mathcal{I}$ is an equal-pool blockchain network, then any two pools are homeomorphic. Formally, we will prove the following lemma.

In the previous two subsections, we have shown that (i) there exists a simplicial map from the input complex to the output complex and (ii) all the simplices in the input complex are homeomorphic. The last piece for our main theorem, which will be presented in §3.6, is demonstrating that the mapped simplices in the output complex indeed constitute a connected subcomplex. Formally, we need to prove the following lemma.

We are now ready to state the main result for equal-pool blockchains. Specifically, we will show that there is a protocol to continuously transform the input complex into the output complex.

Theorem 3.7 and its proof shows that for any blockchain with equal pools, there are at least $q$ equilibria because $\pi$ can be defined on up to $q$ distinct simplices in $\mathcal{I}$. This is a stronger result than (Eyal, 2015) in the sense that the lower bound of the number of equilibria is elevated from one to $q$. Nonetheless, it is arguable that equal pools might not be a practical assumption in real-world blockchain practices. To that end, we will switch our focus on the pooling strategies where the sizes are arbitrary.

Assume there are $q$ pools, where $q\in\mathbb{Z}^{+}$, $q\geq 2$. Let $\{\sigma_{1},\ldots,\sigma_{q}\}$ denote such $q$ pools. At least two pools have distinct numbers of miners. Without loss of generality, let $|\sigma_{1}|\neq|\sigma_{2}|$. In general, we pose no requirement on the equality of cardinality of other pools. To start with an easier problem, we assume

That is, we have one $n$-simplex and $(q-1)$ lower-dimensional $m$-simplices in the blockchain pools. Moreover, all of these $q$ simplices are disconnected pair-wise.

Note that although this condition makes the problem easier than the original one, the condition is strong enough to invalidate Lemma 3.5. Also, if we can show that this “easier” problem does not have an equilibrium, neither does the original problem.

As the equal-pool problem, each vertex $v$ in $\mathcal{I}$ is a tuple $(p_{i}^{j},\bot)$, where $p_{i}^{j}$ denotes the $i$-th pool’s $j$-th node (miner) and $\bot$ denotes logical false—the miner does not join another pool other than $i$. Evidently, we have $1\leq i\leq q$ and $0\leq j\leq n$.

The output complex is defined similarly. Each vertex $v$ in $\mathcal{O}$ is a tuple $(p_{i}^{j},k)$, where $p_{i}^{j}$ is the same as input complex and $k$ denotes the $k$-th pool, $1\leq k\leq q$. Note that, by such definition, even if $p_{i}^{j}$ does not change its originally assigned pool, the vertex will still change the value from $\bot$ to $k$.

Because we are concerned with an equilibrium, each node $p_{i}^{j}$ cannot be intersected by two or more simplices in $\mathcal{O}$. That is, if $(p_{i}^{j},k)\in\sigma\in\mathcal{O}$ and $(p_{i}^{j},k)\in\tau\in\mathcal{O}$, then $\sigma=\tau$. It follows that the output complex $\mathcal{O}$ is a disconnected complex of $N$-simplices where $N=n+(q-1)\cdot(m+1)$. For any $N$-simplex in $\sigma\in\mathcal{O}$, we have

However, the $\mathtt{index}(\cdot)$ would look different for $\sigma_{1}$ and other simplices:

We can define the carrier map $\Delta$ from complex $\mathcal{I}$ to $\mathcal{O}$, similarly to the equal-pool counterpart. The monotonic property of $\Delta$ still holds in this arbitrary-pool problem. We will show that such $\Delta$ cannot exist due to some topological invariant in the remainder of this section.

Our approach to demonstrate that an equilibrium does not exist is built upon the findings in the equal-pool counterpart presented in §3. Specifically, we will split the $q$ simplices in the input complex $\mathcal{I}$ into two subcomplexes: (i) The first subcomplex $\mathcal{I}_{1}$ consists of only one simplex $\sigma_{1}$; (ii) The second subcomplex $\mathcal{I}_{2}$ consists of $(q-1)$ $m$-simplices: $\{\sigma_{2},\ldots,\sigma_{q}\}$. Then, according to Theorem 3.7, $\mathcal{I}_{2}$ can lead to at least $(q-1)$ equilibria, and we can rewrite the simplicial maps with a power of limited maps. It remains to show that the extended problem with $\mathcal{I}=\mathcal{I}_{1}\cup\mathcal{I}_{2}$ has no way to be mapped to a connected simplex in $\mathcal{O}$.

The main technique we use to demonstrate the impossibility is reduction. That is, we reduce a well-known problem, the $k$-set agreement problem, whose solution does not exist for certain conditions that are satisfied by the equilibrium of an arbitrary-pool blockchain. Specifically, we will show that we can “simulate” the execution of the $k$-set agreement procedure by calling the operations in an arbitrary-pool blockchain. Indeed, if we are able to do so, that means we would be able to solve the $k$-set agreement problem, which is not possible. As a result, a protocol for reaching equilibrium in an arbitrary-pool network cannot exist.

We start our analysis with a simpler problem where only one simplex $\sigma_{1}$ has a different dimension than other $q-1$ simplices in the input complex. Without loss of generality, we assume $\mathcal{I}=\mathcal{I}_{1}\cup\mathcal{I}_{2}$, and $\mathcal{I}_{1}=\{\sigma_{1}\}$ and $\mathcal{I}_{2}=\{\sigma_{k}:2\leq k\leq q\}$. Moreover, we assume $\mathtt{dim}(\mathcal{I}_{1})=\mathtt{dim}(\sigma_{1})=n$, $\mathtt{dim}(\mathcal{I}_{2})=\mathtt{dim}(\sigma_{k})=m$, and $n>m>0$.

We then construct limited simplicial maps $\pi_{1}$ and $\pi_{2}$ for $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$, respectively. As before, we have the following equations:

As a result, the mapped simplices can be similarly partitioned into two parts $\mathcal{O}=\mathcal{O}_{1}\cup\mathcal{O}_{2}$, where

We can write $\mathcal{O}_{2}$ as a power of $\pi_{2}$ because all the $\sigma_{k}$, $2\leq k\leq q$ are homeomorphic, as discussed before (cf. Lemma 3.5). It turns out that we can expect two distinct sets of outcomes in the output complex. The problem can now be represented as a triple $(\mathcal{I}_{1}\cup\mathcal{I}_{2},\mathcal{O}_{1}\cup\mathcal{O}_{2},\pi_{1}\circ\pi_{2}^{q-1})$. We define an auxiliary operation to return the partition of a specific simplex:

such that $\mathtt{dim}(I_{i})=\mathtt{dim}(\sigma)$.

We can naturally extend the partition techniques from two to three or more. As we will show later in §4.5, for $k\geq 3$, all the $k$-set agreement problems are not decidable to have a protocol. In the following, we assume $3\leq k\leq q$: there are at least three distinct pools in terms of their sizes. Note that we also require that the size of the largest pool is at least $k$, i.e., $n+1\geq k$, because otherwise there cannot exist $k$ distinct sizes

As in the case of binary partition, we can similarly define $\mathcal{I}=\mathcal{I}_{1}\cup\mathcal{I}_{2}\ldots\cup\mathcal{I}_{k}$. We denote the cardinality, i.e., pool size, of partitioned input complex as:

where $1\leq x<y\leq k\implies i_{x}\neq i_{y}$, and require

We use $K$ to denote the set of pool sizes:

It should be noted that $k$ partitions of the input complex do not change $\mathcal{I}$’s topological properties. There are still $q$ components in $\mathcal{I}$, each of which is a $i_{\kappa}$-dimensional simplex where $i_{\kappa}\in K$. Furthermore, these $q$ simplices are disconnected since the miners are in distinct pools and learn nothing from other pools initially.

Having partitioned input complex based on their cardinalities, we are ready to construct the output complex the corresponding carrier maps. The partitioned simplicial maps for $k$-distinct-pool are a natural extension to the binary partition we discuss in §4.3. Recall that all simplices are homeogeneous for a specific dimension $i_{\kappa}\in K$. Therefore, the compounded simplicial map can be written as

The task then can be expressed in the following triple:

where we use multiplication to denote map composition:

In this section, we summarize the main results for blockchains with arbitrary pools and discuss the relations with game-theoretical approaches.

If a blockchain has pools of only two distinct sizes, Theorem 4.10 states that an equilibrium indeed exists. It should be clear, however, that this claim says nothing about how the protocol’s complexity looks like; the algorithm could be polynomial, exponential, or NP-complete, which is not the scope of this paper. In practice, a two-distinct-pool blockchain network is, admittedly, rare. To this end, it is more interesting to draw some conclusions on the case where more than two pools are formed in the blockchain. Unfortunately, Theorem 4.12 tells us that no equilibrium exists for these more interesting cases. Of course, the impossibility result for $k\geq 3$ distinct pools, although somewhat discouraging, is only based on the mainstream computing models nowadays. The authors, in their very humble opinions, still hold high hopes that future hardware and communication advances plus possibly more advanced mathematical tools would lead to equilibrium results.

Speaking of equilibria over groups of participants, we just cannot skip the discussion on game theory. From a game-theoretical point of view, the pooling strategies are aligned with the so-called coalitional games. Unlike non-cooperative games, where one is interested in the utility equilibrium for individual participants, a coalitional game deals with the utility of a coalition of participants—just like the pools of miners in blockchains. More importantly, the well-known Nash equilibrium that states an equilibrium always exists is only applicable to non-cooperative games; the counterpart equilibrium in coalitional games, namely core, is proven not to always exist. In this sense, a large portion of this section just tries to achieve a stronger result than that in game theory: when $k\geq 3$, such a core does not exist for $k$-distinct-pool blockchains. In coalitional game theory, there are a few more relaxed equilibria than the core per se. For instance, a bargaining set might be a practical replacement that implies that a participant not in the core might still choose to stay in its current coalition because its claims (for higher utility, for example) can be countered. An extensive review of a coalitional game’s solution concepts can be found in (Peleg and Sudholter, 2007). For a general introduction to game theory, see (Maschler et al., 2013).