我們是探索性的物種，剛剛跨出太陽系，但也許有一天我們會回望並稱我們的銀河系只是第一個。沿途有許多問題待解決，今天我們將探討其中一個非常小的問題：我們如何為裝置（或任何物件）分配識別碼，使其永遠保證唯一？
能夠識別物件是建立其他協議的基本工具，也支撐製造、物流、通訊與安全。每艘船與衛星都需要識別碼以便交通管制與維護紀錄。每個無線電、路由器與感測器都需要識別碼，讓封包有來源與目的地。每個製造零件都需要識別碼以便追蹤。且在大規模下，數量爆炸：機器人群、兆級零件、以及文明供應鏈中無數貨櫃。
識別碼的關鍵功能之一是區分物件，因此我們必須確保不會重複分配相同的識別碼。當嘗試在宇宙規模解決此問題時，唯一識別碼的分配變得更具挑戰性。
最簡單的解決方案是每次需要識別碼時隨機挑選一個數字。
這非常簡單，可能是最佳方案；你可以隨時隨地執行，無需中央權威或任何協調。
大問題是兩個裝置可能碰巧選到相同的識別碼。幸運的是，我們可以完全控制隨機數的大小，進而控制碰撞機率，這意味著我們可以將碰撞機率降到實質為零。
你可能會說「實質為零」還不夠，雖然機率很小，但不是真正的零，這讓你擔心。但想想這個例子：你現在被隕石擊中的機率很小但非零，你甚至可能認為這是「合理的」（如果有點偏執的）擔憂。但你會擔心地球上每個人同時被隕石擊中嗎？那機率也是非零，但極其微小到我們視為不可能。這就是我們能將識別碼碰撞機率降到的程度。
那麼，我們需要多小的機率才會安心？換個角度問：我們能產生多少識別碼才會預期發生碰撞？
最新版本的通用唯一識別碼（UUID）使用122位隨機位元。利用生日悖論，我們可計算出預期碰撞前可產生的識別碼數約為2的61次方。
這數字高還是低？是否足以支撐人類銀河系擴張直到宇宙熱寂？讓我們透過宇宙的物理極限來計算一個原則性的數字。
論文「Universal Limits on Computation」計算出若整個宇宙是最大效率的電腦（稱為computronium），在宇宙熱寂前最多可執行10的120次方次運算。若假設每次運算產生一個新識別碼，我們可計算識別碼大小需多大才能避免碰撞直到宇宙耗盡時間。
利用生日悖論近似，n個隨機數在d個值集合中碰撞機率為
我們希望碰撞機率p=0.5（即預期會碰撞）且n=10的120次方，解出d為
這就是避免碰撞直到宇宙熱寂所需的識別碼空間大小。以位元計算，需log2(10的240次方)=797.26，至少798位元。
這是最極端的上限，有點過度。用798位元，我們可以為所有物件分配識別碼，從每個裝置、微晶片、微晶片零件、每次按鍵、每個時鐘滴答、每顆恆星到每個原子，全部都能被唯一識別且不會碰撞。
較合理的上限是假設可觀測宇宙中每個原子都獲得一個識別碼（假設原子不會在時間中被多次分配識別碼，這是妥協）。宇宙中估計有10的80次方個原子。用同樣公式計算，需532位元以避免碰撞。
或者我們將宇宙所有質量轉成1克的奈米機器人？約有1.5乘以10的56次方個機器人，需372位元識別碼。
現在我們有四種識別碼大小可選，取決於你的偏執程度：
請注意，以上假設生成隨機數時是真正隨機，但這有時是挑戰。許多隨機數生成器使用偽隨機數生成器且種子非隨機。你應確保硬體能引入真正隨機性，如量子來源，或使用密碼學安全偽隨機數生成器（CSPRNG）。若無法使用，可用感測器資料、時間戳或其他非決定性來源增加隨機性，但不會是純隨機，會增加識別碼碰撞機率。建議禁止使用「常見」識別碼，如每個知名偽隨機生成器的前1000個ID、全零ID、全一ID等。
但如果我們極度偏執，要求識別碼理論上保證唯一？不接受機率論的模糊。這將帶我們展開一段旅程。
如往常，從最簡單方案開始。
所有視覺化、模擬與分析程式碼可在此github倉庫找到。
我們建立一台中央電腦用計數器分配識別碼。當有人請求識別碼時，分配計數器當前值，然後遞增計數器，確保下一個識別碼唯一。此方案保證唯一且識別碼長度以對數速度成長。
若所有1克奈米機器人都從此中央電腦獲得識別碼，最長識別碼長度約為log2(1.5乘以10的56次方)=187位元。實際會稍長因為變長編碼的開銷，暫且忽略。
此方案最大問題是存取。若你在遙遠星球無法與中央電腦通訊？或距離太遠，取得識別碼需數日？不可接受。
為解決此問題，我們可能派衛星向四面八方分發識別碼。想像第一顆衛星ID為0，第二顆為1，依此類推。人們只需向最近衛星請求識別碼，回傳格式為A.B，其中A是衛星ID，B是衛星上的計數器。例如第四顆衛星分配第十個識別碼為3.9。此法確保識別碼唯一且取得更方便。
但為何只限衛星？為何不讓任何有識別碼的裝置都能分配新識別碼？
例如殖民船由衛星13獲得第六個ID，ID為13.5。殖民者前往遙遠星系，無法通訊。抵達星球後建造建築機器人需新ID。無法向衛星請求，但可向船請求。建築機器人獲得13.5.3與13.5.4，因船已分配3個ID，計數器為3。這些機器人也能分配ID！
此假設附近至少有一台能分配ID的裝置。若你能製造新裝置，附近應有至少一台舊裝置。
我們稱此命名方案為Dewey。
Dewey與隨機ID在位元需求上如何比較？
若ID形式為A.B....Z，可用Elias omega編碼。暫時忽略編碼開銷，假設每數字完美以二進位表示，ID 4.10.1二進位為100.1010.1，共8位元。每個值隨計數器以對數成長。
ID成長取決於分配順序。舉例：
若每新裝置向原始裝置請求，形成擴展子樹，ID以對數成長，與中央電腦模型相同。
若每新裝置向最近裝置請求，形成鏈狀，ID線性成長。
若每新裝置隨機選擇裝置請求，成長介於線性與對數間，稍後探討。
最佳與最差分配樹為何？可模擬選擇最佳或最差節點觀察。多種方式呈現最佳與最差，因多ID長度相同，任意選擇一種。此為單節點前瞻，複雜方案可能失效，但此處有效。
最差樹為鏈狀。Dewey最佳樹為每節點子女數翻倍再重複，快速擴展寬度。此方案適合新裝置多向已有多子女節點請求，不適合新裝置向新節點請求（鏈狀極端）。
大規模最佳樹圖形更直觀，呈現密集圖，表示此方案適合人類從少數節點請求ID。
鏈狀導致ID線性成長令人困擾。能否設計更好方案，使鏈狀也對數成長？
另一方案：將ID空間視為二元樹。每裝置ID位於樹上，分配新ID時，裝置分配其下方欄位（欄位左右交替）。此方案每節點有唯一ID，且有無限ID可分配，且每ID也有無限ID可分配，依此類推。
觀察子樹與鏈狀成長，兩者皆線性成長，非預期。
此方案是否總比Dewey差？
最佳與最差案例顯示最佳樹成長不同於Dewey。
大規模最佳樹呈現各方向均勻成長，深度成長快於Dewey，適合新節點等機率向老舊與新節點請求。最佳樹為每節點新增子女再重複。
此方案對某些樹結構優於Dewey，繼續探索。
實際上有一方案外觀不同但成長相同。
若ID為整數，節點ID為n，則第i子女ID為2的i次方乘以(2n+1)。每子女ID為前一子女ID的兩倍，第一子女ID為2n+1。此基於2-進位估值。
可用算術基本定理證明此方案生成唯一ID。
可用(i, n)取代2的i次方乘以(2n+1)作為ID，子女ID序列對數成長，類似Dewey。
雖複雜，實為先前二元方案的另一表示。仍想探索記憶成長更佳方案。
嘗試逆向設計鏈狀對數成長方案。
計數器對數成長，理想ID新增節點時只遞增計數器。
一想法是傳遞帶跳數的token給子女。若裝置無token可傳，父節點產生新token並附加於ID。三節點鏈為[]、[(0,0)]、[(0,1)]，根節點無token，第一子女觸發根產生token，下一跳token傳遞並遞增跳數。若根節點再有兩ID請求，產生[(1,0)]與[(2,0)]，遞增token索引產生唯一token。每ID為(token索引, 跳數)對列表，按創建順序排列。模擬顯示子樹擴展、鏈狀與最佳案例。
ID較長因資訊多，但極端案例仍對數成長。
大規模最佳樹顯示長鏈從根節點延伸。
但鏈狀對數成長是謊言。若任一節點多一子女，成長即線性。若圖同時深與寬成長，回到線性。模擬使用貪婪搜尋，未產生最差圖，真最差圖硬編碼顯示線性成長。
尚未找到所有情況皆對數成長方案。是否可能設計始終對數成長方案？
為證明方案成長速度，考察新增節點時可能ID數成長。需遍歷所有分配歷史並計算所有可能ID數。
重要的是每條路徑必須產生不同ID，否則會有重複ID。
以4節點樹為例，標記節點用1起始Dewey系統。標籤非ID，僅用於討論路徑與節點。
可見所有達第4節點路徑，共16節點，代表4節點樹需16個唯一ID。
一般而言，每新增ID，會為所有節點新增葉子，ID需求以2的(n-1)次方成長。
標籤值總和等於節點加入迭代數。所有n節點路徑可由整數組合產生，結果同為2的(n-1)次方路徑。
問題是，即使理想情況下用計數器標記所有可能節點（即2-進位估值方案），計數器記憶體以對數成長。無論方案如何，記憶體至少線性成長。
雖證明最差情況線性成長，但不同算法對不同成長模型表現不同。若找到合理人類宇宙擴張模型，應能反推最佳算法。
考慮人類宇宙擴張模型。
最簡模型為隨機父節點選擇。每新增裝置隨機選擇先前裝置請求ID，形成隨機遞歸樹。模擬規模約2048節點，使用Elias omega編碼以便與隨機ID位元使用比較。
最佳方案為Binary，其次Dewey，Token最差。合理，因隨機樹深寬均衡，Binary為最佳。
考慮偏好附著隨機圖，節點較可能連接度數高節點，符合多真實網路。樹寬度主導深度，預期Dewey勝出。
結果顯示Dewey最佳，Token次之，Binary遠後。
但裝置因分配ID多而更受歡迎不太合理。合理假設裝置受歡迎度與歷史無關，如衛星因位置易請求ID較受歡迎。可用適應度模型，節點初始適應度從指數分布抽樣。
結果Dewey與Binary表現相當，Token最差，與純隨機圖相似。
需大量模擬與節點數驗證趨勢。
執行1000次模擬，節點數達百萬(2的20次方)，繪製最大ID長度隨時間變化。x軸採指數尺度，便於觀察對數成長。
結果顯示大多數圖呈直線，Binary在偏好與適應度模型稍有曲線。直線表示ID成長為對數函數。
偏好模型去除Binary後，Dewey與Token仍呈線性趨勢，顯示對數成長。
隨機模型中，節點統計上無差異，預期每節點子樹平均相似。此暗示可用遞迴關係推斷整體尺度律。
模擬1000節點樹，最大ID長度增加約34位元（Dewey）。取最大ID節點再模擬1000節點子樹，預期ID長度再增約34位元。
此子樹嵌入完整樹中，當子樹達1000節點，原樹其他節點平均也有約1000後代。每模擬1000節點子樹，完整樹規模增千倍，最大ID長度增常數。
實際觀察增約38位元，可能因雜訊、小節點效應、編碼開銷或啟發式缺陷。
此意指ID長度線性成長，節點數指數成長。最大ID長度函數滿足遞迴式T(n*1000^d)≈T(n)+34d，解為對數函數T(n)∝log(n)，底數約1.225。
適應度與偏好模型因節點異質，分析較難，但圖形顯示可能仍成立。更大規模模擬或有助判斷趨勢是否非對數。
未來模擬可考慮裝置壽命（節點消失），可能大幅改變分析。初步測試固定壽命顯示ID隨時間線性成長，合理因強制寬鏈狀，所有方案皆線性成長。若裝置壽命與受歡迎度相關，結果如何？
目前以此模擬為基礎，將結果套用於更大模型，再套用更大模型。
為估算宇宙規模人類所需位元，需評估星球間ID成長模型。
使用適應度模型百萬節點模擬，模擬星球表面數年ID分配。以對數曲線擬合適應度模型，外推至數百年全星球。
選擇Dewey方案，因其在各成長模型表現良好。
擬合適應度模型中Dewey最大ID長度對數曲線為(6.5534±0.2856)ln(n)，標準差0.2856。此方程可近似任意裝置數最大ID長度。
有星球擴張模型，需星球間擴張模型。無法確知人類宇宙擴張真貌，但已有相關研究，本文參考並建立相關模型。
星系內星球擴張以恆定速度波前展開，佔領適居星球，新星球由最近已佔領星球隨機ID種子。星系間擴張同理。
此模型導致ID長度隨波前擴展線性成長。每星球重新開始ID分配，ID長度依星球內曲線增加。
估計銀河系約有400億適居星球，觀測宇宙約有2兆星系。
假設星球均勻分布於球體，星系半徑以星球跳數計算約2121。
假設每星球產生10億ID後佔領下一星球，ID長度增量為每星球ID增長乘以星球跳數。結果不樂觀。
位元數龐大，且只會更糟。星系間同理計算，跳數約7816。用前述每星系ID增長288048位元，總位元數極大，約281.4MB記憶體存ID。
此確定性方案遠不及隨機方案，後者最偏執情況也只需798位元。
或許可規定殖民者攜帶數千最短ID，減半ID長度，但若無法使ID跨星球與星系對數成長，仍遠遠不足（2121乘7816共約1657萬星球跳數）。
目前看來，最安全的宇宙唯一識別碼仍是隨機數，範圍足夠大使碰撞機率實質為零。但探討如何將機率降至零、設計不同分配方案、模擬與建模人類宇宙擴張過程，過程十分有趣。
所有視覺化、模擬與分析程式碼皆可於我的github倉庫取得。
此為探索性研究，仍有許多路徑未探，歡迎交流討論，樂趣無窮。
感謝Kevin Montambault與Jacob Hendricks願意與我長時間討論這些奇特興趣，深感榮幸與感激。
另一有趣面向是安全性。可用簽章防止ID偽造，驗證身份與訊息來源。隨機方案用公鑰作ID，確定性方案節點可簽署子節點公鑰，驗證簽章鏈至根節點。重放攻擊可用挑戰機制防範，雖在單向或延遲通訊（星球間）困難，訊息可標記為未確認直到挑戰驗證。
應為ID加入錯誤更正碼，避免讀取錯誤。因錯誤更正方法多樣，應附版本號。
某些物件無法自行存ID，如星球，可能導致多個ID誤指同一物件，應存物件ID列表，涵蓋所有指向該物件的ID。
存在忒修斯之船問題：物件ID隨零件逐步更換是否仍同一ID？實務解法是將ID存於特定硬體，ID即代表該硬體，不論連接何物。
相關主題包括去中心化識別碼（DIDs）與祖譜標記方案。