challengeExit() doesn't correctly verify a challenge

[smartcontracts]

challengeExit(), reproduced below, is only checking that a later spend by a UTXO's owner exists and does not check that the spend is actually spending the exiting UTXO.

https://github.com/omisego/plasma-mvp/blob/4b119a80dd20e2dd8bb4b4cb2dda67d3b88d6f40/plasma/root_chain/contracts/RootChain/RootChain.sol#L167-L182

Challenges are valid in the case that a UTXO has either already been exited, that the UTXO was spent in a later transaction, or that the UTXO was created from an input that was already spent. So we really need to verify that there exists a valid transaction that spends the UTXO. Currently we're just verifying that there exists a valid transaction spent by the owner of the UTXO. This process should look like:

1. Check that the challenge tx is included in the referenced block and that it has correct signatures.
2. Check that the exiting UTXO is included as an input to the challenge tx OR that the challenge tx comes before the exiting UTXO and both have a common input.

Here's a test case that demonstrates the problem:

def test_invalid_challenge_exit(t, u, root_chain):
    owner, value_1, key = t.a1, 100, t.k1
    null_address = b'\x00' * 20

    # Create a deposit
    tx1 = Transaction(0, 0, 0, 0, 0, 0,
                      owner, value_1, null_address, 0, 0)
    tx_bytes1 = rlp.encode(tx1, UnsignedTransaction)
    root_chain.deposit(tx_bytes1, value=value_1)

    # Create an exit for the first deposit
    merkle = FixedMerkle(16, [tx1.merkle_hash], True)
    proof1 = merkle.create_membership_proof(tx1.merkle_hash)
    confirmSig1 = confirm_tx(tx1, root_chain.getChildChain(1)[0], key)
    sigs1 = tx1.sig1 + tx1.sig2 + confirmSig1
    exitId1 = 1 * 1000000000 + 0 * 10000 + 0
    root_chain.startExit(exitId1, tx_bytes1, proof1, sigs1, sender=key)

    # Create a second deposit
    tx2 = Transaction(0, 0, 0, 0, 0, 0,
                      owner, value_1, null_address, 0, 0)
    tx_bytes2 = rlp.encode(tx2, UnsignedTransaction)
    root_chain.deposit(tx_bytes2, value=value_1)

    # Spend the second (unrelated) deposit
    tx3 = Transaction(2, 0, 0, 0, 0, 0,
                      owner, value_1, null_address, 0, 0)
    tx3.sign1(key)
    tx_bytes3 = rlp.encode(tx3, UnsignedTransaction)

    merkle2 = FixedMerkle(16, [tx3.merkle_hash], True)
    proof2 = merkle2.create_membership_proof(tx3.merkle_hash)
    root_chain.submitBlock(merkle2.root, root_chain.currentChildBlock())

    confirmSig2 = confirm_tx(tx3, root_chain.getChildChain(3)[0], key)

    sigs2 = tx3.sig1 + tx3.sig2
    exitId2 = 3 * 1000000000 + 0 * 10000 + 0

    # The exit should exist before
    assert root_chain.exits(exitId1) == ['0x' + owner.hex(), 100, exitId1]
    assert root_chain.exitIds(exitId1) == exitId1

    # Challenge the exit with an unrelated spend
    with pytest.raises(TransactionFailed):
        root_chain.challengeExit(exitId2, exitId1, tx_bytes3, proof2, sigs2, confirmSig2)

    # The exit should also exist afterwards because this challenge is invalid
    assert root_chain.exits(exitId1) == ['0x' + owner.hex(), 100, exitId1]
    assert root_chain.exitIds(exitId1) == exitId1

[smartcontracts]

An error while creating my tests also revealed another problem. Replacing proof2 with proof1 (a completely unrelated Merkle proof) does not throw during challengeExit, suggesting that Merkle proofs aren't being correctly validated.

    # Challenge the exit with an unrelated spend
    root_chain.challengeExit(exitId2, exitId1, tx_bytes3, proof1, sigs2, confirmSig2)

[smartcontracts]

Here's a quick fix for the first case - there's probably a better way to do this but this is a PoC. This still doesn't verify the case where the challenging tx comes before the exiting tx and they share an input.

    function txHasInput(bytes txBytes, uint256 utxoPos)
        internal
        view
        returns (bool)
    {
        var txList = txBytes.toRLPItem().toList(11);

        uint256 blknum = utxoPos / 1000000000;
        uint256 txindex = (utxoPos % 1000000000) / 10000;
        uint256 oindex = utxoPos - blknum * 1000000000 - txindex * 10000;

        bool check1 = txList[0].toUint() == blknum && txList[1].toUint() == txindex && txList[2].toUint() == oindex;
        bool check2 = txList[3].toUint() == blknum && txList[4].toUint() == txindex && txList[5].toUint() == oindex;

        return check1 || check2;
    }

    // @dev Allows anyone to challenge an exiting transaction by submitting proof of a double spend on the child chain
    // @param cUtxoPos The position of the challenging utxo
    // @param eUtxoPos The position of the exiting utxo
    // @param txBytes The challenging transaction in bytes RLP form
    // @param proof Proof of inclusion for the transaction used to challenge
    // @param sigs Signatures for the transaction used to challenge
    // @param confirmationSig The confirmation signature for the transaction used to challenge
    function challengeExit(uint256 cUtxoPos, uint256 eUtxoPos, bytes txBytes, bytes proof, bytes sigs, bytes confirmationSig)
        public
    {
        uint256 cTxindex = (cUtxoPos % 1000000000) / 10000;
        bytes32 root = childChain[cUtxoPos / 1000000000].root;
        uint256 priority = exitIds[eUtxoPos];

        var txHash = keccak256(txBytes);
        var confirmationHash = keccak256(txHash, root);
        var merkleHash = keccak256(txHash, sigs);
        address owner = exits[priority].owner;

        require(owner == ECRecovery.recover(confirmationHash, confirmationSig));
        require(merkleHash.checkMembership(cTxindex, root, proof));

        require(txHasInput(txBytes, eUtxoPos));

        delete exits[priority];
        delete exitIds[eUtxoPos];
    }

I moved the txHasInput check out of challengeExit because you'll get a StackTooDeepException otherwise.

[smartcontracts]

Fixed in https://github.com/omisego/plasma-mvp/commit/9493dffd7589c7bcc660dbe24377e7e7f5ccd9a5