2-8 Oct 2023

This week we continued to focus on quantifying the key criteria and come up with metrics for an optimal prover mechanism. We are defining them as optimization problems, including objective functions and related constraints. I mainly worked on transparency and fairness, security and Sybil resistance during the week (further details below).

On Thursday we had a meeting with Barnabé, our mentor from the Ethereum Foundation's RIG. As per his guidance all three of us in our team are creating their own optimal prover designs and selecting key criteria for measurement and modelling, and in the coming week we are meeting to come up with a unified set of parameters and criteria to simulate in our research project.

• Here are my working notes on what I think could be an optimal design/model for our project to simulate.

Also, we agreed that we'll meet weekly for the rest of the EPF.

During this week I also watched and read the video and study paper Barnabé shared with us. It is related to measuring the decentralization of Ethereum.

• Video: Simon Brown (Consensys)
• Paper: Measuring the Concentration of Control in Contemporary Ethereum

Here are the criteria and metrics I was working on:

Transparency and Fairness
The mechanism should maintain transparency in its operation and ensure that all participants are treated fairly, without any discriminatory practices or bias in participant selection and reward distribution.

1. Transparency Index (TI):
   This metric quantifies the level of transparency in the operation of the prover mechanism, and aims to include the availability of information about the mechanism’s rules, operation, and state, as well as the transparency of decision-making processes.

   Objective function:

   • Maximize TI = ∑ Wi * Si (where i = 1,2,…,n)
     • ‘Wi’ is the weight of the sub-objective reflecting it’s relative importance
     • ‘Si’ is the score for the i-th sub-objective
     • ‘n’ is the number of sub-objectives

   Information Availability Sub-objective = (Available information) / (Total necessary information ensuring transparency)

   • It measures the availability of information about the zk-rollup mechanism's rules, operation, and state.
   • Constraint: the score for the information availability sub-objective to be higher than the predefined acceptable threshold

   Openness in Decision-making Sub-objective = (Openly made decisions) / (Total number of decisions)

   • This assesses the openness of decision-making processes within the zk-rollup mechanism
   • Constraint: the score for the Decision-making sub-objective to be higher than the predefined acceptable threshold

2. Selection Probability Rate (SPR):
   Considering a staking-based approach with predetermined max_Stake_Amount and random selection: this metric aims to measure the probability of a prover being selected which can be determined by the ratio of the provers’ stake to the total amount staked in the prover network.

   • Pi = (Stake of Prover i ≤ max_Stake_Amount)/(total_Staked_Amount)
     • Pi is the probability of prover i being selected.
     • Proportional selection ensures that any prover with higher stake amount is rewarded proportionally higher, while the max_Stake_Amount limits any prover from becoming dominant in the network
   • After incorporating Randomness (‘Ri’) the final SPR of Prover i = Pi * Ri

Security
The mechanism should prioritize security measures to protect against potential attacks, vulnerabilities, malicious behavior, or errors, possibly using staking and slashing as mechanisms to deter and penalize wrongful actions, ensuring the safety of the network.

1. Rate of Decentralization (RD):
   Decentralization is key to ensure the security of a prover network and its resistance to attacks. See metrics under the “Decentralization” criteria.

2. Proof Validity Ratio (PVR):
   This metric aims to quantify the ratio of valid zero-knowledge proofs (VZKP) to the total zero-knowledge proofs (TZKP) generated by provers. A valid zero-knowledge proof (VZKP) is one that is verified successfully by the zk-rollup network's L1 verifier contract. The objective is to encourage the generation of valid zero-knowledge proofs while maintaining the security and integrity of the zk-rollup network.

   Objective function:

   • Maximize PVR = Valid zero-knowledge proofs (VZKP) / Total zero-knowledge proofs (TZKP)

   Constraints:

   • Proof Generation Constraint: TZKP > 0
   • Validity Constraint: VZKP <= TZKP
   • Prover Identity Constraints: ensure that each prover has a unique and verifiable identity or reputation within the network to prevent Sybil attacks. See further details on this in further below at the “Sybil Attack Resistance” criteria
   • Consensus Constraints: the zk-rollup’s consensus mechanism to ensure that only valid transactions are included in a block. Consensus Validity (CV) = 1 if all transactions are correct, and CV = 0 if not
   • Resource Constraints: Consider resource limitations such as computational power which may affect the generation of proofs. Computational Resource Capacity (CPC) = 1 if resources are adequate to generate the proof successfully, CPC = 0 if not

3. Impact (Cost) of No Proof (INP):
   The cost of not generating a valid zk-proof for a block can impact the overall security and efficiency of the network, and can be measured as a combination of various factors, such as security cost, data integrity loss, increased computational cost, loss of trust or reputation cost.

   Objective function:

   • Minimizing Impact of No Proof = W1​ * Security Risk + W2 ​* Data Integrity Loss + W3 * Computational Costs + W4 * Loss of Trust
     Where:
     • Wi​ are weight coefficients that determine the importance of each cost component. These weights can be assigned based on the system's priorities.
     • Security Risk quantifies the risk of security breaches due to invalid proofs.
     • Data Integrity Loss measures the impact on data integrity caused by missing or invalid proofs.
     • Computational Costs represent the increased costs of computation in case of an invalid proof.
     • Loss of Trust from users and validators when valid proofs are not consistently generated.

   Constraints:

   • Transaction Processing Constraint: Ensure that all transactions within a block are correctly processed and included in the proof generation process.
   • Security Constraint: The security constraint may involve checks to ensure the absence of fraudulent or malicious transactions.
   • Computational Constraint: Maximize the efficiency of having a valid proof generated by another prover and minimize waste in the additional computation
   • Trust and Reputation Constraint: Maintain trust in the system and prevent reputation damage. This constraint may involve setting thresholds for trust levels and reputation metrics and ensuring that they are not breached.

4. Risk of Network Failure (RNF):
   The objective is to minimize the risk of network failure due to dishonest provers. We can define a risk metric, R, that captures the impact of dishonest provers on network availability or security.

   Objective function:

   • Minimize R = W1 * CapacityCompromized + W2 * RecoveryCost + W3 * TrustLoss
     • Where Wi is the weight of each parameter

   Constraints:

   • Distributed Validation: Increase the number of provers in the network to reduce the impact of dishonest provers and distribute the risk across multiple entities.
   • Redundancy: Implement redundancy mechanism to ensure that no single prover or validator has critical control over the network.
   • Incentive Mechanisms: Design incentive/collateral mechanisms that penalizes dishonest behavior, increase the cost of attack and reward honest provers.

Sybil Attack Resistance
The mechanism should be resistant to Sybil attacks, where an attacker creates many pseudonymous identities to increase their chances of being selected.

1. Risk of Sybil Attacks (RSA):
   This metric measures the risk of a Sybil attack, with an emphasis on prover identity.The goal is to minimize the Risk of Sybil Attacks (RSA)

   Objective Function:

   • Minimize RSA = W1 * IV + W2 * RS + W3 * SC + W4 * PBA
     • Where Wi is the weight of each of the below constraints.

   Constraints:

   • Identity Verification (IV): A proof of unique identity (e.g.: an identity token) and identity verification should be implemented for the participating provers.
     • IV = 1 if identity is verified, IV = 0 if not
   • Reputation Score (RS): A reputation score to be assigned to each prover (0 ≤ RS ≤ 1) based on their behavior and previous reliability and performance. The higher the reputation, the lower the risk of Sybil attacks:
     • RS = f(prover_behavior)
   • Stake or Collateral (SC): Provers must stake or deposit collateral, which can be a fixed amount or a proportion of their assets. This provides an economic protection against Sybil attacks:
     • SC = 1 if collateral is staked, SC = 0 if not
   • Prover Behavior Auditing (PBA): Periodically audit prover identities and behaviors:
     • PBA = 1 if auditing is performed, BA = 0 otherwise