From c067f8b50973a5bb84223b670e31443854470098 Mon Sep 17 00:00:00 2001 From: Poseidon Date: Fri, 6 Dec 2019 20:45:40 +0800 Subject: [PATCH] Fix mov issue (#462) * fix mov infinite loop * validate equals trade pair * cycle match * fix ci --- application/mov/match/match.go | 26 ++-- application/mov/match/match_test.go | 150 ++++++++++++++++++--- .../mov/match/{order_table.go => order_book.go} | 20 +-- .../{order_table_test.go => order_book_test.go} | 10 +- application/mov/mock/mock.go | 84 ++++++++++++ application/mov/mov_core.go | 12 +- 6 files changed, 253 insertions(+), 49 deletions(-) rename application/mov/match/{order_table.go => order_book.go} (84%) rename application/mov/match/{order_table_test.go => order_book_test.go} (95%) diff --git a/application/mov/match/match.go b/application/mov/match/match.go index db5a2c58..f506cf70 100644 --- a/application/mov/match/match.go +++ b/application/mov/match/match.go @@ -18,14 +18,14 @@ import ( // Engine is used to generate math transactions type Engine struct { - orderTable *OrderTable + orderBook *OrderBook maxFeeRate float64 nodeProgram []byte } // NewEngine return a new Engine -func NewEngine(orderTable *OrderTable, maxFeeRate float64, nodeProgram []byte) *Engine { - return &Engine{orderTable: orderTable, maxFeeRate: maxFeeRate, nodeProgram: nodeProgram} +func NewEngine(orderBook *OrderBook, maxFeeRate float64, nodeProgram []byte) *Engine { + return &Engine{orderBook: orderBook, maxFeeRate: maxFeeRate, nodeProgram: nodeProgram} } // HasMatchedTx check does the input trade pair can generate a match deal @@ -56,7 +56,7 @@ func (e *Engine) NextMatchedTx(tradePairs ...*common.TradePair) (*types.Tx, erro } for _, tradePair := range tradePairs { - e.orderTable.PopOrder(tradePair) + e.orderBook.PopOrder(tradePair) } if err := e.addPartialTradeOrder(tx); err != nil { @@ -113,7 +113,7 @@ func (e *Engine) addPartialTradeOrder(tx *types.Tx) error { return err } - if err := e.orderTable.AddOrder(order); err != nil { + if err := e.orderBook.AddOrder(order); err != nil { return err } } @@ -148,7 +148,7 @@ func (e *Engine) buildMatchTx(orders []*common.Order) (*types.Tx, error) { func (e *Engine) peekOrders(tradePairs []*common.TradePair) []*common.Order { var orders []*common.Order for _, tradePair := range tradePairs { - order := e.orderTable.PeekOrder(tradePair) + order := e.orderBook.PeekOrder(tradePair) if order == nil { return nil } @@ -248,12 +248,12 @@ func calcOppositeIndex(size int, selfIdx int) int { } func isMatched(orders []*common.Order) bool { - for i, order := range orders { - if oppositeOrder := orders[calcOppositeIndex(len(orders), i)]; 1/order.Rate < oppositeOrder.Rate { - return false - } + rate := orders[0].Rate + oppositeRate := 1.0 + for i := 1; i < len(orders); i++ { + oppositeRate *= orders[i].Rate } - return true + return 1/rate >= oppositeRate } func setMatchTxArguments(txInput *types.TxInput, isPartialTrade bool, position int, receiveAmounts uint64) { @@ -272,6 +272,10 @@ func validateTradePairs(tradePairs []*common.TradePair) error { } for i, tradePair := range tradePairs { + if *tradePair.FromAssetID == *tradePair.ToAssetID { + return errors.New("from asset id can't equal to asset id") + } + oppositeTradePair := tradePairs[calcOppositeIndex(len(tradePairs), i)] if *tradePair.ToAssetID != *oppositeTradePair.FromAssetID { return errors.New("specified trade pairs is invalid") diff --git a/application/mov/match/match_test.go b/application/mov/match/match_test.go index 880ab4f9..a73e62d4 100644 --- a/application/mov/match/match_test.go +++ b/application/mov/match/match_test.go @@ -3,29 +3,29 @@ package match import ( "testing" - "github.com/bytom/vapor/protocol/bc" - "github.com/bytom/vapor/testutil" "github.com/bytom/vapor/application/mov/common" "github.com/bytom/vapor/application/mov/mock" + "github.com/bytom/vapor/protocol/bc" "github.com/bytom/vapor/protocol/bc/types" + "github.com/bytom/vapor/protocol/validation" + "github.com/bytom/vapor/testutil" ) -/* - Test: validateTradePairs vaild and invaild case for 2, 3 trade pairs -*/ func TestGenerateMatchedTxs(t *testing.T) { btc2eth := &common.TradePair{FromAssetID: &mock.BTC, ToAssetID: &mock.ETH} eth2btc := &common.TradePair{FromAssetID: &mock.ETH, ToAssetID: &mock.BTC} + eth2eos := &common.TradePair{FromAssetID: &mock.ETH, ToAssetID: &mock.EOS} + eos2btc := &common.TradePair{FromAssetID: &mock.EOS, ToAssetID: &mock.BTC} cases := []struct { desc string - tradePair *common.TradePair + tradePairs []*common.TradePair initStoreOrders []*common.Order wantMatchedTxs []*types.Tx }{ { - desc: "full matched", - tradePair: &common.TradePair{FromAssetID: &mock.BTC, ToAssetID: &mock.ETH}, + desc: "full matched", + tradePairs: []*common.TradePair{btc2eth, eth2btc}, initStoreOrders: []*common.Order{ mock.Btc2EthOrders[0], mock.Btc2EthOrders[1], mock.Eth2BtcOrders[0], @@ -35,8 +35,8 @@ func TestGenerateMatchedTxs(t *testing.T) { }, }, { - desc: "partial matched", - tradePair: &common.TradePair{FromAssetID: &mock.BTC, ToAssetID: &mock.ETH}, + desc: "partial matched", + tradePairs: []*common.TradePair{btc2eth, eth2btc}, initStoreOrders: []*common.Order{ mock.Btc2EthOrders[0], mock.Btc2EthOrders[1], mock.Eth2BtcOrders[1], @@ -46,8 +46,8 @@ func TestGenerateMatchedTxs(t *testing.T) { }, }, { - desc: "partial matched and continue to match", - tradePair: &common.TradePair{FromAssetID: &mock.BTC, ToAssetID: &mock.ETH}, + desc: "partial matched and continue to match", + tradePairs: []*common.TradePair{btc2eth, eth2btc}, initStoreOrders: []*common.Order{ mock.Btc2EthOrders[0], mock.Btc2EthOrders[1], mock.Eth2BtcOrders[2], @@ -58,22 +58,32 @@ func TestGenerateMatchedTxs(t *testing.T) { }, }, { - desc: "unable to match", - tradePair: &common.TradePair{FromAssetID: &mock.BTC, ToAssetID: &mock.ETH}, + desc: "unable to match", + tradePairs: []*common.TradePair{btc2eth, eth2btc}, initStoreOrders: []*common.Order{ mock.Btc2EthOrders[1], mock.Eth2BtcOrders[0], }, wantMatchedTxs: []*types.Tx{}, }, + { + desc: "cycle match", + tradePairs: []*common.TradePair{btc2eth, eth2eos, eos2btc}, + initStoreOrders: []*common.Order{ + mock.Btc2EthOrders[0], mock.Eth2EosOrders[0], mock.Eos2BtcOrders[0], + }, + wantMatchedTxs: []*types.Tx{ + mock.MatchedTxs[6], + }, + }, } for i, c := range cases { movStore := mock.NewMovStore([]*common.TradePair{btc2eth, eth2btc}, c.initStoreOrders) - matchEngine := NewEngine(NewOrderTable(movStore, nil, nil), 0.05, mock.NodeProgram) + matchEngine := NewEngine(NewOrderBook(movStore, nil, nil), 0.05, mock.NodeProgram) var gotMatchedTxs []*types.Tx - for matchEngine.HasMatchedTx(c.tradePair, c.tradePair.Reverse()) { - matchedTx, err := matchEngine.NextMatchedTx(c.tradePair, c.tradePair.Reverse()) + for matchEngine.HasMatchedTx(c.tradePairs...) { + matchedTx, err := matchEngine.NextMatchedTx(c.tradePairs...) if err != nil { t.Fatal(err) } @@ -87,6 +97,10 @@ func TestGenerateMatchedTxs(t *testing.T) { } for i, gotMatchedTx := range gotMatchedTxs { + if _, err := validation.ValidateTx(gotMatchedTx.Tx, &bc.Block{BlockHeader: &bc.BlockHeader{Version: 1}}); err != nil { + t.Fatal(err) + } + c.wantMatchedTxs[i].Version = 1 byteData, err := c.wantMatchedTxs[i].MarshalText() if err != nil { @@ -140,3 +154,105 @@ func TestCalcMatchedTxFee(t *testing.T) { } } } + +func TestValidateTradePairs(t *testing.T) { + cases := []struct { + desc string + tradePairs []*common.TradePair + wantError bool + }{ + { + desc: "valid case of two trade pairs", + tradePairs: []*common.TradePair{ + { + FromAssetID: &mock.BTC, + ToAssetID: &mock.ETH, + }, + { + FromAssetID: &mock.ETH, + ToAssetID: &mock.BTC, + }, + }, + wantError: false, + }, + { + desc: "invalid case of two trade pairs", + tradePairs: []*common.TradePair{ + { + FromAssetID: &mock.BTC, + ToAssetID: &mock.ETH, + }, + { + FromAssetID: &mock.ETH, + ToAssetID: &mock.EOS, + }, + }, + wantError: true, + }, + { + desc: "valid case of three trade pairs", + tradePairs: []*common.TradePair{ + { + FromAssetID: &mock.BTC, + ToAssetID: &mock.ETH, + }, + { + FromAssetID: &mock.ETH, + ToAssetID: &mock.EOS, + }, + { + FromAssetID: &mock.EOS, + ToAssetID: &mock.BTC, + }, + }, + wantError: false, + }, + { + desc: "invalid case of three trade pairs", + tradePairs: []*common.TradePair{ + { + FromAssetID: &mock.BTC, + ToAssetID: &mock.ETH, + }, + { + FromAssetID: &mock.ETH, + ToAssetID: &mock.BTC, + }, + { + FromAssetID: &mock.BTC, + ToAssetID: &mock.BTC, + }, + }, + wantError: true, + }, + { + desc: "invalid case 2 of three trade pairs", + tradePairs: []*common.TradePair{ + { + FromAssetID: &mock.BTC, + ToAssetID: &mock.ETH, + }, + { + FromAssetID: &mock.EOS, + ToAssetID: &mock.BTC, + }, + { + FromAssetID: &mock.ETH, + ToAssetID: &mock.EOS, + }, + }, + wantError: true, + }, + } + + for i, c := range cases { + err := validateTradePairs(c.tradePairs) + if c.wantError && err == nil { + t.Errorf("#%d(%s): want error, got no error", i, c.desc) + } + + if !c.wantError && err != nil { + t.Errorf("#%d(%s): want no error, got error (%v)", i, c.desc, err) + } + } +} diff --git a/application/mov/match/order_table.go b/application/mov/match/order_book.go similarity index 84% rename from application/mov/match/order_table.go rename to application/mov/match/order_book.go index 30b60560..ebfa27c5 100644 --- a/application/mov/match/order_table.go +++ b/application/mov/match/order_book.go @@ -8,8 +8,8 @@ import ( "github.com/bytom/vapor/errors" ) -// OrderTable is used to handle the mov orders in memory like stack -type OrderTable struct { +// OrderBook is used to handle the mov orders in memory like stack +type OrderBook struct { movStore database.MovStore // key of tradePair -> []order dbOrders map[string][]*common.Order @@ -22,9 +22,9 @@ type OrderTable struct { arrivalDelOrders map[string]*common.Order } -// NewOrderTable create a new OrderTable object -func NewOrderTable(movStore database.MovStore, arrivalAddOrders, arrivalDelOrders []*common.Order) *OrderTable { - return &OrderTable{ +// NewOrderBook create a new OrderBook object +func NewOrderBook(movStore database.MovStore, arrivalAddOrders, arrivalDelOrders []*common.Order) *OrderBook { + return &OrderBook{ movStore: movStore, dbOrders: make(map[string][]*common.Order), orderIterators: make(map[string]*database.OrderIterator), @@ -35,7 +35,7 @@ func NewOrderTable(movStore database.MovStore, arrivalAddOrders, arrivalDelOrder } // AddOrder add the in memory temp order to order table -func (o *OrderTable) AddOrder(order *common.Order) error { +func (o *OrderBook) AddOrder(order *common.Order) error { tradePairKey := order.TradePair().Key() orders := o.arrivalAddOrders[tradePairKey] if len(orders) > 0 && order.Rate > orders[len(orders)-1].Rate { @@ -47,7 +47,7 @@ func (o *OrderTable) AddOrder(order *common.Order) error { } // PeekOrder return the next lowest order of given trade pair -func (o *OrderTable) PeekOrder(tradePair *common.TradePair) *common.Order { +func (o *OrderBook) PeekOrder(tradePair *common.TradePair) *common.Order { if len(o.dbOrders[tradePair.Key()]) == 0 { o.extendDBOrders(tradePair) } @@ -71,7 +71,7 @@ func (o *OrderTable) PeekOrder(tradePair *common.TradePair) *common.Order { } // PopOrder delete the next lowest order of given trade pair -func (o *OrderTable) PopOrder(tradePair *common.TradePair) { +func (o *OrderBook) PopOrder(tradePair *common.TradePair) { order := o.PeekOrder(tradePair) if order == nil { return @@ -108,7 +108,7 @@ func arrangeArrivalDelOrders(orders []*common.Order) map[string]*common.Order { return arrivalDelOrderMap } -func (o *OrderTable) extendDBOrders(tradePair *common.TradePair) { +func (o *OrderBook) extendDBOrders(tradePair *common.TradePair) { iterator, ok := o.orderIterators[tradePair.Key()] if !ok { iterator = database.NewOrderIterator(o.movStore, tradePair) @@ -121,7 +121,7 @@ func (o *OrderTable) extendDBOrders(tradePair *common.TradePair) { } } -func (o *OrderTable) peekArrivalOrder(tradePair *common.TradePair) *common.Order { +func (o *OrderBook) peekArrivalOrder(tradePair *common.TradePair) *common.Order { if arrivalAddOrders := o.arrivalAddOrders[tradePair.Key()]; len(arrivalAddOrders) > 0 { return arrivalAddOrders[len(arrivalAddOrders)-1] } diff --git a/application/mov/match/order_table_test.go b/application/mov/match/order_book_test.go similarity index 95% rename from application/mov/match/order_table_test.go rename to application/mov/match/order_book_test.go index 2f9582ab..e4019702 100644 --- a/application/mov/match/order_table_test.go +++ b/application/mov/match/order_book_test.go @@ -12,7 +12,7 @@ var ( btc2eth = &common.TradePair{FromAssetID: &mock.BTC, ToAssetID: &mock.ETH} ) -func TestOrderTable(t *testing.T) { +func TestOrderBook(t *testing.T) { cases := []struct { desc string initMovStore database.MovStore @@ -170,19 +170,19 @@ func TestOrderTable(t *testing.T) { } for i, c := range cases { - orderTable := NewOrderTable(c.initMovStore, c.initArrivalAddOrders, c.initArrivalDelOrders) + orderBook := NewOrderBook(c.initMovStore, c.initArrivalAddOrders, c.initArrivalDelOrders) for _, order := range c.addOrders { - if err := orderTable.AddOrder(order); err != nil { + if err := orderBook.AddOrder(order); err != nil { t.Fatal(err) } } for _, tradePair := range c.popOrders { - orderTable.PopOrder(tradePair) + orderBook.PopOrder(tradePair) } for tradePair, wantOrder := range c.wantPeekedOrders { - gotOrder := orderTable.PeekOrder(&tradePair) + gotOrder := orderBook.PeekOrder(&tradePair) if wantOrder == gotOrder && wantOrder == nil { continue } diff --git a/application/mov/mock/mock.go b/application/mov/mock/mock.go index 8a918a89..cb648e9c 100644 --- a/application/mov/mock/mock.go +++ b/application/mov/mock/mock.go @@ -12,6 +12,8 @@ import ( var ( BTC = bc.NewAssetID([32]byte{1}) ETH = bc.NewAssetID([32]byte{2}) + EOS = bc.NewAssetID([32]byte{3}) + ETC = bc.NewAssetID([32]byte{4}) NodeProgram = []byte{0x58} Btc2EthOrders = []*common.Order{ @@ -97,6 +99,62 @@ var ( }, } + Eos2EtcOrders = []*common.Order{ + { + FromAssetID: &EOS, + ToAssetID: &ETC, + Rate: 1 / 2.0, + Utxo: &common.MovUtxo{ + SourceID: hashPtr(testutil.MustDecodeHash("119a02980796dc352cf6475457463aef5666f66622088de3551fa73a65f0d202")), + SourcePos: 0, + Amount: 100, + ControlProgram: MustCreateP2WMCProgram(ETC, testutil.MustDecodeHexString("0014f928b723999312df4ed51cb275a2644336c19255"), 1, 2.0), + }, + }, + } + + Etc2EosOrders = []*common.Order{ + { + FromAssetID: &ETC, + ToAssetID: &EOS, + Rate: 2.0, + Utxo: &common.MovUtxo{ + SourceID: hashPtr(testutil.MustDecodeHash("119a02980796dc352cf6475457463aef5666f66622088de3551fa73a65f0d203")), + SourcePos: 0, + Amount: 50, + ControlProgram: MustCreateP2WMCProgram(EOS, testutil.MustDecodeHexString("0014df7a97e53bbe278e4e44810b0a760fb472daa9a3"), 2, 1.0), + }, + }, + } + + Eth2EosOrders = []*common.Order{ + { + FromAssetID: Ð, + ToAssetID: &EOS, + Rate: 2.0, + Utxo: &common.MovUtxo{ + SourceID: hashPtr(testutil.MustDecodeHash("c1502d03946e4ea92abdb33f51638b181839bd0d8767acc2ee5c665b659c4b13")), + SourcePos: 0, + Amount: 500, + ControlProgram: MustCreateP2WMCProgram(EOS, testutil.MustDecodeHexString("0014e3178c0f294a9a8f4b304236406507913091df86"), 2, 1.0), + }, + }, + } + + Eos2BtcOrders = []*common.Order{ + { + FromAssetID: &EOS, + ToAssetID: &BTC, + Rate: 1 / 100.0, + Utxo: &common.MovUtxo{ + SourceID: hashPtr(testutil.MustDecodeHash("27cf8a0877dc858968cc06396fe6aa9e02d15f3e44c862fe29fa5fd50497cf20")), + SourcePos: 0, + Amount: 1000, + ControlProgram: MustCreateP2WMCProgram(BTC, testutil.MustDecodeHexString("00144d0dfc8a0c5ce41d31d4f61d99aff70588bff8bc"), 1, 100.0), + }, + }, + } + Btc2EthMakerTxs = []*types.Tx{ // Btc2EthOrders[0] types.NewTx(types.TxData{ @@ -210,6 +268,32 @@ var ( types.NewIntraChainOutput(*Eth2BtcOrders[1].ToAssetID, 8, testutil.MustDecodeHexString("0014f928b723999312df4ed51cb275a2644336c19254")), }, }), + + // full matched transaction from Btc2Eth Eth2Eos Eos2Btc + types.NewTx(types.TxData{ + Inputs: []*types.TxInput{ + types.NewSpendInput([][]byte{vm.Int64Bytes(0), vm.Int64Bytes(1)}, *Eos2EtcOrders[0].Utxo.SourceID, *Eos2EtcOrders[0].FromAssetID, Eos2EtcOrders[0].Utxo.Amount, Eos2EtcOrders[0].Utxo.SourcePos, Eos2EtcOrders[0].Utxo.ControlProgram), + types.NewSpendInput([][]byte{vm.Int64Bytes(1), vm.Int64Bytes(1)}, *Etc2EosOrders[0].Utxo.SourceID, *Etc2EosOrders[0].FromAssetID, Etc2EosOrders[0].Utxo.Amount, Etc2EosOrders[0].Utxo.SourcePos, Etc2EosOrders[0].Utxo.ControlProgram), + }, + Outputs: []*types.TxOutput{ + types.NewIntraChainOutput(*Eos2EtcOrders[0].ToAssetID, 50, testutil.MustDecodeHexString("0014f928b723999312df4ed51cb275a2644336c19255")), + types.NewIntraChainOutput(*Etc2EosOrders[0].ToAssetID, 100, testutil.MustDecodeHexString("0014df7a97e53bbe278e4e44810b0a760fb472daa9a3")), + }, + }), + + // cycle matched + types.NewTx(types.TxData{ + Inputs: []*types.TxInput{ + types.NewSpendInput([][]byte{vm.Int64Bytes(0), vm.Int64Bytes(1)}, *Btc2EthOrders[0].Utxo.SourceID, *Btc2EthOrders[0].FromAssetID, Btc2EthOrders[0].Utxo.Amount, Btc2EthOrders[0].Utxo.SourcePos, Btc2EthOrders[0].Utxo.ControlProgram), + types.NewSpendInput([][]byte{vm.Int64Bytes(1), vm.Int64Bytes(1)}, *Eth2EosOrders[0].Utxo.SourceID, *Eth2EosOrders[0].FromAssetID, Eth2EosOrders[0].Utxo.Amount, Eth2EosOrders[0].Utxo.SourcePos, Eth2EosOrders[0].Utxo.ControlProgram), + types.NewSpendInput([][]byte{vm.Int64Bytes(2), vm.Int64Bytes(1)}, *Eos2BtcOrders[0].Utxo.SourceID, *Eos2BtcOrders[0].FromAssetID, Eos2BtcOrders[0].Utxo.Amount, Eos2BtcOrders[0].Utxo.SourcePos, Eos2BtcOrders[0].Utxo.ControlProgram), + }, + Outputs: []*types.TxOutput{ + types.NewIntraChainOutput(ETH, 500, testutil.MustDecodeHexString("0014f928b723999312df4ed51cb275a2644336c19251")), + types.NewIntraChainOutput(EOS, 1000, testutil.MustDecodeHexString("0014e3178c0f294a9a8f4b304236406507913091df86")), + types.NewIntraChainOutput(BTC, 10, testutil.MustDecodeHexString("00144d0dfc8a0c5ce41d31d4f61d99aff70588bff8bc")), + }, + }), } ) diff --git a/application/mov/mov_core.go b/application/mov/mov_core.go index 0d503774..529f8aba 100644 --- a/application/mov/mov_core.go +++ b/application/mov/mov_core.go @@ -80,12 +80,12 @@ func (m *MovCore) BeforeProposalBlock(txs []*types.Tx, nodeProgram []byte, block return nil, nil } - orderTable, err := buildOrderTable(m.movStore, txs) + orderBook, err := buildOrderBook(m.movStore, txs) if err != nil { return nil, err } - matchEngine := match.NewEngine(orderTable, maxFeeRate, nodeProgram) + matchEngine := match.NewEngine(orderBook, maxFeeRate, nodeProgram) tradePairMap := make(map[string]bool) tradePairIterator := database.NewTradePairIterator(m.movStore) @@ -291,12 +291,12 @@ func validateMatchedTxFeeAmount(tx *types.Tx) error { @issue: the match package didn't support circle yet */ func (m *MovCore) validateMatchedTxSequence(txs []*types.Tx) error { - orderTable, err := buildOrderTable(m.movStore, txs) + orderBook, err := buildOrderBook(m.movStore, txs) if err != nil { return err } - matchEngine := match.NewEngine(orderTable, maxFeeRate, nil) + matchEngine := match.NewEngine(orderBook, maxFeeRate, nil) for _, matchedTx := range txs { if !common.IsMatchedTx(matchedTx) { continue @@ -370,7 +370,7 @@ func applyTransactions(txs []*types.Tx) ([]*common.Order, []*common.Order, error /* @issue: if consensus node packed match transaction first then packed regular tx, this function's logic may make a valid block invalid */ -func buildOrderTable(store database.MovStore, txs []*types.Tx) (*match.OrderTable, error) { +func buildOrderBook(store database.MovStore, txs []*types.Tx) (*match.OrderBook, error) { var nonMatchedTxs []*types.Tx for _, tx := range txs { if !common.IsMatchedTx(tx) { @@ -394,7 +394,7 @@ func buildOrderTable(store database.MovStore, txs []*types.Tx) (*match.OrderTabl arrivalDelOrders = append(arrivalDelOrders, delOrders...) } - return match.NewOrderTable(store, arrivalAddOrders, arrivalDelOrders), nil + return match.NewOrderBook(store, arrivalAddOrders, arrivalDelOrders), nil } func calcMatchedTxGasUsed(tx *types.Tx) int64 { -- 2.11.0