hermez-node/common/zk.go
common/zk.goRaw
1// Package common contains all the common data structures used at the
2// hermez-node, zk.go contains the zkSnark inputs used to generate the proof
3package common
4
5import (
6 "encoding/json"
7 "math/big"
8
9 "github.com/hermeznetwork/hermez-node/log"
10 "github.com/mitchellh/mapstructure"
11)
12
13// ZKMetadata contains ZKInputs metadata that is not used directly in the
14// ZKInputs result, but to calculate values for Hash check
15type ZKMetadata struct {
16 // Circuit parameters
17 // absolute maximum of L1 or L2 transactions allowed
18 NTx uint32
19 // merkle tree depth
20 NLevels uint32
21 MaxLevels uint32
22 // absolute maximum of L1 transaction allowed
23 MaxL1Tx uint32
24 // Maximum number of Idxs where Fees can be send in a batch (currently
25 // is constant for all circuits: 64)
26 MaxFeeIdxs uint32
27
28 L1TxsData [][]byte
29 L2TxsData [][]byte
30 ChainID uint16
31}
32
33// ZKInputs represents the inputs that will be used to generate the zkSNARK proof
34type ZKInputs struct {
35 Metadata ZKMetadata
36
37 //
38 // General
39 //
40
41 // inputs for final `hashGlobalInputs`
42 // OldLastIdx is the last index assigned to an account
43 OldLastIdx *big.Int `json:"oldLastIdx"` // uint64 (max nLevels bits)
44 // OldStateRoot is the current state merkle tree root
45 OldStateRoot *big.Int `json:"oldStateRoot"` // Hash
46 // GlobalChainID is the blockchain ID (0 for Ethereum mainnet). This value can be get from the smart contract.
47 GlobalChainID *big.Int `json:"globalChainID"` // uint16
48 // FeeIdxs is an array of merkle tree indexes where the coordinator will receive the accumulated fees
49 FeeIdxs []*big.Int `json:"feeIdxs"` // uint64 (max nLevels bits), len: [maxFeeIdxs]
50
51 // accumulate fees
52 // FeePlanTokens contains all the tokenIDs for which the fees are being accumulated
53 FeePlanTokens []*big.Int `json:"feePlanTokens"` // uint32 (max 32 bits), len: [maxFeeIdxs]
54
55 //
56 // Txs (L1&L2)
57 //
58
59 // transaction L1-L2
60 // TxCompressedData
61 TxCompressedData []*big.Int `json:"txCompressedData"` // big.Int (max 251 bits), len: [nTx]
62 // TxCompressedDataV2, only used in L2Txs, in L1Txs is set to 0
63 TxCompressedDataV2 []*big.Int `json:"txCompressedDataV2"` // big.Int (max 193 bits), len: [nTx]
64
65 // FromIdx
66 FromIdx []*big.Int `json:"fromIdx"` // uint64 (max nLevels bits), len: [nTx]
67 // AuxFromIdx is the Idx of the new created account which is consequence of a L1CreateAccountTx
68 AuxFromIdx []*big.Int `json:"auxFromIdx"` // uint64 (max nLevels bits), len: [nTx]
69
70 // ToIdx
71 ToIdx []*big.Int `json:"toIdx"` // uint64 (max nLevels bits), len: [nTx]
72 // AuxToIdx is the Idx of the Tx that has 'toIdx==0', is the coordinator who will find which Idx corresponds to the 'toBJJAy' or 'toEthAddr'
73 AuxToIdx []*big.Int `json:"auxToIdx"` // uint64 (max nLevels bits), len: [nTx]
74 // ToBJJAy
75 ToBJJAy []*big.Int `json:"toBjjAy"` // big.Int, len: [nTx]
76 // ToEthAddr
77 ToEthAddr []*big.Int `json:"toEthAddr"` // ethCommon.Address, len: [nTx]
78
79 // OnChain determines if is L1 (1/true) or L2 (0/false)
80 OnChain []*big.Int `json:"onChain"` // bool, len: [nTx]
81
82 //
83 // Txs/L1Txs
84 //
85 // NewAccount boolean (0/1) flag set 'true' when L1 tx creates a new account (fromIdx==0)
86 NewAccount []*big.Int `json:"newAccount"` // bool, len: [nTx]
87 // LoadAmountF encoded as float16
88 LoadAmountF []*big.Int `json:"loadAmountF"` // uint16, len: [nTx]
89 // FromEthAddr
90 FromEthAddr []*big.Int `json:"fromEthAddr"` // ethCommon.Address, len: [nTx]
91 // FromBJJCompressed boolean encoded where each value is a *big.Int
92 FromBJJCompressed [][256]*big.Int `json:"fromBjjCompressed"` // bool array, len: [nTx][256]
93
94 //
95 // Txs/L2Txs
96 //
97
98 // RqOffset relative transaction position to be linked. Used to perform atomic transactions.
99 RqOffset []*big.Int `json:"rqOffset"` // uint8 (max 3 bits), len: [nTx]
100
101 // transaction L2 request data
102 // RqTxCompressedDataV2
103 RqTxCompressedDataV2 []*big.Int `json:"rqTxCompressedDataV2"` // big.Int (max 251 bits), len: [nTx]
104 // RqToEthAddr
105 RqToEthAddr []*big.Int `json:"rqToEthAddr"` // ethCommon.Address, len: [nTx]
106 // RqToBJJAy
107 RqToBJJAy []*big.Int `json:"rqToBjjAy"` // big.Int, len: [nTx]
108
109 // transaction L2 signature
110 // S
111 S []*big.Int `json:"s"` // big.Int, len: [nTx]
112 // R8x
113 R8x []*big.Int `json:"r8x"` // big.Int, len: [nTx]
114 // R8y
115 R8y []*big.Int `json:"r8y"` // big.Int, len: [nTx]
116
117 //
118 // State MerkleTree Leafs transitions
119 //
120
121 // state 1, value of the sender (from) account leaf
122 TokenID1 []*big.Int `json:"tokenID1"` // uint32, len: [nTx]
123 Nonce1 []*big.Int `json:"nonce1"` // uint64 (max 40 bits), len: [nTx]
124 Sign1 []*big.Int `json:"sign1"` // bool, len: [nTx]
125 Ay1 []*big.Int `json:"ay1"` // big.Int, len: [nTx]
126 Balance1 []*big.Int `json:"balance1"` // big.Int (max 192 bits), len: [nTx]
127 EthAddr1 []*big.Int `json:"ethAddr1"` // ethCommon.Address, len: [nTx]
128 Siblings1 [][]*big.Int `json:"siblings1"` // big.Int, len: [nTx][nLevels + 1]
129 // Required for inserts and deletes, values of the CircomProcessorProof (smt insert proof)
130 IsOld0_1 []*big.Int `json:"isOld0_1"` // bool, len: [nTx]
131 OldKey1 []*big.Int `json:"oldKey1"` // uint64 (max 40 bits), len: [nTx]
132 OldValue1 []*big.Int `json:"oldValue1"` // Hash, len: [nTx]
133
134 // state 2, value of the receiver (to) account leaf
135 // if Tx is an Exit, state 2 is used for the Exit Merkle Proof
136 TokenID2 []*big.Int `json:"tokenID2"` // uint32, len: [nTx]
137 Nonce2 []*big.Int `json:"nonce2"` // uint64 (max 40 bits), len: [nTx]
138 Sign2 []*big.Int `json:"sign2"` // bool, len: [nTx]
139 Ay2 []*big.Int `json:"ay2"` // big.Int, len: [nTx]
140 Balance2 []*big.Int `json:"balance2"` // big.Int (max 192 bits), len: [nTx]
141 EthAddr2 []*big.Int `json:"ethAddr2"` // ethCommon.Address, len: [nTx]
142 Siblings2 [][]*big.Int `json:"siblings2"` // big.Int, len: [nTx][nLevels + 1]
143 // newExit determines if an exit transaction has to create a new leaf in the exit tree
144 NewExit []*big.Int `json:"newExit"` // bool, len: [nTx]
145 // Required for inserts and deletes, values of the CircomProcessorProof (smt insert proof)
146 IsOld0_2 []*big.Int `json:"isOld0_2"` // bool, len: [nTx]
147 OldKey2 []*big.Int `json:"oldKey2"` // uint64 (max 40 bits), len: [nTx]
148 OldValue2 []*big.Int `json:"oldValue2"` // Hash, len: [nTx]
149
150 // state 3, value of the account leaf receiver of the Fees
151 // fee tx
152 // State fees
153 TokenID3 []*big.Int `json:"tokenID3"` // uint32, len: [maxFeeIdxs]
154 Nonce3 []*big.Int `json:"nonce3"` // uint64 (max 40 bits), len: [maxFeeIdxs]
155 Sign3 []*big.Int `json:"sign3"` // bool, len: [maxFeeIdxs]
156 Ay3 []*big.Int `json:"ay3"` // big.Int, len: [maxFeeIdxs]
157 Balance3 []*big.Int `json:"balance3"` // big.Int (max 192 bits), len: [maxFeeIdxs]
158 EthAddr3 []*big.Int `json:"ethAddr3"` // ethCommon.Address, len: [maxFeeIdxs]
159 Siblings3 [][]*big.Int `json:"siblings3"` // Hash, len: [maxFeeIdxs][nLevels + 1]
160
161 //
162 // Intermediate States
163 //
164
165 // Intermediate States to parallelize witness computation
166 // Note: the Intermediate States (IS) of the last transaction does not
167 // exist. Meaning that transaction 3 (4th) will fill the parameters
168 // FromIdx[3] and ISOnChain[3], but last transaction (nTx-1) will fill
169 // FromIdx[nTx-1] but will not fill ISOnChain. That's why IS have
170 // length of nTx-1, while the other parameters have length of nTx.
171 // Last transaction does not need intermediate state since its output
172 // will not be used.
173
174 // decode-tx
175 // ISOnChain indicates if tx is L1 (true) or L2 (false)
176 ISOnChain []*big.Int `json:"imOnChain"` // bool, len: [nTx - 1]
177 // ISOutIdx current index account for each Tx
178 ISOutIdx []*big.Int `json:"imOutIdx"` // uint64 (max nLevels bits), len: [nTx - 1]
179 // rollup-tx
180 // ISStateRoot root at the moment of the Tx, the state root value once the Tx is processed into the state tree
181 ISStateRoot []*big.Int `json:"imStateRoot"` // Hash, len: [nTx - 1]
182 // ISExitTree root at the moment of the Tx the value once the Tx is processed into the exit tree
183 ISExitRoot []*big.Int `json:"imExitRoot"` // Hash, len: [nTx - 1]
184 // ISAccFeeOut accumulated fees once the Tx is processed
185 ISAccFeeOut [][]*big.Int `json:"imAccFeeOut"` // big.Int, len: [nTx - 1][maxFeeIdxs]
186 // fee-tx
187 // ISStateRootFee root at the moment of the Tx, the state root value once the Tx is processed into the state tree
188 ISStateRootFee []*big.Int `json:"imStateRootFee"` // Hash, len: [maxFeeIdxs - 1]
189 // ISInitStateRootFee state root once all L1-L2 tx are processed (before computing the fees-tx)
190 ISInitStateRootFee *big.Int `json:"imInitStateRootFee"` // Hash
191 // ISFinalAccFee final accumulated fees (before computing the fees-tx)
192 ISFinalAccFee []*big.Int `json:"imFinalAccFee"` // big.Int, len: [maxFeeIdxs - 1]
193}
194
195func bigIntsToStrings(v interface{}) interface{} {
196 switch c := v.(type) {
197 case *big.Int:
198 return c.String()
199 case []*big.Int:
200 r := make([]interface{}, len(c))
201 for i := range c {
202 r[i] = bigIntsToStrings(c[i])
203 }
204 return r
205 case [256]*big.Int:
206 r := make([]interface{}, len(c))
207 for i := range c {
208 r[i] = bigIntsToStrings(c[i])
209 }
210 return r
211 case [][]*big.Int:
212 r := make([]interface{}, len(c))
213 for i := range c {
214 r[i] = bigIntsToStrings(c[i])
215 }
216 return r
217 case [][256]*big.Int:
218 r := make([]interface{}, len(c))
219 for i := range c {
220 r[i] = bigIntsToStrings(c[i])
221 }
222 return r
223 case map[string]interface{}:
224 // avoid printing a warning when there is a struct type
225 default:
226 log.Warnf("bigIntsToStrings unexpected type: %T\n", v)
227 }
228 return nil
229}
230
231// MarshalJSON implements the json marshaler for ZKInputs
232func (z ZKInputs) MarshalJSON() ([]byte, error) {
233 var m map[string]interface{}
234 dec, err := mapstructure.NewDecoder(&mapstructure.DecoderConfig{
235 TagName: "json",
236 Result: &m,
237 })
238 if err != nil {
239 return nil, err
240 }
241 err = dec.Decode(z)
242 if err != nil {
243 return nil, err
244 }
245
246 for k, v := range m {
247 m[k] = bigIntsToStrings(v)
248 }
249 return json.Marshal(m)
250}
251
252// NewZKInputs returns a pointer to an initialized struct of ZKInputs
253func NewZKInputs(nTx, maxFeeIdxs, nLevels int) *ZKInputs {
254 zki := &ZKInputs{}
255 zki.Metadata.NTx = uint32(nTx)
256 zki.Metadata.MaxFeeIdxs = uint32(maxFeeIdxs)
257 zki.Metadata.NLevels = uint32(nLevels)
258
259 // General
260 zki.OldLastIdx = big.NewInt(0)
261 zki.OldStateRoot = big.NewInt(0)
262 zki.GlobalChainID = big.NewInt(0)
263 zki.FeeIdxs = newSlice(maxFeeIdxs)
264 zki.FeePlanTokens = newSlice(maxFeeIdxs)
265
266 // Txs
267 zki.TxCompressedData = newSlice(nTx)
268 zki.TxCompressedDataV2 = newSlice(nTx)
269 zki.FromIdx = newSlice(nTx)
270 zki.AuxFromIdx = newSlice(nTx)
271 zki.ToIdx = newSlice(nTx)
272 zki.AuxToIdx = newSlice(nTx)
273 zki.ToBJJAy = newSlice(nTx)
274 zki.ToEthAddr = newSlice(nTx)
275 zki.OnChain = newSlice(nTx)
276 zki.NewAccount = newSlice(nTx)
277
278 // L1
279 zki.LoadAmountF = newSlice(nTx)
280 zki.FromEthAddr = newSlice(nTx)
281 zki.FromBJJCompressed = make([][256]*big.Int, nTx)
282 for i := 0; i < len(zki.FromBJJCompressed); i++ {
283 // zki.FromBJJCompressed[i] = newSlice(256)
284 for j := 0; j < 256; j++ {
285 zki.FromBJJCompressed[i][j] = big.NewInt(0)
286 }
287 }
288
289 // L2
290 zki.RqOffset = newSlice(nTx)
291 zki.RqTxCompressedDataV2 = newSlice(nTx)
292 zki.RqToEthAddr = newSlice(nTx)
293 zki.RqToBJJAy = newSlice(nTx)
294 zki.S = newSlice(nTx)
295 zki.R8x = newSlice(nTx)
296 zki.R8y = newSlice(nTx)
297
298 // State MerkleTree Leafs transitions
299 zki.TokenID1 = newSlice(nTx)
300 zki.Nonce1 = newSlice(nTx)
301 zki.Sign1 = newSlice(nTx)
302 zki.Ay1 = newSlice(nTx)
303 zki.Balance1 = newSlice(nTx)
304 zki.EthAddr1 = newSlice(nTx)
305 zki.Siblings1 = make([][]*big.Int, nTx)
306 for i := 0; i < len(zki.Siblings1); i++ {
307 zki.Siblings1[i] = newSlice(nLevels + 1)
308 }
309 zki.IsOld0_1 = newSlice(nTx)
310 zki.OldKey1 = newSlice(nTx)
311 zki.OldValue1 = newSlice(nTx)
312
313 zki.TokenID2 = newSlice(nTx)
314 zki.Nonce2 = newSlice(nTx)
315 zki.Sign2 = newSlice(nTx)
316 zki.Ay2 = newSlice(nTx)
317 zki.Balance2 = newSlice(nTx)
318 zki.EthAddr2 = newSlice(nTx)
319 zki.Siblings2 = make([][]*big.Int, nTx)
320 for i := 0; i < len(zki.Siblings2); i++ {
321 zki.Siblings2[i] = newSlice(nLevels + 1)
322 }
323 zki.NewExit = newSlice(nTx)
324 zki.IsOld0_2 = newSlice(nTx)
325 zki.OldKey2 = newSlice(nTx)
326 zki.OldValue2 = newSlice(nTx)
327
328 zki.TokenID3 = newSlice(maxFeeIdxs)
329 zki.Nonce3 = newSlice(maxFeeIdxs)
330 zki.Sign3 = newSlice(maxFeeIdxs)
331 zki.Ay3 = newSlice(maxFeeIdxs)
332 zki.Balance3 = newSlice(maxFeeIdxs)
333 zki.EthAddr3 = newSlice(maxFeeIdxs)
334 zki.Siblings3 = make([][]*big.Int, maxFeeIdxs)
335 for i := 0; i < len(zki.Siblings3); i++ {
336 zki.Siblings3[i] = newSlice(nLevels + 1)
337 }
338
339 // Intermediate States
340 zki.ISOnChain = newSlice(nTx - 1)
341 zki.ISOutIdx = newSlice(nTx - 1)
342 zki.ISStateRoot = newSlice(nTx - 1)
343 zki.ISExitRoot = newSlice(nTx - 1)
344 zki.ISAccFeeOut = make([][]*big.Int, nTx-1)
345 for i := 0; i < len(zki.ISAccFeeOut); i++ {
346 zki.ISAccFeeOut[i] = newSlice(maxFeeIdxs)
347 }
348 zki.ISStateRootFee = newSlice(maxFeeIdxs - 1)
349 zki.ISInitStateRootFee = big.NewInt(0)
350 zki.ISFinalAccFee = newSlice(maxFeeIdxs - 1)
351
352 return zki
353}
354
355// newSlice returns a []*big.Int slice of length n with values initialized at
356// 0.
357// Is used to initialize all *big.Ints of the ZKInputs data structure, so when
358// the transactions are processed and the ZKInputs filled, there is no need to
359// set all the elements, and if a transaction does not use a parameter, can be
360// leaved as it is in the ZKInputs, as will be 0, so later when using the
361// ZKInputs to generate the zkSnark proof there is no 'nil'/'null' values.
362func newSlice(n int) []*big.Int {
363 s := make([]*big.Int, n)
364 for i := 0; i < len(s); i++ {
365 s[i] = big.NewInt(0)
366 }
367 return s
368}