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/pebble"
19)
20
21const (
22 // PathCoordIdxsDB defines the path of the key-value db where the
23 // CoordIdxs will be stored
24 PathCoordIdxsDB = "/coordidxs"
25)
26
27// txs implements the interface Sort for an array of Tx
28type txs []common.PoolL2Tx
29
30func (t txs) Len() int {
31 return len(t)
32}
33func (t txs) Swap(i, j int) {
34 t[i], t[j] = t[j], t[i]
35}
36func (t txs) Less(i, j int) bool {
37 return t[i].AbsoluteFee > t[j].AbsoluteFee
38}
39
40// CoordAccount contains the data of the Coordinator account, that will be used
41// to create new transactions of CreateAccountDeposit type to add new TokenID
42// accounts for the Coordinator to receive the fees.
43type CoordAccount struct {
44 Addr ethCommon.Address
45 BJJ *babyjub.PublicKey
46 AccountCreationAuth []byte
47}
48
49// SelectionConfig contains the parameters of configuration of the selection of
50// transactions for the next batch
51type SelectionConfig struct {
52 // MaxL1UserTxs is the maximum L1-user-tx for a batch
53 MaxL1UserTxs uint64
54 // MaxL1CoordinatorTxs is the maximum L1-coordinator-tx for a batch
55 MaxL1CoordinatorTxs uint64
56
57 // ProcessTxsConfig contains the config for ProcessTxs
58 ProcessTxsConfig statedb.ProcessTxsConfig
59}
60
61// TxSelector implements all the functionalities to select the txs for the next
62// batch
63type TxSelector struct {
64 l2db *l2db.L2DB
65 localAccountsDB *statedb.LocalStateDB
66
67 coordAccount *CoordAccount
68 coordIdxsDB *pebble.PebbleStorage
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,
75 synchronizerStateDB, statedb.TypeTxSelector, 0) // without merkletree
76 if err != nil {
77 return nil, tracerr.Wrap(err)
78 }
79
80 coordIdxsDB, err := pebble.NewPebbleStorage(dbpath+PathCoordIdxsDB, false)
81 if err != nil {
82 return nil, tracerr.Wrap(err)
83 }
84
85 return &TxSelector{
86 l2db: l2,
87 localAccountsDB: localAccountsDB,
88 coordAccount: coordAccount,
89 coordIdxsDB: coordIdxsDB,
90 }, nil
91}
92
93// LocalAccountsDB returns the LocalStateDB of the TxSelector
94func (txsel *TxSelector) LocalAccountsDB() *statedb.LocalStateDB {
95 return txsel.localAccountsDB
96}
97
98// Reset tells the TxSelector to get it's internal AccountsDB
99// from the required `batchNum`
100func (txsel *TxSelector) Reset(batchNum common.BatchNum) error {
101 err := txsel.localAccountsDB.Reset(batchNum, true)
102 if err != nil {
103 return tracerr.Wrap(err)
104 }
105 return nil
106}
107
108// AddCoordIdxs stores the given TokenID with the correspondent Idx to the
109// CoordIdxsDB
110func (txsel *TxSelector) AddCoordIdxs(idxs map[common.TokenID]common.Idx) error {
111 tx, err := txsel.coordIdxsDB.NewTx()
112 if err != nil {
113 return tracerr.Wrap(err)
114 }
115 for tokenID, idx := range idxs {
116 idxBytes, err := idx.Bytes()
117 if err != nil {
118 return tracerr.Wrap(err)
119 }
120 err = tx.Put(tokenID.Bytes(), idxBytes[:])
121 if err != nil {
122 return tracerr.Wrap(err)
123 }
124 }
125 if err := tx.Commit(); err != nil {
126 return tracerr.Wrap(err)
127 }
128 return nil
129}
130
131// GetCoordIdxs returns a map with the stored TokenID with the correspondent
132// Coordinator Idx
133func (txsel *TxSelector) GetCoordIdxs() (map[common.TokenID]common.Idx, error) {
134 r := make(map[common.TokenID]common.Idx)
135 err := txsel.coordIdxsDB.Iterate(func(tokenIDBytes []byte, idxBytes []byte) (bool, error) {
136 idx, err := common.IdxFromBytes(idxBytes)
137 if err != nil {
138 return false, tracerr.Wrap(err)
139 }
140 tokenID, err := common.TokenIDFromBytes(tokenIDBytes)
141 if err != nil {
142 return false, tracerr.Wrap(err)
143 }
144 r[tokenID] = idx
145 return true, nil
146 })
147
148 return r, tracerr.Wrap(err)
149}
150
151// GetL2TxSelection returns the L1CoordinatorTxs and a selection of the L2Txs
152// for the next batch, from the L2DB pool
153func (txsel *TxSelector) GetL2TxSelection(selectionConfig *SelectionConfig,
154 batchNum common.BatchNum) ([]common.Idx, []common.L1Tx, []common.PoolL2Tx, error) {
155 coordIdxs, _, l1CoordinatorTxs, l2Txs, err := txsel.GetL1L2TxSelection(selectionConfig, batchNum,
156 []common.L1Tx{})
157 return coordIdxs, l1CoordinatorTxs, l2Txs, tracerr.Wrap(err)
158}
159
160// GetL1L2TxSelection returns the selection of L1 + L2 txs
161func (txsel *TxSelector) GetL1L2TxSelection(selectionConfig *SelectionConfig,
162 batchNum common.BatchNum, l1Txs []common.L1Tx) ([]common.Idx, []common.L1Tx, []common.L1Tx,
163 []common.PoolL2Tx, error) {
164 // apply l1-user-tx to localAccountDB
165 // create new leaves
166 // update balances
167 // update nonces
168
169 // get existing CoordIdxs
170 coordIdxsMap, err := txsel.GetCoordIdxs()
171 if err != nil {
172 return nil, nil, nil, nil, tracerr.Wrap(err)
173 }
174 var coordIdxs []common.Idx
175 for tokenID := range coordIdxsMap {
176 coordIdxs = append(coordIdxs, coordIdxsMap[tokenID])
177 }
178
179 // get pending l2-tx from tx-pool
180 l2TxsRaw, err := txsel.l2db.GetPendingTxs() // (batchID)
181 if err != nil {
182 return nil, nil, nil, nil, tracerr.Wrap(err)
183 }
184
185 var validTxs txs
186 var l1CoordinatorTxs []common.L1Tx
187 positionL1 := len(l1Txs)
188
189 for i := 0; i < len(l2TxsRaw); i++ {
190 // If tx.ToIdx>=256, tx.ToIdx should exist to localAccountsDB,
191 // if so, tx is used. If tx.ToIdx==0, for an L2Tx will be the
192 // case of TxToEthAddr or TxToBJJ, check if
193 // tx.ToEthAddr/tx.ToBJJ exist in localAccountsDB, if yes tx is
194 // used; if not, check if tx.ToEthAddr is in
195 // AccountCreationAuthDB, if so, tx is used and L1CoordinatorTx
196 // of CreateAccountAndDeposit is created. If tx.ToIdx==1, is a
197 // Exit type and is used.
198 if l2TxsRaw[i].ToIdx == 0 { // ToEthAddr/ToBJJ case
199 validTxs, l1CoordinatorTxs, positionL1, err =
200 txsel.processTxToEthAddrBJJ(validTxs, l1CoordinatorTxs,
201 positionL1, l2TxsRaw[i])
202 if err != nil {
203 log.Debug(err)
204 }
205 } else if l2TxsRaw[i].ToIdx >= common.IdxUserThreshold {
206 _, err = txsel.localAccountsDB.GetAccount(l2TxsRaw[i].ToIdx)
207 if err != nil {
208 // tx not valid
209 log.Debugw("invalid L2Tx: ToIdx not found in StateDB",
210 "ToIdx", l2TxsRaw[i].ToIdx)
211 continue
212 }
213
214 // TODO if EthAddr!=0 or BJJ!=0, check that ToIdxAccount.EthAddr or BJJ
215
216 // Account found in the DB, include the l2Tx in the selection
217 validTxs = append(validTxs, l2TxsRaw[i])
218 } else if l2TxsRaw[i].ToIdx == common.Idx(1) {
219 // valid txs (of Exit type)
220 validTxs = append(validTxs, l2TxsRaw[i])
221 }
222 }
223
224 // get most profitable L2-tx
225 maxL2Txs := selectionConfig.ProcessTxsConfig.MaxTx - uint32(len(l1CoordinatorTxs)) // - len(l1UserTxs) // TODO if there are L1UserTxs take them in to account
226 l2Txs := txsel.getL2Profitable(validTxs, maxL2Txs)
227
228 //nolint:gomnd
229 ptc := statedb.ProcessTxsConfig{ // TODO TMP
230 NLevels: 32,
231 MaxFeeTx: 64,
232 MaxTx: 512,
233 MaxL1Tx: 64,
234 }
235 // process the txs in the local AccountsDB
236 _, err = txsel.localAccountsDB.ProcessTxs(ptc, coordIdxs, l1Txs, l1CoordinatorTxs, l2Txs)
237 if err != nil {
238 return nil, nil, nil, nil, tracerr.Wrap(err)
239 }
240 err = txsel.localAccountsDB.MakeCheckpoint()
241 if err != nil {
242 return nil, nil, nil, nil, tracerr.Wrap(err)
243 }
244
245 return nil, l1Txs, l1CoordinatorTxs, l2Txs, nil
246}
247
248// processTxsToEthAddrBJJ process the common.PoolL2Tx in the case where
249// ToIdx==0, which can be the tx type of ToEthAddr or ToBJJ. If the receiver
250// does not have an account yet, a new L1CoordinatorTx of type
251// CreateAccountDeposit (with 0 as DepositAmount) is created and added to the
252// l1CoordinatorTxs array, and then the PoolL2Tx is added into the validTxs
253// array.
254func (txsel *TxSelector) processTxToEthAddrBJJ(validTxs txs, l1CoordinatorTxs []common.L1Tx,
255 positionL1 int, l2Tx common.PoolL2Tx) (txs, []common.L1Tx, int, error) {
256 // if L2Tx needs a new L1CoordinatorTx of CreateAccount type, and a
257 // previous L2Tx in the current process already created a
258 // L1CoordinatorTx of this type, in the DB there still seem that needs
259 // to create a new L1CoordinatorTx, but as is already created, the tx
260 // is valid
261 if checkAlreadyPendingToCreate(l1CoordinatorTxs, l2Tx.ToEthAddr, l2Tx.ToBJJ) {
262 validTxs = append(validTxs, l2Tx)
263 return validTxs, l1CoordinatorTxs, positionL1, nil
264 }
265
266 if !bytes.Equal(l2Tx.ToEthAddr.Bytes(), common.EmptyAddr.Bytes()) &&
267 !bytes.Equal(l2Tx.ToEthAddr.Bytes(), common.FFAddr.Bytes()) {
268 // case: ToEthAddr != 0x00 neither 0xff
269 var accAuth *common.AccountCreationAuth
270 if l2Tx.ToBJJ != common.EmptyBJJComp {
271 // case: ToBJJ!=0:
272 // if idx exist for EthAddr&BJJ use it
273 _, err := txsel.localAccountsDB.GetIdxByEthAddrBJJ(l2Tx.ToEthAddr,
274 l2Tx.ToBJJ, l2Tx.TokenID)
275 if err == nil {
276 // account for ToEthAddr&ToBJJ already exist,
277 // there is no need to create a new one.
278 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
279 validTxs = append(validTxs, l2Tx)
280 return validTxs, l1CoordinatorTxs, positionL1, nil
281 }
282 // if not, check if AccountCreationAuth exist for that
283 // ToEthAddr
284 accAuth, err = txsel.l2db.GetAccountCreationAuth(l2Tx.ToEthAddr)
285 if err != nil {
286 // not found, l2Tx will not be added in the selection
287 return validTxs, l1CoordinatorTxs, positionL1, tracerr.Wrap(fmt.Errorf("invalid L2Tx: ToIdx not found in StateDB, neither ToEthAddr found in AccountCreationAuths L2DB. ToIdx: %d, ToEthAddr: %s",
288 l2Tx.ToIdx, l2Tx.ToEthAddr.Hex()))
289 }
290 if accAuth.BJJ != l2Tx.ToBJJ {
291 // if AccountCreationAuth.BJJ is not the same
292 // than in the tx, tx is not accepted
293 return validTxs, l1CoordinatorTxs, 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",
294 l2Tx.ToIdx, l2Tx.ToEthAddr.Hex(), l2Tx.ToBJJ.String()))
295 }
296 validTxs = append(validTxs, l2Tx)
297 } else {
298 // case: ToBJJ==0:
299 // if idx exist for EthAddr use it
300 _, err := txsel.localAccountsDB.GetIdxByEthAddr(l2Tx.ToEthAddr, l2Tx.TokenID)
301 if err == nil {
302 // account for ToEthAddr already exist,
303 // there is no need to create a new one.
304 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
305 validTxs = append(validTxs, l2Tx)
306 return validTxs, l1CoordinatorTxs, positionL1, nil
307 }
308 // if not, check if AccountCreationAuth exist for that ToEthAddr
309 accAuth, err = txsel.l2db.GetAccountCreationAuth(l2Tx.ToEthAddr)
310 if err != nil {
311 // not found, l2Tx will not be added in the selection
312 return validTxs, l1CoordinatorTxs, positionL1, tracerr.Wrap(fmt.Errorf("invalid L2Tx: ToIdx not found in StateDB, neither ToEthAddr found in AccountCreationAuths L2DB. ToIdx: %d, ToEthAddr: %s",
313 l2Tx.ToIdx, l2Tx.ToEthAddr))
314 }
315 validTxs = append(validTxs, l2Tx)
316 }
317 // create L1CoordinatorTx for the accountCreation
318 l1CoordinatorTx := common.L1Tx{
319 Position: positionL1,
320 UserOrigin: false,
321 FromEthAddr: accAuth.EthAddr,
322 FromBJJ: accAuth.BJJ,
323 TokenID: l2Tx.TokenID,
324 DepositAmount: big.NewInt(0),
325 Type: common.TxTypeCreateAccountDeposit,
326 }
327 positionL1++
328 l1CoordinatorTxs = append(l1CoordinatorTxs, l1CoordinatorTx)
329 } else if bytes.Equal(l2Tx.ToEthAddr.Bytes(), common.FFAddr.Bytes()) && l2Tx.ToBJJ != common.EmptyBJJComp {
330 // if idx exist for EthAddr&BJJ use it
331 _, err := txsel.localAccountsDB.GetIdxByEthAddrBJJ(l2Tx.ToEthAddr, l2Tx.ToBJJ,
332 l2Tx.TokenID)
333 if err == nil {
334 // account for ToEthAddr&ToBJJ already exist, (where ToEthAddr==0xff)
335 // there is no need to create a new one.
336 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
337 validTxs = append(validTxs, l2Tx)
338 return validTxs, l1CoordinatorTxs, positionL1, nil
339 }
340 // if idx don't exist for EthAddr&BJJ,
341 // coordinator can create a new account without
342 // L1Authorization, as ToEthAddr==0xff
343 // create L1CoordinatorTx for the accountCreation
344 l1CoordinatorTx := common.L1Tx{
345 Position: positionL1,
346 UserOrigin: false,
347 FromEthAddr: l2Tx.ToEthAddr,
348 FromBJJ: l2Tx.ToBJJ,
349 TokenID: l2Tx.TokenID,
350 DepositAmount: big.NewInt(0),
351 Type: common.TxTypeCreateAccountDeposit,
352 }
353 positionL1++
354 l1CoordinatorTxs = append(l1CoordinatorTxs, l1CoordinatorTx)
355 }
356
357 return validTxs, l1CoordinatorTxs, positionL1, nil
358}
359
360func checkAlreadyPendingToCreate(l1CoordinatorTxs []common.L1Tx,
361 addr ethCommon.Address, bjj babyjub.PublicKeyComp) bool {
362 for i := 0; i < len(l1CoordinatorTxs); i++ {
363 if bytes.Equal(l1CoordinatorTxs[i].FromEthAddr.Bytes(), addr.Bytes()) {
364 if bjj == common.EmptyBJJComp {
365 return true
366 }
367 if l1CoordinatorTxs[i].FromBJJ == bjj {
368 return true
369 }
370 }
371 }
372 return false
373}
374
375// getL2Profitable returns the profitable selection of L2Txssorted by Nonce
376func (txsel *TxSelector) getL2Profitable(txs txs, max uint32) txs {
377 sort.Sort(txs)
378 if len(txs) < int(max) {
379 return txs
380 }
381 txs = txs[:max]
382
383 // sort l2Txs by Nonce. This can be done in many different ways, what
384 // is needed is to output the txs where the Nonce of txs for each
385 // Account is sorted, but the txs can not be grouped by sender Account
386 // neither by Fee. This is because later on the Nonces will need to be
387 // sequential for the zkproof generation.
388 sort.SliceStable(txs, func(i, j int) bool {
389 return txs[i].Nonce < txs[j].Nonce
390 })
391
392 return txs
393}