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, feeStrategy FeeStrategy, rewardProgram []byte) *Engine {
  25         return &Engine{orderBook: orderBook, feeStrategy: feeStrategy, 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, 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.addPartialTradeOrder(tx); err != nil {
  60                 return nil, err
  61         }
  62         return tx, nil
  63 }
  64
  65 func (e *Engine) addMatchTxFeeOutput(txData *types.TxData, refunds []RefundAssets, fees []*bc.AssetAmount) error {
  66         for _, feeAmount := range fees {
  67                 txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*feeAmount.AssetId, feeAmount.Amount, e.rewardProgram))
  68         }
  69
  70         for i, refund := range refunds {
  71                 // each trading participant may be refunded multiple assets
  72                 for _, assetAmount := range refund {
  73                         contractArgs, err := segwit.DecodeP2WMCProgram(txData.Inputs[i].ControlProgram())
  74                         if err != nil {
  75                                 return err
  76                         }
  77
  78                         txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*assetAmount.AssetId, assetAmount.Amount, contractArgs.SellerProgram))
  79                 }
  80         }
  81         return nil
  82 }
  83
  84 func (e *Engine) addPartialTradeOrder(tx *types.Tx) error {
  85         for i, output := range tx.Outputs {
  86                 if !segwit.IsP2WMCScript(output.ControlProgram()) {
  87                         continue
  88                 }
  89
  90                 order, err := common.NewOrderFromOutput(tx, i)
  91                 if err != nil {
  92                         return err
  93                 }
  94
  95                 e.orderBook.AddOrder(order)
  96         }
  97         return nil
  98 }
  99
 100 func (e *Engine) buildMatchTx(orders []*common.Order) (*types.Tx, error) {
 101         txData := &types.TxData{Version: 1}
 102         for _, order := range orders {
 103                 input := types.NewSpendInput(nil, *order.Utxo.SourceID, *order.FromAssetID, order.Utxo.Amount, order.Utxo.SourcePos, order.Utxo.ControlProgram)
 104                 txData.Inputs = append(txData.Inputs, input)
 105         }
 106
 107         receivedAmounts, priceDiffs := CalcReceivedAmount(orders)
 108         allocatedAssets := e.feeStrategy.Allocate(receivedAmounts, priceDiffs)
 109         if err := addMatchTxOutput(txData, orders, receivedAmounts, allocatedAssets.Receives); err != nil {
 110                 return nil, err
 111         }
 112
 113         if err := e.addMatchTxFeeOutput(txData, allocatedAssets.Refunds, allocatedAssets.Fees); err != nil {
 114                 return nil, err
 115         }
 116
 117         byteData, err := txData.MarshalText()
 118         if err != nil {
 119                 return nil, err
 120         }
 121
 122         txData.SerializedSize = uint64(len(byteData))
 123         return types.NewTx(*txData), nil
 124 }
 125
 126 func addMatchTxOutput(txData *types.TxData, orders []*common.Order, receivedAmounts, deductFeeReceives []*bc.AssetAmount) error {
 127         for i, order := range orders {
 128                 contractArgs, err := segwit.DecodeP2WMCProgram(order.Utxo.ControlProgram)
 129                 if err != nil {
 130                         return err
 131                 }
 132
 133                 requestAmount := CalcRequestAmount(order.Utxo.Amount, contractArgs.RatioNumerator, contractArgs.RatioDenominator)
 134                 receivedAmount := receivedAmounts[i].Amount
 135                 shouldPayAmount := calcShouldPayAmount(receivedAmount, contractArgs.RatioNumerator, contractArgs.RatioDenominator)
 136                 isPartialTrade := requestAmount > receivedAmount
 137
 138                 setMatchTxArguments(txData.Inputs[i], isPartialTrade, len(txData.Outputs), receivedAmounts[i].Amount)
 139                 txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*order.ToAssetID, deductFeeReceives[i].Amount, contractArgs.SellerProgram))
 140                 if isPartialTrade {
 141                         txData.Outputs = append(txData.Outputs, types.NewIntraChainOutput(*order.FromAssetID, order.Utxo.Amount-shouldPayAmount, order.Utxo.ControlProgram))
 142                 }
 143         }
 144         return nil
 145 }
 146
 147 func calcOppositeIndex(size int, selfIdx int) int {
 148         return (selfIdx + 1) % size
 149 }
 150
 151 // CalcRequestAmount is from amount * numerator / ratioDenominator
 152 func CalcRequestAmount(fromAmount uint64, ratioNumerator, ratioDenominator int64) uint64 {
 153         res := big.NewInt(0).SetUint64(fromAmount)
 154         res.Mul(res, big.NewInt(ratioNumerator)).Quo(res, big.NewInt(ratioDenominator))
 155         if !res.IsUint64() {
 156                 return 0
 157         }
 158         return res.Uint64()
 159 }
 160
 161 func calcShouldPayAmount(receiveAmount uint64, ratioNumerator, ratioDenominator int64) uint64 {
 162         res := big.NewInt(0).SetUint64(receiveAmount)
 163         res.Mul(res, big.NewInt(ratioDenominator)).Quo(res, big.NewInt(ratioNumerator))
 164         if !res.IsUint64() {
 165                 return 0
 166         }
 167         return res.Uint64()
 168 }
 169
 170 // CalcReceivedAmount return amount of assets received by each participant in the matching transaction and the price difference
 171 func CalcReceivedAmount(orders []*common.Order) ([]*bc.AssetAmount, []*bc.AssetAmount) {
 172         var receivedAmounts, priceDiffs, shouldPayAmounts []*bc.AssetAmount
 173         for i, order := range orders {
 174                 requestAmount := CalcRequestAmount(order.Utxo.Amount, order.RatioNumerator, order.RatioDenominator)
 175                 oppositeOrder := orders[calcOppositeIndex(len(orders), i)]
 176                 receiveAmount := vprMath.MinUint64(oppositeOrder.Utxo.Amount, requestAmount)
 177                 shouldPayAmount := calcShouldPayAmount(receiveAmount, order.RatioNumerator, order.RatioDenominator)
 178                 receivedAmounts = append(receivedAmounts, &bc.AssetAmount{AssetId: order.ToAssetID, Amount: receiveAmount})
 179                 shouldPayAmounts = append(shouldPayAmounts, &bc.AssetAmount{AssetId: order.FromAssetID, Amount: shouldPayAmount})
 180         }
 181
 182         for i, receivedAmount := range receivedAmounts {
 183                 oppositeShouldPayAmount := shouldPayAmounts[calcOppositeIndex(len(orders), i)]
 184                 if oppositeShouldPayAmount.Amount > receivedAmount.Amount {
 185                         assetId := oppositeShouldPayAmount.AssetId
 186                         amount := oppositeShouldPayAmount.Amount - receivedAmount.Amount
 187                         priceDiffs = append(priceDiffs, &bc.AssetAmount{AssetId: assetId, Amount: amount})
 188                 }
 189         }
 190         return receivedAmounts, priceDiffs
 191 }
 192
 193 // IsMatched check does the orders can be exchange
 194 func IsMatched(orders []*common.Order) bool {
 195         sortedOrders := sortOrders(orders)
 196         if len(sortedOrders) == 0 {
 197                 return false
 198         }
 199
 200         rate := big.NewRat(sortedOrders[0].RatioDenominator, sortedOrders[0].RatioNumerator)
 201         oppositeRate := big.NewRat(1, 1)
 202         for i := 1; i < len(sortedOrders); i++ {
 203                 oppositeRate.Mul(oppositeRate, big.NewRat(sortedOrders[i].RatioNumerator, sortedOrders[i].RatioDenominator))
 204         }
 205
 206         return rate.Cmp(oppositeRate) >= 0
 207 }
 208
 209 func setMatchTxArguments(txInput *types.TxInput, isPartialTrade bool, position int, receiveAmounts uint64) {
 210         var arguments [][]byte
 211         if isPartialTrade {
 212                 arguments = [][]byte{vm.Int64Bytes(int64(receiveAmounts)), vm.Int64Bytes(int64(position)), vm.Int64Bytes(contract.PartialTradeClauseSelector)}
 213         } else {
 214                 arguments = [][]byte{vm.Int64Bytes(int64(position)), vm.Int64Bytes(contract.FullTradeClauseSelector)}
 215         }
 216         txInput.SetArguments(arguments)
 217 }
 218
 219 func sortOrders(orders []*common.Order) []*common.Order {
 220         if len(orders) == 0 {
 221                 return nil
 222         }
 223
 224         orderMap := make(map[bc.AssetID]*common.Order)
 225         firstOrder := orders[0]
 226         for i := 1; i < len(orders); i++ {
 227                 orderMap[*orders[i].FromAssetID] = orders[i]
 228         }
 229
 230         sortedOrders := []*common.Order{firstOrder}
 231         for order := firstOrder; *order.ToAssetID != *firstOrder.FromAssetID; {
 232                 nextOrder, ok := orderMap[*order.ToAssetID]
 233                 if !ok {
 234                         return nil
 235                 }
 236
 237                 sortedOrders = append(sortedOrders, nextOrder)
 238                 order = nextOrder
 239         }
 240         return sortedOrders
 241 }
 242
 243 func validateTradePairs(tradePairs []*common.TradePair) error {
 244         if len(tradePairs) < 2 {
 245                 return errors.New("size of trade pairs at least 2")
 246         }
 247
 248         assetMap := make(map[string]bool)
 249         for _, tradePair := range tradePairs {
 250                 assetMap[tradePair.FromAssetID.String()] = true
 251                 if *tradePair.FromAssetID == *tradePair.ToAssetID {
 252                         return errors.New("from asset id can't equal to asset id")
 253                 }
 254         }
 255
 256         for _, tradePair := range tradePairs {
 257                 key := tradePair.ToAssetID.String()
 258                 if _, ok := assetMap[key]; !ok {
 259                         return errors.New("invalid trade pairs")
 260                 }
 261                 delete(assetMap, key)
 262         }
 263         return nil
 264 }