Skip to content

Instantly share code, notes, and snippets.

@mattdesl
Last active August 15, 2023 22:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mattdesl/a2dd49e540d69f3644f6e55da3252a98 to your computer and use it in GitHub Desktop.
Save mattdesl/a2dd49e540d69f3644f6e55da3252a98 to your computer and use it in GitHub Desktop.
verify list of indices are a valid permutation in circom zk circuit
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