Relay Mining: Incentivizing Full Non-Validating Nodes Servicing All RPC Types

Distributed ledgers (blockchains) are often reduced to the problem of Byzantine Fault Tolerant (BFT) State Machine Replication (SMR) [5]. Discussions about scalability typically focus on increasing throughput — the capacity to write more data to the ledger without compromising safety and liveness. This challenge led to the formulation of the Blockchain Scalability Trilemma, which assesses the trade-offs between scalability, decentralization, and security of a blockchain [14].

When evaluating the scalability of a Layer 1 (L1) blockchain, key metrics include Transactions-Per-Second (TPS) and Time-to-Finality (TTF), which provide direct insights into the network’s capacity and usage, as illustrated in Table  1.

The constraints of limited write capacity lead to on-chain auctions, often analyzed through the lens of Maximal Extractable Value (MEV). The need for efficient transaction ordering has introduced additional roles like Proposers and Builders, enhancing the ecosystem’s focus on scaling data throughput rather than data consumption [18] [15].

Despite advancements in addressing the Scalability Trilemma to manage, verify, and incentivize writes, the predominant type of requests made by application developers are reads. Table. 2 highlights the substantial traffic managed by major node providers in 2023, emphasizing the billions of daily requests, mostly reads, which present challenges not addressed by BFT replicated state machines.

Accessing blockchain data, crucial for operations like those described in the Simple Payment Verification [23], typically requires one of the following infrastructure components:

1. 1.

   Full Nodes: Synchronizing a full node to maintain a complete, locally verified copy of the ledger.

2. 2.

   Light Clients: Acquiring headers and proofs just-in-time from other full nodes.

3. 3.

   RPC Providers: Relying on a third party to retrieve data via an RPC request.

Options (1) and (2) often face practical limitations for widespread application use. Although option (3) has evolved into a robust Web2 SaaS-like ecosystem, it depends on provisioning and maintaining scalable infrastructure, while managing off-chain payments and Service Level Agreements (SLAs) in a more traditional and permissioned environment. Fig. 1 illustrates the operational models commonly adopted by decentralized Applications (dApps) today using these methods.

This paper introduces the Relay Mining algorithm, addressing the aforementioned needs. With prospects for future expansion into tokenomics and the duality between centralized Gateways and permissionless hardware operators, we also outline the RPC Trilemma. Illustrated in Fig. 2, this trilemma involves selecting RPC providers based on a trade-off among Reliability, Performance, and Cost. While our optimistic crypto-economic model incentivizes rate limiting and read request servicing, addressing just-in-time quality of service remains beyond this paper’s scope.

Most rate-limiting algorithms can be categorized as either Token Bucket algorithms (e.g., Leaky Bucket) or Window-based algorithms (e.g., Fixed Window, Sliding Window) [24]. Much of the existing work and literature that extends these to Distributed Rate Limiting (DRL) was captured in [21] [25], with two primary goals: 1. Finding a tradeoff between rate-limiting accuracy and communication overhead between brokers, 2. Reducing the DRL penalty on the end-user in exchange for accuracy. Although these approaches are valuable, they assume that the brokers or service providers, despite being geographically distributed, are not decentralized in terms of ownership and assume non-Byzantine guarantees.

Although the solutions discovered by the team at Washington University in St. Louis [21] do not directly apply to Relay mining, their formulation, as shown in Section 5, is relevant. They distilled common Token Bucket rate-limiting algorithms into two key parameters when managing communication between Clients and Brokers:

• $\bullet$

  r: The rate at which tokens are generated. This bounds the long-term rate of message services.

• $\bullet$

  b: The maximum number of tokens that can be accumulated. This bounds the maximum burst of messages that can be sent.

Their work on Scalable Real-Time Messaging (SRTM) encapsulated the following principles in reducing the Distributed Rate Limit (DRL) penalty:

• $\bullet$

  Concentration: Identification of the smallest number of brokers for message servicing to meet the network’s Service Level Objectives (SLOs).

• $\bullet$

  Max-min: Maximization of the minimum workload assigned to each broker.

• $\bullet$

  Correlation-awareness: Assignment of publishers to brokers to minimize inter-publisher correlation and reduce message burstiness.

To the authors’ knowledge, no other multi-tenant decentralized RPC node provider network currently operates in production. Centralized node operators such as Alchemy employ subscription tiers and compute units to manage rate limiting. This strategy, however, relies on centralization and does not necessitate on-chain proof and verification [1]. Compute units measure the total computational resources that applications utilize on platforms, rather than tallying individual requests. Another protocol in development, Lava, also intends to implement compute units for rate limiting [6], but details of this implementation remain undisclosed. The lack of an existing decentralized RPC provider in production underscores the unique and complex challenges involved in maintaining decentralization while achieving on-chain proof and verification.

Applications and Servicers must stake a certain balance and the service(s) that they plan to access and provide, respectively. Note that the maximum long-term rate that the Application can receive is proportional to $r$. This is shown in Step 1 of Fig. 3.

Any Session (a periodic of time determined by a specific number of blocks) determines which Servicers can receive a reward for servicing an Application’s request. This is done with the assumption of the Random Oracle Model and uses on-chain data as entropy [3] as shown in Step 2 of Fig. 3. Note that the maximum number of messages that can be serviced by each individual Servicer per session is $b$. Per the work described in [21], enforceable sub-buckets are not implemented and $r<\sum\limits_{l=1}^{k}r_{l}$. Due to the lack of guarantee that the sub-token count of each individual Servicer will be exhausted, a margin is provided, and a negative Application balance becomes theoretically possible. In this unlikely scenario, an Application would need to rotate the keys associated with its dApp in order to continue using the services provided by the network, and additional mitigations are reserved for future work.

Proposition 1 in [21] demonstrated that in the context of highly dynamic workloads, splitting tokens into sub-buckets $(r_{l},b_{l})$ such that $r=\sum\limits_{l=1}^{k}r_{l}$ and $b=\sum\limits_{l=1}^{k}b_{l}$ can never improve the running sum of message delays. However, building on the work of [25], who investigated probabilistic DRL, we can deduce that there is always an inherent tradeoff between absolute system accuracy and communication cost. Considering the possibility and added complexity of potential Byzantine actors in a multi-tenant, decentralized, and permissionless system, we opt for the tradeoff of accuracy in exchange for reducing coordination costs. In Algorithm 1, $RelayAccuracy$ represents the maximum overhead that can cause an Application’s stake to be negative at the end of a Session. This is shown in the first half of Step 3 in Fig. 3.

The second part of Steps 3 & 4 in Fig. 3 provides an overview of the Claim & Proof lifecycle implemented via a commit-and-reveal scheme.

Once a valid payable relay is serviced, assuming the $digest$ of $(SignedRequest,SignedResponse)$ using a collision-resistant hash function matches the difficulty for that chain/service as described in Section 6.4, it is committed for the purposes of volume estimation into a Merkle Tree Data Structure backed by a Key-Value storage engine. In order to avoid the compute overhead of tree re-balancing on every insertion, while maintaining efficient proof sizes, a Sparse Merkle Trie implementation [13], based on Diem’s Jellyfish Merkle Tree sparse optimizations [26], is used. The value stored on every leaf is the $Serialized(SignedRequest,SignedResponse)$ data structure, pointed to by the $digest$, whose bits act as the path to the leaf in the Trie. This approach guarantees space and compute efficiency, as well as preventing replay attacks through unique leaf guarantees without the need to maintain sorted leaves [28]. The only other modification that will be made to this Trie is that it will be implemented as a Sparse Merkle Sum Trie, so the sum of all the volume-applicable relays are committed to by the root [27] as shown in Fig. 4.

Several blocks after the Servicer submits a Claim to the tree Commitment via an on-chain transaction, there is a time window during which it must also reveal its proof of a randomly selected branch from the tree. Since the tree is not complete, the leaves are not indexed, and the set of all leaves is unknown to anyone but the Servicer’s local state, a random branch must be requested through other means. Using on-chain data (e.g., Block Hash) determined after the commitment, a random set of bits equal to the key’s length is generated in the Random Oracle Model [3], and the closest membership proof of an existing leaf that can be found must be revealed and submitted. For example, if the random set of bits is $0b0001$, the tree is traversed until it retrieves the membership proof for Leaf 3 in Fig. 4 with the key $0b0011$.

In a decentralized network where the exact count of processed relays is not tracked, we have to estimate the actual number of relays from sampled data. Consider the number of observed claims $C_{b}$ for a specific blockchain, denoted by bk, as a random variable following the binomial distribution:

Here, $R_{bk}$ represents the total number of processed relays and $p_{bk}$ denotes the hash collision probability given the current blockchain difficulty. We can then derive the value of $C_{bk}$ as follows ¹¹1For clarity, the subscript ${bk}$ is dropped in the remaining part of this work. Unless otherwise stated, all variables should be interpreted as per-blockchain.:

This estimation is particularly accurate for large numbers of trials and higher probabilities [4], a scenario that is not difficult to achieve in the context of relay mining. The difficulty (and hence $p$) is controlled by the expected number of claims per block and the number of relays $R$ is typically very high  ²²2As per our observations, refer to section 9.1 for details..

The proposed method for difficulty modulation follows Bitcoin’s approach [23], which uses a proportional control of an average of the controlled variable to adapt the current hash collision probability [19].

The modulation of difficulty can be described by algorithm 2. The method involves tracking the number of estimated total relays, denoted as $R_{ema}$, and modulating the hash collision probability $p$ to reach a target number of claims $T$. The Exponential Moving Average (EMA) parameter $\alpha$ and the number of blocks between updates $U$ control the responsiveness of the algorithm, or the speed at which the difficulty adapts to new relay volumes.

The values assigned to these variables are not fixed and are estimated based on empirical observations. They are subject to change to accommodate the dynamic nature of relay volumes.

A key component of the protocol method is the correct estimation of work performed by a dApp. This estimation is crucial for accurately processing the service payments from the dApp, which involves token burning, and for rewarding the Servicers, which involves token minting.³³3For simplicity, we assume a one-to-one mapping from an on-chain Application actor to a single dApp making RPC requests, though in theory, multiple dApps could leverage the key of a single Application.

As explained in Section 6.5, the difficulty modulation relies on estimating the total relays per block on a given chain, where each chain can have multiple dApps. Given that the total number of relays $R$ is distributed among $A$ staked dApps, it is important to consider how edge cases could influence the bias and variability of the dApp relay volume estimation.

An experiment was conducted to examine this. Using a target of $T=10^{4}$ claims per block, the variability and bias of the estimated number of relays $R_{dApp}$ were calculated. The difficulty $d$ (inverse of hash collision probability $p$) ranged from $1.25$ relays per claim to $1000$ relays per claim, and the dApp participation $v$ ranged from $0.1\%$ to $10\%$ of total blockchain traffic. For each test point, a total of $I=10^{5}$ draws from the resulting variable $x\sim B(R,v,p_{b})$ were sampled. The bias and variability of the estimated dApp traffic were then calculated as follows:

then:

and

The resulting bias and variability are illustrated in heat maps in Fig.5a and Fig.5b, respectively. We observe that the bias is close to zero across most of the sample space. Only when the number of $R_{\mbox{dApp}}$ is extremely low does bias become noticeable, but even then it remains above $-5\%$. Conversely, variability is higher, particularly when the dApp participation drops below $1\%$, under which conditions is grows rapidly.

Since its genesis on October 22, 2021, up to the current date (May 10, 2023), Pocket Network has processed over 465 billion successful relays. During this period, the number of served relays per day increased from approximately 1.5 million to 1.5 billion, with a peak of 2 billion on May 8, 2023. The total relay traffic is composed of an increasing number of blockchains, currently supporting 50, distributed over 14 gateways, and over 12 major, with many minor, infrastructure providers across all continents. The performance from May 3, 2023, to May 10, 2023, on the dominant blockchains is presented in table 4.

The network is composed of 20,000 nodes; however, this number does not correlate with the number of deployed blockchain nodes. The current version of the protocol cannot verifiably prove the real number of blockchain nodes, as the Servicers are permissionless, but a rough estimate can be obtained through the nodes’ service domains. The largest Servicer group has approximately 5,000 nodes (about 25% of the network), followed by two others with around 2,500 nodes each (about 12.5% of the network each). Then, the number of nodes by domain decreases. Around 90% of the network is held by 14 independent domains. Assuming no blockchain node is shared among node runners ⁴⁴4This is a fair assumption given the competitive play between node runners. and that each node runner has at least two nodes per staked blockchain ⁵⁵5Accounting for redundancy or geographical distribution of blockchain nodes., the Pocket Network has more than 30 independent blockchain servers on each of the main served blockchains. It is important to note that this is only an estimation; however, the number is significant in terms of decentralization and reliability.

Fig. 6 illustrates the interaction and responsibilities between the various protocol actors in Pocket Network. It is important to note that in the current, live iteration of the protocol, the Portals and the Watchers are off-chain and consolidated as a single entity. The roles of all the actors are outlined below. In the context of Relay Mining, the key item to note is that Applications pay for access to RPC services, and Servicers earn in exchange for handling those requests.

• $\bullet$

  Validator - Validates BFT state transitions of the distributed ledger

• $\bullet$

  Servicer - Provides access to an RPC service and earns rewards in native cryptocurrency

• $\bullet$

  Watcher - Makes periodic Quality of Service (QoS) checks of Servicers

• $\bullet$

  Application - Pays for access to RPC service in native cryptocurrency

• $\bullet$

  Portal - Optionally proxies requests on behalf of the Application and provides secondary off-chain services

This is the expected normal behaviour, where the number of relays by block stay almost constant or varies with low frequency. A blockchain that had this behaviour in the observed period of $3000$ blocks, from height $91000$ to $94000$ ($2023-04-08$ to $2023-05-07$) was the Polygon Mainnet. In Fig. 10 a close-up of the process can be observed.

In this period the average target deviation was of $0.7\%$, with a peak target deviation of $|107\%|$. The accumulated error resulted in a total of $20639$ extra claims, over $3000$ blocks. The average volume estimation error was $>0.00\%$ with a peak of $|4.17|\%$.

To illustrate this case we use the Ethereun data over the blocks $93775$ to $93950$, this is from $2023-05-05$ to $2023-05-07$, during this period the volume of the blockchain processed in the Pocket Network raised from $2.9\times 10^{6}$ to $1.1\times 10^{7}$. The process was fast ⁶⁶6Compared to normal (non-step) increases observed in the network. and steady. In Fig. 11 a close-up of the process can be observed.

In this period the average target deviation was of $6.2\%$, with a peak target deviation of $|44.6\%|$. The accumulated error resulted in a total of $108580$ extra claims, over $175$ blocks. The average volume estimation error was $-0.02\%$ with a peak of $|3.04|\%$.

An step drop in relays occur when a major source of relays stop requesting data. This effect was observed at height $90772$ ($2023-04-05$) for the Harmony Shard 0 blockchain, where the traffic dropped from $273\times 10^{3}$ to $21\times 10^{3}$ in less than four blocks. In Fig. 12 a close-up of the process can be observed.

In this period the average target deviation was of $60.2\%$, with a peak target deviation of $|95\%|$. The accumulated error resulted in a total of $264717$ less claims, over $44$ blocks. The average volume estimation error was $-0.21\%$ with a peak of $|5.21|\%$.

This case is typical when a new chain is introduced in the ecosystem, the evolution number of relays resembles an step function. This behaviour was observed recently, at height $91532$ ($2023-04-13$) for the blockchain Polygon Archival. This blockchain moved from $1120$ to $276\times 10^{3}$ relays per block. In Fig. 13 a close-up of the process can be observed.

In this period the average target deviation was of $170.32\%$, with a peak target deviation of $|789\%|$. The accumulated error resulted in a total of $408767$ extra claims, over $24$ blocks. The average volume estimation error was $0.07\%$ with a peak of $|3.45|\%$.