hermez-node/txselector/txselector.go
txselector/txselector.goRaw
1package txselector
2
3// current: very simple version of TxSelector
4
5import (
6 "bytes"
7 "fmt"
8 "math/big"
9 "sort"
10
11 ethCommon "github.com/ethereum/go-ethereum/common"
12 "github.com/hermeznetwork/hermez-node/common"
13 "github.com/hermeznetwork/hermez-node/db/l2db"
14 "github.com/hermeznetwork/hermez-node/db/statedb"
15 "github.com/hermeznetwork/hermez-node/log"
16 "github.com/hermeznetwork/hermez-node/txprocessor"
17 "github.com/hermeznetwork/tracerr"
18 "github.com/iden3/go-iden3-crypto/babyjub"
19 "github.com/iden3/go-merkletree/db"
20 "github.com/iden3/go-merkletree/db/pebble"
21)
22
23const (
24 // PathCoordIdxsDB defines the path of the key-value db where the
25 // CoordIdxs will be stored
26 PathCoordIdxsDB = "/coordidxs"
27)
28
29// txs implements the interface Sort for an array of Tx
30type txs []common.PoolL2Tx
31
32func (t txs) Len() int {
33 return len(t)
34}
35func (t txs) Swap(i, j int) {
36 t[i], t[j] = t[j], t[i]
37}
38func (t txs) Less(i, j int) bool {
39 return t[i].AbsoluteFee > t[j].AbsoluteFee
40}
41
42// CoordAccount contains the data of the Coordinator account, that will be used
43// to create new transactions of CreateAccountDeposit type to add new TokenID
44// accounts for the Coordinator to receive the fees.
45type CoordAccount struct {
46 Addr ethCommon.Address
47 BJJ babyjub.PublicKeyComp
48 AccountCreationAuth []byte
49}
50
51// SelectionConfig contains the parameters of configuration of the selection of
52// transactions for the next batch
53type SelectionConfig struct {
54 // MaxL1UserTxs is the maximum L1-user-tx for a batch
55 MaxL1UserTxs uint64
56 // MaxL1CoordinatorTxs is the maximum L1-coordinator-tx for a batch
57 MaxL1CoordinatorTxs uint64
58
59 // TxProcessorConfig contains the config for ProcessTxs
60 TxProcessorConfig txprocessor.Config
61}
62
63// TxSelector implements all the functionalities to select the txs for the next
64// batch
65type TxSelector struct {
66 l2db *l2db.L2DB
67 localAccountsDB *statedb.LocalStateDB
68
69 coordAccount *CoordAccount
70 coordIdxsDB *pebble.Storage
71}
72
73// NewTxSelector returns a *TxSelector
74func NewTxSelector(coordAccount *CoordAccount, dbpath string,
75 synchronizerStateDB *statedb.StateDB, l2 *l2db.L2DB) (*TxSelector, error) {
76 localAccountsDB, err := statedb.NewLocalStateDB(dbpath, 128,
77 synchronizerStateDB, statedb.TypeTxSelector, 0) // without merkletree
78 if err != nil {
79 return nil, tracerr.Wrap(err)
80 }
81
82 coordIdxsDB, err := pebble.NewPebbleStorage(dbpath+PathCoordIdxsDB, false)
83 if err != nil {
84 return nil, tracerr.Wrap(err)
85 }
86
87 return &TxSelector{
88 l2db: l2,
89 localAccountsDB: localAccountsDB,
90 coordAccount: coordAccount,
91 coordIdxsDB: coordIdxsDB,
92 }, nil
93}
94
95// LocalAccountsDB returns the LocalStateDB of the TxSelector
96func (txsel *TxSelector) LocalAccountsDB() *statedb.LocalStateDB {
97 return txsel.localAccountsDB
98}
99
100// Reset tells the TxSelector to get it's internal AccountsDB
101// from the required `batchNum`
102func (txsel *TxSelector) Reset(batchNum common.BatchNum) error {
103 err := txsel.localAccountsDB.Reset(batchNum, true)
104 if err != nil {
105 return tracerr.Wrap(err)
106 }
107 return nil
108}
109
110// AddCoordIdxs stores the given TokenID with the correspondent Idx to the
111// CoordIdxsDB
112func (txsel *TxSelector) AddCoordIdxs(idxs map[common.TokenID]common.Idx) error {
113 tx, err := txsel.coordIdxsDB.NewTx()
114 if err != nil {
115 return tracerr.Wrap(err)
116 }
117 for tokenID, idx := range idxs {
118 idxBytes, err := idx.Bytes()
119 if err != nil {
120 return tracerr.Wrap(err)
121 }
122 err = tx.Put(tokenID.Bytes(), idxBytes[:])
123 if err != nil {
124 return tracerr.Wrap(err)
125 }
126 }
127 if err := tx.Commit(); err != nil {
128 return tracerr.Wrap(err)
129 }
130 return nil
131}
132
133// GetCoordIdxs returns a map with the stored TokenID with the correspondent
134// Coordinator Idx
135func (txsel *TxSelector) GetCoordIdxs() (map[common.TokenID]common.Idx, error) {
136 r := make(map[common.TokenID]common.Idx)
137 err := txsel.coordIdxsDB.Iterate(func(tokenIDBytes []byte, idxBytes []byte) (bool, error) {
138 idx, err := common.IdxFromBytes(idxBytes)
139 if err != nil {
140 return false, tracerr.Wrap(err)
141 }
142 tokenID, err := common.TokenIDFromBytes(tokenIDBytes)
143 if err != nil {
144 return false, tracerr.Wrap(err)
145 }
146 r[tokenID] = idx
147 return true, nil
148 })
149
150 return r, tracerr.Wrap(err)
151}
152
153//nolint:unused
154func (txsel *TxSelector) coordAccountForTokenID(l1CoordinatorTxs []common.L1Tx, tokenID common.TokenID, positionL1 int) (*common.L1Tx, int, error) {
155 // check if CoordinatorAccount for TokenID is already pending to create
156 if checkAlreadyPendingToCreate(l1CoordinatorTxs, tokenID, txsel.coordAccount.Addr, txsel.coordAccount.BJJ) {
157 return nil, positionL1, nil
158 }
159
160 _, err := txsel.coordIdxsDB.Get(tokenID.Bytes())
161 if tracerr.Unwrap(err) == db.ErrNotFound {
162 // create L1CoordinatorTx to create new CoordAccount for TokenID
163 l1CoordinatorTx := common.L1Tx{
164 Position: positionL1,
165 UserOrigin: false,
166 FromEthAddr: txsel.coordAccount.Addr,
167 FromBJJ: txsel.coordAccount.BJJ,
168 TokenID: tokenID,
169 DepositAmount: big.NewInt(0),
170 Type: common.TxTypeCreateAccountDeposit,
171 }
172 positionL1++
173
174 return &l1CoordinatorTx, positionL1, nil
175 }
176 if err != nil {
177 return nil, positionL1, tracerr.Wrap(err)
178 }
179 // CoordAccount for TokenID already exists
180 return nil, positionL1, nil
181}
182
183// GetL2TxSelection returns the L1CoordinatorTxs and a selection of the L2Txs
184// for the next batch, from the L2DB pool.
185// It returns: the CoordinatorIdxs used to receive the fees of the selected
186// L2Txs. An array of bytearrays with the signatures of the
187// AccountCreationAuthorization of the accounts of the users created by the
188// Coordinator with L1CoordinatorTxs of those accounts that does not exist yet
189// but there is a transactions to them and the authorization of account
190// creation exists. The L1UserTxs, L1CoordinatorTxs, PoolL2Txs that will be
191// included in the next batch.
192func (txsel *TxSelector) GetL2TxSelection(selectionConfig *SelectionConfig,
193 batchNum common.BatchNum) ([]common.Idx, [][]byte, []common.L1Tx, []common.PoolL2Tx, error) {
194 coordIdxs, accCreationAuths, _, l1CoordinatorTxs, l2Txs, err := txsel.GetL1L2TxSelection(selectionConfig, batchNum,
195 []common.L1Tx{})
196 return coordIdxs, accCreationAuths, l1CoordinatorTxs, l2Txs, tracerr.Wrap(err)
197}
198
199// GetL1L2TxSelection returns the selection of L1 + L2 txs.
200// It returns: the CoordinatorIdxs used to receive the fees of the selected
201// L2Txs. An array of bytearrays with the signatures of the
202// AccountCreationAuthorization of the accounts of the users created by the
203// Coordinator with L1CoordinatorTxs of those accounts that does not exist yet
204// but there is a transactions to them and the authorization of account
205// creation exists. The L1UserTxs, L1CoordinatorTxs, PoolL2Txs that will be
206// included in the next batch.
207func (txsel *TxSelector) GetL1L2TxSelection(selectionConfig *SelectionConfig,
208 batchNum common.BatchNum, l1Txs []common.L1Tx) ([]common.Idx, [][]byte, []common.L1Tx, []common.L1Tx,
209 []common.PoolL2Tx, error) {
210 // TODO WIP this method uses a 'cherry-pick' of internal calls of the
211 // StateDB, a refactor of the StateDB to reorganize it internally is
212 // planned once the main functionallities are covered, with that
213 // refactor the TxSelector will be updated also
214
215 // apply l1-user-tx to localAccountDB
216 // create new leaves
217 // update balances
218 // update nonces
219
220 // get existing CoordIdxs
221 coordIdxsMap, err := txsel.GetCoordIdxs()
222 if err != nil {
223 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
224 }
225 var coordIdxs []common.Idx
226 for tokenID := range coordIdxsMap {
227 coordIdxs = append(coordIdxs, coordIdxsMap[tokenID])
228 }
229
230 // get pending l2-tx from tx-pool
231 l2TxsRaw, err := txsel.l2db.GetPendingTxs() // (batchID)
232 if err != nil {
233 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
234 }
235
236 txselStateDB := txsel.localAccountsDB.StateDB
237 tp := txprocessor.NewTxProcessor(txselStateDB, selectionConfig.TxProcessorConfig)
238
239 var validTxs txs
240 var l1CoordinatorTxs []common.L1Tx
241 positionL1 := len(l1Txs)
242
243 // Process L1UserTxs
244 for i := 0; i < len(l1Txs); i++ {
245 // assumption: l1usertx are sorted by L1Tx.Position
246 _, _, _, _, err := tp.ProcessL1Tx(nil, &l1Txs[i])
247 if err != nil {
248 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
249 }
250 }
251
252 // get last idx from LocalStateDB
253 // lastIdx := txsel.localStateDB.idx
254 // update lastIdx with the L1UserTxs (of account creation)
255
256 var accAuths [][]byte
257 for i := 0; i < len(l2TxsRaw); i++ {
258 // If tx.ToIdx>=256, tx.ToIdx should exist to localAccountsDB,
259 // if so, tx is used. If tx.ToIdx==0, for an L2Tx will be the
260 // case of TxToEthAddr or TxToBJJ, check if
261 // tx.ToEthAddr/tx.ToBJJ exist in localAccountsDB, if yes tx is
262 // used; if not, check if tx.ToEthAddr is in
263 // AccountCreationAuthDB, if so, tx is used and L1CoordinatorTx
264 // of CreateAccountAndDeposit is created. If tx.ToIdx==1, is a
265 // Exit type and is used.
266 if l2TxsRaw[i].ToIdx == 0 { // ToEthAddr/ToBJJ case
267 var accAuth *common.AccountCreationAuth
268 validTxs, l1CoordinatorTxs, accAuth, positionL1, err =
269 txsel.processTxToEthAddrBJJ(validTxs, l1CoordinatorTxs,
270 positionL1, l2TxsRaw[i])
271 if err != nil {
272 log.Debug(err)
273 continue
274 }
275 if accAuth != nil {
276 accAuths = append(accAuths, accAuth.Signature)
277 }
278 } else if l2TxsRaw[i].ToIdx >= common.IdxUserThreshold {
279 _, err = txsel.localAccountsDB.GetAccount(l2TxsRaw[i].ToIdx)
280 if err != nil {
281 // tx not valid
282 log.Debugw("invalid L2Tx: ToIdx not found in StateDB",
283 "ToIdx", l2TxsRaw[i].ToIdx)
284 continue
285 }
286
287 // TODO if EthAddr!=0 or BJJ!=0, check that ToIdxAccount.EthAddr or BJJ
288
289 // Account found in the DB, include the l2Tx in the selection
290 validTxs = append(validTxs, l2TxsRaw[i])
291 } else if l2TxsRaw[i].ToIdx == common.Idx(1) {
292 // valid txs (of Exit type)
293 validTxs = append(validTxs, l2TxsRaw[i])
294 }
295 // TODO if needed add L1CoordinatorTx to create a Coordinator
296 // account for the new TokenID
297 // var newL1CoordTx *common.L1Tx
298 // newL1CoordTx, positionL1, err = txsel.coordAccountForTokenID(l1CoordinatorTxs, l2TxsRaw[i].TokenID, positionL1)
299 // if err != nil {
300 // return nil, nil, nil, nil, nil, tracerr.Wrap(err)
301 // }
302 // if newL1CoordTx != nil {
303 // l1CoordinatorTxs = append(l1CoordinatorTxs, *newL1CoordTx)
304 // }
305 }
306
307 // Process L1CoordinatorTxs
308 for i := 0; i < len(l1CoordinatorTxs); i++ {
309 _, _, _, _, err := tp.ProcessL1Tx(nil, &l1CoordinatorTxs[i])
310 if err != nil {
311 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
312 }
313 }
314 tp.AccumulatedFees = make(map[common.Idx]*big.Int)
315 for _, idx := range coordIdxs {
316 tp.AccumulatedFees[idx] = big.NewInt(0)
317 }
318
319 // once L1UserTxs & L1CoordinatorTxs are processed, get TokenIDs of
320 // coordIdxs. In this way, if a coordIdx uses an Idx that is being
321 // created in the current batch, at this point the Idx will be created
322 coordIdxsMap, err = txsel.localAccountsDB.GetTokenIDsFromIdxs(coordIdxs)
323 if err != nil {
324 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
325 }
326
327 // get most profitable L2-tx
328 maxL2Txs := selectionConfig.TxProcessorConfig.MaxTx - uint32(len(l1CoordinatorTxs)) // - len(l1UserTxs) // TODO if there are L1UserTxs take them in to account
329 l2Txs := txsel.getL2Profitable(validTxs, maxL2Txs)
330
331 // Process L2Txs
332 for i := 0; i < len(l2Txs); i++ {
333 _, _, _, err = tp.ProcessL2Tx(coordIdxsMap, nil, nil, &l2Txs[i])
334 if err != nil {
335 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
336 }
337 }
338 err = txsel.AddCoordIdxs(coordIdxsMap)
339 if err != nil {
340 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
341 }
342
343 err = txsel.localAccountsDB.MakeCheckpoint()
344 if err != nil {
345 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
346 }
347
348 return nil, accAuths, l1Txs, l1CoordinatorTxs, l2Txs, nil
349}
350
351// processTxsToEthAddrBJJ process the common.PoolL2Tx in the case where
352// ToIdx==0, which can be the tx type of ToEthAddr or ToBJJ. If the receiver
353// does not have an account yet, a new L1CoordinatorTx of type
354// CreateAccountDeposit (with 0 as DepositAmount) is created and added to the
355// l1CoordinatorTxs array, and then the PoolL2Tx is added into the validTxs
356// array.
357func (txsel *TxSelector) processTxToEthAddrBJJ(validTxs txs, l1CoordinatorTxs []common.L1Tx,
358 positionL1 int, l2Tx common.PoolL2Tx) (txs, []common.L1Tx, *common.AccountCreationAuth, int, error) {
359 // if L2Tx needs a new L1CoordinatorTx of CreateAccount type, and a
360 // previous L2Tx in the current process already created a
361 // L1CoordinatorTx of this type, in the DB there still seem that needs
362 // to create a new L1CoordinatorTx, but as is already created, the tx
363 // is valid
364 if checkAlreadyPendingToCreate(l1CoordinatorTxs, l2Tx.TokenID, l2Tx.ToEthAddr, l2Tx.ToBJJ) {
365 validTxs = append(validTxs, l2Tx)
366 return validTxs, l1CoordinatorTxs, nil, positionL1, nil
367 }
368
369 var accAuth *common.AccountCreationAuth
370 if !bytes.Equal(l2Tx.ToEthAddr.Bytes(), common.EmptyAddr.Bytes()) &&
371 !bytes.Equal(l2Tx.ToEthAddr.Bytes(), common.FFAddr.Bytes()) {
372 // case: ToEthAddr != 0x00 neither 0xff
373 if l2Tx.ToBJJ != common.EmptyBJJComp {
374 // case: ToBJJ!=0:
375 // if idx exist for EthAddr&BJJ use it
376 _, err := txsel.localAccountsDB.GetIdxByEthAddrBJJ(l2Tx.ToEthAddr,
377 l2Tx.ToBJJ, l2Tx.TokenID)
378 if err == nil {
379 // account for ToEthAddr&ToBJJ already exist,
380 // there is no need to create a new one.
381 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
382 validTxs = append(validTxs, l2Tx)
383 return validTxs, l1CoordinatorTxs, nil, positionL1, nil
384 }
385 // if not, check if AccountCreationAuth exist for that
386 // ToEthAddr
387 accAuth, err = txsel.l2db.GetAccountCreationAuth(l2Tx.ToEthAddr)
388 if err != nil {
389 // not found, l2Tx will not be added in the selection
390 return validTxs, l1CoordinatorTxs, nil, positionL1, tracerr.Wrap(fmt.Errorf("invalid L2Tx: ToIdx not found in StateDB, neither ToEthAddr found in AccountCreationAuths L2DB. ToIdx: %d, ToEthAddr: %s",
391 l2Tx.ToIdx, l2Tx.ToEthAddr.Hex()))
392 }
393 if accAuth.BJJ != l2Tx.ToBJJ {
394 // if AccountCreationAuth.BJJ is not the same
395 // than in the tx, tx is not accepted
396 return validTxs, l1CoordinatorTxs, nil, positionL1, tracerr.Wrap(fmt.Errorf("invalid L2Tx: ToIdx not found in StateDB, neither ToEthAddr & ToBJJ found in AccountCreationAuths L2DB. ToIdx: %d, ToEthAddr: %s, ToBJJ: %s",
397 l2Tx.ToIdx, l2Tx.ToEthAddr.Hex(), l2Tx.ToBJJ.String()))
398 }
399 validTxs = append(validTxs, l2Tx)
400 } else {
401 // case: ToBJJ==0:
402 // if idx exist for EthAddr use it
403 _, err := txsel.localAccountsDB.GetIdxByEthAddr(l2Tx.ToEthAddr, l2Tx.TokenID)
404 if err == nil {
405 // account for ToEthAddr already exist,
406 // there is no need to create a new one.
407 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
408 validTxs = append(validTxs, l2Tx)
409 return validTxs, l1CoordinatorTxs, nil, positionL1, nil
410 }
411 // if not, check if AccountCreationAuth exist for that ToEthAddr
412 accAuth, err = txsel.l2db.GetAccountCreationAuth(l2Tx.ToEthAddr)
413 if err != nil {
414 // not found, l2Tx will not be added in the selection
415 return validTxs, l1CoordinatorTxs, nil, positionL1, tracerr.Wrap(fmt.Errorf("invalid L2Tx: ToIdx not found in StateDB, neither ToEthAddr found in AccountCreationAuths L2DB. ToIdx: %d, ToEthAddr: %s",
416 l2Tx.ToIdx, l2Tx.ToEthAddr))
417 }
418 validTxs = append(validTxs, l2Tx)
419 }
420 // create L1CoordinatorTx for the accountCreation
421 l1CoordinatorTx := common.L1Tx{
422 Position: positionL1,
423 UserOrigin: false,
424 FromEthAddr: accAuth.EthAddr,
425 FromBJJ: accAuth.BJJ,
426 TokenID: l2Tx.TokenID,
427 DepositAmount: big.NewInt(0),
428 Type: common.TxTypeCreateAccountDeposit,
429 }
430 positionL1++
431 l1CoordinatorTxs = append(l1CoordinatorTxs, l1CoordinatorTx)
432 } else if bytes.Equal(l2Tx.ToEthAddr.Bytes(), common.FFAddr.Bytes()) && l2Tx.ToBJJ != common.EmptyBJJComp {
433 // if idx exist for EthAddr&BJJ use it
434 _, err := txsel.localAccountsDB.GetIdxByEthAddrBJJ(l2Tx.ToEthAddr, l2Tx.ToBJJ,
435 l2Tx.TokenID)
436 if err == nil {
437 // account for ToEthAddr&ToBJJ already exist, (where ToEthAddr==0xff)
438 // there is no need to create a new one.
439 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
440 validTxs = append(validTxs, l2Tx)
441 return validTxs, l1CoordinatorTxs, nil, positionL1, nil
442 }
443 // if idx don't exist for EthAddr&BJJ,
444 // coordinator can create a new account without
445 // L1Authorization, as ToEthAddr==0xff
446 // create L1CoordinatorTx for the accountCreation
447 l1CoordinatorTx := common.L1Tx{
448 Position: positionL1,
449 UserOrigin: false,
450 FromEthAddr: l2Tx.ToEthAddr,
451 FromBJJ: l2Tx.ToBJJ,
452 TokenID: l2Tx.TokenID,
453 DepositAmount: big.NewInt(0),
454 Type: common.TxTypeCreateAccountDeposit,
455 }
456 positionL1++
457 l1CoordinatorTxs = append(l1CoordinatorTxs, l1CoordinatorTx)
458 }
459
460 return validTxs, l1CoordinatorTxs, accAuth, positionL1, nil
461}
462
463func checkAlreadyPendingToCreate(l1CoordinatorTxs []common.L1Tx, tokenID common.TokenID,
464 addr ethCommon.Address, bjj babyjub.PublicKeyComp) bool {
465 for i := 0; i < len(l1CoordinatorTxs); i++ {
466 if bytes.Equal(l1CoordinatorTxs[i].FromEthAddr.Bytes(), addr.Bytes()) &&
467 l1CoordinatorTxs[i].TokenID == tokenID &&
468 l1CoordinatorTxs[i].FromBJJ == bjj {
469 return true
470 }
471 }
472 return false
473}
474
475// getL2Profitable returns the profitable selection of L2Txssorted by Nonce
476func (txsel *TxSelector) getL2Profitable(txs txs, max uint32) txs {
477 sort.Sort(txs)
478 if len(txs) < int(max) {
479 return txs
480 }
481 txs = txs[:max]
482
483 // sort l2Txs by Nonce. This can be done in many different ways, what
484 // is needed is to output the txs where the Nonce of txs for each
485 // Account is sorted, but the txs can not be grouped by sender Account
486 // neither by Fee. This is because later on the Nonces will need to be
487 // sequential for the zkproof generation.
488 sort.SliceStable(txs, func(i, j int) bool {
489 return txs[i].Nonce < txs[j].Nonce
490 })
491
492 return txs
493}