Sort evm outputs of import tx

5 files changed, 80 insertions, 44 deletions

diff --git a/go.mod b/go.mod
index adf981a..5d6dfe9 100644
--- a/go.mod
+++ b/go.mod
@@ -4,7 +4,7 @@ go 1.14
 
 require (
 	github.com/VictoriaMetrics/fastcache v1.5.7
-	github.com/ava-labs/avalanchego v0.8.3
+	github.com/ava-labs/avalanchego v1.0.0
 	github.com/davecgh/go-spew v1.1.1
 	github.com/deckarep/golang-set v1.7.1
 	github.com/edsrzf/mmap-go v1.0.0
diff --git a/go.sum b/go.sum
index 407e8b3..ed1316b 100644
--- a/go.sum
+++ b/go.sum
@@ -39,11 +39,12 @@ github.com/aristanetworks/goarista v0.0.0-20200812190859-4cb0e71f3c0e h1:tkEt0le
 github.com/aristanetworks/goarista v0.0.0-20200812190859-4cb0e71f3c0e/go.mod h1:QZe5Yh80Hp1b6JxQdpfSEEe8X7hTyTEZSosSrFf/oJE=
 github.com/aristanetworks/splunk-hec-go v0.3.3/go.mod h1:1VHO9r17b0K7WmOlLb9nTk/2YanvOEnLMUgsFrxBROc=
 github.com/ava-labs/avalanche-go v0.8.0-beta/go.mod h1:quYojL1hu0ue2glUT1ng28kADs9R94zGdEvfW0/HRg8=
-github.com/ava-labs/avalanchego v0.8.3 h1:ioc7RtSAzIv40qxHDikhqZGVxF3y+8cXeIrLpGz9jtc=
 github.com/ava-labs/avalanchego v0.8.3/go.mod h1:6zPzQv7m6vSvdKAwH+lLTga0IMd/0+HLMT5OULrpFcU=
+github.com/ava-labs/avalanchego v1.0.0 h1:xpqiPJS4Gftm6iKrBQJX7tpU8y0QvnyAcznlqOOsriM=
+github.com/ava-labs/avalanchego v1.0.0/go.mod h1:0N34atGvJCfJaIjFkHBDG5QzqlSJlsC07/d9irZfA7Y=
 github.com/ava-labs/coreth v0.2.14-rc.1/go.mod h1:Zhb60GFIB7G5AnUCks0Jo4Rezx/EovL8o+z51aBF1A8=
 github.com/ava-labs/coreth v0.2.15-rc.4/go.mod h1:+sK2XGKCNA48uzeHWe4iBzmiOBYmYvnnzLtOkQeQfkk=
-github.com/ava-labs/gecko v0.6.1-rc.1 h1:BhWmoDGA0Obs5ZbEdpNqw/3rx9ZMPmjcZu1oD+yySLY=
+github.com/ava-labs/coreth v0.3.4/go.mod h1:d5h8SoFyMOoFqg2gHzYgftZlKgZ1MHKKydjyq2hoABk=
 github.com/ava-labs/gecko v0.6.1-rc.1/go.mod h1:TT6uA1BETZpVMR0xiFtE8I5Mv4DULlS+lAL3xuYKnpA=
 github.com/ava-labs/go-ethereum v1.9.3 h1:GmnMZ/dlvVAPFmWBzEpRJX49pUAymPfoASLNRJqR0AY=
 github.com/ava-labs/go-ethereum v1.9.3/go.mod h1:a+agc6fXfZFsPZCylA3ry4Y8CLCqLKg3Rc23NXZ9aw8=
diff --git a/plugin/evm/import_tx.go b/plugin/evm/import_tx.go
index 0b0d348..4d7f219 100644
--- a/plugin/evm/import_tx.go
+++ b/plugin/evm/import_tx.go
@@ -75,6 +75,9 @@ func (tx *UnsignedImportTx) Verify(
 			return err
 		}
 	}
+	if !IsSortedAndUniqueEVMOutputs(tx.Outs) {
+		return errExportOutputsNotSortedAndUnique
+	}
 
 	for _, in := range tx.ImportedInputs {
 		if err := in.Verify(); err != nil {
@@ -127,15 +130,6 @@ func (tx *UnsignedImportTx) SemanticVerify(
 		return tempError{err}
 	}
 
-	utxos := make([]*avax.UTXO, len(tx.ImportedInputs))
-	for i, utxoBytes := range allUTXOBytes {
-		utxo := &avax.UTXO{}
-		if err := vm.codec.Unmarshal(utxoBytes, utxo); err != nil {
-			return tempError{err}
-		}
-		utxos[i] = utxo
-	}
-
 	for i, in := range tx.ImportedInputs {
 		utxoBytes := allUTXOBytes[i]
 
@@ -173,7 +167,7 @@ func (tx *UnsignedImportTx) Accept(ctx *snow.Context, _ database.Batch) error {
 	return ctx.SharedMemory.Remove(tx.SourceChain, utxoIDs)
 }
 
-// Create a new transaction
+// newImportTx returns a new ImportTx
 func (vm *VM) newImportTx(
 	chainID ids.ID, // chain to import from
 	to common.Address, // Address of recipient
@@ -240,20 +234,23 @@ func (vm *VM) newImportTx(
 	//	})
 	//}
 
-	// non-AVAX asset outputs
-	for aidKey, amount := range importedAmount {
-		aid := ids.NewID(aidKey)
-		//if aid.Equals(vm.ctx.AVAXAssetID) || amount == 0 {
+	// This will create unique outputs (in the context of sorting)
+	// since each output will have a unique assetID
+	for assetKey, amount := range importedAmount {
+		assetID := ids.NewID(assetKey)
+		//if assetID.Equals(vm.ctx.AVAXAssetID) || amount == 0 {
 		if amount == 0 {
 			continue
 		}
 		outs = append(outs, EVMOutput{
 			Address: to,
 			Amount:  amount,
-			AssetID: aid,
+			AssetID: assetID,
 		})
 	}
 
+	SortEVMOutputs(outs)
+
 	// Create the transaction
 	utx := &UnsignedImportTx{
 		NetworkID:      vm.ctx.NetworkID,
@@ -269,6 +266,8 @@ func (vm *VM) newImportTx(
 	return tx, utx.Verify(vm.ctx.XChainID, vm.ctx, vm.txFee, vm.ctx.AVAXAssetID)
 }
 
+// EVMStateTransfer performs the state transfer to increase the balances of
+// accounts accordingly with the imported EVMOutputs
 func (tx *UnsignedImportTx) EVMStateTransfer(vm *VM, state *state.StateDB) error {
 	for _, to := range tx.Outs {
 		log.Info("crosschain X->C", "addr", to.Address, "amount", to.Amount)
diff --git a/plugin/evm/tx.go b/plugin/evm/tx.go
index db49980..7dcebc8 100644
--- a/plugin/evm/tx.go
+++ b/plugin/evm/tx.go
@@ -126,7 +126,11 @@ type innerSortInputsAndSigners struct {
 }
 
 func (ins *innerSortInputsAndSigners) Less(i, j int) bool {
-	return bytes.Compare(ins.inputs[i].Address.Bytes(), ins.inputs[j].Address.Bytes()) < 0
+	addrComp := bytes.Compare(ins.inputs[i].Address.Bytes(), ins.inputs[j].Address.Bytes())
+	if addrComp != 0 {
+		return addrComp < 0
+	}
+	return bytes.Compare(ins.inputs[i].AssetID.Bytes(), ins.inputs[j].AssetID.Bytes()) < 0
 }
 
 func (ins *innerSortInputsAndSigners) Len() int { return len(ins.inputs) }
@@ -136,7 +140,7 @@ func (ins *innerSortInputsAndSigners) Swap(i, j int) {
 	ins.signers[j], ins.signers[i] = ins.signers[i], ins.signers[j]
 }
 
-// SortEVMInputsAndSigners sorts the list of EVMInputs based solely on the address of the input
+// SortEVMInputsAndSigners sorts the list of EVMInputs based on the addresses and assetIDs
 func SortEVMInputsAndSigners(inputs []EVMInput, signers [][]*crypto.PrivateKeySECP256K1R) {
 	sort.Sort(&innerSortInputsAndSigners{inputs: inputs, signers: signers})
 }
@@ -146,3 +150,34 @@ func SortEVMInputsAndSigners(inputs []EVMInput, signers [][]*crypto.PrivateKeySE
 func IsSortedAndUniqueEVMInputs(inputs []EVMInput) bool {
 	return utils.IsSortedAndUnique(&innerSortInputsAndSigners{inputs: inputs})
 }
+
+// innerSortEVMOutputs implements sort.Interface for EVMOutput
+type innerSortEVMOutputs struct {
+	outputs []EVMOutput
+}
+
+func (outs *innerSortEVMOutputs) Less(i, j int) bool {
+	addrComp := bytes.Compare(outs.outputs[i].Address.Bytes(), outs.outputs[j].Address.Bytes())
+	if addrComp != 0 {
+		return addrComp < 0
+	}
+	return bytes.Compare(outs.outputs[i].AssetID.Bytes(), outs.outputs[j].AssetID.Bytes()) < 0
+}
+
+func (outs *innerSortEVMOutputs) Len() int { return len(outs.outputs) }
+
+func (outs *innerSortEVMOutputs) Swap(i, j int) {
+	outs.outputs[j], outs.outputs[i] = outs.outputs[i], outs.outputs[j]
+}
+
+// SortEVMOutputs sorts the list of EVMOutputs based on the addresses and assetIDs
+// of the outputs
+func SortEVMOutputs(outputs []EVMOutput) {
+	sort.Sort(&innerSortEVMOutputs{outputs: outputs})
+}
+
+// IsSortedAndUniqueEVMOutputs returns true if the EVMOutputs are sorted and unique
+// based on the account addresses and assetIDs
+func IsSortedAndUniqueEVMOutputs(outputs []EVMOutput) bool {
+	return utils.IsSortedAndUnique(&innerSortEVMOutputs{outputs: outputs})
+}
diff --git a/plugin/evm/vm.go b/plugin/evm/vm.go
index bf43492..64ae42e 100644
--- a/plugin/evm/vm.go
+++ b/plugin/evm/vm.go
@@ -89,30 +89,31 @@ const (
 var (
 	txFee = units.MilliAvax
 
-	errEmptyBlock                 = errors.New("empty block")
-	errCreateBlock                = errors.New("couldn't create block")
-	errUnknownBlock               = errors.New("unknown block")
-	errBlockFrequency             = errors.New("too frequent block issuance")
-	errUnsupportedFXs             = errors.New("unsupported feature extensions")
-	errInvalidBlock               = errors.New("invalid block")
-	errInvalidAddr                = errors.New("invalid hex address")
-	errTooManyAtomicTx            = errors.New("too many pending atomic txs")
-	errAssetIDMismatch            = errors.New("asset IDs in the input don't match the utxo")
-	errWrongNumberOfCredentials   = errors.New("should have the same number of credentials as inputs")
-	errNoInputs                   = errors.New("tx has no inputs")
-	errNoImportInputs             = errors.New("tx has no imported inputs")
-	errInputsNotSortedUnique      = errors.New("inputs not sorted and unique")
-	errPublicKeySignatureMismatch = errors.New("signature doesn't match public key")
-	errUnknownAsset               = errors.New("unknown asset ID")
-	errNoFunds                    = errors.New("no spendable funds were found")
-	errWrongChainID               = errors.New("tx has wrong chain ID")
-	errInsufficientFunds          = errors.New("insufficient funds")
-	errNoExportOutputs            = errors.New("no export outputs")
-	errOutputsNotSorted           = errors.New("outputs not sorted")
-	errNoExportInputs             = errors.New("no inputs to export")
-	errInputsNotSortedAndUnique   = errors.New("inputs not sorted and unique")
-	errOverflowExport             = errors.New("overflow when computing export amount + txFee")
-	errInvalidNonce               = errors.New("invalid nonce")
+	errEmptyBlock                      = errors.New("empty block")
+	errCreateBlock                     = errors.New("couldn't create block")
+	errUnknownBlock                    = errors.New("unknown block")
+	errBlockFrequency                  = errors.New("too frequent block issuance")
+	errUnsupportedFXs                  = errors.New("unsupported feature extensions")
+	errInvalidBlock                    = errors.New("invalid block")
+	errInvalidAddr                     = errors.New("invalid hex address")
+	errTooManyAtomicTx                 = errors.New("too many pending atomic txs")
+	errAssetIDMismatch                 = errors.New("asset IDs in the input don't match the utxo")
+	errWrongNumberOfCredentials        = errors.New("should have the same number of credentials as inputs")
+	errNoInputs                        = errors.New("tx has no inputs")
+	errNoImportInputs                  = errors.New("tx has no imported inputs")
+	errInputsNotSortedUnique           = errors.New("inputs not sorted and unique")
+	errPublicKeySignatureMismatch      = errors.New("signature doesn't match public key")
+	errUnknownAsset                    = errors.New("unknown asset ID")
+	errNoFunds                         = errors.New("no spendable funds were found")
+	errWrongChainID                    = errors.New("tx has wrong chain ID")
+	errInsufficientFunds               = errors.New("insufficient funds")
+	errNoExportOutputs                 = errors.New("no export outputs")
+	errExportOutputsNotSortedAndUnique = errors.New("export outputs are not sorted and unique")
+	errOutputsNotSorted                = errors.New("outputs not sorted")
+	errNoExportInputs                  = errors.New("no inputs to export")
+	errInputsNotSortedAndUnique        = errors.New("inputs not sorted and unique")
+	errOverflowExport                  = errors.New("overflow when computing export amount + txFee")
+	errInvalidNonce                    = errors.New("invalid nonce")
 )
 
 func maxDuration(x, y time.Duration) time.Duration {