Rate Limiting

Owned by Joseph Denman
Last updated: Mar 28, 2018 by Dan ConnollyVersion comment
6 min read

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 Ω : L → 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 state P and 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 | Q →α P' | Q). This implies the existence of multiple resource pools, one for P and one for Q. If P 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 | Q →α Nil | Q describes a program state P 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 →α Q', then Φ(Nil) should be relinquished to Q 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 resource bound is more precise than one at Rholang source level, but it is dependent on Rosette VM.

Rosette VM is a labeled transition system T = Σ × Op × → , where P ∈ Σ is the set of possible VM states, op ∈ Op is the set of Rosette VM opcodes and primitives, and → ⊆ Σ × Op × Σ is the transition relation. Then, a cost model for Rosette is just a function Ω : Op → Q+ that assigns a cost to each opcode and primitive.

Rosette VM will not support parallelism in the Mercury release. Eliminating parallelism eliminates the fairness problem outlined above. In fact, since opcode execution is linear, it suffices to maintain a single gas counter as a component of VMState, without affecting the execution semantics. To account for the impact of input arguments on the complexity of an opcode, we simply make the cost of an opcode parametric in its input arguments, i.e., Ω : Op → Arg → Q+. This was the same approach taken for the cost model of the Ethereum Virtual Machine.

Pros:

  1. Has a well-defined notion of state ( VMState ) and transitions ( Op ).
  2. Provides a more granular resource bound. For example, a Rosette cost model can differentiate between network, storage, and tuplespace access by opcode/primitive type.
  3. Maintaining a resource pool is as simple as adding a counter to VMState.

Cons:

  1. Dependent on the (temporary) Rosette VM.
  2. Does not allow parallelism.

Interpreter

The Rholang Interpreter defines state as Queue[(Env, Par)], essentially a queue of continuations to be evaluated. If the Rholang Interpreter interface defines a set of helper functions to describe how state is transformed, then these functions can be treated as machine instructions w.r.t the interpreter. Then a cost model is, again, relatively straight-forward. For example, if Env := DuBroijn → Term , then following are simple instructions:

read: Env → DuBroijn → Term

write: Env → DuBroijn → Term → Unit

Then, we go on to make similar instructions for tuplespace operations:

consume : Store → Term → Term

produce: Store → Term → Unit

Given a store and an environment, E , the cost of the transition Queue[(E, for(@Nil ← x){ P } | Zero ) :: R] → Queue[R] can be (roughly) calculated Ω(read + consume + write + i) + Ω(instr(P)). The first function quantifies the complexity of a single bind. It uses i to account for the overhead of pattern matching and parallelization, though these could potentially be exported as "instructions" too. The second function represents the cost of the instructions that represent P. Naturally, Zero has no cost.

With a notion of state, and a cost model, the resource bound can be implemented on top of the threading model. To start, the main thread is given a portion of the gas implicitly purchased by the message sender. For every fork, thread resources are divided. For every join, thread resources are added. For every instruction executed on a thread, its resources are decremented. If a thread's resources are entirely depleted, it must block and query its parent for more. If a thread terminates with resources remaining, it relinquishes those to its parent. This continues either until the program terminates or the main thread's resources are depleted.

Pros:

  1. Has well-defined notion of state (Queue[(E, Par)]) and transitions as "helper functions".
  2. Provides a compositional resource bound.
  3. Supports parallelism ; fairness constraints be programmed into custom ExecutionContext

Cons:

  1. TBD