hermez-node/txselector/txselector.go
txselector/txselector.goRaw
1package txselector
2
3// current: very simple version of TxSelector
4
5import (
6 "bytes"
7 "math/big"
8 "sort"
9
10 ethCommon "github.com/ethereum/go-ethereum/common"
11 "github.com/hermeznetwork/hermez-node/common"
12 "github.com/hermeznetwork/hermez-node/db/l2db"
13 "github.com/hermeznetwork/hermez-node/db/statedb"
14 "github.com/hermeznetwork/hermez-node/log"
15 "github.com/iden3/go-iden3-crypto/babyjub"
16)
17
18// txs implements the interface Sort for an array of Tx
19type txs []common.PoolL2Tx
20
21func (t txs) Len() int {
22 return len(t)
23}
24func (t txs) Swap(i, j int) {
25 t[i], t[j] = t[j], t[i]
26}
27func (t txs) Less(i, j int) bool {
28 return t[i].AbsoluteFee > t[j].AbsoluteFee
29}
30
31// TxSelector implements all the functionalities to select the txs for the next batch
32type TxSelector struct {
33 // MaxL1UserTxs is the maximum L1-user-tx for a batch
34 MaxL1UserTxs uint64
35 // MaxL1OperatorTxs is the maximum L1-operator-tx for a batch
36 MaxL1OperatorTxs uint64
37 // MaxTxs is the maximum txs for a batch
38 MaxTxs uint64
39
40 l2db *l2db.L2DB
41 localAccountsDB *statedb.LocalStateDB
42}
43
44// NewTxSelector returns a *TxSelector
45func NewTxSelector(dbpath string, synchronizerStateDB *statedb.StateDB, l2 *l2db.L2DB, maxL1UserTxs, maxL1OperatorTxs, maxTxs uint64) (*TxSelector, error) {
46 localAccountsDB, err := statedb.NewLocalStateDB(dbpath, synchronizerStateDB, statedb.TypeTxSelector, 0) // without merkletree
47 if err != nil {
48 return nil, err
49 }
50
51 return &TxSelector{
52 MaxL1UserTxs: maxL1UserTxs,
53 MaxL1OperatorTxs: maxL1OperatorTxs,
54 MaxTxs: maxTxs,
55 l2db: l2,
56 localAccountsDB: localAccountsDB,
57 }, nil
58}
59
60// Reset tells the TxSelector to get it's internal AccountsDB
61// from the required `batchNum`
62func (txsel *TxSelector) Reset(batchNum common.BatchNum) error {
63 err := txsel.localAccountsDB.Reset(batchNum, true)
64 if err != nil {
65 return err
66 }
67 return nil
68}
69
70// GetL2TxSelection returns the L1CoordinatorTxs and a selection of the L2Txs
71// for the next batch, from the L2DB pool
72func (txsel *TxSelector) GetL2TxSelection(coordIdxs []common.Idx, batchNum common.BatchNum) ([]common.L1Tx, []common.PoolL2Tx, error) {
73 _, l1CoordinatorTxs, l2Txs, err := txsel.GetL1L2TxSelection(coordIdxs, batchNum, []common.L1Tx{})
74 return l1CoordinatorTxs, l2Txs, err
75}
76
77// GetL1L2TxSelection returns the selection of L1 + L2 txs
78func (txsel *TxSelector) GetL1L2TxSelection(coordIdxs []common.Idx, batchNum common.BatchNum, l1Txs []common.L1Tx) ([]common.L1Tx, []common.L1Tx, []common.PoolL2Tx, error) {
79 // apply l1-user-tx to localAccountDB
80 // create new leaves
81 // update balances
82 // update nonces
83
84 // get pending l2-tx from tx-pool
85 l2TxsRaw, err := txsel.l2db.GetPendingTxs() // (batchID)
86 if err != nil {
87 return nil, nil, nil, err
88 }
89
90 var validTxs txs
91 var l1CoordinatorTxs []common.L1Tx
92 positionL1 := len(l1Txs)
93
94 // if tx.ToIdx>=256, tx.ToIdx should exist to localAccountsDB, if so,
95 // tx is used. if tx.ToIdx==0, check if tx.ToEthAddr/tx.ToBJJ exist in
96 // localAccountsDB, if yes tx is used; if not, check if tx.ToEthAddr is
97 // in AccountCreationAuthDB, if so, tx is used and L1CoordinatorTx of
98 // CreateAccountAndDeposit is created.
99 for i := 0; i < len(l2TxsRaw); i++ {
100 if l2TxsRaw[i].ToIdx == 0 {
101 if checkAlreadyPendingToCreate(l1CoordinatorTxs, l2TxsRaw[i].ToEthAddr, l2TxsRaw[i].ToBJJ) {
102 // if L2Tx needs a new L1CoordinatorTx of CreateAccount type,
103 // and a previous L2Tx in the current process already created
104 // a L1CoordinatorTx of this type, in the DB there still seem
105 // that needs to create a new L1CoordinatorTx, but as is already
106 // created, the tx is valid
107 validTxs = append(validTxs, l2TxsRaw[i])
108 continue
109 }
110
111 if !bytes.Equal(l2TxsRaw[i].ToEthAddr.Bytes(), common.EmptyAddr.Bytes()) &&
112 !bytes.Equal(l2TxsRaw[i].ToEthAddr.Bytes(), common.FFAddr.Bytes()) {
113 // case: ToEthAddr != 0x00 neither 0xff
114 var accAuth *common.AccountCreationAuth
115 if l2TxsRaw[i].ToBJJ != nil {
116 // case: ToBJJ!=0:
117 // if idx exist for EthAddr&BJJ use it
118 _, err := txsel.localAccountsDB.GetIdxByEthAddrBJJ(l2TxsRaw[i].ToEthAddr, l2TxsRaw[i].ToBJJ, l2TxsRaw[i].TokenID)
119 if err == nil {
120 // account for ToEthAddr&ToBJJ already exist,
121 // there is no need to create a new one.
122 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
123 validTxs = append(validTxs, l2TxsRaw[i])
124 continue
125 }
126 // if not, check if AccountCreationAuth exist for that ToEthAddr&BJJ
127 // accAuth, err = txsel.l2db.GetAccountCreationAuthBJJ(l2TxsRaw[i].ToEthAddr, l2TxsRaw[i].ToBJJ)
128 accAuth, err = txsel.l2db.GetAccountCreationAuth(l2TxsRaw[i].ToEthAddr)
129 if err != nil {
130 // not found, l2Tx will not be added in the selection
131 log.Debugw("invalid L2Tx: ToIdx not found in StateDB, neither ToEthAddr & ToBJJ found in AccountCreationAuths L2DB", "ToIdx", l2TxsRaw[i].ToIdx, "ToEthAddr", l2TxsRaw[i].ToEthAddr)
132 continue
133 }
134 if accAuth.BJJ != l2TxsRaw[i].ToBJJ {
135 // if AccountCreationAuth.BJJ is not the same than in the tx, tx is not accepted
136 log.Debugw("invalid L2Tx: ToIdx not found in StateDB, neither ToEthAddr & ToBJJ found in AccountCreationAuths L2DB", "ToIdx", l2TxsRaw[i].ToIdx, "ToEthAddr", l2TxsRaw[i].ToEthAddr, "ToBJJ", l2TxsRaw[i].ToBJJ)
137 continue
138 }
139 validTxs = append(validTxs, l2TxsRaw[i])
140 } else {
141 // case: ToBJJ==0:
142 // if idx exist for EthAddr use it
143 _, err := txsel.localAccountsDB.GetIdxByEthAddr(l2TxsRaw[i].ToEthAddr, l2TxsRaw[i].TokenID)
144 if err == nil {
145 // account for ToEthAddr already exist,
146 // there is no need to create a new one.
147 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
148 validTxs = append(validTxs, l2TxsRaw[i])
149 continue
150 }
151 // if not, check if AccountCreationAuth exist for that ToEthAddr
152 accAuth, err = txsel.l2db.GetAccountCreationAuth(l2TxsRaw[i].ToEthAddr)
153 if err != nil {
154 // not found, l2Tx will not be added in the selection
155 log.Debugw("invalid L2Tx: ToIdx not found in StateDB, neither ToEthAddr found in AccountCreationAuths L2DB", "ToIdx", l2TxsRaw[i].ToIdx, "ToEthAddr", l2TxsRaw[i].ToEthAddr)
156 continue
157 }
158 validTxs = append(validTxs, l2TxsRaw[i])
159 }
160 // create L1CoordinatorTx for the accountCreation
161 l1CoordinatorTx := common.L1Tx{
162 Position: positionL1,
163 UserOrigin: false,
164 FromEthAddr: accAuth.EthAddr,
165 FromBJJ: accAuth.BJJ,
166 TokenID: l2TxsRaw[i].TokenID,
167 LoadAmount: big.NewInt(0),
168 Type: common.TxTypeCreateAccountDeposit,
169 }
170 positionL1++
171 l1CoordinatorTxs = append(l1CoordinatorTxs, l1CoordinatorTx)
172 } else if bytes.Equal(l2TxsRaw[i].ToEthAddr.Bytes(), common.FFAddr.Bytes()) && l2TxsRaw[i].ToBJJ != nil {
173 // if idx exist for EthAddr&BJJ use it
174 _, err := txsel.localAccountsDB.GetIdxByEthAddrBJJ(l2TxsRaw[i].ToEthAddr, l2TxsRaw[i].ToBJJ, l2TxsRaw[i].TokenID)
175 if err == nil {
176 // account for ToEthAddr&ToBJJ already exist, (where ToEthAddr==0xff)
177 // there is no need to create a new one.
178 // tx valid, StateDB will use the ToIdx==0 to define the AuxToIdx
179 validTxs = append(validTxs, l2TxsRaw[i])
180 continue
181 }
182 // if idx don't exist for EthAddr&BJJ,
183 // coordinator can create a new account without
184 // L1Authorization, as ToEthAddr==0xff
185 // create L1CoordinatorTx for the accountCreation
186 l1CoordinatorTx := common.L1Tx{
187 Position: positionL1,
188 UserOrigin: false,
189 FromEthAddr: l2TxsRaw[i].ToEthAddr,
190 FromBJJ: l2TxsRaw[i].ToBJJ,
191 TokenID: l2TxsRaw[i].TokenID,
192 LoadAmount: big.NewInt(0),
193 Type: common.TxTypeCreateAccountDeposit,
194 }
195 positionL1++
196 l1CoordinatorTxs = append(l1CoordinatorTxs, l1CoordinatorTx)
197 }
198 } else if l2TxsRaw[i].ToIdx >= common.IdxUserThreshold {
199 _, err = txsel.localAccountsDB.GetAccount(l2TxsRaw[i].ToIdx)
200 if err != nil {
201 // tx not valid
202 log.Debugw("invalid L2Tx: ToIdx not found in StateDB", "ToIdx", l2TxsRaw[i].ToIdx)
203 continue
204 }
205 // Account found in the DB, include the l2Tx in the selection
206 validTxs = append(validTxs, l2TxsRaw[i])
207 } else if l2TxsRaw[i].ToIdx == common.Idx(1) {
208 // valid txs (of Exit type)
209 validTxs = append(validTxs, l2TxsRaw[i])
210 }
211 }
212
213 // get most profitable L2-tx
214 maxL2Txs := txsel.MaxTxs - uint64(len(l1CoordinatorTxs)) // - len(l1UserTxs)
215 l2Txs := txsel.getL2Profitable(validTxs, maxL2Txs)
216
217 // process the txs in the local AccountsDB
218 _, err = txsel.localAccountsDB.ProcessTxs(coordIdxs, l1Txs, l1CoordinatorTxs, l2Txs)
219 if err != nil {
220 return nil, nil, nil, err
221 }
222 err = txsel.localAccountsDB.MakeCheckpoint()
223 if err != nil {
224 return nil, nil, nil, err
225 }
226
227 return l1Txs, l1CoordinatorTxs, l2Txs, nil
228}
229
230func checkAlreadyPendingToCreate(l1CoordinatorTxs []common.L1Tx, addr ethCommon.Address, bjj *babyjub.PublicKey) bool {
231 for i := 0; i < len(l1CoordinatorTxs); i++ {
232 if bytes.Equal(l1CoordinatorTxs[i].FromEthAddr.Bytes(), addr.Bytes()) {
233 if bjj == nil {
234 return true
235 }
236 if l1CoordinatorTxs[i].FromBJJ == bjj {
237 return true
238 }
239 }
240 }
241 return false
242}
243
244// getL2Profitable returns the profitable selection of L2Txssorted by Nonce
245func (txsel *TxSelector) getL2Profitable(txs txs, max uint64) txs {
246 sort.Sort(txs)
247 if len(txs) < int(max) {
248 return txs
249 }
250 txs = txs[:max]
251
252 // sort l2Txs by Nonce. This can be done in many different ways, what
253 // is needed is to output the txs where the Nonce of txs for each
254 // Account is sorted, but the txs can not be grouped by sender Account
255 // neither by Fee. This is because later on the Nonces will need to be
256 // sequential for the zkproof generation.
257 sort.SliceStable(txs, func(i, j int) bool {
258 return txs[i].Nonce < txs[j].Nonce
259 })
260
261 return txs
262}