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