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)
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 // TxProcessorConfig contains the config for ProcessTxs
59 TxProcessorConfig txprocessor.Config
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}
70
71// NewTxSelector returns a *TxSelector
72func NewTxSelector(coordAccount *CoordAccount, dbpath string,
73 synchronizerStateDB *statedb.StateDB, l2 *l2db.L2DB) (*TxSelector, error) {
74 localAccountsDB, err := statedb.NewLocalStateDB(dbpath, 128,
75 synchronizerStateDB, statedb.TypeTxSelector, 0) // without merkletree
76 if err != nil {
77 return nil, tracerr.Wrap(err)
78 }
79
80 return &TxSelector{
81 l2db: l2,
82 localAccountsDB: localAccountsDB,
83 coordAccount: coordAccount,
84 }, nil
85}
86
87// LocalAccountsDB returns the LocalStateDB of the TxSelector
88func (txsel *TxSelector) LocalAccountsDB() *statedb.LocalStateDB {
89 return txsel.localAccountsDB
90}
91
92// Reset tells the TxSelector to get it's internal AccountsDB
93// from the required `batchNum`
94func (txsel *TxSelector) Reset(batchNum common.BatchNum) error {
95 err := txsel.localAccountsDB.Reset(batchNum, true)
96 if err != nil {
97 return tracerr.Wrap(err)
98 }
99 return nil
100}
101
102func (txsel *TxSelector) getCoordIdx(tokenID common.TokenID) (common.Idx, error) {
103 return txsel.localAccountsDB.GetIdxByEthAddrBJJ(txsel.coordAccount.Addr, txsel.coordAccount.BJJ, tokenID)
104}
105
106// coordAccountForTokenID creates a new L1CoordinatorTx to create a new
107// Coordinator account for the given TokenID in the case that the account does
108// not exist yet in the db, and does not exist a L1CoordinatorTx to creat that
109// account in the given array of L1CoordinatorTxs. If a new Coordinator account
110// needs to be created, a new L1CoordinatorTx will be returned from this
111// function.
112//nolint:unused
113func (txsel *TxSelector) coordAccountForTokenID(l1CoordinatorTxs []common.L1Tx,
114 tokenID common.TokenID, positionL1 int) (*common.L1Tx, int, error) {
115 // check if CoordinatorAccount for TokenID is already pending to create
116 if checkAlreadyPendingToCreate(l1CoordinatorTxs, tokenID,
117 txsel.coordAccount.Addr, txsel.coordAccount.BJJ) {
118 return nil, positionL1, nil
119 }
120 _, err := txsel.localAccountsDB.GetIdxByEthAddrBJJ(txsel.coordAccount.Addr, txsel.coordAccount.BJJ, tokenID)
121 if tracerr.Unwrap(err) == statedb.ErrIdxNotFound {
122 // create L1CoordinatorTx to create new CoordAccount for
123 // TokenID
124 l1CoordinatorTx := common.L1Tx{
125 Position: positionL1,
126 UserOrigin: false,
127 FromEthAddr: txsel.coordAccount.Addr,
128 FromBJJ: txsel.coordAccount.BJJ,
129 TokenID: tokenID,
130 Amount: big.NewInt(0),
131 DepositAmount: big.NewInt(0),
132 Type: common.TxTypeCreateAccountDeposit,
133 }
134 positionL1++
135
136 return &l1CoordinatorTx, positionL1, nil
137 }
138 if err != nil {
139 return nil, positionL1, tracerr.Wrap(err)
140 }
141 // CoordAccount for TokenID already exists
142 return nil, positionL1, nil
143}
144
145// GetL2TxSelection returns the L1CoordinatorTxs and a selection of the L2Txs
146// for the next batch, from the L2DB pool.
147// It returns: the CoordinatorIdxs used to receive the fees of the selected
148// L2Txs. An array of bytearrays with the signatures of the
149// AccountCreationAuthorization of the accounts of the users created by the
150// Coordinator with L1CoordinatorTxs of those accounts that does not exist yet
151// but there is a transactions to them and the authorization of account
152// creation exists. The L1UserTxs, L1CoordinatorTxs, PoolL2Txs that will be
153// included in the next batch.
154func (txsel *TxSelector) GetL2TxSelection(selectionConfig *SelectionConfig,
155 batchNum common.BatchNum) ([]common.Idx, [][]byte, []common.L1Tx, []common.PoolL2Tx, error) {
156 coordIdxs, accCreationAuths, _, l1CoordinatorTxs, l2Txs, err :=
157 txsel.GetL1L2TxSelection(selectionConfig, batchNum, []common.L1Tx{})
158 return coordIdxs, accCreationAuths, l1CoordinatorTxs, l2Txs, tracerr.Wrap(err)
159}
160
161// GetL1L2TxSelection returns the selection of L1 + L2 txs.
162// It returns: the CoordinatorIdxs used to receive the fees of the selected
163// L2Txs. An array of bytearrays with the signatures of the
164// AccountCreationAuthorization of the accounts of the users created by the
165// Coordinator with L1CoordinatorTxs of those accounts that does not exist yet
166// but there is a transactions to them and the authorization of account
167// creation exists. The L1UserTxs, L1CoordinatorTxs, PoolL2Txs that will be
168// included in the next batch.
169func (txsel *TxSelector) GetL1L2TxSelection(selectionConfig *SelectionConfig,
170 batchNum common.BatchNum, l1Txs []common.L1Tx) ([]common.Idx, [][]byte, []common.L1Tx,
171 []common.L1Tx, []common.PoolL2Tx, error) {
172 // TODO WIP this method uses a 'cherry-pick' of internal calls of the
173 // StateDB, a refactor of the StateDB to reorganize it internally is
174 // planned once the main functionallities are covered, with that
175 // refactor the TxSelector will be updated also
176
177 // get pending l2-tx from tx-pool
178 l2TxsRaw, err := txsel.l2db.GetPendingTxs()
179 if err != nil {
180 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
181 }
182
183 txselStateDB := txsel.localAccountsDB.StateDB
184 tp := txprocessor.NewTxProcessor(txselStateDB, selectionConfig.TxProcessorConfig)
185
186 // Process L1UserTxs
187 for i := 0; i < len(l1Txs); i++ {
188 // assumption: l1usertx are sorted by L1Tx.Position
189 _, _, _, _, err := tp.ProcessL1Tx(nil, &l1Txs[i])
190 if err != nil {
191 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
192 }
193 }
194
195 var l1CoordinatorTxs []common.L1Tx
196 positionL1 := len(l1Txs)
197 var accAuths [][]byte
198
199 // sort l2TxsRaw (cropping at MaxTx at this point)
200 l2Txs := txsel.getL2Profitable(l2TxsRaw, selectionConfig.TxProcessorConfig.MaxTx)
201
202 // TODO for L1CoordinatorTxs check that always len(l1UserTxs)+len(l1CoordinatorTxs)<MaxL1Txs
203
204 // iterate over l2Txs
205 // - if tx.TokenID does not exist at CoordsIdxDB
206 // - create new L1CoordinatorTx, for Coordinator to receive the fee of the new TokenID
207 for i := 0; i < len(l2Txs); i++ {
208 // check if l2Tx.TokenID does not exist at CoordsIdxDB
209 _, err = txsel.getCoordIdx(l2Txs[i].TokenID) // TODO already used inside coordAccountForTokenID, this will be removed
210 if tracerr.Unwrap(err) != db.ErrNotFound {
211 // if TokenID does not exist yet, create new
212 // L1CoordinatorTx to create the CoordinatorAccount for
213 // that TokenID, to receive the fees. Only in the case
214 // that there does not exist yet a pending
215 // L1CoordinatorTx to create the account for the
216 // Coordinator for that TokenID
217
218 // TODO TMP
219 // var newL1CoordTx *common.L1Tx
220 // newL1CoordTx, positionL1, err =
221 // txsel.coordAccountForTokenID(l1CoordinatorTxs,
222 // l2TxsRaw[i].TokenID, positionL1)
223 // if err != nil {
224 // return nil, nil, nil, nil, nil, tracerr.Wrap(err)
225 // }
226 // if newL1CoordTx != nil {
227 // l1CoordinatorTxs = append(l1CoordinatorTxs, *newL1CoordTx)
228 // }
229 } else if err != nil {
230 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
231 }
232 }
233
234 var validTxs txs
235 // iterate over l2TxsRaw
236 // - if needed, create new L1CoordinatorTxs for unexisting ToIdx
237 // - keep used accAuths
238 // - put the valid txs into validTxs array
239 for i := 0; i < len(l2Txs); i++ {
240 // If tx.ToIdx>=256, tx.ToIdx should exist to localAccountsDB,
241 // if so, tx is used. If tx.ToIdx==0, for an L2Tx will be the
242 // case of TxToEthAddr or TxToBJJ, check if
243 // tx.ToEthAddr/tx.ToBJJ exist in localAccountsDB, if yes tx is
244 // used; if not, check if tx.ToEthAddr is in
245 // AccountCreationAuthDB, if so, tx is used and L1CoordinatorTx
246 // of CreateAccountAndDeposit is created. If tx.ToIdx==1, is a
247 // Exit type and is used.
248 if l2Txs[i].ToIdx == 0 { // ToEthAddr/ToBJJ case
249 var accAuth *common.AccountCreationAuth
250 validTxs, l1CoordinatorTxs, accAuth, positionL1, err =
251 txsel.processTxToEthAddrBJJ(validTxs, l1CoordinatorTxs,
252 positionL1, l2Txs[i])
253 if err != nil {
254 log.Debug(err)
255 continue
256 }
257 if accAuth != nil {
258 accAuths = append(accAuths, accAuth.Signature)
259 }
260 } else if l2Txs[i].ToIdx >= common.IdxUserThreshold {
261 _, err = txsel.localAccountsDB.GetAccount(l2Txs[i].ToIdx)
262 if err != nil {
263 // tx not valid
264 log.Debugw("invalid L2Tx: ToIdx not found in StateDB",
265 "ToIdx", l2Txs[i].ToIdx)
266 continue
267 }
268 // TODO if EthAddr!=0 or BJJ!=0, check that ToIdxAccount.EthAddr or BJJ
269
270 // Account found in the DB, include the l2Tx in the selection
271 validTxs = append(validTxs, l2Txs[i])
272 } else if l2Txs[i].ToIdx == common.Idx(1) {
273 // valid txs (of Exit type)
274 validTxs = append(validTxs, l2Txs[i])
275 }
276 }
277
278 // Process L1CoordinatorTxs
279 for i := 0; i < len(l1CoordinatorTxs); i++ {
280 _, _, _, _, err := tp.ProcessL1Tx(nil, &l1CoordinatorTxs[i])
281 if err != nil {
282 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
283 }
284 }
285
286 // get CoordIdxsMap for the TokenIDs
287 coordIdxsMap := make(map[common.TokenID]common.Idx)
288 // TODO TMP (related to L#260
289 // for i := 0; i < len(l2Txs); i++ {
290 // coordIdx, err := txsel.getCoordIdx(l2Txs[i].TokenID)
291 // if err != nil {
292 // // if err is db.ErrNotFound, should not happen, as all
293 // // the l2Txs.TokenID should have a CoordinatorIdx
294 // // created in the DB at this point
295 // return nil, nil, nil, nil, nil, tracerr.Wrap(err)
296 // }
297 // coordIdxsMap[l2Txs[i].TokenID] = coordIdx
298 // }
299
300 var coordIdxs []common.Idx
301 tp.AccumulatedFees = make(map[common.Idx]*big.Int)
302 for _, idx := range coordIdxsMap {
303 tp.AccumulatedFees[idx] = big.NewInt(0)
304 coordIdxs = append(coordIdxs, idx)
305 }
306
307 // get most profitable L2-tx
308 maxL2Txs := selectionConfig.TxProcessorConfig.MaxTx - uint32(len(l1CoordinatorTxs)) // - len(l1UserTxs) // TODO if there are L1UserTxs take them in to account
309 selectedL2Txs := txsel.getL2Profitable(l2Txs, maxL2Txs) // TODO this will only need to crop the lasts, as are already sorted
310 for i := 0; i < len(selectedL2Txs); i++ {
311 _, _, _, err = tp.ProcessL2Tx(coordIdxsMap, nil, nil, &selectedL2Txs[i])
312 if err != nil {
313 return nil, nil, nil, nil, nil, tracerr.Wrap(err)
314 }
315 }
316
317 return coordIdxs, accAuths, l1Txs, l1CoordinatorTxs, selectedL2Txs, nil
318}
319
320// processTxsToEthAddrBJJ process the common.PoolL2Tx in the case where
321// ToIdx==0, which can be the tx type of ToEthAddr or ToBJJ. If the receiver
322// does not have an account yet, a new L1CoordinatorTx of type
323// CreateAccountDeposit (with 0 as DepositAmount) is created and added to the
324// l1CoordinatorTxs array, and then the PoolL2Tx is added into the validTxs
325// array.
326func (txsel *TxSelector) processTxToEthAddrBJJ(validTxs txs, l1CoordinatorTxs []common.L1Tx,
327 positionL1 int, l2Tx common.PoolL2Tx) (txs, []common.L1Tx, *common.AccountCreationAuth, int, error) {
328 // if L2Tx needs a new L1CoordinatorTx of CreateAccount type, and a
329 // previous L2Tx in the current process already created a
330 // L1CoordinatorTx of this type, in the DB there still seem that needs
331 // to create a new L1CoordinatorTx, but as is already created, the tx
332 // is valid
333 if checkAlreadyPendingToCreate(l1CoordinatorTxs, l2Tx.TokenID, l2Tx.ToEthAddr, l2Tx.ToBJJ) {
334 validTxs = append(validTxs, l2Tx)
335 return validTxs, l1CoordinatorTxs, nil, positionL1, nil
336 }
337
338 var accAuth *common.AccountCreationAuth
339 if !bytes.Equal(l2Tx.ToEthAddr.Bytes(), common.EmptyAddr.Bytes()) &&
340 !bytes.Equal(l2Tx.ToEthAddr.Bytes(), common.FFAddr.Bytes()) {
341 // case: ToEthAddr != 0x00 neither 0xff
342 if l2Tx.ToBJJ != common.EmptyBJJComp {
343 // case: ToBJJ!=0:
344 // if idx exist for EthAddr&BJJ use it
345 _, err := txsel.localAccountsDB.GetIdxByEthAddrBJJ(l2Tx.ToEthAddr,
346 l2Tx.ToBJJ, l2Tx.TokenID)
347 if err == nil {
348 // account for ToEthAddr&ToBJJ already exist,
349 // there is no need to create a new one.
350 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
351 validTxs = append(validTxs, l2Tx)
352 return validTxs, l1CoordinatorTxs, nil, positionL1, nil
353 }
354 // if not, check if AccountCreationAuth exist for that
355 // ToEthAddr
356 accAuth, err = txsel.l2db.GetAccountCreationAuth(l2Tx.ToEthAddr)
357 if err != nil {
358 // not found, l2Tx will not be added in the selection
359 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",
360 l2Tx.ToIdx, l2Tx.ToEthAddr.Hex()))
361 }
362 if accAuth.BJJ != l2Tx.ToBJJ {
363 // if AccountCreationAuth.BJJ is not the same
364 // than in the tx, tx is not accepted
365 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",
366 l2Tx.ToIdx, l2Tx.ToEthAddr.Hex(), l2Tx.ToBJJ.String()))
367 }
368 validTxs = append(validTxs, l2Tx)
369 } else {
370 // case: ToBJJ==0:
371 // if idx exist for EthAddr use it
372 _, err := txsel.localAccountsDB.GetIdxByEthAddr(l2Tx.ToEthAddr, l2Tx.TokenID)
373 if err == nil {
374 // account for ToEthAddr already exist,
375 // there is no need to create a new one.
376 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
377 validTxs = append(validTxs, l2Tx)
378 return validTxs, l1CoordinatorTxs, nil, positionL1, nil
379 }
380 // if not, check if AccountCreationAuth exist for that ToEthAddr
381 accAuth, err = txsel.l2db.GetAccountCreationAuth(l2Tx.ToEthAddr)
382 if err != nil {
383 // not found, l2Tx will not be added in the selection
384 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",
385 l2Tx.ToIdx, l2Tx.ToEthAddr))
386 }
387 validTxs = append(validTxs, l2Tx)
388 }
389 // create L1CoordinatorTx for the accountCreation
390 l1CoordinatorTx := common.L1Tx{
391 Position: positionL1,
392 UserOrigin: false,
393 FromEthAddr: accAuth.EthAddr,
394 FromBJJ: accAuth.BJJ,
395 TokenID: l2Tx.TokenID,
396 Amount: big.NewInt(0),
397 DepositAmount: big.NewInt(0),
398 Type: common.TxTypeCreateAccountDeposit,
399 }
400 positionL1++
401 l1CoordinatorTxs = append(l1CoordinatorTxs, l1CoordinatorTx)
402 } else if bytes.Equal(l2Tx.ToEthAddr.Bytes(), common.FFAddr.Bytes()) && l2Tx.ToBJJ != common.EmptyBJJComp {
403 // if idx exist for EthAddr&BJJ use it
404 _, err := txsel.localAccountsDB.GetIdxByEthAddrBJJ(l2Tx.ToEthAddr, l2Tx.ToBJJ,
405 l2Tx.TokenID)
406 if err == nil {
407 // account for ToEthAddr&ToBJJ already exist, (where ToEthAddr==0xff)
408 // there is no need to create a new one.
409 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
410 validTxs = append(validTxs, l2Tx)
411 return validTxs, l1CoordinatorTxs, nil, positionL1, nil
412 }
413 // if idx don't exist for EthAddr&BJJ,
414 // coordinator can create a new account without
415 // L1Authorization, as ToEthAddr==0xff
416 // create L1CoordinatorTx for the accountCreation
417 l1CoordinatorTx := common.L1Tx{
418 Position: positionL1,
419 UserOrigin: false,
420 FromEthAddr: l2Tx.ToEthAddr,
421 FromBJJ: l2Tx.ToBJJ,
422 TokenID: l2Tx.TokenID,
423 Amount: big.NewInt(0),
424 DepositAmount: big.NewInt(0),
425 Type: common.TxTypeCreateAccountDeposit,
426 }
427 positionL1++
428 l1CoordinatorTxs = append(l1CoordinatorTxs, l1CoordinatorTx)
429 }
430
431 return validTxs, l1CoordinatorTxs, accAuth, positionL1, nil
432}
433
434func checkAlreadyPendingToCreate(l1CoordinatorTxs []common.L1Tx, tokenID common.TokenID,
435 addr ethCommon.Address, bjj babyjub.PublicKeyComp) bool {
436 for i := 0; i < len(l1CoordinatorTxs); i++ {
437 if bytes.Equal(l1CoordinatorTxs[i].FromEthAddr.Bytes(), addr.Bytes()) &&
438 l1CoordinatorTxs[i].TokenID == tokenID &&
439 l1CoordinatorTxs[i].FromBJJ == bjj {
440 return true
441 }
442 }
443 return false
444}
445
446// getL2Profitable returns the profitable selection of L2Txssorted by Nonce
447func (txsel *TxSelector) getL2Profitable(txs txs, max uint32) txs {
448 sort.Sort(txs)
449 if len(txs) < int(max) {
450 return txs
451 }
452 txs = txs[:max]
453
454 // sort l2Txs by Nonce. This can be done in many different ways, what
455 // is needed is to output the txs where the Nonce of txs for each
456 // Account is sorted, but the txs can not be grouped by sender Account
457 // neither by Fee. This is because later on the Nonces will need to be
458 // sequential for the zkproof generation.
459 sort.SliceStable(txs, func(i, j int) bool {
460 return txs[i].Nonce < txs[j].Nonce
461 })
462
463 return txs
464}