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 old1 │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***************************************************************************************************/
98
99include "../gates.circom";
100include "../bitify.circom";
101include "../comparators.circom";
102include "../switcher.circom";
103include "smtlevins.circom";
104include "smtinsertlevel.circom";
105include "smtinsertsm.circom";
106include "smthash.circom";
107
108template SMTInsert(nLevels) {
109 signal input oldRoot;
110 signal input newRoot;
111 signal input siblings[nLevels];
112 signal input oldKey;
113 signal input oldValue;
114 signal input isOld0;
115 signal input newKey;
116 signal input newValue;
117
118 component hash1Old = SMTHash1();
119 hash1Old.key <== oldKey;
120 hash1Old.value <== oldValue;
121
122 component hash1New = SMTHash1();
123 hash1New.key <== newKey;
124 hash1New.value <== newValue;
125
126 component n2bOld = Num2Bits_strict();
127 component n2bNew = Num2Bits_strict();
128
129 n2bOld.in <== oldKey;
130 n2bNew.in <== newKey;
131
132 component smtLevIns = SMTLevIns(nLevels);
133 for (var i=0; i<nLevels; i++) smtLevIns.siblings[i] <== siblings[i];
134
135 component xors[nLevels];
136 for (var i=0; i<nLevels; i++) {
137 xors[i] = XOR();
138 xors[i].a <== n2bOld.out[i];
139 xors[i].b <== n2bNew.out[i];
140 }
141
142 component sm[nLevels];
143 for (var i=0; i<nLevels; i++) {
144 sm[i] = SMTInsertSM();
145 if (i==0) {
146 sm[i].prev_top <== 1;
147 sm[i].prev_old1 <== 0;
148 sm[i].prev_old0 <== 0;
149 sm[i].prev_bot <== 0;
150 sm[i].prev_new1 <== 0;
151 sm[i].prev_na <== 0;
152 } else {
153 sm[i].prev_top <== sm[i-1].st_top;
154 sm[i].prev_old1 <== sm[i-1].st_old1;
155 sm[i].prev_old0 <== sm[i-1].st_old0;
156 sm[i].prev_bot <== sm[i-1].st_bot;
157 sm[i].prev_new1 <== sm[i-1].st_new1;
158 sm[i].prev_na <== sm[i-1].st_na;
159 }
160 sm[i].is0 <== isOld0;
161 sm[i].xor <== xors[i].out;
162 sm[i].levIns <== smtLevIns.levIns[i];
163 }
164 sm[nLevels-1].st_na === 1;
165
166 component levels[nLevels];
167 for (var i=nLevels-1; i != -1; i--) {
168 levels[i] = SMTInsertLevel();
169
170 levels[i].st_top <== sm[i].st_top;
171 levels[i].st_old1 <== sm[i].st_old1;
172 levels[i].st_old0 <== sm[i].st_old0;
173 levels[i].st_bot <== sm[i].st_bot;
174 levels[i].st_new1 <== sm[i].st_new1;
175 levels[i].st_na <==sm[i].st_na;
176
177 levels[i].sibling <== siblings[i];
178 levels[i].old1leaf <== hash1Old.out;
179 levels[i].new1leaf <== hash1New.out;
180
181 levels[i].newlrbit <== n2bNew.out[i];
182 if (i==nLevels-1) {
183 levels[i].oldChild <== 0;
184 levels[i].newChild <== 0;
185 } else {
186 levels[i].oldChild <== levels[i+1].oldRoot;
187 levels[i].newChild <== levels[i+1].newRoot;
188 }
189 }
190
191 levels[0].oldRoot === oldRoot;
192 levels[0].newRoot === newRoot;
193}