Starknet Decentralized Protocol VI - The Buffer Problem

This post deals with a fundamental design problem for blockchain protocols with proofs: the buffer problem. We’ll start by separating it into proactive and reactive problems. Next we’ll discuss their relationship, ending with some thoughts on how to resolve each of them.

Easy and hard buffer problems

The buffer problem: there may be consensus on blocks which are not profitable to prove, resulting in abandoned jobs (“holes” in the forest of jobs).

The name comes from the flow ‘users → consensus → proofs’ in which the consensus layer acts as a buffer between users and provers. Let us distinguish between two challenges underlying the buffer problem.

  • Proactive buffer problem (prevent most holes): prevent consensus on blocks that underpay provers.
  • Reactive buffer problem (plug all holes): promote consensus on unprofitable blocks to L1 state updates (without forking the consensus).

In practice, the reactive buffer problem may arise due to volatile exchange rates between the token and the fiat used by provers. Specifically, a block may be profitable to prove when it reaches consensus but become unprofitable at a later point in time if the reward depreciates.

An effective proactive solution reduces the scope of the reactive problem: better proactive pricing means fewer unprofitable blocks to deal with.

Possible solutions

  1. For the proactive buffer problem, ensure provers earn enough money. The scope of the solution depends on the payment:

    • If provers are paid around market price then mild fluctuations may provoke the reactive problem.
    • If provers are overpaid (using minting) then only extreme events will disrupt proving.

To discover the market price one can use an algorithmic base fee. The base fee can be set as a lower bound on the prover resource price. (Think 1559 minus tips and minus burn rule.) Overpayment can use static (hardcoded) prices or rely on a price discovery mechanism (e.g base fee). For example, the base fee may be 1 token per unit of resource and the protocol may issue a 10x overpayment of 10 tokens.

  1. For the reactive buffer problem, do two things for pending underpaid jobs:

    1. Gradually increase rewards using minting,
    2. Disincentivize collusion to game the reward mechanism (e.g by competition or by carefully setting rewards).

We do not expect a proactive solution to entirely prevent the reactive problem. However, a profitable proving business may incentivize provers to occasionally prove unprofitable blocks at a loss for the sake of maintaining the steady flow of profitable jobs.

34 Likes