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 `json:"-"`
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 (1)) or L2 (false (0))
187 ISOnChain []*big.Int `json:"imOnChain"` // bool, len: [nTx - 1]
188 // ISOutIdx current index account for each Tx
189 // Contains the index of the created account in case that the tx is of
190 // account creation type.
191 ISOutIdx []*big.Int `json:"imOutIdx"` // uint64 (max nLevels bits), len: [nTx - 1]
192 // rollup-tx
193 // ISStateRoot root at the moment of the Tx (once processed), the state root value once the Tx is processed into the state tree
194 ISStateRoot []*big.Int `json:"imStateRoot"` // Hash, len: [nTx - 1]
195 // ISExitTree root at the moment (once processed) of the Tx the value
196 // once the Tx is processed into the exit tree
197 ISExitRoot []*big.Int `json:"imExitRoot"` // Hash, len: [nTx - 1]
198 // ISAccFeeOut accumulated fees once the Tx is processed. Contains the
199 // array of FeeAccount Balances at each moment of each Tx processed.
200 ISAccFeeOut [][]*big.Int `json:"imAccFeeOut"` // big.Int, len: [nTx - 1][maxFeeIdxs]
201 // fee-tx
202 // ISStateRootFee root at the moment of the Tx (once processed), the state root value once the Tx is processed into the state tree
203 ISStateRootFee []*big.Int `json:"imStateRootFee"` // Hash, len: [maxFeeIdxs - 1]
204 // ISInitStateRootFee state root once all L1-L2 tx are processed (before computing the fees-tx)
205 ISInitStateRootFee *big.Int `json:"imInitStateRootFee"` // Hash
206 // ISFinalAccFee final accumulated fees (before computing the fees-tx).
207 // Contains the final values of the ISAccFeeOut parameter
208 ISFinalAccFee []*big.Int `json:"imFinalAccFee"` // big.Int, len: [maxFeeIdxs - 1]
209}
210
211func bigIntsToStrings(v interface{}) interface{} {
212 switch c := v.(type) {
213 case *big.Int:
214 return c.String()
215 case []*big.Int:
216 r := make([]interface{}, len(c))
217 for i := range c {
218 r[i] = bigIntsToStrings(c[i])
219 }
220 return r
221 case [256]*big.Int:
222 r := make([]interface{}, len(c))
223 for i := range c {
224 r[i] = bigIntsToStrings(c[i])
225 }
226 return r
227 case [][]*big.Int:
228 r := make([]interface{}, len(c))
229 for i := range c {
230 r[i] = bigIntsToStrings(c[i])
231 }
232 return r
233 case [][256]*big.Int:
234 r := make([]interface{}, len(c))
235 for i := range c {
236 r[i] = bigIntsToStrings(c[i])
237 }
238 return r
239 case map[string]interface{}:
240 // avoid printing a warning when there is a struct type
241 default:
242 log.Warnf("bigIntsToStrings unexpected type: %T\n", v)
243 }
244 return nil
245}
246
247// MarshalJSON implements the json marshaler for ZKInputs
248func (z ZKInputs) MarshalJSON() ([]byte, error) {
249 var m map[string]interface{}
250 dec, err := mapstructure.NewDecoder(&mapstructure.DecoderConfig{
251 TagName: "json",
252 Result: &m,
253 })
254 if err != nil {
255 return nil, err
256 }
257 err = dec.Decode(z)
258 if err != nil {
259 return nil, err
260 }
261
262 for k, v := range m {
263 m[k] = bigIntsToStrings(v)
264 }
265 return json.Marshal(m)
266}
267
268// NewZKInputs returns a pointer to an initialized struct of ZKInputs
269func NewZKInputs(nTx, maxL1Tx, maxTx, maxFeeIdxs, nLevels uint32) *ZKInputs {
270 zki := &ZKInputs{}
271 zki.Metadata.NTx = nTx
272 zki.Metadata.MaxFeeIdxs = maxFeeIdxs
273 zki.Metadata.NLevels = nLevels
274 zki.Metadata.MaxLevels = uint32(48) //nolint:gomnd
275 zki.Metadata.MaxL1Tx = maxL1Tx
276 zki.Metadata.MaxTx = maxTx
277
278 // General
279 zki.OldLastIdx = big.NewInt(0)
280 zki.OldStateRoot = big.NewInt(0)
281 zki.GlobalChainID = big.NewInt(0)
282 zki.FeeIdxs = newSlice(maxFeeIdxs)
283 zki.FeePlanTokens = newSlice(maxFeeIdxs)
284
285 // Txs
286 zki.TxCompressedData = newSlice(nTx)
287 zki.TxCompressedDataV2 = newSlice(nTx)
288 zki.FromIdx = newSlice(nTx)
289 zki.AuxFromIdx = newSlice(nTx)
290 zki.ToIdx = newSlice(nTx)
291 zki.AuxToIdx = newSlice(nTx)
292 zki.ToBJJAy = newSlice(nTx)
293 zki.ToEthAddr = newSlice(nTx)
294 zki.OnChain = newSlice(nTx)
295 zki.NewAccount = newSlice(nTx)
296
297 // L1
298 zki.LoadAmountF = newSlice(nTx)
299 zki.FromEthAddr = newSlice(nTx)
300 zki.FromBJJCompressed = make([][256]*big.Int, nTx)
301 for i := 0; i < len(zki.FromBJJCompressed); i++ {
302 // zki.FromBJJCompressed[i] = newSlice(256)
303 for j := 0; j < 256; j++ {
304 zki.FromBJJCompressed[i][j] = big.NewInt(0)
305 }
306 }
307
308 // L2
309 zki.RqOffset = newSlice(nTx)
310 zki.RqTxCompressedDataV2 = newSlice(nTx)
311 zki.RqToEthAddr = newSlice(nTx)
312 zki.RqToBJJAy = newSlice(nTx)
313 zki.S = newSlice(nTx)
314 zki.R8x = newSlice(nTx)
315 zki.R8y = newSlice(nTx)
316
317 // State MerkleTree Leafs transitions
318 zki.TokenID1 = newSlice(nTx)
319 zki.Nonce1 = newSlice(nTx)
320 zki.Sign1 = newSlice(nTx)
321 zki.Ay1 = newSlice(nTx)
322 zki.Balance1 = newSlice(nTx)
323 zki.EthAddr1 = newSlice(nTx)
324 zki.Siblings1 = make([][]*big.Int, nTx)
325 for i := 0; i < len(zki.Siblings1); i++ {
326 zki.Siblings1[i] = newSlice(nLevels + 1)
327 }
328 zki.IsOld0_1 = newSlice(nTx)
329 zki.OldKey1 = newSlice(nTx)
330 zki.OldValue1 = newSlice(nTx)
331
332 zki.TokenID2 = newSlice(nTx)
333 zki.Nonce2 = newSlice(nTx)
334 zki.Sign2 = newSlice(nTx)
335 zki.Ay2 = newSlice(nTx)
336 zki.Balance2 = newSlice(nTx)
337 zki.EthAddr2 = newSlice(nTx)
338 zki.Siblings2 = make([][]*big.Int, nTx)
339 for i := 0; i < len(zki.Siblings2); i++ {
340 zki.Siblings2[i] = newSlice(nLevels + 1)
341 }
342 zki.NewExit = newSlice(nTx)
343 zki.IsOld0_2 = newSlice(nTx)
344 zki.OldKey2 = newSlice(nTx)
345 zki.OldValue2 = newSlice(nTx)
346
347 zki.TokenID3 = newSlice(maxFeeIdxs)
348 zki.Nonce3 = newSlice(maxFeeIdxs)
349 zki.Sign3 = newSlice(maxFeeIdxs)
350 zki.Ay3 = newSlice(maxFeeIdxs)
351 zki.Balance3 = newSlice(maxFeeIdxs)
352 zki.EthAddr3 = newSlice(maxFeeIdxs)
353 zki.Siblings3 = make([][]*big.Int, maxFeeIdxs)
354 for i := 0; i < len(zki.Siblings3); i++ {
355 zki.Siblings3[i] = newSlice(nLevels + 1)
356 }
357
358 // Intermediate States
359 zki.ISOnChain = newSlice(nTx - 1)
360 zki.ISOutIdx = newSlice(nTx - 1)
361 zki.ISStateRoot = newSlice(nTx - 1)
362 zki.ISExitRoot = newSlice(nTx - 1)
363 zki.ISAccFeeOut = make([][]*big.Int, nTx-1)
364 for i := 0; i < len(zki.ISAccFeeOut); i++ {
365 zki.ISAccFeeOut[i] = newSlice(maxFeeIdxs)
366 }
367 zki.ISStateRootFee = newSlice(maxFeeIdxs - 1)
368 zki.ISInitStateRootFee = big.NewInt(0)
369 zki.ISFinalAccFee = newSlice(maxFeeIdxs - 1)
370
371 return zki
372}
373
374// newSlice returns a []*big.Int slice of length n with values initialized at
375// 0.
376// Is used to initialize all *big.Ints of the ZKInputs data structure, so when
377// the transactions are processed and the ZKInputs filled, there is no need to
378// set all the elements, and if a transaction does not use a parameter, can be
379// leaved as it is in the ZKInputs, as will be 0, so later when using the
380// ZKInputs to generate the zkSnark proof there is no 'nil'/'null' values.
381func newSlice(n uint32) []*big.Int {
382 s := make([]*big.Int, n)
383 for i := 0; i < len(s); i++ {
384 s[i] = big.NewInt(0)
385 }
386 return s
387}
388
389// HashGlobalData returns the HashGlobalData
390func (z ZKInputs) HashGlobalData() (*big.Int, error) {
391 b, err := z.ToHashGlobalData()
392 if err != nil {
393 return nil, err
394 }
395
396 h := sha256.New()
397 _, err = h.Write(b)
398 if err != nil {
399 return nil, err
400 }
401
402 r := new(big.Int).SetBytes(h.Sum(nil))
403 v := r.Mod(r, cryptoConstants.Q)
404
405 return v, nil
406}
407
408// ToHashGlobalData returns the data to be hashed in the method HashGlobalData
409func (z ZKInputs) ToHashGlobalData() ([]byte, error) {
410 var b []byte
411 bytesMaxLevels := int(z.Metadata.MaxLevels / 8) //nolint:gomnd
412
413 // [MAX_NLEVELS bits] oldLastIdx
414 oldLastIdx := make([]byte, bytesMaxLevels)
415 copy(oldLastIdx, z.OldLastIdx.Bytes())
416 b = append(b, SwapEndianness(oldLastIdx)...)
417
418 // [MAX_NLEVELS bits] newLastIdx
419 newLastIdx := make([]byte, bytesMaxLevels)
420 newLastIdxBytes, err := z.Metadata.NewLastIdxRaw.Bytes()
421 if err != nil {
422 return nil, err
423 }
424 copy(newLastIdx, newLastIdxBytes[len(newLastIdxBytes)-bytesMaxLevels:])
425 b = append(b, newLastIdx...)
426
427 // [256 bits] oldStRoot
428 oldStateRoot := make([]byte, 32)
429 copy(oldStateRoot, z.OldStateRoot.Bytes())
430 b = append(b, oldStateRoot...)
431
432 // [256 bits] newStateRoot
433 newStateRoot := make([]byte, 32)
434 copy(newStateRoot, z.Metadata.NewStateRootRaw.Bytes())
435 b = append(b, newStateRoot...)
436
437 // [256 bits] newExitRoot
438 newExitRoot := make([]byte, 32)
439 copy(newExitRoot, z.Metadata.NewExitRootRaw.Bytes())
440 b = append(b, newExitRoot...)
441
442 // [MAX_L1_TX * (2 * MAX_NLEVELS + 480) bits] L1TxsData
443 l1TxDataLen := (2*z.Metadata.MaxLevels + 480)
444 l1TxsDataLen := (z.Metadata.MaxL1Tx * l1TxDataLen)
445 l1TxsData := make([]byte, l1TxsDataLen/8) //nolint:gomnd
446 for i := 0; i < len(z.Metadata.L1TxsData); i++ {
447 dataLen := int(l1TxDataLen) / 8 //nolint:gomnd
448 pos0 := i * dataLen
449 pos1 := i*dataLen + dataLen
450 copy(l1TxsData[pos0:pos1], z.Metadata.L1TxsData[i])
451 }
452 b = append(b, l1TxsData...)
453
454 // [MAX_TX*(2*NLevels + 24) bits] L2TxsData
455 var l2TxsData []byte
456 l2TxDataLen := 2*z.Metadata.NLevels + 24 //nolint:gomnd
457 l2TxsDataLen := (z.Metadata.MaxTx * l2TxDataLen)
458 expectedL2TxsDataLen := l2TxsDataLen / 8 //nolint:gomnd
459 for i := 0; i < len(z.Metadata.L2TxsData); i++ {
460 l2TxsData = append(l2TxsData, z.Metadata.L2TxsData[i]...)
461 }
462 if len(l2TxsData) > int(expectedL2TxsDataLen) {
463 return nil, fmt.Errorf("len(l2TxsData): %d, expected: %d", len(l2TxsData), expectedL2TxsDataLen)
464 }
465
466 l2TxsPadding := make([]byte, (int(z.Metadata.MaxTx)-len(z.Metadata.L2TxsData))*int(l2TxDataLen)/8) //nolint:gomnd
467 b = append(b, l2TxsPadding...)
468 b = append(b, l2TxsData...)
469
470 // [NLevels * MAX_TOKENS_FEE bits] feeTxsData
471 for i := 0; i < len(z.FeeIdxs); i++ {
472 var r []byte
473
474 padding := make([]byte, bytesMaxLevels/4) //nolint:gomnd
475 r = append(r, padding...)
476
477 feeIdx := make([]byte, bytesMaxLevels/2) //nolint:gomnd
478 feeIdxBytes := z.FeeIdxs[i].Bytes()
479 copy(feeIdx[len(feeIdx)-len(feeIdxBytes):], feeIdxBytes[:])
480 r = append(r, feeIdx...)
481 b = append(b, r...)
482 }
483
484 // [16 bits] chainID
485 var chainID [2]byte
486 binary.BigEndian.PutUint16(chainID[:], z.Metadata.ChainID)
487 b = append(b, chainID[:]...)
488
489 return b, nil
490}