circomlib/circuits/smt/smtinsert.circom
circuits/smt/smtinsert.circomRaw
1/***************************************************************************************************
2
3Insert to an empty leaf
4=======================
5
6 STATE OLD STATE NEW STATE
7 ===== ========= =========
8
9 oldRoot newRoot
10 ▲ ▲
11 │ │
12 ┌───────┐ ┏━━━┻━━━┓ ┌───────┐ ┏━━━┻━━━┓
13 top │Sibling├────▶┃ Hash ┃◀─┐ │Sibling├────▶┃ Hash ┃◀─┐
14 └───────┘ ┗━━━━━━━┛ │ └───────┘ ┗━━━━━━━┛ │
15 │ │
16 │ │
17 ┏━━━┻━━━┓ ┌───────┐ ┏━━━┻━━━┓ ┌───────┐
18 top ┌─────▶┃ Hash ┃◀──┤Sibling│ ┌─────▶┃ Hash ┃◀──┤Sibling│
19 │ ┗━━━━━━━┛ └───────┘ │ ┗━━━━━━━┛ └───────┘
20 │ │
21 │ │
22 ┌───────┐ ┏━━━┻━━━┓ ┌───────┐ ┏━━━┻━━━┓
23 top │Sibling├──▶┃ Hash ┃◀─────┐ │Sibling├──▶┃ Hash ┃◀─────┐
24 └───────┘ ┗━━━━━━━┛ │ └───────┘ ┗━━━━━━━┛ │
25 │ │
26 │ │
27 ┌────┴────┐ ┌────┴────┐
28 old0 │ 0 │ │New1Leaf │
29 └─────────┘ └─────────┘
30
31
32 ┏━━━━━━━┓ ┏━━━━━━━┓
33 na ┃ Hash ┃ ┃ Hash ┃
34 ┗━━━━━━━┛ ┗━━━━━━━┛
35
36
37 ┏━━━━━━━┓ ┏━━━━━━━┓
38 na ┃ Hash ┃ ┃ Hash ┃
39 ┗━━━━━━━┛ ┗━━━━━━━┛
40
41
42
43Insert to a used leaf.
44=====================
45
46 STATE OLD STATE NEW STATE
47 ===== ========= =========
48
49
50 oldRoot newRoot
51 ▲ ▲
52 │ │
53 ┌───────┐ ┏━━━┻━━━┓ ┌───────┐ ┏━━━┻━━━┓
54 top │Sibling├────▶┃ Hash ┃◀─┐ │Sibling├────▶┃ Hash ┃◀─┐
55 └───────┘ ┗━━━━━━━┛ │ └───────┘ ┗━━━━━━━┛ │
56 │ │
57 │ │
58 ┏━━━┻━━━┓ ┌───────┐ ┏━━━┻━━━┓ ┌───────┐
59 top ┌─────▶┃ Hash ┃◀──┤Sibling│ ┌─────▶┃ Hash ┃◀──┤Sibling│
60 │ ┗━━━━━━━┛ └───────┘ │ ┗━━━━━━━┛ └───────┘
61 │ │
62 │ │
63 ┌───────┐ ┏━━━┻━━━┓ ┌───────┐ ┏━━━┻━━━┓
64 top │Sibling├──▶┃ Hash ┃◀─────┐ │Sibling├──▶┃ Hash ┃◀─────┐
65 └───────┘ ┗━━━━━━━┛ │ └───────┘ ┗━━━━━━━┛ │
66 │ │
67 │ │
68 ┌────┴────┐ ┏━━━┻━━━┓ ┌───────┐
69 bot │Old1Leaf │ ┌─────▶┃ Hash ┃◀──┼─ 0 │
70 └─────────┘ │ ┗━━━━━━━┛ └───────┘
71 │
72 │
73 ┏━━━━━━━┓ ┌───────┐ ┏━━━┻━━━┓
74 bot ┃ Hash ┃ │ 0 ─┼──▶┃ Hash ┃◀─────┐
75 ┗━━━━━━━┛ └───────┘ ┗━━━━━━━┛ │
76 │
77 │
78 ┏━━━━━━━┓ ┏━━━┻━━━┓ ┌───────┐
79 bot ┃ Hash ┃ ┌─────▶┃ Hash ┃◀──│ 0 │
80 ┗━━━━━━━┛ │ ┗━━━━━━━┛ └───────┘
81 │
82 │
83 ┏━━━━━━━┓ ┌─────────┐ ┏━━━┻━━━┓ ┌─────────┐
84 new1 ┃ Hash ┃ │Old1Leaf ├──▶┃ Hash ┃◀──│New1Leaf │
85 ┗━━━━━━━┛ └─────────┘ ┗━━━━━━━┛ └─────────┘
86
87
88 ┏━━━━━━━┓ ┏━━━━━━━┓
89 na ┃ Hash ┃ ┃ Hash ┃
90 ┗━━━━━━━┛ ┗━━━━━━━┛
91
92
93 ┏━━━━━━━┓ ┏━━━━━━━┓
94 na ┃ Hash ┃ ┃ Hash ┃
95 ┗━━━━━━━┛ ┗━━━━━━━┛
96
97
98Fnction
99fnc[0] fnc[1]
1000 0 NOP
1010 1 UPDATE
1021 0 INSERT
1031 1 DELETE
104
105
106***************************************************************************************************/
107
108include "../gates.circom";
109include "../bitify.circom";
110include "../comparators.circom";
111include "../switcher.circom";
112include "smtlevins.circom";
113include "smtinsertlevel.circom";
114include "smtinsertsm.circom";
115include "smthash.circom";
116
117template SMTInsert(nLevels) {
118 signal input oldRoot;
119 signal input newRoot;
120 signal input siblings[nLevels];
121 signal input oldKey;
122 signal input oldValue;
123 signal input isOld0;
124 signal input newKey;
125 signal input newValue;
126 signal input fnc[2];
127
128 signal enabled;
129
130 enabled <== fnc[0] + fnc[1] - fnc[0]*fnc[1]
131
132 component hash1Old = SMTHash1();
133 hash1Old.key <== oldKey;
134 hash1Old.value <== oldValue;
135
136 component hash1New = SMTHash1();
137 hash1New.key <== newKey;
138 hash1New.value <== newValue;
139
140 component n2bOld = Num2Bits_strict();
141 component n2bNew = Num2Bits_strict();
142
143 n2bOld.in <== oldKey;
144 n2bNew.in <== newKey;
145
146 component smtLevIns = SMTLevIns(nLevels);
147 for (var i=0; i<nLevels; i++) smtLevIns.siblings[i] <== siblings[i];
148 smtLevIns.enabled <== enabled;
149
150 component xors[nLevels];
151 for (var i=0; i<nLevels; i++) {
152 xors[i] = XOR();
153 xors[i].a <== n2bOld.out[i];
154 xors[i].b <== n2bNew.out[i];
155 }
156
157 component sm[nLevels];
158 for (var i=0; i<nLevels; i++) {
159 sm[i] = SMTInsertSM();
160 if (i==0) {
161 sm[i].prev_top <== enabled;
162 sm[i].prev_old0 <== 0;
163 sm[i].prev_bot <== 0;
164 sm[i].prev_new1 <== 0;
165 sm[i].prev_na <== 1-enabled;
166 sm[i].prev_upd <== 0;
167 } else {
168 sm[i].prev_top <== sm[i-1].st_top;
169 sm[i].prev_old0 <== sm[i-1].st_old0;
170 sm[i].prev_bot <== sm[i-1].st_bot;
171 sm[i].prev_new1 <== sm[i-1].st_new1;
172 sm[i].prev_na <== sm[i-1].st_na;
173 sm[i].prev_upd <== sm[i-1].st_upd;
174 }
175 sm[i].is0 <== isOld0;
176 sm[i].xor <== xors[i].out;
177 sm[i].fnc[0] <== fnc[0];
178 sm[i].fnc[1] <== fnc[1];
179 sm[i].levIns <== smtLevIns.levIns[i];
180 }
181 sm[nLevels-1].st_na === 1;
182
183 component levels[nLevels];
184 for (var i=nLevels-1; i != -1; i--) {
185 levels[i] = SMTInsertLevel();
186
187 levels[i].st_top <== sm[i].st_top;
188 levels[i].st_old0 <== sm[i].st_old0;
189 levels[i].st_bot <== sm[i].st_bot;
190 levels[i].st_new1 <== sm[i].st_new1;
191 levels[i].st_na <== sm[i].st_na;
192 levels[i].st_upd <== sm[i].st_upd;
193
194 levels[i].sibling <== siblings[i];
195 levels[i].old1leaf <== hash1Old.out;
196 levels[i].new1leaf <== hash1New.out;
197
198 levels[i].newlrbit <== n2bNew.out[i];
199 if (i==nLevels-1) {
200 levels[i].oldChild <== 0;
201 levels[i].newChild <== 0;
202 } else {
203 levels[i].oldChild <== levels[i+1].oldRoot;
204 levels[i].newChild <== levels[i+1].newRoot;
205 }
206 }
207
208 component topSwitcher = Switcher();
209
210 topSwitcher.sel <== fnc[0]*fnc[1];
211 topSwitcher.L <== levels[0].oldRoot;
212 topSwitcher.R <== levels[0].newRoot;
213
214 topSwitcher.outL === oldRoot*enabled;
215 topSwitcher.outR === newRoot*enabled;
216}