# How ERC721Psi Work By [Albert.Lin](https://paragraph.com/@albertlin) · 2022-06-25 --- 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`。 ![](https://storage.googleapis.com/papyrus_images/c00300698881b4a01aadae9bdb2323c417acfa8ce7b89f2b06b6862e874f6f76.png) 當你同時 mint 多個 NFTs 的時候，你需要對這些 NFTs 在 `_owners` 對應的位置寫上你的 address 來表示你是這些 NFTs 的 `owner`。這也導致在 mint 多個 NFTs 時所需要花費的 gas 會是 mint 單一個 NFT 時的複數倍。那有什麼方式可以減少 gas cost 嗎？ ERC721A ======= ERC721A 是由著名的 NFT Project — [Azuki](https://www.azuki.com/) 開發團隊所發表。其中針對於 mint 多個 NFT 所花費的 gas cost 進行了改善。 ![](https://storage.googleapis.com/papyrus_images/255c27d6b90abb47097dca77a6631d836ed885c6da81908c5f90c751a6ffc259.png) 其原理我用一個範例來解釋。假設今天我 (Albert) 一口氣去 mint 第50號～第54號的 NFT (50,51,52,53,54)。如果是原本 ERC721 的做法，在這些 NFTs 都會寫上 owner 是 Albert。 ![ERC721](https://storage.googleapis.com/papyrus_images/2bc85a0dd6e20b6638f22be25e9107cca878a54b2e1aff1f36ccb7046cf39121.png) ERC721 若是 ERC721A 的做法會變成，只有第一個 (#50) 的 NFT 會填上 owner = Albert 。其他的 NFTs (#51~#54) 都會是 `owner_not_set` 的狀態。 ![ERC721A](https://storage.googleapis.com/papyrus_images/a0c3f32a27f0f936a69b20d511b66b8f809243cccd7e2dc9ba9bfaa8db9c624e.png) ERC721A 若我們今天想要把 #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 擁有。 ![transfer #53 to Bob](https://storage.googleapis.com/papyrus_images/fbfb427c830e4c06b867a6f5fcadff29f5ac1ac8fcb8ddb4f5dcae2b7275a3d9.png) transfer #53 to 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 還沒有。 ![](https://storage.googleapis.com/papyrus_images/67a1c739807b27db160c13ee5056cd9042d772f11ffbd3a72c06e54e9bc4bc5c.png) 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 都會對應一個唯一數字。 ![](https://storage.googleapis.com/papyrus_images/58779adc98aea7c406c1ea862406fa25e9a22e31bce37737680d726dbc73faed.png) 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 ----------------------------------------------------------- ![](https://storage.googleapis.com/papyrus_images/2a1dedde280190f35f003cf41a306e4e6ee4d8b9a0d1fabd07d5f88bc2a92cb3.png) `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 ![](https://storage.googleapis.com/papyrus_images/89ca3f78cdd0a66ea9ecbfe0e099856b6673f0d05fdc692cccdc4929a220e8e6.png) Find LS1B --------- 我們希望 tokenId 往左邊第一個 bit 為 1 的位置留下來，其他都設成 0 。這邊使用了一個小技巧，如 `isolateLS1B256(uint256)` 所示。 ![](https://storage.googleapis.com/papyrus_images/8b5dd3a2bca7c2a52a4cb08004e8d330223936c63b08a0ff04c1096ff77cbcb9.png) ![](https://storage.googleapis.com/papyrus_images/a8b173b3ec7203176e2f7863a96dd0461d06e22d06817a25167c533293202f4f.png) 呈現的效果就會如同下圖所示，除了從右邊數來第一個 1 的位置是 1 之外，其他都為 0 。 ![](https://storage.googleapis.com/papyrus_images/b505aedb695e52de0c6e493d98152bcc6472e58fba71f186f356961532b16130.png) 圖中可以發現距離 `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`)。 ![](https://storage.googleapis.com/papyrus_images/2572f20c44e7ca051641cc523f207a60e70816191df3d8f1996c7717ac799882.png) 因為唯一 sub-sequence 會對應一個唯一數字。我們可以針對這些數字建立一個 map (or lookup table)。key 為 sub-sequence number， value 為與 LS1B 之間的距離。這樣就可以直接快速定位出與 LS1B 的距離而不需要利用輪詢的方式找出。 ![](https://storage.googleapis.com/papyrus_images/1e254140834716edab52a17aa417b994095d050bf36279b869e20a96d4b3cbba.png) Gas Cost ======== 可以發現不管是在執行 mint 或者做 transfer 所花費的 gas 都有顯著的減少。 ![](https://storage.googleapis.com/papyrus_images/8b8304a55421a52bd4b733485f57a8bf4222efc438c761a2c5ffd26a1aabe3e7.png) ![](https://storage.googleapis.com/papyrus_images/3bba80ec866a7c7192d87ca5511d6303f036c87b10a1d69922912c56e8e98cba.png) Takeaway ======== 以上就是主要 ERC721Psi 用來減少 gas cost 主要用到的技術。熱門的 project所消耗的 gas 可以說是非常驚人。所以現階段在開發 dApp 時候，gas cost 也會成為主要考量之一。ERC721 Psi 開發者使用的手段非常精妙，非常值得學習。但因為 ERC721Psi 尚未經過市場驗證，是否能保證一定安全無虞，還需要時間的考驗。隨著 L2 或其他 L1 公鏈的興起，gas cost 有機會可以大幅下降。屆時 dDapp 的架構會可以進一步更加複雜，能實現的更多的功能！ Reference ========= * [ERC721PSI](https://www.slideshare.net/EstarriolVetch/erc721psi) * [ERC721 Github](https://github.com/estarriolvetch/ERC721Psi) --- *Originally published on [Albert.Lin](https://paragraph.com/@albertlin/how-erc721psi-work)*