application/mov/match/engine.go

   1 package match
   2
   3 import (
   4         "math/big"
   5
   6         "github.com/bytom/vapor/application/mov/common"
   7         "github.com/bytom/vapor/application/mov/contract"
   8         "github.com/bytom/vapor/consensus/segwit"
   9         "github.com/bytom/vapor/errors"
  10         vprMath "github.com/bytom/vapor/math"
  11         "github.com/bytom/vapor/protocol/bc"
  12         "github.com/bytom/vapor/protocol/bc/types"
  13         "github.com/bytom/vapor/protocol/vm"
  14 )
  15
  16 // Engine is used to generate math transactions
  17 type Engine struct {
  18         orderBook     *OrderBook
  19         feeStrategy   FeeStrategy
  20         rewardProgram []byte
  21 }
  22
  23 type orderPosition struct {
  24         blockHeight uint64
  25         txIndex     uint64
  26 }
  27
  28 // NewEngine return a new Engine
  29 func NewEngine(orderBook *OrderBook, rewardProgram []byte) *Engine {
  30         return &Engine{orderBook: orderBook, feeStrategy: NewDefaultFeeStrategy(), rewardProgram: rewardProgram}
  31 }
  32
  33 // HasMatchedTx check does the input trade pair can generate a match deal
  34 func (e *Engine) HasMatchedTx(tradePairs ...*common.TradePair) bool {
  35         if err := validateTradePairs(tradePairs); err != nil {
  36                 return false
  37         }
  38
  39         orders := e.orderBook.PeekOrders(tradePairs)
  40         if len(orders) == 0 {
  41                 return false
  42         }
  43
  44         return IsMatched(orders)
  45 }
  46
  47 // NextMatchedTx return the next matchable transaction by the specified trade pairs
  48 // the size of trade pairs at least 2, and the sequence of trade pairs can form a loop
  49 // for example, [assetA -> assetB, assetB -> assetC, assetC -> assetA]
  50 func (e *Engine) NextMatchedTx(tradePairs ...*common.TradePair) (*types.Tx, error) {
  51         if !e.HasMatchedTx(tradePairs...) {
  52                 return nil, errors.New("the specified trade pairs can not be matched")
  53         }
  54
  55         tx, partialOrderPositions, err := e.buildMatchTx(sortOrders(e.orderBook.PeekOrders(tradePairs)))
  56         if err != nil {
  57                 return nil, err
  58         }
  59
  60         for _, tradePair := range tradePairs {
  61                 e.orderBook.PopOrder(tradePair)
  62         }
  63
  64         if err := e.addReOrder(tx, partialOrderPositions); err != nil {
  65                 return nil, err
  66         }
  67         return tx, nil
  68 }
  69
  70 func addMatchTxFeeOutput(txData *types.TxData, fees []*bc.AssetAmount, rewardProgram []byte) {
  71         for _, feeAmount := range fees {
  72                 txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*feeAmount.AssetId, feeAmount.Amount, rewardProgram))
  73         }
  74 }
  75
  76 func (e *Engine) addReOrder(tx *types.Tx, partialOrderPositions []*orderPosition) error {
  77         index := 0
  78         for i, output := range tx.Outputs {
  79                 if !segwit.IsP2WMCScript(output.ControlProgram()) || output.AssetAmount().Amount == 0 {
  80                         continue
  81                 }
  82
  83                 partialOrderPos := partialOrderPositions[index]
  84                 order, err := common.NewOrderFromOutput(tx, i, partialOrderPos.blockHeight, partialOrderPos.txIndex)
  85                 if err != nil {
  86                         return err
  87                 }
  88
  89                 index++
  90                 e.orderBook.AddOrder(order)
  91         }
  92         return nil
  93 }
  94
  95 func addRefundOutput(txData *types.TxData, takerProgram []byte) {
  96         refundAmount := map[bc.AssetID]uint64{}
  97         for _, input := range txData.Inputs {
  98                 refundAmount[input.AssetID()] += input.Amount()
  99         }
 100
 101         for _, output := range txData.Outputs {
 102                 assetAmount := output.AssetAmount()
 103                 refundAmount[*assetAmount.AssetId] -= assetAmount.Amount
 104         }
 105
 106         for assetID, amount := range refundAmount {
 107                 if amount != 0 {
 108                         txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(assetID, amount, takerProgram))
 109                 }
 110         }
 111 }
 112
 113 func (e *Engine) buildMatchTx(orders []*common.Order) (*types.Tx, []*orderPosition, error) {
 114         txData := &types.TxData{Version: 1}
 115         for _, order := range orders {
 116                 input := types.NewSpendInput(nil, *order.Utxo.SourceID, *order.FromAssetID, order.Utxo.Amount, order.Utxo.SourcePos, order.Utxo.ControlProgram)
 117                 txData.Inputs = append(txData.Inputs, input)
 118         }
 119
 120         takerPos := takerPos(orders)
 121         receivedAmounts, priceDiffs := CalcReceivedAmount(orders)
 122         allocatedAssets := e.feeStrategy.Allocate(receivedAmounts, priceDiffs, takerPos)
 123
 124         partialOrderPositions, err := addMatchTxOutput(txData, orders, receivedAmounts, allocatedAssets)
 125         if err != nil {
 126                 return nil, nil, err
 127         }
 128
 129         addMatchTxFeeOutput(txData, allocatedAssets.Fees, e.rewardProgram)
 130         addRefundOutput(txData, orders[takerPos].SellerProgram)
 131
 132         byteData, err := txData.MarshalText()
 133         if err != nil {
 134                 return nil, nil, err
 135         }
 136
 137         txData.SerializedSize = uint64(len(byteData))
 138         return types.NewTx(*txData), partialOrderPositions, nil
 139 }
 140
 141 func addMatchTxOutput(txData *types.TxData, orders []*common.Order, receivedAmounts []*bc.AssetAmount, allocatedAssets *AllocatedAssets) ([]*orderPosition, error) {
 142         var partialOrderPositions []*orderPosition
 143         for i, order := range orders {
 144                 receivedAmount := receivedAmounts[i].Amount
 145                 shouldPayAmount := calcShouldPayAmount(receivedAmount, order.RatioNumerator, order.RatioDenominator)
 146
 147                 requestAmount := CalcRequestAmount(order.Utxo.Amount, order.RatioNumerator, order.RatioDenominator)
 148                 exchangeAmount := order.Utxo.Amount - shouldPayAmount
 149                 isPartialTrade := requestAmount > receivedAmount && CalcRequestAmount(exchangeAmount, order.RatioNumerator, order.RatioDenominator) >= 1
 150
 151                 setMatchTxArguments(txData.Inputs[i], isPartialTrade, len(txData.Outputs), receivedAmount)
 152
 153                 txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*order.ToAssetID, allocatedAssets.Receives[i].Amount, order.SellerProgram))
 154                 if isPartialTrade {
 155                         txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*order.FromAssetID, exchangeAmount, order.Utxo.ControlProgram))
 156                         partialOrderPositions = append(partialOrderPositions, &orderPosition{blockHeight: order.BlockHeight, txIndex: order.TxIndex})
 157                 }
 158         }
 159         return partialOrderPositions, nil
 160 }
 161
 162 func calcOppositeIndex(size int, selfIdx int) int {
 163         return (selfIdx + 1) % size
 164 }
 165
 166 // CalcRequestAmount is from amount * numerator / ratioDenominator
 167 func CalcRequestAmount(fromAmount uint64, ratioNumerator, ratioDenominator int64) uint64 {
 168         res := big.NewInt(0).SetUint64(fromAmount)
 169         res.Mul(res, big.NewInt(ratioNumerator)).Quo(res, big.NewInt(ratioDenominator))
 170         if !res.IsUint64() {
 171                 return 0
 172         }
 173         return res.Uint64()
 174 }
 175
 176 func calcShouldPayAmount(receiveAmount uint64, ratioNumerator, ratioDenominator int64) uint64 {
 177         res := big.NewInt(0).SetUint64(receiveAmount)
 178         res.Mul(res, big.NewInt(ratioDenominator)).Quo(res, big.NewInt(ratioNumerator))
 179         if !res.IsUint64() {
 180                 return 0
 181         }
 182         return res.Uint64()
 183 }
 184
 185 // CalcReceivedAmount return amount of assets received by each participant in the matching transaction and the price difference
 186 func CalcReceivedAmount(orders []*common.Order) ([]*bc.AssetAmount, []*bc.AssetAmount) {
 187         var receivedAmounts, priceDiffs, shouldPayAmounts []*bc.AssetAmount
 188         for i, order := range orders {
 189                 requestAmount := CalcRequestAmount(order.Utxo.Amount, order.RatioNumerator, order.RatioDenominator)
 190                 oppositeOrder := orders[calcOppositeIndex(len(orders), i)]
 191                 receiveAmount := vprMath.MinUint64(oppositeOrder.Utxo.Amount, requestAmount)
 192                 shouldPayAmount := calcShouldPayAmount(receiveAmount, order.RatioNumerator, order.RatioDenominator)
 193                 receivedAmounts = append(receivedAmounts, &bc.AssetAmount{AssetId: order.ToAssetID, Amount: receiveAmount})
 194                 shouldPayAmounts = append(shouldPayAmounts, &bc.AssetAmount{AssetId: order.FromAssetID, Amount: shouldPayAmount})
 195         }
 196
 197         for i, receivedAmount := range receivedAmounts {
 198                 oppositeShouldPayAmount := shouldPayAmounts[calcOppositeIndex(len(orders), i)]
 199                 priceDiffs = append(priceDiffs, &bc.AssetAmount{AssetId: oppositeShouldPayAmount.AssetId, Amount: 0})
 200                 if oppositeShouldPayAmount.Amount > receivedAmount.Amount {
 201                         priceDiffs[i].Amount = oppositeShouldPayAmount.Amount - receivedAmount.Amount
 202                 }
 203         }
 204         return receivedAmounts, priceDiffs
 205 }
 206
 207 // IsMatched check does the orders can be exchange
 208 func IsMatched(orders []*common.Order) bool {
 209         sortedOrders := sortOrders(orders)
 210         if len(sortedOrders) == 0 {
 211                 return false
 212         }
 213
 214         product := big.NewRat(1, 1)
 215         for _, order := range orders {
 216                 product.Mul(product, big.NewRat(order.RatioNumerator, order.RatioDenominator))
 217         }
 218         one := big.NewRat(1, 1)
 219         return product.Cmp(one) <= 0
 220 }
 221
 222 func takerPos(orders []*common.Order) int {
 223         for i, order := range orders {
 224                 if !isMaker(order, orders[calcOppositeIndex(len(orders), i)]) {
 225                         return i
 226                 }
 227         }
 228         return 0
 229 }
 230
 231 func isMaker(order, oppositeOrder *common.Order) bool {
 232         if order.BlockHeight != oppositeOrder.BlockHeight {
 233                 return order.BlockHeight < oppositeOrder.BlockHeight
 234         }
 235
 236         if order.TxIndex != oppositeOrder.TxIndex {
 237                 return order.TxIndex < oppositeOrder.TxIndex
 238         }
 239
 240         return order.UTXOHash().String() < oppositeOrder.UTXOHash().String()
 241 }
 242
 243 func setMatchTxArguments(txInput *types.TxInput, isPartialTrade bool, position int, receiveAmounts uint64) {
 244         var arguments [][]byte
 245         if isPartialTrade {
 246                 arguments = [][]byte{vm.Int64Bytes(int64(receiveAmounts)), vm.Int64Bytes(int64(position)), vm.Int64Bytes(contract.PartialTradeClauseSelector)}
 247         } else {
 248                 arguments = [][]byte{vm.Int64Bytes(int64(position)), vm.Int64Bytes(contract.FullTradeClauseSelector)}
 249         }
 250         txInput.SetArguments(arguments)
 251 }
 252
 253 func sortOrders(orders []*common.Order) []*common.Order {
 254         if len(orders) == 0 {
 255                 return nil
 256         }
 257
 258         orderMap := make(map[bc.AssetID]*common.Order)
 259         firstOrder := orders[0]
 260         for i := 1; i < len(orders); i++ {
 261                 orderMap[*orders[i].FromAssetID] = orders[i]
 262         }
 263
 264         sortedOrders := []*common.Order{firstOrder}
 265         for order := firstOrder; *order.ToAssetID != *firstOrder.FromAssetID; {
 266                 nextOrder, ok := orderMap[*order.ToAssetID]
 267                 if !ok {
 268                         return nil
 269                 }
 270
 271                 sortedOrders = append(sortedOrders, nextOrder)
 272                 order = nextOrder
 273         }
 274         return sortedOrders
 275 }
 276
 277 func validateTradePairs(tradePairs []*common.TradePair) error {
 278         if len(tradePairs) < 2 {
 279                 return errors.New("size of trade pairs at least 2")
 280         }
 281
 282         assetMap := make(map[string]bool)
 283         for _, tradePair := range tradePairs {
 284                 assetMap[tradePair.FromAssetID.String()] = true
 285                 if *tradePair.FromAssetID == *tradePair.ToAssetID {
 286                         return errors.New("from asset id can't equal to asset id")
 287                 }
 288         }
 289
 290         for _, tradePair := range tradePairs {
 291                 key := tradePair.ToAssetID.String()
 292                 if _, ok := assetMap[key]; !ok {
 293                         return errors.New("invalid trade pairs")
 294                 }
 295                 delete(assetMap, key)
 296         }
 297         return nil
 298 }