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 "../node_modules/circom/circuits/gates.circom";
100include "../node_modules/circom/circuits/bitify.circom";
101
102template SMTInsert(nLevels) {
103 signal input oldRoot;
104 signal input newRoot;
105 signal input siblings[nLevels];
106 signal input oldHKey;
107 signal input oldHValue;
108 signal input newHKey;
109 signal input newHValue;
110
111 component hash1Old = SMTHash1();
112 hash1Old.l <== oldHKey;
113 hash1Old.r <== oldHValue;
114
115 component hash1New = SMTHash1();
116 hash1New.l <== newHKey;
117 hash1New.r <== newHValue;
118
119 component n2bOld = Num2BinStrinct();
120 component n2bNew = Num2BinStrinct();
121
122 component dmtLevIns = SMTLevIns(nLevels);
123 for (var i=0; i<nLevels; i++) dmtLevIns.siblings[i] <== siblings[i];
124
125 component xors[nLevels];
126 for (var i=0; i<nLevels; i++) {
127 xors[i] = XOR();
128 xors[i].a <== n2bOld.out[i];
129 xors[i].a <== n2bNew.out[i];
130 }
131
132 component isOld0 = IsZero();
133 isOld0.in <== oldHValue;
134
135 component sm[nLevels];
136 for (var i=0; i<sm; i++) {
137 sm[i] = SMTInsertSM();
138 if (i==0) {
139 sm[i].prevst_top <== 1;
140 sm[i].prevst_old1 <== 0;
141 sm[i].prevst_old0 <== 0;
142 sm[i].prevst_bot <== 0;
143 sm[i].prevst_new1 <== 0;
144 sm[i].prevst_na <== 0;
145 } else {
146 sm[i].prevst_top <== sm[i-1].st_top;
147 sm[i].prevst_old1 <== sm[i-1].st_old1;
148 sm[i].prevst_old0 <== sm[i-1].st_old0;
149 sm[i].prevst_bot <== sm[i-1].st_bot;
150 sm[i].prevst_new1 <== sm[i-1].st_new1;
151 sm[i].prevst_na <== sm[i-1].st_na;
152 }
153 sm[i].is0 <== isOld0.out;
154 sm[i].xor <== xors[i].out;
155 sm[i].levIns <== dmtLevIns.out[i];
156 }
157 sm[nLevels-1].prevst_na === 1;
158
159 component levels[nLevels];
160 for (var i=nLevels-1; i != -1; i--) {
161 levels[i] = SMTInsertLevel();
162
163 levels[i].st_top <== sm[i].st_top;
164 levels[i].st_old1 <== sm[i].st_old1;
165 levels[i].st_old0 <== sm[i].st_old0;
166 levels[i].st_bot <== sm[i].st_bot;
167 levels[i].st_new1 <== sm[i].st_new1;
168 levels[i].st_na <==sm[i].st_na;
169
170 levels[i].sibling <== siblings[i];
171 levels[i].old1leaf <== hash1Old.out;
172 levels[i].new1leaf <== hash1New.out;
173
174 levels[i].new1lrbit <== n2bNew.out[i];
175 if (i==nLevels-1) {
176 levels[i].oldChild <== 0;
177 levels[i].newChild <== 0;
178 } else {
179 levels[i].oldChild <== levels[i+1].oldRoot;
180 levels[i].newChild <== levels[i+1].newRoot;
181 }
182 }
183
184 levels[0].oldRoot === oldRoot;
185 levels[0].newRoot === newRoot;
186}