As part of a series on Stateless Ethereum, the first blog looked at why Stateless Ethereum was proposed and the key changes Stateless introduces to the Ethereum ecosystem. Part one also briefly touched on the need to achieve balance between complexity and simplicity in model design. In part two of this series, we look at the way we approached building a model of such a complex ecosystem, while balancing this need.
Choosing a Bayesian Network Model for Ethereum
There are many different modeling techniques. However, we decided on a Bayesian Network (BN) modeling approach for several reasons.
First, a BN is a probabilistic graphical and visual modelling tool that represents the interaction of stakeholders within the model. Secondly, we can explicitly represent uncertainty using joint probability distributions across all the factors and interactions in the model. Thirdly, this network model is suited to modelling complex systems like Ethereum. And finally, it may be used regardless of whether there is a lot or little data. Diverse data sources can be combined to inform the model like expert knowledge, empirical data, model output, published and grey literature.
Perhaps the most compelling reason to use a Bayesian Network to model Ethereum is that it explicitly captures uncertainty, allowing the model to learn from new research and data input. The BN is designed to predict the health of the ecosystem after the introduction of Stateless Ethereum.
High level view of the Stateless Ethereum model
Figure 1 shows the simplified view of the complete model, consisting of four sub-models: Block creation, Witness creation, Ethereum network, and Block propagation.
In each of the sub-models, we capture the key factors and their interactions in Ethereum mainnet and focus on the changes introduced by Stateless Ethereum.
Once all the information has been added to the model, we are then able to explore how the model behaves when certain parts of it change. More specifically, we see to what extent these changes potentially impact on the overall health of the Ethereum ecosystem.
We use publicly available Ethereum mainnet data, added with other data sources that include model output and expert knowledge in order to quantify the model.
Information flow between Stateless Ethereum sub-models
In the expanded view of the model (Figure 2), we see how information flows through the sub-models to determine the health of the Ethereum ecosystem. We created the Stateless Ethereum model as an object oriented Bayesian Network (OOBN). This way of designing a model is more modular and has properties of object program design.
For example, we can model a key factor as an ‘output node’ which means it is visible to other sub-models. This means the key factors that are quantified in a model (ellipse with solid line) can be used in another sub-model by having a placeholder or ‘input node’ (ellipse with broken line) for that factor.
In the next sections we describe the sub-models that constitute the combined model (Figure 1). We discuss the challenges and techniques that we used to develop and quantify these sub-models.
Building the Ethereum network BN sub-model
The Ethereum network model has five key factors. Three of them are block producer?, node bandwidth and network latency, also referenced in other sub-models. The place holders for these factors in other sub-models are shown as ellipses with broken lines.
We treat all Ethereum nodes as being either miners, i.e. block producers or “semi-stateless” nodes that do not produce blocks. “Semi-stateless” nodes have a varying degree of “statelessness” so that all full nodes and archive nodes in Ethereum mainnet will be classed as “semi-stateless” nodes.
For each of the factors in the model, we need a probability distribution across the various states that the factor can be in. That means that we attach a table of probabilities, known as a conditional probability table (CPT) to each factor in the model.
Block producer?
For Block producer? we have to estimate the proportion of all Ethereum nodes that are miners and do this by using data from Ethereum mainnet. We calculated the proportion of distinct public address keys that have received miner or uncle rewards. This gave us an upper bound that we provided to our various experts. Using their collective knowledge, they estimated the percentage of miners to be 1.0%.
Node bandwidth
Node bandwidth enables fast propagation of blocks through the Ethereum network. This is particularly important to miners. We assigned three levels of bandwidth: businesses and hosting nodes are deemed to have high bandwidth, colleges and residential nodes as having medium bandwidth, and all other categories were assigned a low bandwidth. The proportions were calculated using data from ethernodes.org. The data collected by ethernodes.org are voluntary and represent only a subset of all the nodes in the Ethereum ecosystem. Experts assisted in adjusting these proportions for semi-stateless nodes and we relied entirely on expert knowledge for miners since we had little information for them.
Node location
We grouped the countries where nodes are located into five regions: Europe, North America, China, Rest of Asia, and Rest of the world. The country information was obtained from ethernodes.org. Figure 4 below provides a visual representation of the five regions.
Five experts participated in the exercise for node location, using a range of strategies to estimate the probability distributions for mining and semi-stateless nodes, including ranking the locations and using the data from ethernodes.org as a baseline to vary for miners.
Peer location
Miners are likely to have direct connections with other miners to ensure efficient and fast propagation and receipt of blocks, and they may have a preference for peers that are geographically co-located.The choice of location of peers for miners may depend on other factors that are more difficult to evaluate, such as connectivity and trust. We therefore concluded that Peer location is influenced by both the location of the connected node and whether the connected node is a miner. However, this information is not readily available. Consequently, we had to rely entirely on experts with domain knowledge to quantify peer location.
Network latency
To quantify Network latency we used GNU ping data from Wondernetwork. Each row in the dataset contains an average, standard deviation, minimum and maximum of 30 pings between two cities. There are one or more entries (rows) for each combination. To model the latencies between various source and destination regions, we used this dataset to calculate the CPT entries in a number of steps and used inverse-variance weighted means to take the between and within city and region variation into account.
The data from Wondernetwork had to tie back to the five regions used for node and peer locations. The approach we took was to nominate a city for each country that we assessed to be representative of that country. We then grouped the countries that were running several nodes into a region to be representative of that region. For example, there were 40 countries in the Europe region. We ended up choosing eight to represent the region: Finland (Helsinki), France (Paris), Germany (Frankfurt), Ireland (Dublin), Netherlands (Amsterdam), Russia (Moscow), Switzerland (Zurich) and the United Kingdom (London).
Building the block creation BN
We built the initial version of the block creation model structure based on our understanding of the current block creation process in Ethereum.
We then extracted the data from blocks that were mined during 26-30 November 2019. As can be seen in Figure 5, we read data such as block creation time, number of transactions per block, difficulty and more. The total number of blocks in this period was 226,545 blocks.
We chose these blocks because we created witnesses for them when we implemented the Stateless witness specification (See the Witness creation BN model below).
We ran multiple structure learning algorithms to explore the merit of various proposed model structures. As input to the learning exercise we used the block information. Hugin Expert, the software modelling tool we used to develop the model, has several pre-coded algorithms available. We considered both general and structure restricted methods.
The output from the learning exercises resulted in slight modifications to the initial structure (Figure 5).
Building the Witness creation BN sub-model
We implemented the Stateless Ethereum witness specification in a fork of Hyperledger Besu, creating witnesses for 26,595 blocks. We recorded the size and creation time for each witness.
These are the same blocks that we used to build the block creation model.
The dependencies between witnesses and blocks are shown in Figure 6. They were determined using a combination of logic, e.g. the bigger the size of the witness being created, the longer it is likely to take, and additional insights provided by running various model structure learning algorithms.
Once the structure was ratified, we used the witness and block information to learn the conditional probabilities.
Building the Block propagation BN sub-model
In the Ethereum network, nodes are connected to several peers to send and receive data packages in a timely manner. Nodes sync to the network via their closest connected peers, receiving missing blocks and processing them to update their world state. However, nodes can go offline, or may be affected by low bandwidth and/or high latency. In these situations, they would typically lag behind the head of the chain.
Currently, when a miner finds a valid block, it propagates the block through the network as quickly as possible. Another miner receiving this block will check its validity, i.e. validate the proof of work (PoW) in the block header, before abandoning their efforts at solving the cryptographic puzzle. They will propagate the block to their peers and then start building a new block on the validated block they have received, providing it has a higher total work than their previous block.
Nodes that do not produce blocks also validate the PoW in the block header before sending it to their peers. Thereafter they replay the transactions in the block, they update their world state and wait to receive new blocks from the network.
In Stateless Ethereum we will have additional data packages and witnesses that need to be passed around with the blocks that they are associated with.Five of the factors in the block propagation BN model are part of other Stateless Ethereum sub-models. These are shown in Figure 12 as ellipses with a broken line: Block creation time, Witness creation time, Node bandwidth, Network latency and Block producer?. We therefore only need to create CPTs for the remaining five nodes: Uncle rate, Block propagation time, Block and witness processing time, Node status and Node keeps up with head of the chain.
Uncle rate
To calculate the marginal uncle rate probabilities, we checked the daily uncle rates recorded by etherchain.org and Alethio. Although Alethio is no longer updating their databases, the historical information is still available. This means that we can generate reports from their reporting portal using the historical data. These two data sources used two different calculations for uncle rate. etherchain.org used (1) and Alethio (2):
etherchain.org used (1) and Alethio (2). It does not really matter which one is used, as long as it is used consistently to calculate the marginal distribution for daily Uncle rates.
Block propagation time
Once a valid block has been found by a miner, it is propagated through the network so that all nodes are able to verify that it is a valid block and update their world state. Nodes are connected to several peers to send and receive data packages. Nodes may go offline or be affected by low bandwidth or high latency which will cause them to be lagging behind the head of the chain.
They are able to sync to the network via their closest connected peers to receive the missing blocks and process them to update their world state.
We collected block propagation times as reported on ethstats.io and ethstats.net. Contribution of block propagation times to these websites are optional and do not represent all of the Ethereum network. Silva et al (2020) conducted a month-long experiment from April 1st 2019 to May 2nd 2019. They collected Ethereum network data, including block propagation times between the nodes they were running in geographically diverse settings. The resulting datasets and code are available from Kaggle, and the links are listed on their webpage, angainor.science/ethmeasure. We combined information from these three data sources for the initial prior probabilities, taking into account that changes in node latency and bandwidth will have an effect on block propagation time. These factors have been taken into account in block propagation time and its effect on uncle rates.
The extent to which they influence block propagation time came from experts.
Block and witness processing time
We aggregated the combined block and witness processing time, as the sum of witness creation time and block creation time. The assumption therefore is that these times are additive.
Node status
We now need to quantify the effect that block propagation times have on node status for mining and non-mining nodes in the network. In other words we have to determine the probability that a node is offline, syncing, or updated. To do this, we used our primary empirical data source, ethernodes.org, as a baseline for experts to estimate the CPT entries.
Node keeps up with the head of the chain
The current status of a node provides some insight into the ability of a node to keep up with the head of the chain. If the node status is ‘up to date’, the node has synced successfully with the chain, but we do not know how it achieved this. For example, was it after joining a proposed sync protocol, or from processing the next block and witness. If the node is busy syncing, the question remains whether the node will be able to ‘catch up’. If the node is offline, the ability of the node is more opaque because we do not know if the offline status is due to difficulty keeping up to date with the head of the chain, whether the node was decommissioned, or had another reason for being offline.In addition, the time it takes to propagate blocks through the network will affect the ability of a node to keep up with the head of the chain. We consulted with experts to obtain the conditional probabilities for node keeps up with head of the chain. The resulting CPT entries reflect their combined input.
The combined Stateless Ethereum model
Now that we have an initial quantification of the four sub-models, we only need to quantify the final outcome - the health of the Ethereum ecosystem.
The health of the Ethereum ecosystem is dependent on uncle rate and node keeps up with head of the chain (Figure 2). Whether these two key factors are good indicators of the overall health of the Ethereum ecosystem is open to debate, but the consensus among experts was that they were good indicators.
We are now ready to run the combined model.
Read the final post of this series next Wednesday, October 26th, for more explorations into Stateless Ethereum where we will run the Stateless Ethereum model and the four sub-models.
If you would like more information about the project, please get in touch with me via email.
References
V. Buterin, “The Stateless Ethereum Concept”, 2017.B. Edgington, “What’s New in Eth2 – 10 January 2020”, 2020.A. E. Gencer, S. Basu, I. Eyal, R. Van Renesse, and E. G. Sirer, “Decentralization in Bitcoin and Ethereum Networks, 2018.G.I. Hotchkiss, “The 1.x Files: The State of Stateless Ethereum”, 2019.F.V. Jensen and T. D. Nielsen, Bayesian Networks and Decision Graphs, Second Edition. Springer New York, 2007. https://doi.org/10.1007/978-0-387-68282-2U. B. Kjærulff and A. L. Madsen, Bayesian Networks and Influence Diagrams, Second Edition. Springer, 2013.B. G. Marcot and T. D. Penman, “Advances in Bayesian network modelling: Integration of modelling technologies,” Environmental Modelling and Software. 2019.R. E. Neapolitan and X. Jiang, Artificial Intelligence : With an Introduction to Machine Learning, Second edition. Boca Raton, FL: Chapman and Hall/CRC, 2018.P. Silva, D. Vavřička, J. Barreto, and M. Matos, “Impact of Geo-Distribution and Mining Pools on Blockchains: A Study of Ethereum”, in 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), 2020, pp. 245–252.