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

Listing all kitties owned by a user is O(n^2) #4

Open
Arachnid opened this issue Nov 16, 2017 · 2 comments
Open

Listing all kitties owned by a user is O(n^2) #4

Arachnid opened this issue Nov 16, 2017 · 2 comments

Comments

@Arachnid
Copy link

Description

tokensOfOwnerByIndex linearly scans all kitties looking for the nth one owned by the specified account. Since each call iterates over all the previous results, if there are n kitties, m of them owned by the specified address, this will take O(m * n) time.

Although this function notes that it's not intended to be called onchain, even offchain the execution time of listing kitties will soon become impractical.

Scenario

  1. Create lots of kitties.
  2. Attempt to enumerate all kitties owned by someone with lots of kitties.

Impact

It may become effectively impossible to list someone's kitties - particularly newer ones.

Reproduction

See Scenario.

Fix

Maintain an array of kitties-by-owner. This array can be efficiently updated by moving the last element into deleted indexes, since it's not necessary for the array to be kept in order. EG:

mapping(address=>uint[]) kittiesByOwner;

function deleteKitty(address owner, uint idx) {
  var kittyList = kittiesByOwner[owner];
  require(idx < kittyList.length);
  if(idx < kittyList.length - 1) {
    kittyList[idx] = kittyList[kittyList.length - 1];
  }
  kittyList.length -= 1;
}
@dete
Copy link

dete commented Nov 16, 2017

Thanks for this, @Arachnid!

Although this function notes that it's not intended to be called onchain, even offchain the execution time of listing kitties will soon become impractical.

This is a great point, I'm so used to treating off-chain code as "free", I didn't think through this properly. And the added state of tracking IDs by owner was something we hoped to avoid.

We've already been talking about switching to an O(n) version of this (returning a dynamic array, which only works for off-chain calls), which would solve the problem without gas impact.

@dete dete mentioned this issue Nov 18, 2017
@kimcope
Copy link
Contributor

kimcope commented Nov 21, 2017

Thanks for your participation, @Arachnid! Our team has reviewed your submission, and we are pleased to reward you for your report.

Impact: Low
Likelihood: Low
Points: 50

Please see the final leaderboard here.

kophyo1234 added a commit to kophyo1234/openzeppelin-contracts that referenced this issue Jan 29, 2022
Standards

ERC-20 Token Standard.
ERC-165 Standard Interface Detection.
ERC-173 Owned Standard.
ERC-223 Token Standard.
ERC-677 transferAndCall Token Standard.
ERC-827 Token Standard.
Ethereum Name Service (ENS). https://ens.domains
Instagram – What’s the Image Resolution? https://help.instagram.com/1631821640426723
JSON Schema. https://json-schema.org/
Multiaddr. https://github.com/multiformats/multiaddr
RFC 2119 Key words for use in RFCs to Indicate Requirement Levels. https://www.ietf.org/rfc/rfc2119.txt
Issues

The Original ERC-721 Issue. ethereum/EIPs#721
Solidity Issue OpenZeppelin#2330 – Interface Functions are External. ethereum/solidity#2330
Solidity Issue OpenZeppelin#3412 – Implement Interface: Allow Stricter Mutability. ethereum/solidity#3412
Solidity Issue OpenZeppelin#3419 – Interfaces Can’t Inherit. ethereum/solidity#3419
Solidity Issue OpenZeppelin#3494 – Compiler Incorrectly Reasons About the selector Function. ethereum/solidity#3494
Solidity Issue OpenZeppelin#3544 – Cannot Calculate Selector of Function Named transfer. ethereum/solidity#3544
CryptoKitties Bounty Issue OpenZeppelin#4 – Listing all Kitties Owned by a User is O(n^2). dapperlabs/cryptokitties-bounty#4
OpenZeppelin Issue OpenZeppelin#438 – Implementation of approve method violates ERC20 standard. OpenZeppelin#438
Solidity DelegateCallReturnValue Bug. https://solidity.readthedocs.io/en/develop/bugs.html#DelegateCallReturnValue
Discussions

Reddit (announcement of first live discussion). https://www.reddit.com/r/ethereum/comments/7r2ena/friday_119_live_discussion_on_erc_nonfungible/
Gitter #EIPs (announcement of first live discussion). https://gitter.im/ethereum/EIPs?at=5a5f823fb48e8c3566f0a5e7
ERC-721 (announcement of first live discussion). ethereum/EIPs#721 (comment)
ETHDenver 2018. https://ethdenver.com
NFT Implementations and Other Projects

CryptoKitties. https://www.cryptokitties.co
0xcert ERC-721 Token. https://github.com/0xcert/ethereum-erc721
Su Squares. https://tenthousandsu.com
Decentraland. https://decentraland.org
CryptoPunks. https://www.larvalabs.com/cryptopunks
DMarket. https://www.dmarket.io
Enjin Coin. https://enjincoin.io
Ubitquity. https://www.ubitquity.io
Propy. https://tokensale.propy.com
CryptoKitties Deployed Contract. https://etherscan.io/address/0x06012c8cf97bead5deae237070f9587f8e7a266d#code
Su Squares Bug Bounty Program. https://github.com/fulldecent/su-squares-bounty
XXXXERC721. https://github.com/fulldecent/erc721-example
ERC721ExampleDeed. https://github.com/nastassiasachs/ERC721ExampleDeed
Curio Cards. https://mycuriocards.com
Rare Pepe. https://rarepepewallet.com
Auctionhouse Asset Interface. https://github.com/dob/auctionhouse/blob/master/contracts/Asset.sol
OpenZeppelin SafeERC20.sol Implementation. https://github.com/OpenZeppelin/zeppelin-solidity/blob/master/contracts/token/ERC20/SafeERC20.sol
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants