Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Sorted

If we need an array to be sorted, we could sort the array out-of-circuit and pass in the sorted array, finally asserting that it is sorted indeed. To do this, we can simply check that consecutive elements are ordered, that is for all .

IsSorted

template IsSorted(n, b) {
  signal input in[n];
  signal output out;

  // range check
  for (var i = 0; i < n; i++) {
    _ <== Num2Bits(b)(in[i]);
  }

  // accumulator for in[i-1] <= in[i] checks
  var acc = 0;
  for (var i = 1; i < n; i++) {
    var isLessThan = LessEqThan(b)([in[i-1], in[i]]);
    acc += isLessThan;
  }

  // sorted only if all `n - 1` pairs are ordered
  out <== IsEqual()([acc, n - 1]);
}

Since the correctness of LessEqThan(b) is guaranteed only for inputs of at most b bits, we also add a range check using Num2Bits(b), which internally asserts that the input fits within b bits.

Each LessEqThan returns 1 for an ordered pair, so acc counts the ordered pairs. There are pairs, and the array is sorted only if all of them are ordered, so we return whether acc equals .

Be careful to not check whether acc is non-zero instead: that only tells that some pair is ordered, and an array like [0, 1, 2, 4, 3] would be considered sorted!

AssertSorted

template AssertSorted(n, b) {
  signal input in[n];

  // range check
  for (var i = 0; i < n; i++) {
    _ <== Num2Bits(b)(in[i]);
  }

  // accumulator for in[i-1] <= in[i] checks
  var acc = 0;
  for (var i = 1; i < n; i++) {
    var isLessThan = LessEqThan(b)([in[i-1], in[i]]);
    acc += isLessThan;
  }

  acc === n - 1;
}

If you would like to assert that the array is sorted instead of returning 0 or 1, you can simply constrain acc === n-1 at the end, instead of comparing it with IsEqual.

Constraint Count

Both circuits range-check each element with Num2Bits(b), and compare each consecutive pair with LessEqThan(b), for a total of non-linear constraints; IsSorted has two more for its final IsEqual. For 10 elements of 16 bits, AssertSorted has 313 constraints and IsSorted has 315.