In this paper, we investigate the behavior of provers in decentralized proof generation for zk-SNARK Based Sidechains, specifically, Latus consensus protocol. We obtained results that give necessary and sufficient conditions for the existence of the Nash equilibrium, and the value of the relevant utility function, for various parameters of the sidechain and various price policies. These results allow picking a price policy to ensure the stable operation of the sidechain.
In an SC, the entity that creates the block, the block forger, shares a list of transactions, which he intends to include into the block, with other entities, called provers. The provers construct SNARKproofs for these transactions and also for each node of the corresponding Merkle tree. Each prover sets prices for his proofs, according to the price policy of the current epoch that was set at the end of the previous one. If there are a few proofs for a certain node, the block forger chooses the cheapest one.
The results of this paper continue a series on combinatorial, stochastic, and game-theoretic aspects of distributed proof generation for zk-SNARK-based blockchains started in [10].
In what follows, we will describe the operation of SCs, and, first of all, provers’ behavior, from the game-theoretical point of view. We will show that the optimal provers’ behavior, i.e. Nash equilibrium in the corresponding symmetric game, is fully determined by the price policy and by such parameters as the number of proofs and the number of provers.
We obtained necessary and sufficient conditions for the existence of the Nash equilibrium, for various models, price policies, and parameters, both in pure and mixed strategies. Such results allow modeling and sometimes prediction of the provers’ behavior, proof prices, and block forgers’ rewards, and help the inadequate setting of the price policy, to provide stable operation of SC.
The paper is organized as follows. In Chapter 2, we recall some basic definitions from game theory and general results on the existence of the Nash equilibrium. Then, in Chapter 3, we: Give the mathematical model of a one-step game, that we will use to describe distributed proof generation. Obtain some auxiliary results which we need to find Nash equilibrium for different price policies and other parameters. Obtain necessary and sufficient conditions for the Nash equilibrium existence. Describe these Nash equilibriums and corresponding utility functions.
In Chapter 4 we study the natural continuation and development of the one-step game, described in Definition 1, and formulate new Definition 5. This new game that is also a one-step game, deals with the creation of a sequence of blocks, rather than the creation of only one block. We investigate provers’ behavior, allowing them to choose proofs from different blocks.
Let us recall some basic definitions from game theory. More details can be found in one of the textbooks, in particular [11].
Definition 1. A strategic form game consists of the set of players = {1,2, … , }; and for each player the non-empty set of pure strategies ; the utility (payment) function : ∏ → .
A strategy profile is a combination of strategies of each player, i.e. an element of the Cartesian product ∏ .
Definition 2. A game is called symmetric if all strategy sets are the same and for each permutation of strategies
( )( 1, … , ) = ( (
In this case, is a symmetric function of all its arguments except for the th.
Note that replacement of the left action of the symmetric group by the right action leads to a stronger notion of fully symmetric game [12].
Definition 3. If the sets of strategies are equipped with a topology, one can consider the corresponding Borel σ-algebra.
A mixed (randomized) strategy is a Borel probability measure on the set of strategies .
The utility for mixed strategy on the th place is the expectation calculated via Lebesgue integral: each ∈ , (… , , … ) = ∫ (… , , … ) ( ).
Definition 4. A pure strategy Nash equilibrium is a strategy profile ( ) ∈ ∈ ∏ ∈ , where for ( 1 … , −1, , +1, … , ) ≥ ( 1 … , −1, ′ , +1, … , )for all ′ ∈ .
A mixed strategy Nash equilibrium is a mixed strategy profile ( ) ∈ , where for each ∈ ( 1 … , −1, , +1, … , ) ≥ ( 1 … , −1, ′ , +1, … , ) for all mixed strategies ′ on .
In this paper, we consider a symmetric game and are looking for a symmetric Nash equilibrium given by the same probability measure ∗ repeated times. In this case, we can formulate an equivalent Nash equilibrium criterion by making comparisons only with pure strategies:
Lemma 1. For any symmetric game, a symmetric Nash equilibrium is given by a probability measure ∗ iff the utility satisfies the condition −1 1∈ 1( 1, ∗, … , ∗) = ∫
1( 1, … , )∏ ∗( ). where supp ∗ is the support of the measure ∗.
In this case, the game price is
1∈
∗ = max 1( 1, ∗ … , ∗).
(
In what follows, under a one-step game, we will mean a symmetric strategic game corresponding to one step of provers’ work for a distributed proof generation.
Each th prover (≡ player), i ∈ {1,2, … , m}, randomly selects and builds one of proofs according to the function g: {1,2, … , m} → {1,2, … , n} and quote a price (≡strategy) ∈ ⊂ ℝ>0 for his work.
Let ⊆ {1,2, … , }, ≠ ∅. For the function ∋ ↦ , consider the set
′∈ argmin( ′) ≔ { ′′ ∈ ∣ ′′ = ′∈ ′}.
A block-forger, for every built -th proof, allocates a subset argmin( ′)of provers, who asked
the allocated subset and pays him the declared price.
the minimal price ′, among the set −1( ) of all provers who built it, randomly selects a prover from
For the subset (
′∈ 0, otherwise. has the binomial distribution (as a sum of independent Bernoulli random variables): . The number of other provers, which select the same proof as to the th prover, For a fixed th prover and for a fixed set −1( ( )) of other provers that select the same proof after averaging overall selections of the block-forger, the payment for this prover will be ⋅ argmin( ′)( ). Each subset ⊆ {1,2, … , } with ∈ appeared as −1( ( )) with probability ( = ) = ( ) ( ) ( ) = ( )
Lemma 2. The utility (
For example, in the case of two provers ( 1, … , ) = ∑ ∈ ⊆{1,2,…, } ( − 1) −| | ∙ ⋅ argmin( ′)( )⋅
′∈ −1( ( )) 1 −1 =0 1( 1, ∗ … , ∗) = −1 ∑ ( ∗( ≥ 1)+ − 1) ( ∗( ≥ 1)+ − 1) where ≥ 1 = { ∈ | ≥ 1} and > 1 = { ∈ | > 1}.
In particular, when ∗( 1) = 0 1( 1, ∗ … , ∗) =
1 −1 ( ∗( ≥ 1)+ − 1) −1 .
Proof. Substitution of (
1
use of the Fubini’s theorem and the binomial identity to get (
If ∗( 1) = 0, one can ignore in (
)( − 1) − −1 ∗( ≥ 1) 1 = −1 ( ∗( ≥ 1)+ − 1) −1 Then we need the identity
In the case + = 1, this is the expectation of 1/( + 1) with respect to the binomial distribution.
If ∗( 1)> 0, one can rewrite (
1 For ∈ ℤ>0 , consider the following homogeneous polynomials Lemma 3. =
( , ) ( , )− −1 ( , ). 1. The following polynomial identity is true ( , )= − − −1 =0 = ∑ − , ( , , )≔ ( , )
( , )− ( , ) ( , )= ( , , )= ∑ −1− − ( , )( − )( − ) = = 2( , , )= ∑ =−11 −1− − ( , ) ( , ) ( , ),
For positive , , , if 2( , , )= ( − )( − )> 0 then ( , , )> 0 for all ≥ 2.
−1
=0
−1
=1
(
( −1+ + −1− + + − −1 + − −1 + ) equilibriums.
The expression and the interval from the following lemma appears in the description of Nash The utility on the symmetric profile of pure strategies has the form ( , … , ) = The endpoints and length of the above interval admit the asymptotics
lim
, →∞
⁄ →
− −1
Proof. The identity (
Asymptotic formulas come from easy calculation with the Maclaurin series.
between endpoints of (
Here we obtain the main results are obtained on the Nash equilibrium for a game from Definition 5 in pure strategies for the general case (Proposition 1) and a particular case (Corollary 1) with only two strategies. We also provide numerical examples are given, built using these statements.
Proposition 1. Let be the set of pure strategies and ∗ ∈ . The profile ( = ∗)1≤ ≤ is a symmetric Nash equilibrium iff for all ∈ the following two conditions hold
Lemma 4. l, im→∞ ⁄ →
(
)1≤ ≤ is a symmetric Nash equilibrium iff )1≤ ≤ is a symmetric Nash equilibrium iff }.
)1≤ ≤ and ( = )1≤ ≤ are symmetric Nash equilibria iff ≤
. ≥ −1 ( −1) −1 . If
< ∗ then If > ∗ then ( −1) −1 ≤ ∗. (I.e.
⋂( ≤ ∗.
∗, ∗) = ∅. ) Proof. Note that 1( , ∗, … , ∗) =
{ ( − 1 −1
) , if 1 < ∗, , if 1 = ∗, , if 1 > ∗.
Then 1( ∗, ∗, … , ∗) ≥ 1( , ∗, … , ∗) yields the conditions 1 and 2 from the proposition.
Let
m = 50, n = 10 S = {1, 2, … ,10}. Then only one Nash equilibrium exists in pure symmetric strategies with s∗ = 1. symmetric strategies with s∗ = 10. exists in pure symmetric strategies with s∗ = 9.
Let m = 100, n = 10000S = {1, 2, … ,10}. Then only one Nash equilibrium exists in pure Let m = n = 200 S = {1, 2, 3, 4, 5, 9, 9.1, 9.2, 9.3, … ,10}. Then only one Nash equilibrium Corollary 1. Suppose that consists of two strategies { < The profile ( = The profile ( =
Both profiles( = lies in the interval [ −( −1) , strategies with s∗ = smax.
smax strategies with s∗ = smin.
1⁄( −1) 3.4
Mixed Strategies Absolutely Continuous in an Interval
Here we obtain the main results on the Nash equilibrium for the game from Definition 5 in mixed strategies that are considered as absolutely continuous measures on some intervals. Numerical examples are provided to illustrate the results obtained.
Proposition 2. Suppose that the set of strategies is an interval = [ , ].
A symmetric Nash equilibrium is given by the probability measure ∗ absolutely continuous with respect to the Lebesgue measure exists iff support of the measure are ≤ ( −1) −1 . In this case, the game price and the and the density of the measure ∗ is ∗ =
smin . Then if b = 0.1 and n ≥ m, the Nash equilibrium exists in pure symmetric If m = 10 and n = 2, or m = 50 and n = 10, or m = 200 and n = 50, or m = 500 and n = 100, two Nash equilibria exist in pure symmetric strategies with s∗ = smin and s∗ = smax.
For all other values of m, n from the set ranges, Nash equilibrium exists in pure symmetric (13) (14) (15) ,
)and the formula (
. and 1 = ′ in (15) yield ′ = ∗ =
( −1) −1 Substitutions of 1 =
∗( {≥ 1}) = ∫ ∗ ( ) = ( − 1) 1 1⁄ −1 −1⁄ −1 − + 1.
Taking derivative in ∈ supp ∗ = [ ′ Remark 1. Note that in the previous proposition ,
], we obtain the formula for the density. 1 ∗( ) ∗( ) = l, i→m∞ / → So, for large /
Let parameters , = ,li→m∞ (1 − / → 1 ) = − 1
= the measure ∗ is closed to uniform.
take the same values as in Numerical example 2, = [ , = 0.1. Then the existence of the Nash equilibrium in mixed strategy (20), (21) is described by the following Table 1, where “+” stands for the existence of the Nash equilibrium for given parameters, “-” stands for its absence. −1 =0 −1 =0 10 + + + + + + + + + number of proofs is bigger than the number of provers.
It also should be noted that, though the case of a continuous set of strategies seems unreal, we may use some approximations of these results in the case when prices may change in very small steps. 3.5
other parameters.
interval from (
Here we obtain conditions of the Nash equilibrium for the game from Definition 5 in mixed strategies that are considered as discrete measures on some intervals, for various sets of strategies and Proposition 3. Suppose that the set of strategies = {
Then the symmetric Nash equilibrium in mixed strategies ∗ exists iff the value lies on the In this case, − ∗(
)is the a root of the polynomial and the game price is ( − 1) −1 − ( − 1) − ( − 1) ,
, ∗, … , ∗) = 1( , ∗, … , ∗) =
−1 ∑ ( − 1) ( − ∗( −1 ∑ ( − ∗( )) − −1 .
The equality between two expressions from (19) takes the form ℎ( − 1 + ∗(
)) = 0 for the polynomial ℎ( ) from (17). ( − ( − 1) )−
( − 1) −1 > 0 iff ( − ( − 1) ) < 0 iff < .
> ( −1) −1 −1 ) the Bolzano’s theorem implies the existence of ∈ − , , 3 2−3 +1): 3 2 ∗( ) = (3 − 2) − (3 − 3) + √ = −3 2 2 + (6 2 − 6 + 4) 2( − ) − 3( − 1)2 2 .
Remark 2. In the case of a two-element set = {
belongs to the interval from (
Proposition 3 on mixed strategies. The first is the limit case of the second. − 1. So for small
Example 4 ( = { <
}). Note that the degree of the polynomial ℎ( ) from (17) equals to one can calculate the equilibrium measure ∗ and the game price ∗ explicitly.
In the case of two provers, = 2, for ∈ (
This expression comes from the largest root of the square polynomial (17) (the smallest root is always outside the interval ( − 1, )).
Substitution of ∗(
)into (18) yields the game price.
= 2 and the set of strategies is = { (0) >
(
Note that ℎ( − 1) = and ℎ( ) = So for ∈ ( −1 ( −1) −1 mixed strategy ∗. −1 ( −1) −1
. ( − 1, )which is a root of ℎ( ), and the corresponding probability = − + 1 = ∗( inequality implies ℎ( ) > 0 when
. The second inequality implies ℎ( ) < 0 when Let ∈ ( − 1, ). By Lemma 3 we have ( , − 1, ) > 0 and ( − 1, , ) > 0. The first ⁄ ) of
< (20) ∗ = , (21) (22) then the game price and probabilities are
, = 1 + (1 + (−1) )( − 1). ∗( (ℓ)) = 2 ∗( − −1)− (−1)ℓ(2 − 2) = − −1 − (−1)ℓ(2 − 2), 0 ≤ ≤ .
Denote : = ∑ ′=0 ( − ′) for = 0,1, … , ; and for convenience put −1 = 0. Then ( ) are
restored as 1⁄( + −1). In this case, a one-to-one correspondence is obtained between ( +
1)tuples (0) > (
0 < 0 < 2 < 4 < ⋯ , 0 < 1 < 3 < 5 < ⋯ .
If the symmetric Nash equilibrium is given by a probability measure ∗ with (−1) ′
2
Such Nash equilibrium exists iff ( )0≤ ≤ satisfy the inequalities (20) and (22)
> −1 + (−1) (2 − 2) , 0 ≤ ≤ ,
The set of all such ( )0≤ ≤ is a nonempty interior of convex ( + 1) is dimensional polytope.
Proof. The formula (
Then we prove simultaneously by induction in = 0,1, … , the formulas for probabilities (21) and The equation ∗ ( ≥ ( )) = 1 yields the formula for the game price ∗.
For ( )0≤l≤ satisfying (20), an above Nash equilibrium exists iff all values of probabilities in (21) are positive, that is equivalent to (22). 0 > 2 −2 and then select ∈ ( −1 − 2 −2 2 −1 , +1 − 2 −2 2 −1 )for all odd .
Suitable ( )0≤l≤ can be obtained algorithmically depending on the parity of : In the case when
is odd, one can select arbitrarily with odd satisfying 0 < 1 < 3 < ⋯ < and then select
∈ ((2 − 2) + −1, (2 − 2)
select arbitrarily
with even
+ +1)for all even . In the case when is even, one can
satisfying 0 < 0 < 2 < ⋯ < and additional condition
Proposition 5. Suppose that there are two provers
= 2. Then each symmetric Nash equilibrium
is given by a probability measure ∗ with
∗ =
on the countable set of strategies is
0 = −1 < 1 < 3 < ⋯ is strongly increasing and bounded and for each even ≥ 0
= { (0) > (
→∞ In this case the subsequence of elements with even indices is strongly increasing 0 < 2 < ⋯ and 2 +1; the game price is
→∞ strategies and probabilities are (ℓ) =
1 + −1
, ∗( (ℓ)) = 2 ∗( − −1)− (−1)ℓ(2 − 2), ℓ = 0,1, … Proof. This Proposition can be proved similarly to the previous one.
Example 5. According to the previous proposition, one can select = and = 2 − 2 + −1+ +1 = 2 − 2 + 2 (ℓ+1)(ℓ+3) ℓ2+3ℓ+1 for even ℓ = 0,2,4, ⋯ Then +2 +1 for odd = −1,1,3, … (ℓ) = ( (ℓ)}) = 1 1 2 − 2ℓ + 1 ℓ(ℓ + 2) { 2 −
2ℓ + 5 (ℓ + 1)(ℓ + 3) , if ℓ = 1,3,5, ⋯
, if ℓ = 0,2,4, … 1 1 ℓ(ℓ + 2) {(ℓ + 1)(ℓ + 3) , if ℓ = 1,3,5, ⋯ , if ℓ = 0,2,4, …
Note that though the results of this paragraph were obtained under some artificial restrictions on the set of strategies and number of provers, they also help to understand the equilibrium existence for some exotic and extreme cases.
Here we obtain conditions of the Nash equilibrium for the game from Definition 5 in mixed strategies, which are considered as measures with discrete and continuous parts, on suitable sets of strategies.
Proposition 6. Suppose that = { } ⋃[ ′, ] , < ′ <
Then there exists a symmetric Nash equilibrium given by the probability measure ∗ absolutely continuous with respect to the Lebesgue measure on [ ′,
] iff ∈ ( ( − 1) −1 ( − 1) −1
, − ( − 1) ).
In this case, the game price ∗, the discrete part ∗( given by the formulas ) and the density ∗( ) of the measure is ,
Substitution of the expression for game price into (
In this case, the game price ∗, the continuous part ∗([
measure are given by the formulas
, ′]) and the density ∗( ) of the
=0
iff
(23)
(24)
(25)
(26)
(27)
of (
Proof. Substitution of
that ℎ1(0) ≥ 0 If solution of equation (25).
Proposition 7. Suppose that Lebesgue measure on [
, ′] iff ( −1) −1 ( −1) −1 ∈ [ −1 , −( −1) ] we have a symmetric Nash equilibrium with ∗( and symmetric Nash equilibrium given by probability measure ∗ absolutely continuous with respect to ∗ = [ , ′] ∪ { < ′ <
. Then there exists
( − 1) −1 −( − 1)
∈ (
,
and ′ into the formula for the game price (
). =
.
, ′] −1 =0 Proof. Substitution of ∗ = and ′ yields
( − ∗([ = ′ −1 , ′, ])) −1 .
Substitution of the expression for game price in (
(28)
Note that h2(0) ≥ 0 iff
smin ≤ nm−(n−1)m−1
smax mnm−1
and
h2(
Here we are going to study another game describing the behavior of provers when choosing proofs for the next step from different blocks. This game may be considered as some further development and generalization of the game from Definition 5.
Definition 6. One-step game. We have provers (= players) and blocks under construction
with accessible proof-candidates in th block for 1 ≤ ≤ . The strategy of th prover is the block
number 1 ≤ ≤ he selects for the next step. In this case, the utility is defined as
( 1, … , ) = (
.
Remark 3. The utility given by (29) comes as the price of the game on the interval described by (13).
Proposition 8. The symmetric Nash equilibrium for the game from Definition 6 is given by the measure ∗( ) =
1 + 2 ⋯ + , = 1,2, … , .
(29)
(30)
Proof. The utility 1( 1, ∗, … , ∗)from (
− 1 ∑ ( ′ ) ∗( ) ′(1 − ∗( 1)) − ′−1 (1 − 1 ) ′ = (1 − ∗( 1)) −1 .
′=0
We described necessary and sufficient conditions of Nash equilibrium existence for two one-step games, which describe provers’ behavior in the process of distributed proof generation in sidechains. All results proposed are strictly formulated and proved using game-theoretical apparatus. Though we used rather complicated theoretical constructions, all results obtained are of significant practical value. They are expected to be used when building price policy in Latus Consensus in sidechains.
The direction for our further research, related to Latus Consensus and decentralized proof generation, is an investigation of sidechain functioning as a whole, taking into account both multilevel distributed proof generation in each block and provers’ simultaneous work with proofs from few different blocks.