tldr: Request for papers

Pricing state growth

Apply Here

Pricing state growth

Public blockchains that require network participants to store global state are faced with a daunting challenge: state growth. As these networks become more popular, the size of the state monotonically increases. This increase places a growing burden on validators, who must access the relevant state of each transacting party, verify signatures, check for double-spending, and update respective states. As the size of the chain’s state increases, this process becomes increasingly difficult, potentially outpacing validators’ limited hardware resources. To date, there has been little theoretically-grounded work focused on dealing with the state growth problem.

Problem statement

This RFP focuses on mechanisms for pricing state growth. (Sometimes called ‘storage.’) The mechanism should be grounded in theory and its analysis should help understand design tradeoffs (e.g., state rent vs. expiry). A successful project will result in a report or paper that includes most, if not all, of the following:

  • A proposed multidimensional fee mechanism that accounts for the nuances of ‘cumulative resources’ such as storage. The final mechanism definition and analysis should include:
    • Clearly-defined design parameters. (The proposal should clarify what parameters blockchain designers are able to choose and how these parameters directly impact the pricing mechanism.)
    • A path to an efficient implementation as part of the node client. (This RFP should not just be a theoretical exercise!)
    • Well-defined action space for developers. (For example: do developers need to worry about expiry? About rent? A fee to ‘resurrect’ expired state? A tiered memory system? etc.)
  • Empirical analysis of historic state growth for 1-2 particular blockchains that answers the following questions:
    • What is historic state growth? How do we define it clearly in these scenarios? How do we measure it?
    • How has state growth impacted sync time and throughput?
    • At a target throughput, how long would it be before a full node is unable to keep state in RAM?
  • Simulated analysis of the proposed mechanism
    • How does the mechanism alleviate the issues in the blockchain analyzed above?
    • How does the mechanism improve throughput, and by how much?

In Places to Start, we point to a number of places were this question or related questions have been explored, including frameworks for multidimensional resource pricing.

Background

Public blockchains allow any user to submit a transaction that modifies the shared state of the network. Transactions are independently verified and executed by a decentralized network of full nodes, who must store the state of the network, verify that these transactions are executed properly, and update the network’s state accordingly. This state includes every account ID, balance, any additional data stored by the account (e.g., code for smart contracts), and metadata (e.g., nonces). In most blockchain architectures, full nodes must store the entire state of all accounts on the network.

Pricing transactions

Because full nodes have finite resources, blockchains limit the total computational resources that can be consumed per unit of time through both a hard per-block limit and a transaction fee mechanism. The more expensive a transaction is for a full node to execute, the higher the fee the user must pay to submit it. Recent work (see “Resources” below) has focused on pricing the resources these transactions use more accurately by splitting up the markets for different resources (e.g., computation, bandwidth, storage). However, most work has not addressed the differences between ephemeral resources, where the amount used in one block minimally impacts the next block (e.g., CPU usage), and cumulative resources, where the amount used in one block may directly limit the available amount in the next block (e.g., memory and storage). This RFP focuses on the latter type of resource, which has been under-explored and presents unique problems.

Motivating case study: Binance Smart Chain

Binance Smart Chain (BSC) sought to address throughput concerns with Ethereum but preserve its smart contract capabilities. Accordingly, BSC forked from Geth in September of 2020 but increased block size and reduced block time. As a result, BSC’s state grew nearly 10x faster than Ethereum’s in the year after its launch (400GB/yr vs. Ethereum’s 50GB/yr), quickly becoming too large to store on consumer hardware. Even professional hardware began to experience issues accessing state on-demand for transactions. This rapid state growth, in turn, likely led to high centralization, reduced throughput, and an almost-unusable blockchain for many applications and users. BSC’s woes suggest that the rate of state growth must be carefully managed.

Places to start

One approach is to extend the model in Dynamic Pricing for Non-fungible Resources: Designing Multidimensional Blockchain Fee Markets (and Multidimensional Blockchain Fees are (Essentially) Optimal) to cumulative resources by introducing a ‘multi-block’ loss function which takes transaction history into account. Since it seems that this is “roughly” the best we can hope to do, it is very likely that there exists a similar framework for these cumulative resources. Of course, the proposed theoretical model must also be implementable in practice.

Resources

Sponsored By
The Uniswap Foundation has committed up to $3,000,000 over the next 3 years to DeFi Research.

Get Involved

sign up