Time Towers

In this section, we discuss Time Towers, a key component of StateMesh's mechanism to ensure persistent, secure identities and verifiable metrics for node operators. We first introduce the concept of verifiable delay functions (VDF) and then explain how Time Towers work in detail.

tip

Time Towers facilitate the bootstrapping of nodes without reliance on traditional mechanisms such as token sales, node sales or airdrops, while simultaneously mitigating vulnerability to attacks.

This approach eliminates financial incentives to promote robust and fair network participation, enabling anyone to become a node operator.

Overview

Time Towers are StateMesh's mechanism to ensure persistent, secure identities and verifiable metrics for node operators. Time Towers are essentially puzzle towers that act as a proof of elapsed time leveraging verifiable delay functions (VDF). A VDF is a cryptographic delay function that is designed to be computationally intensive and time-consuming to reverse engineer, making it ideal for generating secure, unique identifiers for nodes. It cannot be parallelized, ahs has no substantial benefit by using more computational resources.

Each node operator locally executes a VDF to generate proofs at regular intervals, and these proofs are chained to build its Time Tower, i.e., each proof executes from the hash of the previous proof. In addition, StateMesh reconfigures nodes participating in consensus at regular intervals by punishing unwanted behavior, for example, eliminating failed nodes.

Time Towers are stored on the StateMesh blockchain, and each node operator can have only one Time Tower. The Time Tower is used to:

• identify the node operator and to ensure that the node operator is who they say they are.
• establish a persistent identity for the node operator across reboots and network failures.
• provide a tamper-evident record of the node operator's activity over time.
• provide a way to record node metrics and reward node operators for their contributions to the network.
• provide a way to punish node operators for malicious behavior.

The nodes which actively generate Time Tower proofs are given higher preference to execute Agent tasks. Though this approach has similarities to proof of stake (PoS), it does not rely on staking financial assets to establish identities.

Key concepts

• Miner: A node that generates Time Tower proofs.
• Node Operator: A miner that is elected as a node operator for the next epoch, or is a node operator in the current epoch.
• Cluster Owner: The creator of the StateMesh cluster, who is responsible for the operation and management of the cluster.

Verifiable Delay Functions

Verifiable Delay Functions (VDFs) are employed as a Proof of Time (PoT) mechanism to establish persistent identities. A VDF is a cryptographic primitive designed to impose a predetermined sequential computation time. It is defined as a tuple of three functions: $\text{VDF} = (\text{Setup}, \text{Evaluate}, \text{Verify})$:

1. $\text{Setup}(\text{security}, t) \rightarrow \text{pp}$ - This function initializes the VDF. It takes two inputs: a $security$ parameter and a time bound $t$. The output is a public parameter $pp$. These public parameters are specific to each participant and define the input space X and output space Y for the VDF.
2. $\text{Evaluate}(\text{pp,x}) \rightarrow \text{y,p}$ - This deterministic function executes a sequence of $t$ time-bound steps to compute $(\text{f:X} \rightarrowtail \text{Y})$. It takes as input the public parameters $\text{pp}$ and an element $x$ from the input space $\text{X}$, producing an output $y \in \text{Y}$ along with a proof of computation $p$. This function embodies the delay component of the VDF, ensuring a prescribed computational time.
3. $\text{Verify}(\text{pp,x,y,p}) \rightarrow \{\text{true}, \text{false}\}$ - A deterministic Boolean function that ascertains the validity of the output $y$ and its corresponding proof $p$, given the public parameters $pp$ and input $x$.

The $\text{Evaluate}$ function of VDF exhibits two fundamental properties:

1. Uniqueness: For any given input $x \in X$, there exists a unique output $y \in Y$ such that $f(\text{pp}, x) = (y, p)$. This property ensures that the evaluation function produces a deterministic and unique output $y$ for each defined input $x$. It is worth noting that while the output $y$ is unique, the accompanying proof $p$ may vary across different evaluations.

2. Sequentiality: The $\text{Evaluate}$ function requires a minimum of $t$ sequential steps to compute, regardless of the available computational resources or parallelization capabilities. This property guarantees that no parallel algorithm or randomized approach can produce the output in fewer than $t$ steps, effectively enforcing a predetermined delay in the computation process.

These properties collectively ensure the integrity and time-bound nature of the VDF, making it suitable for applications requiring verifiable time delays.

The final stage in the VDF construction involves the efficient verification of output and proof correctness. The most prominent algorithms for the $verify$ function are those proposed by Wesolowski and Pietrzak. For our VDF implementation, we have selected the Wesolowski algorithm due to its superior performance characteristics in the verification phase.

Time Towers are constructed through the sequential chaining of VDF proofs, thereby establishing persistent and verifiable identities for node operators within the network.

Proof of Time (PoT)

To establish persistent and verifiable identities for node operators, we introduce the concept of Time Towers. These structures extend the traditional notion of puzzle towers by incorporating Verifiable Delay Functions (VDFs). The utilization of VDFs addresses several sustainability challenges inherent in Proof of Work (PoW) puzzles, including vulnerability to mining attacks and environmental concerns associated with excessive energy consumption.

Time Towers constitute a sequential series of cryptographic proofs, each building upon its predecessor. The process of constructing these towers is formally referred to as Proof of Time (PoT) mining, with each participating node designated as a PoT miner. The collective set of miners forms the miner pool $M$, which is a subset of the total node set $N$, denoted as $M \subseteq N$.

In contrast to Proof of Work (PoW) algorithms, which are inherently parallelizable and probabilistic, PoT mining is characterized by its sequential and deterministic nature. The underlying Verifiable Delay Functions (VDFs) employed in PoT mining are resistant to parallelization, thereby negating any significant advantages that might be conferred by superior hardware configurations, such as GPUs.

The construction of a Time Tower involves the iterative extension of each proof from its immediate predecessor, resulting in a rigorously ordered sequence of computational work. This architecture facilitates the establishment of persistent, verifiable identities within the network. These identities are distinguished by their permissionless and non-forgeable attributes, achievable with minimal capital investment.

Time Towers serve as a tangible manifestation of Proof of Time (PoT), with the tower's height serving as a quantifiable metric of a miner's sustained participation in the network. This height not only demonstrates the miner's commitment to the network but also provides a robust criterion for evaluating and ranking potential candidates for inclusion in the Operator pool.

Each miner $m$ within the StateMesh network possesses a delay tower, denoted as $T_m = \{P_0, P_1, ...\}$. This tower comprises a sequence of proofs, where each proof $P_{n+1}$, with the exception of the initial proof $P_0$, is constructed upon its predecessor $P_n$, thereby demonstrating the computational work performed by the miner subsequent to its most recent proof $P_n$.

From an implementation perspective, the $setup$ and $evaluate$ functions are executed locally within the miner's node environment. The resulting proofs are subsequently transmitted to the blockchain for verification purposes. The chain validators are responsible for executing the $verify$ function to authenticate the validity of these proofs.

It is noteworthy that the security parameters $sec$, which serve as input for the setup function, are established and remain constant from the network's genesis, ensuring consistent security measures across all miners.

A node $f \in N$ transitions to miner status through the execution of the $setup$ function and the subsequent submission of its inaugural VDF proof, thereby initializing its miner state. The $setup$ function accepts as input the security parameters $sec$ and public parameters $pp$, which are utilized to generate the initial VDF proof. The public parameters encompass the cryptographic public key $pk_f$ and the IP address of the miner's dedicated machine. This process establishes an inextricable link between the public key and the Time Tower, rendering them non-transferable. The output of $setup$ is a set of signed parameters ($sig_f(params)$), which are subsequently submitted to the chain's transaction pool. Chain validators then assess these parameters to determine if they constitute a valid proof, and if so, update the ledger state accordingly.

A Verifiable Delay Function (VDF) proof $P_{k+1}$ is considered valid under two conditions:

1. It constitutes the initial proof $P_0$, accompanied by the requisite initialization parameters.
2. It is constructed upon the SHA-256 cryptographic hash of the most recent proof, denoted as $SHA256(P_k)$.

Furthermore, a proof is deemed valid if and only if it yields a positive result ($true$) when subjected to the $verify$ function. This rigorous validation process ensures the integrity and continuity of the proof chain within the Time Tower structure.

Upon successful validation of the initial proof $P_0$ generated by the $setup$ function, the node's miner state is initialized, thereby formally inducting the node into the miner pool $M$. Subsequently, each miner $m \in M$ engages in Proof of Time (PoT) mining, which entails the iterative local execution of the $eval$ function to generate and submit VDF proofs to the blockchain. The proof computation process, encapsulated within the $eval$ function, requires $t$ sequential steps, utilizing the cryptographic hash of the preceding proof as input to produce the subsequent proof. In essence, a node initiates its participation by executing the $setup$ function, which establishes the foundational element of its Time Tower. Following this initialization, the node assumes the role of a miner, continuously executing the $eval$ function to facilitate the progressive expansion of its tower structure.

When a node operator submits the output from executing $setup$ locally to the chain, the miner state of the node is initialized. The miner state $ms$ stores the following information:

• tower height, denoted by height
• the hash of the latest verified proof as hash
• the number of proofs submitted in the current epoch as num
• jailed to signify whether the miner is jailed or not
• the remaining sentence jail_sentence if it is jailed
• the metrics of the miner such as CPU, GPU, RAM and disk consumption

For all the sequential proofs $P_{k+1}$ submitted by the miner, on-chain validators use the following O(1) algorithms to check the validity of the proofs:

validVDFProof(addr, proof): bool
    if !isAuthorized(addr)
        return false

    result = false
    if validSignature(addr, proof) {
        ms = getMinerState(addr)
        if ms.hash === proof.previous_proof_hash and ms.height < proof.height {
            if VDF.verify(proof) {
                ms.height = ms.height + 1
                ms.num = ms.num + 1
                ms.hash = sha256(proof)
                resut = true
            }
        }
    }
    return result

The validation process commences with an authentication check to ascertain the miner's authorization to submit the proof, typically through signature verification. Subsequently, validators assess whether the submitted proof incorporates the hash of the previously verified proof, denoted as $sha256(P_k)$, and confirm that the proposed tower height exceeds the current on-chain record. The final step involves the execution of the verify function to authenticate the VDF proof's validity. Upon successful validation of all criteria, the miner's state undergoes an update. This update encompasses an increment in both the epoch-specific proof count (num) and the overall tower height (height). Additionally, the hash of the most recently verified proof is revised to $sha256(P_{k+1})$. This iterative process persists throughout the duration of the Proof of Time (PoT) mining phase.

The Time Tower mechanism establishes a persistent, non-transferable identity that demonstrates Proof of Time (PoT), requiring temporal investment and minimal resource allocation. However, the aforementioned design does not account for the potential presence of node failures, whether due to system crashes or more severe Byzantine behavior. To mitigate these challenges, StateMesh implements a periodic reconfiguration of the node operator pool for each cluster, coinciding with the conclusion of the chain's epoch. This reconfiguration process involves the penalization of non-conformant nodes through a jailing mechanism, while simultaneously rewarding nodes that exhibit correct behavior.

Jailing

To detect and mitigate non-compliant behavior, StateMesh employs a quantitative metric termed liveness, which serves as an indicator of a node's active participation within a cluster.

The liveness of a node is defined as the ratio of consecutive valid proofs submitted by the node during an epoch to the maximum possible number of proofs in that epoch. Formally, for a node $N_i$ in epoch $E$, the liveness $L(N_i, E)$ is expressed as:

$L(N_i, E) = \frac{\text{number of continuous valid proofs submitted by } N_i}{\text{maximum number of possible proofs in epoch } E}$

At the conclusion of each epoch, StateMesh performs a liveness assessment for all nodes. Nodes failing to meet a predetermined liveness threshold $\pi$ are classified as non-compliant and subjected to a jailing mechanism. Jailed nodes forfeit their node operator status for the subsequent epoch and incur a penalty period, denoted as $\phi$, measured in epochs. To regain operational status, jailed nodes must demonstrate consistent proof generation by submitting a threshold number $\tau$ of proofs in each epoch throughout the duration of their penalty period $\phi$, where $\phi$ is a globally defined constant.

The process of identifying and jailing non-compliant nodes is implemented through an O(n) algorithm, where n represents the cardinality of the node set $NS$ for a given cluster. The algorithm is structured as follows:

jailNodes():
    foreach addr in :
        ms = getMinerState(addr)
        // Check if threshold liveliness is met
        if LE(addr) <= tau {
            ms.jailed = true
            ms.jail_sentence = phi
            updateMinerState(addr, ms)
        }

Node sets

Following the implementation of the jailing mechanism for non-compliant nodes, the subsequent phase involves the selection of operator nodes from the candidate pool of miners, denoted as M. Initially, a subset is identified based on the specific requirements established by the cluster, encompassing factors such as CPU, RAM, disk capacity, and geographical region. This subset is designated as the miner set MS for a given cluster. A subset of miners from MS will be elected as node operators for the forthcoming epoch, contingent upon their successful mining of the threshold $\tau$ number of proofs in the current epoch E, which is recorded as num in the miner state. The process of extracting nodes from the miner set MS entails the exclusion of jailed miners and the resetting of the proof count num to zero for the impending epoch. This operation exhibits linear time complexity with respect to the cardinality of the miner pool M:

candidatesForNextEpoch(M): []
    NS = []
    foreach addr in M {
        ms = getMinerState(addr)
        if ms.num > tau & !isJailed(addr) {
            NS.append(addr)
        }
        ms.num = 0
    }

While all candidates within the node set NS meet compliance standards, the selection process is further refined to include only the top N performers. This refinement is achieved by ranking the miners in NS according to their respective tower heights. The rationale behind this approach is twofold: firstly, tower height serves as an easily computable and deterministic metric for quantifying the duration of a miner's active participation. Secondly, the linear nature of tower growth confers only a marginal advantage to genesis nodes when compared to Proof of Stake (PoS) mechanisms. Furthermore, the construction of time towers is characterized by its permissionless nature, necessitating minimal capital investment. The algorithm for proposing a new miner set NS is delineated as follows:

nodeSetForNextEpoch(M): []
    NS = []
    i = 0
    C = candidatesForNextEpoch(M)
    C.sort(by_tower_height)
    while i < MAX_NODES and i < len(C) do {
        val = C[i]
        NS.append(val)
        i = i + 1
    }
    return NS

Conclusion

The Time Towers mechanism offers several advantages that merit consideration. Firstly, it significantly reduces barriers to entry by minimizing capital requirements; the ability to mine Time Towers is accessible to any individual with access to a CPU. Of particular note is the environmental sustainability of Proof of Time (PoT) mining for time towers, which utilizes minimal computational resources. This efficiency is attributed to its sequential nature, which precludes any advantages from parallelization.

Moreover, the linear growth characteristic of time towers results in a gradual diminution of the initial advantage held by genesis peers over time. This feature promotes long-term equity in participation opportunities for all interested parties.