Atlas
Atlas
名詞
1.拉丁文，來源於希臘神話，泰坦神族的成員，Iapetus與Oceanid Asia (或Clymene)之子，被罰永世擎住蒼穹。
2.韋氏字典中，一個有界地圖合集，通常含有插圖與信息表。
3.支撐全球地圖服務的空間共識區塊鏈。
一、ATLAS目標
海伯利安催生出一個服務100億人的去中心化全球地圖經濟體系，而Atlas即是支持海伯利安，使其可基於區塊鏈提供全球地圖服務的關鍵組成。同行審議機制已在實踐中證明其有效性，於是我們深入研究並作出一些創新，設計了Atlas。Atlas將專注於可伸縮的空間區塊鏈的通用性，提供支持某些特定功能例如定位、位置搜索的可擴展智能合約。除滿足去中心化的內部需求如抗審查、開放參與、高容錯等，Atlas還致力於滿足以下設計目標：
高可伸縮性：按照Google s2層次結構中最細粒度的劃分，地球表面可被劃分為6*2^60個單元，一個單元最大面積不足1cm2。根據騰訊的報告，我們預計100億用戶每日的定位請求可達8千億次。將近1/3的谷歌搜索，是基於位置的。數十億物聯網設備分布在地球各處，以空前的體量感知、測量著這個世界。數據之廣，用戶之多，對服務的可伸縮性提出了極高的要求。
低延遲性：高延遲的地圖服務會嚴重影響用戶體驗，導致一些實際的後果。例如，在高速行車的過程中，地圖服務延遲可能導致用戶錯過變道等，造成額外的行駛時間、更多的高速費用，這類情況是非常普遍的。延遲性還會影響數據的時效性，對於自優化網絡、自動車輛等應用來說，影響甚至可能是毀滅性的。
低成本：地圖服務對於普通個人用戶而言通常是免費的，而對於企業卻非常昂貴。最近谷歌地圖的收費定價做了大幅調整，取消了許多免費的調用額度，這對於依賴其地圖服務的企業無疑造成了巨大的成本上漲。與此同時， mapbox以其更低的定價，吸引到了不少用戶，其中不乏眾所周知的應用商如snapchat。
隱私保護：個人用戶得以免費使用地圖服務，是以接受競價排名的地點搜索、基於位置的廣告為代價的。最近，TechCrunch報導稱谷歌保存了用戶的歷史位置數據。除用戶軌跡數據的隱私，敏感的地圖數據隱私也包含在內。
可擴展性：通過智能合約，為基於位置的地圖服務如定位、鄰近搜索等，提供原生的高性能交易。支持任意位置數據的索引，包括靜態地圖數據、時序性傳感數據與位置軌跡。
交互性：Atlas作為主宰位置服務的神，通過雙向輕量交易驗證提供跨鏈通訊，並與繼鏈平臺如Polkadot整合。
二、彈性空間分區
1. 挑戰
彈性
這個時代的數據產生速度和存量是空前的，隨之而來是數據在時空維度同樣空前且複雜的傾斜。因此，處理數據傾斜、平衡負載與索引大規模的動態位置數據的能力，對於海伯利安是十分必要的。此外Atlas網絡還將持續增加社區支持，以持續增加網絡吞吐量。
空間
位置是許多數據的元數據，如物聯網數據等天然即是地理空間相關的。Atlas需要索引各種形式的位置數據，以外鍵關聯，支持高容錯分布式資料庫與存儲。
基礎地理空間請求，如多邊形包含、交叉與空間連接操作，需要高效與健壯的多維索引技術。然而如果需要實現高頻的目標插入，R樹索引需要高昂的重構成本，使得平衡樹結構難以實現。而使用四叉樹，又難以處理高效的非點數據索引。因此我們需要一個新的高效、劃分友好的空間索引數據結構，能夠索引、查詢大規模位置數據並保證高性能。
分區
如前文所提到的，空間數據規模之大與對速度要求之高，對海伯利安是充滿挑戰的。現存的空間索引技術如GiST，並非為大規模的並行與分布式環境、且數據變化頻繁複雜的場景而設計的。因此，讓所有Atlas區塊鏈網絡中的機器驗證每一次交易，是不現實也不必要的。分區允許在驗證器增加時，網絡總吞吐量線性／亞線性地增長。
2. 解決方案
Atlas設計了一個分區結構，針對大規模並行操作包括預處理、索引與查詢空間數據，保證數據更新快速且位置保持，具有抗數據傾斜、延遲創建等屬性。為此，我們研究了位置數據的內部特徵，並著重探索其位置保持、易並行的部分。借鑑希爾伯特曲線（一種分形空間填充曲線）的不同特徵，我們有以下設計上的考慮：
空間填充：使地球上每一個位置與標識符一一對應，避免奇點與不連續。
分解：原生支持高維樹數據結構，降維解決數據工作負載統一划分的問題，實現抗傾斜與分布式數據結構的彈性。
確定性：推遲實例化，避免高開銷的位置節點合併與分割等操作。
位置保持：統一網絡層與應用位置，以各自在空間分區數據結構中產生本地處理單元。
Atlas在分區之間與驗證器核心之間，分發基於位置的交易負載，有兩個階段的彈性分區。我們拓展了並行處理領域中的Gather-Apply-Scatter模型，使本地節點狀態，通過兩個階段的pull-reduce模型，先跨輔助處理器然後跨分區合併。
多層位置地址編碼
希爾伯特曲線使Atlas可以用一維的key就可以充分、確切地描述高維空間，如包含區塊時間的額外維度。每一個位置都是一個邏輯存儲緩衝器，通過分布式資料庫廣泛支持的鍵-鍵值（key-value）結構，索引所有類型的數據。Atlas使用多維樹結構。每一層的節點與希爾伯特曲線的不同分解順序相連接，類似於s2單元編碼數據結構。每一個位置，每一個單元，根據一個取值在0-6之間的64位單元id進行索引。
彈性的按照範圍分區
共識委員會以分區，去驗證交易。高維樹結構允許我們以更低的原生維度對節點上的工作負載更均勻地進行分區。鑑於節點地址在希爾伯特曲線上的分布天然是位置保持的，分表空間便是對單元id在[0.6]內至關重要的範圍劃分。通過簡單調整範圍內的劃分間隔與移動變動區域內的目標，這種架構可以支持彈性再分表。這種具有確定性的地址編碼結構允許節點的延遲創建，以最少的節點分割、合併操作來實現高效的分布式空間索引，尤其適應於數據高頻變動的場景。
在索引時間內，Atlas通過分表，分發進入的數據，以降低再平衡時的系統開銷。此外，這種節點地址編碼策略確保一個統一的空間物體劃分，高效地避免了分布式情況下的某些節點訪問熱度過高造成系統並發能力不足的問題（簡稱熱點問題）。Atlas整合了位置保持分布系統的設計，來優化網絡和應用兩個層面的位置保持，使用戶與「附近的」分表交互，以減少延遲。
本地圖塊分區
以圖塊作為本地處理單元，應對大規模的並行。微分表的想法來源於Mosaic: processing trillion edge graph on a single machine ，mosaic的創新之處在於使用了一種基於希爾伯特曲線的高效數據結構，來產生位置保持的希爾伯特有序圖塊。每一個圖塊是一個本地處理單元，具有局部優化、節省空間的特點，可應對多核處理（在Mosaic中可支持高達244核）。這種設計有一種簡單的負載均衡結構，解決單節點處理大規模數據集的內在問題，如由於分表內數據結構不平衡造成的低局部性和負載均衡問題。
三、區塊生產協議
Atlas區塊生產協議主要受到OmniLedger和RapidChain相關著作中同行審議概念的啟發，同時也結合了一些其他被證明行之有效的研究成果。
1. 安全性與一致性
隨機用戶
公共隨機性基於公共密碼抽籤協議，支持共識組織自啟動與重構（連接與重組），幫助其抵抗長期安全損害。擁有可證明的魯棒的重構能力，以避免基於分布式哈希表的布穀鳥規則（Cuckoo Rule）的連接-離開（join-leave）攻擊。
原子性跨分區
每一個交易或者是被提交，或者是最終被取消，以簡單的鎖定-解鎖模型去協調，複雜度為O(1)
魯棒轉變
假定至少2/3的用戶是誠實的，以逐漸轉變來確保BTF共識，並最小化活躍度短暫損失的可能性。當出現領導失誤、單一分區受到DoS 攻擊等異常情況導致主節點宕掉，view change協議被快速觸發，選舉新的主節點。
2. 可伸縮的共識協調
2.1 可伸縮的聯合籤名
PBFT即實用拜佔庭容錯算法，用聯合籤名輪詢，進行準備和確認。使用樹結構，將每輪次的溝通複雜度由O(n^2)降低至O(n)，籤名驗證複雜度由O(n)降低至O(1)。
2.2 檢查點修剪
使用在PBFT中穩定的檢查點技術和狀態區塊，包括多跳反向指針，指到中間區塊的頭部。
2.3 高效的信息散布
使用糾刪碼技術機制，在網絡間傳播大的信息；同時對與默克爾樹根節點一致的誠實節點，使用協議，保證一致性。
2.4 信任，也要核實
用樂觀確認在數秒內，快速驗證小价值的交易，選擇另外一些慢但是安全的驗證器在數分鐘內去核實交易。對於不誠實的驗證器將給予懲罰。
四、隱私與密鑰分配
Atlas會處理各種地圖數據、位置軌跡與用戶畫像，其中可能包括一些敏感信息，因此需要提供原生支持，以保護這些隱私數據。
1. 鏈上隱私
用戶也許想要有私人的地圖數據，並通過白名單授權訪問這些數據。我們受CALYPSO: Auditable Sharing of Private Data over Blockchain和TDH2協議啟發，開發了這樣的一套權限控制可審查的去中心化門限密碼系統。這套系統在寫入時間上的複雜度為O(1)，而在讀取時間上的複雜度為O(n)，n為受信者（Secret Control Trustees ，SCTs）的數量。
系統自舉於分布式密鑰生成（Distributed Key Generation），n個受信者共同產生一個公鑰與私鑰對，私鑰通過t-out-of-n秘密分享方案得到，即對於n個總受信者，只有t個或以上受信者一起，才能分享秘密），通過非交互的零知識證明可驗證私鑰有效性。分享成功後，這t個受信者，同時擁有訪問和審核讀取與寫入的操作記錄的權限。
2. 零知識位置證明
用戶的位置軌跡是非常私密的數據。設計Atlas是為了支持位置軌跡的零知識證明，滿足預定義功能如地理圍欄審查時保護用戶隱私。參考Pepper Project: towards practical verifiable computation與zk-SNARK（zero-knowledge succint non-interactive arguments of knowledge），我們可以實現零知識的位置證明，其中設置過程的時間複雜度為O(n)，n為「算術電路」個數，證明過程的時間複雜度為O(n log n)，n為安全性參數個數，驗證過程的時間複雜度為O(n)，n為實例數（與安全性參數個數）。
對於每一個位置證明合約，它必須用配置來引導，如地理圍欄區域。編譯器執行一個程序，然後將其轉化為一個二次算術規劃（quadratic arithmetic program ，QAP）。QAP與一個安全性參數一起，被用於產生各自的zk-SNARK 證明與驗證密鑰。用戶作為證明者，提供位置和對應的證明密鑰來產生位置證明。然後證明會被記錄在Atlas，被驗證者和相關的政策驗證密鑰一起，去核實一個指定的證明。
3. 匿名畫像
Atlas需要在面對第三方時保證用戶畫像數據的匿名性。畫像數據可能包括例如訪問的餐館、花費與聲譽（是否有引架性評論、不適合的言論等）。在實現這一點的過程中，我們部分參考AnonRep: Towards Tracking-Resistant Anonymous Reputation中的概念。創新之處在於存儲數據時，使用混合網絡（mix net）和可驗證的切換與一次性假名，而不使用長期追蹤。此外，利用可連結環籤名，可抵制複製的反饋。隨參與用戶增長，系統的複雜度為O(n)。
對於一個新用戶，其畫像資料是以混合網絡伺服器相繼加密後，產生一條記錄<user public key (private key sk), encrypted data>，然後廣播給所有的伺服器。在這個過程中，系統以可驗證的切換，可以轉換所有伺服器上的記錄為<one-time pseudonym, plain-text data>的形式，而一次性假名實際上是一個與其私鑰對應的一次性公鑰。這樣，我們就可以允許用戶與系統匿名交互，第三方可獲得畫像數據但並不知道數據對應的實際用戶。最後，如果記錄有更新，混合網絡也可以通過信息的逆向轉換獲得。
所有用戶與系統交互的反饋，例如對一條消息的評論，會通過可連結環籤名提交。任何企圖對同一條消息提交重複反饋的不誠實用戶，都會被立即檢測到。