jose-compu / jose-compu/opencircom
Circuit: Permutation and sort verification
- Dominant language
- Circom
- Stars
- 2
- Forks
- 2
- PR merge metrics
- No merged PRs in 30d
Description
## Summary
Add **permutation / sort verification** circuits.
## Motivation
Prove that output array is a permutation of input (e.g. shuffle, auction ordering, ballot sorting) without revealing order. Common in MACI, poker, and fair ordering protocols. Not in current library.
## Proposed templates
- `IsPermutation(n)` — prove `out[]` is a reordering of `in[]` (via sorted hashes or grand-product argument)
- `SortedCheck(n, ascending)` — prove array is sorted (building block)
## References
- circomlib `Permutation` / grand-product patterns
- Plonkish permutation arguments (simplified for R1CS)
## Acceptance criteria
- [ ] Valid permutation accepted; invalid rejected
- [ ] Constraint count for n=8, n=32 documented
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reviewing the circomlib Permutation and grand-product patterns, then compare them with the proposed simplified R1CS approach. Define the scope for IsPermutation(n) and SortedCheck(n, ascending), including how invalid inputs are rejected. Done means valid permutations pass, invalid ones fail, and constraint counts for n=8 and n=32 are documented.
Written by the indexing model from the issue text.
Assessment
- Domain
- cryptography
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100