Review the fairness of the single signature selection algorithm for the non-recursive SNARK
Maintainers usually reply within 2 days
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 38/100
- Issue type
- Feature
- Clarity
- Mostly clear
- Activity status
- Quiet
- Tech stack
- rust
- Domain
- blockchain, cryptography
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.
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?
- Dominant language
- Rust
- Stars
- 155
- Forks
- 52
- Avg merge
- 2d 17h
- Merged PRs (30d)
- 37
Getting set up
- No Dockerfile or Docker Compose file
- Has a pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from IntersectMBO/mithril
-
Difficulty 2/5 1-3 hours Newbie friendliness 64/100
IntersectMBO/mithril#1605 · 2 comments ·
Maintainers usually reply within 2 days
-
spike :satellite:
Difficulty 5/5 Over a week Newbie friendliness 10/100
IntersectMBO/mithril#3701 ·
Maintainers usually reply within 2 days
-
Publish a DNSLink record of the immutable archives IPNS name in the Mithril networks DNS zonesPossibly taken @jpraynaud claimed this 2 days ago. Openfeature :rocket:
IntersectMBO/mithril#3700 · 1 assignee ·
Maintainers usually reply within 2 days
-
feature :rocket:
Difficulty 4/5 3-5 days Newbie friendliness 25/100
IntersectMBO/mithril#3699 ·
Maintainers usually reply within 2 days
-
feature :rocket:
Difficulty 4/5 3-5 days Newbie friendliness 35/100
IntersectMBO/mithril#3698 ·
Maintainers usually reply within 2 days
All issues in IntersectMBO/mithril
Similar issues
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
storytold/photocraft#14822 ·
Maintainers usually reply within 1 day
-
bug css
Difficulty 2/5 1-3 hours Newbie friendliness 66/100
dginev/latexml-oxide#853 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
Maintainers usually reply within 2 days
-
[Bug] export_build_environment admits its output directory only after the export ran in the build computerPossibly taken @viniciusdsandrade claimed this today. Open
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 1 day