Merge pull request #42 from ava-labs/v1.0.2-rc.1-bumpv0.3.5

V1.0.2 rc.1 bump

8 files changed, 761 insertions, 51 deletions

diff --git a/plugin/evm/export_tx.go b/plugin/evm/export_tx.go
index f210352..d099eb2 100644
--- a/plugin/evm/export_tx.go
+++ b/plugin/evm/export_tx.go
@@ -92,16 +92,25 @@ func (tx *UnsignedExportTx) SemanticVerify(
 		return permError{err}
 	}
 
+	if len(tx.Ins) != len(stx.Creds) {
+		return permError{errSignatureInputsMismatch}
+	}
+
 	f := crypto.FactorySECP256K1R{}
-	for i, cred := range stx.Creds {
+	for i, input := range tx.Ins {
+		cred := stx.Creds[i].(*secp256k1fx.Credential)
 		if err := cred.Verify(); err != nil {
 			return permError{err}
 		}
-		pubKey, err := f.RecoverPublicKey(tx.UnsignedBytes(), cred.(*secp256k1fx.Credential).Sigs[0][:])
+
+		if len(cred.Sigs) != 1 {
+			return permError{fmt.Errorf("expected one signature for EVM Input Credential, but found: %d", len(cred.Sigs))}
+		}
+		pubKey, err := f.RecoverPublicKey(tx.UnsignedBytes(), cred.Sigs[0][:])
 		if err != nil {
 			return permError{err}
 		}
-		if tx.Ins[i].Address != PublicKeyToEthAddress(pubKey) {
+		if input.Address != PublicKeyToEthAddress(pubKey) {
 			return permError{errPublicKeySignatureMismatch}
 		}
 	}
@@ -160,7 +169,7 @@ func (tx *UnsignedExportTx) Accept(ctx *snow.Context, _ database.Batch) error {
 	return ctx.SharedMemory.Put(tx.DestinationChain, elems)
 }
 
-// Create a new transaction
+// newExportTx returns a new ExportTx
 func (vm *VM) newExportTx(
 	assetID ids.ID, // AssetID of the tokens to export
 	amount uint64, // Amount of tokens to export
@@ -183,14 +192,14 @@ func (vm *VM) newExportTx(
 		toBurn = vm.txFee
 	}
 	// burn AVAX
-	ins, signers, err := vm.GetSpendableCanonical(keys, vm.ctx.AVAXAssetID, toBurn)
+	ins, signers, err := vm.GetSpendableFunds(keys, vm.ctx.AVAXAssetID, toBurn)
 	if err != nil {
 		return nil, fmt.Errorf("couldn't generate tx inputs/outputs: %w", err)
 	}
 
 	// burn non-AVAX
 	if !assetID.Equals(vm.ctx.AVAXAssetID) {
-		ins2, signers2, err := vm.GetSpendableCanonical(keys, assetID, amount)
+		ins2, signers2, err := vm.GetSpendableFunds(keys, assetID, amount)
 		if err != nil {
 			return nil, fmt.Errorf("couldn't generate tx inputs/outputs: %w", err)
 		}
@@ -210,6 +219,9 @@ func (vm *VM) newExportTx(
 		},
 	}}
 
+	avax.SortTransferableOutputs(exportOuts, vm.codec)
+	SortEVMInputsAndSigners(ins, signers)
+
 	// Create the transaction
 	utx := &UnsignedExportTx{
 		NetworkID:        vm.ctx.NetworkID,
@@ -225,6 +237,7 @@ func (vm *VM) newExportTx(
 	return tx, utx.Verify(vm.ctx.XChainID, vm.ctx, vm.txFee, vm.ctx.AVAXAssetID)
 }
 
+// EVMStateTransfer executes the state update from the atomic export transaction
 func (tx *UnsignedExportTx) EVMStateTransfer(vm *VM, state *state.StateDB) error {
 	addrs := map[[20]byte]uint64{}
 	for _, from := range tx.Ins {
diff --git a/plugin/evm/export_tx_test.go b/plugin/evm/export_tx_test.go
new file mode 100644
index 0000000..319c6dd
--- /dev/null
+++ b/plugin/evm/export_tx_test.go
@@ -0,0 +1,132 @@
+// (c) 2019-2020, Ava Labs, Inc. All rights reserved.
+// See the file LICENSE for licensing terms.
+
+package evm
+
+import (
+	"testing"
+
+	"github.com/ava-labs/avalanchego/ids"
+	"github.com/ava-labs/avalanchego/utils/crypto"
+	"github.com/ava-labs/avalanchego/vms/components/avax"
+	"github.com/ava-labs/avalanchego/vms/secp256k1fx"
+)
+
+func TestExportTxVerifyNil(t *testing.T) {
+	var exportTx *UnsignedExportTx
+	if err := exportTx.Verify(testXChainID, NewContext(), testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("Verify should have failed due to nil transaction")
+	}
+}
+
+func TestExportTxVerify(t *testing.T) {
+	var exportAmount uint64 = 10000000
+	exportTx := &UnsignedExportTx{
+		NetworkID:        testNetworkID,
+		BlockchainID:     testCChainID,
+		DestinationChain: testXChainID,
+		Ins: []EVMInput{
+			{
+				Address: testEthAddrs[0],
+				Amount:  exportAmount,
+				AssetID: testAvaxAssetID,
+				Nonce:   0,
+			},
+			{
+				Address: testEthAddrs[2],
+				Amount:  exportAmount,
+				AssetID: testAvaxAssetID,
+				Nonce:   0,
+			},
+		},
+		ExportedOutputs: []*avax.TransferableOutput{
+			{
+				Asset: avax.Asset{ID: testAvaxAssetID},
+				Out: &secp256k1fx.TransferOutput{
+					Amt: exportAmount - testTxFee,
+					OutputOwners: secp256k1fx.OutputOwners{
+						Locktime:  0,
+						Threshold: 1,
+						Addrs:     []ids.ShortID{testShortIDAddrs[0]},
+					},
+				},
+			},
+			{
+				Asset: avax.Asset{ID: testAvaxAssetID},
+				Out: &secp256k1fx.TransferOutput{
+					Amt: exportAmount, // only subtract fee from one output
+					OutputOwners: secp256k1fx.OutputOwners{
+						Locktime:  0,
+						Threshold: 1,
+						Addrs:     []ids.ShortID{testShortIDAddrs[1]},
+					},
+				},
+			},
+		},
+	}
+
+	// Sort the inputs and outputs to ensure the transaction is canonical
+	avax.SortTransferableOutputs(exportTx.ExportedOutputs, Codec)
+	// Pass in a list of signers here with the appropriate length
+	// to avoid causing a nil-pointer error in the helper method
+	emptySigners := make([][]*crypto.PrivateKeySECP256K1R, 2)
+	SortEVMInputsAndSigners(exportTx.Ins, emptySigners)
+
+	ctx := NewContext()
+
+	// Test Valid Export Tx
+	if err := exportTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err != nil {
+		t.Fatalf("Failed to verify valid ExportTx: %w", err)
+	}
+
+	exportTx.syntacticallyVerified = false
+	exportTx.NetworkID = testNetworkID + 1
+
+	// Test Incorrect Network ID Errors
+	if err := exportTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ExportTx should have failed verification due to incorrect network ID")
+	}
+
+	exportTx.syntacticallyVerified = false
+	exportTx.NetworkID = testNetworkID
+	exportTx.BlockchainID = nonExistentID
+	// Test Incorrect Blockchain ID Errors
+	if err := exportTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ExportTx should have failed verification due to incorrect blockchain ID")
+	}
+
+	exportTx.syntacticallyVerified = false
+	exportTx.BlockchainID = testCChainID
+	exportTx.DestinationChain = nonExistentID
+	// Test Incorrect Destination Chain ID Errors
+	if err := exportTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ExportTx should have failed verification due to incorrect destination chain")
+	}
+
+	exportTx.syntacticallyVerified = false
+	exportTx.DestinationChain = testXChainID
+	exportedOuts := exportTx.ExportedOutputs
+	exportTx.ExportedOutputs = nil
+	// Test No Exported Outputs Errors
+	if err := exportTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ExportTx should have failed verification due to no exported outputs")
+	}
+
+	exportTx.syntacticallyVerified = false
+	exportTx.ExportedOutputs = []*avax.TransferableOutput{exportedOuts[1], exportedOuts[0]}
+	// Test Unsorted outputs Errors
+	if err := exportTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ExportTx should have failed verification due to no unsorted exported outputs")
+	}
+
+	exportTx.syntacticallyVerified = false
+	exportTx.ExportedOutputs = []*avax.TransferableOutput{exportedOuts[0], nil}
+	// Test invalid exported output
+	if err := exportTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ExportTx should have failed verification due to invalid output")
+	}
+}
+
+func TestExportTxSemanticVerify(t *testing.T) {
+
+}
diff --git a/plugin/evm/import_tx.go b/plugin/evm/import_tx.go
index 0b0d348..ae6b540 100644
--- a/plugin/evm/import_tx.go
+++ b/plugin/evm/import_tx.go
@@ -98,6 +98,10 @@ func (tx *UnsignedImportTx) SemanticVerify(
 		return permError{err}
 	}
 
+	if len(stx.Creds) != len(tx.ImportedInputs) {
+		return permError{errSignatureInputsMismatch}
+	}
+
 	// do flow-checking
 	fc := avax.NewFlowChecker()
 	//fc.Produce(vm.ctx.AVAXAssetID, vm.txFee)
@@ -122,20 +126,12 @@ func (tx *UnsignedImportTx) SemanticVerify(
 	for i, in := range tx.ImportedInputs {
 		utxoIDs[i] = in.UTXOID.InputID().Bytes()
 	}
+	// allUTXOBytes is guaranteed to be the same length as utxoIDs
 	allUTXOBytes, err := vm.ctx.SharedMemory.Get(tx.SourceChain, utxoIDs)
 	if err != nil {
 		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 +169,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 +236,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 +268,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/import_tx_test.go b/plugin/evm/import_tx_test.go
new file mode 100644
index 0000000..fcd18ac
--- /dev/null
+++ b/plugin/evm/import_tx_test.go
@@ -0,0 +1,349 @@
+// (c) 2019-2020, Ava Labs, Inc. All rights reserved.
+// See the file LICENSE for licensing terms.
+
+package evm
+
+import (
+	"testing"
+
+	"github.com/ava-labs/avalanchego/chains/atomic"
+	"github.com/ava-labs/avalanchego/ids"
+	"github.com/ava-labs/avalanchego/utils/crypto"
+	"github.com/ava-labs/avalanchego/vms/components/avax"
+	"github.com/ava-labs/avalanchego/vms/secp256k1fx"
+)
+
+func TestImportTxVerifyNil(t *testing.T) {
+	var importTx *UnsignedImportTx
+	if err := importTx.Verify(testXChainID, NewContext(), testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("Verify should have failed due to nil transaction")
+	}
+}
+
+func TestImportTxVerify(t *testing.T) {
+	var importAmount uint64 = 10000000
+	txID := ids.NewID([32]byte{0xff})
+	importTx := &UnsignedImportTx{
+		NetworkID:    testNetworkID,
+		BlockchainID: testCChainID,
+		SourceChain:  testXChainID,
+		ImportedInputs: []*avax.TransferableInput{
+			{
+				UTXOID: avax.UTXOID{
+					TxID:        txID,
+					OutputIndex: uint32(0),
+				},
+				Asset: avax.Asset{ID: testAvaxAssetID},
+				In: &secp256k1fx.TransferInput{
+					Amt: importAmount,
+					Input: secp256k1fx.Input{
+						SigIndices: []uint32{0},
+					},
+				},
+			},
+			{
+				UTXOID: avax.UTXOID{
+					TxID:        txID,
+					OutputIndex: uint32(1),
+				},
+				Asset: avax.Asset{ID: testAvaxAssetID},
+				In: &secp256k1fx.TransferInput{
+					Amt: importAmount,
+					Input: secp256k1fx.Input{
+						SigIndices: []uint32{0},
+					},
+				},
+			},
+		},
+		Outs: []EVMOutput{
+			{
+				Address: testEthAddrs[0],
+				Amount:  importAmount,
+				AssetID: testAvaxAssetID,
+			},
+			{
+				Address: testEthAddrs[1],
+				Amount:  importAmount,
+				AssetID: testAvaxAssetID,
+			},
+		},
+	}
+
+	ctx := NewContext()
+
+	// // Sort the inputs and outputs to ensure the transaction is canonical
+	avax.SortTransferableInputs(importTx.ImportedInputs)
+	SortEVMOutputs(importTx.Outs)
+
+	// Test Valid ImportTx
+	if err := importTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err != nil {
+		t.Fatalf("Failed to verify ImportTx: %w", err)
+	}
+
+	importTx.syntacticallyVerified = false
+	importTx.NetworkID = testNetworkID + 1
+
+	// // Test Incorrect Network ID Errors
+	if err := importTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ImportTx should have failed verification due to incorrect network ID")
+	}
+
+	importTx.syntacticallyVerified = false
+	importTx.NetworkID = testNetworkID
+	importTx.BlockchainID = nonExistentID
+	// // Test Incorrect Blockchain ID Errors
+	if err := importTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ImportTx should have failed verification due to incorrect blockchain ID")
+	}
+
+	importTx.syntacticallyVerified = false
+	importTx.BlockchainID = testCChainID
+	importTx.SourceChain = nonExistentID
+	// // Test Incorrect Destination Chain ID Errors
+	if err := importTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ImportTx should have failed verification due to incorrect source chain")
+	}
+
+	importTx.syntacticallyVerified = false
+	importTx.SourceChain = testXChainID
+	importedIns := importTx.ImportedInputs
+	importTx.ImportedInputs = nil
+	// // Test No Exported Outputs Errors
+	if err := importTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ImportTx should have failed verification due to no imported inputs")
+	}
+
+	importTx.syntacticallyVerified = false
+	importTx.ImportedInputs = []*avax.TransferableInput{importedIns[1], importedIns[0]}
+	// // Test Unsorted Imported Inputs Errors
+	if err := importTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ImportTx should have failed verification due to unsorted import inputs")
+	}
+
+	importTx.syntacticallyVerified = false
+	importTx.ImportedInputs = []*avax.TransferableInput{importedIns[0], nil}
+	if err := importTx.Verify(testXChainID, ctx, testTxFee, testAvaxAssetID); err == nil {
+		t.Fatal("ImportTx should have failed verification due to invalid input")
+	}
+}
+
+func TestImportTxSemanticVerify(t *testing.T) {
+	_, vm, _, sharedMemory := GenesisVM(t, false)
+
+	xChainSharedMemory := sharedMemory.NewSharedMemory(vm.ctx.XChainID)
+
+	importAmount := uint64(1000000)
+	utxoID := avax.UTXOID{
+		TxID: ids.NewID([32]byte{
+			0x0f, 0x2f, 0x4f, 0x6f, 0x8e, 0xae, 0xce, 0xee,
+			0x0d, 0x2d, 0x4d, 0x6d, 0x8c, 0xac, 0xcc, 0xec,
+			0x0b, 0x2b, 0x4b, 0x6b, 0x8a, 0xaa, 0xca, 0xea,
+			0x09, 0x29, 0x49, 0x69, 0x88, 0xa8, 0xc8, 0xe8,
+		}),
+	}
+
+	utxo := &avax.UTXO{
+		UTXOID: utxoID,
+		Asset:  avax.Asset{ID: vm.ctx.AVAXAssetID},
+		Out: &secp256k1fx.TransferOutput{
+			Amt: importAmount,
+			OutputOwners: secp256k1fx.OutputOwners{
+				Threshold: 1,
+				Addrs:     []ids.ShortID{testKeys[0].PublicKey().Address()},
+			},
+		},
+	}
+	utxoBytes, err := vm.codec.Marshal(utxo)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	evmOutput := EVMOutput{
+		Address: testEthAddrs[0],
+		Amount:  importAmount,
+		AssetID: vm.ctx.AVAXAssetID,
+	}
+	unsignedImportTx := &UnsignedImportTx{
+		NetworkID:    vm.ctx.NetworkID,
+		BlockchainID: vm.ctx.ChainID,
+		SourceChain:  vm.ctx.XChainID,
+		ImportedInputs: []*avax.TransferableInput{{
+			UTXOID: utxoID,
+			Asset:  avax.Asset{ID: vm.ctx.AVAXAssetID},
+			In: &secp256k1fx.TransferInput{
+				Amt:   importAmount,
+				Input: secp256k1fx.Input{SigIndices: []uint32{0}},
+			},
+		}},
+		Outs: []EVMOutput{evmOutput},
+	}
+
+	state, err := vm.chain.BlockState(vm.lastAccepted.ethBlock)
+	if err != nil {
+		t.Fatalf("Failed to get last accepted stateDB due to: %s", err)
+	}
+
+	if empty := state.Empty(testEthAddrs[0]); !empty {
+		t.Fatalf("Expected ethereum address to have empty starting balance.")
+	}
+
+	if err := unsignedImportTx.Verify(vm.ctx.XChainID, vm.ctx, vm.txFee, vm.ctx.AVAXAssetID); err != nil {
+		t.Fatal(err)
+	}
+	unsignedImportTx.syntacticallyVerified = false
+
+	tx := &Tx{UnsignedTx: unsignedImportTx}
+
+	// Sign with the correct key
+	if err := tx.Sign(vm.codec, [][]*crypto.PrivateKeySECP256K1R{{testKeys[0]}}); err != nil {
+		t.Fatal(err)
+	}
+
+	// Check that SemanticVerify passes without the UTXO being present during bootstrapping
+	if err := unsignedImportTx.SemanticVerify(vm, tx); err != nil {
+		t.Fatal("Should have failed to import non-existent UTXO")
+	}
+
+	if err := xChainSharedMemory.Put(vm.ctx.ChainID, []*atomic.Element{{
+		Key:   utxo.InputID().Bytes(),
+		Value: utxoBytes,
+		Traits: [][]byte{
+			testKeys[0].PublicKey().Address().Bytes(),
+		},
+	}}); err != nil {
+		t.Fatal(err)
+	}
+
+	// Check that SemanticVerify passes when the UTXO is present during bootstrapping
+	if err := unsignedImportTx.SemanticVerify(vm, tx); err != nil {
+		t.Fatalf("Semantic verification should have passed during bootstrapping when the UTXO was present")
+	}
+
+	// Check that SemanticVerify does not pass if an additional output is added in
+	unsignedImportTx.Outs = append(unsignedImportTx.Outs, EVMOutput{
+		Address: testEthAddrs[1],
+		Amount:  importAmount,
+		AssetID: vm.ctx.AVAXAssetID,
+	})
+
+	if err := unsignedImportTx.SemanticVerify(vm, tx); err == nil {
+		t.Fatal("Semantic verification should have failed due to insufficient funds")
+	}
+
+	unsignedImportTx.Outs = []EVMOutput{evmOutput}
+
+	if err := vm.Bootstrapping(); err != nil {
+		t.Fatal(err)
+	}
+
+	if err := vm.Bootstrapped(); err != nil {
+		t.Fatal(err)
+	}
+
+	vm.ctx.Bootstrapped()
+
+	// Remove the signature
+	tx.Creds = nil
+	if err := unsignedImportTx.SemanticVerify(vm, tx); err == nil {
+		t.Fatalf("SemanticVerify should have failed due to no signatures")
+	}
+
+	// Sign with the incorrect key
+	if err := tx.Sign(vm.codec, [][]*crypto.PrivateKeySECP256K1R{{testKeys[1]}}); err != nil {
+		t.Fatal(err)
+	}
+	if err := unsignedImportTx.SemanticVerify(vm, tx); err == nil {
+		t.Fatalf("SemanticVerify should have failed due to an invalid signature")
+	}
+
+	// Re-sign with the correct key
+	tx.Creds = nil
+	if err := tx.Sign(vm.codec, [][]*crypto.PrivateKeySECP256K1R{{testKeys[0]}}); err != nil {
+		t.Fatal(err)
+	}
+
+	// Check that SemanticVerify passes when the UTXO is present after bootstrapping
+	if err := unsignedImportTx.SemanticVerify(vm, tx); err != nil {
+		t.Fatalf("Semantic verification should have passed after bootstrapping with the UTXO present")
+	}
+
+	if err := unsignedImportTx.Accept(vm.ctx, nil); err != nil {
+		t.Fatalf("Accept failed due to: %w", err)
+	}
+
+	if err := unsignedImportTx.EVMStateTransfer(vm, state); err != nil {
+		t.Fatalf("EVM State Transfer failed due to: %s", err)
+	}
+
+	balance := state.GetBalance(testEthAddrs[0])
+	if balance == nil {
+		t.Fatal("Found nil balance for address receiving imported funds")
+	} else if balance.Uint64() != importAmount*x2cRate.Uint64() {
+		t.Fatalf("Balance was %d, but expected balance of: %d", balance.Uint64(), importAmount*x2cRate.Uint64())
+	}
+
+	// Check that SemanticVerify fails when the UTXO is not present after bootstrapping
+	if err := unsignedImportTx.SemanticVerify(vm, tx); err == nil {
+		t.Fatalf("Semantic verification should have failed after the UTXO removed from shared memory")
+	}
+}
+
+func TestNewImportTx(t *testing.T) {
+	_, vm, _, sharedMemory := GenesisVM(t, true)
+
+	importAmount := uint64(1000000)
+	utxoID := avax.UTXOID{
+		TxID: ids.NewID([32]byte{
+			0x0f, 0x2f, 0x4f, 0x6f, 0x8e, 0xae, 0xce, 0xee,
+			0x0d, 0x2d, 0x4d, 0x6d, 0x8c, 0xac, 0xcc, 0xec,
+			0x0b, 0x2b, 0x4b, 0x6b, 0x8a, 0xaa, 0xca, 0xea,
+			0x09, 0x29, 0x49, 0x69, 0x88, 0xa8, 0xc8, 0xe8,
+		}),
+	}
+
+	utxo := &avax.UTXO{
+		UTXOID: utxoID,
+		Asset:  avax.Asset{ID: vm.ctx.AVAXAssetID},
+		Out: &secp256k1fx.TransferOutput{
+			Amt: importAmount,
+			OutputOwners: secp256k1fx.OutputOwners{
+				Threshold: 1,
+				Addrs:     []ids.ShortID{testKeys[0].PublicKey().Address()},
+			},
+		},
+	}
+	utxoBytes, err := vm.codec.Marshal(utxo)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	xChainSharedMemory := sharedMemory.NewSharedMemory(vm.ctx.XChainID)
+
+	if err := xChainSharedMemory.Put(vm.ctx.ChainID, []*atomic.Element{{
+		Key:   utxo.InputID().Bytes(),
+		Value: utxoBytes,
+		Traits: [][]byte{
+			testKeys[0].PublicKey().Address().Bytes(),
+		},
+	}}); err != nil {
+		t.Fatal(err)
+	}
+
+	tx, err := vm.newImportTx(vm.ctx.XChainID, testEthAddrs[0], []*crypto.PrivateKeySECP256K1R{testKeys[0]})
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	importTx, ok := tx.UnsignedTx.(UnsignedAtomicTx)
+	if !ok {
+		t.Fatal("newImportTx did not return an atomic transaction")
+	}
+
+	if err := importTx.SemanticVerify(vm, tx); err != nil {
+		t.Fatalf("newImportTx created an invalid transaction")
+	}
+
+	if err := importTx.Accept(vm.ctx, nil); err != nil {
+		t.Fatalf("Failed to accept import transaction due to: %s", err)
+	}
+}
diff --git a/plugin/evm/service.go b/plugin/evm/service.go
index 8ede1b0..a844f10 100644
--- a/plugin/evm/service.go
+++ b/plugin/evm/service.go
@@ -151,7 +151,7 @@ type ExportKeyReply struct {
 func (service *AvaxAPI) ExportKey(r *http.Request, args *ExportKeyArgs, reply *ExportKeyReply) error {
 	log.Info("EVM: ExportKey called")
 
-	address, err := service.vm.ParseEthAddress(args.Address)
+	address, err := ParseEthAddress(args.Address)
 	if err != nil {
 		return fmt.Errorf("couldn't parse %s to address: %s", args.Address, err)
 	}
@@ -200,10 +200,7 @@ func (service *AvaxAPI) ImportKey(r *http.Request, args *ImportKeyArgs, reply *a
 	sk := skIntf.(*crypto.PrivateKeySECP256K1R)
 
 	// TODO: return eth address here
-	reply.Address, err = service.vm.FormatEthAddress(GetEthAddress(sk))
-	if err != nil {
-		return fmt.Errorf("problem formatting address: %w", err)
-	}
+	reply.Address = FormatEthAddress(GetEthAddress(sk))
 
 	db, err := service.vm.ctx.Keystore.GetDatabase(args.Username, args.Password)
 	if err != nil {
@@ -234,7 +231,7 @@ func (service *AvaxAPI) ImportAVAX(_ *http.Request, args *ImportArgs, response *
 	return service.Import(nil, args, response)
 }
 
-// ImportAVAX issues a transaction to import AVAX from the X-chain. The AVAX
+// Import issues a transaction to import AVAX from the X-chain. The AVAX
 // must have already been exported from the X-Chain.
 func (service *AvaxAPI) Import(_ *http.Request, args *ImportArgs, response *api.JsonTxID) error {
 	log.Info("EVM: ImportAVAX called")
@@ -244,7 +241,7 @@ func (service *AvaxAPI) Import(_ *http.Request, args *ImportArgs, response *api.
 		return fmt.Errorf("problem parsing chainID %q: %w", args.SourceChain, err)
 	}
 
-	to, err := service.vm.ParseEthAddress(args.To)
+	to, err := ParseEthAddress(args.To)
 	if err != nil { // Parse address
 		return fmt.Errorf("couldn't parse argument 'to' to an address: %w", err)
 	}
diff --git a/plugin/evm/tx.go b/plugin/evm/tx.go
index 9580bc0..7c2ebf1 100644
--- a/plugin/evm/tx.go
+++ b/plugin/evm/tx.go
@@ -4,14 +4,17 @@
 package evm
 
 import (
+	"bytes"
 	"errors"
 	"fmt"
+	"sort"
 
 	"github.com/ava-labs/coreth/core/state"
 
 	"github.com/ava-labs/avalanchego/database"
 	"github.com/ava-labs/avalanchego/ids"
 	"github.com/ava-labs/avalanchego/snow"
+	"github.com/ava-labs/avalanchego/utils"
 	"github.com/ava-labs/avalanchego/utils/codec"
 	"github.com/ava-labs/avalanchego/utils/crypto"
 	"github.com/ava-labs/avalanchego/utils/hashing"
@@ -30,12 +33,14 @@ var (
 	errNilTx             = errors.New("tx is nil")
 )
 
+// EVMOutput defines an output from EVM State created from export transactions
 type EVMOutput struct {
 	Address common.Address `serialize:"true" json:"address"`
 	Amount  uint64         `serialize:"true" json:"amount"`
 	AssetID ids.ID         `serialize:"true" json:"assetID"`
 }
 
+// EVMInput defines an input for the EVM State to be used in import transactions
 type EVMInput struct {
 	Address common.Address `serialize:"true" json:"address"`
 	Amount  uint64         `serialize:"true" json:"amount"`
@@ -43,10 +48,12 @@ type EVMInput struct {
 	Nonce   uint64         `serialize:"true" json:"nonce"`
 }
 
+// Verify ...
 func (out *EVMOutput) Verify() error {
 	return nil
 }
 
+// Verify ...
 func (in *EVMInput) Verify() error {
 	return nil
 }
@@ -115,3 +122,66 @@ func (tx *Tx) Sign(c codec.Codec, signers [][]*crypto.PrivateKeySECP256K1R) erro
 	tx.Initialize(unsignedBytes, signedBytes)
 	return nil
 }
+
+// innerSortInputsAndSigners implements sort.Interface for EVMInput
+type innerSortInputsAndSigners struct {
+	inputs  []EVMInput
+	signers [][]*crypto.PrivateKeySECP256K1R
+}
+
+func (ins *innerSortInputsAndSigners) Less(i, j int) bool {
+	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) }
+
+func (ins *innerSortInputsAndSigners) Swap(i, j int) {
+	ins.inputs[j], ins.inputs[i] = ins.inputs[i], ins.inputs[j]
+	ins.signers[j], ins.signers[i] = ins.signers[i], ins.signers[j]
+}
+
+// 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})
+}
+
+// IsSortedAndUniqueEVMInputs returns true if the EVM Inputs are sorted and unique
+// based on the account addresses
+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 9ad7411..f19c105 100644
--- a/plugin/evm/vm.go
+++ b/plugin/evm/vm.go
@@ -103,12 +103,16 @@ var (
 	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")
+	errSignatureInputsMismatch    = errors.New("number of inputs does not match number of signatures")
 	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")
+	errNoExportOutputs            = errors.New("tx has no export outputs")
+	errOutputsNotSorted           = errors.New("tx outputs not sorted")
+	errNoImportOutputs            = errors.New("tx has no outputs to import")
+	errNoExportInputs             = errors.New("tx has 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")
 )
@@ -772,17 +776,6 @@ func (vm *VM) getLastAccepted() *Block {
 	return vm.lastAccepted
 }
 
-func (vm *VM) ParseEthAddress(addrStr string) (common.Address, error) {
-	if !common.IsHexAddress(addrStr) {
-		return common.Address{}, errInvalidAddr
-	}
-	return common.HexToAddress(addrStr), nil
-}
-
-func (vm *VM) FormatEthAddress(addr common.Address) (string, error) {
-	return addr.Hex(), nil
-}
-
 // ParseAddress takes in an address and produces the ID of the chain it's for
 // the ID of the address
 func (vm *VM) ParseAddress(addrStr string) (ids.ID, ids.ShortID, error) {
@@ -871,16 +864,11 @@ func (vm *VM) GetAtomicUTXOs(
 	return utxos, lastAddrID, lastUTXOID, nil
 }
 
-func GetEthAddress(privKey *crypto.PrivateKeySECP256K1R) common.Address {
-	return PublicKeyToEthAddress(privKey.PublicKey())
-}
-
-func PublicKeyToEthAddress(pubKey crypto.PublicKey) common.Address {
-	return ethcrypto.PubkeyToAddress(
-		(*pubKey.(*crypto.PublicKeySECP256K1R).ToECDSA()))
-}
-
-func (vm *VM) GetSpendableCanonical(keys []*crypto.PrivateKeySECP256K1R, assetID ids.ID, amount uint64) ([]EVMInput, [][]*crypto.PrivateKeySECP256K1R, error) {
+// GetSpendableFunds returns a list of EVMInputs and keys (in corresponding order)
+// to total [amount] of [assetID] owned by [keys]
+// TODO switch to returning a list of private keys
+// since there are no multisig inputs in Ethereum
+func (vm *VM) GetSpendableFunds(keys []*crypto.PrivateKeySECP256K1R, assetID ids.ID, amount uint64) ([]EVMInput, [][]*crypto.PrivateKeySECP256K1R, error) {
 	// NOTE: should we use HEAD block or lastAccepted?
 	state, err := vm.chain.BlockState(vm.lastAccepted.ethBlock)
 	if err != nil {
@@ -920,12 +908,15 @@ func (vm *VM) GetSpendableCanonical(keys []*crypto.PrivateKeySECP256K1R, assetID
 		signers = append(signers, []*crypto.PrivateKeySECP256K1R{key})
 		amount -= balance
 	}
+
 	if amount > 0 {
 		return nil, nil, errInsufficientFunds
 	}
+
 	return inputs, signers, nil
 }
 
+// GetAcceptedNonce returns the nonce associated with the address at the last accepted block
 func (vm *VM) GetAcceptedNonce(address common.Address) (uint64, error) {
 	state, err := vm.chain.BlockState(vm.lastAccepted.ethBlock)
 	if err != nil {
@@ -933,3 +924,27 @@ func (vm *VM) GetAcceptedNonce(address common.Address) (uint64, error) {
 	}
 	return state.GetNonce(address), nil
 }
+
+// ParseEthAddress parses [addrStr] and returns an Ethereum address
+func ParseEthAddress(addrStr string) (common.Address, error) {
+	if !common.IsHexAddress(addrStr) {
+		return common.Address{}, errInvalidAddr
+	}
+	return common.HexToAddress(addrStr), nil
+}
+
+// FormatEthAddress formats [addr] into a string
+func FormatEthAddress(addr common.Address) string {
+	return addr.Hex()
+}
+
+// GetEthAddress returns the ethereum address derived from [privKey]
+func GetEthAddress(privKey *crypto.PrivateKeySECP256K1R) common.Address {
+	return PublicKeyToEthAddress(privKey.PublicKey())
+}
+
+// PublicKeyToEthAddress returns the ethereum address derived from [pubKey]
+func PublicKeyToEthAddress(pubKey crypto.PublicKey) common.Address {
+	return ethcrypto.PubkeyToAddress(
+		(*pubKey.(*crypto.PublicKeySECP256K1R).ToECDSA()))
+}
diff --git a/plugin/evm/vm_test.go b/plugin/evm/vm_test.go
new file mode 100644
index 0000000..8ce7825
--- /dev/null
+++ b/plugin/evm/vm_test.go
@@ -0,0 +1,133 @@
+// (c) 2019-2020, Ava Labs, Inc. All rights reserved.
+// See the file LICENSE for licensing terms.
+
+package evm
+
+import (
+	"encoding/json"
+	"testing"
+
+	"github.com/ava-labs/avalanchego/api/keystore"
+	"github.com/ava-labs/avalanchego/chains/atomic"
+	"github.com/ava-labs/avalanchego/database/memdb"
+	"github.com/ava-labs/avalanchego/database/prefixdb"
+	"github.com/ava-labs/avalanchego/ids"
+	"github.com/ava-labs/avalanchego/snow"
+	engCommon "github.com/ava-labs/avalanchego/snow/engine/common"
+	"github.com/ava-labs/avalanchego/utils/crypto"
+	"github.com/ava-labs/avalanchego/utils/formatting"
+	"github.com/ava-labs/avalanchego/utils/logging"
+	"github.com/ava-labs/coreth/core"
+	"github.com/ethereum/go-ethereum/common"
+)
+
+var (
+	testNetworkID    uint32 = 10
+	testCChainID            = ids.NewID([32]byte{'c', 'c', 'h', 'a', 'i', 'n', 't', 'e', 's', 't'})
+	testXChainID            = ids.NewID([32]byte{'t', 'e', 's', 't', 'x'})
+	nonExistentID           = ids.NewID([32]byte{'F'})
+	testTxFee               = uint64(1000)
+	startBalance            = uint64(50000)
+	testKeys         []*crypto.PrivateKeySECP256K1R
+	testEthAddrs     []common.Address // testEthAddrs[i] corresponds to testKeys[i]
+	testShortIDAddrs []ids.ShortID
+	testAvaxAssetID         = ids.NewID([32]byte{1, 2, 3})
+	username                = "Johns"
+	password                = "CjasdjhiPeirbSenfeI13" // #nosec G101
+	ethChainID       uint32 = 43112
+)
+
+func init() {
+	cb58 := formatting.CB58{}
+	factory := crypto.FactorySECP256K1R{}
+
+	for _, key := range []string{
+		"24jUJ9vZexUM6expyMcT48LBx27k1m7xpraoV62oSQAHdziao5",
+		"2MMvUMsxx6zsHSNXJdFD8yc5XkancvwyKPwpw4xUK3TCGDuNBY",
+		"cxb7KpGWhDMALTjNNSJ7UQkkomPesyWAPUaWRGdyeBNzR6f35",
+	} {
+		_ = cb58.FromString(key)
+		pk, _ := factory.ToPrivateKey(cb58.Bytes)
+		secpKey := pk.(*crypto.PrivateKeySECP256K1R)
+		testKeys = append(testKeys, secpKey)
+		testEthAddrs = append(testEthAddrs, GetEthAddress(secpKey))
+		testShortIDAddrs = append(testShortIDAddrs, pk.PublicKey().Address())
+	}
+}
+
+// BuildGenesisTest returns the genesis bytes for Coreth VM to be used in testing
+func BuildGenesisTest(t *testing.T) []byte {
+	ss := StaticService{}
+
+	genesisJSON := "{\"config\":{\"chainId\":43112,\"homesteadBlock\":0,\"daoForkBlock\":0,\"daoForkSupport\":true,\"eip150Block\":0,\"eip150Hash\":\"0x2086799aeebeae135c246c65021c82b4e15a2c451340993aacfd2751886514f0\",\"eip155Block\":0,\"eip158Block\":0,\"byzantiumBlock\":0,\"constantinopleBlock\":0,\"petersburgBlock\":0,\"istanbulBlock\":0,\"muirGlacierBlock\":0},\"nonce\":\"0x0\",\"timestamp\":\"0x0\",\"extraData\":\"0x00\",\"gasLimit\":\"0x5f5e100\",\"difficulty\":\"0x0\",\"mixHash\":\"0x0000000000000000000000000000000000000000000000000000000000000000\",\"coinbase\":\"0x0000000000000000000000000000000000000000\",\"alloc\":{\"0100000000000000000000000000000000000000\":{\"code\":\"0x7300000000000000000000000000000000000000003014608060405260043610603d5760003560e01c80631e010439146042578063b6510bb314606e575b600080fd5b605c60048036036020811015605657600080fd5b503560b1565b60408051918252519081900360200190f35b818015607957600080fd5b5060af60048036036080811015608e57600080fd5b506001600160a01b03813516906020810135906040810135906060013560b6565b005b30cd90565b836001600160a01b031681836108fc8690811502906040516000604051808303818888878c8acf9550505050505015801560f4573d6000803e3d6000fd5b505050505056fea26469706673582212201eebce970fe3f5cb96bf8ac6ba5f5c133fc2908ae3dcd51082cfee8f583429d064736f6c634300060a0033\",\"balance\":\"0x0\"}},\"number\":\"0x0\",\"gasUsed\":\"0x0\",\"parentHash\":\"0x0000000000000000000000000000000000000000000000000000000000000000\"}"
+
+	genesis := &core.Genesis{}
+	if err := json.Unmarshal([]byte(genesisJSON), genesis); err != nil {
+		t.Fatalf("Problem unmarshaling genesis JSON: %w", err)
+	}
+	genesisReply, err := ss.BuildGenesis(nil, genesis)
+	if err != nil {
+		t.Fatalf("Failed to create test genesis")
+	}
+	return genesisReply.Bytes
+}
+
+func NewContext() *snow.Context {
+	ctx := snow.DefaultContextTest()
+	ctx.NetworkID = testNetworkID
+	ctx.ChainID = testCChainID
+	ctx.AVAXAssetID = testAvaxAssetID
+	ctx.XChainID = ids.Empty.Prefix(0)
+	aliaser := ctx.BCLookup.(*ids.Aliaser)
+	aliaser.Alias(testCChainID, "C")
+	aliaser.Alias(testCChainID, testCChainID.String())
+	aliaser.Alias(testXChainID, "X")
+	aliaser.Alias(testXChainID, testXChainID.String())
+
+	// SNLookup might be required here???
+	return ctx
+}
+
+// GenesisVM creates a VM instance with the genesis test bytes and returns
+// the channel use to send messages to the engine, the vm, and atomic memory
+func GenesisVM(t *testing.T, finishBootstrapping bool) (chan engCommon.Message, *VM, []byte, *atomic.Memory) {
+	genesisBytes := BuildGenesisTest(t)
+	ctx := NewContext()
+
+	baseDB := memdb.New()
+
+	m := &atomic.Memory{}
+	m.Initialize(logging.NoLog{}, prefixdb.New([]byte{0}, baseDB))
+	ctx.SharedMemory = m.NewSharedMemory(ctx.ChainID)
+
+	// NB: this lock is intentionally left locked when this function returns.
+	// The caller of this function is responsible for unlocking.
+	ctx.Lock.Lock()
+
+	userKeystore := keystore.CreateTestKeystore()
+	if err := userKeystore.AddUser(username, password); err != nil {
+		t.Fatal(err)
+	}
+	ctx.Keystore = userKeystore.NewBlockchainKeyStore(ctx.ChainID)
+
+	issuer := make(chan engCommon.Message, 1)
+	vm := &VM{
+		txFee: testTxFee,
+	}
+	err := vm.Initialize(
+		ctx,
+		prefixdb.New([]byte{1}, baseDB),
+		genesisBytes,
+		issuer,
+		[]*engCommon.Fx{},
+	)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	return issuer, vm, genesisBytes, m
+}
+
+func TestVMGenesis(t *testing.T) {
+	_, _, _, _ = GenesisVM(t, true)
+}