博客 / STORAGE

存储算法:4+2 纠删码与一条闭合的哈希链 How Falari stores data: 4+2 erasure coding and a closed hash chain

一个文件不会完整地躺在一台矿机上。它被切成段、编成 6 个分片、承诺到 Merkle 根,只有凑齐至少 4 份可验证的回执才会结算。本文按数据实际流动的顺序,拆开这条链路。 A file never sits whole on one miner. It is segmented, encoded into six shards, committed to Merkle roots, and settled only after at least four verifiable receipts per segment. This essay follows the data in the order it actually moves.

Erasure4 + 2
Proof leaf4 KiB
Receipts / segment≥ 4
Max intent64 GiB
On this page

存储链上只保存承诺,不保存字节。链负责记住「这个文件应该是什么样」,矿工负责证明「我这里的分片确实还是那个样」。两者之间由一条从 4 KiB 叶子一直连到 segment root 的哈希路径闭合。

01一次上传的完整链路

客户端先把文件按固定大小切段,默认每段 4 MiB。每一段独立做 4+2 纠删码,得到 6 个分片;对每个分片计算承诺,再把 6 个承诺合成该段的根。所有段的根、文件大小、段大小和存储策略一起写进 MsgCreateIntent,这是链上第一次知道这个文件。

创建成功后,链为每个分片生成确定性的矿工分配。客户端把 6 个分片分别上传给对应的矿工;矿工校验分片哈希后签名一条回执。客户端收集回执并提交 MsgBatchCommit。最后,当每个段都拿到至少 4 份来自不同分片的有效回执时,MsgFinalizeDeal 才会通过。

这条顺序不是流程偏好,而是结算的前提。没有 intent,就没有可验证的承诺;没有回执,就没有矿工对字节的签名;没有达到 4 份覆盖,一份文件就可能只有一份拷贝,纠删码也就失去了意义。

024+2:固定的编码,不是可调参数

每个段被编码为 4 个数据分片和 2 个校验分片。任意 4 个分片都能重建原段;6 个全在时,多出的 2 个用于校验和修复。相对的存储开销是 1.5 倍,而不是三副本的 3 倍。按默认 4 MiB 段计算,单个分片约 1 MiB。

这个布局是协议常量。链上参数校验会拒绝任何不是 4+2 的组合;治理也不能把它改成 3+1 或 6+3。原因很实际:客户端、矿工、修复任务和证明验证都按同一个形状实现,一旦允许每个 intent 自带布局,验证路径就会出现分叉,而分叉的角落最容易藏漏洞。

上限同样写死在模块里:单个 intent 最大 64 GiB,最多 16,384 段。按默认 4 MiB 段计算,这正好覆盖 64 GiB;如果客户端把段设得更小,段数会先撞上 16,384 的上限。

03三层哈希,各回答一个问题

这套结构里有三个不同层级的承诺,名字相近但作用不同:

  • 4 KiB 叶子。分片内部按 4 KiB 切片,每片做一次 SHA-256。这是证明抽样的最小单位,也是全链唯一的分片几何。
  • shard_hash。把一个分片的所有叶子哈希做成 Merkle 根。它同时是回执里的 sector_commitment,回答「这个分片的字节有没有变」。
  • segment_root。把 6 个 shard_hash 做成 Merkle 根,写进 intent。它回答「这一段是不是由这 6 个分片组成」。

此外还有 file_root:客户端对完整存储载荷做 SHA-256,作为文件的身份和反查索引。它不参与段内证明,但把「用户以为上传的那个文件」和「链上记录的那个 intent」绑定在一起。私有文件先加密再编码,因此这里的哈希针对的是密文。

commitments
leaf[i]       = SHA-256(shard[i*4KiB : (i+1)*4KiB])
shard_hash    = MerkleRoot(leaf[0..n])
segment_root  = MerkleRoot([shard_hash_0, …, shard_hash_5])
file_root     = SHA-256(stored_payload)

Merkle 树在奇数节点处复制最后一个节点,这是旧链延续下来的确定性规则,不能被某一端「优化」掉。树的深度上限是 20 层:默认 4 MiB 的段切成 6 个分片,单分片约 699 KiB,按 4 KiB 叶子算是 171 片、路径 9 层;上限设在 20 是为了给更大分片留余量,同时让恶意回执不能靠超长路径抬高批量提交的成本。

图 1 从文件到 6 个分片,再到三层承诺:file_root 标识完整存储载荷,segment_root 固定这一段的 6 个分片,shard_hash 同时是回执里的 sector_commitment。每段至少 4 份来自不同分片的回执才能结算。

04回执:矿工对字节签名

矿工收到分片后,先按约定重算 shard_hash,再确认自己收到的字节与分配一致。回执里带着 intent、段号、分片号、分片大小、分片哈希、segment_root,以及一条从分片哈希到 segment_root 的 Merkle 路径。矿工用自己的账户密钥签名,客户端无法伪造。

链在 MsgBatchCommit 里重算两件事:这条路径能否把 shard_hash 还原到 intent 记录的 segment_root,以及回执里的 sector_commitment 是否与分片哈希一致。两项都通过,回执才被接受。

finalize 的门槛是「每段至少 4 份来自不同分片的回执」。只交 1 份、或者 6 份都来自同一个分片,都不能结算。这个规则直接对应纠删码的可恢复性:4 份不同分片足以重建,少于 4 份则不能。

05派单、去重与冗余

分片到矿工的分配由链上确定性计算,同一份 intent 在每个节点上得到同样的结果,不依赖中心的调度器。矿工的 endpoint 必须是公网可达的:EndpointUsable 会排除回环、私网和链路本地地址。一个 endpoint 写着 localhost 的矿工可以在链上显示 active,但不会收到新的分片。

计权时,链按 (miner, shard_hash) 去重。同一个物理分片被多个 intent 引用,只算一次有效存储;而容量约束和退出检查用的是全部回执字节,不去重。这两个数字故意不同:前者防止自买自卖刷权重,后者防止矿工在仍持有数据时退出。

冗余不是「多存几份完整文件」,而是「同一段的 6 个分片分散在不同矿工」。任何一台矿机离线,客户端仍可以用其余 4 个分片重建该段。链上还会为失效分片生成修复任务,默认期限 72 小时;修复完成后重新补足 6 个分片。

06证明:随机抽一片 4 KiB

存储证明不重传整个分片。每个 epoch 产生 30 条存储挑战,挑战从矿工持有的回执中选一条,再随机选一个 4 KiB 叶子。矿工返回这个叶子的原始字节、它的哈希,以及从该叶子到 shard_hash 的 Merkle 路径。链验证路径终点等于挑战里记录的承诺,再检查叶子的哈希与长度。

截止时间是 300 秒。超时未答即计一次失败,并从该矿工的可用容量中扣下对应分片;连续 720 个 epoch(5 秒出块、60 秒一个 epoch 时约 12 小时)没有成功应答,矿工被置为 degraded 并罚没质押的 1%,累计上限为全部质押,两次罚没之间至少间隔 1 小时。罚没所得进入赔付池,一次成功证明即可恢复。证明本身在 mining v2 里不再按次发币,它只作为质量乘数的一部分——这个设计把「证明」从收入来源变回了完整性检查。

检索探针是另一条路径:每个 epoch 1,800 条、每个矿工约 3 条,随机向矿工索取指定分片,只用来衡量检索可用性。检索失败不会增加存储证明的失败计数,也不触发降级或罚没;由于链上检索挖矿已经关闭,探针结果也不再影响任何链上预算,而是作为链下评估检索奖励的依据。

07这套算法保证什么,不保证什么

它保证:链上记录的分片集合确实能还原出用户提交的那份载荷;单个矿工无法在结算前伪造另一份字节;少于 4 份回执不会触发结算;同一份物理分片不会被重复计权。它不保证:矿工永久在线、数据永远可下载、或者上传后就自动多出三份拷贝。可用性依赖矿工持续证明、客户端及时发现缺片、以及修复任务被真正执行。

还有一个常被忽略的边界:file_root 是对存储载荷计算的。私有上传时,载荷是密文;同一个明文用不同密钥或不同 nonce 加密,会得到不同的 file_root。因此它适合做文件身份与反查,不适合用来判断两个用户是否持有同一份明文。

Permanent is still billed

存储策略里的 duration = 0 表示「永久」,订单不过期,但费用按 30 年窗口计算,而不是免费。永久指的是没有到期日,不是没有成本。

把这条链路压缩成一句话:文件被切成段,段被编成 6 个分片,分片被承诺进两棵 Merkle 树,回执把矿工的字节接回树上,而 finalize 只在至少 4 条路径都接上时才发生。

The chain stores commitments, not bytes. It remembers what the file should look like; miners prove that the shards they hold still look that way. A hash path from a 4 KiB leaf up to a segment root closes the loop between the two.

01The full path of one upload

The client splits the file into fixed-size segments, 4 MiB by default. Each segment is independently erasure-coded 4+2 into six shards; each shard gets a commitment, and the six commitments form that segment's root. The segment roots, file size, segment size, and storage policy go into MsgCreateIntent — the first moment the chain knows the file exists.

The chain then derives a deterministic miner assignment for every shard. The client uploads the six shards to their assigned miners; each miner verifies the shard hash and signs a receipt. The client collects receipts and submits MsgBatchCommit. Finally, MsgFinalizeDeal succeeds only when every segment has at least four valid receipts from distinct shards.

That order is not a workflow preference; it is the precondition for settlement. No intent means no verifiable commitment. No receipts means no miner signature over the bytes. Fewer than four receipts means the file may exist in only one copy, which defeats the point of erasure coding.

024+2 is a protocol constant, not a setting

Every segment becomes four data shards and two parity shards. Any four reconstruct the segment; with all six present, the extra two also support verification and repair. The storage overhead is 1.5×, not the 3× of three full replicas. With the default 4 MiB segment, one shard is roughly 1 MiB.

The layout is fixed in the protocol. Parameter validation rejects anything that is not 4+2, and governance cannot change it to 3+1 or 6+3. The reason is practical: clients, miners, repair jobs, and proof verification all implement the same shape. Allowing a per-intent layout would fork the verification path, and forks are where bugs hide.

The limits are equally fixed: one intent is at most 64 GiB and 16,384 segments. At the default 4 MiB segment, that covers 64 GiB exactly; a smaller segment size hits the segment cap first.

03Three hash levels, three different questions

The structure contains three commitments with similar-looking names and different jobs:

  • 4 KiB leaves. Each shard is sliced into 4 KiB chunks, each hashed with SHA-256. This is the sampling unit for proofs, and the only shard geometry the chain accepts.
  • shard_hash. The Merkle root of all leaves in one shard. It is also the receipt's sector_commitment and answers: did these shard bytes change?
  • segment_root. The Merkle root of the six shard_hash values, written into the intent. It answers: is this segment made of these six shards?

There is also file_root: the client hashes the complete stored payload with SHA-256 and uses it as the file's identity and reverse index. It does not participate in segment proofs, but it binds “the file the user meant to upload” to the intent on chain. Private files are encrypted before encoding, so this hash covers ciphertext.

commitments
leaf[i]       = SHA-256(shard[i*4KiB : (i+1)*4KiB])
shard_hash    = MerkleRoot(leaf[0..n])
segment_root  = MerkleRoot([shard_hash_0, …, shard_hash_5])
file_root     = SHA-256(stored_payload)

The Merkle tree duplicates the last node at an odd level. That deterministic rule is inherited from the earlier chain and must not be “optimised” on one side. Tree depth is capped at 20: a default 4 MiB segment becomes six shards of about 699 KiB each, which at 4 KiB leaves is 171 leaves and a path of 9 levels. The cap leaves headroom for larger shards while still stopping a hostile receipt from inflating batch-commit cost with an enormous path.

Fig. 1 From a file to six shards and three commitments: file_root identifies the stored payload, segment_root fixes the six shards of one segment, and shard_hash is also the receipt's sector_commitment. A segment settles only with at least four receipts from distinct shards.

04Receipts: miners sign the bytes

After receiving a shard, the miner recomputes shard_hash and confirms the bytes match the assignment. The receipt carries the intent, segment index, shard index, shard size, shard hash, segment_root, and a Merkle path from the shard hash to that root. The miner signs with its account key; a client cannot forge it.

MsgBatchCommit recomputes two things: whether the path reconstructs shard_hash to the intent's segment_root, and whether the receipt's sector_commitment equals the shard hash. Only then is the receipt accepted.

finalize requires at least four receipts per segment, from distinct shards. One receipt, or six receipts all for the same shard, cannot settle. The rule maps directly to recoverability: four distinct shards reconstruct the segment; fewer cannot.

05Assignment, deduplication, and redundancy

Shard-to-miner assignment is derived deterministically on chain. Every node computes the same result for the same intent; there is no central scheduler. A miner's endpoint must be publicly reachable: EndpointUsable rejects loopback, private, and link-local hosts. A miner advertising localhost may appear active, but it receives no new shards.

Weight accounting deduplicates by (miner, shard_hash). The same physical shard referenced by several intents counts once as effective storage. Capacity checks and exit constraints use all receipt bytes without deduplication. The two numbers differ on purpose: the first stops self-dealing from inflating weight, the second stops a miner from exiting while it still holds data.

Redundancy is not “several full copies of the file”; it is “six shards of the same segment on different miners.” If one machine goes offline, the client can rebuild the segment from the other four. The chain also creates repair tasks for failed shards, due within 72 hours by default, and refills the segment to six shards when repair completes.

06Proofs sample one 4 KiB leaf

A storage proof does not resend the whole shard. Each epoch produces 30 storage challenges. A challenge picks one of the miner's receipts and one random 4 KiB leaf. The miner returns that leaf's bytes, its hash, and the Merkle path from the leaf to shard_hash. The chain checks that the path ends at the committed root and that the leaf length and hash match.

The deadline is 300 seconds. A missed proof counts as a failure and withholds that shard's capacity; 720 consecutive epochs (about 12 hours at 60-second epochs) without a successful proof mark the miner degraded and slash 1% of stake, capped at the full stake, with at least one hour between slashes. Slashed funds go to the compensation pool, and one successful proof recovers the miner. Answering a proof no longer pays per proof: it feeds the quality multiplier, so proofs are an integrity check rather than an income stream.

Retrieval probes are a separate path: 1,800 per epoch, about 3 per miner, measuring whether a miner can still serve a specific shard. A failed probe does not increment storage-proof failures or trigger degradation. On-chain retrieval mining is retired, so probe results now feed no on-chain budget; they are the evidence for off-chain assessment of retrieval rewards.

07What this guarantees, and what it does not

It guarantees that the shard set recorded on chain can reconstruct the payload the user submitted; that one miner cannot substitute different bytes before settlement; that fewer than four receipts do not settle; and that the same physical shard is not counted twice for weight. It does not guarantee that miners stay online forever, that data remains downloadable without repair, or that an upload automatically creates three copies. Availability depends on miners continuing to prove, clients noticing missing shards, and repair tasks actually running.

One boundary is easy to miss: file_root is computed over the stored payload. For a private upload, that payload is ciphertext; the same plaintext encrypted with a different key or nonce yields a different file_root. It is a file identity and reverse index, not a way to tell whether two users hold the same plaintext.

Permanent is still billed

duration = 0 means “permanent” in the storage policy: the deal never expires, but the fee is computed over a 30-year window. Permanent means no expiry date, not no cost.

The whole chain in one sentence: the file becomes segments, segments become six shards, shards are committed into two Merkle trees, receipts tie a miner's bytes back to those trees, and finalize happens only when at least four paths per segment connect.

Sources

  • evm/x/storage/types/proof.go — leaf size, Merkle root, path and proof validation
  • evm/x/storage/types/params.go — fixed 4+2, 64 GiB, 16,384 segments
  • evm/x/storage/keeper/msg_server.go — receipt verification and batch commit
  • evm/x/storage/keeper/intent_lifecycle.go — four-receipt coverage rule
  • evm/cmd/falari-p2p/upload.go — client-side encoding and roots