How ERC721Psi Work
最近剛好看到有人介紹 ERC721 相關的變形。其中 ERC721Psi 又是其中針對 降低 gas cost 最有效率的一個，於是興起了研究的想法。這邊跟大家介紹一下 ERC721Psi 主要改進了什麼和用什麼方式改進
Introduce ERC721
ERC721 是目前主流的 NFT 的格式之一（另外還有 ERC1155)。大家對於 NFT 的需求增高，隨之而來的就是成本的降低。各種 ERC721 的變形也就孕育而生。介紹一下 ERC721 的一些概念，這些概念有助於理解上ERC721Psi 是如何減少 gas cost。在 ERC721 中每一個 token 對應一個 NFT，每一個 token 都有自己的 tokenId 和 owner 。在 ERC721 合約中會有一個 _owners 的 map 來記錄 tokenId 對應的 owner 。當你在傳送 token 給其他人的時候，就會去修改 _owners 該 token 的 owner。
當你同時 mint 多個 NFTs 的時候，你需要對這些 NFTs 在 _owners 對應的位置寫上你的 address 來表示你是這些 NFTs 的 owner。這也導致在 mint 多個 NFTs 時所需要花費的 gas 會是 mint 單一個 NFT 時的複數倍。那有什麼方式可以減少 gas cost 嗎？
ERC721A
ERC721A 是由著名的 NFT Project — Azuki 開發團隊所發表。其中針對於 mint 多個 NFT 所花費的 gas cost 進行了改善。
其原理我用一個範例來解釋。假設今天我 (Albert) 一口氣去 mint 第50號～第54號的 NFT (50,51,52,53,54)。如果是原本 ERC721 的做法，在這些 NFTs 都會寫上 owner 是 Albert。
若是 ERC721A 的做法會變成，只有第一個 (#50) 的 NFT 會填上 owner = Albert 。其他的 NFTs (#51~#54) 都會是 owner_not_set 的狀態。
若我們今天想要把 #53 NFT 轉移給 Bob 時，要如何知道 #53 NFT 的 owner 就是 Albert 呢？此時我們只要從 #53 NFT 往前找，找到第一個有 owner 的 NFT，該 owner 就是 #53 NFT 的 owner。此時只要把 #53 NFT 的 owner 填上 Bob ，並把 #54 NFT 的 owner 填上 Albert 就可以了。若沒有把 #54 NFT的 owner 也一併填上 Albert 話，會導致連 #54 NFT 都是 Bob 擁有。
可以從上圖發現從 #53 NFT 要確認 owner 是 Albert 需要往前找三個 token 才知道 owner 是 Albert。那有什麼方式可以快速知道這件事嗎？這個就是 ERC721Psi 想要改善的問題。
ERC721Psi
ERC721Psi 利用神奇的演算法有辦法快速定位距離 #53 最近有 owner 的 NFT 是哪一個。在解說之前有一些觀念需要先跟大家解說一下，方便等一下知道是如何運用在 ERC721psi 中。
Bitmap
因為存在電腦中的資料都是以二進位方式儲存，二進位的特性來記錄和運算資料。其中每一個 bit 我們都個別可以拿來記錄資料。舉例現在有三個 NFT (#1, #2 和 #3），我們可以使用一個 uint8 的變數和搭配 bitmap 的方式來記錄他們有沒有 被 mint。 因為uint8 變數以二進位表示剛好有 3 bit ( 000 )。當每一個 bit 為 0 的時候我們可以視為沒有被 mint，當 bit 為 1 可以視為已經被 mint 出來了。上面那張圖表示 #1 NFT 已經被 mint 出來了，#2 和 #3 還沒有，此時 uint8變數值為 4 (十進位）。下面那張圖的 uint8變數值為 5 （十進位），表示 #1 和 #3 皆都 mint 出來，唯獨 #2 還沒有。
De Bruijn Sequence
de Bruijn sequence 是指有某種特性的數列。當這個數列是由 k 種字母組成，給定長度為 n 的連續子數列，總長度為 k^n 。每一種子數列裡面的組合皆不一樣，這種數列我們就稱之為 de Bruijn sequence （標示成 B(k, n)）。舉例來說，我們設定 k= 2 ，字母就選 0 和 1 表示。n = 3：代表連續子數列長為 3。整個數列長度會是 2³ = 8。 數列 00010111就剛好是符合這些條件的其中一種 de Brujin Sequence。由下圖可以發現每個 sub-sequence 都是不同的排列組合。若把他們轉成數字會發現每個 sub-sequence 都會對應一個唯一數字。
How to index the owner of token Id
用一個例子來說明在 ERC721Psi 是怎麼利用上面兩個技術來達成快速找到 owner 。在 contract 裡面是用 256 bitmap 來記錄 owner。為了大家理解方便，我們這邊還是使用 8 bitmap 來說明。 主要的 function 是 BitMaps.sol 的 scanForward(uint256 index) ( index 是指 tokenId)。
Use Bitmap to record the existement of the owner of tokenId
uint256 bucketIndex = (index & off) 把 index 除與 256 來獲得此 tokenId 會是放在哪一個 bucket。一個 bucket 是以 256 為一個單位（表示存放了 256 tokenId 的 owner)。 uint256 bucketIndex = (index & 0xff) 計算出在該 bucket 中這個 tokenId 對應的位置。 bb = bb >> (0xff ^ bucketIndex) 是將要查詢的 tokenId 對應的 bitmap 移到最右邊。情形會如同下圖所示。Batch Head 就是我們要找該 tokenId 的 owner
Find LS1B
我們希望 tokenId 往左邊第一個 bit 為 1 的位置留下來，其他都設成 0 。這邊使用了一個小技巧，如 isolateLS1B256(uint256) 所示。
呈現的效果就會如同下圖所示，除了從右邊數來第一個 1 的位置是 1 之外，其他都為 0 。
圖中可以發現距離 1 的位置有三個間隔，所以表示我們需要往右移動三次。那有什麼方式可以不用移動三次就可以知道 1 的位置呢？這就要用到 De Bruijn Sequence
利用 De Bruijn Sequence 快速找出與 LS1B 的距離
De Bruijn Sequence 就以前面的 000101111 做範例。我們現在已經知道 LS1B ( 00001000) 是在右邊數過來第四個位置。此時把 LS1B ( 00001000) 和 De Bruijn Sequence(000101111 ) 做相乘，等同於跟把 De Bruijn Sequence(000101111 ) 往左移 4 個 bit。之後再把得到的結果往右移 k^n-n 位數（範例 k=2, n=3, 2^3-3 = 5)。可得到對應的且唯一的 sub-sequence( 101)。
因為唯一 sub-sequence 會對應一個唯一數字。我們可以針對這些數字建立一個 map (or lookup table)。key 為 sub-sequence number， value 為與 LS1B 之間的距離。這樣就可以直接快速定位出與 LS1B 的距離而不需要利用輪詢的方式找出。
Gas Cost
可以發現不管是在執行 mint 或者做 transfer 所花費的 gas 都有顯著的減少。
Takeaway
以上就是主要 ERC721Psi 用來減少 gas cost 主要用到的技術。熱門的 project所消耗的 gas 可以說是非常驚人。所以現階段在開發 dApp 時候，gas cost 也會成為主要考量之一。ERC721 Psi 開發者使用的手段非常精妙，非常值得學習。但因為 ERC721Psi 尚未經過市場驗證，是否能保證一定安全無虞，還需要時間的考驗。隨著 L2 或其他 L1 公鏈的興起，gas cost 有機會可以大幅下降。屆時 dDapp 的架構會可以進一步更加複雜，能實現的更多的功能！