IC topology - Node diversification part II

TL;DR

This post explores metrics and models for node decentralization and presents strategies for future node onboarding and offboarding decisions.

  • Metrics: A recap of key metrics for node decentralization, in particular the Nakamoto coefficient.
  • Modeling: Introduction of an optimization model designed to reach decentralization targets with a minimum node count.
  • Community involvement: After incorporating community feedback we aim to proceed with a motion proposal for NNS agreed rules for node onboarding.

For an introduction and additional background, please refer to the previous post on node diversification.

Recap of problem statement

The Internet Computer (IC) operates on physical node machines and achieves decentralization by partnering with multiple independent node providers. This decentralization reduces risks of central control, failures, and censorship. However, there is a trade-off: a high degree of decentralization comes at a cost in the form of node provider rewards to account for hardware, maintenance, and operations.

In order to strike the right balance between network size & cost and the degree of decentralization, the IC needs to tackle two aspects

  1. Establishing a Target Topology: This involves defining the number of subnets and their respective sizes, aligning with anticipated future demand. It also involves setting decentralization targets.
  2. Optimization: Given a target topology, optimize between node rewards (onboarding of additional new nodes and rewards for existing nodes) and decentralization.

This blog post explores metrics and models for assessing node decentralization, along with suggested strategies for future node onboarding and offboarding decisions.

Metrics of decentralization of Nodes in a Subnet

Definition of the Nakamoto Coefficient

The Nakamoto Coefficient traditionally signifies the smallest number of entities required to control 51% of resources in a decentralized system. It provides a measure of how centralized or decentralized control is within that system.

In the context of IC subnets, an adjusted definition is more meaningful. According to the IC consensus protocol, if a third (or more) of the nodes behave maliciously, they can stall a subnet. Hence, we define the Nakamoto Coefficient as the smallest subset of entities corresponding to a specific characteristic (such as node provider, data center, country, etc.) that collectively control at least a third of the nodes in the subnet. Taking the “node provider” characteristic as an example, it denotes the fewest number of node providers such that their cumulative node count is at least one-third of the subnet size.

More formally we can define the Nakamoto coefficient as follows

Given:

  • N is the total number of nodes in a subnet.
  • χ is a characteristic of the node (e.g., node provider, country, data center, etc.).
  • ξ(χ) denotes the number of nodes with the characteristic χ

Then the Nakamoto Coefficient for the characteristic χ is

NC_χ(N) = |P|

where P is the smallest subset of unique χ values such that:

sum(ξ(χ_i) for χ_i in P) ≥ N/3

Alternative Metric: Subnet Limit

A more straightforward (but also less precise) metric for node decentralization is the subnet limit, denoting the maximum instances a specific characteristic can appear within a subnet. For instance, if the subnet limit for the “node provider” characteristic is 1, each node provider within the subnet is unique.

Connection between Nakamoto Coefficient and Subnet Limit

When each node’s characteristic is unique within the subnet, i.e. subnet limit = 1, the Nakamoto Coefficient NC_χ(N) is ceil(N/3), where ceil(x) is the ceiling function, which rounds x up to the nearest integer. This value represents the maximum Nakamoto Coefficient achievable. In the context of a 13-node subnet, this coefficient becomes ceil(13/3) = 5.

If each characteristic can appear up to twice in a given subnet, i.e. subnet limit = 2, the Nakamoto Coefficient will be reduced. In this case Nakamoto Coefficient NC_χ(N) is ceil(N/(2*3)). Taking the 13-node subnet as an example again, the Nakamoto Coefficient becomes ceil(13/6) = 3.

Modeling approach

In this section, we outline a mathematical model for optimizing between node rewards (including onboarding new nodes and compensating existing ones) and network decentralization. We employ linear optimization for this purpose, describing the model input, applied constraints, and objective functions. Model results will be discussed in a later section.

Optimization Strategy

Starting with a specified decentralization goal for the network, this method calculates the least number of new nodes or the minimal node rewards necessary to meet this goal.

Model Input

  • Available Nodes and Their Characteristics: Represents available resources. Every node possesses instances of characteristics influencing its allocation. Nodes can either be existing or potential additions (e.g., from a future node provider).
  • Target Topology: Describes the desired network structure, detailing the count and size of subnets. For every characteristic, it specifies a decentralization goal, which could be the target Nakamoto coefficient or a subnet limit.

Formulation of Constraints

  • Nodes to Subnet Allocation Constraints: Create a matrix mapping nodes to subnets, adhering to:
    • Uniqueness: Each node can be linked to just one subnet.
    • Subnet Fill: Each subnet must have its designated number of nodes.
  • Characteristic Constraints: For every characteristic (e.g. node provider), construct a ‘characteristic matrix’ that maps the instances of the characteristic to subnets. The matrix values are derived from the node-to-subnet mapping. This matrix must respect:
    • Subnet Limit: If a subnet limit is set, ensure that the entries of the characteristic matrix are bounded by the subnet net limit (e.g. individual node providers can appear only twice within a subnet).
    • Nakamoto Coefficient: If a Nakamoto coefficient target NC (e.g. five) is set, ensure that every possible subset of instances of this characteristic, with sizes up to and including NC, should have control over less than one-third of the nodes within the subnet (e.g. all subsets with up to five node providers should not control a third of the nodes). Note: This introduces numerous constraints.

Objective Function

The objective is to minimize the required nodes (or node rewards) to achieve the given target.

Suggested Process for Applying the Model

We propose utilizing the previously presented model framework for making informed decisions regarding future node onboarding as follows:

Establishing a Target Topology

Context

  • Target Subnet structure: This involves determining the number and respective sizes of subnets, aligned with anticipated future demand.
  • Decentralization Targets: Per subnet, decentralization targets should be set, utilizing either a Nakamoto coefficient or a subnet limit. The node topology matrix, described in the previous forum post, assists in evaluating achievable targets.

We propose that the NNS agrees on a single target topology at any given time. Various decisions, such as whether to onboard additional nodes, can be derived from this agreed-upon topology. As the IC evolves, updated target topologies could be proposed to the NNS, ensuring continual alignment with the network’s development and needs.

Optimizing Node Allocation

Utilizing the defined target topology, the model can determine the minimal number of nodes, or alternatively, the minimal amount of rewards required for achieving the target topology.

Deciding on Node Candidates

Utilizing the model, the following can be analyzed given a set of current nodes and node candidates:

  • Effectiveness of Candidate Nodes: Can node candidates 1:1 reduce the number of additional nodes needed?
  • Node Relevance of Existing Nodes: Which existing nodes are not utilized to achieve the decentralization target (and thus could potentially be offboarded) ?

Modeling Results

Utilized Model Inputs

Suggested Target Subnet Structure

The following table specifies the type, number, and size of anticipated subnets. The column labeled “SEV” indicates whether the subnet is designated to run on generation 2 SEV machines, enhancing protection against malicious actors. This table serves as a suggestion for the Subnet Target Structure for the next 6-12 months. The number of subnets is based on current and anticipated demand. There are some special subnets that are dedicated to specific use cases, e.g. ECDSA signing. The sizes of the subnets were chosen depending on the sensitivity of the services/dapps running on them, e.g. the NNS subnet has the highest sensitivity and is thus proposed to be larger than app subnets.

Subnet type # Subnets # Nodes Total SEV
NNS 1 43 43 no
SNS 1 34 34 no
Fiduciary (used as ECDSA signing today) 1 28 28 no
II 1 28 28 yes
ECDSA signing (new) 1 28 28 yes
ECDSA backup (new) 1 28 28 yes
Bitcoin canister 1 13 13 no
European Subnet (new) 1 13 13 yes
Swiss Subnet (new) 1 13 13 yes
Application Subnet 31 13 403 no
Reserve nodes 120
Total 751

Note: The optimization model does not yet consider the adjusted country constraints required for the planned European and Swiss subnet.

Current nodes

The current node set, extracted from the IC dashboard as of September 7, 2023, totals 1151 nodes, with 84 of these being SEV nodes.

Candidate nodes

The analysis will incorporate candidate nodes from new countries, data centers, and data center providers. We assume that for every new country, there are 20 candidate nodes (5 node providers x 4 nodes per node provider), and that these candidate nodes are generation 2 SEV machines.

Proposed Decentralization Targets for further Analysis

From the previous blog post, we know that decentralization, considered on a standalone basis, is well-achieved for data centers and data center providers and near optimal for node providers. For the country characteristic the current node set shows a lower degree of decentralization.

In light of this, we propose the following decentralization targets for further analysis, each of which assumes compliance with the SEV requirement:

  • Decentralization Target 1: A subnet limit of 3 for all characteristics.
  • Decentralization Target 2: A subnet limit of 2 for all characteristics.
  • Decentralization Target 3: A subnet limit of 2 for country characteristic and 1 for other characteristics.
  • Decentralization Target 4: A stringent subnet limit of 1 for all characteristics.

Optimizing Node Allocation

Below, we share the results of applying the optimization model to the targets outlined previously. In this analysis, we focus on minimizing the node count of candidate nodes. In a second step, this could be enhanced to minimize node rewards instead.

Decentralization Target 1

The following bar chart illustrates node allocation per subnet, focusing on the country characteristic. Each bar corresponds to a subnet, sorted by size in descending order from left to right. Segments on a bar, sharing the same color, represent nodes from the same country, delineating current (blue) and candidate (red) nodes from a presumed 12 new countries. The number atop a bar reflects the Nakamoto coefficient of the subnet with respect to the considered characteristic (here country).

Decentralization Target 2

For the stricter decentralization target 2, enforcing a subnet limit = 2 for all characteristics, additional nodes are necessary. A total of 84 candidate nodes are required. We observe that candidate nodes are mainly assigned to the larger subnets on the left (NNS and SNS subnet), as well as to the SEV subnets (subnet number 4,5,6, 8,9).

Decentralization Target 3

For Target 3, 120 candidate nodes are required. The following table illustrates the allocation to subnets, this time using the characteristic node provider. In line with the target, we observe maximum decentralization only featuring unique node provider instances per subnet.

Decentralization Target 4

Achieving maximal decentralization across all characteristics necessitates 210 candidate nodes, sourced from 28 new countries.

Preliminary Conclusion

Relying on the suggested target topology and the provided model framework, our initial conclusions are as follows:

  1. Overall Node count: Utilizing the Target Subnet Structure, there are approximately 400 excess nodes, with a current total of 1150 nodes compared to the 750-node target. The excess applies in particular to Generation 1 nodes.

  2. Generation 2 nodes: There remains a need to introduce additional Generation 2 SEV nodes to fill the SEV subnets (e.g. ECDSA signing subnet).

  3. Decentralization target:

    • The node provider, data center, and data center provider characteristics, which already showcase a higher degree of decentralization, could adhere to stricter targets, demanding maximum decentralization (subnet limit = 1).
    • Currently exhibiting the least decentralization, it seems logical to, at least initially, set a comparatively weaker decentralization target for the country characteristic. This would permit the same country to appear up to twice in any given subnet (country subnet limit = 2).
    • To achieve this target (referred to as Target 3 above), an addition of 120 Generation 2 nodes would be necessary.
  4. Node provider bound: As a consequence of the proposed decentralization target, no single node provider should manage more nodes than the number of subnets (40). Taking into account that there are typically 14 nodes in a rack, we propose a slight adjustment to this criterion: No node provider should control more than 42 (3*14) nodes.

Suggested next steps

In the journey towards refining and implementing models for node decentralization, we suggest a progressive path with the following steps:

Inviting Feedback

  • Community Participation: We invite community members to offer feedback on the model for assessing node decentralization and the suggested strategies for future node onboarding and offboarding.
  • Model Sharing: We aim to share the prototype used to run the model and create the visuals showcased in this blog, providing a tangible basis for feedback and collaborative refinement.

Motion Proposal

After consideration of the feedback, we plan to submit motion proposals that articulate

  • The principles and model guiding future decisions on node onboarding and offboarding.
  • A target topology for the next 6-12 months.

Further Refinements

  • Security Review: Should the decision be made to progress with the presented model framework, a security review of the prototype implementation will be required to ensure its robustness and reliability.
  • Strategic Enhancement: Beyond its initial capabilities, the model could be enriched to recommend strategies for re-assigning nodes effectively transitioning from the current to the target subnet allocation.
12 Likes

Thanks for the work done. Going through both parts, wanted to understand specifically your optimization model parameters and setting. What is the target function specifically? Max decentralization while best performance?

1 Like

Minimize the number of candidate (new) nodes, while achieving the decentralization targets, given in the form of subnet limits or Nakamot coefficients.

1 Like

I can’t help but feel like there are more pressing issues than on-boarding more Nodes:

What is your suggestion for the coming new NP, for example me?

1 Like

Please note: This proposal is about agreeing on a target topology and optimizing to the the target. Indeed, it is suggested that (as part of the target topology) we need 400 nodes less compared to what the IC has today.

5 Likes

Noted, this was shortsighted on my part, I should have done a complete review on the proposal rather than simply reviewing the TLDR & Problem Statement. Appreciate the update.

3 Likes

I think this is a great to help decide on a nodes-target based on decentralization.

However, it doesn’t take into account node hardware resources.

@bjoernek Could this lead to a situation where the decentralization target has been met based on the proposed Nakamoto Coefficient but, at the same time, for dApps to have already exhausted the available hardware resources? Or would that be settled elsewhere?

Hi all, please find here the prototype implementation of the IC topology optimization model.

1 Like

If the network capacity cannot cover the demand generated from dapps, then a revised target subnet structure (see table above) would need to be defined (e.g. add further subnets) and be approved by a motion proposal. The revised target subnet structure would then feed into the optimization model, as an input.

thank you for clarifying. voted in favor :slight_smile:

Good job on this whole topic, really nice!

2 Likes

Hi all, the suggested model framework has been submitted as a motion proposal. Please have a look and vote!

1 Like

It seems to me that there are considerable technical difficulties in signing t-ECDSA on AMD-SEV nodes, can this be cleared up? Also, am I correct in assuming that subnets in Switzerland and certain European countries and regions are intended to protect privacy in compliance with GDPR?

I wanna be node provider and now talk with data centers in Portugal, Spain, Poland , in this countries any np, how new topology affect me and can i be np?

Can a similar optimization be made for staking interest in terms of making a positive contribution to the tokenomy?

dear official,
This proposal had been put into practice. One of the aims of the proposal was to optimize the network and eliminate redundant nodes. However, recently, many node addition requests and data center addition requests have been put to vote in NNS. It is not clear whether these demands are requests for adding a new node or increasing capacity such as storage and processor power in the existing node.More descriptive information should be added to the node addition requests, so that we the voters, can make an easy decision.
I hope the node optimization is rejecting offers to locations that are not needed. Otherwise, by voting cannot prevent the formation of new nodes in unnecessary locations of the network.

Thanks for the sharing and insight!

After reading the latest post, I still have some questions:

I saw the words in this posts:

  1. country subnet limit = 2
  2. As a consequence of the proposed decentralization target, no single node provider should manage more nodes than the number of subnets (40). Taking into account that there are typically 14 nodes in a rack, we propose a slight adjustment to this criterion: No node provider should control more than 42 (3*14) nodes.

And I also noticed that there are more than 50 nodes in some countries which is not the rule according to previous doc.(no more than 50 nodes in one country)

SvenF replied me in the Element ICP community as below:

How to understand the conclusion from the above 3 statements?

  1. one country can only be involved in two Subnets?
  2. Within 2 subnetes in one country, it can only have no more than 42 nodes for each NP?

One quesion:
What is SEV nodes?

Thanks!

Lisa

@Lisa_Crato, to answer your questions:

  • a subnet limit of 2 per country means that in each subnets only 2 node machines can be located in the same country.
  • a node provider can have no more than 42 node machines, whether across all subnets.

SEV/SNP is additional security functionality on the AMD processors that is used by the IC network. So for a brief explanation AMD SEV Virtual Machine Support. Hence the hardware requirement for AMD processors on the Gen2 node machines.

Hope this answers your questions.

1 Like

very useful.
Thanks for your support as always!

Lisa

If you don’t mind sharing Lisa, which country are you looking into?