25 Sep - 1 Oct 2023

This week our team's focus has been on quantifying key criteria of an optimal prover mechanism, approaching them as optimization problems and defining metrics that could be used in our simulation. Our team had multiple brainstorming sessions and we have split the work so that we can work on the criteria and the metrics parallel. While we discussed multiple criteria, I have mainly worked on censorship resistance, permissionless entry and transparency and fairness during the week.

• Here are our common research notes on the Prover Optimization: LINK

Nilu suggested some lessons from MIT on optimization problems which I have watched and took notes of: https://youtu.be/C1lhuz6pZC0?si=jfOcB_moo7PMAGIP

Also, we have spent some time getting familiar with cadCAD: https://www.cadcad.education/start

Our meeting with Barnabe has been postponed to next Thursday, 5 October. By then I expect we will have finished quantifying all key criteria related to prover mechanisms.

Here are some of the criteria I have been working on:

Censorship Resistance
The mechanism should encourage more provers to participate, which should increase censorship resistance. A small set of provers may refuse to prove certain types of transactions.

1. Non-censorship Index (NCI): this metric aims to measure the degree of censorship resistance in a prover network. It can be defined as the ratio of successfully proved transactions to the total number of transactions.

   • NCI = (Σ X) / T
     • ‘Σ X’ represents the sum of binary variables ‘X’.
     • ‘X’ is a binary decision variable (1 if not censored, 0 if censored)’ for each transaction.
     • ‘T’ represents the total number of transactions.
   • Objective function: Maximize NCI
   • Participation constraint: with this we aim to ensure that all provers prove a minimum proportion of all transactions, and to discourage refusal
     • A certain participation proportion to be defined for all transaction types (privacy transactions, or low fee&high compute transactions)
   • Prover Non-censorship Index (PNI): the above Non-censorship Index (NCI) could also be tailored to measure the censorship of the individual provers, for this we include the below penalty in the formula:
     • Prover Censorship Penalty (PCP): could be included in the objective function to penalize censoring provers. This should be subtracted from the NCI when a prover censors a transaction.
     • PNI = (Σ X) / T - Σ C * (1 - X)
       • ‘C’ is the censorship penalty for the transactions.
     • This index could be used in two ways:
       • included in the calculation formula of the provers’ reputation
       • Could be used to dynamically adjust the rewards for provers; i.e. non-censoring provers get full rewards, while censoring provers get rewarded according to their score (1 = 100% rewards; 0.9 => 90% of rewards)

2. Censorship Likelihood (CL): this metric quantifies the likelihood of provers refusing to prove certain types of transactions. Our objective is to minimize the likelihood of censorship by a subset of provers for any transaction type.

   • Minimize CL = ∑(i=1 to N) Ci * Xi
     • ‘N’ is the number of different types of transactions (e.g.: privacy transactions, low-fee & high-compute transactions etc)
     • ‘Ci’ is the likelihood coefficient for type ‘i’
     • ‘Xi’ is the decision variable (0 or 1) indicating whether the transaction is censored or not
     • Different environments carry different censorship likelihood for certain types of transaction; e.g. low-fee & high-compute transactions in a profit maximizing environment)
   • Participation constraint: just as further above, with this we aim to ensure that all provers prove a minimum proportion of all transaction types, and to discourage refusal
     • A certain participation proportion to be defined for all transaction types

Permissionless entry
The mechanism should allow any eligible participant to join without requiring special permissions or approvals, ensuring open access and inclusivity.

1. Permissionlessness Coefficient (PC): this metric aims to ensure that anyone can join the prover network without special permissions or approvals and to maximize the openness and inclusivity of the prover mechanism, which can be represented by the number of eligible participants (who meet the accessibility criteria under the Accessibility Coefficient (AC) further below).
   • PC = Maximize Number of Participants
   • Constraints:
     • Censorship constraint: to ensure that no eligible participant is denied access to the prover network due to censorship or discrimination.
       • No_Censorship = 1
     • Access Permission constraint: to ensure that there are no special permissions or approvals required by any central parties for an eligible prover to join
       • Special_Permissions = 0
2. Accessibility Coefficient (AC): it aims to minimize the entry barrier for participation in the prover network. This barrier can be financial as well as technical. The lower the AO, the lower the entry barrier for prover participation.
   • Objective function: Minimize AO = Σ(Bi(Stake, TechnicalRequirements))
     • ‘Bi’ is the entry barrier for each participant ‘i’
     • ‘Stake’ represents the amount of stake needed to join the prover network.
     • ‘TechnicalRequirements’ represents the technical prerequisites that participants need to meet.
   • Financial constraint: a certain threshold (maximum acceptable amount) to be defined to ensure the financial prerequisite never exceeds it
     • Constraint: Stake <= StakeThreshold
   • Technical constraint: to ensure that the technical requirements to generate zk-proofs does not exceedingly limit participation
     • Constraint: TechnicalRequirements <= MaxTechnicalRequirements