prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  is_genesis_trigger fails to verify deposit merkle branch
  ## Issue
  Deposits are processed against empty state with undefined `eth1_data` while `genesis_eth1_data` should be in place.
  
  
  </issue>
  <code>
  [start of deposit_contract/contracts/validator_registration.v.py]
  1 MIN_DEPOSIT_AMOUNT: constant(uint256) = 1000000000  # Gwei
  2 DEPOSIT_CONTRACT_TREE_DEPTH: constant(uint256) = 32
  3 MAX_DEPOSIT_COUNT: constant(uint256) = 4294967295 # 2**DEPOSIT_CONTRACT_TREE_DEPTH - 1
  4 PUBKEY_LENGTH: constant(uint256) = 48  # bytes
  5 WITHDRAWAL_CREDENTIALS_LENGTH: constant(uint256) = 32  # bytes
  6 AMOUNT_LENGTH: constant(uint256) = 8  # bytes
  7 SIGNATURE_LENGTH: constant(uint256) = 96  # bytes
  8 
  9 Deposit: event({
  10     pubkey: bytes[48],
  11     withdrawal_credentials: bytes[32],
  12     amount: bytes[8],
  13     signature: bytes[96],
  14     index: bytes[8],
  15 })
  16 
  17 branch: bytes32[DEPOSIT_CONTRACT_TREE_DEPTH]
  18 deposit_count: uint256
  19 
  20 # Compute hashes in empty sparse Merkle tree
  21 zero_hashes: bytes32[DEPOSIT_CONTRACT_TREE_DEPTH]
  22 @public
  23 def __init__():
  24     for i in range(DEPOSIT_CONTRACT_TREE_DEPTH - 1):
  25         self.zero_hashes[i + 1] = sha256(concat(self.zero_hashes[i], self.zero_hashes[i]))
  26 
  27 
  28 @private
  29 @constant
  30 def to_little_endian_64(value: uint256) -> bytes[8]:
  31     # Reversing bytes using bitwise uint256 manipulations
  32     # Note: array accesses of bytes[] are not currently supported in Vyper
  33     # Note: this function is only called when `value < 2**64`
  34     y: uint256 = 0
  35     x: uint256 = value
  36     for _ in range(8):
  37         y = shift(y, 8)
  38         y = y + bitwise_and(x, 255)
  39         x = shift(x, -8)
  40     return slice(convert(y, bytes32), start=24, len=8)
  41 
  42 
  43 @public
  44 @constant
  45 def get_deposit_root() -> bytes32:
  46     node: bytes32 = 0x0000000000000000000000000000000000000000000000000000000000000000
  47     size: uint256 = self.deposit_count
  48     for height in range(DEPOSIT_CONTRACT_TREE_DEPTH):
  49         if bitwise_and(size, 1) == 1:  # More gas efficient than `size % 2 == 1`
  50             node = sha256(concat(self.branch[height], node))
  51         else:
  52             node = sha256(concat(node, self.zero_hashes[height]))
  53         size /= 2
  54     return node
  55 
  56 
  57 @public
  58 @constant
  59 def get_deposit_count() -> bytes[8]:
  60     return self.to_little_endian_64(self.deposit_count)
  61 
  62 
  63 @payable
  64 @public
  65 def deposit(pubkey: bytes[PUBKEY_LENGTH],
  66             withdrawal_credentials: bytes[WITHDRAWAL_CREDENTIALS_LENGTH],
  67             signature: bytes[SIGNATURE_LENGTH]):
  68     # Avoid overflowing the Merkle tree (and prevent edge case in computing `self.branch`)
  69     assert self.deposit_count < MAX_DEPOSIT_COUNT
  70 
  71     # Validate deposit data
  72     deposit_amount: uint256 = msg.value / as_wei_value(1, "gwei")
  73     assert deposit_amount >= MIN_DEPOSIT_AMOUNT
  74     assert len(pubkey) == PUBKEY_LENGTH
  75     assert len(withdrawal_credentials) == WITHDRAWAL_CREDENTIALS_LENGTH
  76     assert len(signature) == SIGNATURE_LENGTH
  77 
  78     # Emit `Deposit` log
  79     amount: bytes[8] = self.to_little_endian_64(deposit_amount)
  80     log.Deposit(pubkey, withdrawal_credentials, amount, signature, self.to_little_endian_64(self.deposit_count))
  81 
  82     # Compute `DepositData` root
  83     zero_bytes32: bytes32 = 0x0000000000000000000000000000000000000000000000000000000000000000
  84     pubkey_root: bytes32 = sha256(concat(pubkey, slice(zero_bytes32, start=0, len=64 - PUBKEY_LENGTH)))
  85     signature_root: bytes32 = sha256(concat(
  86         sha256(slice(signature, start=0, len=64)),
  87         sha256(concat(slice(signature, start=64, len=SIGNATURE_LENGTH - 64), zero_bytes32)),
  88     ))
  89     node: bytes32 = sha256(concat(
  90         sha256(concat(pubkey_root, withdrawal_credentials)),
  91         sha256(concat(amount, slice(zero_bytes32, start=0, len=32 - AMOUNT_LENGTH), signature_root)),
  92     ))
  93 
  94     # Add `DepositData` root to Merkle tree (update a single `branch` node)
  95     self.deposit_count += 1
  96     size: uint256 = self.deposit_count
  97     for height in range(DEPOSIT_CONTRACT_TREE_DEPTH):
  98         if bitwise_and(size, 1) == 1:  # More gas efficient than `size % 2 == 1`
  99             self.branch[height] = node
  100             break
  101         node = sha256(concat(self.branch[height], node))
  102         size /= 2
  103 
  104
  [end of deposit_contract/contracts/validator_registration.v.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/deposit_contract/contracts/validator_registration.v.py b/deposit_contract/contracts/validator_registration.v.py
  --- a/deposit_contract/contracts/validator_registration.v.py
  +++ b/deposit_contract/contracts/validator_registration.v.py
  @@ -6,7 +6,7 @@
   AMOUNT_LENGTH: constant(uint256) = 8  # bytes
   SIGNATURE_LENGTH: constant(uint256) = 96  # bytes
   
  -Deposit: event({
  +DepositEvent: event({
       pubkey: bytes[48],
       withdrawal_credentials: bytes[32],
       amount: bytes[8],
  @@ -42,8 +42,9 @@
   
   @public
   @constant
  -def get_deposit_root() -> bytes32:
  -    node: bytes32 = 0x0000000000000000000000000000000000000000000000000000000000000000
  +def get_hash_tree_root() -> bytes32:
  +    zero_bytes32: bytes32 = 0x0000000000000000000000000000000000000000000000000000000000000000
  +    node: bytes32 = zero_bytes32
       size: uint256 = self.deposit_count
       for height in range(DEPOSIT_CONTRACT_TREE_DEPTH):
           if bitwise_and(size, 1) == 1:  # More gas efficient than `size % 2 == 1`
  @@ -51,7 +52,7 @@
           else:
               node = sha256(concat(node, self.zero_hashes[height]))
           size /= 2
  -    return node
  +    return sha256(concat(node, self.to_little_endian_64(self.deposit_count), slice(zero_bytes32, start=0, len=24)))
   
   
   @public
  @@ -75,11 +76,11 @@
       assert len(withdrawal_credentials) == WITHDRAWAL_CREDENTIALS_LENGTH
       assert len(signature) == SIGNATURE_LENGTH
   
  -    # Emit `Deposit` log
  +    # Emit `DepositEvent` log
       amount: bytes[8] = self.to_little_endian_64(deposit_amount)
  -    log.Deposit(pubkey, withdrawal_credentials, amount, signature, self.to_little_endian_64(self.deposit_count))
  +    log.DepositEvent(pubkey, withdrawal_credentials, amount, signature, self.to_little_endian_64(self.deposit_count))
   
  -    # Compute `DepositData` root
  +    # Compute `DepositData` hash tree root
       zero_bytes32: bytes32 = 0x0000000000000000000000000000000000000000000000000000000000000000
       pubkey_root: bytes32 = sha256(concat(pubkey, slice(zero_bytes32, start=0, len=64 - PUBKEY_LENGTH)))
       signature_root: bytes32 = sha256(concat(
  @@ -91,7 +92,7 @@
           sha256(concat(amount, slice(zero_bytes32, start=0, len=32 - AMOUNT_LENGTH), signature_root)),
       ))
   
  -    # Add `DepositData` root to Merkle tree (update a single `branch` node)
  +    # Add `DepositData` hash tree root to Merkle tree (update a single `branch` node)
       self.deposit_count += 1
       size: uint256 = self.deposit_count
       for height in range(DEPOSIT_CONTRACT_TREE_DEPTH):
  
verification_info: {"golden_diff": "diff --git a/deposit_contract/contracts/validator_registration.v.py b/deposit_contract/contracts/validator_registration.v.py\n--- a/deposit_contract/contracts/validator_registration.v.py\n+++ b/deposit_contract/contracts/validator_registration.v.py\n@@ -6,7 +6,7 @@\n AMOUNT_LENGTH: constant(uint256) = 8  # bytes\n SIGNATURE_LENGTH: constant(uint256) = 96  # bytes\n \n-Deposit: event({\n+DepositEvent: event({\n     pubkey: bytes[48],\n     withdrawal_credentials: bytes[32],\n     amount: bytes[8],\n@@ -42,8 +42,9 @@\n \n @public\n @constant\n-def get_deposit_root() -> bytes32:\n-    node: bytes32 = 0x0000000000000000000000000000000000000000000000000000000000000000\n+def get_hash_tree_root() -> bytes32:\n+    zero_bytes32: bytes32 = 0x0000000000000000000000000000000000000000000000000000000000000000\n+    node: bytes32 = zero_bytes32\n     size: uint256 = self.deposit_count\n     for height in range(DEPOSIT_CONTRACT_TREE_DEPTH):\n         if bitwise_and(size, 1) == 1:  # More gas efficient than `size % 2 == 1`\n@@ -51,7 +52,7 @@\n         else:\n             node = sha256(concat(node, self.zero_hashes[height]))\n         size /= 2\n-    return node\n+    return sha256(concat(node, self.to_little_endian_64(self.deposit_count), slice(zero_bytes32, start=0, len=24)))\n \n \n @public\n@@ -75,11 +76,11 @@\n     assert len(withdrawal_credentials) == WITHDRAWAL_CREDENTIALS_LENGTH\n     assert len(signature) == SIGNATURE_LENGTH\n \n-    # Emit `Deposit` log\n+    # Emit `DepositEvent` log\n     amount: bytes[8] = self.to_little_endian_64(deposit_amount)\n-    log.Deposit(pubkey, withdrawal_credentials, amount, signature, self.to_little_endian_64(self.deposit_count))\n+    log.DepositEvent(pubkey, withdrawal_credentials, amount, signature, self.to_little_endian_64(self.deposit_count))\n \n-    # Compute `DepositData` root\n+    # Compute `DepositData` hash tree root\n     zero_bytes32: bytes32 = 0x0000000000000000000000000000000000000000000000000000000000000000\n     pubkey_root: bytes32 = sha256(concat(pubkey, slice(zero_bytes32, start=0, len=64 - PUBKEY_LENGTH)))\n     signature_root: bytes32 = sha256(concat(\n@@ -91,7 +92,7 @@\n         sha256(concat(amount, slice(zero_bytes32, start=0, len=32 - AMOUNT_LENGTH), signature_root)),\n     ))\n \n-    # Add `DepositData` root to Merkle tree (update a single `branch` node)\n+    # Add `DepositData` hash tree root to Merkle tree (update a single `branch` node)\n     self.deposit_count += 1\n     size: uint256 = self.deposit_count\n     for height in range(DEPOSIT_CONTRACT_TREE_DEPTH):\n", "issue": "is_genesis_trigger fails to verify deposit merkle branch\n## Issue\r\nDeposits are processed against empty state with undefined `eth1_data` while `genesis_eth1_data` should be in place.\r\n\n", "before_files": [{"content": "MIN_DEPOSIT_AMOUNT: constant(uint256) = 1000000000  # Gwei\nDEPOSIT_CONTRACT_TREE_DEPTH: constant(uint256) = 32\nMAX_DEPOSIT_COUNT: constant(uint256) = 4294967295 # 2**DEPOSIT_CONTRACT_TREE_DEPTH - 1\nPUBKEY_LENGTH: constant(uint256) = 48  # bytes\nWITHDRAWAL_CREDENTIALS_LENGTH: constant(uint256) = 32  # bytes\nAMOUNT_LENGTH: constant(uint256) = 8  # bytes\nSIGNATURE_LENGTH: constant(uint256) = 96  # bytes\n\nDeposit: event({\n    pubkey: bytes[48],\n    withdrawal_credentials: bytes[32],\n    amount: bytes[8],\n    signature: bytes[96],\n    index: bytes[8],\n})\n\nbranch: bytes32[DEPOSIT_CONTRACT_TREE_DEPTH]\ndeposit_count: uint256\n\n# Compute hashes in empty sparse Merkle tree\nzero_hashes: bytes32[DEPOSIT_CONTRACT_TREE_DEPTH]\n@public\ndef __init__():\n    for i in range(DEPOSIT_CONTRACT_TREE_DEPTH - 1):\n        self.zero_hashes[i + 1] = sha256(concat(self.zero_hashes[i], self.zero_hashes[i]))\n\n\n@private\n@constant\ndef to_little_endian_64(value: uint256) -> bytes[8]:\n    # Reversing bytes using bitwise uint256 manipulations\n    # Note: array accesses of bytes[] are not currently supported in Vyper\n    # Note: this function is only called when `value < 2**64`\n    y: uint256 = 0\n    x: uint256 = value\n    for _ in range(8):\n        y = shift(y, 8)\n        y = y + bitwise_and(x, 255)\n        x = shift(x, -8)\n    return slice(convert(y, bytes32), start=24, len=8)\n\n\n@public\n@constant\ndef get_deposit_root() -> bytes32:\n    node: bytes32 = 0x0000000000000000000000000000000000000000000000000000000000000000\n    size: uint256 = self.deposit_count\n    for height in range(DEPOSIT_CONTRACT_TREE_DEPTH):\n        if bitwise_and(size, 1) == 1:  # More gas efficient than `size % 2 == 1`\n            node = sha256(concat(self.branch[height], node))\n        else:\n            node = sha256(concat(node, self.zero_hashes[height]))\n        size /= 2\n    return node\n\n\n@public\n@constant\ndef get_deposit_count() -> bytes[8]:\n    return self.to_little_endian_64(self.deposit_count)\n\n\n@payable\n@public\ndef deposit(pubkey: bytes[PUBKEY_LENGTH],\n            withdrawal_credentials: bytes[WITHDRAWAL_CREDENTIALS_LENGTH],\n            signature: bytes[SIGNATURE_LENGTH]):\n    # Avoid overflowing the Merkle tree (and prevent edge case in computing `self.branch`)\n    assert self.deposit_count < MAX_DEPOSIT_COUNT\n\n    # Validate deposit data\n    deposit_amount: uint256 = msg.value / as_wei_value(1, \"gwei\")\n    assert deposit_amount >= MIN_DEPOSIT_AMOUNT\n    assert len(pubkey) == PUBKEY_LENGTH\n    assert len(withdrawal_credentials) == WITHDRAWAL_CREDENTIALS_LENGTH\n    assert len(signature) == SIGNATURE_LENGTH\n\n    # Emit `Deposit` log\n    amount: bytes[8] = self.to_little_endian_64(deposit_amount)\n    log.Deposit(pubkey, withdrawal_credentials, amount, signature, self.to_little_endian_64(self.deposit_count))\n\n    # Compute `DepositData` root\n    zero_bytes32: bytes32 = 0x0000000000000000000000000000000000000000000000000000000000000000\n    pubkey_root: bytes32 = sha256(concat(pubkey, slice(zero_bytes32, start=0, len=64 - PUBKEY_LENGTH)))\n    signature_root: bytes32 = sha256(concat(\n        sha256(slice(signature, start=0, len=64)),\n        sha256(concat(slice(signature, start=64, len=SIGNATURE_LENGTH - 64), zero_bytes32)),\n    ))\n    node: bytes32 = sha256(concat(\n        sha256(concat(pubkey_root, withdrawal_credentials)),\n        sha256(concat(amount, slice(zero_bytes32, start=0, len=32 - AMOUNT_LENGTH), signature_root)),\n    ))\n\n    # Add `DepositData` root to Merkle tree (update a single `branch` node)\n    self.deposit_count += 1\n    size: uint256 = self.deposit_count\n    for height in range(DEPOSIT_CONTRACT_TREE_DEPTH):\n        if bitwise_and(size, 1) == 1:  # More gas efficient than `size % 2 == 1`\n            self.branch[height] = node\n            break\n        node = sha256(concat(self.branch[height], node))\n        size /= 2\n\n", "path": "deposit_contract/contracts/validator_registration.v.py"}]}