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 "crypto/sha256"
7 "encoding/binary"
8 "encoding/json"
9 "fmt"
10 "math/big"
11
12 "github.com/hermeznetwork/hermez-node/log"
13 cryptoConstants "github.com/iden3/go-iden3-crypto/constants"
14 "github.com/iden3/go-merkletree"
15 "github.com/mitchellh/mapstructure"
16)
17
18// ZKMetadata contains ZKInputs metadata that is not used directly in the
19// ZKInputs result, but to calculate values for Hash check
20type ZKMetadata struct {
21 // Circuit parameters
22 // absolute maximum of L1 or L2 transactions allowed
23 NTx uint32
24 // merkle tree depth
25 NLevels uint32
26 MaxLevels uint32
27 // absolute maximum of L1 transaction allowed
28 MaxL1Tx uint32
29 // total txs allowed
30 MaxTx uint32
31 // Maximum number of Idxs where Fees can be send in a batch (currently
32 // is constant for all circuits: 64)
33 MaxFeeIdxs uint32
34
35 L1TxsData [][]byte
36 L2TxsData [][]byte
37 ChainID uint16
38
39 NewLastIdxRaw Idx
40 NewStateRootRaw *merkletree.Hash
41 NewExitRootRaw *merkletree.Hash
42}
43
44// ZKInputs represents the inputs that will be used to generate the zkSNARK proof
45type ZKInputs struct {
46 Metadata ZKMetadata
47
48 //
49 // General
50 //
51
52 // inputs for final `hashGlobalInputs`
53 // OldLastIdx is the last index assigned to an account
54 OldLastIdx *big.Int `json:"oldLastIdx"` // uint64 (max nLevels bits)
55 // OldStateRoot is the current state merkle tree root
56 OldStateRoot *big.Int `json:"oldStateRoot"` // Hash
57 // GlobalChainID is the blockchain ID (0 for Ethereum mainnet). This value can be get from the smart contract.
58 GlobalChainID *big.Int `json:"globalChainID"` // uint16
59 // FeeIdxs is an array of merkle tree indexes where the coordinator will receive the accumulated fees
60 FeeIdxs []*big.Int `json:"feeIdxs"` // uint64 (max nLevels bits), len: [maxFeeIdxs]
61
62 // accumulate fees
63 // FeePlanTokens contains all the tokenIDs for which the fees are being accumulated
64 FeePlanTokens []*big.Int `json:"feePlanTokens"` // uint32 (max 32 bits), len: [maxFeeIdxs]
65
66 //
67 // Txs (L1&L2)
68 //
69
70 // transaction L1-L2
71 // TxCompressedData
72 TxCompressedData []*big.Int `json:"txCompressedData"` // big.Int (max 251 bits), len: [nTx]
73 // TxCompressedDataV2, only used in L2Txs, in L1Txs is set to 0
74 TxCompressedDataV2 []*big.Int `json:"txCompressedDataV2"` // big.Int (max 193 bits), len: [nTx]
75
76 // FromIdx
77 FromIdx []*big.Int `json:"fromIdx"` // uint64 (max nLevels bits), len: [nTx]
78 // AuxFromIdx is the Idx of the new created account which is consequence of a L1CreateAccountTx
79 AuxFromIdx []*big.Int `json:"auxFromIdx"` // uint64 (max nLevels bits), len: [nTx]
80
81 // ToIdx
82 ToIdx []*big.Int `json:"toIdx"` // uint64 (max nLevels bits), len: [nTx]
83 // 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'
84 AuxToIdx []*big.Int `json:"auxToIdx"` // uint64 (max nLevels bits), len: [nTx]
85 // ToBJJAy
86 ToBJJAy []*big.Int `json:"toBjjAy"` // big.Int, len: [nTx]
87 // ToEthAddr
88 ToEthAddr []*big.Int `json:"toEthAddr"` // ethCommon.Address, len: [nTx]
89
90 // OnChain determines if is L1 (1/true) or L2 (0/false)
91 OnChain []*big.Int `json:"onChain"` // bool, len: [nTx]
92
93 //
94 // Txs/L1Txs
95 //
96 // NewAccount boolean (0/1) flag set 'true' when L1 tx creates a new account (fromIdx==0)
97 NewAccount []*big.Int `json:"newAccount"` // bool, len: [nTx]
98 // LoadAmountF encoded as float16
99 LoadAmountF []*big.Int `json:"loadAmountF"` // uint16, len: [nTx]
100 // FromEthAddr
101 FromEthAddr []*big.Int `json:"fromEthAddr"` // ethCommon.Address, len: [nTx]
102 // FromBJJCompressed boolean encoded where each value is a *big.Int
103 FromBJJCompressed [][256]*big.Int `json:"fromBjjCompressed"` // bool array, len: [nTx][256]
104
105 //
106 // Txs/L2Txs
107 //
108
109 // RqOffset relative transaction position to be linked. Used to perform atomic transactions.
110 RqOffset []*big.Int `json:"rqOffset"` // uint8 (max 3 bits), len: [nTx]
111
112 // transaction L2 request data
113 // RqTxCompressedDataV2
114 RqTxCompressedDataV2 []*big.Int `json:"rqTxCompressedDataV2"` // big.Int (max 251 bits), len: [nTx]
115 // RqToEthAddr
116 RqToEthAddr []*big.Int `json:"rqToEthAddr"` // ethCommon.Address, len: [nTx]
117 // RqToBJJAy
118 RqToBJJAy []*big.Int `json:"rqToBjjAy"` // big.Int, len: [nTx]
119
120 // transaction L2 signature
121 // S
122 S []*big.Int `json:"s"` // big.Int, len: [nTx]
123 // R8x
124 R8x []*big.Int `json:"r8x"` // big.Int, len: [nTx]
125 // R8y
126 R8y []*big.Int `json:"r8y"` // big.Int, len: [nTx]
127
128 //
129 // State MerkleTree Leafs transitions
130 //
131
132 // state 1, value of the sender (from) account leaf
133 TokenID1 []*big.Int `json:"tokenID1"` // uint32, len: [nTx]
134 Nonce1 []*big.Int `json:"nonce1"` // uint64 (max 40 bits), len: [nTx]
135 Sign1 []*big.Int `json:"sign1"` // bool, len: [nTx]
136 Ay1 []*big.Int `json:"ay1"` // big.Int, len: [nTx]
137 Balance1 []*big.Int `json:"balance1"` // big.Int (max 192 bits), len: [nTx]
138 EthAddr1 []*big.Int `json:"ethAddr1"` // ethCommon.Address, len: [nTx]
139 Siblings1 [][]*big.Int `json:"siblings1"` // big.Int, len: [nTx][nLevels + 1]
140 // Required for inserts and deletes, values of the CircomProcessorProof (smt insert proof)
141 IsOld0_1 []*big.Int `json:"isOld0_1"` // bool, len: [nTx]
142 OldKey1 []*big.Int `json:"oldKey1"` // uint64 (max 40 bits), len: [nTx]
143 OldValue1 []*big.Int `json:"oldValue1"` // Hash, len: [nTx]
144
145 // state 2, value of the receiver (to) account leaf
146 // if Tx is an Exit, state 2 is used for the Exit Merkle Proof
147 TokenID2 []*big.Int `json:"tokenID2"` // uint32, len: [nTx]
148 Nonce2 []*big.Int `json:"nonce2"` // uint64 (max 40 bits), len: [nTx]
149 Sign2 []*big.Int `json:"sign2"` // bool, len: [nTx]
150 Ay2 []*big.Int `json:"ay2"` // big.Int, len: [nTx]
151 Balance2 []*big.Int `json:"balance2"` // big.Int (max 192 bits), len: [nTx]
152 EthAddr2 []*big.Int `json:"ethAddr2"` // ethCommon.Address, len: [nTx]
153 Siblings2 [][]*big.Int `json:"siblings2"` // big.Int, len: [nTx][nLevels + 1]
154 // newExit determines if an exit transaction has to create a new leaf in the exit tree
155 NewExit []*big.Int `json:"newExit"` // bool, len: [nTx]
156 // Required for inserts and deletes, values of the CircomProcessorProof (smt insert proof)
157 IsOld0_2 []*big.Int `json:"isOld0_2"` // bool, len: [nTx]
158 OldKey2 []*big.Int `json:"oldKey2"` // uint64 (max 40 bits), len: [nTx]
159 OldValue2 []*big.Int `json:"oldValue2"` // Hash, len: [nTx]
160
161 // state 3, value of the account leaf receiver of the Fees
162 // fee tx
163 // State fees
164 TokenID3 []*big.Int `json:"tokenID3"` // uint32, len: [maxFeeIdxs]
165 Nonce3 []*big.Int `json:"nonce3"` // uint64 (max 40 bits), len: [maxFeeIdxs]
166 Sign3 []*big.Int `json:"sign3"` // bool, len: [maxFeeIdxs]
167 Ay3 []*big.Int `json:"ay3"` // big.Int, len: [maxFeeIdxs]
168 Balance3 []*big.Int `json:"balance3"` // big.Int (max 192 bits), len: [maxFeeIdxs]
169 EthAddr3 []*big.Int `json:"ethAddr3"` // ethCommon.Address, len: [maxFeeIdxs]
170 Siblings3 [][]*big.Int `json:"siblings3"` // Hash, len: [maxFeeIdxs][nLevels + 1]
171
172 //
173 // Intermediate States
174 //
175
176 // Intermediate States to parallelize witness computation
177 // Note: the Intermediate States (IS) of the last transaction does not
178 // exist. Meaning that transaction 3 (4th) will fill the parameters
179 // FromIdx[3] and ISOnChain[3], but last transaction (nTx-1) will fill
180 // FromIdx[nTx-1] but will not fill ISOnChain. That's why IS have
181 // length of nTx-1, while the other parameters have length of nTx.
182 // Last transaction does not need intermediate state since its output
183 // will not be used.
184
185 // decode-tx
186 // ISOnChain indicates if tx is L1 (true) or L2 (false)
187 ISOnChain []*big.Int `json:"imOnChain"` // bool, len: [nTx - 1]
188 // ISOutIdx current index account for each Tx
189 ISOutIdx []*big.Int `json:"imOutIdx"` // uint64 (max nLevels bits), len: [nTx - 1]
190 // rollup-tx
191 // ISStateRoot root at the moment of the Tx, the state root value once the Tx is processed into the state tree
192 ISStateRoot []*big.Int `json:"imStateRoot"` // Hash, len: [nTx - 1]
193 // ISExitTree root at the moment of the Tx the value once the Tx is processed into the exit tree
194 ISExitRoot []*big.Int `json:"imExitRoot"` // Hash, len: [nTx - 1]
195 // ISAccFeeOut accumulated fees once the Tx is processed
196 ISAccFeeOut [][]*big.Int `json:"imAccFeeOut"` // big.Int, len: [nTx - 1][maxFeeIdxs]
197 // fee-tx
198 // ISStateRootFee root at the moment of the Tx, the state root value once the Tx is processed into the state tree
199 ISStateRootFee []*big.Int `json:"imStateRootFee"` // Hash, len: [maxFeeIdxs - 1]
200 // ISInitStateRootFee state root once all L1-L2 tx are processed (before computing the fees-tx)
201 ISInitStateRootFee *big.Int `json:"imInitStateRootFee"` // Hash
202 // ISFinalAccFee final accumulated fees (before computing the fees-tx)
203 ISFinalAccFee []*big.Int `json:"imFinalAccFee"` // big.Int, len: [maxFeeIdxs - 1]
204}
205
206func bigIntsToStrings(v interface{}) interface{} {
207 switch c := v.(type) {
208 case *big.Int:
209 return c.String()
210 case []*big.Int:
211 r := make([]interface{}, len(c))
212 for i := range c {
213 r[i] = bigIntsToStrings(c[i])
214 }
215 return r
216 case [256]*big.Int:
217 r := make([]interface{}, len(c))
218 for i := range c {
219 r[i] = bigIntsToStrings(c[i])
220 }
221 return r
222 case [][]*big.Int:
223 r := make([]interface{}, len(c))
224 for i := range c {
225 r[i] = bigIntsToStrings(c[i])
226 }
227 return r
228 case [][256]*big.Int:
229 r := make([]interface{}, len(c))
230 for i := range c {
231 r[i] = bigIntsToStrings(c[i])
232 }
233 return r
234 case map[string]interface{}:
235 // avoid printing a warning when there is a struct type
236 default:
237 log.Warnf("bigIntsToStrings unexpected type: %T\n", v)
238 }
239 return nil
240}
241
242// MarshalJSON implements the json marshaler for ZKInputs
243func (z ZKInputs) MarshalJSON() ([]byte, error) {
244 var m map[string]interface{}
245 dec, err := mapstructure.NewDecoder(&mapstructure.DecoderConfig{
246 TagName: "json",
247 Result: &m,
248 })
249 if err != nil {
250 return nil, err
251 }
252 err = dec.Decode(z)
253 if err != nil {
254 return nil, err
255 }
256
257 for k, v := range m {
258 m[k] = bigIntsToStrings(v)
259 }
260 return json.Marshal(m)
261}
262
263// NewZKInputs returns a pointer to an initialized struct of ZKInputs
264func NewZKInputs(nTx, maxL1Tx, maxTx, maxFeeIdxs, nLevels uint32) *ZKInputs {
265 zki := &ZKInputs{}
266 zki.Metadata.NTx = nTx
267 zki.Metadata.MaxFeeIdxs = maxFeeIdxs
268 zki.Metadata.NLevels = nLevels
269 zki.Metadata.MaxLevels = uint32(48) //nolint:gomnd
270 zki.Metadata.MaxL1Tx = maxL1Tx
271 zki.Metadata.MaxTx = maxTx
272
273 // General
274 zki.OldLastIdx = big.NewInt(0)
275 zki.OldStateRoot = big.NewInt(0)
276 zki.GlobalChainID = big.NewInt(0)
277 zki.FeeIdxs = newSlice(maxFeeIdxs)
278 zki.FeePlanTokens = newSlice(maxFeeIdxs)
279
280 // Txs
281 zki.TxCompressedData = newSlice(nTx)
282 zki.TxCompressedDataV2 = newSlice(nTx)
283 zki.FromIdx = newSlice(nTx)
284 zki.AuxFromIdx = newSlice(nTx)
285 zki.ToIdx = newSlice(nTx)
286 zki.AuxToIdx = newSlice(nTx)
287 zki.ToBJJAy = newSlice(nTx)
288 zki.ToEthAddr = newSlice(nTx)
289 zki.OnChain = newSlice(nTx)
290 zki.NewAccount = newSlice(nTx)
291
292 // L1
293 zki.LoadAmountF = newSlice(nTx)
294 zki.FromEthAddr = newSlice(nTx)
295 zki.FromBJJCompressed = make([][256]*big.Int, nTx)
296 for i := 0; i < len(zki.FromBJJCompressed); i++ {
297 // zki.FromBJJCompressed[i] = newSlice(256)
298 for j := 0; j < 256; j++ {
299 zki.FromBJJCompressed[i][j] = big.NewInt(0)
300 }
301 }
302
303 // L2
304 zki.RqOffset = newSlice(nTx)
305 zki.RqTxCompressedDataV2 = newSlice(nTx)
306 zki.RqToEthAddr = newSlice(nTx)
307 zki.RqToBJJAy = newSlice(nTx)
308 zki.S = newSlice(nTx)
309 zki.R8x = newSlice(nTx)
310 zki.R8y = newSlice(nTx)
311
312 // State MerkleTree Leafs transitions
313 zki.TokenID1 = newSlice(nTx)
314 zki.Nonce1 = newSlice(nTx)
315 zki.Sign1 = newSlice(nTx)
316 zki.Ay1 = newSlice(nTx)
317 zki.Balance1 = newSlice(nTx)
318 zki.EthAddr1 = newSlice(nTx)
319 zki.Siblings1 = make([][]*big.Int, nTx)
320 for i := 0; i < len(zki.Siblings1); i++ {
321 zki.Siblings1[i] = newSlice(nLevels + 1)
322 }
323 zki.IsOld0_1 = newSlice(nTx)
324 zki.OldKey1 = newSlice(nTx)
325 zki.OldValue1 = newSlice(nTx)
326
327 zki.TokenID2 = newSlice(nTx)
328 zki.Nonce2 = newSlice(nTx)
329 zki.Sign2 = newSlice(nTx)
330 zki.Ay2 = newSlice(nTx)
331 zki.Balance2 = newSlice(nTx)
332 zki.EthAddr2 = newSlice(nTx)
333 zki.Siblings2 = make([][]*big.Int, nTx)
334 for i := 0; i < len(zki.Siblings2); i++ {
335 zki.Siblings2[i] = newSlice(nLevels + 1)
336 }
337 zki.NewExit = newSlice(nTx)
338 zki.IsOld0_2 = newSlice(nTx)
339 zki.OldKey2 = newSlice(nTx)
340 zki.OldValue2 = newSlice(nTx)
341
342 zki.TokenID3 = newSlice(maxFeeIdxs)
343 zki.Nonce3 = newSlice(maxFeeIdxs)
344 zki.Sign3 = newSlice(maxFeeIdxs)
345 zki.Ay3 = newSlice(maxFeeIdxs)
346 zki.Balance3 = newSlice(maxFeeIdxs)
347 zki.EthAddr3 = newSlice(maxFeeIdxs)
348 zki.Siblings3 = make([][]*big.Int, maxFeeIdxs)
349 for i := 0; i < len(zki.Siblings3); i++ {
350 zki.Siblings3[i] = newSlice(nLevels + 1)
351 }
352
353 // Intermediate States
354 zki.ISOnChain = newSlice(nTx - 1)
355 zki.ISOutIdx = newSlice(nTx - 1)
356 zki.ISStateRoot = newSlice(nTx - 1)
357 zki.ISExitRoot = newSlice(nTx - 1)
358 zki.ISAccFeeOut = make([][]*big.Int, nTx-1)
359 for i := 0; i < len(zki.ISAccFeeOut); i++ {
360 zki.ISAccFeeOut[i] = newSlice(maxFeeIdxs)
361 }
362 zki.ISStateRootFee = newSlice(maxFeeIdxs - 1)
363 zki.ISInitStateRootFee = big.NewInt(0)
364 zki.ISFinalAccFee = newSlice(maxFeeIdxs - 1)
365
366 return zki
367}
368
369// newSlice returns a []*big.Int slice of length n with values initialized at
370// 0.
371// Is used to initialize all *big.Ints of the ZKInputs data structure, so when
372// the transactions are processed and the ZKInputs filled, there is no need to
373// set all the elements, and if a transaction does not use a parameter, can be
374// leaved as it is in the ZKInputs, as will be 0, so later when using the
375// ZKInputs to generate the zkSnark proof there is no 'nil'/'null' values.
376func newSlice(n uint32) []*big.Int {
377 s := make([]*big.Int, n)
378 for i := 0; i < len(s); i++ {
379 s[i] = big.NewInt(0)
380 }
381 return s
382}
383
384// HashGlobalData returns the HashGlobalData
385func (z ZKInputs) HashGlobalData() (*big.Int, error) {
386 b, err := z.ToHashGlobalData()
387 if err != nil {
388 return nil, err
389 }
390
391 h := sha256.New()
392 _, err = h.Write(b)
393 if err != nil {
394 return nil, err
395 }
396
397 r := new(big.Int).SetBytes(h.Sum(nil))
398 v := r.Mod(r, cryptoConstants.Q)
399
400 return v, nil
401}
402
403// ToHashGlobalData returns the data to be hashed in the method HashGlobalData
404func (z ZKInputs) ToHashGlobalData() ([]byte, error) {
405 var b []byte
406 bytesMaxLevels := int(z.Metadata.MaxLevels / 8) //nolint:gomnd
407
408 // [MAX_NLEVELS bits] oldLastIdx
409 oldLastIdx := make([]byte, bytesMaxLevels)
410 copy(oldLastIdx, z.OldLastIdx.Bytes())
411 b = append(b, SwapEndianness(oldLastIdx)...)
412
413 // [MAX_NLEVELS bits] newLastIdx
414 newLastIdx := make([]byte, bytesMaxLevels)
415 newLastIdxBytes, err := z.Metadata.NewLastIdxRaw.Bytes()
416 if err != nil {
417 return nil, err
418 }
419 copy(newLastIdx, newLastIdxBytes[len(newLastIdxBytes)-bytesMaxLevels:])
420 b = append(b, newLastIdx...)
421
422 // [256 bits] oldStRoot
423 oldStateRoot := make([]byte, 32)
424 copy(oldStateRoot, z.OldStateRoot.Bytes())
425 b = append(b, oldStateRoot...)
426
427 // [256 bits] newStateRoot
428 newStateRoot := make([]byte, 32)
429 copy(newStateRoot, z.Metadata.NewStateRootRaw.Bytes())
430 b = append(b, newStateRoot...)
431
432 // [256 bits] newExitRoot
433 newExitRoot := make([]byte, 32)
434 copy(newExitRoot, z.Metadata.NewExitRootRaw.Bytes())
435 b = append(b, newExitRoot...)
436
437 // [MAX_L1_TX * (2 * MAX_NLEVELS + 480) bits] L1TxsData
438 l1TxDataLen := (2*z.Metadata.MaxLevels + 480)
439 l1TxsDataLen := (z.Metadata.MaxL1Tx * l1TxDataLen)
440 l1TxsData := make([]byte, l1TxsDataLen/8) //nolint:gomnd
441 for i := 0; i < len(z.Metadata.L1TxsData); i++ {
442 dataLen := int(l1TxDataLen) / 8 //nolint:gomnd
443 pos0 := i * dataLen
444 pos1 := i*dataLen + dataLen
445 copy(l1TxsData[pos0:pos1], z.Metadata.L1TxsData[i])
446 }
447 b = append(b, l1TxsData...)
448
449 // [MAX_TX*(2*NLevels + 24) bits] L2TxsData
450 var l2TxsData []byte
451 l2TxDataLen := 2*z.Metadata.NLevels + 24 //nolint:gomnd
452 l2TxsDataLen := (z.Metadata.MaxTx * l2TxDataLen)
453 expectedL2TxsDataLen := l2TxsDataLen / 8 //nolint:gomnd
454 for i := 0; i < len(z.Metadata.L2TxsData); i++ {
455 l2TxsData = append(l2TxsData, z.Metadata.L2TxsData[i]...)
456 }
457 if len(l2TxsData) > int(expectedL2TxsDataLen) {
458 return nil, fmt.Errorf("len(l2TxsData): %d, expected: %d", len(l2TxsData), expectedL2TxsDataLen)
459 }
460
461 l2TxsPadding := make([]byte, (int(z.Metadata.MaxTx)-len(z.Metadata.L2TxsData))*int(l2TxDataLen)/8) //nolint:gomnd
462 b = append(b, l2TxsPadding...)
463 b = append(b, l2TxsData...)
464
465 // [NLevels * MAX_TOKENS_FEE bits] feeTxsData
466 for i := 0; i < len(z.FeeIdxs); i++ {
467 var r []byte
468
469 padding := make([]byte, bytesMaxLevels/4) //nolint:gomnd
470 r = append(r, padding...)
471
472 feeIdx := make([]byte, bytesMaxLevels/2) //nolint:gomnd
473 feeIdxBytes := z.FeeIdxs[i].Bytes()
474 copy(feeIdx[len(feeIdx)-len(feeIdxBytes):], feeIdxBytes[:])
475 r = append(r, feeIdx...)
476 b = append(b, r...)
477 }
478
479 // [16 bits] chainID
480 var chainID [2]byte
481 binary.BigEndian.PutUint16(chainID[:], z.Metadata.ChainID)
482 b = append(b, chainID[:]...)
483
484 return b, nil
485}