Research Engineering Sync

2024/11/27

• Incentives:
  • Rewards should ideally cover node operational costs.
  • Happiness rewards (based on network performance) could encourage participation.
  • Participation rewards are not yet fully modeled or implemented.
  • Ensuring good actors are rewarded while avoiding adversarial manipulation.
  • Simplicity is prioritized for early models, with more sophisticated approaches to be added later.
  • Small operators may struggle to benefit from rewards: inclusivity vs. efficiency.
  • Fewer, larger stake pools are easier to incentivize and manage compared to numerous smaller ones.
  • A significant number of small pools may never contribute meaningfully under a lottery-based reward system.
  • Encourage merging smaller pools or setting minimum stake thresholds.
  • Address the risk of adversarial behavior if smaller pools are excluded.
  • Sync with Vangelis for insights on incentives and participation models.
• SNARKs for Mithril and Alba
  • Alba may have advantages (no pairings required, simple hash calculations), but Mithril faces challenges with linear pairing checks.
  • Research on related algorithms and fields is ongoing.
  • Verification times and proving efficiency need further evaluation.
  • Updates on field arithmetic and implementation viability will be shared in the coming weeks.
• Protocol Parameter Updates
  • Current protocol parameters are slightly outdated.
  • Updated values for protocol constants will be shared in the channel to ensure alignment with the latest research.

2024/11/13

• Efforts to reduce input size are ongoing; Mithril remains the best candidate for Peras.
• SNARKs on ALBA being explored. Proof size and circuit compatibility under evaluation.
• Tolik's concurrent hybrid approach for ALBA shows moderate improvements.
• Sync Committee uses BLS signatures (28 bytes) and multisignatures.
  • Requires further analysis for potential use.
• SPO incentives needed for sustained participation. Proposals:
  • Centralized treasury funded by Catalyst grants.
  • Fixed payments (per epoch or monthly).
  • Tiered rewards based on contribution metrics.
• Aggregator incentives could involve user fees or leveraging a SNARK marketplace.
• Game Theory: Start with small rewards and adjust empirically. Update existing models with realistic parameters for better accuracy.
• Draft incentive requirements and priorities.
• Contact Vangelis and Brian for input on incentive mechanisms.
• Verify Peras project parameters and assess SNARK costs.

2024/10/30

• Work is focused on generating certificates with compression to improve scalability.
• Mithril certificates, currently 56 KB, need reduction to around 5 KB to fit within block headers.
• Compression may involve SNARKs or similar techniques, though exact requirements are still undefined, prompting further discussions to align on a unified certificate generation protocol.
• In Peras, the 50% adversarial threshold requires high computational resources due to intensive consensus demands, unlike checkpoint scenarios which achieve consensus more economically with lower adversarial impact.
• This 50% threshold in Peras complicates balancing security and cost.
• Mithril requirements specify certificates with rapid (1-second) aggregation and small size, creating challenges in aggregation speed and verification performance due to concatenation and size constraints.
• Bulletproofs are unlikely to meet Mithril's size and time targets; finding efficient SNARKs for verification and aggregation remains a priority.
• Decentralizing signer registration without traditional consensus is being explored, possibly through gossip-based registration on a p2p network, to avoid the expense and complexity of a dedicated chain for key updates.
• Evolving keys pose challenges, as proofs of possession need verification, increasing verification structure size and computational demands.
• Alternatives like registration hints for aggregators or distributed storage are under consideration.
• Frequent key verification impacts registration and verification costs, particularly with evolving key schemes that increase demands.
• Potential solutions such as distributed systems or market-driven services for offloading verification are being explored but are not yet finalized.

2024/10/02

• Alba-Mithril Integration: Integration of Alba's lottery-based aggregation mechanism into Mithril's signature scheme.
  • Determine whether security parameters require adjustment during integration.
  • Assess if Alba's parameters can be aligned with Mithril's existing security guarantees or if a full re-evaluation is needed.
  • Signers will use Alba's lottery mechanism during individual signature generation, submitting lottery results to the aggregator.
  • The aggregator will reapply the lottery mechanism to aggregate signatures and generate the final certificate.
  • The modular design allows for flexibility in switching between different lottery schemes if future adjustments are required.
• Alba-Peras: Security Audits and Verification
  • Verify whether Alba has a formal security proof by reviewing the original paper.
  • Plan further formal audits for both Alba and Peras protocols to ensure robust security.
  • Explore acquiring additional resources to conduct in-depth security audits.
• Cardano-Mithril: Aggregator and Mainnet Status
  • Certification for Cardano transactions has been activated on the mainnet.
  • The aggregator is currently importing transactions and will generate the first certificates soon (expected within 24-48 hours).

2024/09/18

• The protocol security document is still pending review. The document may require a small clarification regarding how classifications like "blockchain" are used.
• Progress on upgrading signers is expected in the next sprint, with a target of two weeks for an update.

2024/09/04

• Mithril-STM Protocol Security Document:
  • The document was clear and concise, especially for non-experts.
  • Complex sections should be simplified or removed to make it more accessible for a general audience, especially if published on the website.
  • Technically sound, but trimming some elements for the web version would enhance readability without losing essential points.
  • Mithril does not handle value transfers like traditional blockchains, so security risks like double-spending are less relevant.
    • The document should be updated accordingly.
    • It should focus on Mithril-specific threats, such as adversarial stake accumulation or participation failures.
  • The team will give feedback to ensure the inclusion of the most relevant cases.
• Security, Participation, and Adversarial Models:
  • Concrete thresholds are needed to maintain Mithril's security.
    • While Mithril can tolerate some missing stakes, adversarial participation raises risks.
    • Over 95% stake involvement was proposed as the target for robust security guarantees.
    • Clear thresholds should be set based on current participation levels to guide both the team and SPOs.
  • A new feature requiring a sufficient number of upgraded signers to generate valid aggregate signatures will rely on these thresholds.
    • A mathematical model will be used to compute the minimum stake participation needed for quorum in signature generation, factoring in the possibility of outdated protocol versions.
    • The model will provide reliable security guarantees without requiring 100% participation.
  • Adversarial Behavior
    • Scenarios where 2-5% adversarial stake could be tolerated, but beyond this, security begins to degrade significantly.
    • To address this, various scenarios based on participation levels (e.g., 98%, 90%, 80%) will be included in the documentation, analyzing how security is affected in each case.

2024/07/24

• JP shared his computation on how many signers would be eligible to send signatures given the stake distribution on the Cardano network.
  • Computed stake weight and expected number of lotteries each signer can participate in.
  • Observed that 2/3 of the stake would not be eligible to sign.
  • To cut networking costs, we could aim to reduce the number of signers from 3000 to 1500.
  • Considered the impact on security and participation if smaller stakes are excluded.
  • Decision to possibly exclude the smallest stakes to keep the participation rate high, around 99.8%.
  • Centralized systems currently manage costs efficiently, but decentralization requires careful evaluation.
• Security Threat Model
  • Decided to provide brief information about the protocol and refer to the detailed paper for in-depth analysis.
  • Highlighted adversarial eligibility, quorum parameters, and their effect on security.
  • Plan to create a document for collaboration and comments, aiming to refine the security section for the website.

2024/06/26

• Instead of transmitting individual signatures, only the necessary elements (winning lotteries) could be regenerated during aggregation. This method leverages CPU power to recompute these elements, potentially optimizing the process by focusing only on winning lotteries.
• Removing indices from signatures could help reduce bandwidth usage, though it is unclear if this alone would be sufficient. A lottery-based approach to verification could optimize the process by calculating the number of winning tokens, thus avoiding multiple lotteries. An algorithm for electing committee members based on stake, similar to Algorand's use of VRF outputs for elections, could provide similar benefits by eliminating the need for indices and ensuring node agreement on the output.
• Switching to different elliptic curves could reduce signature size, but integrating new curves into the existing infrastructure would be complex.
• Implementing binomial computations within the verification circuit could be challenging due to the need for precise floating-point arithmetic. Verifying operations within a zk-SNARK using the Halo2 version may require recursion due to the constraints involved, especially with foreign field arithmetic and group operations. Using PLONK for group operations and hashing could simplify the process but might increase signature size and affect on-chain operations if unsupported.
• For the ALBA bounded version, the current implementation used random factors for testing purposes; exact parameters are needed for proper evaluation.
• It needs to be determined whether the protocol security should be included in the Mithril threat model.

2024/05/29

Eurocrypt and ALBA improvements

• Eurocrypt ALBA presentation went well, we had some numbers with the help of Arnaud.
• Some improvements: The communication constants don't look to be as intimidating.
• We have some greater variety of prover strategies.
  • Slightly complex protocol, more dependency on how the input looks like.
  • Three sets of different parameters for small, medium, and large inputs.
  • For large inputs it's the same as it was before the update.
  • For quite small inputs, significantly different parameters for reliability. We aim for only 50%, and we have a mechanism for performing retries until we achieve the intended reliability. Therefore, we need a layer to iterate over the proof index in addition to the $d$ value to verify if it works out. Not ideal, but a manageable approach.
  • For moderate values, we start with a baseline reliability that is higher than 50% but still below our target. We then perform a small number of repetitions. The new concept here is that if we are repeatedly running the same protocol, we can apply some heuristics to estimate if we are stuck in a bad iteration of the protocol.

Mithril Threat Model

• Draft Threat model created by Arnaud and JP.
• The idea was to put everything, such as risks, threats, crypto-related problems, software problems, etc., in the same bucket.
• No budget allocated for security audit. Our cybersecurity team (Charles) will audit the repo.
• We want to provide some information about what could go wrong.
• Some attack frameworks such as Mitre attack matrix or NIST documents can be helpful for threat modeling.
• JP and Gamze will keep in touch about the threat model document.
• Community feedback should be handled cautiously. The points where the community can interact and where the mithril team can should be clarified. For example, we may put the document on the website, and afterward, we get some feedback. So we make improvements depending on them. The sequence would iterate until we find something that makes everyone happy.

KES keys

• For Mithril, it is complicated to get the consensus or something which is a kind of consensus on the standard registration.
• The goal is to decentralize the protocol.
• We already have a consensus for SPOs: Cardano. We can determine the associations to IDs and stakes with KES keys.
• However, Ed25519 keys are not directly usable since the signatures are not unique. So, we may rebuild something that looks like Mithril by using the KES keys and VRF keys that we have. VRF keys will provide the uniqueness.
• In addition, with this method, we can use the VRF outputs for lottery; and also dense mapping may not be needed anymore.
• Alteration in the security proof might be needed. Theory side would need a medium scpoe rewrite.
• We should consider the aggregate size, because they won't be aggregated compactly.
• Verification keys would be slightly smaller.
• Initially, we would go with the concatenation in terms of aggregation. After that, we may look into ALBA and SNARKs.
• Another option: we would have to skip the consensus on the verification key. We can have a network layer which is not completely reliable but still be able to sign and not skip an epoch or adversaries break the whole.
• Still, we need to think of this alteration before we act.

2024/02/21

• ALBA is accepted for Eurocrypt. The submitted paper proposes an updated version for proof generation.

• The existing version of ALBA:

  • a set of half-completed proofs that were a few elements long.
  • extend the proofs: join everyone of these half-completed proofs with every signature on the list.
  • For every such pair: perform a check to see if the hash was good or not.

• The existing version works well but we have a "quadratic term" in the prover cost.

• The alternative: do one round of hashing for every signature and then do one round of hashing for every partial proof.

  • Partial proofs of length one,
  • Pass each partial proof to a hash function to check which of the hashes agreed,
  • Consider each of the signatures to be some sort of bucket that accepts some range of hash values.
  • If a partial proof lands in a bucket that has signatures, it is extended into a partial proof that is one signature longer.
  • If that bucket had, x signatures inside, that one partial signature turns into x.
  • If that partial signature falls into an empty bucket, then it dies.
  • Limit the range of the hashes to be small enough so that matches exist.

• Pro: In every round, if we have X partial signatures, we only do X hashes, previously, we would do X times the number of initial signature hashes.

• Con: If, at the beginning of the protocol, the arrangement of buckets is a bit weird, we can end up in an unstable situation where all our partial signatures die.

  • trade-off 1: (Submitted version), if we start with a lot of signatures, we can make that bound work nicely. If not, we will just fall back.
  • trade-off 2: (Upcoming strategy), use the pre-hashing code for everything,
    • Start with a small number of initial signatures: a small number of retries. On average, it will run with a probability of success of about 1/2
    • Start with a large number of initial signatures: notion of an allowed number of retries and a retry counter. The retries are performed locally by the prover only, by incrementing something in the hash. Signers do not need to generate new signatures for slightly modified texts.

• Pyrros will share the updated version of the paper and a prototype code when they are ready.

• Studies on the conversion of the telescope scheme into a SNARK proof still continue, however, they will be affected by the update of the scheme.

• SNARK studies can be useful for Hydra as well.

• Reza is working on a public statement to explain Mithril security, covering both theoretical and practical boundaries.

• Gamze and Reza are going to work on that together.

2024/01/24

• The algorithm for the mapping of (random number, stake) -> (#wins) is decided, and the notation will be updated for the Telescope scheme.
• Update on the registration process:
  • Without a consensus, it is challenging to guarantee the uniqueness of signatures.
  • Individuals may exploit the system to gain an advantage by delaying registration and attempting to register on the spot by signing their own keys.
  • To prevent manipulation, we need strict sequencing in evaluating signatures and including a hash of the registration table in the design.
  • If we use the keys that are registered 2 epocs before, it may fix the problem.
  • Due to the sequential nature of key sending, there are no collisions in key usage. However, potential issues arising if different key registrations lead to varied eligibility checks.
  • In the worst-case scenario, a network split could occur, with one part seeing one thing and the other part seeing something different, making it challenging to sign and create a consensus.
  • Even with a few aggregators and numerous signers, the risk exists, especially if one or two aggregators are on the wrong side, potentially preventing the signing for the old epoch.
  • On the other hand, we should consider how to prevent a situation where too many individuals, acting as aggregators, present conflicting information, making it difficult to reach a consensus quorum.
  • Achieving the results may not be possible within the current framework.
  • The process might be more of an experiment or artifact, serving as an initial step toward decentralization.
  • It might work in a laboratory but may not be effective in the real world.
  • We should consider the possibility of defining certain situations where, even without full consensus, agreement on the number of signers and aggregators could be sufficient.
  • Having a network-wide mechanism to address discrepancies in each node's registration table would be beneficial.
    • The idea of a period where different key registrations are reconciled to resolve discrepancies.
    • Alternatively, a more localized approach, running registrations locally and proceeding with signatures promptly.
  • We can work on a prototype designed for a laboratory setting with potential adversaries. The prototype is functional, especially with a balanced number of signers and aggregators.
  • A practical approach to trade-offs in the system's design could be implementing a mini consensus protocol, accepting some small errors in exchange for the benefits of early stopping or fewer rounds.
  • We could consider the evolution of the key registration process to gradually decentralize it from the centralization we have today. Starting with a few nodes running a simple consensus algorithm and gradually moving to a more sophisticated setup.
  • We also need to identify and address potential attack vectors without consensus.

2024/01/10

ALBA Discussion

• The lottery winning scheme is very similar to the current version:
  • If we assume that everybody only has one unit of stake then every signer can have just one set element which is their signature.
  • Once we add stake to the mix, we will let each signer essentially roll a die for every unit of stake they have.
  • The number of wins can be from zero up to the number of stake.
• We are flexible about the aggregator scheme. We may either choose
  • The way that every signer may broadcast their signatures to every node, then everyone becomes an aggregator.
  • Or, we can follow what we are doing now: a designated aggregator.
• The estimate for the communication cost: For instance, the cost is multiplied by one if there is only one recipient or it's multiplied by n if there are n recipients.
• The aggregator is hoping to get at least $n_p$ set elements delivered to them. After running tests, they expect to create a proof that is around u elements long. It's quite possible that the aggregator will throw some elements away which we are hoping we can throw away more elements to make the proof smaller.
• It's always possible that there will be more than one certificate, and you can choose amongst them freely.
• The set element would be the signature and an index pointing to the signer who produced that signature, or just a hash.
• The only check that needs to be done is to actually verify the signature against some index.
• We set $\mu$ (expected number of participants) to be higher or low depending on how much communication we can tolerate. If we try and reduce $\mu$, the other parameters become slightly worse.
• We do not need the $\phi$ function.
• The stake or the weight of some party is going to be some integer value.
• We would prefer not to run a linear number of checks for every unit of stake that somebody has.
• Instead, with a random number put in a binomial distribution, that gives the probability of number of wins for the coins that signer has.
• As a conclusion, the only part that we need to change is the eligibility check mechanism of the current Mithril implementation.

2023/12/13

• We plan to evaluate the Mithril 2 prototype code and determine the effort needed for implementation.
• The feedback for the Mithril 2 paper is encouraging; at least, the internal reviews are quite positive. Final results will be known after the new year.
• The possibility of Leos using Mithril directly involves the need for very quick proofs in single-digit seconds and small certificates. However, there is no concrete plan for leveraging measures.
• SNARK proofs would probably exceed our time budget because they are easy to verify and very succinct, but achieving the proof time in a few seconds seems difficult.

2023/10/18

ALBA:

• Proposes an "approximate lower bound argument" to streamline proofs and avoid exhaustive signer inclusions.
• Focuses on employing sampling and computational tricks for shorter, manageable proofs.
• Emphasizes maintaining signature uniqueness (as in Mithril) for argument integrity and flexibility.

Telescope Scheme:

• Proposed evolution from Mithril with a different proving system.
• Involves random checks to maintain a sufficient number of candidates.
• Optimization starts with hashing elements to introduce randomness.
• Elements paired strategically to reduce proof computational complexity.
• Two variations: simple telescope (independently hashing elements) and improved telescope (optimized hashing, fewer distinct values).
• Sets a threshold based on the probability of an element being acceptable.
• Hashing and pairing create random sampling, refining selected elements exponentially.
• Adjusts probability for a balance between initial elements and desired outcome.
• Ensures good elements have higher success chances. Bad elements decrease exponentially.

Key Features of ALBA:

• Smaller k value than Compact Certificates, practical advantage in real-world scenarios.
• Anticipated snark proofs under 100 KBs, easier production with ALBA system.
• Removal of obstacles, like the need for an alligator-based construction, enhances adaptability.

Proof Size and Communication:

• ALBA proofs are more efficient than Mithril and Compact Certificates in real-world situations.
• Potential challenges related to communication overhead during Telescope Scheme.
• Need for a substantial number of signatures in the initial phase, impacting communication requirements.
• Smaller proof sizes align with on-chain proof verification goals, particularly advantageous for snark proofs.
• Revisiting optimizations is required to reduce communication requirements further.

Efficiency and Integration:

• ALBA's proof size efficiency is beneficial for resource-constrained environments.
• Optimization has potential implications for network performance, ensuring effective scaling without compromising efficiency.
• Seamless integration with Mithril's decentralized ecosystem and existing protocols is crucial.
• Potential impact on transaction throughput within the Mithril network.
• Ensuring smooth integration with Mithril's consensus protocol, be it proof-of-work, proof-of-stake, or another model.

Future Considerations:

• Identifying collaborators and partners within Mithril network to promote ALBA adoption.
• Ongoing exploration of the balance between proof size and communication overhead.
• Integrating ALBA into Mithril requires further exploration, considering resources, and alignment with goals.
• If decided to integrate, the decision on in-house implementation or outsourcing may depend on discussions, resource availability, budget considerations, and specific strategic goals.

2023/09/06

New Version of Mithril

• The design looks to be finalized, but we don't have performance estimates yet.
• It looks to be on track, and at the next meeting, we will have more information.
• Shortly, the new version is: Instead of just looking for signatures that independently have a hash value that is small, we look for signatures that have a small hash value altogether.
• It will probably provide a small constant time improvement.
• It doesn't change anything in the interface.
• It won't be a backward-compatible version.

Incentive mechanism

• From a pure engineering point of view, incentivization doesn't seem so urgent.
• We might want to reach out for a different solution from a practical standpoint, like finding a social incentive mechanism.
• Now, Leos relies on Mithril. If we start incentivizing Mithril, we will be paying the Leos users, and we also ask Leos users to pay, which makes no sense because it should be an improvement.
• It might be possible to use the theoretic output in the future for the aggregator. However, some adaptation may be required.

SNARKS

• We contacted Tanja Lange about a year back about researching curve choices for proof systems.
• Her suggestion was a custom BN curve.
• The rest of the IOG might be gravitating towards Plonk.
• We are unsure about the curve choice, but it might be better for Mithril to follow it rather than go off on the side.
• As long as the curve choice does not complicate things too much, it should be possible to follow that choice.
• The Mithril redesign, some things might need checking up. But it might not be too bad.

2023/07/26

New version of Mithril

• There are still a few things to figure out.
• In mid-September, we'll have a much better draft, so we should wait until then, not to waste time, just in case there are any changes.
• The new version of Mithril uses a different proofs system which provides a more efficient aggregation but the performance in the prover side is poor.
• This proof system is not as small as bulletproofs; it is still tens of KBs but not big as it is now.
• It is light in crypto and basically uses hash functions.
• We are optimistic in terms of the speed of the system.
• The main focus is that how small we can get with a realistic communication cost.
• We are certain that we can get these types of certificates to be very small if we set the eligibility to be 1 for every SPO on every round and also be mindful of the communication cost.
• We avoid the case of the 3000 certificates being thrown to an aggregator every single round in order to get good proof sizes.
• A further investigation is needed about what the curve of tradeoffs looks like, starting from everyone sends with the best possible certificate size and scaling down what we have now.
• Integration of the SNARK system to this new version is either implementing SNARKS with this new system or getting back to the current version of Mithril. Both cases will have very similar characteristics.

Incentive mechanism

• Vangelis shared a draft with Reza. He may be available for the meeting on the 24th of August.
• The current focus is to get an approximation of what the stake dist of Mithril looks like.

2023/07/12

• The paper about the game theoretic approach to incentive mechanism will be shared by Pyrros soon.
  • Reward distribution is not straightforward.
  • We should discuss
    • How to implement the stake distribution,
    • Bridging between theory and practice,
    • What should be the reward.
  • good progress on the non-symmetric case.
• The parameters given in the paper will be used for the release.
• Implementing SNARKs for Mithril: the system is almost shaped; IO started an audition to select the most suitable curve model.

2023/06/28

• Signing immutable files of other data structures

  • It is implemented.
  • We are only signing AVK separately.
  • For the future: implementing the Cardano stake distribution and creating incremental versions of the immutable files.
  • Should talk to Mark to understand what files could be signed for a light client.
  • Also want to send the UTxO set, which is interesting for light clients.

• Parameters (participation)

  • We are moving to main-net, with very few SPOs and low expectations. Also, we need to figure out the parameter thing (problem of the participation).
  • We’ll probably do some regenesis at the beginning until we reach a reasonable amount of participants.
  • Regarding the protocol parameters, we were thinking about whether it makes sense to create several certificates for a single epoch (with different parameters, so different chances of happening).
  • This depends on what assumptions we want to make. Good to discuss with Reza.

• Full-node verifier

  • Should talk to Mark (he is working more closely in the Leios work) to learn whether the full-node verifier is planned to be used in the near future.

• SNARKs on Mithril

  • Going through a different direction, which is closer to compact certificates (Algorand work), but this would make the primitive more SNARK-friendly so that it could be leveraged there.
  • Also, we might be able to get savings on certificate sizes even before SNARKs. We might end up with a k value probability below 150.
  • For main-net release no changes are expected.
  • Design should be pretty simple and have better SNARK compatibility definitely not for main-net, but as an improvement.

2023/05/31

In this meeting we hosted Vangelis, and he introduced the game theoretic model that they (Pyrros & Aggelos & Vangelis) have been working on for incentive schemes.

• The main focus of the work: Incentivize people to perform a task that has some cost to them or some users that are lazy - game theoretic model
• The work is still in progress.
• Preliminary results are obtained.

Simple game theoretic model

Parameters

• Population of $n$ users
• Cost per epoch: $\alpha$
• Reward given to a user per epoch: $r$
• Probability of winning: $p_i$
• Inherent value to user $i$ for the successful production of a Mithril certificate: $v_i$ (For simplicity $v_i = 0$)
• Minimum num of signers to generate a certificate: $k$

Available actions for users

• Binary decision space: {A: abstain, P: participate}
• Each user cares for her expected utility
• Malicious behavior is not taken into account yet.
  • Users could temper with the software
  • Selected users could choose not to generate a signature...

Nash equilibrium: describes situations where no user has a unilateral incentive to deviate and choose a different action.

• Bad equilibrium: everyone is abstaining. This is an unrealistic scenario.
• Solving a Nash equilibrium: (See the presentation for more details.)
  • Two sets of users: $\lambda$ participants where $0 \leq \lambda \leq n$ and $n - \lambda$ abstainers.
• We need to solve a system of $n$ inequalities.
• It is not trivial since it's not linear.
• Symmetric case: all signers have the same probability of winning, $p_i = p$: Not a realistic case for Mithril, but is a useful start.
• As long as the reward is sufficiently high compared to the cost, we have exactly 2 Nash equilibria:
  • The all-abstain is always an equilibrium
  • The all-in (everybody participates) is also an equilibrium
• If we have an estimate for the cost, it tells us how to tune the rewards so as to incentivize all rational players
• Further implications: We can adjust the equilibrium:
  • Symmetric case: At least $\lambda$ people to be incentivized to participate.
  • Non-symmetric case: Incentivize the users with the highest owned stake (incentivizing the top $m$ users in terms of the stake owned). This will result in more complex formulas.

2023-05-17

• Vangelis should be able to show something in the next meeting regarding incentives.
• Open question on whether the implemented version of Ouroboros has some implicit assumption that is higher than 51%. There are no implementation properties that require a higher assumption, and therefore no argument we can piggyback on.
• We will have to justify a gap in any case, but now it seems the gap is from 51% to whatever we commit to in Mithril. i.e., it won’t be smaller
• Internal document (ouroboros praos/genesis parametrisation notes) seems to indicate that we assume 2/3 honest nodes
• This assumption might be for other properties to hold, rather than the security of Ouroboros.
• Sidechains team is also encountering similar problems (what assumptions to make on Cardano Stake in order to choose the side chains committee size)
• If we assume only 51%, all numbers for mithril are read. We need to make assumptions on SPOs that register in Mithril
• Seems that 250_000_000ADA is handled by SPOs run by IOG — Confirmed in Cardano Explorer.
• For a first iteration, we could design a use case where we make assumptions on the honesty of the registered Stake, rather than the whole network (for example, running a DeFi dApp - > e.g. Melt are building lending protocol, and they are having troubles with scaling in Cardano. L2 problems are trust assumptions, maybe using Mithril with the stake running the L2 can be something to explore)
• Catalyst -> We already have only a portion of the stake participating in it, and it might be easier to make assumptions on that.
• A summary of the above two points, is that we might find use cases that already make assumptions on some committees, and leverage that assumption to create mithril certificates.
• We can leave the decision on how much a user trusts the protocol by listing SPOs.

2023-05-03

In this meeting, we discussed Mithril security and participation, covering the following details:

• Making a security assumption depends on getting the knowledge of the honest stake of Cardano.
• We need to specify reasonable assumptions and boundaries for Mithril.
• In order to control z parameter for the assumption ACK(x,y,z), we may use some trusted/known SPOs. However, trusting 3rd party won't be a good solution.
• No SPOs running by IO or Cardano Foundation. (Update: We learned that actually, we have some SPOs.)
• Measuring the reliability is possible but forgery is not for SPOs.
  • We may use a reliability matrix to evaluate the SPOs.
• Further discussion is needed to set some metrics and measuring strategies.

2023-04-19

We discussed Mithril participation over the document Mithril Participation. The following are the 3 assumptions:

1. AM(x): x% of Mithril stake is honest, where x>50%. Paper suggests x as 60% or 70%.
2. AC(x,y): x% of Cardano stake is honest, y is the over-represented ratio of adversarial stake that joins Mithril. y=1 is equivalent to AM(x), y=inf means Mithril is not applicable. Assumption suggests y>=1. The dishonest stake is calculated as y(1-x).
3. ACK(x,y,z): x% of Cardano stake is honest, first z% of Cardano stake that joins Mithril is honest, and y is the over-represented ratio of adversarial stake that joins Mithril. Assumption states that x>50%, y>=1, and x>=z>=0.

• As most of Cardano SPOs joın mithril, mithril will catch up with Cardano for better or worse.
• When Mithril participation increases, it will catch up with the adv stake of Cardano.
• We need a stronger assumption of honest Cardano stake.
• We start with trusted people and allow some others gradually. To stay in the safe zone.
• Extra effort for registration. White list, centralized setup will be easier
• No control on x and y. We have control over z.
• Parameters for 128- and 100- bit security:
  • 3 scenarios: Full abstention represents a worst-case scenario, where an adversarial party is being obstructive and refuses to sign. Half abstention represents a milder scenario where only half of the presumed adversarial nodes are abstaining (representing a scenario where failures to sign are less malicious and uncoordinated). Full participation values represent an almost ideal case where all is working perfectly.
  • Running multiple parameters at the same time.
  • The number of trials (to generate a certificate) can be increased
  • Parameter adaptation may cost a lot, however, parameters may be adapted automatically depending on joiners or new epoch.
  • What should we aim for, what is the limit, then how we can achieve
  • We should make Mithril more efficient to tolerate more assumptions

2023-03-22

We discussed using smart contracts for Mithril incentives. We have two solutions:

1. Trusted party creates the contract. Not good for decentralization. No contract related to failed certificates.
2. Linked smart contracts. More complexity, we have maintenance issue, unsure if we can make a lot of information available to a smart contract.

For future directions, SNARK-based solutions are the best way to go, as these can be verified on-chain (with the new bindings)

• For practicality, it is better to assume we’ll use the single smart contract solution, until further notice. The problem with decentralisation, is that it is unclear how funds are used. And given that we have to trust someone to handle funds, we might as well trust them to handle the smart contracts.
• Always better to have a plan of how things could transition in the future.
• We don’t have the incentive scheme in place. Open thread with Evangelis. AFAIK, we don’t yet have an incentive scheme. We cannot count on setting up a treasury. Might have legal implications. We should not plan on starting main-net release with smart contracts for incentives. Incentives will be a problem that we’ll solve once we stagnate on SPO participation, and therefore we have ‘proof’ that we need to solve the problem.
• We can still work on a design, assuming we have these funds, so that once we have to actually solve the problem, we have a potential design.
• It is best to separate the smart contracts of registration and those of rewards.
• There is no due date for the incentive mechanism.
• The caveat of pay to pub key is that it gives extra freedom to the aggregator. The problem is that in this paytopubkey we would be using the certificate to pay the rewards.

2023-03-01

Today's meeting covered, partly, the topic of security equivalence of Cardano and Mithril. Often times, we claim that having a Mithril certificate about a certain statement (e.g. there exists 10 valid signatures) gives the same guarantees as verifying that statement on-chain (verifying these 10 signatures in a script). However, that is not the case:

• Mithril uses the same kind of assumptions as Cardano, but by no means gives the same guarantees as the latter.
• Cardano is OK with having a big series of adversarial blocks (it can recover), while in Mithril, a single adversarial block would completely destroy its security properties.
• If assumptions are true, this happens with very low probability, but it is important to distinguish this difference, Mithril cannot recover from an adversarial block.
• On way to look at it is that even adversarial blocks have constraints on main-net. An adversary cannot fake transactions that change the stake distribution. Contrarily, in mithril, an adversarial block can completely re-invent the stake distribution, giving the adversary full control in the future.
• Verifying a SNARK is stronger than having someone say they've verified a SNARK, regardless of how much we trust this 'someone'.
• One way to go would be to use SNARKs to prove the correct stake distribution transitions (rather than mithril certificate). This would guarantee that the stake distribution is bound by chain rules. However, this seems extremely complex, as we would need to prove validity of everything that changes the stake (including scripts).

Another topic of discussion was that of skipping certificates. How can we know that certificate at epoch N+1 was really skipped? How to avoid a committee from claiming that N+1 was skipped, when in reality it isn't.

• We could think of extra requirement such as proving that N+1 didn’t exist. However that seems quite hard to pull-off: proving that something does not exist.
• On of the possible solutions we are considering for rewards is to have a script paying them off. We could use this to see if rewards for N+1 were actually payed.
• Another option to protect an adversary from controlling N+2 on its own would be to bump the security parameteres.

We also discussed about a dynamic/static analysis of the adversary.

• dynamic/static analysis. The adversary knows the keys of signers for a long period of time (15 days between registration and end of signing epoch). It might make sense to have a more concrete idea of how much we expect the adversary to be dynamic. This will have a follow up.

Finally, a comment by Pyrros regarding which type of curves we need and why:

• we don't need a full cycle, a 1-chain is fine, with the requirement being that the embedded curve needs to be pairing friendly (i.e we don't require that we can embed the outside curve into the inside one). The pluto/eris pair gives us a full cycle (with one of the two being pairing-friendly), but I don't know of anything that's cheaper. Having the cycle is nice wrt recursion. Alternatively, having pairings on both curves allows us to do e.g. a snark about e.g BLS

2023-02-08

The topic of discussion was incentives. What are the blockers, what is required from engineering and what from research. Needed from engineering/product:

• Is it feasible to periodically set up a smart contract to get rewards from there? Technically and in terms of perf. i.e. if verifier of that is too expensive (verifying a single signature per user claiming rewards)
  • We will be paying around 2K people. If we assume blocks every 20s, block execution budget of 50ms, and 1ms verification time of signature, we need 40 full blocks. Seems we need 8 minutes of Cardano to pay rewards (assuming full usage of main-net exclusively for mithril rewards… seems optimistic).
  • One line of research is to turn successful signatures into lottery tickets themselves. So basically we are paying 100x more, but paying only 1/100th of the time
• Who handles the funds? -> decision will not come from research. The guess is that the first version will be centralised.
• Do we go with a design of individual smart contracts or and updatable smart contract?
  • One per reward, is easier because we have one function, that checks a particular setting, and marks the person as payed. And maybe a time function that if a lot of time passed, the funds can be unlocked to the next setting.
  • The problem of having updatable by, e.g., taking also the message. And have another function for including funds. This does leave open the issue of who inserts the funds.
  • What happens if the window to get the money is smaller than the time to the next certificate. This can be resolved by having more than one cert active for rewards

There might be a need to have some functionality to push the script forward without needing the money, so that it doesn’t get blocked. Needed from research:

• @pyrros.chaidos , I know I said in the meeting that we’ll start writing down a document with the trade-offs of existing options (one or several smart contracts). But could we do it the other way around? You draft a quick doc explaining the two possibilities, and then we iterate over it. I’m still unsure that I fully understand the different trade-offs. We can start assuming funds are managed centrally. And some other topics discussed today:
• If we have several aggregators, how do we handle payments? -> Payments are wrt to the message, not wrt the certificate. i.e. you get payed regardless of whether you are in the cert or not.
• One thing that has come up on the CSM, we could use Mithril network to show that the election was valid. However, nothing set in stone.
• To some degree we can use VRF instead of BLS, but this has some downsides on provable security of the system.
• One idea to make signature verification cheaper is to use the proof of possession data transmitted during registration. On the proof of possession we also have the pre-image of the secret key in G1, so maybe DLEQ proof
• Delegation for mithril was discussed with Aggelos and Vangelis. They are more inclined in using delegation only in cardano rather than having this in between, where delegation may happen in mithril but not in Cardano. Action items:
• @pyrros.chaidos , that little draft would be very useful 🙏
• @Reza , maybe we can start figuring out who are the decision makers for the first two points.
  • who will handle the funds? Is it going to be only IOG? The cardano foundation? a combination of the MBO?
  • is it feasible to expect 8 minutes of main-net for rewards payment? I think the answer will be a straight-up no (maybe even @Arnaud can hop in and confirm that).

2023-01-25

• Research (in particular @Vangelis Markakis ), is looking into how much money should be allocated for the system to be stable. We don’t have an estimate of when this will be solved. Research will sync with Aggelos mid next-week.
• The problem of incentives can be divided into two blocks. The first one of which users should be payed and how much (e.g. all signers, only those appearing in the certificate or all eligible signers). And the second problem how do we get these funds and how do we pay them.
• For the former, we may want to do a sync with research soon enough to understand whether there exists any requirements, as for example if we need registration to be public ( @pyrros.chaidos , any words on that?)
• For the latter, several options are being considered:
  • Have smart contracts that handle each mithril epoch. Problem is what do we do about the administrative details (e.g. who is in charge of setting them up, taking money that has not been claimed after few months, etc). Governance proposed as a solution
  • Another option is to have single smart contracts to be updatable. A single contract that handles all funds (easier to administrate), but is technically more complex. Again, this has close links with governance.
• How to make mithril ‘sustainable’. Have users of Mithril pay a fee, that is then used to incentivise mithril signers. Seems that a nice setting for paying a fee would be in a light wallet. Do we need more resources to solve the incentives problem?
• Game theory part should be addressed by what Evangelios is doing.
• Maybe research needs help with the smart contract solution to understand how we could make that work. Open questions:
• How much do we pay SPOs?
• How do marketise Mithril?
• However, do different users of Mithril have to pay differently? e.g. lightclients, fast boostrapping, or leios have different descriptions of ‘mithril clients’, in certain cases, mithril clients may not have cardano funds altogether. I think that for these questions we need a follow up meeting. It is also unclear to me who are the right persons to solve it. It seems to me that the decision on whether to make mithril clients pay or not, how much, and how, is not technical, at least not at this stage. I guess that Roy could help us out in figuring out who these people are, but maybe in the meantime (until he is back from leave) @Reza you want to take the lead on this, and set up a follow up meeting with the right people?

Interesting proposal by @Gamze wrt increasing participation of mithril stake via delegation of Mithril power:

• To increase participation of ‘active stake’, we could rely on delegation. Idea seems attractive, and there is no clear concern. We need to think about what kind of wrong can be done if delegation is performed to the right actors, and whether we can detect it. This could potentially result on a parallel economy for rewards.
• Problem is that this might incentivise ‘lazy’ users into ‘malicious’ users. In the theoretical method ‘lazy’ are the same as ‘malicious’, so it does not affect. However, practically, it might make sense to have a more careful idea.
• Seems reasonable to have some tolerance to potentially make some lazy users malicious.