简介
storj 是在 Kademlia 上构建的。
加密与分片
文件应该在分片前在客户端被加密。
数据拥有者拥有加密的密钥。
碎片大小是一个可设置的参数。
Proofs of Retrievability
数据完整性通过proof of retrievability维持
可获取证明，确保分片被正确存储。
通过 challenge-response 交互，也称为 audit, 或 heartbeat, 来验证文件是否可获取。
data owner 随机生成 n 个 challenge salts 列表, s0, s1, ...sn−1, 并存储 salts 列表.
pi 是 pre-leaf
pi = H(si + d)
li 是 merkle 树的叶子
li = H(H(si + d))
如果叶节点的个数不是2的幂次，增加空字符串的 hash 作为新叶子，知道叶节点的个数是2的幂次。
data owner 存储 challenges(salts) 列表, merkle root, 和 merkle 树的高度，然后把 merkle 树的部分叶节点发给 farmer。
farmer 存储部分 merkle 叶节点和 shard。
data owner 会周期性地挑选出一个 challenge(salt)，并发送给 farmer。challenge 不可以被重用。
data owner 用 challenge(salt)、shard、merkle 树叶列表，生成 merkle proof 并发送给 data owner。
merkle proof 总是包含 log2(l) + 1 个 hashes，data owner 使用 merkle root 和 merkle 树高来验证 merkle proof 的有效性。
局部 audit
为了减小 IO 负担而采取的一种方案。
发出 Audits
Storj 扩展 Kademlia message，增加来一个新消息类型: AUDIT.
数据存取流程
该合同系统扩展 Kademlia message，增加来四个新消息类型: OFFER, CONSIGN, MIRROR, and RETRIEVE.
存文件
取文件
备份文件
付费
使用 Strojcoin，使用微支付管道。
在 audit 时支付费用，最小化信任需求。
小额支付，价格小于 $0.000001 per audit.
Quasar
p2p publish/subscribe system.
扩展 Kademlia, 增加 3 个新消息类型: SUBSCRIBE、UPDATE、PUBLISH。
每个节点保存 topic，以及订阅那些 topic 的 节点，这些节点距离本节点最远距离为 3.
获取其他节点的订阅列表
传播本节点的新订阅
先 SUBSCRIBE 是为了了解邻居的状态，可能是为了做一些策略。
发布
PUBLISH 消息包含一个 TTL 参数，防止无限传播。
为了防止节点再次收到同样的 PUBLISH 信息，节点收到 PUBLISH 后，会将自己的 node id 加到过滤列表再转发，转发时不会发送给过滤列表中存在的节点。
冗余方案
简单副本策略
文件shard 存多个副本，shard副本 越多，可靠性越高。
K-of-M 丢失文件还原
丢失文件还原算法讲一个文件分成 k 个 shard，并创建 m 个等价 shard，共 k + m = n 个 shard。
n 个 shard 中的任意 k 个 shard，可以重建文件或任意一个丢失的 shard。
data owner 可以容忍部分 shard 丢失。
比如 20-of-40 组合，可以容忍 5 个 shard丢失，因为再丢失 16 个 shard 的概率很低。
KFS
本地文件存储，使用 LevelDB。
LevelDB存储超过100GB，会影响性能，所以需要多个 LevelDB 实例。
基本原理
多个 LevelDB实例缓解了操作压力，提升每个实例的操作速度。
多个 LevelDB，每个 LevelDB 存的范围小，锁的范围更小，并发数更大，阻塞时间也更短。
S-Buckets 与路由
KFS 存储分片在 B 个 大小限制的 LevelDB 实例，称为 S-Buckets.
S-Buckets 存储最大的字节大小为 S。
因此 KFS 最大存储大小为 S*B bytes。
Stroj 目前使用 S = 32 GB，B = 256 个实例。总大小为 8 TB。
KFS 有一个随机的 R bits id，要求 R >= log2(B)。
即 256 个实例，至少需要 8 bit。
1、 g = log2(B)
2、 h 为 KFS id 的前 g bits
3、 i 为 shard hash 的前 g bits
4、 n = h 异或 i
5、 存储 shard 在第 n 个LevelDB 实例
如果一个 KFS 实例满了，第二个实例会被创建。
存储细节
数据被分块存储，每块 C 字节。默认 C = 128 KB。
每个块的 key 为 数据全部内容的 hash + “ ” + 数字索引
这是为了确保 kv对 较小，同时能够从 S-Bucket 中顺序读写。
数字索引字符长度为：l = log10(LevelDB存储容量/块大小)
比如 l = 6,则第 3753 个块的数字索引为 ‘003753’
NAT 穿透与反向 HTTP 打开通道
Storj 扩展 Kademlia，增加 3 个额外类型：PROBE、FIND_TUNNEL、OPEN_TUNNEL。
检查自己是否是公网地址
本节点不是公网IP，反向打开通道
Bridge
Bridge 是管理节点。负责文件存取协商、校验文件可获取、支付、文件状态。被设计为只存储云数据。
Client 负责加密、文件预处理、文件密钥管理。
Bridge 必须是可靠的，Client可以不可靠。
上传操作
- Client 收集并预处理。
- Client 通知 Bridge 等待上传数据。
- Bridge 与网络节点协商(上传)
- Bridge 返回节点和 token 列表给 Client
- Client 根据节点IP 和 token 上传数据
- Client 把 AUDIT 信息给 Bridge，委托管理
- Bridge 验证文件可获取
- Bridge 承担 AUDIT、支付、管理文件状态的责任
- Bridge 通过 API 显示文件的 metadata
下载操作
- Client 传递标记文件的标识符，并请求文件
- Bridge 校验请求，提供 farmer IP + token 的列表
- Client 根据 IP 和 token 取得文件
- 文件在客户端组装并解码
