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>的形式，而一次性假名实际上是一个与其私钥对应的一次性公钥。这样，我们就可以允许用户与系统匿名交互，第三方可获得画像数据但并不知道数据对应的实际用户。最后，如果记录有更新，混合网络也可以通过信息的逆向转换获得。

 所有用户与系统交互的反馈，例如对一条消息的评论，会通过可链接环签名提交。任何企图对同一条消息提交重复反馈的不诚实用户，都会被立即检测到。