Game-Theoretic View on Decentralized Proof Generation in zk-SNARK-based Sidechains Yuri Bespalova, Alberto Garoffolob, Lyudmila Kovalchukc,d, Hanna Nelasae, and Roman Oliynykovc,f a Bogolyubov Institute for Theoretical Physics, 14b, Metrolohichna str., Kyiv, 03143, Ukraine b Zen Blockchain Foundation,701 Gervais str, Columbia, South Carolina, 29201, USA c Input Output HK, Tesbury Centre, Queen’s Road East, 24-32, Hong Kong d Igor Sikorsky Kyiv Polytechnic Institute, 37 Peremohy ave., Kyiv, 03056, Ukraine e Zaporizhzhia Polytechnic National University, 64 Zhukovskogo str., Zaporizhzhia, 69063, Ukraine f V. N. Karazin Kharkiv National University, 4 Svobody sq., Kharkiv, 61022, Ukraine Abstract 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. Keywords 1 Blockchain, sidechain, game theory, Nash equilibrium, Latus, Ouroboros Praos, Merkle tree 1. Introduction This paper deals with a relatively new direction in cryptology - blockchains and cryptocurrencies. It investigates sidechains as a new instrument in blockchain technology. Sidechains (SCs) [1-4] are very adequate and universal instruments in blockchain technology. They may be used as an extension of a blockchain in the case when we need some additional functionality that is not available in the initial blockchain (that is called the main chain). SCs may use both Proof-of-Work and Proof-of-Stake protocols. In this paper, we are dealing with Latus Protocol [5] which is a hybrid PoS based on Ouroboros Praos [6] with an additional feature of binding to a PoW mainchain (MC). SCs should bind to MC, as described in [1-5], to provide such necessary blockchain properties as liveness and persistence [7]. SC also should send some information to MC to guarantee the fairness of transformations in SC. This information contains a series of recurrent zk-SNARK-proofs [8, 9] to establish decentralized and verifiable cross-chain transfers. Latus introduces a special dispatching scheme that assigns generation of proofs randomly to interested parties who then perform these tasks in parallel and submit generated proofs to the blockchain. An incentive scheme provides a reward for each valid submission. The general idea of Latus is to utilize a recursive composition of SNARKs to construct a succinct proof of the sidechain state progression for the period of a withdrawal epoch. Then, a SNARK for a withdrawal certificate is constructed so that it proves the correct sidechain state transition for the whole epoch and validates backward transfers. That allows the mainchain to verify the sidechain efficiently without having to rely on any intermediary—such as certifiers [4]—and still be oblivious to the sidechain construction and interactions within. Cybersecurity Providing in Information and Telecommunication Systems, January 28, 2021, Kyiv, Ukraine EMAIL: yu.n.bespalov@gmail.com (A.1); alberto@horizen.global (B.2); lusi.kovalchuk@gmail.com (C.3); annanelasa@gmail.com (D.4); roliynykov@gmail.com (C.5) ORCID: 0000-0003-0503-953X (A.1); 0000-0003-2874-7950 (B.2); 0000-0002-3708-0089 (C.3); 0000-0002-3494-0493 (D.4); 0000-0002- 3494-0493 (C.5) ©️ 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) 47 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 SNARK- proofs 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. 2. Preliminaries 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 , … , 𝑠𝑚 ) = 𝑢𝑖 (𝑠𝜋(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 𝑆𝑖 . 48 The utility for mixed strategy 𝜇𝑖 on the 𝑗th place is the expectation calculated via Lebesgue integral: 𝑢𝑖 (… , 𝜇𝑗 , … ) = ∫ 𝑢𝑖 (… , 𝑠𝑗 , … ) 𝑑𝜇(𝑠𝑗 ). 𝑆𝑗 Definition 4. A pure strategy Nash equilibrium is a strategy profile (𝑠𝑖 )𝑖∈ 𝑃 ∈ ∏𝑖∈ 𝑃 𝑆𝑖 , where for each 𝑖 ∈ 𝑃, 𝑢𝑖 (𝑠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 𝑚 ∗ ∗) 𝑢1 (𝑠1 , 𝜇 , … , 𝜇 =∫ 𝑢1 (𝑠1 , … , 𝑠𝑚 ) ∏ 𝑑𝜇∗ (𝑠𝑗 ) . (1) 𝑆 𝑚−1 𝑗=2 satisfies the condition 𝑠𝑢𝑝𝑝 𝜇∗ ⊆ 𝑎𝑟𝑔𝑚𝑎𝑥 𝑢1 (𝑠1 , 𝜇∗ … , 𝜇∗ ). 𝑠1 ∈𝑆 (2) where supp 𝜇∗ is the support of the measure 𝜇∗ . In this case, the game price is 𝑢∗ = max 𝑢1 (𝑠1 , 𝜇∗ … , 𝜇∗ ). 𝑠1 ∈𝑆 3. The Case of One-Step Game of Distributed Proof Generations 3.1 Description of the Game 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. Definition 5. (One-step game). 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(𝑠𝑖′ ) ≔ {𝑖 ′′ ∈ 𝐼 ∣ 𝑠𝑖′′ = 𝑚𝑖𝑛 ′ 𝑠𝑖′ }. (3) 𝑖 ′ ∈𝐼 𝑖 ∈𝐼 A block-forger, for every built 𝑗-th proof, allocates a subset argmin (𝑠𝑖′ ) of provers, who asked 𝑖 ′ ∈𝑔−1 (𝑗) −1 the minimal price 𝑠𝑖′ , among the set 𝑔 (𝑗) of all provers who built it, randomly selects a prover from the allocated subset and pays him the declared price. For the subset (3) in {1,2, … , m}, consider the corresponding δ-function 1 , if 𝑖 ∈ argmin(𝑠𝑖′ ) ; 𝛿argmin(𝑠 ′ ) : {1,2, … , 𝑚} → ℝ, 𝑖 → {# argmin(𝑠𝑖′ ) 𝑖 ′ ∈𝐼 𝑖 𝑖 ′ ∈𝐼 𝑖′ ∈𝐼 0, otherwise. 49 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 𝑖 𝑖′ ∈𝑔−1 (𝑔(𝑖)) 1 |𝐼|−1 𝑛−1 𝑚−|𝐼| (𝑛) ( 𝑛 ) . The number 𝜅𝑖 of other provers, which select the same proof as to the 𝑖 th prover, has the binomial distribution (as a sum of independent Bernoulli random variables): 𝑚 − 1 1 𝑘 𝑛 − 1 𝑚−𝑘−1 𝑚 − 1 (𝑛 − 1)𝑚−𝑘−1 𝐏𝐫(𝜅𝑖 = 𝑘) = ( )( ) ( ) =( ) . 𝑘 𝑛 𝑛 𝑘 𝑛𝑚−1 Then the utility of the 𝑖-th prover is (𝑛 − 1)𝑚−|𝐼| 𝑢𝑖 (𝑠1 , … , 𝑠𝑚 ) = ∑ ∙ 𝑠𝑖 ⋅ 𝛿argmin(𝑠 ′ ) (𝑖) ⋅ 𝑛𝑚−1 𝑖 (4) 𝐼⊆{1,2,…,𝑚} 𝑖′ ∈𝑔−1 (𝑔(𝑖)) 𝑖∈𝐼 For example, in the case of two provers 𝑠1 , if 𝑠1 < 𝑠2 , 𝑛−1 1 𝑢1 (𝑠1 , 𝑠2 ) = 𝑠1 + {𝑠1⁄2 , if 𝑠1 = 𝑠2 , (5) 𝑛 𝑛 0, if 𝑠1 > 𝑠2 . The general formula (4) or its particular cases will be used in all following statements 3.2 The Utility in Mixed Strategies. Auxiliary Results Below we formulate and prove some auxiliary results that were helpful in obtaining the main results. The following Lemma adopts the general case of the utility function for the Nash equilibrium for the one-step game from Definition 5. Lemma 2. The utility (1) for a one-step game admits the expression 𝑚−1 ∗ ∗) 𝑠1 𝑘 𝑚−𝑘−1 𝑢1 (𝑠1 , 𝜇 … , 𝜇 = ∑ (𝜇∗ (𝑆≥𝑠1 ) + 𝑛 − 1) (𝜇∗ (𝑆≥𝑠1 ) + 𝑛 − 1) , 𝑚𝑛 𝑚−1 (6) 𝑘=0 where 𝑆≥𝑠1 = {𝑠 ∈ 𝑆 | 𝑠 ≥ 𝑠1 } and 𝑆>𝑠1 = {𝑠 ∈ 𝑆 | 𝑠 > 𝑠1 }. In particular, when 𝜇∗ (𝑠1 ) = 0 𝑠1 𝑚−1 𝑢1 (𝑠1 , 𝜇∗ … , 𝜇∗ ) = (𝜇∗ (𝑆≥𝑠1 ) + 𝑛 − 1) . (7) 𝑛𝑚−1 Proof. Substitution of (4) into (1) and then grouping together of the summands with the same cardinality of 𝐼 yields 𝑠1 1 𝑢1 (𝑠1 , 𝜇∗ … , 𝜇∗ ) = 𝑚−1 ∑ (𝑛 − 1)𝑚−|𝐼| ∫ ∏ 𝑑𝜇∗ (𝑠𝑗 ) = 𝑛 |𝐼|−1 𝑆≥𝑠 # argmin(𝑠𝑗 ) 𝐼⊆{1,2,…,𝑚} 1 𝑗∈𝐼 𝑗∈𝐼\{1} 𝑖∈𝐼 𝑚−1 𝑘+1 (8) 𝑠1 𝑚−1 1 = 𝑚−1 ∑ ( ) (𝑛 − 1)𝑚−𝑘−1 ∫ ∏ 𝑑𝜇∗ (𝑠𝑗 ). 𝑛 𝑘 𝑘 𝑆≥𝑠 # argmin (𝑠𝑗 ) 𝑘=0 1 1≤𝑗≤𝑘+1 𝑗=2 If 𝜇∗ (𝑠1 ) = 0, one can ignore in (8) the set of zero measure, where 𝑠1 = 𝑠𝑖 for some 𝑖 ≠ 1, then use of the Fubini’s theorem and the binomial identity to get (7) 50 𝑚−1 ∗ ∗) 𝑠1 𝑚−1 𝑢1 (𝑠1 , 𝜇 … , 𝜇 = ∑( ) (𝑛 − 1)𝑚−𝑘−1 𝜇∗ (𝑆≥𝑠1 )𝑘 𝑛𝑚−1 𝑘 𝑘=0 𝑠1 ∗ 𝑚−1 = (𝜇 (𝑆≥𝑠1 ) + 𝑛 − 1) 𝑛𝑚−1 Then we need the identity 𝑛 𝑛 𝑛 𝑝𝑘 𝑞𝑛−𝑘 1 𝑛 + 1 𝑘+1 𝑛−𝑘 (𝑝 + 𝑞)𝑛+1 − 𝑞 𝑛+1 ∑( ) = ∑( )𝑝 𝑞 = . (9) 𝑘 𝑘+1 𝑝(𝑛 + 1) 𝑘+1 𝑝(𝑛 + 1) 𝑘=0 𝑘=0 In the case 𝑝 + 𝑞 = 1, this is the expectation of 1/(𝑘 + 1) with respect to the binomial distribution. If 𝜇∗ (𝑠1 ) > 0, one can rewrite (8) using (9) three times: 𝑚−1 𝑘 𝑘−𝑙 ∗ ∗) 𝑠1 𝑚−1 𝑘 𝜇∗ (𝑠1 )𝑙 𝜇∗ (𝑆≥𝑠1 ) 𝑢1 (𝑠1 , 𝜇 … , 𝜇 = 𝑚−1 ∑ ( ) (𝑛 − 1)𝑚−𝑘−1 ∑ ( ) = 𝑛 𝑘 𝑙 𝑙+1 𝑘=0 𝑙=0 𝑚−1 𝑘+1 𝑘+𝑙 𝑠1 𝑚−1 𝑚−𝑘−1 𝜇∗ (𝑆≥𝑠1 ) – 𝜇∗ (𝑆>𝑠1 ) = 𝑚−1 ∑ ( ) (𝑛 − 1) = 𝑛 𝑘 (𝑘 + 1)𝜇∗ (𝑠1 ) 𝑘=0 𝑠1 (𝜇∗ (𝑆≥𝑠1 ) + 𝑛 − 1)𝑚 – ( 𝜇∗ (𝑆>𝑠1 ) + 𝑛 − 1)𝑚 = 𝑛𝑚−1 𝑚𝜇∗ (𝑠1 ) 𝑚−1 𝑠1 = ∑ (𝜇∗ (𝑆≥𝑠1 ) + 𝑛 − 1)𝑘 ( 𝜇∗ (𝑆>𝑠1 ) + 𝑛 − 1)𝑚−𝑘−1 𝑚𝑛𝑚−1 𝑘=0 For 𝑚 ∈ ℤ>0 , consider the following homogeneous polynomials 𝑚−1 𝑥𝑚 − 𝑦𝑚 𝑝𝑚 (𝑥, 𝑦) = = ∑ 𝑥 𝑘 𝑦 𝑚−𝑘 , 𝑥−𝑦 𝑘=0 𝑞𝑚 (𝑥, 𝑦, 𝑧) ≔ 𝑝𝑚 (𝑥, 𝑦)𝑝𝑚 (𝑥, 𝑧) − 𝑝𝑚 (𝑥, 𝑥)𝑝𝑚 (𝑦, 𝑧) = =𝑝𝑚 𝑦)𝑝𝑚 𝑧) − 𝑚𝑥 𝑚−1 𝑝𝑚 (𝑦, 𝑧). (𝑥, (𝑥, Lemma 3. 1. The following polynomial identity is true 𝑚−1 𝑞𝑚 (𝑥, 𝑦, 𝑧) = ∑ 𝑥 𝑚−1−𝑘 𝑝𝑚−𝑘 (𝑦, 𝑧)(𝑥 𝑘 − 𝑦 𝑘 )(𝑥 𝑘 − 𝑧 𝑘 ) = 𝑘=1 (10) =𝑞2 (𝑥, 𝑦, 𝑧) = ∑𝑚−1 𝑘=1 𝑥 𝑚−1−𝑘 𝑝𝑚−𝑘 (𝑦, 𝑧)𝑝𝑘 (𝑥, 𝑦)𝑝𝑘 (𝑥, 𝑧), 2. For positive 𝑥, 𝑦, 𝑧, if 𝑞2 (𝑥, 𝑦, 𝑧) = (𝑥 − 𝑦)(𝑥 − 𝑧) > 0 then 𝑞𝑚 (𝑥, 𝑦, 𝑧) > 0 for all 𝑚 ≥ 2. Proof. Parts of (10) equals to 𝑚−1 ∑ ∑ (𝑥 𝑚−1+𝑘 𝑦 𝑖 𝑧 𝑗 + 𝑥 𝑚−1−𝑘 𝑦 𝑖+𝑘 𝑧 𝑗+𝑘 − 𝑥 𝑚−1 𝑦 𝑖 𝑧 𝑗+𝑘 − 𝑥 𝑚−1 𝑦 𝑖+𝑘 𝑧 𝑗 ) 𝑘=1 𝑖,𝑗≥0 𝑖+𝑗=𝑚−1−𝑘 The expression 𝜈𝑚𝑛 and the interval from the following lemma appears in the description of Nash equilibriums. 51 Lemma 4. 1. The utility on the symmetric profile of pure strategies has the form 𝑛𝑚 − (𝑛 − 1)𝑚 𝑢𝑖 (𝑠, … , 𝑠) = 𝑠𝜐𝑚𝑛 , 𝜐𝑚𝑛 ≔ . (11) 𝑚𝑛{𝑚−1} 2. For 𝑚, 𝑛 ≥ 2 the following interval is nonempty −1 (𝑛 − 1)𝑚−1 𝑚(𝑛 − 1)𝑚−1 𝑛𝑚 − (𝑛 − 1)𝑚 (𝜐𝑚𝑛 , 𝜐𝑚𝑛 ) = ( , ). (12) 𝑛𝑚−1 𝑛𝑚 − (𝑛 − 1)𝑚 𝑚𝑛𝑚−1 3. The endpoints and length of the above interval admit the asymptotics −1⁄𝑧 1 1 lim 𝜐 𝑚𝑛 = 𝑧(1 − 𝑒 ) = 1 − + 𝑂 ( ), 𝑚,𝑛→∞ 𝑧→+∞ 2𝑧 𝑧2 𝑛⁄𝑚→𝑧 −1 (𝑛 − 1)𝑚−1 −1⁄𝑧 𝑒 −1⁄𝑧 1 1 lim (𝜐𝑚𝑛 − 𝜐𝑚𝑛 𝑚−1 ) = 𝑧(1 − 𝑒 ) − = 2 + 𝑂 ( ) 𝑚,𝑛→∞ 𝑛 ⁄ 𝑧(1 − 𝑒 −1 𝑧 ) 𝑧→+∞ 12𝑧 𝑧3 𝑛⁄𝑚→𝑧 Proof. The identity (11) can be obtained directly or as the special case of (6). −1 (𝑛−1)𝑚−1 The inequality 𝜐𝑚𝑛 𝑛 < 𝜐𝑚𝑛 between endpoints of (12) is equivalent to the positivity of 𝑞𝑚 (𝑛, 𝑛 − 1, 𝑛 − 1) from Lemma 3. Asymptotic formulas come from easy calculation with the Maclaurin series. 3.3 Pure Strategy Nash Equilibrium 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 1. If 𝑠 < 𝑠 ∗ then 𝑠 ≤ 𝜐𝑚𝑛 𝑠 ∗ . (I.e. 𝑆 ⋂( 𝜐𝑚𝑛 𝑠 ∗ , 𝑠 ∗ ) = ∅. ) 𝑛−1 𝑚−1 2. If 𝑠 > 𝑠 ∗ then 𝑠 ( 𝑛 ) ≤ 𝜐𝑚𝑛 𝑠 ∗ . Proof. Note that 𝑠, if 𝑠1 < 𝑠 ∗ , 𝜐𝑚𝑛 𝑠, if 𝑠1 = 𝑠 ∗ , 𝑢1 (𝑠, 𝑠 ∗ , … , 𝑠 ∗ ) = 𝑛 − 1 𝑚−1 {( 𝑛 ) , if 𝑠1 > 𝑠 ∗ . Then 𝑢1 (𝑠 ∗ , 𝑠 ∗ , … , 𝑠 ∗ ) ≥ 𝑢1 (𝑠, 𝑠 ∗ , … , 𝑠 ∗ ) yields the conditions 1 and 2 from the proposition. Example 1 (Numerical). 1. Let m = 50, n = 10 S = {1, 2, … ,10}. Then only one Nash equilibrium exists in pure symmetric strategies with s ∗ = 1. 2. Let m = 100, n = 10000 S = {1, 2, … ,10}. Then only one Nash equilibrium exists in pure symmetric strategies with s ∗ = 10. 3. Let m = n = 200 S = {1, 2, 3, 4, 5, 9, 9.1, 9.2, 9.3, … ,10}. Then only one Nash equilibrium exists in pure symmetric strategies with s ∗ = 9. Corollary 1. Suppose that 𝑆 consists of two strategies {𝑠𝑚𝑖𝑛 < 𝑠𝑚𝑎𝑥 }. 𝑠 1. The profile (𝑠𝑖 = 𝑠𝑚𝑎𝑥 )1≤ 𝑖≤ 𝑚 is a symmetric Nash equilibrium iff 𝑠 𝑚𝑖𝑛 ≤ 𝜐𝑚𝑛 . 𝑚𝑎𝑥 𝑠 𝑚−1 −1 𝑛−1 2. The profile (𝑠𝑖 = 𝑠𝑚𝑖𝑛 )1≤ 𝑖≤ 𝑚 is a symmetric Nash equilibrium iff 𝑠 𝑚𝑖𝑛 ≥ 𝜐𝑚𝑛 ( 𝑛 ) . 𝑚𝑎𝑥 𝑠 3. Both profiles(𝑠𝑖 = 𝑠𝑚𝑎𝑥 )1≤ 𝑖≤ 𝑚 and (𝑠𝑖 = 𝑠𝑚𝑖𝑛 )1≤ 𝑖≤ 𝑚 are symmetric Nash equilibria iff 𝑠 𝑚𝑖𝑛 𝑚𝑎𝑥 𝑚(𝑛−1)𝑚−1 𝑛𝑚 −(𝑛−1)𝑚 lies in the interval [ 𝑚 , ] from (12). 𝑛 −(𝑛−1)𝑚 𝑚𝑛𝑚−1 52 Example 2 (Numerical). Let S = {smin , smax }, m ∈ { 2, 10, 50, 100, 200, 500}, n ∈ {2, 10,50,100, 200, 500, 103 , 2 ∙ 103 , 5 ∙ 103 , 104 }. s Define b = s min . Then if b = 0.1 and n ≥ m, the Nash equilibrium exists in pure symmetric max strategies with s ∗ = smax. 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 strategies with s ∗ = smin . 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 𝑠 𝑛−1 𝑚−1 respect to the Lebesgue measure exists iff 𝑠 𝑚𝑖𝑛 ≤ ( 𝑛 ) . In this case, the game price and the 𝑚𝑎𝑥 support of the measure are (𝑛 − 1)𝑚−1 (13) 𝑢∗ = 𝑠𝑚𝑎𝑥 , 𝑠𝑢𝑝𝑝 𝜇 ∗ = [𝑢 ∗ , 𝑠𝑚𝑎𝑥 ] 𝑛𝑚−1 and the density of the measure 𝜇∗ is 1⁄(𝑚−1) (14) 𝑑𝜇∗ (𝑠) 𝑛 − 1 𝑠𝑚𝑎𝑥 = . 𝑑𝑠 𝑚 − 1 𝑠 𝑚⁄(𝑚−1) ′ ′ Proof. The support of the measure 𝜇 should be a subinterval supp 𝜇∗ = [𝑠𝑚𝑖𝑛 ∗ , 𝑠𝑚𝑎𝑥 ], 𝑠𝑚𝑖𝑛 ∈ [𝑠𝑚𝑖𝑛 , 𝑠𝑚𝑎𝑥 ) and the formula (7) for the game price 𝑢 is∗ 𝑠1 𝑚−1 ′ (15) 𝑚−1 (𝜇∗ (𝑆≥𝑠1 ) + 𝑛 − 1) = 𝑢∗ , 𝑠𝑚𝑖𝑛 ≤ 𝑠1 ≤ 𝑠𝑚𝑎𝑥 . 𝑛 ′ ′ 𝑛−1 𝑚−1 Substitutions of 𝑠1 = 𝑠𝑚𝑎𝑥 and 𝑠1 = 𝑠𝑚𝑖𝑛 in (15) yield 𝑠𝑚𝑖𝑛 = 𝑢∗ = 𝑠𝑚𝑎𝑥 ( 𝑛 ) Then (15) can be rewritten as 𝑠𝑚𝑎𝑥 ⁄ ⁄ 1 𝑚−1 −1 𝑚−1 𝜇∗ (𝑆{≥𝑠1 } ) = ∫ 𝑑𝜇∗ (𝑠) = (𝑛 − 1)𝑠𝑚𝑎𝑥 𝑠1 − 𝑛 + 1. 𝑠1 ′ Taking derivative in 𝑠 ∈ supp 𝜇∗ = [𝑠𝑚𝑖𝑛 , 𝑠𝑚𝑎𝑥 ], we obtain the formula for the density. Remark 1. Note that in the previous proposition 𝑑𝜇∗ (𝑠) 𝑚𝑖𝑛 𝑑𝑠 1 𝑚 − 1 1 1 lim ∗ = lim (1 − ) = 𝑒 𝑧 = 1 − + 𝑂 ( 2 ). 𝑚,𝑛→∞ 𝑑𝜇 (𝑠) 𝑚,𝑛→∞ 𝑛 𝑧→+∞ 𝑧 𝑧 𝑛/𝑚→𝑧 𝑚𝑎𝑥 𝑛/𝑚→𝑧 𝑑𝑠 So, for large 𝑛/𝑚 the measure 𝜇∗ is closed to uniform. Example 3 (Numerical). Let parameters 𝑚, 𝑛 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. 53 Table 1 Existence of Nash equilibrium in mixed strategy (20), (21) m 2 10 50 100 200 500 n 2 + - - - - - 10 + + - - - - 50 + + + + - - 100 + + + + + - 200 + + + + + - 500 + + + + + + 1000 + + + + + + 2000 + + + + + + 5000 + + + + + + 10000 + + + + + + From Table 1 we can conclude that Nash equilibrium in mixed strategies always exists when the 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 The Cases of Discreet Measures 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 other parameters. Proposition 3. Suppose that the set of strategies 𝑆 = {𝑠𝑚𝑖𝑛 < 𝑠𝑚𝑎𝑥 } consists of two elements. 𝑠 Then the symmetric Nash equilibrium in mixed strategies 𝜇∗ exists iff the value 𝑚𝑖𝑛 lies on the 𝑠𝑚𝑎𝑥 interval from (12): 𝑠𝑚𝑖𝑛 𝑚(𝑛 − 1)𝑚−1 𝑛𝑚 − (𝑛 − 1)𝑚 (16) ∈( 𝑚 , ) 𝑠𝑚𝑎𝑥 𝑛 − (𝑛 − 1)𝑚 𝑚𝑛𝑚−1 In this case, 𝑛 − 𝜇∗ (𝑠𝑚𝑖𝑛 ) is the a root of the polynomial 𝑚−1 (17) ℎ(𝑥) = ∑ (𝑠𝑚𝑖𝑛 𝑛𝑘 − 𝑠𝑚𝑎𝑥 (𝑛 − 1)𝑘 )𝑥 𝑚−𝑘−1 ; 𝑘=0 and the game price is 𝑚−1 ∗ 𝑠𝑚𝑎𝑥 𝑚−𝑘−1 𝑢 = 𝑚−1 ∑ (𝑛 − 1)𝑘 (𝑛 − 1 + 𝜇∗ (𝑠𝑚𝑎𝑥 )) 𝑚𝑛 𝑘=0 (18) 𝑚−1 𝑠𝑚𝑖𝑛 𝑚−𝑘−1 = 𝑚−1 ∑ 𝑛𝑘 (𝑛 − 𝜇∗ (𝑠𝑚𝑎𝑥 )) . 𝑚𝑛 𝑘=0 Proof. As special cases of (6), we get 𝑚−1 𝑠𝑚𝑎𝑥 𝑚−𝑘−1 𝑢1 (𝑠𝑚𝑎𝑥 , 𝜇∗ , … , 𝜇∗ ) = ∑ (𝑛 − 1)𝑘 (𝑛 − 𝜇∗ (𝑠𝑚𝑖𝑛 )) , 𝑚𝑛𝑚−1 𝑘=0 (19) 𝑚−1 ∗ ∗ 𝑠𝑚𝑖𝑛 𝑚−𝑘−1 𝑢1 (𝑠𝑚𝑎𝑥 , 𝜇 , … , 𝜇 ) = 𝑚−1 ∑ 𝑛𝑘 (𝑛 − 𝜇∗ (𝑠𝑚𝑖𝑛 )) . 𝑚𝑛 𝑘=0 The equality between two expressions from (19) takes the form ∗ (𝑠 )) ℎ(𝑛 − 1 + 𝜇 𝑚𝑖𝑛 = 0 for the polynomial ℎ(𝑥) from (17). 54 𝑠 𝑛−1 𝑚−1 Note that ℎ(𝑛 − 1) = 𝑠𝑚𝑖𝑛 (𝑛𝑚 − (𝑛 − 1)𝑚 ) − 𝑠𝑚𝑎𝑥 𝑚(𝑛 − 1)𝑚−1 > 0 iff 𝑠 𝑚𝑖𝑛 > ( 𝑛 ) −1 𝜐𝑚𝑛 𝑚𝑎𝑥 𝑠 and ℎ(𝑛) = 𝑠𝑚𝑖𝑛 𝑚𝑛𝑚−1 − 𝑠𝑚𝑎𝑥 (𝑛𝑚 − (𝑛 − 1)𝑚 ) < 0 iff 𝑠 𝑚𝑖𝑛 < 𝜐𝑚𝑛 . 𝑚𝑎𝑥 𝑚−1 𝑠𝑚𝑖𝑛 −1 (𝑛−1) So for 𝑠𝑚𝑎𝑥 ∈ (𝜐𝑚𝑛 𝑛 𝑚−1 , 𝜐𝑚𝑛 ) the Bolzano’s theorem implies the existence of 𝑥 ∈ (𝑛 − 1, 𝑛) which is a root of ℎ(𝑡), and the corresponding probability 𝑝 = 𝑥 − 𝑛 + 1 = 𝜇∗ (𝑠𝑚𝑎𝑥 ) of mixed strategy 𝜇∗ . Let 𝑥 ∈ (𝑛 − 1, 𝑛). By Lemma 3 we have 𝑞𝑚 (𝑛, 𝑛 − 1, 𝑥) > 0 and 𝑞𝑚 (𝑛 − 1, 𝑛, 𝑥) > 0. The first 𝑠 𝑠 inequality implies ℎ(𝑥) > 0 when 𝑚𝑖𝑛 < 𝜐𝑚𝑛 . The second inequality implies ℎ(𝑥) < 0 when 𝑚𝑖𝑛 < 𝑠𝑚𝑎𝑥 𝑠𝑚𝑎𝑥 𝑚−1 −1 (𝑛−1) 𝜐𝑚𝑛 𝑛 . Remark 2. In the case of a two-element set 𝑆 = {𝑠𝑚𝑖𝑛 < 𝑠𝑚𝑎𝑥 } the condition that 𝑠𝑚𝑖𝑛 ⁄𝑠𝑚𝑎𝑥 belongs to the interval from (12) appeared in both Corollary 1. about pure strategies and in Proposition 3 on mixed strategies. The first is the limit case of the second. Example 4 (𝑆 = {𝑠𝑚𝑖𝑛 < 𝑠𝑚𝑎𝑥 }). Note that the degree of the polynomial ℎ(𝑥) from (17) equals to 𝑚 − 1. So for small 𝑚 one can calculate the equilibrium measure 𝜇∗ and the game price 𝑢∗ explicitly. 𝑠 2𝑛−2 2𝑛−1 In the case of two provers, 𝑚 = 2, for 𝑚𝑖𝑛 ∈ ( , ): 𝑠𝑚𝑎𝑥 2𝑛−1 2𝑛 (2𝑛 − 1)𝑠𝑚𝑖𝑛 − (2𝑛 − 2)𝑠𝑚𝑎𝑥 ∗ 𝑠𝑚𝑎𝑥 𝑠𝑚𝑖𝑛 𝜇∗ (𝑠𝑚𝑎𝑥 ) = ,𝑢 = . 𝑠𝑚𝑎𝑥 − 𝑠𝑚𝑖𝑛 2𝑛(𝑠𝑚𝑎𝑥 − 𝑠𝑚𝑖𝑛 ) 𝑠 3(𝑛−1)2 3𝑛2 −3𝑛+1 In the case of three provers, 𝑚 = 3, for 𝑠 𝑚𝑖𝑛 ∈ (3𝑛2 −3𝑛+1 , 3𝑛2 ): 𝑚𝑎𝑥 (3𝑛 − 2)𝑠𝑚𝑖𝑛 − (3𝑛 − 3)𝑠𝑚𝑎𝑥 + √𝐷 𝜇∗ (𝑠𝑚𝑎𝑥 ) = , 2(𝑠𝑚𝑎𝑥 − 𝑠𝑚𝑖𝑛 ) 2 𝐷 = −3𝑛2 𝑠𝑚𝑖𝑛 + (6𝑛2 − 6𝑛 + 4)𝑠𝑚𝑖𝑛 𝑠𝑚𝑎𝑥 − 3(𝑛 − 1)2 𝑠𝑚𝑎𝑥 2 . 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. Proposition 4. Suppose that there are two provers 𝑚 = 2 and the set of strategies is 𝑆 = {𝑠(0) > 𝑠(1) > ⋯ > 𝑠(𝑘) }. ′ (−1)𝑙 1. 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) > 𝑠(1) > ⋯ > 𝑠(𝑘) > 0 and (𝑘 + 1)-tuples of (𝜎𝑖 )0≤𝑖≤𝑘 such that 0 < 𝜎0 < 𝜎2 < 𝜎4 < ⋯ , 0 < 𝜎1 < 𝜎3 < 𝜎5 < ⋯ . (20) 2. If the symmetric Nash equilibrium is given by a probability measure 𝜇∗ with 𝑠𝑢𝑝𝑝 𝜇∗ = 𝑆, then the game price and probabilities are 𝑎 𝑢∗ = , 𝑎 = 1 + (1 + (−1)𝑘 )(𝑛 − 1). 2𝑛𝜎𝑘 𝜎𝑙 − 𝜎𝑙−1 𝜇∗ (𝑠(ℓ) ) = 2𝑛𝑢∗ (𝜎𝑙 − 𝜎𝑙−1 ) − (−1)ℓ (2𝑛 − 2) = 𝑎 − (−1)ℓ (2𝑛 − 2), 0 ≤ 𝑙 ≤ 𝑘. (21) 𝜎𝑘 3. Such Nash equilibrium exists iff (𝜎𝑖 )0≤𝑖≤𝑘 satisfy the inequalities (20) and (22) 𝑎𝜎𝑙 > 𝑎𝜎𝑙−1 + (−1)𝑙 (2𝑛 − 2)𝜎𝑘 , 0 ≤ 𝑙 ≤ 𝑘, (22) The set of all such (𝜎𝑖 )0≤𝑖≤𝑘 is a nonempty interior of convex (𝑘 + 1) is dimensional polytope. 55 Proof. The formula (6) for the game price 𝑢∗ = 𝑢1 (𝑠1 , 𝜇∗ ) takes the form 𝑢∗ 𝜇∗ (𝑠1 ) = 2𝑛 − 2𝑛 + 2 − 2𝜇∗ (𝑆>𝑠1 ). 𝑠1 Then we prove simultaneously by induction in 𝑙 = 0,1, … , 𝑘 the formulas for probabilities (21) and 𝜇∗ (𝑆≥𝑠(𝑙) ) = 2𝑛𝜎𝑙 − (1 + (−1)𝑙 )(𝑛 − 1). 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). 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)𝜎𝑘 + 𝜎𝑙+1 ) for all even 𝑙. In the case when 𝑘 is even, one can select arbitrarily 𝜎𝑙 with even 𝑙 satisfying 0 < 𝜎0 < 𝜎2 < ⋯ < 𝜎𝑘 and additional condition 𝜎0 2𝑛−2 2𝑛−2 2𝑛−2 𝜎 > 2𝑛−1 and then select 𝜎𝑙 ∈ (𝜎𝑙−1 − 2𝑛−1 𝜎𝑘 , 𝜎𝑙+1 − 2𝑛−1 𝜎𝑘 ) for all odd 𝑙. 𝑘 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) > ⋯ } [bounded below by a positive constant] is described as follows: Consider an arbitrary sequence 𝜎−1 < 𝜎0 < 𝜎1 , …, where the subsequence of elements with odd indexes 0 = 𝜎−1 < 𝜎1 < 𝜎3 < ⋯ is strongly increasing and bounded and for each even 𝑙 ≥ 0 𝜎𝑙 ∈ ((2𝑛 − 2) lim 𝜎2𝑖+1 + 𝜎𝑙−1 , (2𝑛 − 2) lim 𝜎2𝑖+1 + 𝜎𝑙+1 ). 𝑖→∞ 𝑖→∞ In this case the subsequence of elements with even indices is strongly increasing 𝜎0 < 𝜎2 < ⋯ and 𝑙𝑖𝑚 𝜎2𝑖 = (2𝑛 − 1) 𝑙𝑖𝑚 𝜎2𝑖+1 ; the game price is 𝑖→∞ 𝑖→∞ 1 2𝑛 − 1 𝑢∗ = = . 2𝑛 lim 𝜎2𝑖 2𝑛 lim 𝜎2𝑖+1 𝑖→∞ 𝑖→∞ strategies and probabilities are 1 𝑠(ℓ) = , 𝜇∗ (𝑠(ℓ) ) = 2𝑛𝑢∗ (𝜎𝑙 − 𝜎𝑙−1 ) − (−1)ℓ (2𝑛 − 2), ℓ = 0,1, … 𝜎𝑙 + 𝜎𝑙−1 Proof. This Proposition can be proved similarly to the previous one. 𝑙+1 Example 5. According to the previous proposition, one can select 𝜎𝑙 = 𝑙+2 for odd 𝑙 = −1,1,3, … 𝜎 +𝜎 ℓ2 +3ℓ+1 and 𝜎𝑙 = 2𝑛 − 2 + 𝑙−1 2 𝑙+1 = 2𝑛 − 2 + (ℓ+1)(ℓ+3) for even ℓ = 0,2,4, ⋯ Then 1 , if ℓ = 1,3,5, ⋯ 2ℓ + 1 2𝑛 − ℓ(ℓ + 2) 𝑠(ℓ) = 1 , if ℓ = 0,2,4, … 2ℓ + 5 2𝑛 − { (ℓ + 1)(ℓ + 3) 1 , if ℓ = 1,3,5, ⋯ ℓ(ℓ + 2) 1 𝜇(𝑠(ℓ) }) = 𝑢∗ = . 1 2𝑛 , if ℓ = 0,2,4, … {(ℓ + 1)(ℓ + 3) 56 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. 3.6 Measures with Discreet and Continuous Parts 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 𝑛 − (𝑛 − 1)𝑚 𝑑𝜇∗ (𝑠) In this case, the game price 𝑢∗ , the discrete part 𝜇∗ (𝑠𝑚𝑖𝑛 ) and the density 𝑑𝑠 of the measure is given by the formulas 𝑚−1 (𝑛 − 1)𝑚−1 (𝑛 − 𝜇∗ (𝑠𝑚𝑖𝑛 )) 𝑠𝑚𝑎𝑥 ∗ 𝑢 = 𝑠𝑚𝑎𝑥 , = ′ . (23) 𝑛 𝑚−1 (𝑛 − 1) 𝑚−1 𝑠 ⁄ 1 𝑚−1 𝑑𝜇∗ (𝑠) 𝑛 − 1 𝑠𝑚𝑎𝑥 (24) = , 𝑠 ∈ [𝑠 ′ , 𝑠𝑚𝑎𝑥 ] 𝑑𝑠 𝑚 − 1 𝑠 𝑚⁄𝑚−1 Proof. Substitution of 𝑠𝑚𝑎𝑥 and 𝑠 ′ into the formula for the game price (6) yields (29). Derivation of (7) yields (24). Substitution of the expression for game price into (6) for 𝑠1 = 𝑠𝑚𝑖𝑛 yields 𝑚−1 𝑚−𝑘−1 ℎ1 (𝜇 𝑚𝑖𝑛 )) = 𝑠𝑚𝑖𝑛 ∑ 𝑛𝑘 (𝑛 − 𝜇∗ (𝑠𝑚𝑖𝑛 )) ∗ (𝑠 − 𝑠𝑚𝑎𝑥 𝑚(𝑛 − 1)𝑚−1 = 0., (25) 𝑘=0 𝑠𝑚𝑖𝑛 (𝑛−1)𝑚−1 𝑠𝑚𝑖𝑛 𝑚(𝑛−1)𝑚−1 Note that ℎ1 (0) ≥ 0 iff ≥ 𝑚−1 and ℎ1 (0) ≤ 0 iff ≤ 𝑚 . 𝑠𝑚𝑎𝑥 𝑛 𝑠𝑚𝑎𝑥 𝑛 −(𝑛−1)𝑚 𝑠 (𝑛−1)𝑚−1 𝑚(𝑛−1)𝑚−1 If 𝑠 𝑚𝑖𝑛 ∈ [ 𝑛𝑚−1 , 𝑛𝑚 −(𝑛−1)𝑚] we have a symmetric Nash equilibrium with 𝜇∗ (𝑠𝑚𝑖𝑛 ) given by a 𝑚𝑎𝑥 solution of equation (25). Proposition 7. Suppose that 𝑠𝑢𝑝𝑝 𝜇∗ = [𝑠𝑚𝑖𝑛 , 𝑠 ′ ] ∪ {𝑠𝑚𝑎𝑥 }, 𝑠𝑚𝑖𝑛 < 𝑠 ′ < 𝑠𝑚𝑎𝑥 . Then there exists symmetric Nash equilibrium given by probability measure 𝜇∗ absolutely continuous with respect to Lebesgue measure on [𝑠𝑚𝑖𝑛 , 𝑠 ′ ] iff 𝑠𝑚𝑖𝑛 (𝑛 − 1)𝑚−1 𝑛𝑚 −(𝑛 − 1)𝑚 ∈ ( 𝑚−1 , ). 𝑠𝑚𝑎𝑥 𝑛 𝑚𝑛𝑚−1 𝑑𝜇∗ (𝑠) In this case, the game price 𝑢∗ , the continuous part 𝜇∗ ([𝑠𝑚𝑖𝑛 , 𝑠 ′ ]) and the density 𝑑𝑠 of the measure are given by the formulas 𝑚−1 ∗ ′ (𝑛 − 𝜇∗ ([𝑠𝑚𝑖𝑛 , 𝑠 ′ ])) (26) 𝑢 = 𝑠𝑚𝑖𝑛 , 𝑠 = 𝑠𝑚𝑖𝑛 . 𝑛𝑚−1 1⁄(𝑚−1) 𝑑𝜇∗ (𝑠) 𝑛 𝑠𝑚𝑖𝑛 (27) = , 𝑠 ∈ [𝑠𝑚𝑖𝑛 , 𝑠 ′ ] 𝑑𝑠 𝑚 − 1 𝑠 𝑚⁄(𝑚−1) 57 Proof. Substitution of 𝑠𝑚𝑖𝑛 and 𝑠 ′ yields (𝑛 − 𝜇∗ ([𝑠𝑚𝑖𝑛 , 𝑠 ′ , ]))𝑚−1 𝑢∗ = 𝑠𝑚𝑖𝑛 = 𝑠 ′ . 𝑛𝑚−1 The formula for density coincides with (14). Substitution of the expression for game price in (6) for 𝑠1 = 𝑠𝑚𝑎𝑥 yields 𝑚−1 ℎ2 (𝜇∗ ′ ])) ([𝑠𝑚𝑖𝑛 , 𝑠 , = 𝑠𝑚𝑎𝑥 ∑ (𝑛 − 1)𝑘 (𝑛 − 𝜇∗ ([𝑠𝑚𝑖𝑛 , 𝑠 ′ , ]))𝑚−1 − 𝑠𝑚𝑖𝑛 𝑚𝑛𝑚−1 = 0. (28) 𝑘=0 smin nm −(n−1)m−1 smin (n−1)m−1 Note that h2 (0) ≥ 0 iff smax ≤ mnm−1 and h2 (1) ≤ 0 iff smax ≥ nm−1 . If smin (n−1)m−1 nm −(n−1)m smax ∈ [ m−1 n , mnm−1 ] we have symmetric Nash equilibrium with μ∗ ([smin , s ′ , ]) given by the solution of equation (28). 4. Prover Migration Game 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≤𝑖 ′ ≤𝑚|𝑖 ′ ≠𝑖 ⋀ 𝑠𝑖′ =𝑠𝑖 } (29) 1 𝑢𝑖 (𝑠1 , … , 𝑠𝑚 ) = (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, … , 𝑘. (30) 𝑛1 + 𝑛2 ⋯ + 𝑛𝑘 Proof. The utility 𝑢1 (𝑠1 , 𝜇∗ , … , 𝜇∗ ) from (1) for (29) is given by the binomial formula 𝑚−1 𝑚′ 𝑚−1 𝑚 − 1 ∗ 𝑚′ ′ 1 𝜇∗ (𝑠1 ) ∑ ( ′ ) 𝜇 (𝑖) (1 − 𝜇∗ (𝑠1 ))𝑚−𝑚 −1 (1 − ) = (1 − ) . ′ 𝑚 𝑛𝑠𝑖 𝑛𝑠𝑖 𝑚 =0 Then the condition (2) for Nash equilibrium yields (30). The formula (30) means that the “best” strategy for provers to choose the block is to choose randomly one of the proofs-candidates among all proposed ones from different blocks. After that, proof selection completely defines the corresponding block selection. 5. Conclusions 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. 58 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. 6. Acknowledgments This work was supported in part by the National Research Foundation of Ukraine under Grant 2020.01/0351. 7. References [1] Rootstock: smart contracts on bitcoin network, 2018. URL: https://www.rsk.co. [2] A. Back, M. Corallo, L. Dashjr, M. Friedenbach, G. Maxwell, A. Miller, A. Poelstra, J. Timón, P. Wuille, Enabling blockchain innovations with pegged sidechains, 2014. URL: https://blockstream.com/sidechains.pdf. [3] A. Garoffolo, R. Viglione, Sidechains: Decoupled consensus between chains, 2018. URL: https://arxiv.org/abs/1812.05441.pdf. [4] A. Kiayias, D. Zindros, Proof-of-work sidechains, Cryptology ePrint Archive, Report 2018/1048, 2018. URL: https://eprint.iacr.org/2018/1048.pdf [5] A. Garoffolo, D. Kaidalov, R. Oliynykov, Zendoo: a zk-SNARK Verifiable Cross-Chain Transfer Protocol Enabling Decoupled and Decentralized Sidechains. 2020. URL: https://arxiv.org/pdf/2002.01847.pdf [6] A. Kiayias, A. Russell, B. David, R. Oliynykov, Ouroboros: A provably secure proof-of-stake blockchain protocol, CRYPTO 2017, Part I, volume 10401 of Lecture Notes in Computer Science, Springer, Heidelberg, 2017, pp. 357–388. [7] J. Garay, A. Kiayias, N. Leonardos, The bitcoin backbone protocol: Analysis and applications, Advances in Cryptology - EURO-CRYPT 2015, Part II, volume 9057 of Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 2015, pp. 281–310. [8] E. Ben-Sasson, A. Chiesa, E.Trómer, M. Virza, Succinct non-interactive zero knowledge for a von Neumann architecture, Cryptology ePrint Archive, Report 2013/879, 2013. URL: https://eprint.iacr.org/2013/879.pdf [9] S. Bowe, A.Gabizon. Making Groth’s zk-SNARK simulation extractable in the random oracle model, Cryptology ePrint Archive, Report 2018/187, 2018. URL: https://eprint.iacr.org/2018/187.pdf. [10] Y. Bespalov, A. Garofolo, L. Kovalchuk, H. Nelasa, R.Oliynykov, Models of distributed proof generation for zk-SNARK-based blockchains, Theoretical and Applied Cryptography, Belarusian State University, Minsk, Belarus, 2020, pp. 112–120. URL: http://conf.bsu.by/data/theoreticalandappliedcrypto/doc/TAC_2020_Proceedings.pdf, [11] R. B. Myerson, Game theory: Analysis of conflict, Harvard University Press, 1997. [12] N. Ham, Notions of symmetry for finite strategic-form games, 2013. URL: https://arxiv.org/abs/1311.4766.pdf 59