本地首先的SDK的crdt

ORSet

此crate的核心是一个ORSet（观察-删除集合）。ORSet包含一个存储集合和一个过期集合。当添加一个元素时，它会添加到存储集合，并在删除时移动到过期集合。

路径

存储在此ORSet中的元素称为路径。这些路径用于表示其他crdt，如EWFlag、MVReg、ORMap和ORArray。路径具有以下逻辑格式

prim := prim_bool | prim_u64 | prim_i64 | prim_str
key := prim
field := prim_str
ewflag := nonce
mvreg := nonce prim
path := doc (key | field)* (ewflag | mvreg | policy) peer sig
tombstone := path peer sig

案例研究：使用ORSet构建MVReg

MVReg（多值）是一组同时写入的值。当分配一个值时，所有先前的值都会被清除。要创建一个在与其他ORSet连接时执行MVReg分配的ORSet，我们将MVReg中当前的所有值添加到过期集合，并将新值添加到存储集合。当此增量与先前状态或其他并发更新连接时，值集将收敛。

注意：路径中的对等体标识符用于声明作者身份和验证签名。它们对于收敛不是必需的。nonce用于向路径添加一些随机性，使它们独特。

拜占庭最终一致性

在没有协调的分布式系统中，只能实现某些属性。没有协调的分布式系统可以达到的最强属性称为BEC。在存在任意数量拜占庭节点的情况下，假设正确副本形成了一个连接组件，BEC具有以下保证属性

• 自我更新：如果一个正确副本生成一个更新，它会将其应用于自己的状态。
• 最终更新：对于任何由正确副本应用更新的更新，所有正确副本最终都会应用该更新。
• 收敛：任何两个已应用相同更新集的正确副本都处于相同的状态。
• 原子性：当正确副本应用一个更新时，它会原子性地应用由此事务产生的所有更新。
• 真实性：如果一个正确副本应用了一个标记为来自副本s的更新，那么该更新是由副本s生成的。
• 因果一致性：如果一个正确副本在生成或应用更新u1之前生成更新u2，那么所有正确副本都将在u2之前应用u1。
• 不变性保持：正确副本的状态始终满足所有应用声明的不变性。

不变性汇合

如果且仅当一组事务与所有应用的不变性I一致时，这组事务可以无协调地执行。

事务T与不变性I一致，如果对于所有Ti、Tj和S，其中Ti和Tj是并发执行的，状态S满足Si = apply(Ti, S)和Sj = apply(Tj, S)，则I意味着apply(Tj, apply(Ti, S))也满足I。

访问控制

无协调访问控制基于以下原则：

• 策略编码在一种逻辑语言中，该语言提供了一种指定路径上行动者权限的方法。
• 权限从单个根节点流出来；策略语句结合时没有歧义。具有相同策略声明的两个副本将做出相同的访问控制决策，无论它们了解这些声明的顺序如何。
• 访问控制检查在实现数据复制的操作中进行。这些访问控制检查根据实施时的本地策略状态进行强制执行。
• 编码的安全策略由现有的复制框架作为数据复制。

权限根是在创建文档时生成的临时密钥对。公钥用作文档标识符。有三种类型的策略语句，每种都编码为ORSet中的路径：

• 无条件：{actor}表示{actor}可以对{path}进行{permission}
• 条件：{actor}表示如果{actor}可以对{path}进行{permission}，则{actor}可以对{path}进行{permission}
• 撤销：{actor}撤销{hash(path)}

其中，permission是read/write/control/own之一。control允许委托读取和写入权限，而own允许委托读取/写入/control/own权限，actor是公钥或匿名。匿名actor可以用于例如向每个人授予读取权限。

使用所有策略语句的集合来确定对等方是否有权执行任务。有五个推理规则可以用来确定对等方是否有权限：

• 解决条件：如果有真实语句隐含了条件，则将条件转换为无条件语句。
• 本地权限：如果无条件语句由临时的文档密钥签名，则该语句被授权。
• 所有权：如果无条件语句由对等方签名，并且存在一个授权语句隐含对等方具有所有权，则该语句被授权。
• 控制：如果无条件语句由对等方签名，并且存在一个授权语句隐含对等方具有控制权限，则如果该语句正在委派读取/写入权限，则该语句被授权。
• 撤销：如果满足以下条件之一，则对等方可以撤销一个语句：
  • 撤销对等方是根权限
  • 撤销对等方的权限高于签发对等方，但至少有控制权限
  • 撤销对等方有权访问父节点，而签发对等方无权访问
  • 撤销对等方与签发对等方相同

模式与转换

为了使应用程序能够以前后兼容的方式进化，使用了一种双向模式转换的系统，称为透镜。从有序的透镜列表中构建一个模式，用于强制执行I-一致不变性。从一个源和目标有序的透镜列表中，可以将一个模式中的有效数据转换到另一个模式。这是通过找到那些列表的共同前缀，然后按照相反的顺序应用源模式的透镜的逆，之后应用目标模式的透镜来实现的。

网络

为了确保在有拜占庭节点的情况下实现收敛，从对等节点请求周期性的退出。当请求退出时，会发送一个包含一组活动点和一个已过期点的CausalContext，其中点是一个路径的哈希。然后服务器响应一个Causal，其中包含一组不在活动点或已过期点集合中的活动路径，以及一组不在已过期点集合中的已过期路径。

为了确保正确的节点形成一个完全连接的组件，我们使用了一种点对点广播协议。这使得广播协议对Sybil攻击具有抵抗力，并防止了 eclipse 攻击。

未来改进

• 妥协恢复：从意外的或恶意的修改中恢复，以恢复到先前状态。
• 使用不受信任的服务器：目前即使路径被加密，ORSet 也能收敛。然而，为了正确运行，我们还需要证明加密更新不会违反不变性，以及作者有权限进行更改。此外，还需要同态变换，以保持零知识证明。