Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Maximum deposit count #26

Closed
daejunpark opened this issue Apr 12, 2019 · 2 comments

Comments

Projects
None yet
3 participants
@daejunpark
Copy link

commented Apr 12, 2019

What was wrong?

The current contract does not work as expected if the deposit count becomes 2** DEPOSIT_CONTRACT_TREE_DEPTH. (Note that a Merkle tree of height DEPOSIT_CONTRACT_TREE_DEPTH should be able to contain 2** DEPOSIT_CONTRACT_TREE_DEPTH leaf items.)

Here is a problematic scenario.

Suppose deposit is called when the current self.deposit_count is 2** DEPOSIT_CONTRACT_TREE_DEPTH - 1.

Then, after the following loop, i becomes DEPOSIT_CONTRACT_TREE_DEPTH, since index + 1 is 2** DEPOSIT_CONTRACT_TREE_DEPTH and thus the if condition is always true for all loop iterations.

for _ in range(DEPOSIT_CONTRACT_TREE_DEPTH):
if (index+1) % power_of_two != 0:
break
i += 1
power_of_two *= 2

Thus, the following assignment leads to the index out of bounds error:

(BTW, the computed value is correct even in this case, which is the root of the fully filled Merkle tree.)

NOTE:

The index out of bounds error itself can be avoided by increasing the size of self.branch, but in that case, note that get_deposit_root will return a wrong value (i.e., sha3(...sha3(sha3(0,0),sha3(0,0))...)) when self.deposit_count becomes 2** DEPOSIT_CONTRACT_TREE_DEPTH.

How can it be fixed?

It is non-trivial to fix (without increasing the gas cost) the contract to be able to receive 2**DEPOSIT_CONTRACT_TREE_DEPTH deposits, due to the current algorithm of get_deposit_root.

Thus, if it is OK to restrict the maximum deposit count to 2**DEPOSIT_CONTRACT_TREE_DEPTH - 1 instead of 2**DEPOSIT_CONTRACT_TREE_DEPTH, then adding the following assert at the beginning of deposit will be a quick solution:

assert deposit_count < MAX_DEPOSIT_COUNT

where:

MAX_DEPOSIT_COUNT: constant(uint256) = 4294967295 # 2**DEPOSIT_CONTRACT_TREE_DEPTH - 1

@daejunpark daejunpark changed the title maximum deposit count Maximum deposit count Apr 12, 2019

@yzhang90

This comment has been minimized.

Copy link

commented Apr 12, 2019

Another possible fix is: increase size of branch to DEPOSIT_CONTRACT_TREE_DEPTH + 1 and when size becomes 2** DEPOSIT_CONTRACT_TREE_DEPTH, get_deposit_root just return branch[DEPOSIT_CONTRACT_TREE_DEPTH]

@djrtwo

This comment has been minimized.

Copy link
Contributor

commented May 8, 2019

After discussing with @daejunpark today, we decided that it makes sense to just put the assert deposit_count < MAX_DEPOSIT_COUNT to ensure that the tree doesn't hit this edge case. To note, reaching this point with the constants as currently defined is impossible do to the uni-directional nature of transfers from eth1 to eth2 and the total ether supply (< 130M).

@NIC619 Can you handle this edit?

NIC619 added a commit to NIC619/deposit_contract-1 that referenced this issue May 9, 2019

Fix ethereum#26:
prevent `deposit_count` reaches `2**DEPOSIT_CONTRACT_TREE_DEPTH - 1`

@NIC619 NIC619 referenced this issue May 9, 2019

Merged

Implement optimizations suggested in the issues #39

2 of 4 tasks complete

@NIC619 NIC619 closed this in e357f37 May 22, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.