https://github.com/cronokirby/butterfly-test
Testing an algorithm for creating routing networks from permutations
Science Score: 13.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
○CITATION.cff file
-
✓codemeta.json file
Found codemeta.json file -
○.zenodo.json file
-
○DOI references
-
○Academic publication links
-
○Academic email domains
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (4.7%) to scientific vocabulary
Repository
Testing an algorithm for creating routing networks from permutations
Basic Info
- Host: GitHub
- Owner: cronokirby
- License: other
- Language: Jupyter Notebook
- Default Branch: main
- Size: 11.7 KB
Statistics
- Stars: 2
- Watchers: 0
- Forks: 0
- Open Issues: 0
- Releases: 0
Metadata Files
README.md
butterfly-test
A little test script, and implementation of a greedy algorithm for creating Benes (double butterfly) sorting networks.
These are a way to encode permutations using a fixed topology of switches. Each switch has two inputs and two outputs, and either swaps them, or lets them pass through. This provides a way to encode that the input and output values are permutations of each other, using a boolean circuit with a fixed topology, just with variable switch values.
This is very useful for ZK proofs, when compiling random access machines to circuits. It's much easier to prove the integrity of memory accesses if these accesses or sorted by address. This can be done outside of the circuit, but the circuit needs to attest that the address sorted accesses are a permutation of the time sorted addresses. Using a routing network allows doing this with a fixed circuit, but with private inputs for the switch values.
Owner
- Name: Lúcás Meier
- Login: cronokirby
- Kind: user
- Location: Seattle
- Website: https://cronokirby.com
- Repositories: 177
- Profile: https://github.com/cronokirby
"apprentice cryptographer"
GitHub Events
Total
Last Year
Issues and Pull Requests
Last synced: over 1 year ago
All Time
- Total issues: 0
- Total pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Total issue authors: 0
- Total pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 0
- Pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Issue authors: 0
- Pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0