Models for Generation of Proof Forest in zk-SNARK Based Sidechains

Abstract

Sidechains are among the most promising scalability and extended functionality solutions for blockchains. Application of zero knowledge techniques (Latus, Mina) allows for reaching high level security and general throughput, though it brings new challenges on keeping decentralization where significant effort is required for robust computation of zk-proofs. We consider a simultaneous decentralized creation of various zk-proof trees that form proof-trees sequences in sidechains in the model that combines behavior of provers, both deterministic (mutually consistent) or stochastic (independent) and types of proof trees. We define the concept of efficiency of such process, introduce its quantity measure and recommend parameters for tree creation. In deterministic cases, the sequences of published trees are ultimately periodic and ensure the highest possible efficiency (no collisions in proof creation). In stochastic cases, we obtain a universal measure of prover efficiencies given by the explicit formula in one case or calculated by a simulation model in another case. The optimal number of allowed provers’ positions for a step can be set for various sidechain parameters, such as number of provers, number of time steps within one block, etc. Benefits and restrictions for utilization of non-perfect binary proof trees are also explicitly presented.

1. Introduction

Sidechains (SCs) were first proposed in [1] and quickly became a universal and very comfortable tool in blockchain technology, while [1] proposed sidechains with a “classical” proof-of-work (PoW) protocol for usage in Bitcoin blockchain, the next article [2] builds secure proof-of-stake (PoS) sidechains, and articles [3,4] create a special type of sidechain consensus, the Latus protocol, which is secure for both PoW and PoS sidechains. They may be considered as an additional construction bound to blockchain (called mainchain (MC)) with the aim to provide some additional functionalities. SCs should be bound to an MC, as described in mentioned articles, to provide stronger security guarantees using blockchain properties, such as liveness and persistence [5]. Binding means that SCs also should send some information to the MC to guarantee the fairness of transformations in the SC [3].

In Latus, this information contains a series of recursive zk-SNARK-proofs [6,7] to establish decentralized and verifiable cross-chain transfers. Such an approach is similar to the ones proposed in [8] (Mina) and [9] (zkSync Era), but with additional features that allow its secure usage in sidechains. Latus introduces a special dispatching scheme that assigns the generation of proofs randomly to interested parties, who then implement these tasks in parallel and submit generated proofs to the blockchain. An incentive scheme provides a reward for each accepted proof.

There are a variety of purposes to use SCs in different blockchains: for making smart-grid systems scalable and adaptable [10]; for secure data isolation in scalable consortium blockchain architecture based on world-state collaborative storage methods [11]; for secure parallel computation [12]; and for creating an exchange platform that allows the ability to trade tokens issued from different sidechains [13].

SCs may be based on various consensus protocols (such as PoW [14], PoS [15], etc.).

In this paper, we assume that SC uses the Latus protocol [4], which is a hybrid PoS based on Ouroboros Praos [16]. However, as SCs may be based on various consensuses, our main results may be applied for other consensus protocols (such as proof of work, proof of stake, etc.) with similar properties, allowing distributed proof generation and recursive SNARKs.

Following the modern trends in blockchain investigations, we use SNARKs to prove the correct functioning of SCs (detailed survey about different types of SNARKs used in blockchain can be found in [17]). These cause some modifications of the Merkle tree, which we call the “proof tree”.

Distributed proof generation for block creation is the basic feature of Latus consensus. In brief, the procedure of block creation is as follows. A block forger—an entity that creates the block—shares a list of transactions to be included into the block. Then, other entities, called provers, construct SNARK-proofs for these transactions and also for each node of the corresponding proof trees built on these transactions.

Each prover, who creates a SNARK-proof, sets the prices for their proofs, according to the pricing policy of the current epoch. In the case of collisions, when there are several proofs for some node of the binary tree, the block forger chooses the cheapest one. Proofs that were included into the block are paid by the block forger from the corresponding transaction fees.

Our previous papers [18,19,20] considered only issues related to a single block creation. We used probabilistic and game-theoretic approaches to answer the questions on the optimal choice of SC parameters (e.g., a recommended number of transactions per block and a recommended value of incentives chosen). The model in which we obtain our results is very close to realistic with only one simplifying assumption: splitting of the block construction process into a fixed number of similar steps. Such assumption can be justified by the fact that the network synchronization time is essentially smaller than the proof generation time.

In this paper, unlike the previous ones, we consider algorithms related to simultaneous construction of trees by different block forgers. The sequence of such trees forms a linearly ordered forest. When the following block is published, the most left tree is included into it, and the remaining ones are regarded as a buffer for further block generation. The base assumptions used in this paper is almost the same as in the our previous papers, with the following modification: In practice, blockchain’s sequences of transitions are proved using base SNARK for certifying single state transitions (in leaves) and merge SNARK for merging two proofs (in other vertices) ([21], Section 4.1.1). We consider the scheme that replaces each base proof for a transaction by merged proofs for pair of leaves from the new additional level. So, we obtain a mathematically equivalent model where trees are one level higher and a pair of fresh leaves correspond to each transaction; therefore, we obtain more succinct algorithms.

The paper is organized as follows. The necessary basic preliminary results on binary trees are presented in Section 2. For us it is convenient to consider the sets of strict binary trees and of non-strict binary trees as specific realizations of the free magma $\mathcal{M}={\coprod }_{n⩾0}{\mathcal{M}}_0$ with a single generator. In Section 2.2, we introduce agreed monoid structures on infinite sequences of strict binary trees and positive numbers. The background of these constructions is explained in Appendix A. In Section 2.3, we introduce the concept of perfect forest necessary for description of the main algorithm.

Section 3 presents the general scheme for $2\times 2$ algorithms corresponding to the prover’s behavior: deterministic (mutually consistent) or stochastic (independent), and shapes of generated trees: strict binary or perfect binary. It works with a potentially infinite sequence of trees t called a buffer. In the external for-loop, the first element is removed from the buffer and published as the following block. Block generation is divided into a fixed number of steps, each of which calls the OneStep() procedure. In all $2\times 2$ cases each of suitable subsequent pairs of trees is merged into a single tree. Selection of such suitable pairs, deterministic or stochastic, is the unique difference among $2\times 2$ cases (see Table 1). Its result can be encoded as a sequence $\Lambda$ of trees with the height $⩽1$. After this, the result of OneStep() procedure can be described as a function $f:t\mapsto \Lambda \circ t$, acting on the buffer t via the product defined in Section 2.2. Iteration of f over all steps and then a removal of the first tree from the buffer determines a function $F\left(t\right)$ describing transformation of the buffer during block generation. In Section 3.1, we consider a reduction of the above scheme, where only the number of leaves of each tree is taken into account. This is sufficient to study the throughput parameters of the blockchain(s). This reduction is possible due to the homomorphism of monoids described in Section 2.2.

In Section 4, we consider the case when behavior is deterministic. We prove that a sequence $(t,Ft,F^{2}t,\dots )$ of buffer states takes a finite number of values and, hence, this sequence and the sequence of published trees are ultimately periodic. In Section 4.1, deterministic generation of strict binary trees is considered. The sequences of buffer states and published blocks are ultimately periodic with a period of length 1. This follows from the fact that transformation of the buffer after each block publishing is a weak contraction with respect to the Hamming distance. Under some natural assumption the height of the tree published over the period is the sum of (the integer part of) the binary logarithm of the number of provers and of the number of steps. An explicit formula for the fixed point is obtained in terms of the product on infinite sequences of binary trees. In Section 4.2, deterministic generation of perfect binary trees is considered. It is observed that the period of the sequence of published trees consists of perfect trees of two heights $h_{max-1}$ and $h_{max}$. The total efficiency is independent of shapes of generated trees and can be expressed by an explicit formula and admits natural asymptotics. Explicit results are obtained in the cases of a singe prover of a single step.

In Section 5, we consider the case when behavior is stochastic. In Section 5.1, it is shown that the placement of provers into suitable positions at each stage can be described by the classical occupancy distribution. In the deterministic case, the total number of generated proofs is the product of numbers of published blocks, of steps in a block and of provers. In the stochastic case, we define the total efficiency (respectively the block publishing efficiency) as the total number of generated proofs (respectively the number of proofs embodied in published blocks) divided by the above product. Thus, both efficiencies are numbers in the interval $[0,1]$. They are convenient to compare the cases of various shapes and various values of integer parameters. The total efficiency is independent of shapes of generated trees and is expressed by an explicit formula and admits natural asymptotics. In Section 5.2, average values of the block publishing efficiency are calculated using a simulation model. We compare two cases when the shape of trees is binary strict or perfect. The maxima of these values as functions of numbers of positions are investigated. In Section 5.3 for generation of strict binary trees in a stochastic case we investigate an analog of the deterministic Formula (22) for heights of trees. Using the least squares method, we find the best approximation of the expected height of generated trees linear on the number of steps and logarithmic on the number of provers.

In Appendix A, we recall the concept of a non-symmetric operad and construction of the corresponding PRO. As the following step, one can obtain a monoid structure of infinite sequences of operations. The non-symmetric magma operad and the non-symmetric semi-group operad as its factor come from corresponding free objects with a single generator. The corresponding monoids of infinite sequences of strict binary trees and its factor-monoid given by taking the number of leaves of each tree are considered in Section 2.2.

In Appendix B, we describe the software implementation of our algorithms and explain how they are used in the main text.

2. Preliminaries: Binary Trees and Forests

2.1. Binary Trees and Free Magmas

Trees, as a part of Graph Theory, are used in mathematics ([22], Chapter 5) and computer science, (see the classical volume [23]). In this subsection, we give some necessary definitions related to various types of binary rooted trees and forests, as there is no precise description convenient for our purposes and there might exist a confusion in terminology.

Rooted trees can be defined either (1) recursively, or as (2) partially ordered sets, or as (3) special types of graphs. All of these points of view are useful in their respective contexts.

A tree is defined as a connected acyclic undirected graph. Choosing a vertex in a tree as a root determines the natural direction for all edges (towards the root). However, usually it is not shown explicitly.

A rooted tree is a directed graph with a distinguished vertex called the root such that there exists a unique path from each vertex to the root. Thus, the set of vertices is equipped with a natural partial order: $v⩽w$ if there exists a path from v to w. In addition, the rooted tree itself becomes the Hasse diagram for this partial order (being drawn root up). If $v\to w$ is an edge in a directed rooted tree, we say that v is a child of w, and w is a parent of v. A vertex that has no child is called a leaf. Let us denote as $htt$ the height of the tree t, i.e., the maximal length of the path from a leaf to the root. Thus, leaves are minimal elements, and the root is the greatest element in the corresponding partially ordered set.

Each tree can be embedded in the plane. For a rooted tree all such embeddings are classified by linear orderings for the children of each vertex. Thus, if all such orderings are fixed, we say they are an ordered rooted tree (or a plane rooted tree).

Here, we mainly consider strict binary plane rooted trees (Instead of the term “strict binary tree”, the terms “complete binary trees” and “full binary trees” are also used.), where “strict binary” means that every vertex is either a leaf or has exactly two children (left and right). In this case, for each non-leaf vertex, its left child vertex and its right child vertex are roots of maximal binary subtrees called, respectively, a left child tree and a right child tree.

Notation 1.

Let us denote as $n_v\left(t\right)$ the number of vertices, as $n_i\left(t\right)$ the number of internal vertices and as $n_{\ell }\left(t\right)$ the number of leaves in a rooted tree t.

In a strict binary tree t these numbers satisfy the identities

$$n_v\left(t\right)=n_i\left(t\right)+n_{\ell }\left(t\right),n_{\ell }\left(t\right)=n_i\left(t\right)+1.$$

(1)

A magma is a set equipped with a binary operation ★ without any additional properties Chapter 1 [23], ([24], 0.2). The free magma $\mathcal{M}$ with a single generator ∗ (up to isomorphism) is described recursively as

$$\mathcal{M}:=\coprod _{n=1}^{\infty }{\mathcal{M}}_n$$

of recursively described subsets:

$$\begin{array}{c}{\mathcal{M}}_1:=\{\ast \},{\mathcal{M}}_n:=\coprod _{m=1}^{n-1}\left\{\left(xy\right)\right|x\in {\mathcal{M}}_m\wedge y\in {\mathcal{M}}_{n-m}\}\mathrm{for}n>1.\end{array}$$

Thus, an element of ${\mathcal{M}}_{n+1}$ is a bracketing of a string of $n+1$ symbols ∗, i.e., the insertion of n left parentheses and n right parentheses defining the order of an n-fold application of the binary operation, e.g., five elements of ${\mathcal{M}}_4$ are presented in Figure 1a (with the outer brackets removed). Cardinality of ${\mathcal{M}}_{n+1}$ is counted by Catalan number $C_n:={\displaystyle \frac{1}{n+1}}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)$. Various kinds of objects that are counted using Catalan numbers are called Catalan families. The Stanley’s book [25] presents 214 Catalan families including various types of trees.

Strict binary trees are mentioned in Exercise 2.5 [25]. The generator of the free magma of strict binary trees is the zero height tree • whose single vertex is the root. For two binary trees $t_1,t_2$, the binary tree $t_1★t_2$ is a binary tree with a new root, whose left child tree is $t_1$ and the right child tree is $t_2$. Strict binary trees with four leaves corresponding to elements of ${\mathcal{M}}_4$ are presented in Figure 1c.

Non-strict binary trees (often in computer science literature just “binary trees”) obtain yet another example of Catalan family Exercise 2.4 [25]. Thus, they can be defined recursively in the same way as strict binary trees, with the only difference that their free magma generator is the empty tree. A non-empty non-strict binary tree can be represented by a plane rooted tree, where each vertex has 0, 1 or 2 children, but with additional structure, every single child must be labeled “left” or “right”. Such trees with three vertices corresponding to elements of ${\mathcal{M}}_4$ are presented in Figure 1b. Note that a non-strict binary tree is obtained from the corresponding strict binary by removing all its leaves.

2.2. Monoid of Sequences of Strict Binary Trees

Here, we consider composition $t\circ t^{\prime }$ of infinite sequences of strict binary trees given by the gluing of subsequent leaves in t with subsequent roots in $t^{\prime }$, and composition $\ell \circ {\ell }^{\prime }$ of infinite sequences of positive integers corresponding to the numbers of leaves in a tree.

First, for a strict binary tree t with n leaves and strict binary trees $t_1,\dots ,t_n$, we define the composition $t\circ (t_1,\dots ,t_n)$ obtained by gluing together the i-th leaf in t with the root of $t_i$ for $i=1,2,\dots n$.

This obtains the a non-symmetric operad structure on strict binary trees. Then one can apply the construction from Appendix A to obtain the monoidal structures described below. The details of the Appendix A are not necessary to understand the remainder of the material.

Let $\mathbb{T}={\mathbb{T}}_{\mathrm{strict}}$ be a set of sequences ${\left(t_i\right)}_{i⩾0}$ of strict binary trees with only a finite number of non-zero height trees, equipped with a binary operation $(t,t^{\prime })\mapsto t\circ t^{\prime }$, where

$${(t\circ t^{\prime })}_i=t_i\circ \left(t_{n_{\ell }\left(t_0\right)+\cdots +n_{\ell }\left(t_{i-1}\right)}^{\prime },t_{n_{\ell }\left(t_0\right)+\cdots +n_{\ell }\left(t_{i-1}\right)+1}^{\prime },\dots ,t_{n_{\ell }\left(t_0\right)+\cdots +n_{\ell }\left(t_i\right)-1}^{\prime }\right),$$

(2)

i.e., each $t_i$ is successively applied in the sense of (A1) to the first not yet used $n_{\ell }\left(t_i\right)$ elements of $t^{\prime }$.

Let $\mathbb{L}={\mathbb{L}}_{\mathrm{strict}}$ be a set of sequences ${\left({\ell }_i\right)}_{i⩾0}$ of positive integers with only a finite number of elements $>1$, equipped with a binary operation $(\ell ,{\ell }^{\prime })\mapsto \ell \circ {\ell }^{\prime }$, where

$${(\ell \circ {\ell }^{\prime })}_i={\ell }_{{\ell }_0+\cdots +{\ell }_{i-1}}^{\prime }+{\ell }_{{\ell }_0+\cdots +{\ell }_{i-1}+1}^{\prime }+\cdots +{\ell }_{{\ell }_0+\cdots +{\ell }_i-1}^{\prime },$$

(3)

i.e., successively each $(t\circ t^{\prime })$ is the sum of the first not yet used ${\ell }_i$ elements of ${\ell }^{\prime }$.

Corollary 1.

The above binary operations turn both $\mathbb{T}$ and $\mathbb{L}$ into monoids. The units are $t^{\left(0\right)}={(•)}_{i⩾0}\in \mathbb{T}$ and ${\ell }^{\left(0\right)}={\left(1\right)}_{i⩾0}\in \mathbb{L}$. The map $\mathbb{T}\to \mathbb{L}$, ${\left(t_i\right)}_{i⩾0}\mapsto \left(n_{\ell }(t_i\right){)}_{i⩾0}$ is a morphism of monoids.

2.3. Perfect Binary Trees and Forests

A rooted tree is called perfect (“complete” by some authors) if all leaves are of the same distance to the root (that equals to the height h of the tree).

Notation 2.

For each non-negative integer h, the unique perfect binary tree of height h is denoted as $t_h^{★}$.

The perfect binary tree $t_h^{★}$ has $2^h$ leaves; moreover, $2^d$ vertices are on the distance d from the root (they can be subsequently indexed with $0⩽j<2^d$, whose binary string representation has length d), and $2^{h+1}-1$ vertices in total. See Figure 2.

Note that a non-strict binary tree can be obtained from the corresponding strict binary tree by removing all its leaves.

All perfect binary trees are built recursively using magma square:

$$t_0^{★}=•,t_{h+1}^{★}=t_h^{★}★t_h^{★}.$$

Perfect binary trees are most convenient to store a maximal number of leaves (that correspond to transactions).

A forest (respectively plane forest) f is a co-product (disconnected disjoint union) of a family of trees (respectively plane trees) ${\left(t_i\right)}_{i\in I}$. In both cases, the set of components I is unordered.

Let us recall that a subset $I\subseteq P$ in a poset P is called a down-set (respectively up-set) if, for each $x\in I$ and $y\in P$ with $y⩽x$ (respectively $y⩾x$), we have $y\in I$. Note that a subset $I\subseteq P$ is a down-set if its complement $P\backslash I$ is an up-set.

Lemma 1.

For a finite sequence $f={\left(t_i\right)}_{0⩽i<p}$ of strict binary trees, the following conditions are equivalent:

1.

There exists a bracketing, i.e., an element of the free magma ${\mathcal{M}}_p$, such that, after the corresponding application of $p-1$ magma operations ★, a perfect binary tree $t^{★}\left(f\right)$ is obtained;

2.

${\left(t_i\right)}_{0⩽i<p}$ is a down-set of some perfect binary tree containing all its leaves with components ordered from left to right;

3.

(a) Each tree $t_i$ in the family is perfect,

(b) For each i, $n_{\ell }\left(t_i\right)$ divides ${\sum }_{j=0}^{j=i-1}{n}_{\ell }\left(j\right)$;

(c) The total sum ${\sum }_{j=0}^{j=p-1}{n}_{\ell }\left(j\right)$ is an power of 2.

Proof. 

$1\iff 2$: For a down-set in the perfect binary tree containing all its leaves, its complement is the non-strict binary tree corresponding to the appropriate bracketing.

$1\Rightarrow 3$: (a) and (c) are obvious; to prove (b), let $t^{\prime }$ be a subtree of height $h^{\prime }$ in a perfect tree t of height h such that each leaf in $t^{\prime }$ is a leaf in t. Then, there exists a subforest in t that consists of $2^{h-h^{\prime }}$ perfect trees of height h including $t^{\prime }$.

$3\Rightarrow 2$: Split the leaves of f into equal left and right halves. If there is a tree $t_i$ in our forest whose leaves are in both halves, then, from 3(c), we conclude that the forest consists of this unique tree. Otherwise, we can represent $f=f_{\ell }\bigsqcup f_r$ as a co-product of two forests satisfying condition 3, so we suppose $t^{★}\left(f\right)=t^{★}\left(f_{\ell }\right)★t^{★}\left(f_r\right)$ and repeat the above choice for $f_{\ell }$ and $f_r$.  □

Definition 1.

A finite sequence ${\left(t_i\right)}_{0⩽i<p}$ of binary trees satisfying conditions of the above lemma is called a perfect binary forest.

Figure 3 shows an example of a perfect binary forest and the corresponding perfect binary tree $t_4^{★}=(t_2^{★}★(t_1^{★}★(t_0^{★}★t_0^{★})))★(t_2^{★}★((t_0^{★}★t_0^{★})★t_1^{★}))$.

In what follows, we use (potentially) infinite sequences of proof trees ${\left(t_i\right)}_{i⩾0}$ with only a finite number of non-zero height trees as a buffer of proofs.

Definition 2.

An infinite sequences of binary trees ${\left(t_i\right)}_{i⩾0}$ with only a finite number of non-zero height trees is called perfect if some its initial fragment ${\left(t_i\right)}_{0⩽i<p}$, containing all non-zero height trees, is perfect.

Proposition 1.

A sequence $t\in \mathbb{T}$ is perfect if there exists $t^{\prime }\in \mathbb{T}$ such that $t^{\prime }\circ t$ is a sequence that consists of a single perfect tree followed by zero-height trees.

Definition 3.

A pair $(t_i,t_{i+1})$ of subsequent trees in a perfect sequence is called a perfect, if the new sequence with the pair $(t_i,t_{i+1})$ replaced with the product $t_i★t_{i+1}$ remains perfect.

Note that the binary operation between two strict binary trees can be written as $t★t^{\prime }=\wedge \circ (t,t^{\prime })$, where ∧ is the strict binary tree of the height 1. Thus, to replace $(t_i,t_{i+1})$ with the product $t_i★t_{i+1}$ is the same as to take the composition ${\wedge }_i\circ t$ in the sense of (2), where ${\wedge }_i:=(\underset{i}{\underbrace{•,\dots ,•}},\wedge ,\underset{\infty }{\underbrace{•,\dots }})$.

According to Lemma 1 a pair $(t_i,t_{i+1})$ is perfect if $n_{\ell }\left(t_i\right)=n_{\ell }\left(t_{i+1}\right)$ and $2n_{\ell }\left(t_i\right)$ divides ${\sum }_{j=0}^{j=i-1}{n}_{\ell }\left(j\right)$.

Equivalently, suppose that the vertices of the whole perfect tree are labeled as in Figure 2. A pair $(t_i,t_{i+1})$ of neighboring trees in its down-set is perfect if their roots are labeled by strings ’$w0$’ and ’$w1$’ respectively for some $w\in {\{0,1\}}^{*}$.

Obviously, two different perfect pairs cannot intersect. Thus, perfect pairs in a perfect sequence form an infinite sequence.

3. The General Scheme

A special feature of Algorithm 1 considered in this paper is a simultaneous construction of several trees forming a linear ordered forest, rather than a single tree. Periodically, the leftmost tree is included into the published block, and the remainder are considered as a buffer for further block generation.

Algorithm 1: The general scheme of blocks generation

Input parameters are:

• Dichotomous $b_{\mathrm{behavior}}$ regulates behavior of provers, deterministic (mutually consistent) or stochastic (independent);
• Dichotomous $b_{\mathrm{shape}}$ describes the shape of generated trees, only perfect binary trees or arbitrary strict binary trees;
• $n_{\mathrm{bl}}$ is the number of blocks published during the epoch;
• $n_{\mathrm{st}}$ is the number of steps for one block generation;
• $n_{\mathrm{pr}}$ is the number of provers;
• $n_{\mathrm{pos}}$ is the number of positions allocated for proof.

During the work of the algorithm, a potentially infinite sequence of binary trees $t={\left(t_i\right)}_{i⩾0}$ arises that we call a buffer. It describes the state of the system and is used in the further block generation.

The output is the sequence $t^{\copyright }={\left(t_i^{\copyright }\right)}_{0⩽i<n_{\mathrm{bl}}}$ of binary trees included into published blocks (one tree per block).

The published list is initialized with the empty list $t^{\copyright }\leftarrow \left(\right)$. Theoretically, we assume that at the beginning $t={(•)}_{i⩾0}$ is a potentially infinite sequence of zero height trees. In practice, we initialize t with an empty list and put zero-height trees there as needed.

Remark 1.

In a specific implementation, instead of two lists of binary trees, one can work with a single list, and an integer pointer p; trees with indexes $i<p$ are considered as published, and trees with indexes $i⩾p$ form a buffer. Block publishing in these terms is just an increment of the pointer $p\leftarrow p+1$.

The external for-loop of Algorithm 1 runs over all $n_{\mathrm{bl}}$ blocks in the epoch. The body of this loop consists of the internal for-loop that runs over $n_{\mathrm{st}}$ steps in the block and the block publishing directives. The body of the internal loop consists of Procedure OneStep$(b_{\mathrm{behavior}},b_{\mathrm{shape}},n_{\mathrm{pr}},n_{\mathrm{pos}})$.

Procedure OneStep(bbehavior, bshape, npr, npos)

This procedure presents the general scheme for $2\times 2$ different cases corresponding to combinations of two dichotomous parameters $b_{\mathrm{behavior}}$ and $b_{\mathrm{shape}}$. It acts on the buffer: some subsequent pairs of trees $(t_k,t_{k+1})$ are replaced with their magma product $t_k★t_{k+1}$, and these pairs essentially depend on dichotomous parameters $b_{\mathrm{behavior}}$ and $b_{\mathrm{shape}}$.

In the case “$b_{\mathrm{behavior}}$ is deterministic”, the number of such pairs coincides with the number of provers $n_{\mathrm{pr}}$; then, for the case that “$b_{\mathrm{shape}}$ is strict”, these pairs are first $n_{\mathrm{pr}}$ subsequent pairs of the trees in the buffer: $\{(t_0,t_1),(t_2,t_3),\dots (t_{2n_{\mathrm{pr}}-2},t_{2n_{\mathrm{pr}}-1})\}$; for the case that $b_{\mathrm{shape}}$ is perfect, we use first $n_{\mathrm{pr}}$ perfect pairs in the buffer. In the case “$b_{\mathrm{behavior}}$ is stochastic”, first $n_{\mathrm{pos}}$ subsequent/perfect positions are reserved for the random choice. Each prover independently with equal probability selects one of these positions. For positions selected by at least one prover, the corresponding pair of trees is replaced with its magma product.

For fixed input parameters $b_{\mathrm{behavior}}$, $b_{\mathrm{shape}}$, $n_{\mathrm{st}}$, $n_{\mathrm{pr}}$, $n_{\mathrm{pos}}$, the following functions (deterministic or random) together with their domains and codomains are defined. Let us denote

• $T=T_{b_{\mathrm{shape}}}$ the set of $b_{\mathrm{shape}}$ (i.e., strict/perfect) binary trees;
• $\mathbb{T}={\mathbb{T}}_{b_{\mathrm{shape}}}$ the set of sequences $t={\left(t_i\right)}_{i⩾0}$ of $b_{\mathrm{shape}}$ binary trees with finitely many non-zero height trees;
• $t^{\left[\right]}$ be the sequence obtained by the shift, i.e., $t_i^{\left[\right]}=t_{i+1}$ for $i⩾0$.

  $$\begin{array}{c}f=f_{b_{\mathrm{behavior}},b_{\mathrm{shape}},n_{\mathrm{pr}},n_{\mathrm{pos}}}:\mathbb{T}\to \mathbb{T},t\mapsto \Lambda \circ t,\end{array}$$

  (4)

  $$\begin{array}{c}F=F_{b_{\mathrm{behavior}},b_{\mathrm{shape}},n_{\mathrm{st}},n_{\mathrm{pr}},n_{\mathrm{pos}}}:\mathbb{T}\to \mathbb{T},t\mapsto {\left(f^{n_{\mathrm{st}}}\left(t\right)\right)}^{\left[\right]},\end{array}$$

  (5)

  $$\begin{array}{c}\pi ={\pi }_{b_{\mathrm{behavior}},b_{\mathrm{shape}},n_{\mathrm{st}},n_{\mathrm{pr}},n_{\mathrm{pos}}}:\mathbb{T}\to T,t\mapsto {\left(f^{n_{\mathrm{st}}}\left(t\right)\right)}_0.\end{array}$$

  (6)

Here, the function (4) is determined by Procedure OneStep. It can be described as a product (2) with the sequence $\Lambda ={\Lambda }_{b_{\mathrm{behavior}},b_{\mathrm{shape}},n_{\mathrm{pr}},n_{\mathrm{pos}}}\in \mathbb{T}$ of trees of height $⩽1$. The internal for-loop of Algorithm 1 means the $n_{\mathrm{st}}$-th iteration of this function. Then, block publishing determines the map (6), and the state of the buffer after each block publishing is changed according to the map (5).

Table 1. The scheme of $2\times 2$ algorithms.

	Strict binary trees: merged positions are first pairs of subsequent trees	Perfect binary trees: merged positions are first so-called perfect pairs
Deterministic prover behavior: provers act mutually consistent, taking the first possible $n_{\mathrm{pr}}$ merge positions	$b_{\mathrm{behavior}}$ is deterministic $b_{\mathrm{shape}}$ is strict	$b_{\mathrm{behavior}}$ is deterministic $b_{\mathrm{shape}}$ is perfect
Stochastic prover behavior: provers act independently, with each selecting one of $n_{\mathrm{pos}}$ merge positions	$b_{\mathrm{behavior}}$ is stochastic $b_{\mathrm{shape}}$ is strict	$b_{\mathrm{behavior}}$ is stochastic $b_{\mathrm{shape}}$ is perfect

shows the whole scheme. This four cases are also implemented in software described in Appendix B.

The Algorithm in Terms of Numbers of Leaves

Let us recall that a perfect tree is completely determined by its height, but there are $C_n$ strict binary trees with $n+1$ leaves. However, the exact shape of trees is not important for the blockchain(’s) throughput parameters’ study. Thus, we can collect information about the number of leaves (and, therefore, (1) about the number of vertices) and optionally about heights of trees. Thus, instead of the sequence of trees $t={\left(t_i\right)}_{i⩾0}$, one can consider the sequence of integers $\ell ={\left({\ell }_i\right)}_{i⩾0}$, where ${\ell }_i=n_{\ell }\left(t_i\right)$ is the number of leaves of the corresponding tree. The initial state is described as ${({\ell }_i=1)}_{i⩾0}$. The magma operation ★ on strict trees corresponds to addition of the numbers of leaves: $n_{\ell }(t_i★t_{i+1})=n_{\ell }\left(t_i\right)+n_{\ell }\left(t_{i+1}\right)$.

A pair of numbers $({\ell }_j,{\ell }_{j+1})$ in a perfect sequence ${\left({\ell }_i\right)}_{i⩾0}$ is perfect (i.e., corresponds to the perfect pair of trees) if

$${\ell }_j={\ell }_{j+1}\mathrm{and}2{\ell }_j\mathrm{divides}\sum _{i=0}^{j-1}{\ell }_i.$$

(7)

If, moreover, the sequence ${\left({\ell }_i\right)}_{i⩾0}$ is non-increasing, the condition (7) takes the equivalent form

$${\ell }_j={\ell }_{j+1}\mathrm{and}\#\left\{i\right|0⩽i<j\wedge {\ell }_i={\ell }_j\}\mathrm{is}\mathrm{even}.$$

(8)

Let us denote by $\mathbb{L}={\mathbb{L}}_{b_{\mathrm{shape}}}$ a set of sequences ${\left({\ell }_i\right)}_{i⩾0}$ of positive integers with only a finite number of elements $>1$, in the case that $b_{\mathrm{shape}}$ is perfect. For a version of Algorithm 1 in terms of numbers of leaves, one considers the functions corresponding to (4)–(6). We keep the same names for the functions. Different (co)domains avoid ambiguity:

$$\begin{array}{c}f:\mathbb{L}\to \mathbb{L},\ell \mapsto \lambda \circ \ell ,\end{array}$$

(9)

$$\begin{array}{c}F:\mathbb{L}\to \mathbb{L},\ell \mapsto {\left(f^{n_{\mathrm{st}}}(\ell )\right)}^{\left[\right]},\end{array}$$

(10)

$$\begin{array}{c}\pi :\mathbb{L}\to {\mathbb{Z}}_{>0},t\mapsto {\left(f^{n_{\mathrm{st}}}(\ell )\right)}_0,\end{array}$$

(11)

where in (9), $\lambda ={\lambda }_{b_{\mathrm{behavior}},b_{\mathrm{shape}},n_{\mathrm{pr}},n_{\mathrm{pos}}}\in \mathbb{L}$ is the sequence of 1 or 2.

Functionality of the transition from trees to their numbers of leaves is expressed by the commutative squares

Here, $n_{\ell }:\mathbb{T}\to \mathbb{L}$ means ${\left(t_i\right)}_{i⩾0}\mapsto {\left(n_{\ell }\left(t_i\right)\right)}_{i⩾0}$.

Let us define the sequences of sequences (of elements of $\mathbb{L}$) as

$$\begin{array}{c}{\ell }^{(n,k)}:=f^k\left(F^n\left({\left(1\right)}_{i⩾0}\right)\right),n⩾0,0⩽k⩽n_{\mathrm{pr}},\end{array}$$

(12)

$$\begin{array}{c}{\ell }^{\left(n\right)}:={\ell }^{(n,0)}=F^n\left({\left(1\right)}_{i⩾0}\right),n⩾0.\end{array}$$

(13)

Elements of the double sequence $\left({\ell }^{(n,k)}\right)$ are naturally linearly ordered, lexicographically on the pairs $(n,k)$. In this sequence,

$${\ell }^{(n,k+1)}=f\left({\ell }^{(n,k)}\right),{\ell }^{(n+1,0)}={\ell }^{(n,n_{\mathrm{st}})\left[\right]}.$$

The length of the sequence $\ell ={\left({\ell }_i\right)}_{i⩾0}\in L$ is defined as follows:

$$Len\ell :=\underset{j}{min}\{j⩾0|\forall i⩾j:{\ell }_i=1\}.$$

(14)

4. Deterministic Case

In this section, we consider only the case of Algorithm 1 when $b_{\mathrm{behavior}}$ is deterministic. We consider sequences ${\ell }^{(n,k)}$ for an arbitrary n that corresponds to the limiting case $n_{\mathrm{bl}}\to \infty$ of an infinite outer for-loop. One can also consider the infinite sequence $\widehat{\ell }$ of the number of leaves of published trees with elements

$${\ell }_n^{\copyright }=\pi \left({\ell }^{\left(n\right)}\right),n⩾0.$$

Lemma 2.

In the case, $b_{\mathit{behavior}}$ is deterministic, and the function $f:\mathbb{L}\to \mathbb{L}$ preserves a property of a sequence to be non-increasing.

Proof. 

In the case $b_{\mathrm{shape}}$ is perfect, take into account (8). □

Corollary 2.

In the case that $b_{\mathit{behavior}}$ is deterministic, the sequences ${\ell }^{(n,k)}$ from (12) are non-increasing for all $n⩾0$ and $0⩽k⩽n_{\mathrm{pr}}$.

Let us denote as $\mathbb{L}{}^{{}^{\searrow }}$ a set of non-increasing sequences from $\mathbb{L}$.

For a non-increasing sequence $\ell \in \mathbb{L}$ (e.g., for all ${\ell }^{(n,k)}$ when $b_{\mathrm{behavior}}$ is deterministic), the Formula (14) can be simplified:

$$Len\ell =\underset{j}{min}\{j⩾0|{\ell }_j=1\}.$$

For $\ell \in \mathbb{L}$, the sum

$$N_i(\ell ):=\sum _j({\ell }_j-1)$$

(15)

has only finite non-zero summands and, according to (1), can be interpreted as the total numbers of internal vertices. Independently on $b_{\mathrm{shape}}$, for $\ell \in \mathbb{L}$, we have the identities

$$N_i\left(f(\ell )\right)=N_i(\ell )+n_{\mathrm{pr}}.$$

$$\pi (\ell )-1+N_i\left(F(\ell )\right)=N_i(\ell )+n_{\mathrm{st}}{n}_{\mathrm{pr}}.$$

(16)

Lemma 3.

In the case “$b_{\mathit{behavior}}$ is deterministic”, for fixed $n_{\mathit{st}}$, $n_{\mathit{pr}}$ the total number of internal vertices (and, hence, the length and all elements) of all ${\ell }^{(n,k)}$ are bounded together, i.e.,:

$$\underset{n,k}{sup}{N}_i\left({\ell }^{(n,k)}\right)<\infty ,\underset{n,k}{sup}Len{\ell }^{(n,k)}<\infty ,\underset{n,k,j}{sup}{\ell }_j^{(n,k)}<\infty .$$

Proof. 

In the case “$b_{\mathrm{shape}}$ is strict”, $Len{\ell }^{(n,k)}⩽n_{\mathrm{pr}}$ and $Len{\ell }^{\left(n\right)}<n_{\mathrm{pr}}$. This follows from the observation that $Len\ell ⩽2n_{\mathrm{pr}}$ implies $Lenf(\ell )⩽n_{\mathrm{pr}}$.

In the case that “$b_{\mathrm{shape}}$ is perfect”, the number of the same non-zero height trees in the buffer is bounded by $n_{\mathrm{pr}}+1$. See (27) for more accurate estimates.

Then, we can estimate from above the total number of internal vertices:

$$N_i({\ell }^{\left(n\right)})⩽C_{b_{\mathrm{shape}}}({\ell }_0^{\left(n\right)})=\left\{\begin{array}{cc}(n_{\mathrm{pr}}-1)({\ell }_0^{\left(n\right)}-1),\hfill & \mathrm{if} b_{\mathrm{shape}}\mathrm{is} \mathrm{strict},\hfill \\ (n_{\mathrm{pr}}+1)(2{\ell }_0^{\left(n\right)}-{log}_2{\ell }_0^{\left(n\right)}-1),\hfill & \mathrm{if} b_{\mathrm{shape}}\mathrm{is} \mathrm{perfect}.\hfill \end{array}\right.$$

In the second case, we use the fact that all ${\ell }_j^{\left(n\right)}$ are powers of 2. For ${\ell }_0^{\left(n\right)}>1$ and $n_{\mathrm{pr}}>1$, the function $C_{b_{\mathrm{shape}}}$ is monotone increasing and, hence, invertible. Let $N_i\left({\ell }^{\left(n\right)}\right)⩾C_{b_{\mathrm{shape}}}(n_{\mathrm{st}}{n}_{\mathrm{pr}}+1)$. Then, $\pi \left({\ell }^{\left(n\right)}\right)⩾{\ell }_0^{\left(n\right)}⩾n_{\mathrm{st}}{n}_{\mathrm{pr}}+1$ and, by (16), we have $N_i\left(F(\ell )\right)⩽N_i(\ell )$. Thus, ${sup}_{n,k}{N}_i\left({\ell }^{(n,k)}\right)<C_{b_{\mathrm{shape}}}(n_{\mathrm{st}}{n}_{\mathrm{pr}}+1)+n_{\mathrm{st}}{n}_{\mathrm{pr}}$. □

Definition 4.

The sequence $x={\left(x_i\right)}_{i\in {\mathbb{Z}}_{⩾-1}}$ is called ultimately periodic if there exists $r\in {\mathbb{Z}}_{⩾0}$ and $s\in {\mathbb{Z}}_{>0}$ such that, if $i>r$, then $x_i=x_{i+s}$. In this case, we write

$$x=\underset{\mathit{preperiod}}{\underbrace{x_0,\dots ,x_r}},(\underset{\mathit{period}}{\underbrace{x_{r+1},\dots ,x_{r+s}}}).$$

The minimal preperiod is the minimal r satisfying the above condition. The minimal period is the minimal s for minimal r satisfying the above condition.

Given a function $g:X\to X$ and an element $x_0\in X$, the sequence $x_0,g\left(x_0\right),g\left(g\left(x_0\right)\right),\dots$ is ultimately periodic, whenever X is finite. Lemma 3 implies that the set $\left\{{\ell }^{\left(n\right)}|n⩾0\right\}$ is finite.

Corollary 3.

In the case that "$b_{\mathit{behavior}}$ is deterministic", the sequences ${\left({\ell }^{\left(n\right)}\right)}_{n⩾0}$ of buffer states and ${\ell }^{\copyright }$ of published trees are ultimately periodic.

Lemma 4.

If $({\ell }^{(r+1)},\dots ,{\ell }^{(r+s)})$ is a period of ${\left({\ell }^{\left(n\right)}\right)}_{}$, then

$${\ell }_{r+1}^{\copyright }+\cdots +{\ell }_{r+s}^{\copyright }-s=s{n}_{\mathit{st}}{n}_{\mathit{pr}}.$$

(17)

Proof. 

The identity (17) is the result of the summing of (16) over a period, i.e., for $\ell ={\ell }^{(r+1)},\dots ,{\ell }^{(r+s)}$. □

4.1. Generation of Strict Binary Trees

In this subsection, we consider the case “$b_{\mathrm{behavior}}$ is deterministic” and “$b_{\mathrm{shape}}$ is strict”. In this case, one-step functions (4) and (9) are

$$\begin{array}{c}t\mapsto \Lambda \circ t,\Lambda =n_{\mathrm{pr}}\wedge =(\underset{n_{\mathrm{pr}}}{\underbrace{\wedge ,\dots ,\wedge }},\underset{\infty }{\underbrace{•,\dots }}),\\ \ell \mapsto \lambda \circ \ell ,\lambda =n_{\mathrm{pr}}·\mathbf{2}=(\underset{n_{\mathrm{pr}}}{\underbrace{2,\dots ,2}},\underset{\infty }{\underbrace{1,\dots }}).\end{array}$$

Lemma 5.

$$t^{(0,k)}={(n_{\mathit{pr}}\wedge )}^{\circ k},t^{(n,k)}={(n_{\mathit{pr}}\wedge )}^{\circ k}\circ t^{\left(n\right)}.$$

(18)

$${\ell }^{(0,k)}={(n_{\mathit{pr}}·\mathbf{2})}^{\circ k},{\ell }^{(n,k)}={(n_{\mathit{pr}}·\mathbf{2})}^{\circ k}\circ {\ell }^{\left(n\right)}.$$

(19)

Let us consider the Hamming distance for $\ell ,{\ell }^{\prime }\in \mathbb{L}{}^{{}^{\searrow }}$:

$$d_H(\ell ,{\ell }^{\prime }):=\#\left\{i\right|{\ell }_i\ne {\ell }_i^{\prime }\}.$$

Lemma 6.

In the case that "$b_{\mathit{behavior}}$ is deterministic and $b_{\mathit{shape}}$ is strict", the transformation F is a weak contraction on $(\mathbb{L}{}^{{}^{\searrow }},d_H)$:

$$d_H(F(\ell ),F\left({\ell }^{\prime }\right))<d_H(\ell ,{\ell }^{\prime }),\ell \ne {\ell }^{\prime }\in \mathbb{L}{}^{{}^{\searrow }}.$$

Corollary 4.

The sequence of buffer states ${\left({\ell }^{\left(n\right)}\right)}_{n⩾0}$ is stabilized at the fixed point of F. Thus, this sequence and the sequence of published blocks are ultimately periodic with a period of length 1. The tree published in the period has $n_{\mathit{pr}}{n}_{\mathit{st}}+1$ leaves.

The following lemma shows that, if $n_{\mathrm{st}}⩾{log}_2(n_{\mathrm{pr}}-1)$, then the length of pre-period $⩽1$.

Lemma 7.

If $n_{\mathit{st}}⩾{log}_2(n_{\mathit{pr}}-1)$, then

$$t^{\left(n\right)}={\left({(n_{\mathit{pr}}\wedge )}^{\circ n_{\mathit{st}}}\right)}^{\left[\right]},t_n^{\copyright }={\left({(n_{\mathit{pr}}\wedge )}^{\circ n_{\mathit{st}}}\circ {\left({(n_{\mathit{pr}}\wedge )}^{\circ n_{\mathit{st}}}\right)}^{\left[\right]}\right)}_0,n⩾1.$$

(20)

If $n_{\mathit{st}}⩾{log}_2\left(n_{\mathit{pr}}\right)$, then

$${\left({(n_{\mathit{pr}}\wedge )}^{\circ n_{\mathit{st}}}\right)}^{\left[\right]}={\left({(n_{\mathit{pr}}\wedge )}^{\circ \lceil {log}_2{n}_{\mathit{pr}}\rceil }\right)}^{\left[\right]}.$$

(21)

Proof. 

In both cases, we use the observation: for $t,t^{\prime }\in \mathbb{T}$, if $n_{\ell }\left(t_0\right)⩾Len{t}^{\prime }$, then ${(t\circ t^{\prime })}^{\left[\right]}=t^{\left[\right]}$. □

Thus, if $n_{\mathrm{st}}⩾{log}_2\left(n_{\mathrm{pr}}\right)$, then the period of the sequence of published trees consists of a single tree ${\left({(n_{\mathrm{pr}}\wedge )}^{\circ n_{\mathrm{st}}}\circ {\left({(n_{\mathrm{pr}}\wedge )}^{\circ \lceil {log}_2{n}_{\mathrm{pr}}\rceil }\right)}^{\left[\right]}\right)}_0$. According to (17), this is a tree with $n_{\mathrm{st}}{n}_{\mathrm{pr}}+1$ leaves.

Proposition 2.

For $n_{\mathit{st}}⩾{log}_2{n}_{\mathit{pr}}$, the height of the tree published in the period is the following

$$ht{\left({(n_{\mathit{pr}}\wedge )}^{\circ n_{\mathit{st}}}\circ {\left({(n_{\mathit{pr}}\wedge )}^{\circ \lceil {log}_2{n}_{\mathit{pr}}\rceil }\right)}^{\left[\right]}\right)}_0=\lfloor {log}_2{n}_{\mathit{pr}}\rfloor +n_{\mathit{st}}.$$

(22)

Proof. 

Both parts of (22) equal to $ht{\left({(n_{\mathrm{pr}}\wedge )}^{\circ n_{\mathrm{st}}}\right)}_0+ht{\left({(n_{\mathrm{pr}}\wedge )}^{\circ \lceil {log}_2{n}_{\mathrm{pr}}\rceil }\right)}_1$. □

Example 1.

Let $n_{\mathit{pr}}=2^m$ and $n_{\mathit{st}}⩾m$; then, the period of the buffers consists of the single sequence (21) of perfect trees

$${\left({(2^m\wedge )}^{\circ m}\right)}^{\left[\right]}=(t_m^{★},t_{m-1}^{★},t_{m-1}^{★},\dots ,\underset{2^{m-1}}{\underbrace{t_1^{★},\dots ,t_1^{★}}},t_0^{★}\dots )).$$

Let us consider a semi-infinite matrix, where rows are given by (21) for $n_{\mathrm{pr}}⩾1$, and the corresponding matrix, where each tree is replaced by the number of its leaves. Elements ${\left({(n\wedge )}^{\circ \lceil {log}_{2}n\rceil }\right)}_0=t_{\lceil {log}_{2}n\rceil }^{★}$ are removed after the shift. The matrix is lower triangular in the sense that ${\left({(n\wedge )}^{\circ \lceil {log}_{2}n\rceil }\right)}_m=•$ for $m⩾n⩾1$.

Proposition 3.

Let us denote $f_{k,p}=\left(p·\wedge ,(2^k-p)·•\right)$ the sequence of trees of length $2^k$ for $0⩽p⩽2^k$.

1.

For each $m⩾1$, the following sequence can be presented as the concatenation

$${\left({\left({(n\wedge )}^{\circ \lceil {log}_{2}n\rceil }\right)}_m\right)}_{n>m}=\underset{k=1}{\overset{\infty }{⨁}}\left(2^{k-1}(m-1)t_k^{★},t_k^{★}\circ f_{k,1},t_k^{★}\circ f_{k,2},\dots ,t_k^{★}\circ f_{k,2^k}\right).$$

(23)

2.

For $n⩾m⩾1$,

$${\left({(n\wedge )}^{\circ \lceil {log}_{2}n\rceil }\right)}_m=\left\{\begin{array}{cc}{t}_k^{★}\circ f_{k,n-2^{k}m},\hfill & if⌈{log}_2\frac{n}{m+1}⌉=⌊{log}_2\frac{n}{m}⌋=k,\hfill \\ t_k^{★},\hfill & if⌈{log}_2\frac{n}{m}⌉=⌊{log}_2\frac{n}{m+1}⌋+1=k.\hfill \end{array}\right.$$

Proof. 

For each $m⩾1$, the sequence (23) is the concatenation over all positive integers k of sequences consisting of $2^{k-1}(m-1)$ copies of $t_k^{★}$ and then compositions $t_k^{★}\circ (p\wedge )$ for p from 1 to $2^k$. (Note that $t_k^{★}\circ (2^k\wedge )=t_{k+1}^{★}$.) The tree $t_k^{★}$ appears in the positions $2^{k-1}(m+1)⩽n⩽2^{k}m$, or, equivalently, $\frac{n}{m}⩽2^k⩽\frac{2n}{m+1}$. The tree $t_k^{★}\circ (p\wedge )$ appears in the position $2^{k}m<n=p+2^{k}m⩽2^k(m+1)$, or, equivalently, $\frac{n}{m+1}⩽2^k<\frac{n}{m}$. □

Corollary 5.

For each $m⩾1$,

$${\left({\left({(n·\mathbf{2})}^{\circ \lceil {log}_{2}n\rceil }\right)}_m\right)}_{n⩾m}=(1,\underset{m}{\underbrace{2,\dots ,2}},3,\dots ,2^{k+1}-1,\underset{2^k(m-1)+1}{\underbrace{2^{k+1},\dots ,2^{k+1}}},2^{k+1}+1,\dots )$$

(24)

is a sequence of positive integers with inserted additional $(m-1)·2^k$ copies of $2^{k+1}$ for each $k⩾0$.

4.2. Generation of Perfect Binary Trees

Let us recall that the perfect tree is completely determined by its height. Thus, in this subsection, we consider the sequences $h={\left(h_i\right)}_{i⩾0}$ of heights of perfect trees instead of perfect trees itself: $t={\left(t_{h_i}^{*}\right)}_{i⩾0}$. Buffer states and published trees are characterized by the sequences of heights $h^{(n,k)}$ and $h^{\copyright }$ with $t_i^{(n,k)}=t_{h_i^{(n,k)}}^{★}$ and $t_i^{\copyright }=t_{h_i^{\copyright }}^{★}$.

According to Lemma 2, at each moment, the sequence of heights of perfect trees in the buffer is non-increasing. By Lemma 3, the heights of trees are bounded by the constant $h_{max}$, the same for all buffer states.

Let ${\mu }_h={\mu }_h^{(n,k)}$ be the number of perfect trees in the buffer of positive height h, i.e., the buffer at each step has the form

$$h^{(n,k)}=\left(h_{max}^{\times {\mu }_{h_{max}}},{(h_{max}-1)}^{\times {\mu }_{h_{max}-1}},\dots ,1^{\times {\mu }_1},0^{\times \infty }\right),$$

(25)

where $h_i^{\times \mu }:=\underset{\mu }{\underbrace{h_i,\dots ,h_i}}$.

The following Lemma describes these parameters for a fixed number of provers $n_{\mathrm{pr}}$ and number of steps $n_{\mathrm{st}}$.

Lemma 8.

At every step,

$$\begin{array}{c}{\mu }_h⩽\frac{n_{\mathit{pr}}-1}{2^{h-1}}+2,1⩽h⩽h_{max};\end{array}$$

(26)

$$\begin{array}{c}\sum _{h=1}^{h_{max}}⌊\frac{{\mu }_h}{2}⌋⩽n_{\mathit{pr}}.\end{array}$$

(27)

The map f corresponding to one step is given by the formula

$${\mu }_h^{(n,k+1)}=2\left\{{\mu }_h^{(n,k)}/2\right\}+\left\{\begin{array}{cc}⌊{\mu }_{h-1}^{(n,k)}/2⌋,\hfill & if h>1,\hfill \\ n_{\mathrm{pr}}-\sum _{h^{\prime }}⌊{\mu }_{h^{\prime }}^{(n,k)}/2⌋,\hfill & if h=1.\hfill \end{array}\right.$$

(28)

Here $2\{p/2\}\in \{0,1\}$ is the parity of p.

Proof. 

The inequality (26) is proved by induction. Let ${\mu }_h^{\max }={max}_{n,k}{\mu }_h^{(n,k)}$. Then ${\mu }_1^{\max }⩽1+n_{\mathrm{pr}}$ and ${\mu }_{h+1}^{\max }⩽1+⌊\frac{{\mu }_h^{\max }}{2}⌋⩽\frac{n_{\mathrm{pr}}-1}{2^h}+2$.

The inequality (27) and the formula (28) are proved together. If (27) is satisfied, then the quantity of provers is sufficient to build all possible non-zero height perfect trees and, hence, we obtain (28). Now, suppose that ${\sum }_h⌊\frac{{\mu }_h}{2}⌋⩽n_{\mathrm{pr}}$; then, at the next step, by (28),

$$\begin{array}{cc}\hfill \sum _h⌊\frac{{\mu }_h^{(n,k+1)}}{2}⌋& =⌊\left\{\frac{{\mu }_1^{(n,k)}}{2}\right\}+\frac{n_{\mathrm{pr}}}{2}-\frac{1}{2}\sum _{h^{\prime }}⌊\frac{{\mu }_{h^{\prime }}^{(n,k)}}{2}⌋⌋+\sum _{h=2}^{h_{max}}⌊\left\{\frac{{\mu }_h^{(n,k)}}{2}\right\}+\frac{1}{2}⌊\frac{{\mu }_{h-1}^{(n,k)}}{2}⌋⌋\hfill \\ & ⩽⌊\frac{1}{2}+\frac{n_{\mathrm{pr}}}{2}-\frac{1}{2}\sum _{h^{\prime }}⌊\frac{{\mu }_{h^{\prime }}^{(n,k)}}{2}⌋⌋+\sum _{h=2}^{h_{max}}⌊\frac{1}{2}+\frac{1}{2}⌊\frac{{\mu }_{h-1}^{(n,k)}}{2}⌋⌋\hfill \\ & ⩽⌊\frac{2n_{\mathrm{pr}}+1}{2}⌋=n_{\mathrm{pr}},\hfill \end{array}$$

where the last inequality follows from the fact that the number of non-zero summands in (27) is not greater than $n_{\mathrm{pr}}$. □

Remark 2.

The above lemma allows for constructing an optimized implementation of OneStep() procedure according to formula (28), and then to obtain a (pre-)reduced form of $h^{\copyright }$ according to Definition 5. The remainder of the results in this subsection essentially use this implementation.

Let $h^{\copyright }=h^{\copyright }\left(n_{\mathrm{pr}},n_{\mathrm{st}}\right)$ be the sequence of heights of trees in generated blocks. According to Corollary 3, it is ultimately periodic.

Hypothesis 1.

$$h_{max}=\lfloor {log}_2{n}_{\mathit{st}}{n}_{\mathit{pr}}\rfloor +1=min\{k\in {\mathbb{Z}}_{>0}|2^k>n_{\mathit{st}}{n}_{\mathit{pr}}\}.$$

Moreover, ${\mu }_{h_{max}}=0$ after block publishing.

Hypothesis 2.

A period of $h^{\copyright }$ consists of perfect trees of heights $h_{max-1}$ and $h_{max}$ in some order.

Corollary 6.

Let a (respectively b) be the number of perfect trees of height $h_{max-1}$ (respectively $h_{max}$). Then, the length of the period is

$$a+b=2^{\lfloor {log}_2{n}_{\mathit{st}}{n}_{\mathit{pr}}\rfloor -\nu },$$

for some $\nu \in \{0,1,\dots ,{\nu }_2(n_{\mathit{st}}{n}_{\mathit{pr}}+1)\}$, where ${\nu }_2(n_{\mathit{st}}{n}_{\mathit{pr}}+1)$ is the multiplicity of 2 in prime factorization of $n_{\mathit{st}}{n}_{\mathit{pr}}+1$, and

$$a=2^{\lfloor {log}_2{n}_{\mathit{st}}{n}_{\mathit{pr}}\rfloor +1-\nu }-\frac{n_{\mathit{st}}{n}_{\mathit{pr}}+1}{2^{\nu }},b=\frac{n_{\mathit{st}}{n}_{\mathit{pr}}+1}{2^{\nu }}-2^{\lfloor {log}_2{n}_{\mathit{st}}{n}_{\mathit{pr}}\rfloor -\nu }.$$

Remark 3.

The difference $h_{i+1}^{\copyright }-h_i^{\copyright }$ can be arbitrarily large:

$$h^{\copyright }(n_{\mathit{pr}},n_{\mathit{st}})=n_{\mathit{st}},2n_{\mathit{st}},\dots ,\mathit{whenever}{n}_{\mathit{pr}}⩾2^{2n_{\mathit{st}}-1}+2^{n_{\mathit{st}}-1}.$$

Definition 5.

The presentation $h^{\copyright }=h_1^{\copyright },\dots ,h_r^{\copyright },(h_{r+1}^{\copyright },\dots ,h_{r+s}^{\copyright })$ of the sequence (of heights) of published trees with the smallest pre-period and period is called the reduced form of $h^{\copyright }$.

If $h^{\left(1\right)},\dots ,h^{\left(r^{\prime }\right)},(h^{(r^{\prime }+1)},\dots ,h^{(r^{\prime }+s^{\prime })})$ is the presentation of the sequence of buffer states with the smallest pre-period and period, then the corresponding presentation of the sequence (of heights) of published trees $h^{\copyright }=h_1^{\copyright },\dots ,h_{r^{\prime }}^{\copyright },(h_{r^{\prime }+1}^{\copyright },\dots ,h_{r^{\prime }+s^{\prime }}^{\copyright })$ is called the pre-reduced form of $h^{\copyright }$.

Remark 4.

The pre-reduced and reduced forms of $h^{\copyright }$ can be different as in the following cases:

$$\begin{array}{cc}\hfill h^{\copyright }(2^6+1,1)& =1,2,3,4,5,6^{\times 31},(6^{\times 30},7,6)\hfill \\ & =1,2,3,4,5,6^{\times 30},(6^{\times 31},7);\hfill \end{array}$$

$$\begin{array}{cc}\hfill h^{\copyright }(360,1)& =1,2,3,4,5,6,7,8^{\times 4},9,8,(\underset{2^8}{\underbrace{8,9,\dots ,9,8}})\hfill \\ \hfill & =1,2,3,4,5,6,7,8^{\times 4},9,(\underset{2^8}{\underbrace{8^{\times 2},9,\dots ,9}});\hfill \end{array}$$

(29)

$$\begin{array}{cc}\hfill h^{\copyright }(361,1)& =1,2,3,4,5,6,7,8^{\times 4},9,8^{\times 2},(\underset{2^7}{\underbrace{9,8,\dots ,9,8^2}})\hfill \\ \hfill & =1,2,3,4,5,6,7,8^{\times 4},9,(\underset{2^7}{\underbrace{8^{\times 2},9,8,\dots ,9}}).\hfill \end{array}$$

(30)

Hypothesis 3.

The pre-period of the reduced form of $h^{\copyright }$ is a non-decreasing sequence.

Remark 5.

The above hypothesis is not true for the pre-reduced form of $h^{\copyright }$ as we can see in (29) and (30).

4.2.1. The Case of a Single Prover $n_{\mathrm{pr}}=1$

In the case of a single prover Conjectures 1 and 2 are obvious, moreover explicit description is obtained.

Proposition 4.

Let $2^h⩽k+1⩽2^{h+1}$. In the case of a single prover $n_{\mathit{pr}}=1$, the sequence $h^{\copyright }=h^{\copyright }(1,k)$ can be determined recursively together with an auxiliary sequence g that calculates the number of generated proofs in the buffer

$$\begin{array}{cc}\hfill g_0=0,h_n^{\copyright }& =\lfloor {log}_2(g_n+k+1)\rfloor =\left\{\begin{array}{cc}h,\hfill & if{g}_n+k<2^{h+1}-1,\hfill \\ h+1,\hfill & otherwise,\hfill \end{array}\right.\hfill \\ \hfill g_{n+1}& =g_n+k-2^{h_n^{\copyright }}+1.\hfill \end{array}$$

(31)

Corollary 7.

In the case of a single prover $n_{\mathrm{pr}}=1$, the sequence $h^{\copyright }(1,k)$ is periodic.

Let $k,k^{\prime }\in [2^h-1,2^{h+1}-1]$ and $k+k^{\prime }=2^{h+1}+2^h-2$. Then, the periods of reduced forms of $h^{\copyright }(1,k)$ and $h^{\copyright }(1,k^{\prime })$ are obtained each from the other with order reversing and replacement $h\leftrightarrow h+1$.

Proof. 

The sequence of the buffer state is periodic because at each step the increment of the number of generated proofs in the buffer is constant k by module $2^h-1$.

If $(q_0,q_1,\dots ,q_{s-1})$ is the period of the sequence of the number of generated proofs in the buffer for k steps, then $(2^h-q_{s-1},\dots ,2^h-q_1,2^h-q_0)$ is the period of the sequence of the number of generated proofs in the buffer for $k^{\prime }=2^{h+1}+2^h-2-k$ steps. Equation (31) for the first data implies the same equations for the second data. □

Example 2.

The cases of $n_{\mathit{pr}}=1$ and $n_{\mathit{st}}$ are closed to $2^h-1$. The following presentations are special cases (31):

• $k_1=2^h-1$, $k_2=2^{h+1}-1$

  $$h^{\copyright }(1,2^h-1)=\left(h\right),h^{\copyright }(1,2^{h+1}-1)=(h+1).$$
• $k_1=2^h$, $k_2=2^{h+1}-2$

  $$h^{\copyright }(1,2^h)=(h^{\times (2^h-1)},h+1),h^{\copyright }(1,2^{h+1}-2)=(h,{(h+1)}^{\times (2^h-1)}).$$
• $k_1=2^h+1$, $k_2=2^{h+1}-3$

  $$h^{\copyright }(1,2^h)+1=(h^{\times (2^{h-1}-1)},h+1),h^{\copyright }(1,2^{h+1}-3)=(h,{(h+1)}^{\times (2^{h-1}-1})).$$
• $k_1=2^h+2$, $k_2=2^{h+1}-4$, if $h=3,5,7,\dots$

  $$\begin{array}{c}{h}^{\copyright }(1,2^h+2)=\left(h^{\times \frac{2^h-2}{3}},h+1,h^{\times \frac{2^h-2}{3}},h+1,h^{\times \frac{2^h-5}{3}},h+1\right),\\ h^{\copyright }(1,2^{h+1}-4)=\left(h,{(h+1)}^{\times \frac{2^h-5}{3}},h,{(h+1)}^{\times \frac{2^h-2}{3}},h,{(h+1)}^{\times \frac{2^h-2}{3}}\right),\end{array}$$
  if $h=4,6,8,\dots$

  $$\begin{array}{c}{h}^{\copyright }(1,2^h+2)=\left(h^{\times \frac{2^h-1}{3}},h+1,h^{\times \frac{2^h-4}{3}},h+1,h^{\times \frac{2^h-4}{3}},h+1\right),\\ h^{\copyright }(1,2^{h+1}-4)=\left(h,{(h+1)}^{\times \frac{2^h-4}{3}},h,{(h+1)}^{\times \frac{2^h-4}{3}},h,{(h+1)}^{\times \frac{2^h-1}{3}}\right).\end{array}$$

4.2.2. The Case of a Single Step $n_{\mathrm{st}}=1$

Hypothesis 4.

Let $k_1,k_2\in [2^h-1,2^{h+1}-1]$ and $k_1+k_2=2^{h+1}+2^h-2$. Then the periods of reduced forms of $h^{\copyright }(k_1,1)$ and $h^{\copyright }(k_2,1)$ are obtained each from the other by order reversing and replacement $h\leftrightarrow h+1$.

Example 3.

The cases of $n_{\mathit{st}}=1$ and $n_{\mathit{pr}}$ closed to $2^h-1$ agree with the above hypothesis:

• $k_1=2^h-1$, $k_2=2^{h+1}-1$

  $$h^{\copyright }(2^h-1,1)=1,2,\dots ,h-1,\left(h\right),h^{\copyright }(2^{h+1}-1,1)=1,2,\dots ,h,(h+1);$$
• $k_1=2^h$, $k_2=2^{h+1}-2$

  $$h^{\copyright }(2^h,1)=1,2,\dots ,h-1,h^{\times (2^h-h)},(h^{\times (2^h-1)},h+1),$$

  $$h^{\copyright }(2^{\times (h+1)}-2,1)=1,2,\dots ,h,(h,{(h+1)}^{\times (2^h-1)});$$
• $k_1=2^h$, $k_2=2^{h+1}-2$, $h⩾3$

  $$h^{\copyright }(2^h+1,1)=1,2,\dots ,h-1,h^{\times \left(2^{h-1}-⌊\frac{h-1}{2}⌋\right)},(h^{\times (2^{h-1}-1)},h+1),$$

  $$h^{\copyright }(2^{h+1}-3,1)=1,2,\dots ,h,(h,{(h+1)}^{\times (2^{h-1}-1)}).$$

5. Stochastic Case

In this section, we consider the result of Algorithm 1 only in the case of “$b_{\mathrm{behavior}}$ is stochastic”.

5.1. Occupancy Distribution: Efficiency

Placement of provers into suitable positions at each stage can be described by the classical occupancy distribution. See [26], the more recent [27] and references therein. Another closely related model is a coupon collector problem.

Thus, we have $n_{\mathrm{pr}}⩾1$ provers placed independently and with equal probability into $n_{\mathrm{pos}}⩾1$ positions. In terms of urn models [26], provers and positions correspond to balls and bins, respectively. Let us denote ${\xi }^{n_{\mathrm{pr}}{n}_{\mathrm{pos}}}$ a random number of non-empty positions. It takes integer values i from 1 to $min\{n_{\mathrm{pr}},n_{\mathrm{pos}}\}$ with probabilities

$$Pr\{{\xi }^{n_{\mathrm{pr}}{n}_{\mathrm{pos}}}=i\}=n_{\mathrm{pos}}^{-n_{\mathrm{pr}}}\left(\genfrac{}{}{0pt}{}{n_{\mathrm{pos}}}{i}\right)i!\left\{\genfrac{}{}{0.0pt}{}{n_{\mathrm{pr}}}{i}\right\}=n_{\mathrm{pos}}^{-n_{\mathrm{pr}}}{\left(n_{\mathrm{pos}}\right)}_i\left\{\genfrac{}{}{0.0pt}{}{n_{\mathrm{pr}}}{i}\right\}.$$

Here, we use the following notations:

Notation 3.

• $\left\{\genfrac{}{}{0.0pt}{}{n}{m}\right\}$ is the Stirling number of the second kind, i.e., the number of factorizations of an n-element set to an m-element factor-set;
• ${\left(n\right)}_k=n(n-1)\cdots (n-k+1)$ is the falling factorial.

Mean and variance of the occupancy distribution (e.g., Theorem 2A [27]) are obtained as the special cases of expected values of falling factorials Theorem 1A [27]:

$$\begin{array}{c}E{\left(n_{\mathrm{pos}}-{\xi }^{n_{\mathrm{pr}}{n}_{\mathrm{pos}}}\right)}_r={\left(n_{\mathrm{pos}}\right)}_r{E}_r,E_r={\left(1-r/n_{\mathrm{pos}}\right)}^{n_{\mathrm{pr}}},0⩽r<n_{\mathrm{pos}};\\ E{\xi }^{n_{\mathrm{pr}}{n}_{\mathrm{pos}}}=n_{\mathrm{pos}}(1-E_1),Var{\xi }^{n_{\mathrm{pr}}{n}_{\mathrm{pos}}}=n_{\mathrm{pos}}\left((n_{\mathrm{pos}}-1)E_2+E_1-n_{\mathrm{pos}}{E}_1^2\right).\end{array}$$

Let $N_t:=Len\ell$ denote the total number of generated trees, $N_{\ell }$ and $N_{\mathrm{int}}$, respectively, the numbers of leaves and internal vertices in these trees. Similarly let $N_t^{\copyright }=n_{\mathrm{bl}}$ be the number of published trees, $N_{\ell }^{\copyright }$ and $N_{\mathrm{int}}^{\copyright }$, respectively, the number of leaves and internal vertices in these trees.

Note that, according to (1),

$$N_{\ell }=N_{\mathrm{int}}+N_t,N_{\ell }^{\copyright }=N_{\mathrm{int}}^{\copyright }+n_{\mathrm{bl}}.$$

(32)

Moreover, as a random variable,

$$N_{\mathrm{int}}=n_{\mathrm{bl}}{n}_{\mathrm{st}}{\xi }^{n_{\mathrm{pr}}{n}_{\mathrm{pos}}}.$$

(33)

Throughput of our system can be naturally measured by the number of processed transactions, i.e., be the number of leaves $N_{\ell }$ and $N_{\ell }^{\copyright }$. On the other hand, the useful work of provers is given by the number of internal vertices $N_{\mathrm{int}}$ and $N_{\mathrm{int}}^{\copyright }$. According to (32), if $n_{\mathrm{st}}{n}_{\mathrm{pr}}\gg 1$, then $N_{\mathrm{int}}/N_{\ell }\approx 1$ and $N_{\mathrm{int}}^{\copyright }/N_{\ell }^{\copyright }\approx 1$.

Note that in the cases that “$b_{\mathrm{behavior}}$ is deterministic”, $N_{\mathrm{int}}=n_{\mathrm{bl}}{n}_{\mathrm{st}}{n}_{\mathrm{pr}}$. We use this to define the “normalized” values:

• proof generation efficiency

  $$Ef(n_{\mathrm{pr}},n_{\mathrm{pos}}):=E\frac{N_{\mathrm{int}}}{n_{\mathrm{bl}}{n}_{\mathrm{st}}{n}_{\mathrm{pr}}}=E\frac{{\xi }^{n_{\mathrm{pr}}{n}_{\mathrm{pos}}}}{n_{\mathrm{pr}}}=\frac{n_{\mathrm{pos}}}{n_{\mathrm{pr}}}\left(1-{\left(1-1/n_{\mathrm{pos}}\right)}^{n_{\mathrm{pr}}}\right),$$

  (34)
• proof publishing efficiency

  $${Ef}^{\copyright }(n_{\mathrm{bl}},n_{\mathrm{st}},n_{\mathrm{pr}},n_{\mathrm{pos}}):=E\frac{N_{\mathrm{int}}^{\copyright }}{n_{\mathrm{bl}}{n}_{\mathrm{st}}{n}_{\mathrm{pr}}}.$$

  (35)

Note that

$$0<{Ef}^{\copyright }⩽Ef⩽1.$$

There are two limit cases:

$$\underset{n_{\mathrm{pos}}\to \infty }{lim}Ef(n_{\mathrm{pr}},n_{\mathrm{pos}})=1,\underset{\begin{array}{c}{n}_{\mathrm{pr}}\to \infty \\ n_{\mathrm{pos}}\to \infty \\ n_{\mathrm{pr}}/n_{\mathrm{pos}}\to \gamma \end{array}}{lim}Ef(n_{\mathrm{pr}},n_{\mathrm{pos}})=\frac{1-e^{-\gamma }}{\gamma }.$$

5.2. Simulation Model for Block Publishing Efficiencies

In both cases that “$b_{\mathrm{shape}}$ is strict” and “$b_{\mathrm{shape}}$ is perfect”, ${Ef}^{\copyright }$ is an increasing function of $n_{\mathrm{bl}}$. In the cases that “$b_{\mathrm{shape}}$ is strict”, the lengths of buffers $h^{\left(n\right)}$ are not greater then $n_{\mathrm{pos}}-1$. This implies convergence in the following proposition.

Proposition 5.

In the case that “$b_{\mathrm{shape}}$ is strict”, ${Ef}^{\copyright }\nearrow Ef$ whenever $n_{\mathrm{bl}}\to \infty$.

Hypothesis 5.

In the case that “$b_{\mathrm{shape}}$ is perfect”, ${Ef}^{\copyright }\nearrow Ef$ whenever $n_{\mathrm{bl}}\to \infty$.

We try to illustrate the above convergences in Figure 4. As we can see, in the case that “$b_{\mathrm{shape}}$ is strict”, ${Ef}^{\copyright }$ tends quickly to Ef. On the contrary, in the case that “$b_{\mathrm{shape}}$ is perfect”, the convergence is very slow. Note that the limit value is ${Ef|}_{n_{\mathrm{pr}}=n_{\mathrm{pos}}=5}=0.67232$, and some values close to asymptote are ${Ef}^{\copyright }{|}_{n_{\mathrm{bl}}=1000}=0.6359$, ${Ef}^{\copyright }{|}_{n_{\mathrm{bl}}=2000}=0.6451$, ${Ef}^{\copyright }{|}_{n_{\mathrm{bl}}=3000}=0.6497$, ${Ef}^{\copyright }{|}_{n_{\mathrm{bl}}=5000}=0.6541$.

In practice, it is important to select a right value of $n_{\mathrm{pos}}$ when other parameters are fixed. In Figure 5, dependencies of Ef and ${Ef}^{\copyright }$ (for both cases “$b_{\mathrm{shape}}$ is strict” and binary and “$b_{\mathrm{shape}}$ is perfect”) on the number of positions are shown in the case when $n_{\mathrm{bl}}=100$, $n_{\mathrm{st}}=10$, $n_{\mathrm{pr}}=10$. Values for efficiencies are average over 300 random calculations.

In

Table 2. ArgMax and Max of the function $n_{\mathrm{bl}}\mapsto {Ef}^{\copyright }$ for the case “$b_{\mathrm{shape}}$ is perfect”.

nst∖npr	2	3	4	5	6	7	8	9	10
1	7 0.89	8 0.83	8 0.78	8 0.72	8 0.67	9 0.62	9 0.58	9 0.55	9 0.52
2	4 0.85	5 0.74	5 0.67	6 0.62	6 0.58	7 0.56	7 0.53	7 0.51	8 0.49
3	3 0.80	4 0.70	5 0.65	5 0.60	6 0.57	6 0.55	7 0.53	7 0.51	8 0.50
4	3 0.78	4 0.70	5 0.65	6 0.61	6 0.58	7 0.57	8 0.56	9 0.54	9 0.53
5	3 0.77	4 0.71	5 0.66	6 0.63	7 0.61	7 0.59	8 0.56	9 0.55	9 0.53
6	3 0.79	4 0.72	5 0.67	6 0.65	7 0.62	7 0.60	7 0.58	8 0.57	9 0.55
7	3 0.79	4 0.71	6 0.68	6 0.65	7 0.63	7 0.61	8 0.60	9 0.59	10 0.59
8	3 0.79	4 0.73	6 0.70	6 0.67	7 0.65	8 0.64	9 0.62	10 0.61	10 0.60
9	3 0.80	5 0.74	6 0.70	6 0.68	8 0.66	8 0.65	10 0.64	10 0.61	11 0.61
10	3 0.81	5 0.75	6 0.72	7 0.70	8 0.68	9 0.66	10 0.64	10 0.63	11 0.62

, for the case “$b_{\mathrm{shape}}$ is perfect” and in

Table 3. ArgMax and Max of $n_{\mathrm{bl}}\mapsto {Ef}^{\copyright }$ for the case “$b_{\mathrm{shape}}$ is strict”.

nst∖npr	2	3	4	5
1	13/0.92	19/0.90	23–24/0.89	28–29/0.88
2	14/0.93	21–22/0.91	28/0.90	34–35/0.89
3	15/0.94	23–24/0.92	32/0.91	38–39/0.90
4	16/0.94	25–26/0.93	33–34/0.92	41–42/0.91
5	18/0.95	27–28/0.93	36–37/0.92	44–46/0.92

for the case “$b_{\mathrm{shape}}$ is strict”, the arguments of maxima and the corresponding maximal values of blocks publishing efficiency ${Ef}^{\copyright }$ are given, as functions of the number of positions $n_{\mathrm{pos}}$ for $n_{\mathrm{bl}}=200$ and various values of $n_{\mathrm{st}}$ and $n_{\mathrm{pr}}$.

5.3. Simulation Model for Heights of Strict Binary Trees

Here, we consider an analog of the formula (22) for average heights h of published strict binary trees in the case when “$b_{\mathrm{behavior}}$ is stochastic”. We consider a linear approximation

$$h(n_{\mathrm{st}},n_{\mathrm{pr}})\approx \alpha n_{\mathrm{st}}+\beta {log}_2{n}_{\mathrm{pr}}+\gamma .$$

Optimal parameters $\alpha ,\beta ,\gamma$ are obtained by means of the least squares method. For a fixed positive integer m, we consider all pairs of integers $(n_{\mathrm{st}},{log}_2{n}_{\mathrm{pr}})=(i,j)$ satisfying $1⩽j⩽i⩽m$. Thus, the problem is to minimize the square of the error vector

$$r=\sum _{i=1}^m\sum _{j=1}^i{\left(\alpha i+\beta j+\gamma -h(i,2^j)\right)}^2.$$

The critical point $(\alpha ,\beta ,\gamma )$ is the solution of the system of linear equations

$$\left\{\begin{array}{c}\frac{\partial r}{\partial \alpha }=0\hfill \\ \frac{\partial r}{\partial \beta }=0\hfill \\ \frac{\partial r}{\partial \gamma }=0\hfill \end{array}\right.\iff \sum _{i=1}^m\sum _{j=1}^i\left(\begin{array}{c}i\\ j\\ 1\end{array}\right)\left(\left(\begin{array}{ccc}i& j& 1\end{array}\right)\left(\begin{array}{c}\alpha \\ \beta \\ \gamma \end{array}\right)-h(i,2^j)\right)=0.$$

(36)

The inverse matrix for this system is:

$${\left(\sum _{i=1}^m\sum _{j=1}^i\left(\begin{array}{c}i\\ j\\ 1\end{array}\right)\left(\begin{array}{ccc}i& j& 1\end{array}\right)\right)}^{-1}=\frac{6}{{(m+2)}_4}\left(\begin{array}{ccc}8& -4& -4m\\ -4& 8& -4\\ -4m& -4& 3m^2+3m+2\end{array}\right).$$

It can be calculated using Wolfram Mathematica. Enthusiasts can verify this using formulas for sums ${\sum }_{k=1}^n{k}^{\left(p\right)}=\frac{1}{p+1}{n}^{(p+1)}$ of rising factorial powers for $k^{\left(p\right)}=k(k+1)\cdots (k+p-1)$ or the Faulhaber’s formulas for generalized harmonic numbers $H_{n,-p}:={\sum }_{k=1}^n{k}^p$.

The results of numerical experiments (coefficients for linear approximation and the standard deviation) are presented in

Table 4. Linear approximations of average height of generated trees as functions of $n_{\mathrm{st}}$ and ${log}_2{n}_{\mathrm{pr}}$.

m	$\mathit{\alpha }$	$\mathit{\beta }$	$\mathit{\gamma }$	$\sqrt{\frac{2\mathit{r}}{\mathit{m}(\mathit{m}+1)}}$
6	0.84	1.35	−0.75	0.072
7	0.81	1.40	−0.75	0.074
8	0.79	1.43	−0.74	0.075
9	0.77	1.46	−0.74	0.075
10	0.75	1.49	−0.73	0.075

.

For the case $m=8$, the graphical presentation of average values $h(i,2^j)$ and their linear approximation are given in Figure 6.

6. Discussion

Latus consensus, proposed in [3,4], provides secure and stable sidechain operation, even under the complete distrust assumption in sidechains, and even when all participants in the sidechain consensus are malicious. We assume that the adversary in the sidechain may try to sensor the transactions of other participants inside the SC, or from the MC to the SC, or try to steal tokens in the SC, hide the state of the SC, or stop block production in the SC, but these actions must not be successful. For reliable operation under such assumptions, Latus consensus needs uninterruptible zk-SNARK-proof generation, which, in turn, demands essential computational power and cannot be performed by a single regular participant with commodity hardware. Projects Coda [8] or Polygon [28] implicitly involve a semi-trusted participant with powerful computational capabilities (such as cloud computation) to solve this task on time, but this approach may lead to a single failure point. To eliminate this problem we propose a new approach for efficient decentralization proof generation. According to our approach, decentralized generation is applied not only to blocks in the whole epoch but even to each block. Thus, proofs are generated with the involvement of a large number of independent participants, which are called provers. This provides a decentralization of the zk-SNARK sidechain operation in secure and reliable way.

In this article, we introduced the properties of this process as proof generation efficiency Ef and proof publishing efficiency ${Ef}^{\copyright }$, which are investigated in Section 5.1.

For the generation of a single block considered in [18], the block forger initially selects the number of levels ℓ of a perfect binary tree that will be included into a block. In [18] (Table 1), we find what number of provers is needed to build the perfect binary tree with $\ell =4,5,6,7,8,9$ levels during $n_{\mathrm{st}}=9$ steps with probability $⩾0.95$. In this limit case, the role of the efficiency garnered from this article results in the ratio of the number of useful proofs, which is the number of internal vertices $n_i\left(t\right)$ in the built tree to the total number of proofs $n_{\mathrm{st}}{n}_{\mathrm{pr}}$ produced by all provers during the block publishing process

$${Ef}_1\approx \frac{n_i\left(t\right)}{n_{\mathrm{st}}{n}_{\mathrm{pr}}}=\frac{2^{\ell -1}-1}{9n_{\mathrm{pr}}}.$$

(37)

In

Table 5. Comparison of efficiencies for $n_{\mathrm{st}}=9$ steps and $n_{\mathrm{pos}}=n_{\mathrm{pr}}$.

${\mathit{n}}_{\mathbf{pr}}$	ℓ	${\mathbf{Ef}}_1$	${\mathbf{Ef}}_{\mathbf{perfect}}^{\mathbf{\copyright }}$	${\mathbf{Ef}}_{\mathbf{perfect}}^{\mathbf{\copyright }}$	${\mathbf{Ef}}_{\mathbf{perfect}}^{\mathbf{\copyright }}$	${\mathbf{Ef}}_{\mathbf{strict}}^{\mathbf{\copyright }}$	Ef
			${\mathit{n}}_{\mathbf{bl}}=\mathbf{10}$	${\mathit{n}}_{\mathbf{bl}}=\mathbf{100}$	${\mathit{n}}_{\mathbf{bl}}={\mathbf{n}}_{\mathrm{pr}}$	${\mathit{n}}_{\mathbf{bl}}=\mathbf{10}$
3	4	0.26	0.64	0.69	0.50	0.69	0.70
4	4	0.19	0.64	0.67	0.54	0.67	0.68
10	5	0.17	0.48	0.59	0.50	0.62	0.65
33	6	0.10	0.34	0.45	0.43	0.58	0.64
95	7	0.07	0.18	0.27	0.26	0.56	0.63
452	8	0.03	0.05	0.09	0.11	0.53	0.63
2176	9	0.01	0.02	0.03	0.04	0.50	0.63

, we compare the values of ${Ef}_1$ from (37) with the efficiencies ${Ef}^{\copyright }$ obtained by the emulation procedure when $b_{\mathrm{shape}}$ is perfect in three cases: $n_{\mathrm{bl}}=10$, $n_{\mathrm{bl}}=100$ and $n_{\mathrm{bl}}=n_{\mathrm{pr}}$, and when $b_{\mathrm{shape}}$ is strict and $n_{\mathrm{bl}}=10$ (denoted ${Ef}_{\mathrm{perfect}}^{\copyright }$ and ${Ef}_{\mathrm{strict}}^{\copyright }$, respectively). The value of Ef calculated from (34) is the limit for both ${Ef}_{\mathrm{perfect}}^{\copyright }$ and ${Ef}_{\mathrm{strict}}^{\copyright }$ at $n_{\mathrm{bl}}\to \infty$.

So, one can see ${Ef}^{\copyright }$/${Ef}_1\approx 3$ as the average. In the top half of Table 5, the values of ${Ef}^{\copyright }$ are closed to the best possible limit Ef. At the bottom, when the number of provers becomes extreme, ${Ef}_{\mathrm{perfect}}^{\copyright }$ still obtains an increment with respect to ${Ef}_1$; however, both values are too small. The convergence ${Ef}_{\mathrm{perfect}}^{\copyright }\to Ef$ is slow and a very big buffer size is required in this situation. However, ${Ef}_{\mathrm{strict}}^{\copyright }$ remains closed to Ef.

7. Conclusions

We investigated characteristics of blocks and characteristics of a SC in a whole under various parameters of a SC, such as the number of blocks in an epoch, number of provers, number of available transactions, time of block creation, etc. We obtained theoretical results for a model with additional restrictions on provers’ behavior and various experimental results for an extended model without such restrictions. These results are helpful when determining the parameters of a sidechain, such as epoch length, block creation time, proof incentives, etc. We show that in deterministic cases the sequences of published trees are ultimately periodic and ensure the highest possible efficiency of the proof creation process, because in this case there are no collisions in proof creation.

In stochastic cases, we obtain a universal measure of prover efficiencies taking values in the interval [0,1] and given by the explicit formula in one case, calculated by simulation models in other cases.

In the sense of efficiency defined, the optimal number of allowed prover positions for a step can be proposed for various sidechain parameters, such as number of provers, number of steps in a block, and so on. We also considered non-perfect binary tree utilization in a blockchain, and described benefits and restrictions for such trees’ use. It turns out that we can achieve large efficiency using these very trees.

Our algorithm for the strict binary trees gives the following differences (compared with the case of perfect binary trees):

• The buffer size is smaller;
• Block publishing efficiency is higher;
• The average height of the generated perfect binary trees is proportional to $log\left(n_{\mathrm{st}}{n}_{\mathrm{pr}}\right)=log{n}_{\mathrm{st}}+log{n}_{\mathrm{pr}}$. The average height of the generated strict binary trees has a similar linear dependence on the logarithm of the number of provers $log{n}_{\mathrm{pr}}$, but a different linear dependence to the number of steps $n_{\mathrm{st}}$ (not $log{n}_{\mathrm{st}}$). So, we can consider the case of strict binary trees practically interesting only if the number of steps $n_{\mathrm{st}}$ is small.

All results from [18,19,20] and the present paper are related and, put together, give a comprehensive description of SC behavior under our chosen parameters, allowing us to find the optimal sets of parameters that help to optimize functioning, in particular increasing throughput.

One of the most interesting results in this article shows that, under the condition of quick synchronization among block forgers, the throughput increases up to three times in practical settings and can be increased even more for extreme settings cases.

One topic of future research is the investigation of the efficiency of Verkle tree [29] and Curve tree structures [30], which can be used for creating proof trees instead of using different variants of Merkle trees.