Last active
August 15, 2023 22:30
-
-
Save mattdesl/a2dd49e540d69f3644f6e55da3252a98 to your computer and use it in GitHub Desktop.
verify list of indices are a valid permutation in circom zk circuit
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
pragma circom 2.1.5; | |
include "circomlib/circuits/comparators.circom"; | |
/* | |
Verifies a permutation is valid and includes all indices once and only once. | |
Examples: | |
[ 0 1 2 3 ] == OK | |
[ 1 2 0 3 ] == OK | |
[ 0 2 0 3 ] == NOT OK | |
[ 1 1 2 3 ] == NOT OK | |
*/ | |
template Verifier(N) { | |
signal input indices[N]; | |
signal output out; | |
// Check all values are < N | |
component lt[N]; | |
for (var i = 0; i < N; i++) { | |
var num = indices[i]; | |
// 1. Ensure num is less than N | |
// numMaxBits = 16, max number of elements in the array must be < 2^16 | |
lt[i] = LessThan(16); | |
lt[i].in[0] <== num; | |
lt[i].in[1] <== N; | |
lt[i].out === 1; // assert | |
} | |
// Check that each element is visited once | |
var visited[N]; | |
for (var i = 0; i < N; i++) { | |
visited[i] = 0; | |
} | |
for (var i = 0; i < N; i++) { | |
visited[indices[i]] = 1; | |
} | |
var sum = 0; | |
for (var i = 0; i < N; i++) { | |
sum += visited[i]; | |
} | |
// ensure that the sum adds up to the N value | |
component eq = IsEqual(); | |
eq.in[0] <-- sum; // note: no constraint here; is this a problem? | |
eq.in[1] <== N; | |
eq.out === 1; | |
out <== eq.out; | |
} | |
// Operates on a fixed array of N size | |
component main = Verifier(4); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment