<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by miragenesi on Medium]]></title>
        <description><![CDATA[Stories by miragenesi on Medium]]></description>
        <link>https://medium.com/@miragenesi?source=rss-a99f3b6544e7------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*4oC5nUu_Yv_qmqNuOS9CuA.png</url>
            <title>Stories by miragenesi on Medium</title>
            <link>https://medium.com/@miragenesi?source=rss-a99f3b6544e7------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 11:14:34 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@miragenesi/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[NFT Art]]></title>
            <link>https://medium.com/@miragenesi/nft-art-da826db9bfdb?source=rss-a99f3b6544e7------2</link>
            <guid isPermaLink="false">https://medium.com/p/da826db9bfdb</guid>
            <category><![CDATA[nft]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[art]]></category>
            <category><![CDATA[generative-art]]></category>
            <dc:creator><![CDATA[miragenesi]]></dc:creator>
            <pubDate>Fri, 26 Apr 2024 14:10:06 GMT</pubDate>
            <atom:updated>2024-05-07T07:40:21.798Z</atom:updated>
            <content:encoded><![CDATA[<h4>Beyond JPEGs</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Du_yVUbzJ8UsMKsYP7VTCg.png" /></figure><h3>Preamble</h3><p>Do you hate NFTs? Fine.<br>This article is not about markets, prices, scams, and speculation (the things you most likely hate), but it’s about NFTs as a way to make art, as much as painting, music, etc.</p><p>I have intentionally omitted any direct link to the artworks that I am mentioning here because my goal is not to “shill” some NFTs, but to explain what’s happening in the substrate of the crypto society called “on-chain NFT art”. It’s a kingdom that is seldom explored by the mainstream media but that deserves attention, especially within the broader context of the arts.</p><p>I hope to be able to give you a new perspective on what this new type of artist is creating with this novel medium of expression and also to show you that there are people with a genuine creative drive working in this space.</p><h3>Introduction</h3><p>Art is everything and everywhere. It’s hard and unnecessary to try to draw a line between what’s art and what’s not.</p><p>You perform art by just filtering what the universe offers to you.</p><p>If a white square with nothing else but a frame speaks to you, let it be art.</p><p>If a picture of an ape with laser eyes triggers deep ancient emotions in you, well… let it be art.</p><p>There is another point of debate that I find more interesting: <strong>how the medium is used</strong> for artistic expression, which is what I will elaborate on in this article, specifically with regard to NFTs.</p><h3>The Medium</h3><p>Artists can express what they feel and see in many different ways: words, images, motions, sounds… Different media are available and the question is whether they are used at their best.</p><p>A camera can be used to frame moments in time, portraits, and landscapes...</p><p>A canvas can be used to paint a king&#39;s portrait or a landscape. But one can paint the realm of dreams and fantasy too. Using a canvas only to paint “real world” subjects would be reductive.</p><p>A film can be used to portray moving subjects, taking the time dimension in the frame. It would be again reductive to create a movie of still paintings.</p><p>Now we come to the NFT: it is not only a technology to handle ownership of art (and anything else really), but it’s also a medium that gives an arsenal of expressive options to the artist.</p><h3>The NFT</h3><p>The examples above show, very simplistically, how different tools can be used or NOT used.</p><p>The NFT can be seen through the same lenses: most of the currently circulating NFTs are still pictures or <em>still</em> animations, drawn with tool X or Y and <em>imported</em> on the blockchain.</p><p>What I mean is that what you end up owning once you buy one of these NFTs is a… URL. Nothing more. A URL that might contain a picture or a video today, and nothing tomorrow. But that’s pretty much it. The artist has certainly done some work, but the NFT technology was only used as a way to sell. Attention: it is not wrong. It’s just like an artist making a video of their painting and selling the streaming rights to Netflix. The artist sold their amazing work, but they cannot call themselves “video-makers”.</p><p>So what’s exactly the thing an artist can do to qualify as <strong>NFT Artist</strong> (in my own very personal view)?</p><h3>Generative Art</h3><p>Let’s start with a little digression into what <strong>I believe</strong> is at the foundation of everything that is currently happening in this space: generative computer art.</p><p>Born way before Bitcoin was invented, and even before the Internet existed, this niche category of the arts started around the beginning of the 60s, when employees at Bell’s Lab found an intriguing aesthetics in plotter’s errors.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/287/1*xTXWcGLj8HW4nHztJBeGcg.png" /><figcaption>Pattern One by A. Michael Noll (1962)</figcaption></figure><p>Although looking at the purely aesthetical side of it, Piet Mondrian was surely a pioneer of this type of artifacts</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qkxMYnI0BQr08IoT8k6K1w.jpeg" /><figcaption>Composition with Lines by Piet Mondrian (1917)</figcaption></figure><p>Computer Generated Art is a type of art where the visual output is delegated to a machine. The human product is the algorithm that gives life to it. <br>This is art that speaks to the viewer, but also to the maker, mesmerized by the surprising beauties that can emerge from mere electronic circuitry.</p><p>The artist-collector relationship is the same as for all other types of traditional art: the artist creates the output, and the collector buys it.</p><p>Let’s see how NFTs evolved this equation.</p><h3>Generative NFTs</h3><p>The first, and most fundamental aspect that NFTs bring to the world of arts is the possibility to turn the algorithm into the artwork.</p><p>The job of the artist is now to define the rules, not to select the outputs. Everything else will be determined by the chance.</p><p>The first example of NFT generative art is <strong>Autoglyphs</strong>, by <em>Larva Labs</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/880/1*GJtPJbpJIrHL2O3IFd3M1g.png" /><figcaption>Autoglyph #7, owned by 0x8088D74111a2368f5b7F0064A581D3bb72e6527e</figcaption></figure><p>The look of this is not far from what we have seen in the previous chapter, but there is a nuance to it: the artist created only a <em>contract</em> defining the rules. What you see is not a print from the artist, but the direct result of the contract computation, based on some randomness that was created during the purchase.</p><p>The artist becomes the meta-creator. The final collection is determined through the action of the collectors and it comes into existence only at the moment someone looks at it, triggering the machine to produce its visual output.</p><p>This is the foundation upon which most of the NFTs are built. What comes next is “just” an extension of it. We will try to answer the question: how far can the artist go <strong>programming</strong> their artwork? Can NFTs be <strong>alive</strong>?</p><h3>Time</h3><p>At the very base of every living being there is time.</p><p>Time inevitably affects art, both anthropologically and physically. A painting deteriorates through time. A cave drawing probably changes color and shades through the centuries.</p><p>In a way, most of the artworks are alive, as they evolve through time. But it’s currently out of the control of the artist to tell what time should do to their artwork.</p><p>Now imagine if the artist could define not only the rules of how to generate the look of their work but also of <em>how time should influence it</em>.</p><p>One example to clarify the concept is <strong>Chaos Roads</strong>, by <a href="https://x.com/chainleftist">Chainleft</a>.</p><p>This NFT uses Time to release chaos: the visual look of the NFT starts from a low entropy state (first image) to slowly descend into chaos, through the passage of time (second image, different NFT, higher entropy).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*J4aB5NQnYrtffGJOK8jcYA.png" /><figcaption>Chaos Roads #11, owned by sector12.eth</figcaption></figure><p>…more chaos…</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jQihE3oC3RbGw_K_mriokQ.png" /><figcaption>Chaos Roads #257, owned by zaphodok.eth</figcaption></figure><p>What you have today will look different and more chaotic in a month. A continuous surprise awaits the owners of this NFT.</p><p>As an analogy, imagine a Mona Lisa whose hair looks whiter every day.</p><p>Some may argue: “I could have an image in my computer and have a script that changes it every day”. Correct. The difference is mainly in the very definition of what an NFT is: ownable.</p><p>I can buy the image of your computer, you could run away tomorrow with it and my evolutionary art piece is gone.</p><p>The behavior I just showcased can instead, with NFTs, be embedded in the artwork that you buy. No one will ever be able to stop your NFT visual from changing tomorrow. Only the collapse of an entire financial system (called Ethereum) could cause this permanent loss.</p><p>The chances are lower than the entire Louvre burning down to ashes.</p><p>What else? We explored time as a new tool for the artists to express their inner vision of the universe, is that it? No: we are just scratching the surface. Generative algorithms and Time are the base dough of everything that will be described later, many tools are available on top.</p><h3>Ownership</h3><p>NFTs are based on a few standards (ERC721, ERC1155, and more) that essentially create a very clear relationship between the artwork and its owners.</p><p>At every point in time, I can know which and how many NFTs a given person owns. Or I can say how many unique collectors own pieces from a specific collection. And more.</p><p>This information can be used by the work itself to change itself.</p><p><strong>The Mesh</strong> by <a href="https://x.com/takenstheorem">Takenstheorem</a> is one good example of how ownership dynamics can affect the artwork. Each NFT draws data about its owner from the blockchain, in order to reveal, through a visual composition, the relationship of the collector to this and other artworks. Fascinating, isn’t it?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/1*ISopRvXKrz_66o_WjE5zog.png" /><figcaption>The Mesh #28, owned by remography.eth</figcaption></figure><p>Another notable example is <strong>See You There</strong> by <a href="https://twitter.com/simondlr">Simon de la Rouviere</a>: it’s a single NFT that captures the chain of owners from its inception until the next 5 years. The spiral will have a different section for each of the collectors who owned the piece for at least 20 days.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*E6ej3fLkfp5jODW_E44tnw.png" /><figcaption>See You There, currently owned by spengrah.eth</figcaption></figure><p>Time and ownership will determine how it will evolve…. Who knows what will it look like in 1,2,3 years?</p><p>What these artists are doing is to express through art the intricate dynamics between a collector and their artworks, a dimension that was always hidden away in previous media.</p><p>Imagine if the Mona Lisa would suddenly start smiling when purchased by one of Leonardo’s descendants. Agreed, it would probably be quite creepy.</p><h3>Activity</h3><p>The most mind-bending detail is probably the following: NFTs are artworks that are, to an extent, self-aware.</p><p>Everything that happens to a single NFT can be used by the NFT itself and others to change, evolve, respond…</p><p>We can have an artwork that deteriorates if no one looks at it, and that restores itself if people trade it. Well, with some external help, more or less the same can happen even with paintings, buildings, etc...</p><p>But let’s bring it a step further: <strong>Gold</strong>, by <a href="https://x.com/crashblossom1">James Bloom</a>.</p><p>This collection responds to anything that happens in its own market. All the activity of their collectors (in relation to the NFT itself) is recorded and used to paint and re-paint its visuals.</p><p>Transfers, prices, sales, provenance, everything that you can possibly imagine becomes the paintbrush of this NFT.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/974/1*cd60LBgcj5RBMW2HtXGnTg.gif" /><figcaption>Gold #124, owned by 0xD308BA2636A2B152e954479cD6E19B6479873ee5</figcaption></figure><p><strong>You are Here</strong> by <a href="https://x.com/0xShiroi">0xff</a> goes beyond Ethereum. This NFT records all the transfers that the token has undergone across different blockchains and simply shows the journey in a minimal, yet delightful way:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3sDvicXthfmD8R_ngssRRQ.png" /><figcaption>You Are Here #42161, owned by 0x697C89c4Bc5344960C26Da9517e39204186d7EfA</figcaption></figure><p>It’s a way to make the artwork life part of the artwork itself.</p><p>Image if the Mona Lisa, once moved to the Louvre, would have switched background from Montefeltro in the Marche to Paris.</p><h3>Interdependency</h3><p>In the previous chapter, I hinted at the fact that an NFT can know about itself. There is more: an NFT can know about others too. And it can draw itself based on this information.</p><p><strong>XXYYZZ</strong> by <a href="https://twitter.com/emo_eth"><em>emo.eth</em></a> and <a href="https://twitter.com/AspynPalatnick"><em>Aspyn</em></a> was created as a collection of colors, in all its conceptual purity. You really just buy a color:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/964/1*adJDGxrh5xCJXvrDAsoezA.png" /><figcaption>XXYYZZ #c3ff00, owned by cryptoferd.eth</figcaption></figure><p>In case the same collector owns as well a piece from another collection called <strong>Together </strong>(by the same author) the two NFTs are <em>plugged </em>together, composing the aesthetic features of the two artworks</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/964/1*VJFSbV69F9I4PbQiBMf7zw.png" /><figcaption>Together #318, owned by cryptoferd.eth</figcaption></figure><p>This is a static example, but options are infinite: one could in theory create an NFT that reacts to the changes of another NFT.</p><p>Imagine a Mona Lisa that starts crying when the The Battle of Anghiari burns down.</p><h3>Price</h3><p>There is something that, with or without our liking, is and will always be a crucial factor in almost all types of art: price.</p><p>Hardly will you find an artist that does not put a price tag on their items. Art is a form of expression first, and a business then.</p><p>We should not consider this negatively, because artists, like all other professions, need money. But, as promised in the introduction, this is not going to be a discussion about how to price art.</p><p>What I want to show here is how NFT artists can use price not only for profit but also for fun.</p><p>Among the <em>rules </em>that one can bake in the NFT, we have the price rules. In most of the cases these are used in their most basic way: to set a fixed price for the NFT, or to implement some kind of auction mechanics.</p><p>But <em>price</em> can also be used in more creative ways. For instance, to incentivize/disincentivize certain behaviours among the collectors, which then become part of that artistic performance.</p><p>One example of NFT where price played a fundamental role in the concept itself is <strong>Black Hole</strong> by <a href="https://x.com/miragenesi">miragenesi</a> (the author of this article).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wJ5ErIR7HuUHCPVPt9BARg.gif" /><figcaption>Blackhole ##226, owned by 0xaa5124f1128962aE115588611A6467ce318c8081</figcaption></figure><p>For every purchase of this NFT, the price would increase. Every time a piece was destroyed, the price would instead decrease. All the money spent during the sale would be accumulated in the NFT itself and be released to the last person destroying their NFT.</p><p>The pricing, in this case, was conceived so as to make the <em>Black Hole</em> absorb money for eternity, hence behaving like an actual black hole.</p><p>NFT Art blurs the line between generative, performative, and interactive art.</p><p>NFT Art can make the collectors part of the artwork.</p><h3>Infinity²</h3><p>What we have seen until now are just bits of what’s possible with NFT Art and it’s not meant to be a comprehensive list of all possible types of NFTs that can be created.</p><p>FAR FROM IT!</p><p>An NFT is a whole computer turned into an ownable artifact, the possibilities for the artists are an infinite larger than what was possible earlier. There are even NFTs that can produce audio.</p><p>New NFT artists join this niche circle daily, bringing amazing <strong>experimental</strong> and <strong>experiential</strong> artworks to this space.</p><p>You can explore more following the X profiles linked throughout the article, but also:</p><ul><li><a href="https://www.folia.app/">Folia</a> and especially the works from the founder <a href="https://twitter.com/billyrennekamp">Billy Rennekamp</a>, where interactivity and fun are so central to his NFTs that one might even call them game art</li><li><a href="https://discord.gg/fMxWdXFj">Pushers</a>, the Discord server from Chainleft, offers a very active and erudite NFT Art community, including specific channels for well-known artists where people can see new works and ask questions</li><li><a href="https://onchainchecker.xyz/">Onchainchecker</a> from <a href="https://twitter.com/tokenfox1">Tokenfox</a>, which indexes a plethora of artworks in the NFT space, with many projects showing, to a higher or lesser extent, the traits showcased above</li><li><a href="https://fingerprintsdao.xyz/">Fingerprints DAO</a>, a collective that owns and releases as well artworks in this category (and more traditional ones too)</li></ul><p>I myself write about NFTs and create new concepts, every now and then. Feel free to <a href="https://twitter.com/miragenesi">follow me</a> if interested, join my <a href="https://discord.gg/J5rAsNXsUE">Discord</a>, or if you have questions just write me an email at miragenesi |o| posteo |.| de.</p><p>I believe we are still in a phase of exploration and experimentation, where the technology is being tested, to both check what can technically be achieved and also to see how collectors relate and react to it. I imagine a future when the use of these tools will be as <em>normal</em> and simple as a brush is nowadays for painters, giving artists the power to bring art to a whole new level.</p><p>Thanks for reading this article, share it with haters and lovers, and let’s spread some good vibes for these wonderful artists 🙏</p><p><em>PS: I would like to repeat that all that was described in the article can indeed be performed without an NFT but just with a computer and a script. The difference is that, with NFTs, the algorithm is part of the artistic item and, hence, part of what the collectors are going to buy. Which can then </em><strong><em>exist independently and beyond the life of the artist itself</em></strong><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=da826db9bfdb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Chaos in Big NFT Collections]]></title>
            <link>https://medium.com/@miragenesi/chaos-in-big-nft-collections-63b83aa893d8?source=rss-a99f3b6544e7------2</link>
            <guid isPermaLink="false">https://medium.com/p/63b83aa893d8</guid>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[solidity]]></category>
            <category><![CDATA[entropy]]></category>
            <category><![CDATA[nft]]></category>
            <dc:creator><![CDATA[miragenesi]]></dc:creator>
            <pubDate>Mon, 07 Mar 2022 09:10:42 GMT</pubDate>
            <atom:updated>2022-03-07T18:38:05.208Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*48XpkBwPiogSeFqcnwliLA.jpeg" /></figure><h3>Introduction</h3><p>In the NFT realm, there are different ways of creating and distributing tokens.</p><p>Very often, the final outcomes are collections of hundreds if not thousands of pieces that are either generated or, less frequently, manually curated.</p><p>To manage the minting costs, such collections don’t usually come pre-minted. Instead, they let the collectors mint their own tokens, so to spread the gas costs.</p><p>This big collections usually include an element of chaos, to create surprise: when the collectors decide to mint the token, they don’t know what they are going to get. They will either know it after a reveal phase or right after the minting is done, depending on the strategy,.</p><p>The issue in this environment is that the NFT creator has to try to keep the minting phase fair, so to make the drop trustworthy. It should be as hard as possible for anyone to willingly “snipe” a rare token before it’s reveald. Given that we are dealing with a blockchain where everything is public and randomness is not given for granted, the problem is not trivial to solve.</p><p>Depending on the specific requirements, there are different approaches available, all very interesting and creative. Let’s take a deep dive.</p><h3>Token ID VS Content ID</h3><p>A small preamble to explain the relationship between token and content ID.</p><p>Usually an NFT is a URL pointing to some metadata (which in turn contains the link to the image/video/other media). This URL is generally a composition of a <strong>base URL</strong> and a <strong>path. </strong>Mapping the token ID to its path can be achieved with this pretty common technique</p><pre>Token #n URL =&gt; baseUrl + tokenId</pre><pre>Token #1 URL =&gt; <a href="https://ipfs.infura.io/ipfs/QmPK1s3pNYLi9ERiq3BDxKa4XosgWwFRQUydHUtz4YgpqB/1">https://ipfs.infura.io/ipfs/</a><a href="https://ipfs.infura.io/ipfs/QmPK1s3pNYLi9ERiq3BDxKa4XosgWwFRQUydHUtz4YgpqB/1">QmPK1s3pNYLi9ERiq3BDxKa4XosgWwFRQUydHUtz4YgpqB/1</a></pre><pre>Token #2 URL =&gt; <a href="https://ipfs.infura.io/ipfs/QmPK1s3pNYLi9ERiq3BDxKa4XosgWwFRQUydHUtz4YgpqB/2">https://ipfs.infura.io/ipfs/</a><a href="https://ipfs.infura.io/ipfs/QmPK1s3pNYLi9ERiq3BDxKa4XosgWwFRQUydHUtz4YgpqB/2">QmPK1s3pNYLi9ERiq3BDxKa4XosgWwFRQUydHUtz4YgpqB/2</a></pre><p>In case the token should be revealed at a later point, this approach presents an issue: if token ID<strong> #42</strong> is automatically associated to the content ID <strong>/42 </strong>, and we know <strong>/42 </strong>is some rare piece, we can just try to snap<strong> #42 </strong>after the minting phase starts.</p><p>For this reason, the methods described below will try to untangle the <strong>token ID</strong> from the <strong>content ID</strong>, so to be able, for instance, to randomly assign token ID <strong>#42</strong> to content ID <strong>/21.</strong></p><h3>Different requirements, different problems</h3><p>There are different problems that can come to play, depending on how you design your drop. There are, to my knowledge, two main ways to conceive a token distribution:</p><blockquote><strong>Mint now, reveal later</strong>: the user mints a token, but they will know the content they bought (content ID) only <strong>after </strong>a certain date (or other conditions).</blockquote><p>OR</p><blockquote><strong>Mint and reveal</strong>: The user mints and gets a random token from the available ones and they immediately know the content ID.</blockquote><p>They present different requirements and, consequently, completely different challenges. Below, I will dive into each of them, explaining the issues involved and some creative ways of addressing them.</p><h3>Mint now, reveal later</h3><p>In this approach, the user mints a token which is not revealed. Either at a specific date, or after other conditions (i.e.: when all the tokens are minted) the user can see the content (given from the content ID) of the acquired token.</p><p>The requirement to create a fair minting phase for this approach is:</p><blockquote>Neither the creators nor the collectors should be able to predict the content ID that will be associated to their token during the pre-reveal phase.</blockquote><p>Two main challenges are associated to this requirement.</p><p>First, you don’t want that people that have insider knowledge of the NFT collection, can simply snipe the rarest and higher value items during the pre-reveal minting phase. Example:</p><blockquote>Bob develops an NFT with 5 tokens, where token 4 is the rarest. Minting phase starts, no one but Bob knows that 4 is the rarest token. Tokens 1,2,3 are bought, then Bob immediatly snipes token 4, effectively exploiting his insider knowledge.</blockquote><p>Second: you also don’t want that the NFT creators tamper with the content of the collection <strong>after the minting, </strong>so to give advantage to their own tokens. Example:</p><blockquote>Alice develops an NFT with 5 tokens, where token 3 is the rarest. Minting phase ends and Alice bought the token with id 2. Alice, before publishing the collection, switches the content between tokens 2 and 3, so now she owns the rarest item. She effectively exploited her privileges to tamper in her favour with the content.</blockquote><p>Generally speaking, you need a way to randomize the mapping between a token ID and its content ID, so whatever someone’s previous knowledge is, they won’t be able to predict which content will be associated to the token they are going to buy. This boils down to 2 main problems:</p><ul><li>Mapping tokens to content in a way that it’s not possible to predict which content ID a token ID will be mapped to</li><li>Obtaining randomness (good ol’, good ol’…)</li></ul><h3>Obtaining randomness</h3><p>Solidity does not have a simple “randomNumber()” function. So entropy has to be fetched from other sources of randomness. There is already extensive literature about creating PRNG with Solidity. A good read is <a href="https://blog.positive.com/predicting-random-numbers-in-ethereum-smart-contracts-e5358c6b8620">Predicting Random Numbers in Ethereum Smart Contracts </a>, where all potential attack vectors are clarified.</p><p>To avoid redundancy, I will just show the baseline approach and the current-best approach.</p><h4><strong><em>Blockhash</em></strong></h4><p>Right after the last mint, you can store the <em>blockhash , </em>which is supposedly random<em>.</em></p><pre>public uint256 chaos;</pre><pre>function mint() public {</pre><pre>...</pre><pre>if(isMintingDone() || isRevealTime()) {<br>      entropy = blockhash(block.number - 1);<br>  }</pre><pre>...<br>}</pre><p><strong>Pros:</strong></p><ul><li>Simple and cheap</li></ul><p><strong>Cons:</strong></p><ul><li>Miners can manipulate (theoretically) the <strong>blockhash</strong></li><li>One could try to snipe an advantageous blockhash (hard)</li></ul><h4><strong>VRF</strong></h4><p>This approach uses <a href="https://en.wikipedia.org/wiki/Verifiable_random_function">Verifiable Random Functions</a> to generate entropy, effectively addressing all issues at a small cost</p><pre>public uint256 chaos;<br>internal uint256 chainLinkRequestId;</pre><pre>// Assumes the subscription is funded sufficiently.<br>function reveal() external onlyOwner {<br>   chainLinkRequestId = COORDINATOR.requestRandomWords(...);<br>}<br>  <br>function fulfillRandomWords(<br>   uint256, # chainLinkRequestId<br>   uint256[] memory randomWords<br>) internal override {<br>  chaos = randomWords[0];<br>}</pre><p><strong>Pros</strong></p><ul><li>State of the art PRNG</li><li>Cheap minting</li></ul><p><strong>Cons</strong></p><ul><li>Additional costs related to <a href="https://docs.chain.link/docs/get-a-random-number/">Chainlink</a> interaction</li></ul><h3>Random Mapping</h3><p>Now that we have entropy, how do we route a token id to some other content ID? There are potentially many approaches, but I will list here only some that I have seen used.</p><h4>Offset</h4><p>As simple as possible: the entropy is used to generate an offset. You re-map then the token ids like</p><pre>function tokenURI(uint256 tokenId) public returns (string memory) {</pre><pre>  uint256 contentId = (tokenId + offset) % maxSupply();</pre><pre>  return abi.encodedPacked(_baseURI(), contentId.toString();<br>}</pre><p><strong>Pros</strong></p><ul><li>Simple</li></ul><p><strong>Cons</strong></p><ul><li>Knowledge of the distribution of rarity could allow carpet-bombing the rare tokens. Extreme example: if someone knows that there is a rare token each 10 tokens, they could bulk buy 20 tokens and have a good chance to get a rare one</li></ul><h4><strong>Linear Congruential Generator</strong></h4><p>LCGs are an example of random number generators, that can be used to generate a deterministic random sequence. In this instance, it leverages a nice property of prime numbers. In practice:</p><pre>function tokenURI(uint256 tokenId) public returns (string memory) {</pre><pre>  # Both <strong>prime</strong> and <strong>offset </strong>have to depend on the entropy. <br>  uint256 contentId = (offset + tokenId * prime) % maxSupply();</pre><pre>  return abi.encodedPacked(_baseURI(), contentId.toString();<br>}</pre><pre># Courtesy of <a href="https://twitter.com/dievardump">https://twitter.com/dievardump</a></pre><p>This is not only an injective function, but it also changes the relative distance of the ids in the new, re-mapped sequence! Easier an example:</p><pre># With offset<br>offset = 2 # random<br>ids = [1,2,3,4,5,6,7,8,9,10]<br>newIds = (ids + 2) % 4<br>newIds == [3,4,5,6,7,8,9,10,1,2]</pre><pre># If last 5 tokens were rare, rare tokens will most likely be close to each others even in the new sequence</pre><pre>-------</pre><pre># With LCG<br>offset = 347 # random<br>prime = 13<br>ids = [1,2,3,4,5,6,7,8,9,10]<br>newIds = LCG(ids, offset, prime)<br>newIds == [8,1,4,7,10,3,6,9,2,5]</pre><pre># Last 5 tokens are now completely broken apart</pre><p><strong>Pros</strong></p><ul><li>No carpet bombing possible</li><li>Light: concise and with constant computational complexity</li></ul><p><strong>Cons</strong></p><ul><li>Quality depends also on the prime, that has to be drawn randomly from a big set</li></ul><h4>Shuffle</h4><p>A more sophisticated mapping can be based on shuffling: once the entropy is acquired, use it as a seed to shuffle the list of ids. Example</p><pre>function tokenId(uint256 tokenId) public view returns (uint256) {</pre><pre>  Shuffler memory shuffler = Shuffler.init(maxSupply(), entropy);<br>  <br>  for (uint256 idx = 0; idx &lt; tokenId; idx++) {</pre><pre>    shuffle.next(); # All in memory, no storage!<br>  }      <br>  <br>  return shuffle.next(); <br>}</pre><p>The approach is courtesy of <a href="https://twitter.com/cxkoda">cxkoda</a>, who also created an implementation of the <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">Fisher-Yates</a> shuffle, available in the appendix.</p><p><strong>Pros</strong></p><ul><li>Distribution of the resulting sequence different from the first one</li><li>Depends only on the quality of entropy source</li></ul><p><strong>Cons</strong></p><ul><li>Minor: more code to store on-chain than LCG</li></ul><h3>Additional Note</h3><p>On-chain mapping is useful when the collection content is already public, with the location stored in the contract before the minting starts.</p><p>But if someone wants to hide the collection content until reveal, thus not immediately linking the contract to the location of the content, there has to be a way to prove, after reveal, that the collection was not manipulated in between.</p><p>This involves managing the provenance of the collection, which will be dealth with in a different article.</p><h3>Mint and reveal</h3><p>This approach is used when the collector is supposed see the content immediately after minting. In this case, token ID and content ID are the same. This creates a requirement:</p><blockquote>Collectors should not be able to predict, before minting, the token ID that they will receive</blockquote><p>In general, we need a strategy to randomly draw an item from a collection, without picking the same item twice.</p><h3>Naive approach</h3><p>I’ll describe this approach just to give a feeling of what issues are involved in this problem.</p><pre>function mint() public {<br>  uint256 tokenId = availableTokenIds[randomNumber() % _leftSupply];</pre><pre>  # This moves all the ids after tokenId to the left. O(N)!<br>  shiftList(availableTokenIds);</pre><pre>  _leftSupply--;</pre><pre>  _mint(msg.sender, tokenId);<br>}</pre><p>As simple at it may seem, this brings a big gas costs to the minter, in particular if the size of the collection is big. No mention the storage writing expenditure.</p><p><strong>Pros</strong></p><ul><li>It works</li></ul><p><strong>Cons</strong></p><ul><li>Big gas cost for the minter, due to computational complexity and written memory</li></ul><h3>Bitmap</h3><p>This approach can be used with collections of limited size, but it’s a pretty nice code golf that shows how bitwise logic can be used to spare a lot of resources.</p><p>In fact, it uses a <em>uint256 </em>to store the map of the minted token. Imagine that in the 256-bit long sequence of zeros and ones, 1 represents a token that is already minted. <strong>01010</strong><em> </em>would mean that token #2 and #4 have already been minted.</p><pre>function mint() public {</pre><pre>  uint256 x = (1 &lt;&lt; randomNumber()) % maxSupply();</pre><pre>  // Is the bit at x unset?<br>  if ((allocationMap &amp; x) == 0) {<br>   allocationMap |= x;<br>   return x;<br>  }</pre><pre>  // The bit is not free, let&#39;s find the first free bit<br>  // on the &quot;left side&quot; of x.</pre><pre>  // Set all bits less significant than x<br>  x = allocationMap | (x - 1);<br>  // Find the rightmost unset bit<br>  x = ~x &amp; (x + 1);</pre><pre>  // Found something<br>  if (x &lt; 1 &lt;&lt; maxSupply()) {<br>    allocationMap |= x;<br>    return x;<br>  }</pre><pre>  // Nope, still unlucky. we need to search in the other half<br>  x = ~allocationMap &amp; (allocationMap + 1);<br>  if (x &lt; 1 &lt;&lt; maxSupply()) {<br>    allocationMap |= x;<br>    return x;<br>  }<br>  <br>  # log can be implemented, cheapest solution 700 gas<br>  # <a href="https://ethereum.stackexchange.com/a/30168">https://ethereum.stackexchange.com/a/30168</a><br>  uint256 tokenId = log(x);</pre><pre>  _mint(msg.sender, tokenId);</pre><pre>}</pre><pre># Courtesy of code and explanations <a href="https://twitter.com/vrde">https://twitter.com/vrde</a></pre><p>If the token id is already taken, takes the first available one from its position:</p><pre>mintingState  ==      0001110010<br>randomTokenId == 6 _______|<br>firstUnsetBit  == 4 _________|</pre><pre># if it doesn&#39;t work, check on the left</pre><p>Due to the magic of bitwise logic, finding this bit<em> </em>has<em> </em>constant complexity and it is also very gas efficient. The only issue with this approach is that the probability distribution of each draw becomes more and more uneven the further we go with the minting. Easier explained with an example:</p><pre>0000000000 # all token have 10% chance to be drawn<br>0011100000 # token #5 has P(5) + P(6) + P(7) of being drawn</pre><p><strong>Pros</strong></p><ul><li>Cheapest solution, thanks to constant complexity, bitwise logic and low writes (only one <strong>uint256</strong> written)</li></ul><p><strong>Cons</strong></p><ul><li>Probability distribution loses uniformity over time</li><li>Can work out of the box only with max 256 token collections.</li></ul><h3>Swaps</h3><p>This last approach is based on the Fisher-Yale shuffle and tries to be both efficient and sound.</p><pre>uint256 internal leftToMint = 10000;<br>mapping(uint256 =&gt; uint256) internal _idSwaps;</pre><pre>// We start with the idea that each index match its id <br>//   (tokenId = _isSwaps[index] || index)     <br>// then whenever an index is minted, we set the id in<br>//   _isSwaps[index] = _isSwaps[leftToMint] || leftToMint;     <br>// and decrease our range of &#39;search&#39; for ids over time, <br>// _isSwaps[index] will be filled with unminted ids so none <br>// will be lost. This is like swapping values, just with the rule<br>/// &#39;if the value is 0 alors the value is actually index&#39;</pre><pre>function mint() public {<br>    uint256 index = 1 + (randomNumber() % leftToMint);<br>    uint256 tokenId = _idSwaps[index];<br>   <br>    if (tokenId == 0) {<br>      tokenId = index;<br>    }</pre><pre>    uint256 temp = _idSwaps[leftToMint];</pre><pre>    // &quot;swap&quot; indexes so we don&#39;t loose any unminted ids<br>    // either it&#39;s id leftToMint or the id that was swapped with it<br>    if (temp == 0) {<br>      _idSwaps[index] = leftToMint;<br>    } else {<br>      // get some refund<br>      _idSwaps[index] = temp;<br>      delete _idSwaps[leftToMint];<br>    }</pre><pre>    // decrement so we will only get [1; leftToMint] next time<br>    leftToMint--;<br>    _mint(msg.sender, tokenId);</pre><pre>}</pre><pre># Code and explanation courtesy of <a href="https://twitter.com/dievardump">https://twitter.com/dievardump</a></pre><p>The beauty of this approach is that chances are uniformly distributed over all the left token ids and it’s also relatively cheap.</p><p>All sequences resulting from this approach have equal probabilities. Here the distribution over 100000 draws on a 4-ids sequence.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/715/1*7vYcTjOTDjnbhx7otaz5oQ.png" /></figure><p>It does this quite gas-efficiently, although (unlike the previous solution) it writes 2 <strong>uint256 </strong>instead of 1.</p><p><strong>Pros</strong></p><ul><li>Constant complexity</li><li>Cheap</li><li>Maximum un-predictability (assuming good enough random source)</li></ul><h3>Conclusions</h3><p>In this article I have shown <strong>some </strong>of the existing approaches aimed at solving common problems with dealing with big NFT collections.</p><p>In the code snippets, I have willingly omitted all the guards in order to focus the attention on the algorithmical aspect of the solution.</p><p>Many thanks to <a href="https://twitter.com/vrde">vrde</a>, <a href="https://twitter.com/dievardump">dievardump</a> and <a href="https://twitter.com/cxkoda">cxkoda</a> for their great contribution to this knowledge base.</p><p>Should you have any question, feel free to write <a href="https://twitter.com/the_innerspace">me on <em>Twitter</em></a><em> </em>or to any of the very kind contributors.</p><h3>Appendix</h3><p>Fisher-Yates shuffle from <a href="https://github.com/divergencetech/ethier">https://github.com/divergencetech/ethier</a></p><p>Modified by <a href="https://twitter.com/cxkoda">cxkoda</a></p><pre>/**<br><a href="http://twitter.com/notice">@notice</a> Computes the values in a shuffled list [0,n).<br><a href="http://twitter.com/dev">@dev</a> The library is a modified from github.com/divergencetech/ethier to allow in-memory shuffling.<br> */<br>library NextShuffler {<br>  struct State {<br>    uint256[] permutation;<br>    bytes32 entropy;<br>    uint256 shuffled;<br>    uint256 numToShuffle;<br>  }</pre><pre>/// <a href="http://twitter.com/notice">@notice</a> Allocates the internal state of the shuffler.<br>  function allocate(uint256 numToShuffle, bytes32 entropy)<br>    internal<br>    pure<br>    returns (State memory)<br>  {<br>    return<br>      State({<br>        permutation: new uint256[](numToShuffle),<br>        entropy: entropy,<br>        shuffled: 0,<br>        numToShuffle: numToShuffle<br>      });<br>  }</pre><pre>/**<br>  <a href="http://twitter.com/notice">@notice</a> Returns the current value stored in list index `i`, accounting for<br>  all historical shuffling.<br>   */<br>  function get(State memory state, uint256 i)<br>    internal<br>    pure<br>    returns (uint256)<br>  {<br>    uint256 val = state.permutation[i];<br>    return val == 0 ? i : val - 1;<br>  }</pre><pre>/**<br>  <a href="http://twitter.com/notice">@notice</a> Sets the list index `i` to `val`, equivalent `arr[i] = val` in a<br>  standard Fisher–Yates shuffle.<br>   */<br>  function set(<br>    State memory state,<br>    uint256 i,<br>    uint256 val<br>  ) internal pure {<br>    state.permutation[i] = val + 1;<br>  }</pre><pre>/**<br>  <a href="http://twitter.com/notice">@notice</a> Returns the next value in the shuffle list in O(1) time and memory.<br>  <a href="http://twitter.com/dev">@dev</a> NB: See the `dev` documentation of this contract re security (or lack<br>  thereof) of deterministic shuffling.<br>   */<br>  function next(State memory state) internal pure returns (uint256) {<br>    require(state.shuffled &lt; state.numToShuffle, &quot;NextShuffler: finished&quot;);</pre><pre>uint256 j = (_getRandom(state) %<br>      (state.numToShuffle - state.shuffled)) + state.shuffled;</pre><pre>uint256 chosen = get(state, j);<br>    set(state, j, get(state, state.shuffled));<br>    state.shuffled++;<br>    return chosen;<br>  }</pre><pre>/**<br>  <a href="http://twitter.com/notice">@notice</a> Generate a random number form the seed.<br>   */<br>  function _getRandom(State memory state) internal pure returns (uint256) {<br>    return<br>      uint256(keccak256(abi.encodePacked(state.entropy, state.shuffled)));<br>  }<br>}</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=63b83aa893d8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Snake in a Block — How I Ran Snake on Ethereum]]></title>
            <link>https://medium.com/@miragenesi/snake-in-a-block-how-i-ran-snake-on-ethereum-f46f9812abb1?source=rss-a99f3b6544e7------2</link>
            <guid isPermaLink="false">https://medium.com/p/f46f9812abb1</guid>
            <category><![CDATA[bitwise]]></category>
            <category><![CDATA[arcade]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[nft]]></category>
            <category><![CDATA[solidity]]></category>
            <dc:creator><![CDATA[miragenesi]]></dc:creator>
            <pubDate>Tue, 23 Nov 2021 15:33:20 GMT</pubDate>
            <atom:updated>2021-12-05T22:01:33.268Z</atom:updated>
            <content:encoded><![CDATA[<h3>Snake in a Block —How I Ran Snake on Ethereum</h3><h3>Brief Introduction</h3><p>Some months ago <a href="https://twitter.com/the_innerspace">I</a> and <a href="https://twitter.com/CaptPixel">a friend</a> decided to collaborate on an NFT. We wanted to create a piece of retro-game art that could be arcade in spirit. Something engaging, fun that would at the same time need to push the limits of its own technology to come to life. The same attitude that brought many legendary arcade games to existence. Remember how Nintendo managed to make the 1st <a href="https://en.wikipedia.org/wiki/Star_Fox">3D game for the SNES</a>, when that was not even imaginable for that type of hardware?</p><p>So we created the <a href="https://www.arcadeglyphs.io/">ArcadeGlyphs</a>. Simply put, it’s a generative NFT that, once minted, creates a Snake game. The twist is that the collectors only get the initial state of the snake. The creature will advance every hour, guided by a <a href="https://en.wikipedia.org/wiki/Greedy_algorithm">greedy search algorithm</a>. At the end of the game, the NFT turns (magic) into an animation of the game itself. The cherry on the top: we wanted to have NFT-prizes that the owners of the best game could claim “for free”.</p><p>Where is the complication? We wanted it to sit 100% on-chain. In the old days, if you wanted to make a mind-blowing game for a certain console, you had to be able to do it with the hardware that was already out there in the gamers’ houses. We wanted to give ourselves the same challenge.</p><p>In this article, we will explain in technical details part of the journey to minimize the gas needed to run the game so as to fit all that was needed within the block.</p><h3>Why Gas Matters</h3><p>Quick intro about gas: it’s a unit of measurement of the amount of computation that some Solidity code requires. It is used to estimate the cost related to a Solidity function call. There are 2 potential issues related to it:</p><ul><li>It determines how much the user will have to pay for a transaction (a “write call”). The more the gas consumed, the higher the transaction’s cost.</li><li>Read calls (so-called view functions in Solidity) should not be affected by gas, but each node may decide to still put some limits on it, to avoid resource exhaustion. These limits are not standard. Some allow double the actual gas limit, some less... It’s most importantly not clear what’s the Opensea configuration. One way to be safe is to keep it within the actual block gas limit.</li></ul><p>Back to the NFT look: it shows the current state of the game if the game is in progress, and an animation otherwise.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*vYwY7JQ7Yy_9uP4EYAOV_g.jpeg" /><figcaption>Game in Progress</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*dwO5K2NGMkQy4TymmhLzsw.gif" /><figcaption>Game Over</figcaption></figure><p>Both cases require the contract to be able to calculate the current state by using only</p><ul><li>the initial snake configuration (determined at minting time)</li><li>the current block.</li></ul><p>In a nutshell: it needs to simulate the game up until the current block. This was the only way to avoid transactions and still provide through-time-mutability.</p><p>The problem is that the simulation is an O(N) function, with N the number of moves. In the best case, the snake collides right away and not much needs to be calculated, but in the worst case, we might need to run through the full number of iterations.</p><p>Imagine a very lucky game that runs quite long. On a grid 11x11 the game could run beyond 400 iterations. On top of calculating the outcome of the game, the contract has to generate the SVG animation if the game is over (very gas-intensive). This should give you a hunch of why even saving 700 gas (this is the cost for an optimized log2 computation) could have a pretty perceivable impact at the end of the simulation.</p><p>The other point of saving on gas though comes from an extra feature we implemented: the token owners can redeem trophies for the best games. For example, collectors with a 42-score game could redeem the 1st place trophy (requiring at least 40 points). This “proof-of-score” requires running the whole simulation again. It would be cost-irrelevant for a view call, but in this case, the function needs (after the verification) to change the state of the blockchain, by transferring the trophy to the token owner. The final gas fee will then include the overhead of the “proof-of-score”, which is one of the fundamental reasons why gas efficiency was vital.</p><h3>Basic Operations</h3><p>To simulate the snake game, the minimum set of operations that the logic has to support is:</p><ul><li><strong>Collision detection</strong>: this can be between single points (e.g. head and apple), or multi-point objects (head and snake body)</li><li><strong>Movement</strong>: basically advancing the snake, either for real or while searching for the next best move</li><li><strong>Extension</strong>: the snake needs to grow, the more apples it eats</li></ul><p>We can then implement the simulation roughly like this:</p><pre>1: for each iteration<br>2:    move snake according to strategy<br>3:    if collision with wall OR snake body<br>4:      then break<br>5:    else if collision with apple<br>6:      extend the snake<br>7:      move apple</pre><p>When the collector wants to see the state of their snake after (say) 21 hours, the contract would run 21 such iterations to define how the game looks at that time. Let’s remember that that is an oversimplified version of the real algorithm. Line 2 and 7, for instance, are a whole piece of logic by their own. And ‘move snake’ is not merely 1 statement, but it involves advancing the head and the tail. This is just to say that there are a lot of devils in the details of that seemingly simple loop.</p><h3>Data Structure</h3><p>We will now show 2 different types of data structures that could be used to run the above-mentioned simulation. For each, we will show how the basic operations are implemented and the gas implications.</p><h4>Most Naive Solution</h4><p>Given that the Snake game-board is a grid, the most intuitive approach is to represent everything in a 2D coordinate system, where each element is either a point or a list of points. More specifically:</p><ul><li>Apple and Snake Head: uint[2] , the (x, y) coordinate of the point</li><li>Snake: uint[][2] an arbitrarily long list of (x, y) coordinates representing the space that the snake occupies in the grid</li><li>Wall: although it occupies points in the system, for the sake of collision detection, it’s enough to know what the boundaries are, so 0 and GRID_SIZE</li></ul><p>The different operations would then be implemented this way (pseudo-pseudo code):</p><pre>// Extend Snake<br>snake[nextPosition] = newHead</pre><pre>// Check apple-to-head collision<br>head[0] == apple[0] &amp;&amp; head[1] == apple[1]</pre><pre>// Check head-to-body collision<br>for (bodyPart in snake) { <br>   head[0] == bodyPart[0] &amp;&amp; head[1] == bodyPart[1]<br>}</pre><pre>// Check collision between wall and head<br>(<br>    head[0] &gt; 0 &amp;&amp; head[0] &lt; GRID_SIZE - 1 &amp;&amp;<br>    head[1] &gt; 0 &amp;&amp; head[1] &lt; GRID_SIZE - 1<br>)</pre><pre>// Check collision between apple and snake body (useful not to move // the apple over the body of the snake)<br>for (bodyPart in snake) { <br>   apple[0] == bodyPart[0] &amp;&amp; apple[1] == bodyPart[1]<br>}</pre><pre>// Move head right, left, up and down<br>head[0] = head[0] + 1<br>head[0] = head[0] - 1<br>head[1] = head[1] + 1<br>head[1] = head[1] - 1</pre><p>A quick benchmark on the different operations shows (very approximately) what they could cost in terms of gas</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/369/1*YRJMAMmOlLsEo7OlbO5A0w.png" /></figure><p>There is a clear point of optimization in the snake-to-point collision, but we should not underestimate all other operations, because they are repeated multiple times per iteration and they could have a snowballing effect.</p><p>With a 30M gas limit one could think this is still nothing to worry about, but the more precisely the simulation logic is implemented (including edge case handling, etc), the more operations like those listed above are needed, making it very likely that with a long game, the limit is breached. As mentioned already in the previous section, though, one other motivation to cut the cost is to allow a not-so-expensive trophy-claiming functionality.</p><h4>Better Solution</h4><p>The optimization objective was simple:</p><ul><li>Critical: decrease the computational complexity of the snake-to-point collision detection</li><li>Very desirable: decrease the single operation gas</li></ul><p>Decreasing the computational complexity of the snake-to-point collision is by itself easy. We could use a matrix where 1 indicates that the snake occupies that position in the grid, 0 otherwise.</p><p>We felt that there was an even more efficient way to work with this problem though.</p><p>The intuition was simple: what if every element in the game (snake, wall, apple, etc) could be represented by an integer such that all the snake-relevant functions could be then handled just with bitwise logic, executed straight into 1 processor instruction?</p><p>The solution was then to imagine the grid system as if it was 1 dimensional, with each coordinate (x, y) represented by a bit in a bit array.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/529/1*l7O2ilVarKK6OZVocvVcNQ.png" /></figure><p>Each bit would be set if that position was occupied. For instance, to represent a snake occupying the first 3 points in the grid:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/647/1*9jNbvO8ssIldJ7NbRdiqbQ.png" /></figure><p>A grid with 9 playable slots and a wall occupies 11x11 points, for a total of 121. We need 121 bits to be able to represent every possible element configuration within this system, which is achievable simply with a uint128 , which represents 128 bits integers.</p><p>To represent the snake above we would then use the number 14 ( 1 &lt;&lt; 1 | 1 &lt;&lt; 2 | 1 &lt;&lt; 3) where 0 and 10 positions are occupied by the wall.</p><p>The operations with this new representation would be:</p><pre>// Extend Snake<br>snake = snake | newHead</pre><pre>// Remove tail<br>snake = snake ^ tail</pre><pre>// Check apple-to-head collision<br>head &amp; apple == 0</pre><pre>// Check head-to-body collision<br>snake &amp; head == 0</pre><pre>// Check collision between wall and head<br>snake &amp; wall == 0</pre><pre>// Check collision between apple and snake body (useful not to move // the apple over the body of the snake)<br>snake &amp; apple == 0</pre><pre>// Move head right, left, up and down<br>head = head &gt;&gt; 1<br>head = head &lt;&lt; 1<br>head = head &gt;&gt; GRID_SIZE<br>head = head &lt;&lt; GRID_SIZE</pre><p>Checking the benchmark</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/552/1*yl_Cq95FIItZISBpUJ4PuQ.png" /></figure><p>All collision operations became not only O(1) but also as gas-efficient as they can get and the other operations considerably improved as well. All those listed above are indeed a subset of everything that needs to be done. But with this data structure, we could handle almost everything with bitwise logic.</p><p>Way to go. In the next chapter, we will clarify how the search algorithm (“AI”) has been implemented. Another insidious issue was hiding there as well.</p><h3>Greedy Search</h3><p>We tried to make the snake move at least halfway decently. The best solution we found that could still be implemented on a contract was a greedy search strategy where the snake follows a couple of heuristics:</p><ul><li>tries to decrease the Manhattan Distance from the apple</li><li>if not possible, try to decrease the Manhattan Distance from the tail</li><li>if not possible, “random” move</li></ul><p>The main issue with this algorithm (paired with the solution described above) is that it requires knowledge of x and y to decide how to minimize the distance. Given that we deal mainly with uint representations of the snake (including the head), to get x and y we need to do the following</p><pre>function getXY(uint coord) returns (uint x, uint y) {<br>    // Get bit position inside the int <br>    uint position = log2(coord)</pre><pre>    return position / GRID_SIZE, position % GRID_SIZE<br>}</pre><p>The log2 is unfortunately not natively implemented in Solidity and the most efficient implementation still costs 700 gas.</p><p>The naive implementation of the “AI” would then be to try each single move and check if</p><ul><li>a) it decreases either the x or y distance from the apple</li><li>b) it does not collide with either wall or snake itself</li></ul><p>This of course requires to know exactly what x and y are. But we don’t, we only know the integer representation. And going back to the 2D system would cost quite some gas.</p><p>The idea was to see if we could find a way to perform this same logic without ever passing through the 2D coordinates data structure again.</p><p>If the grid was actually a line, this would be easy: different positions are already naturally sorted. If I have head on 2 and apple on 15, we can safely tell the head to increase (so to move towards the apple). Unfortunately, we have a grid, so numbers that are distant in the int realm might be close once transposed to the grid. Example: what’s closer to P1 ? P2 or P3 ?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/377/1*3jDhECcCzCixQUCqnTOVCA.png" /></figure><p>Clearly P3. Let’s see how the integer representation of these coordinates is though:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/389/1*JyShXnbTaWAw-PfcgK1Edw.png" /></figure><p>From this perspective, P2 is closer to P1 than P3 .</p><p>The relations of distance in this representation do not allow us to make a proper calculation.</p><p>There is no way (to our knowledge) to have this information without first decoding the coordinates into x and y. BUT, there is another way to move the head in the right direction, still remaining in our efficient system.</p><p>What’s needed to know is whether the apple x is greater or smaller than the head’s x and just move accordingly. If smaller, move back, if greater, move forward. If the same, try with y .</p><p>Computing this information requires still a kind of decoding of x a y, but we don’t care about their exact value, we only care that the proportions between two decoded x are correct. If x1 &gt; x2 in the 2D data structure, it should be the same in this newly decoded version.</p><p>Now, focus.</p><p>Let’s say the head is on (1,9) (end of the first row) and apple on (2,1) (beginning of the second row). 0 and 10 in both axes are occupied by walls. What we want is that the snake notices that the head’s y (9) is greater than the apple’s y(1) so that we can instruct the head to move left (backward).</p><p>The problem is that head is encoded as 1048576, apple as 8388608, which is the opposite of what we are looking for. The reason is that the x coordinate pushes the set bit 11 positions to the left (as many as the grid size). Visually:</p><pre>// Spaces added to visualise the rows within the bit array<br>// head (1, 9)<br>00000000000 01000000000 00000000000</pre><pre>// apple (2, 1)<br>00000000010 00000000000 00000000000</pre><p>Every 11 bits refer to a row (x). What we need is a way to factor out the x part of the shift so that we can compare only the y part. Something that would bring us here</p><pre>// head decoded<br>00000000000 00000000000 01000000000</pre><pre>// apple decoded<br>00000000000 00000000000 00000000010</pre><p>The way we found to achieve this was with some brainfucky masking</p><pre>// --- This is the algorithm ---<br>// If it&#39;s the first row, we don&#39;t have to do anything<br>// If it&#39;s the second row, we should shift by GRID_SIZE * 1<br>// If it&#39;s the third row, we should shift by GRID_SIZE * 2<br>// ...</pre><pre>// --- This is how we implement it in bitwise logic ---<br>// &quot;If it&#39;s the first row&quot; becomes:</pre><pre>00000000000 00000000000 11111111111<br>                &amp;<br>00000000000 01000000000 00000000000</pre><pre>OR more simply </pre><pre>2047 &amp; p // this would now compute to 0</pre><pre>// &quot;If it&#39;s the second row&quot; becomes:<br>00000000000 11111111111 00000000000<br>                &amp;<br>00000000000 01000000000 00000000000</pre><pre>OR more simply <br>4192256 &amp; p // which computes to p</pre><pre>// &quot;we should shift by GRID_SIZE * 1&quot; becomes:<br>p &gt;&gt; 11</pre><pre>// How to make sure the shift happens only if the correct row is <br>// found?</pre><pre> (2047 &amp; p)<br>| (4192256 &amp; p) &gt;&gt; 11<br>| (8585740288 &amp; p) &gt;&gt; 22<br>.....</pre><p>At the end of the execution of this chain, we will get 2 comparable values of y. So head = 512 and apple = 2. Way more efficiently than going with the log2 decoding. We won’t know the position in the grid, but we will know enough to instruct the snake where to move. This way:</p><pre>...<br>if(head &gt; apple &amp;&amp; !isCollision(p1 &gt;&gt; GRID_SIZE)) {<br>     return p1 &gt;&gt; GRID_SIZE; // this stands for &quot;move backward&quot;<br>}<br>...</pre><p>From here on, it was possible to compute the next move mainly with bitwise logic.</p><h3>Conclusion</h3><p>Some non-thorough tests have been done to also check whether assembly optimized code would have worked as well, but we noticed a small if not irrelevant gain which did not justify the effort of rewriting everything in machine code. Definitely, a challenge we will consider for the next game, should this first project work.</p><p>Bitwise logic makes the code much harder to grasp, but its benefits in terms of efficiency gains are superb. With a technology where optimization saves actual money, it’s a no-brainer to go with it.</p><p>Keep in touch, we will make another article explaining how we could generate the SVG animation within the same function call, still remaining within limits.</p><p>Also, feel free to check out the <a href="https://www.arcadeglyphs.io/">NFT page</a> and the <a href="https://etherscan.io/address/0xd723190ea96380e00ea21bd88ed53baf76a84253#code">mainnet contract</a>, in case you’d like to give us any feedback or support.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*AYoao0gtdkaBDIQevv3OWw.png" /><figcaption>The Logo</figcaption></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f46f9812abb1" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>