Fixed bitmap collision issue

[Havoc19]

Update Summary for updateTokens and _verifyNewTokenList

Changes Made

• Replaced Single Bitmap with 256-Slot Bitmap Array (uint256[256]):
  • Each function now uses a uint256[256] array instead of a single uint256 variable. This allows us to handle up to 65,536 unique bit positions (256 slots * 256 bits per slot).
• Collision-Free Hashing Using keccak256:
  • Each token address is hashed with keccak256 and then mapped to a unique bit position in the bitmap using modulo 65,536. This ensures a collision-free approach to track each token’s presence.
• Index and Offset Calculations:
  • bitPos: Each token address is hashed, and the hash is taken modulo 65,536 to ensure it falls within the range 0 to 65,535.
  • index: Calculated as bitPos / 256, which identifies the specific slot in the uint256[256] array.
  • offset: Calculated as bitPos % 256, which determines the exact bit within the selected slot.

How It Works

1. Token Presence Tracking:

   • Each token’s address is hashed and mapped to a unique bit position within uint256[256].
   • The bitmap allows us to set, clear, and check each token’s presence efficiently by setting or clearing specific bits.

2. Bitmap Array (uint256[256]):

   • Each uint256 element in the array provides 256 bits.
   • With 256 uint256 elements, we get a total of 65,536 bits, exactly matching the space needed for bit positions 0 to 65,535.
   • By dividing bitPos by 256, we determine the slot (index) in the array, and by taking bitPos % 256, we determine the specific bit within that slot (offset).

3. Collision-Free Mapping:

   • keccak256 produces a unique 256-bit hash for each token address.
   • By taking bitPos = hash % 65536, we map the hash to one of the 65,536 unique bit positions in uint256[256].
   • This approach ensures that each token address has a unique bit in the bitmap, preventing any collisions.

Why We Use an Array

• Efficient Memory Use:

  • uint256[256] provides exactly 65,536 bits, meeting our requirement without any additional storage overhead.
  • This is more efficient than a single uint256 or a larger array like uint256[1024], which would consume unnecessary memory and gas.

• Gas Optimization:

  • Storing and accessing bits in uint256[256] in memory is gas-efficient compared to alternative storage structures.
  • This memory structure allows us to perform bitwise operations for tracking token presence without costly storage operations (SSTORE).

Benefits of This Approach

• Collision-Free Tracking: The keccak256 hashing with modulo 65,536 and mapping to uint256[256] ensures no collisions, so each token address is represented uniquely.
• Scalability: Efficiently supports up to 65,536 unique tokens without additional space requirements.
• Gas Efficiency: Using a uint256[256] bitmap in memory reduces gas costs compared to on-chain storage and larger data structures.

[langnavina97]

The changes look good! I think the chance to have a collision is reduced but there is still a small risk, it might be small enough to accept this solution. Can we confirm with the auditors?