IntersectMBO / IntersectMBO/mithril
Review the fairness of the single signature selection algorithm for the non-recursive SNARK
- Dominant language
- Rust
- Stars
- 154
- Forks
- 51
- Avg merge
- 1d 23h
- Merged PRs (30d)
- 38
Description
## Why
`select_valid_signatures_for_k_indices` picks the signatures that enter the proof by hash priority, then deduplicates by keeping the smallest hash per index. The algorithm is deterministic and tested, but its fairness across signers over many epochs has not been analyzed.
## What
Analyze the selection algorithm for fairness and for manipulability, and adjust it if the analysis calls for it.
## How
- [ ] Model the selection probability per signer as a function of the stake and of the number of won lotteries
- [ ] Check whether a signer can influence its own selection odds
- [ ] Simulate the selection over many epochs and report the distribution
- [ ] Propose an adjustment if a bias is found, and cover it with property tests (`proof_system/halo2_snark/clerk.rs`)
## Later
- Could we extend this work to the concatenation proof?
- Impact on https://github.com/IntersectMBO/mithril/issues/2913?
Contributor guide
Research direction
Read proof_system/halo2_snark/clerk.rs and the existing tests for select_valid_signatures_for_k_indices first. Model and simulate selection probabilities across stake and won lotteries, then assess signer influence. Done means a fairness report, an adjustment if bias is found, and property tests covering the result.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- blockchain, cryptography
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100