HC notes - HackMD

# HC notes ## Hierarchical consensus growth Hierarchical consensus (HC) represents a tree of subnets whose structure can change in time. Since it's difficult to reason about economics even on a single network, it's worth trying to understand what the HC network can look like under plausible growth assumptions. To do this, we can note the similarities between the patterns of branching we expect in HC, and structures that arise in fields, such as taxonomy, nuclear fission, and society formation, amongst others. In these fields the mathematics is fairly established. So to describe the dynamics of the HC structure we can use related ideas and some tools from probability theory. This serves both as an exercise to formalize our understanding of HC, and further down the line to model and simulate it. ### Basic Model Let $\mathcal{I}^{*}$ denote the set of progeny, and $\mathcal{I}$ be the set of all networks including the root. The root is endowed with a set of elements \begin{align*} \{\chi^{\tau}(\cdot),\,N^{\tau}(\cdot)\}_{\tau\ge0}\,. \end{align*} Here * $\chi^{\tau}(\cdot)\in\{0,1\}$ is a random characteristic describing its operational status: whether a subnet is functioning or not. * $N(\cdot)\in\mathbb{\mathbb{N}}$ is a counting process, which keeps track of subnets spawned by the root. * $\tau$ denotes time of inception. * Additional elements may be added to this set as it becomes clear what HC means. The HC mechanism, as I understand it, is universal. Since it's the same at each node in the hierarchy, it seems plausible to appeal to a form of Bellman's *first generation principle*. In this context, the principle means that for subnet $i\in\mathcal{I^{*}}$, the set $\{\chi_{i},\,N_{i}(\cdot)\}_{\tau\ge0}$ is an identically distributed copy of $\{\chi,\,N(\cdot)\}_{\tau\ge0}$. Identically distributed because there there's a single protocol, but not independent. A conditional dependence in time arises via the causal relationship the ancestor network existing and its first generation progeny subnets existing and being operational. Now our goal is to provide a formalism that describes the state of the complete HC structure. To this end, we can first start by considering the operational state of subnets under the approximation they're born but do not die \begin{align*} \chi^{\tau}(u):=\begin{cases} 0 & u<0\\ 1 & u>0 \end{cases}\,. \end{align*} We can relax the condition of immortality later. This will make the dynamics substantially more complicated. Now, with operational state as defined, the evolution of the HC network can be characterised as \begin{align*} Z(t,\tau):=\underset{\text{root}}{\underbrace{\chi^{\tau}(t-\tau)}}+\underset{\text{subnets}}{\underbrace{\sum_{i\in\mathcal{I^{*}}}\chi_{_{i}}^{\tau_{i}}(t-\tau_{i})}}\,, \end{align*} Across subnets operational state must respect the causal order that only parents can spawn children. Let the operator $\mathcal{T}$ order $\tau_{i_{k}}$, so that for subnet $i$ spawning at time $\tau$ we have the stratification \begin{align*} \sum_{i\in\mathcal{I^{*}}}\chi_{_{i}}^{\tau_{i}}(t-\tau_{i})=\sum_{k:\mathcal{T}(\tau_{i_{k}})<t}\underset{:=Z_{k}(t)}{\underbrace{\sum_{i\in\mathcal{I}_{k}}\chi_{_{i}}^{\tau_{i}}(t-\tau_{i})}}\,. \end{align*} Conditional on ordering each $Z_{k}(t)$ is independent. It follows using the tower property of conditional expectation that the expected value of operational state for the network at a given time is \begin{align*} \mathbb{E}\left[Z(t,\tau)\right] & =\mathbb{E}\left[\underset{\text{root}}{\underbrace{\chi^{\tau}(t-\tau)}}\right]+\mathbb{E}\left[\sum_{k:\mathcal{T}(\tau_{i_{k}})<t}\underset{\text{subnets}}{\underbrace{Z_{k}(t)}}\right]\,.\\ & =\mathbb{E}\left[\underset{\text{root}}{\underbrace{\chi^{\tau}(t-\tau)}}\right]+\mathbb{E}\left[\sum_{k:\mathcal{T}(\tau_{i_{k}})<t}\underset{\text{subnets}}{\underbrace{\mathbb{E}\left[Z(t,\tau_{i_{k}})\right]}}\right] \end{align*} which leads to the following integral equation for the expected cumulative number of operating subnets \begin{align*} n(t,\tau)=1+\int_{(0,t-\tau]}n(t,u+\tau)d\Lambda^{\tau}(u)\,. \end{align*} Here $d\Lambda^{\tau}=\mathbb{E}\left[\Delta N^{\tau}(\cdot)\right]$ is a measure of time between birth and spawning a new generation. In reality this is a function of demand for consensus. In short, the fundamental relation for growth of operating subnets is simply \begin{align*} n=1+n*\Lambda\,. \end{align*} **Interpretation** * What does this mean? To start, there's a single network operating, Filecoin. As the HC protocol spawns new nodes, the population of subnets across the structure should grow according to the above recursion relation. * Why's this useful to know? It's a general and high-level perspective, but formalises notions of growth in HC. It also gives an equation to simulate the HC network. * What are the limitations? For a start we assumed immortal subnets, and that subnets are alike. All models wrong, some are useful. * Qs: What do we gain from a complicated hierarchical structure? Why shouldn't the structure just be one level deep? HC risks a cascade of failure --- death of a subnet kills all descendents. ### Model with subnet death If subnets can die, we consider a random operating characteristic of the form \begin{align*} \chi^{\tau}(u):=\begin{cases} 0 & u<0\\ 1 & u\in[0,L^{\tau}]\\ 0 & u>L^{\tau} \end{cases} \end{align*} where a node is active for random length of time $L^{\tau}$. Subnet death raises an interesting question. As well time-ordering so that children must be younger than parents, it implies a further causal structure that has to be accounted for. If a parent subnet fails, then I think it's correct to say that all progeny also must die. *tbc* ### Other observables * Can we say anything about the dynamics beyond subnet operational status. Total network value could be an easy one along similar lines. Systemic risk of failure and how thing scales depending on depth vs width growth seems important. * Ideally, understanding HC takes a multiscale perspective. We *do* have a top level model now, but what about the finer scale processes. E.g. a typical approach for block demand is to model it using a Poisson arrival process. How does this gel with the full HC level process. * Maybe now the lowest hanging fruit is look at arrival processes and try to think how these would differ within subnet vs across subnets. *tbc* ## Gas At the top level the gas model should attempts to satisfy three economic goals: 1. Incentivize message validation in the very low congestion regime. 2. Align supply of message validation with demand as congestion increases on a subnet. 3. Ensure net cash flow towards HC root.  * $g^{*}\in\mathbb{R}_{+}$ [bytes] is a gas target parameter. * $r_{t}$ is the gas usage to target gas usage ratio, $r_{t}=g_{t}/g^{*}$. * $k\in\mathbb{R}^{+}$ is the attack parameter that defines how reponsive the burn fee is to exceeding the gas usage target ratio. The proposed message fee has three elements. A whole network reward that depends on the amount of gas used, a tip to reward miners individually, and an option to chose the gas mechanism for within subnet messages. -->   For a given message, the cost for transmitting it between sender $i$ and reciever $j$ at time $t$ is given by \begin{align*} f_{ijt}(g,\,m,\,\cdot):=\begin{cases} \underset{\text{network reward}}{\underbrace{b_{t}g_{t}}}+\underset{\text{miner reward}}{\underbrace{m}} & ij\in\mathcal{A}\\ \underset{\text{subnet defined}}{\underbrace{f(\cdot)}} & ij\in\mathcal{B}\\ \sum_{k:{i_k}{j_k}\in\mathcal{A}} f_{{i_k}{j_k}t} & ij\in\mathcal{C} \end{cases}\,. \end{align*} The key features are * between parent and child messages ($\mathcal{A}$), pay a variable gas burn fee $b_{t}g_{t}$ to reward the network, and fixed reward $m$ to incentivize miners. * the gas costs and mechanism for within subnet transactions ($\mathcal{B}$) are decided by the subnet. For example, the subnet may opt but isn't mandated to use the parent-child gas mechanism. * messages in $\mathcal{C}$ occur by traversing a path along parent-child pairs via a common ancestor. * the miner reward $m$ is universal across HC levels and fixed in time. There are arguments both for and against relaxing these conditions. To be discussed below. The burn rate has a minimum value $b^*$. The burn rate can be chosen by the subnet to be static or dynamic. If dynamic, it changes according to the update rule -->      -->