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 // NewEngine return a new Engine
  24 func NewEngine(orderBook *OrderBook, rewardProgram []byte) *Engine {
  25         return &Engine{orderBook: orderBook, feeStrategy: NewDefaultFeeStrategy(), rewardProgram: rewardProgram}
  26 }
  27
  28 // HasMatchedTx check does the input trade pair can generate a match deal
  29 func (e *Engine) HasMatchedTx(tradePairs ...*common.TradePair) bool {
  30         if err := validateTradePairs(tradePairs); err != nil {
  31                 return false
  32         }
  33
  34         orders := e.orderBook.PeekOrders(tradePairs)
  35         if len(orders) == 0 {
  36                 return false
  37         }
  38
  39         return IsMatched(orders)
  40 }
  41
  42 // NextMatchedTx return the next matchable transaction by the specified trade pairs
  43 // the size of trade pairs at least 2, and the sequence of trade pairs can form a loop
  44 // for example, [assetA -> assetB, assetB -> assetC, assetC -> assetA]
  45 func (e *Engine) NextMatchedTx(tradePairs ...*common.TradePair) (*types.Tx, error) {
  46         if !e.HasMatchedTx(tradePairs...) {
  47                 return nil, errors.New("the specified trade pairs can not be matched")
  48         }
  49
  50         tx, partialOrders, err := e.buildMatchTx(sortOrders(e.orderBook.PeekOrders(tradePairs)))
  51         if err != nil {
  52                 return nil, err
  53         }
  54
  55         for _, tradePair := range tradePairs {
  56                 e.orderBook.PopOrder(tradePair)
  57         }
  58
  59         if err := e.addReOrder(partialOrders, tx); err != nil {
  60                 return nil, err
  61         }
  62         return tx, nil
  63 }
  64
  65 func addMatchTxFeeOutput(txData *types.TxData, fees []*bc.AssetAmount, rewardProgram []byte) {
  66         for _, feeAmount := range fees {
  67                 if feeAmount.Amount != 0 {
  68                         txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*feeAmount.AssetId, feeAmount.Amount, rewardProgram))
  69                 }
  70         }
  71 }
  72
  73 func (e *Engine) addReOrder(partialOrders []*common.Order, tx *types.Tx) error {
  74         index := 0
  75         for i, output := range tx.Outputs {
  76                 if !segwit.IsP2WMCScript(output.ControlProgram()) || output.AssetAmount().Amount == 0 {
  77                         continue
  78                 }
  79
  80                 partialOrder := partialOrders[index]
  81                 order, err := common.NewOrderFromOutput(tx, i, partialOrder.BlockHeight, partialOrder.TxIndex)
  82                 if err != nil {
  83                         return err
  84                 }
  85
  86                 index++
  87                 e.orderBook.AddOrder(order)
  88         }
  89         return nil
  90 }
  91
  92 func addRefundOutput(txData *types.TxData, orders []*common.Order) {
  93         refundAmount := map[bc.AssetID]uint64{}
  94         var assetIDs []bc.AssetID
  95         var refundScript [][]byte
  96         for i, input := range txData.Inputs {
  97                 refundAmount[input.AssetID()] += input.Amount()
  98                 assetIDs = append(assetIDs, input.AssetID())
  99                 refundScript = append(refundScript, orders[i].ContractArgs.SellerProgram)
 100         }
 101
 102         for _, output := range txData.Outputs {
 103                 assetAmount := output.AssetAmount()
 104                 refundAmount[*assetAmount.AssetId] -= assetAmount.Amount
 105         }
 106
 107         refundCount := len(refundScript)
 108         for _, assetID := range assetIDs {
 109                 amount := refundAmount[assetID]
 110                 averageAmount := amount / uint64(refundCount)
 111                 if averageAmount == 0 {
 112                         averageAmount = 1
 113                 }
 114
 115                 for i := 0; i < refundCount && amount > 0; i++ {
 116                         if i == refundCount-1 {
 117                                 averageAmount = amount
 118                         }
 119                         txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(assetID, averageAmount, refundScript[i]))
 120                         amount -= averageAmount
 121                 }
 122         }
 123 }
 124
 125 func addTakerOutput(txData *types.TxData, orders []*common.Order, priceDiffs []*bc.AssetAmount, makerFlags []*MakerFlag) {
 126         for i := range orders {
 127                 if makerFlags[i].IsMaker {
 128                         continue
 129                 }
 130                 for _, priceDiff := range priceDiffs {
 131                         if priceDiff.Amount == 0 {
 132                                 continue
 133                         }
 134
 135                         txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*priceDiff.AssetId, priceDiff.Amount, orders[i].ContractArgs.SellerProgram))
 136                 }
 137                 break
 138         }
 139 }
 140
 141 func (e *Engine) buildMatchTx(orders []*common.Order) (*types.Tx, []*common.Order, error) {
 142         txData := &types.TxData{Version: 1}
 143         for _, order := range orders {
 144                 input := types.NewSpendInput(nil, *order.Utxo.SourceID, *order.FromAssetID, order.Utxo.Amount, order.Utxo.SourcePos, order.Utxo.ControlProgram)
 145                 txData.Inputs = append(txData.Inputs, input)
 146         }
 147
 148         isMakers := MakerFlags(orders)
 149         receivedAmounts, priceDiffs := CalcReceivedAmount(orders)
 150         allocatedAssets := e.feeStrategy.Allocate(receivedAmounts, priceDiffs, isMakers)
 151
 152         partialOrders, err := addMatchTxOutput(txData, orders, receivedAmounts, allocatedAssets, isMakers)
 153         if err != nil {
 154                 return nil, nil, err
 155         }
 156
 157         addMatchTxFeeOutput(txData, allocatedAssets.Fees, e.rewardProgram)
 158         addTakerOutput(txData, orders, priceDiffs, isMakers)
 159         addRefundOutput(txData, orders)
 160
 161         byteData, err := txData.MarshalText()
 162         if err != nil {
 163                 return nil, nil, err
 164         }
 165
 166         txData.SerializedSize = uint64(len(byteData))
 167         return types.NewTx(*txData), partialOrders, nil
 168 }
 169
 170 func addMatchTxOutput(txData *types.TxData, orders []*common.Order, receivedAmounts []*bc.AssetAmount, allocatedAssets *AllocatedAssets, makerFlags []*MakerFlag) ([]*common.Order, error) {
 171         var partialOrders []*common.Order
 172         for i, order := range orders {
 173                 contractArgs := order.ContractArgs
 174                 receivedAmount := receivedAmounts[i].Amount
 175                 shouldPayAmount := calcShouldPayAmount(receivedAmount, contractArgs.RatioNumerator, contractArgs.RatioDenominator)
 176
 177                 requestAmount := CalcRequestAmount(order.Utxo.Amount, order.RatioNumerator, order.RatioDenominator)
 178                 exchangeAmount := order.Utxo.Amount - shouldPayAmount
 179                 isPartialTrade := requestAmount > receivedAmount && CalcRequestAmount(exchangeAmount, contractArgs.RatioNumerator, contractArgs.RatioDenominator) >= 1
 180
 181                 setMatchTxArguments(txData.Inputs[i], isPartialTrade, len(txData.Outputs), receivedAmount, makerFlags[i].IsMaker, contractArgs.Version)
 182
 183                 txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*order.ToAssetID, allocatedAssets.Receives[i].Amount, contractArgs.SellerProgram))
 184                 if isPartialTrade {
 185                         txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*order.FromAssetID, exchangeAmount, order.Utxo.ControlProgram))
 186                         partialOrders = append(partialOrders, order)
 187                 }
 188         }
 189         return partialOrders, nil
 190 }
 191
 192 func calcOppositeIndex(size int, selfIdx int) int {
 193         return (selfIdx + 1) % size
 194 }
 195
 196 // CalcRequestAmount is from amount * numerator / ratioDenominator
 197 func CalcRequestAmount(fromAmount uint64, ratioNumerator, ratioDenominator int64) uint64 {
 198         res := big.NewInt(0).SetUint64(fromAmount)
 199         res.Mul(res, big.NewInt(ratioNumerator)).Quo(res, big.NewInt(ratioDenominator))
 200         if !res.IsUint64() {
 201                 return 0
 202         }
 203         return res.Uint64()
 204 }
 205
 206 func calcShouldPayAmount(receiveAmount uint64, ratioNumerator, ratioDenominator int64) uint64 {
 207         res := big.NewInt(0).SetUint64(receiveAmount)
 208         res.Mul(res, big.NewInt(ratioDenominator)).Quo(res, big.NewInt(ratioNumerator))
 209         if !res.IsUint64() {
 210                 return 0
 211         }
 212         return res.Uint64()
 213 }
 214
 215 // CalcReceivedAmount return amount of assets received by each participant in the matching transaction and the price difference
 216 func CalcReceivedAmount(orders []*common.Order) ([]*bc.AssetAmount, []*bc.AssetAmount) {
 217         var receivedAmounts, priceDiffs, shouldPayAmounts []*bc.AssetAmount
 218         for i, order := range orders {
 219                 requestAmount := CalcRequestAmount(order.Utxo.Amount, order.RatioNumerator, order.RatioDenominator)
 220                 oppositeOrder := orders[calcOppositeIndex(len(orders), i)]
 221                 receiveAmount := vprMath.MinUint64(oppositeOrder.Utxo.Amount, requestAmount)
 222                 shouldPayAmount := calcShouldPayAmount(receiveAmount, order.RatioNumerator, order.RatioDenominator)
 223                 receivedAmounts = append(receivedAmounts, &bc.AssetAmount{AssetId: order.ToAssetID, Amount: receiveAmount})
 224                 shouldPayAmounts = append(shouldPayAmounts, &bc.AssetAmount{AssetId: order.FromAssetID, Amount: shouldPayAmount})
 225         }
 226
 227         for i, receivedAmount := range receivedAmounts {
 228                 oppositeShouldPayAmount := shouldPayAmounts[calcOppositeIndex(len(orders), i)]
 229                 priceDiffs = append(priceDiffs, &bc.AssetAmount{AssetId: oppositeShouldPayAmount.AssetId, Amount: 0})
 230                 if oppositeShouldPayAmount.Amount > receivedAmount.Amount {
 231                         priceDiffs[i].Amount = oppositeShouldPayAmount.Amount - receivedAmount.Amount
 232                 }
 233         }
 234         return receivedAmounts, priceDiffs
 235 }
 236
 237 // IsMatched check does the orders can be exchange
 238 func IsMatched(orders []*common.Order) bool {
 239         sortedOrders := sortOrders(orders)
 240         if len(sortedOrders) == 0 {
 241                 return false
 242         }
 243
 244         product := big.NewRat(1, 1)
 245         for _, order := range orders {
 246                 product.Mul(product, big.NewRat(order.RatioNumerator, order.RatioDenominator))
 247         }
 248         one := big.NewRat(1, 1)
 249         return product.Cmp(one) <= 0
 250 }
 251
 252 // MakerFlag represent whether the order is isMaker and include the contract version of order
 253 type MakerFlag struct {
 254         IsMaker         bool
 255         ContractVersion int
 256 }
 257
 258 // MakerFlags return a slice of array indicate whether orders[i] is maker
 259 func MakerFlags(orders []*common.Order) []*MakerFlag {
 260         makerFlags := make([]*MakerFlag, len(orders))
 261         for i, order := range orders {
 262                 makerFlags[i].IsMaker = isMaker(order, orders[calcOppositeIndex(len(orders), i)])
 263                 makerFlags[i].ContractVersion = order.ContractArgs.Version
 264         }
 265         return makerFlags
 266 }
 267
 268 func isMaker(order, oppositeOrder *common.Order) bool {
 269         // old version of order's block height and tx sequence is 0
 270         if order.BlockHeight == 0 && oppositeOrder.BlockHeight != 0 {
 271                 return true
 272         }
 273         if order.BlockHeight != 0 && oppositeOrder.BlockHeight == 0 {
 274                 return false
 275         }
 276         if order.BlockHeight == oppositeOrder.BlockHeight {
 277                 if order.TxIndex == oppositeOrder.TxIndex {
 278                         return order.UTXOHash().String() < oppositeOrder.UTXOHash().String()
 279                 }
 280                 return order.TxIndex < oppositeOrder.TxIndex
 281         }
 282         return order.BlockHeight < oppositeOrder.BlockHeight
 283 }
 284
 285 func setMatchTxArguments(txInput *types.TxInput, isPartialTrade bool, position int, receiveAmounts uint64, isMaker bool, contractVersion int) {
 286         feeRate := TakerFeeRate
 287         if isMaker {
 288                 feeRate = MakerFeeRate
 289         }
 290
 291         var arguments [][]byte
 292         if isPartialTrade {
 293                 arguments = [][]byte{vm.Int64Bytes(int64(receiveAmounts))}
 294                 if contractVersion == segwit.MagneticV2 {
 295                         arguments = append(arguments, vm.Int64Bytes(feeRate))
 296                 }
 297                 arguments = append(arguments, vm.Int64Bytes(int64(position)), vm.Int64Bytes(contract.PartialTradeClauseSelector))
 298         } else {
 299                 if contractVersion == segwit.MagneticV2 {
 300                         arguments = append(arguments, vm.Int64Bytes(feeRate))
 301                 }
 302                 arguments = [][]byte{vm.Int64Bytes(int64(position)), vm.Int64Bytes(contract.FullTradeClauseSelector)}
 303         }
 304         txInput.SetArguments(arguments)
 305 }
 306
 307 func sortOrders(orders []*common.Order) []*common.Order {
 308         if len(orders) == 0 {
 309                 return nil
 310         }
 311
 312         orderMap := make(map[bc.AssetID]*common.Order)
 313         firstOrder := orders[0]
 314         for i := 1; i < len(orders); i++ {
 315                 orderMap[*orders[i].FromAssetID] = orders[i]
 316         }
 317
 318         sortedOrders := []*common.Order{firstOrder}
 319         for order := firstOrder; *order.ToAssetID != *firstOrder.FromAssetID; {
 320                 nextOrder, ok := orderMap[*order.ToAssetID]
 321                 if !ok {
 322                         return nil
 323                 }
 324
 325                 sortedOrders = append(sortedOrders, nextOrder)
 326                 order = nextOrder
 327         }
 328         return sortedOrders
 329 }
 330
 331 func validateTradePairs(tradePairs []*common.TradePair) error {
 332         if len(tradePairs) < 2 {
 333                 return errors.New("size of trade pairs at least 2")
 334         }
 335
 336         assetMap := make(map[string]bool)
 337         for _, tradePair := range tradePairs {
 338                 assetMap[tradePair.FromAssetID.String()] = true
 339                 if *tradePair.FromAssetID == *tradePair.ToAssetID {
 340                         return errors.New("from asset id can't equal to asset id")
 341                 }
 342         }
 343
 344         for _, tradePair := range tradePairs {
 345                 key := tradePair.ToAssetID.String()
 346                 if _, ok := assetMap[key]; !ok {
 347                         return errors.New("invalid trade pairs")
 348                 }
 349                 delete(assetMap, key)
 350         }
 351         return nil
 352 }