Owner: @Alexander Mozeika
Reviewers: 🟢@Marvin Jones 🟢@Álvaro Castro-Castilla
In order to guide a design of the Blend Network, we summarise in this document parameters (and results of analysis) of the leader election process, communication on trees and inference of relative stake. In addition to this, we considered sampling of linear trees and derived conditions under which results for communication on trees can be used. Also we analysed the probability of linking a sender node to its message which allows us to quantify the “unlinkability of block proposer.” All these parameters (and results) were used to design (and implement) the “calculator” which can be used to quantify resilience and anonymity of communication in the Blend Network.
Finally, in this document we also analysed strategies which can be used to reduce anonymity failure and statistical properties of number of time-slots between two consecutive blocks in Cryptarchia.
The leader election process is organised into epochs and each epoch is divided into $T$ time-slots.
One epoch of the leader election process. Node $i$ participates in the leader election at time-slots $t_1,\ldots,t_T$. The (binary) outcome of this lottery, where 0/1 corresponds to lost/won, is either observed (numbers in square brackets) or unobserved.
The leader election process has the following parameters
| Parameter | Description | Value/Range |
|---|---|---|
| $N$ | Number of nodes | $10^2\ldots10^4$ |
| $T$ | Number of time-slots per epoch | $\approx 432,000$ |
| $f$ | Fraction of time-slots with at least one winner | $0.05$ |
| $\Delta t$ | The duration of a single time-slot | $1$ s |
Communication on Linear Trees. A message is sent from a root node through $K$ communication paths where each path has $L$ nodes.
The number of nodes in linear tree design is $1+KL$, where $K$ is the number of paths and $L$ is the number of nodes in each path excluding the sender node. In the linear tree design, one node is the sender node and the other $KL$ nodes are mix nodes.
We assume that in each epoch of the protocol there are $n$ sender nodes, labelled by the set $[n]$. Each of the $n$ sender nodes sample $K \times L$ nodes from the population of $N$ nodes (labeled by the set $[N]$). The total number of nodes involved in communication is $n(1+KL)$.
We assume that each sender node samples $K\times L$ nodes, independently from other nodes, using sampling without replacement. A node among the $K\times L$ nodes sampled from $[N]$ just by chance can also appear in other $n-1$ random subsets of nodes.
Result of the sampling process described above can be represented by the following random factor-graph:
![The random factor-graph generated by sampling of $n$ subsets of $K\times L$ nodes, represented by factors (squares), from the set of all nodes $[N]$ represented by (filled) circles. If node is member of a subset then this is represented by an edge on this graph. Each node in the subset of $[N]$, $[n]$, is a member of at least $1$ of these subsets. Here $K\times L=4$.](attachment:d892cf87-779b-4c75-979f-ebe2dd150dfe:Screenshot_2025-02-07_at_16.18.50.png)
The random factor-graph generated by sampling of $n$ subsets of $K\times L$ nodes, represented by factors (squares), from the set of all nodes $[N]$ represented by (filled) circles. If node is member of a subset then this is represented by an edge on this graph. Each node in the subset of $[N]$, $[n]$, is a member of at least $1$ of these subsets. Here $K\times L=4$.
Structure of a factor $\mu$ in the random factor graph associated with sampling of linear trees. Here $K=L=2$. Node $i$ , associated with $\mu$, is a sending a message to nodes $i_2$ and $i_4$ via the mix nodes $i_1$ and $i_3$.
Connectivity of a node $i\in[N]$ is the number of random edges connecting this nodes to factors labelled by the set $[n]$. The connectivity of a node $i \in [N]$ is the number of linear trees that $i$ appears in. The connectivity is a random number from the binomial distribution