Skip to main content

The Matching Protocol

The Matching Engine follows the following algorithm to match Proof Requesters with Proof Generators:

  1. The Matching Engine picks an unassigned Proof Request from the queue.
  2. It checks whether the Assignment Deadline since the Proof Request was submitted onchain hasn't passed.
  3. It filters Generators who have registered in the Market corresponding to the Proof Request such that:
    • Max Proof Generation Time (submitted by Requesters) <=<= MaxProofTime (quoted by Generators)
    • Budget (submitted by Requesters) >=>= PricePerProof (quoted by Generators)
    • Available native stake (that's not already locked up in a job) >=>= Native stake per job for the Market
    • Available Symbiotic stake (that's not already locked up in a job) >=>= Symbiotic stake per job for the Market
    • Available compute (that's not already being used) >=>= Minimum compute required per job for the Market
  4. Amongst Generators that meet the above criteria, a Generator is randomly picked with a probability such that:
    • it is inversely proportional to PricePerProof
    • it is inversely proportional to MaxProofTime
    • it is inversely proportional to the number of times the Generator missed submitting a valid proof in the past 48 hours

Below is deeper logic behind the weighted_time_cost_random_selection.

Let i∈{1,2,…,n} denote the index for each candidate.ci=Proof generation cost for candidate i,ti=Proposed time for candidate i,mi=Number of missed jobs for candidate i in last 48 hours ,mi≥0(assume mi=0 if no record exists).\begin{aligned} &\text{Let } i \in \{1, 2, \dots, n\} \text{ denote the index for each candidate.} \\ &\quad c_i = \text{Proof generation cost for candidate } i, \\ &\quad t_i = \text{Proposed time for candidate } i, \\ &\quad m_i = \text{Number of missed jobs for candidate i in last 48 hours } , \quad m_i \ge 0 \quad (\text{assume } m_i = 0 \text{ if no record exists}). \end{aligned}

1. Normalization​

First, we define the maximum values for cost and time across all candidates. To avoid division by zero, if these maximums are zero, they are replaced by 1:

Mc=max⁡1≤j≤ncj,with Mc=1 if max⁡jcj=0,M_c = \max_{1 \leq j \leq n} c_j, \quad \text{with } M_c = 1 \text{ if } \max_{j} c_j = 0, Mt=max⁡1≤j≤ntj,with Mt=1 if max⁡jtj=0.M_t = \max_{1 \leq j \leq n} t_j, \quad \text{with } M_t = 1 \text{ if } \max_{j} t_j = 0.

Each candidate's cost and time are normalized as:

c^i=ciMc,t^i=tiMt.\hat{c}_i = \frac{c_i}{M_c}, \quad \hat{t}_i = \frac{t_i}{M_t}.

2. Weight Computation​

The weight ( w_i ) for candidate ( i ) is computed by inverting the normalized cost and time (so that lower values yield higher weight) and then applying an exponential penalty based on the number of missed jobs:

wi=1c^i t^i×2−mi.w_i = \frac{1}{\hat{c}_i \, \hat{t}_i} \times 2^{-m_i}.

Equivalently, substituting the normalized values, the weight can be written as:

wi=Mc Mtci ti×2−mi.w_i = \frac{M_c \, M_t}{c_i \, t_i} \times 2^{-m_i}.

3. Selection Probability​

Candidate ( i ) is chosen with a probability proportional to its weight. That is, the probability ( P(i) ) that candidate ( i ) is selected is given by:

P(i)=wi∑j=1nwj=Mc Mtci ti 2−mi∑j=1nMc Mtcj tj 2−mj.P(i) = \frac{w_i}{\displaystyle \sum_{j=1}^{n} w_j} = \frac{\dfrac{M_c \, M_t}{c_i \, t_i} \, 2^{-m_i}}{\displaystyle \sum_{j=1}^{n} \dfrac{M_c \, M_t}{c_j \, t_j} \, 2^{-m_j}}.

Summary​

The entire process can be summarized mathematically as follows:

  1. Normalization:

    c^i=cimax⁡jcj,t^i=timax⁡jtj.\hat{c}_i = \frac{c_i}{\max_{j} c_j}, \quad \hat{t}_i = \frac{t_i}{\max_{j} t_j}.

  2. Weight Calculation:

    wi=1c^i t^i⋅2−mi=Mc Mtci ti⋅2−mi.w_i = \frac{1}{\hat{c}_i \, \hat{t}_i} \cdot 2^{-m_i} = \frac{M_c \, M_t}{c_i \, t_i} \cdot 2^{-m_i}.

  3. Selection Probability:

    P(i)=wi∑j=1nwj.P(i) = \frac{w_i}{\sum_{j=1}^{n} w_j}.