/
Rate Limiting

Rate Limiting

Summary

  • Reason for writing: The resources (CPU cycles, memory, storage, network access) available to a Rholang contract must be limited to those purchased by the message sender who triggers the contract. Since Rholang is Turing complete, a resource bound cannot be statically determined. Thus, we require means to bound resource consumption at runtime.

  • Problem: In the following, the necessary definitions are given and implementation options explored. Essentially, I make the argument that a fair bound for Rholang requires a well-defined notion of state, of operations that transform the state, and a means to quantify resource consumption in a concurrent setting.
  • Conclusion: A resource bound enforced at the Rosette VM level is trivial and granular w.r.t Rosette. A bound enforced at the Rholang source level is infeasible and imprecise. A resource bound for the Rholang interpreter is feasible and granular.

  • Implications:

    1. Considering the triviality of implementation, a bound at the Rosette VM level should be implemented and is in progress.
    2. A bound for the Rholang Interpreter is not only feasible but superior to one for Rosette. Implementation is in progress.

Note: In the following, CPU cycles are really the only resources considered. Inclusive definitions exist for memory, storage, and network. Also, the term resource bound typically refers to one that is determined statically. Since this is actually impossible, I use resource bound to mean a bound that can be checked and enforced at runtime.

Cost Model

We need a cost model to quantify the complexity of a Rholang program.

First, define a transition system T as a triple Σ × L × → , where P ∈ Σ is a set of states, α ∈ L is a set of transition labels, and → ⊆ Σ × L × Σ is a transition relation. Basically, L is the set of operations that can cause the system to transition. Given T, a cost model is a function Ω : Q+ that maps each transition label to a non-negative rational number. From a complexity perspective, Ω quantifies the time it takes to perform a given operation. Suppose a program begins at stateand transitions to the state P' by performing α. This can be represented P → α P'. Since we have a cost model, the cost of the transition can be represented P → Ω(α) P'. This is read, "P performs α to become P' and consumes Ω(α) resources". 

Resource Bound

We need a resource bound to ensure that the program doesn't exceed a certain complexity.

To do this, define a potential function Φ : Σ → Q+ that maps each program state to some non-negative rational number. Φ represents the resources available for consumption in a given state. If it can be shown that  P → Ω(α) P'  ∧  Φ(P)  ≥  Ω(α)  ⇒  Φ(P') = Φ(P) - Ω(α)  is true for all program states, then Φ(P) is a valid resource bound. Clearly, the validity of Φ depends on the definition of T.

Implementing a resource bound for sequential programs is trivial. It basically amounts to maintaining a counter to represent consumable resources. The initial value of the counter equals the initial resources allocated to the program. With every operation, the counter is decremented by the cost of the operation.

For concurrent programs, matters are more complicated. For rholang in particular, two processes can transition independently (represented P | α P' | Q). This implies the existence of multiple resource pools, one for P and one for Q. If transitions independently of Q, then Φ(P) must be checked independently of Φ(Q)else the transitions are linearized around a single resource pool.

In addition, resource allocation must be fair. For example, the transition P | α NilQ describes a program state that transitions to a final state Nil. If the resources belonging to Nil are greater than zero, Φ(Nil) ≥ 0, and the resources of Q are less than the cost of a transition, Φ(Q) < Ω(α) for some transition α Q', then Φ(Nil) should be relinquished to to enable the transition.

Basically, we have to answer three principle questions:

  1. What is our notion of state?
  2. What is our cost model?
  3. Given a notion of state and a cost model, how do we implement a concurrent and fair resource bound?

Source Level

A resource bound implemented in Rholang itself is modular, but less precise than one implemented for Rosette.

To derive a resource bound from the source-code of a Rholang program, we need a source-level notion of state and a source-level cost model - neither of which exist currently. We can define a source-level control flow graph for Rholang that treats source-level operations as abstract machine instructions. For example, for(z ← x) can be interpreted as the abstract instruction sequence  read(x) = temp ; bind(z, temp). Then, in the compiler, we insert a  tick(n) function/companion process (written in Rholang source) before each abstraction instruction. The tick(n) process decrements a local resource pool by n and returns true if the resource pool is greater than zero after it is decremented. If tick(n) returns false, the instruction is not executed, and the program halts.

Pros:

  • Independent of the machine executing the program.
  • Compositional
  • Does not force linearization around resource pools
  • If the bound is itself written in Rholang source, it is checked for semantic correctness
  • If resource consumption is evident in source code, it's easier to consider resource consumption when choosing programming constructs.

Cons:

  • Requires at least one additional produce, consume, and conditional check for each abstract instruction.
  • In general, quantification of resources at source-level is less precise than machine level. Without a type-checker to differentiate the behavior of abstract instructions for over types, network, storage, and tuple access are all cost-equivalent. Similarly, abstract instructions manipulating integers and floating-point numbers are cost-equivalent.
  • A realistic notion of state is difficult to derive, yet the complexity definition requires a notion of state.
  • It may not be possible to transpile each source-level construct into a set of abstract instructions. Iteration, for example, is hard to describe.

VM Level

A VM-level resou