NFToken: The Non-Fungible ERC20
tl;dr
The ERC721 Non-Fungible Token Standard, which collectible tokens such as Cryptokitties are based upon, is one of the most widely adopted tokens standards on Ethereum. NFT transfers account for a significant potion of traffic; anyone who has been around for a couple of years will remember when breeding cats almost took down the network. This is because NFT transfers are immensely gas heavy — costing upwards of 50,000 gas per token. Over the past year many bright minds have sought to reduce these costs, finding better and better ways to efficiently pack data and minimize storage writes. But what if there was another way? What if we could reduce that 50,000 gas by a factor of 50 or more?
…but why?
Why ERC20, you ask? What’s the point? Why not instead attempt to create a hyper-efficient version of something that’s meant to be non-fungible?
I blame Gabriel Shapiro. Over the past nine months Gabriel and I have been discussing the benefits and challenges, both technical and legal, of representing corporate stock on a public blockchain. It’s been a massive rabbit hole that I never thought I’d go down… I’ve learned enough about US federal securities laws at this point to confidently admit that I know next to nothing about them, and to have a profound respect for those who do. One of the topics Gabriel and I keep returning to is the idea of certificated shares. There’s a laundry list of reasons why a certificated model is preferable to a book-entry model, especially if you want the tokens to be transferable in any meaningful capacity. I won’t go into those reasons here, but if you’re interested Gabriel has written a deeply insightful article on the subject.
On the technical front, the biggest factor separating the certificated model from its book-entry counterpart is the non-fungibility introduced by the certificates. Interestingly to me, nobody has been talking about this — there seems to be an assumption throughout the security token industry that a book-entry model is the only viable path. Delaware explicitly allows this, with a bill stating that corporations may use a blockchain for their share registries. The path seems so simple, why try anything else? But then Gabriel started talking about Wyoming…
So — challenge accepted. How can we achieve transfers using the standard ERC20 interface, while also enabling non-fungibility? Oh, and it has to scale. We aren’t talking about moving 10 or 100 tokens at a time. If we can’t move millions in a single transfer, what good is it anyway?
¯\_(ツ)_/¯
First, I looked to existing NFT models. ERC721, the “Non Fungible Token Standard”, is best the known and widest implemented approach, and so a logical place to start. ERC721 stores unique identifiers for every token, and transferring multiple tokens in a single transaction requires a wrapper contract. This makes sense when each of your tokens are precious and unique, such as with CryptoKitties, but for our use case it just isn’t going to scale adequately.
ERC1155, the “Multi Token Standard”, has been making a lot of waves recently. It’s a very impressive design that works for both NFTs and fungible tokens, and with the right implementation it significantly reduces gas costs compared to ERC721. But even the most efficient implementations are relying on tightly packing identifiers next to one another. When applied to NFTs it will certainly scale more than ERC721, but it’s still not going to handle transfers in the scope we’re hoping for.
ERC998, the “Composable Non-Fungible Token Standard”, allows NFTs to own other NFTs — now this could be promising! Using composable NFTs we could group individual tokens together, and allow large transfers by only moving the single composable. So long as everyone is happy with the size of their groupings this will work perfectly. Unfortunately, there is still a significant overhead in transferring ownership of the base tokens in and out of the composables. What happens when you have a bundle of 1000 tokens, but a buyer for 500? Token transfers could end up being relatively complex with several transactions required. This could get expensive quickly.
…But I do like the idea of grouping the tokens. Can we come up with a more efficient manner to accomplish this?
💡 💡 💡
Enter NFToken. This contract takes advantage of the EVM’s lack of gas costs to initialize empty storage space, tracking token ownership within a very long fixed length array. Token identifiers are sequential numbers corresponding to index values of that array. Instead of recording the owner of every single token, it only records the stop position of each owned range. These positions are marked in the array with the start position, which also corresponds to a mapping that lists the owner and the stop position.
For example — suppose Alice owns tokens 1–5, Bob owns 6–8, and Carol 9–10. Starting from position 1, our range would look like:
[0, 0, 0, 0, 1, 0, 0, 6, 0, 9]
If we want to know who owns token #2, we iterate the array until reaching a non-zero value. In this case, we find the number 1 in the 5th slot. We can then check a mapping with the 1 as the key, where we will find:
{owner: “Alice”, stop: 5}
If Alice then wishes to transfer some of her tokens to Bob, say 3 to 5, the range is updated to look like so:
[0, 1, 0, 0, 0, 0, 0, 3, 0, 9]
And just like that, we can move a large range of sequential NFTs with only a few writes to the blockchain! The above example was limited to 10 tokens for readability, but the process to transfer a million tokens is near identical to that of transferring 10.
…but does it scale?
Good question! While not perfect, it’s still pretty damn efficient 😎
Starting with the worst case scenario: the upper bound gas cost to transfer a single range is ~86,000 gas for the first range, and ~38,000 for each additional range. With a maximally fragmented token range, transferring one hundred tokens with a single token per range will cost ~39,000 gas per token.
However, transfer costs increase linearly based not on the number of tokens transferred, but the number of ranges. This means the absolute lower bound cost, transferring the maximum total supply of ²⁶⁴-2 tokens as a single range, is only ~0.00000000145 gas per token! A more reasonable lower bound, transferring one hundred tokens within a single range, costs just ~860 gas per token.
in conclusion…
And so we can move large ranges of sequential NFTs with just a few writes to the blockchain! We get similar gas efficiency to moving an ERC998 composable, without the overheard of creating or populating it. Costs increase linearly based not on the number of tokens transferred, but the number of ranges.
If you have a million sequential tokens and wish to move them all, you can do so for under 100,000 gas.
The actual implementation of this process is a bit more complex than what was summarized here — the goal of this article is not to drown you in technical details. If you’re interested in going deeper I invite you to view the code on GitHub. This is still an area I’m actively exploring, there are likely further optimizations that can be performed to decrease costs and reduce the rate of fragmentation. And while my own use case best fits ERC20, it should be possible to implement this technique within other existing NFT standards.
If this is interesting to you, if you have ideas, comments or criticisms, please reach out! Leave a comment below, send me an email or find me on Gitter or Telegram. I would love to hear from you.
