  Relay Mining presents a scalable solution employing probabilistic mechanisms,
crypto-economic incentives, and new cryptographic primitives to estimate and
prove the volume of Remote Procedure Calls (RPCs) made from a client to a
server. Distributed ledgers are designed to secure permissionless state
transitions (writes), highlighting a gap for incentivizing full non-validating
nodes to service non-transactional (read) RPCs. This leads applications to have
a dependency on altruistic or centralized off-chain Node RPC Providers. We
present a solution that enables multiple RPC providers to service requests from
independent applications on a permissionless network. We leverage digital
signatures, commit-and-reveal schemes, and Sparse Merkle Sum Tries (SMSTs) to
prove the amount of work done. This is enabled through the introduction of a
novel ClosestMerkleProof proof-of-inclusion scheme. A native cryptocurrency on
a distributed ledger is used to rate limit applications and disincentivize
over-usage. Building upon established research in token bucket algorithms and
distributed rate-limiting penalty models, our approach harnesses a feedback
loop control mechanism to adjust the difficulty of mining relay rewards,
dynamically scaling with network usage growth. By leveraging crypto-economic
incentives, we reduce coordination overhead costs and introduce a mechanism for
providing RPC services that are both geopolitically and geographically
distributed. We use common formulations from rate limiting research to
demonstrate how this solution in the Web3 ecosystem translates to distributed
verifiable multi-tenant rate limiting in Web2.
