Merkle Trees 用於 Fuchsia 生態系統中的多個位置,包括 FAR 封存格式、Blob 儲存檔案系統和套件管理員。
在 Zircon zx-verity
中,應用程式元件可提供 API,以便從本機儲存空間讀取資料。當資料經過修改或損毀時,系統會驗證資料的完整性,並且導致讀取失敗。zx-verity 是以 Merkle Tree 為基礎,且衍生自 Chrome OS 中的類似系統。
這些實作都是本文介紹的演算法。
梅克爾樹參數
- 區塊大小:8 KB,已填充 0。
- 根摘要大小:32 個位元組。
- 雜湊演算法:SHA-256。
- 區塊摘要計算:SHA-256(u64(offset | level) + u32(長度) + 資料)
定義
豚骨樹包含多層次。層級是樹狀結構的一列,從 0 開始計算。層級 0 代表包含輸入串流區塊雜湊的層級。
每個層級都包含前一個層級的雜湊。某個層級的雜湊,是從前一個層級 (或層級為 0) 的 8 KB 區塊計算,並在前面加上區塊身分。
區塊身分是指在目前層級和目前層級索引內區塊起始位元組索引的二進位「或」,後面接著區塊的長度。如為等級 0,區塊長度為 8kb,除了最後一個區塊以外,可能小於 8 KB。所有其他層級都會使用 8 KB,即使最後一個區塊有 0 填充也是如此。
特定等級的計算
- 使用索引、從 0 開始的偏移值和空白雜湊清單來初始化關卡。
- 針對輸入的每個 8 KB (或餘數),請擷取等級索引「或」目前偏移值,然後加上輸入內容的長度,來計算下一個區塊身分。
- 初始化 SHA-256 摘要,然後附加到身分和輸入內容中;如果輸入的值少於 8 KB (填充介於 0 至 8 KB),
- 將摘要的輸出內容附加至層級的雜湊清單。您可以按照輸入長度增加偏移值。
- 重複 1 至 4,直到耗用所有輸入來源。
- 如果雜湊長度為 32 個字元,則即可完成。
- 如果雜湊長度未與 8kb 對齊,0 會填滿 8 KB 的對齊方式,並計算更多層級,直到有包含單一 32 位元組摘要的根層級為止。
根摘要的計算
搭配輸入資料的運算層級 0。請使用先前層級的雜湊做為輸入資料,建構及計算後續層級,直到關卡雜湊恰好包含 32 個位元組為止。這個最後一個層級含有墨爾克樹的根摘要。
空白摘要的附註
以特殊情況來說,如果沒有輸入資料,實作可能需要獨立處理計算。空白輸入的摘要就是 120 個位元組的 SHA-256,也就是單一 0 長度區塊的區塊身分。
範例值
- 空白摘要:
15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b
- 8,192 個位元組,共
0xff
個 -「oneblock」68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737
- 65536 位元組,共
0xff
- 「小」f75f59a944d2433bc6830ec243bfefa457704d2aed12f30539cd4f18bf1d62cf
- 第 2105344 個位元組,共
0xff
個 - 「大」7d75dfb18bfd48e03b5be4e8e9aeea2f89880cb81c1551df855e0d0a0cc59a67
- 第 2109440 個位元組,共
0xff
個 -「未對齊」7577266aa98ce587922fdc668c186e27f3c742fb1b732737153b70ae46973e43
- 已填入
0xff0080
個位元組,包含重複0xff0080
-「fuchsia」2feb488cffc976061998ac90ce7292241dfa86883c0edc279433b5c4370d0f30