Since with rlp you can encode/decode dynamic lists, I think we should support a variable number of inputs and outputs for each tx.

Here is how we could represent these in the Msg of the Tx struct on the childchain.

Also, is the sender address still necessary?

type SpendMsg struct {
    Inputs    Inputs[]
    Outputs  Outputs[]
    Fee         uint64
}

type Input struct {
    Blknum uint64
    Txindex uint16
    Oindex uint8
    DepositNum uint64
    Address common.Address
}

type Output struct {
    Address common.Address
    Denom uint64
}

The truffle tests are beginning to become unreadable. Refactoring is in order

The position of the fee utxo should be min(2^16-1, blk.numTxns), when calculated in startFeeExit

I think a future optimization to be considered is removing the requirement for 65 zero bytes to be passed in for the signature of a 1 input transaction. It would add a bit more logic to the rootchain, but reduces the block size of the sidechain (allowing more txs in a block).

All past tests never touched the Validator.sol's checkSig function. In the mean time we should also write tests for Validator.sol and ByteUtils.sol

When an exit is successfully challenged, the exit is deleted from the exits mapping but it isn't deleted from the PriorityQueue.

This means that in finalizeExit, there will be a loop to process a "zero-valued" exit struct since the exit associated with the priority has been deleted. As far as I can tell, there are no bugs that arise from this with the current implementation, but it is still a waste of gas to process a useless "zero-valued" exit.

Perhaps we can have a check for a zero valued struct and if it is zero, we can simply continue to the next iteration.

Keep track of total Wei in balances mapping. Let this number be stored in variable owed

When someone calls finalizeExit, validate that
this.balance - owed >= exit.amount

If check passes, finalize exit
Else, continue loop. (Note it may be better to simply return in this case. Open to debate on this.)

This issue is being reported as part of the ongoing audit being conducted by Authio for Kyokan.

startDepositExit(uint nonce, uint committedFee) allows the owner of the newly created deposit to set an arbitrary committed fee. In the case where the owner of a deposit does not spend their deposit on the plasma chain, the fee amount cannot be challenged, as the deposit is not included in a block. As the deposit exit queue relies on successfully exiting its highest-priority deposit, an attacker can halt the queue by creating an exit that will never finalize, claiming a committedFee >= amount + minExitBond

Since we are no longer creating deposit blocks on sidechain, there is no need to create an empty merkle tree with our deposit and store the hash. Instead we can just store the hash of the transaction itself as the "block hash". This makes it easier to validate on the sidechain.

We should update the README and add contribution guidelines. README should have a short introduction regarding our implementation of plasma and any important specs regarding the root contract.

All of the points here should be further expanded and eventually be moved into docs/ possibly under subfolder spec/

In MVP:

in one queue priority is (blocknum, txIndex, OIndex) and in another queue it’s just (DepositNonce)

This is to prevent the attack mentioned in safeDeposit where a validator can submit a malicious block before the deposit gets included. The solution of having users submit the block that they have validated allows users to claim that the only block they've validated is block 1 to get a high priority and DOS the network.
Thus we use two seperate queues to process Deposits and regular UTXO's and avoid this problem

For MoreVP, since regular transactions can have their priorities be dependent on an input we need to change this

in the queue that processes regular transaction exits the priority is (blocknum, txIndex, OIndex, DepositNonce)
and the other queue processes deposits and ANY TX'S THAT ONLY SPEND DEPOSITS exits it is just (DepositNonce)

so in the case where a tx spends a deposit and a regular utxo, that tx gets the priority of its regular utxo input position

in the case where tx has only deposit inputs, the priority is just the latest deposit and the tx is placed in deposit queue

Every solidity file, regardless of contract/library should have tests written for them.

I think the check that the transaction, handed in for a deposit-challenge, is actually spending deposit is missing. Currently, only the owner is double checked, but this should not be enough

Tendermint uses RIPEMD160 as its hash function when forming blocks. We should adjust the root contract to do the same.

Use of RIPEMD160 on tendermint can be seen here:
https://github.com/tendermint/tendermint/blob/master/types/tx.go#L19

• Merge all compatibility changes to master - @laskdaf
• Implement exiting fees @legengliu
• Implement non-final block submission (see SubmitBlock optimization in plasma-research)
• Include Tx position in exit struct and event

This issue is being reported as part of the ongoing audit being conducted by Authio for Kyokan.
The methods challengeExit and challengeFeeMismatch are subject to a transaction order dependence/race condition vulnerability. If a member of the community transmits a call to challengeExit or challengeFeeMismatch then a malicious party can see that and transmit the same data to challengeExit or challengeFeeMismatch with a higher gas price and receive the exit bond. This has two consequences:
(1) It removes some of the incentive of the community to watch for bad behavior, since they won't get the bond reward.
(2) If a person wants to behave maliciously they can submit their malicious exit then wait to see if someone will notice. When a person submits a challenge they can then race it and receive their own bond back. This means that malicious parties can submit malicious exits and only risk losing gas fees.

Most transactions only make use of one input, causing a lot of zero bytes to be included in the transactions.

The transaction should be formed with variable inputs/outputs capped at 2

Change logs are incredibly useful and I think users of this contract will greatly benefit from having a human readable summary of all changes that occur over time. This change log should work with semantic versioning. I suggest we follow these guidelines

Tests fail with 4.21 compiler. We should look into either changing the contracts with the language updates or wait until contracts are stable and then change to latest solidity version then

• Introduce RLPReaderStrict which enforces byte size for the uint data type (32 bytes)

• Additional checks in calcPosition.
  - txPos[0] <= lastComittedblock, txPos[1] < blk.numTxs

• decodeTransaction checks every field in the the txList to enforce validity in addition to the total payload size.

• add an extra transaction signature check when challenging

• More sanity checks when submitting blocks and exiting the fee transaction

Switch bond from proportional bond currently, to a constant bond. This stops bond from being unnecessarily high for large UTXO's. If constant bond is high enough, it will still be an incentive for fraud bounty hunters. #7 will certainly cause a bug with this implementation. since exit's bond will not be 0 in this case.

Currently we have users sign over the RLP-encoded tx.

If a user owns the same UTXO position on two different plasma chains and they spend the UTXO on one chain, a malicious receiver can publish the same transaction on the other chain and take both UTXOs.

Solution: User signs over the RLP-encoded tx as well as the rootchain smart-contract address.

Priority Queue implementation is broken. See failing tests in: #22

Currently the fee in a block is the aggregate FeeAmounts of all UTXOs included in that block.

So if a block contains UTXOs A, B, C:

FeeUTXO has amount = Fee(A) + Fee(B) + Fee(C)

However, if input to A decides not to send confirm sigs and exits on rootchain. Then FeeUTXO amount does not change, even if one of its inputs, A is not valid.

The correct FeeUTXO amount in this scenario would be:
FeeUTXO has amount = Fee(B) + Fee(C)

Thus with current implementation, anytime any input to an included UTXO is successfully exited, the Fee for that block has an incorrect amount that will inflate the number of Ether in the sidechain.

Possible Solutions:

1. Have users commit to any fee they spent in a transaction (whether included or not) during StartExit so that they can exit UTXO.Amount - AlreadySpentFee
   Then we also need a way to challenge an Exit by proving that a spend of the UTXO was included on sidechain with a Fee that is different from the claimed fee by user during startExit. (Note: No confirm sigs are necessary for this particular challenge)

2. Possibly others, but I think they will be more complicated than the above fix

Since, we are transitioning from using a transaction simple merkle tree with constant depth 16 to a merkle tree of the app state we will have to refactor Merkle proof.

This should be changed once we finalize how things work on the child chain.

In order to take care of the direct-descendant, double withdrawal attack (https://ethresear.ch/t/plasma-vulnerabiltity-sybil-txs-drained-contract/1654), keep a mapping of previously finalized exits (maybe priority => True/False) and allow someone to challenge an exit by proving that the exit's inputs have already been withdrawn.

Travis CI fails every now and then because of timing issues. Change Travis CI file to make tests pass deterministically.

This issue is being reported as part of the ongoing audit being conducted by Authio for Kyokan.

Both startTransactionExitHelper and challengeFeeMismatch do not correctly check the signatures of transactions. The former checks that the externally-passed-in confirm signature matches a portion of the txBytes, but the portion matched is not required to be included in the signed portion of the transaction, meaning it can be spoofed by the sender. The latter case allows the operator to produce blocks that include exiting transactions in order to exit them. While this would be grounds for a mass exit, the operator is able to halt exits by doing this.

Since block ordering scheme won't work we need to change how deposits are handled.

Current idea: We add the deposits in during beginBlock. Will need to finalize sidechain design before changing rootchain.

Now that deposit blocks and validator blocks have separate numbering, validator can be certain which block number he is submitting. Thus, we can pass in a block number as part of submitBlock transaction. This allows the child chain to continue creating blocks before presumed finalization on the rootchain. Since one can continue building blocks in a specified order, if a submitBlock ever gets reorged out of existence, validator can simply fill in the gaps by resubmitting the transaction.

This allows the child chain to run faster as it does not need to wait for presumed finality on the rootchain before working on the next block.

To avoid issue of validator refusing to submitBlocks: We make submitBlock take 3 arguments (blockNum, root, signature).
Where signature is the authority's signature over (blockNum, root). This allows anyone to fill in the gaps. This way we can make sure the validator was the one who submitted the block with that specified root at that specified position without requiring they call submitBlock themselves

One may try to submit a block n + 1 that is inconsistent with block n if block n is reorged out of existence and try to exit.

Possible Solutions:
Allow people to challenge exit by proving that a previous block is no longer on rootchain (Issue: Validator may DOS network by refusing to fill in gap)
Have users monitor mempool and save any submit block transactions submitted by validator and resubmit if transaction gets reorged.

Changes:

• Don't pass in txBytes
• Pass in address to deposit msg.value to
• Pass in bool or use some type of flag to distinguish when the depositor will deposit to an address other than their own

Pros:
Allows for deposits to any address while adding a little user safety by using some type of flag. User doesn't need to construct the txBytes themselves.

Cons:
Slightly more complexity and less clean.

A way to get around passing in txBytes is to build an on chain rlp encoder or as proposed on omisego/plasma-mvp in issue 65 make a deposit tx hash only be hash(address, value).

Pending deposits get stored in a queue. Upon a submit block from validator, all pending deposits get added first and then the submit block gets added first.

Concerns:
Storing deposits in queue may be expensive. Look into storing in memory vs storage

This issue is being reported as part of the ongoing audit being conducted by Authio for Kyokan.
Severity: Note
The signature library used doesn't throw on signatures which have the form (r, -s mod n), and so accepts the non-canonical signature form. https://eklitzke.org/bitcoin-transaction-malleability is a good reference on signature malleability. We haven't found a case where this problem can be used to have an affect on the application, but given the complexity of the plasma chain system and its extensive use of signatures best practice would be to have the signature library reject the non-canonical form.
Remediation is to include a check that s < n/2 in the ECDSA library.

If an output it over a week old, it should not have to be placed in the exit queue. Outputs within the last week should go into the queue

The output should rather go into a Pending state and be finalized independently.

Most of the library contracts can be replaced with using OpenZeppelin contracts instead with little work. Should do this after we have full test coverage so we're sure we aren't breaking anything.

Tendermint updated their simple merkle tree to the following:

leaf nodes and inner nodes have different hashes. 
This is for "second pre-image resistance", to prevent the proof to an inner node being valid as the proof of a leaf. 
The leaf nodes are SHA256(0x00 || leaf_data), and inner nodes are SHA256(0x01 || left_hash || right_hash)

This can be seen here

Validators should not have to create and propagate deposit blocks. Instead, we simply validate that a deposit occurred by checking the rootchain and making sure that it hasn't already been spent in a transaction.

Proposal:
Have validator submitted blocks increment by 1000's
Have deposit fill numbers 1-999.

Inspired by OmiseGo approach: omgnetwork/plasma-mvp#50

Users should be allowed to approve/revoke another address to exit on their behalf with a time limit (or none).

PlasmaMVP that supports a deposit/exit of any erc20 token.

Construct a way for multiple validators via the rootchain. If possible to do this through an account model would incredibly useful. Leave the utxo model for regular spends be keep a track of accounts for validators/delegators (only allow withdraws of fees/stake). This would allow for x/stake, x/slashing from sdk to be used on the sidechain. Fee model of the sdk could be leveraged. We could get rid of committed fee as well as the fee utxo.

finalizeExit should not be required to process every single valid exit. Every iteration should check if enough gas is available to complete that one iteration and if not, return to avoid the the transaction from reverting.

if the function reverts on for example the third iteration, the previous two successfully exited startExits will have to processed again.

• Transaction Exit test- @legengliu @laskdaf
• Two queues @hamdiallam
• Tracked Exits @legengliu @hamdiallam
• Finalize exit/revert @laskdaf
• SubmitBlock Optimization - @AdityaSripal
• Align interfaces with SideChain

Deposits face the same issue transaction exits do when dealing with ordering of an exiting deposit. Currently we use the nonce as its priority, however earlier deposits could therefore delay exits since we pop from the top of the queue to see if pending a deposit exit is older than one week.

This can be fixed by making the priority value inserted into the priority queue be:
block.time << 128 | nonce

We do not need to take into account a deposits "age" as we do with transactions because they cannot be faked since they are logged by the rootchain. They can only be invalid and therefore challenged.

• Comment code with all remaining work to be done for full, correct implementation of Minimum Viable Plasma. Someone should be able to read through the comments and know exactly what is left to be implemented and where in the code they need to implement their changes.
• Fix obvious known bugs in the codebase
• Release version 0.1.0 with latest work on Minimum Viable Plasma
• Fork rootchain repo to start work on More Viable Plasma.

A malicious validator can steal a depositor's funds.

Let’s say I want to deposit onto a child chain. I validate the child chain upto its most recent block (Block n). I submit a deposit transaction. A malicious validator sees my transaction in flight and produces an invalid block (Block n+1) by creating a UTXO out of thin air equal to my deposit. He can try to get his transaction processed by the root chain first by submitting the tx with a very high gasPrice. Thus, on the root chain his invalid block shows up before my deposit. Everyone exits with the UTXO’s from previous block. The validator’s fake UTXO can exit before mine, and he can steal my money.

Proposed solution: We keep track of the number of blocks that have been submitted by the validator (call this counter). When you deposit, you also pass in the last validator-submitted block you saw. In the case above, I pass in n as an argument to deposit. Inside deposit, if the argument is not equal to counter, then we reject the deposit. The depositor then sees the new submitted block and chooses if he still want to deposit in light of this new information. Since blocks can only be submitted by validators in 6-block intervals, this isn’t too much of a burden on a depositor.

Currently, when processing exits we get the exit at the top of the priority queue. Since our priorities are determined by when the utxo was created on the child chain, it is possible to delay a majority of withdrawals from the child chain for a large amount of time.

Assume probabilistic finality occurs in x blocks.
To delay for exits for up to a year, one would do the following.

1. Deposit a small amount of eth
2. Every x blocks submit a transaction creating a 2 utxo's
3. repeat step 2 51 times with 1 of the created utxo's

To prevent a majority of withdrawals for a year, submit an exit for your youngest utxo. Right before 1 week is up, submit a withdrawal for your next youngest utxo. In each case, the newer withdrawals will have a better priority and it's 1 week challenge period will start fresh.

Possible Solutions:

• Allow users to finalize an exit by passing in their priority. If the corresponding exit is > 1 week, finalize it and add a flag to remove it from the pq once it is the min.

• As per mvp spec, limit priorities to be no longer than the oldest block younger than 1 week old. Therefore a exit that is almost done with it's challenge period can never be put behind a exit that just started it's challenge period.

The second solution should be more efficient and will be easier to implement. Thoughts?

how to avoid double spent at the end of the exited duration ?
I am not sure it is because of the Tx "finalizeExits"

startExit: When a user decides to exit for any reason, they will call startExit() and their pending exit will be added to a priority queue that has a 1 week challenge period. This function requires a bond.

challengeExit: If any users notice an invalid withdrawal attempt, they may challenge this exit by providing the relevant information. If their challenge is successful, they will be awarded the bond associated with the exit attempt.

finalizeExits: This function will finalize any pending exits that have been in the priority queue for longer than a week. If the exit attempt has not been invalidated by a successful challenge then it will be eligible for withdrawal.

withdraw: Allows users to withdraw any balance that avaliable after the successful processing of an exit.

Changes that need to be made:

• CheckMembership()
  When checking for the inclusion of a tx in a block, checkmembership should see if the sha256(txbytes) is included into the reported header for that block. The number of txs in a block will be variable and this should be taken into account.

• RLP Decoding
  Currently the rootchain RLP decodes using the SpendMsg format on the side chain. This needs to be adjusted as the txbytes correspond to the BaseTx struct. BaseTx has two fields, SpendMsg (actual plasma tx) and a Signature array.

• Switch to sha256 when hashing txbytes (note that tx sigs use keccak256)
  see #21

• Confirmation Hash
  Confirmation Hash should be Keccak256(abi.encodePacket(txHash, blockHash)) . Hashing with sigs need to be deleted.

• Handling of Fees
  Allow submitBlock() to accept the header (data hash) of a block and a fee associated with it.

To solve the issue brought up here: https://ethresear.ch/t/plasma-vulnerabiltity-sybil-txs-drained-contract/1654

Confirm sigs of the inputs must be included in transaction. Transaction structure must now be modified

[Blknum1, TxIndex1, Oindex1, Amount1, ConfirmSig1, Blknum2, TxIndex2, Oindex2, Amount2, ConfirmSig2, NewOwner, Denom1, NewOwner, Denom2, Fee]

Here ConfirmSig1-1 is the first confirm sig from the first input, confirm sig is the second confirm sig from the first input, etc.
If there is no confirm sig for the given position, replace with a zero-bytes.

We must also include the signatures since that is how it is stored in the merkle tree in child-chain blocks.

Changes to be made:
Deposit, StartExit and ChallengeExit must be changed to handle new transaction structure

Note Possible Confusion: We are not including confirm sig for transaction itself, we are including confirm sigs of the INPUTS

Consider Transactions A -> B -> C:
Only one input and output for each transaction for simplicity sake.

The Transaction B->C will include the confirm sig A sent to B for the transaction A->B.

The slice function in BytesUtil is internal, meaning the bytecode is copied to the importing contracts at compile time.

we have more than 1 library using BytesUtil which then gets compiled into PlasmaMVP. Check that the bytecode is not duplicated when compiling PlamaMVP.sol