1/*
  2    Copyright 2018 0KIMS association.
  3
  4    This file is part of circom (Zero Knowledge Circuit Compiler).
  5
  6    circom is a free software: you can redistribute it and/or modify it
  7    under the terms of the GNU General Public License as published by
  8    the Free Software Foundation, either version 3 of the License, or
  9    (at your option) any later version.
 10
 11    circom is distributed in the hope that it will be useful, but WITHOUT
 12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 13    or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
 14    License for more details.
 15
 16    You should have received a copy of the GNU General Public License
 17    along with circom. If not, see <https://www.gnu.org/licenses/>.
 18*/
 19
 20/*
 21
 22This component finds the level where the oldInsert is done.
 23The rules are:
 24
 25levIns[i] == 1 if its level and all the child levels have a sibling of 0 and
 26the parent level has a sibling != 0.  Considere that the root level always has
 27a parent with a sibling != 0.
 28
 29
 30                                  ┌──────────────┐
 31                                  │              │
 32                                  │              │───▶ levIns[0] <== (1-done[i])
 33                                  │              │
 34                                  └──────────────┘
 35                                          ▲
 36                                          │
 37                                          │
 38                                       done[0]
 39
 40
 41
 42                                      done[i-1] <== levIns[i] + done[i]
 43                                          ▲
 44                                          │
 45                                          │
 46                   ┌───────────┐  ┌──────────────┐
 47                   │           │  │              │
 48   sibling[i-1]───▶│IsZero[i-1]│─▶│              │───▶ levIns[i] <== (1-done[i])*(1-isZero[i-1].out)
 49                   │           │  │              │
 50                   └───────────┘  └──────────────┘
 51                                          ▲
 52                                          │
 53                                          │
 54                                       done[i]
 55
 56
 57
 58                                     done[n-2] <== levIns[n-1]
 59                                         ▲
 60                                         │
 61                                         │
 62                  ┌───────────┐  ┌──────────────┐
 63                  │           │  │              │
 64  sibling[n-2]───▶│IsZero[n-2]│─▶│              │────▶ levIns[n-1] <== (1-isZero[n-2].out)
 65                  │           │  │              │
 66                  └───────────┘  └──────────────┘
 67
 68                  ┌───────────┐
 69                  │           │
 70  sibling[n-1]───▶│IsZero[n-1]│────▶ === 0
 71                  │           │
 72                  └───────────┘
 73
 74 */
 75
 76template SMTLevIns(nLevels) {
 77    signal input enabled;
 78    signal input siblings[nLevels];
 79    signal output levIns[nLevels];
 80    signal done[nLevels-1];        // Indicates if the insLevel has aready been detected.
 81
 82    var i;
 83
 84    component isZero[nLevels];
 85
 86    for (i=0; i<nLevels; i++) {
 87        isZero[i] = IsZero();
 88        isZero[i].in <== siblings[i];
 89    }
 90
 91    // The last level must always have a sibling of 0. If not, then it cannot be inserted.
 92    (isZero[nLevels-1].out - 1) * enabled === 0;
 93
 94    levIns[nLevels-1] <== (1-isZero[nLevels-2].out);
 95    done[nLevels-2] <== levIns[nLevels-1];
 96    for (i=nLevels-2; i>0; i--) {
 97        levIns[i] <== (1-done[i])*(1-isZero[i-1].out)
 98        done[i-1] <== levIns[i] + done[i];
 99    }
100
101    levIns[0] <== (1-done[0]);
102}