使用對抗性數據來建構內容定義的分塊，保證分裂機率和全域穩定性
我正在使用Prolly 樹資料結構。這種結構對序列化數據進行操作，它在字節級別將其分塊。為了遞歸地建構樹，塊雜湊列表本身被序列化和分塊，直到創建一個未分塊的根節點。
我正在建構一個分佈式應用程序，它必須在潛在的對抗數據上建構這些樹。可以操縱正常的分塊算法來產生性能不佳的過大或過小的塊。我需要一種分塊算法，它可以保證良好的分塊屬性，同時為攻擊者公開所知。
該算法必須是全域穩定的，以保持資料結構的效率，因為局部修改不應該需要在某些局部區域之外重新計算分塊。這確保了修改具有一致的
log(n)樹大小相關的時間複雜度。我對這個問題的安全解決方案感興趣，即使不是非常有效地計算。
我認為可能可行的是一些標準的滾動雜湊函式應用於原始內容的單向雜湊以確定分裂點，但我無法編寫一個沒有根本缺陷的算法。
問題的形狀
輸入是一串字節 $ {D_1,D_2,D_3,…D_n} $ . 此輸入需要分塊。
在一般情況下，我假設有一些假設的函式
chunk_at_index(Data[i-N:i+N])可以呼叫來確定是否應該在 index 處剪切流i。任何在給定流的一部分時輸出剪切位置的函式都可以被包裝以產生這個更簡單的函式。這要求分塊邊界是穩定的，並且僅由本地資訊確定。一般情況是不可能的
在一般情況下不可能保證這一點，同時還要確保塊滿足給定的（最小/最大）長度標准或保持全域穩定性。沒有這樣的功能可以保證局部編輯後塊邊界的全域穩定性。
考慮一串重複的字元“aaaaaa
$$ … $$啊啊啊” 在滾動視窗上評估的函式必須在每個字節上分塊或保持整個字元串完好無損。沒有一個局部函式可以穩定地決定在統一區域內繪製塊邊界的位置而不考慮該區域之外的數據。
任何保證塊在一定大小範圍內的算法都必須要麼不穩定，要麼使用非本地資訊。
考慮以下字元串，其中一個部分由重複的“a”字元組成。一個假設的分塊函式將其分塊。進行編輯，然後重新分塊。
“你好” “世界！aa” “aaaaa” “aaaaa” “aaaHello” “世界！
“你好世界！
啊” “aaaaa” “aaaaa” “aaaHello” “世界！“你好” “世界！aa” “aaaaa” “aaaaa” “aHello” “世界！
對第二個塊的更改會更改任意距離之外的塊。
可能會建構數據壓縮算法來預處理數據以解決此問題。它需要一些遞歸壓縮自己的輸出的能力，以防止自己的輸出具有類似的重複模式。
這說明了尋找特徵來可靠地切斷流的問題。
Prolly Trees 沒有這個問題
幸運的是，Prolly 樹用於儲存排序的數據項，通常是鍵值對。假設該值由序列化數據中的加密雜湊引用儲存，並且密鑰足夠接近，則分塊算法將具有本地獨特的特徵，用於對字元串上的給定視窗做出是/否分塊決策。如果算法不能可靠地決定在哪裡進行剪輯，那是算法的錯。
為什麼是滾動雜湊？
滾動散列獲取字元串中的一個字節視窗，並輸出一個表示對該位置的偏好的分數作為塊邊界。
這是一個非常強大的概念。分數表示算法應該在特定位置分割流的程度。它僅取決於該索引附近的數據，這就是為什麼塊邊界趨於穩定和重新同步的原因。
對於非對抗性數據，一個簡單的門檻值可以很好地決定在哪里分割，但如果對手可以操縱分數，我們需要一個更好的算法來選擇邊界。
滾動雜湊的要求
任何滾動雜湊都會有一個輸出範圍。如果攻擊者可以完全控制輸出，他們可以創建任何函式都不能用於選擇分割點的病理分數配置文件。碰撞和精確重複是非常有問題的，整數函式輸出限制也是如此。通常，攻擊者必須做一些
2^N工作來設置N函式值的位。對於通用散列或任何其他使用易處理的數學來使在滾動視窗上計算散列有效的東西，可以簡單地控制輸出。似乎有必要使用強大的雜湊算法來生成分數（本質上應用 SHA2 或類似於雜湊視窗）。這確保了攻擊者必須更加努力地獲得更好的分數並且不能作弊。所需要做的就是建構一個從長遠來看在計算上不可行的分裂函式。理想情況下，它沒有標記塊邊界的時間越長，它就會變得二次或指數地更難。
符號
輸入是一串字節 $ {D_1,D_2,D_3,…D_n} $ .
我們在這個字元串上計算一個滾動雜湊函式來計算每個剪切位置的分數。
S(i) = SHA2(Data[i-A:i+A]). 分數可以看作是一個可以切片的值數組S[i:j]。這裡的一個問題並不是太重要。同樣，我將忽略與雜湊視窗未滿的字元串開頭和結尾處的雜湊值相關的問題。雜湊視窗大小
A應該比最小塊大小稍大一些，原因稍後將變得清楚。本土化選美大賽
強制執行最小塊大小的一種穩健方法是選擇某個本地視窗內最小的值。對於流索引
i，我們檢查該索引的分數是否是最小塊大小S[i]的切片S[i-A:i+A]的最小值。A如果一個點在視窗中心時是最小值，則該點獲勝並成為塊邊界。這可以通過保持排序的值堆或升序最小值算法在滾動視窗上完成。它大約每2*A字節一次分塊。這並不強制規定最大塊長度。如果
S[i]獲勝，攻擊者可以更改索引周圍的一些字節i+2A以S[i+A]降低。他們在指數處重複這一點，i+A找到一個變化來S[i+2A]降低。當繪製出來時，這看起來像一個階梯圖案。攻擊者必須確保這些點不太好。從統計上看，每次出現更好的分數時，較低的分數將是之前分數的一半左右。這確保了普通數據沒有很長的塊。如果攻擊者是幼稚的，那麼每一步的搜尋時間大約會翻倍。攻擊者可以選擇不使用太低的值，以使未來的搜尋更容易。增加每一步的計算成本會按比例減慢難度增加的速度，使這種攻擊非常實用。
尋找一個“好地方”來剪斷一根邪惡的弦
上述算法提供了最小塊大小的硬保證。任何可以進行額外削減的更改都可能會破壞最小塊大小保證，並且通常會。大多數直接涉及分數值數學的事情都會失敗。
攻擊者還可以將邪惡攻擊部分的部分連接在一起。他們只需要找到一塊“膠水”，在過渡區域中給出滿足其攻擊要求的雜湊值。
防止這種情況的一種方法是使用雜湊樹。分數
S[i]，作為加密雜湊，是對 的承諾Data[i-A:i+A]。SHA2(S[i] | S[j])如果數據在indexi或j.假設我們遇到了階梯模式。點間隔太近而不能用作塊邊界。直接使用分數很困難，但我們可以通過將點與左鄰或右鄰進行散列來製作一組新的分數。本地競賽算法可以再次應用於這些新分數，以篩選出剩餘分數列表。重複該過程，直到點相距足夠遠以滿足最小塊大小要求。阻止算法取得進展需要攻擊者將連續層中的值安排為階梯模式，涉及的層越多，這就越難。
讓我更清楚一點
假設指數 $ {j_1,j_2,j_3,…j_n} $ 是所有分數的索引，這些分數是第一個算法通過
s[j]的視窗的最小值。S[i-A:i+A]這些是階梯輪廓中的點以及“獲勝”的其他點，現在是塊邊界。任何超過最大塊大小的塊都必須進一步處理。
J[n:m]取對應於最大大小的塊的索引，J[n]並J[m]作為該塊的邊界。查找相應的“有趣”一級分數
I_1[k]=S[J[k]]。k=n...m我們建構 $ I_2[k]=SHA2(I_1[k],I_1[max(n,k-1)]) $ 對於
k=n...m，在左鄰居中進行散列以獲得下一級的得分值。這一系列 $ (J[k],I_2[k]) $ (index,score) 點數由類似的選美算法處理，該算法找到局部最小點。除非在 I_2 點中存在類似的階梯模式，否則某些點將被淘汰或獲勝並成為塊邊界。這可以重複在每個級別的左右鄰居中交替散列的連續級別，並應用“選美”算法來減少每個級別的得分和挑選獲勝者的數量。
最終，過大的塊將被切成非過大的塊。這也適用於本地，因為我們不需要看到一個塊的末端就知道它是超大的。只要看到一長串沒有塊邊界的字元串就告訴我們需要應用另一個層。
每增加一層，攻擊者添加的難度就會成倍增加，因此分塊算法必須查看的層數是有限的。這確保了函式可以在本地進行評估，只需要比
A*(Max layers+2)以往更少的上下文字節數。我沒有做任何分析，但我猜測攻擊者永遠不會超過 40 層左右。
如果您仍然感到困惑，我可以將一些實現此功能的 python 程式碼放在一起。
這是一個原始算法，因此可能存在一些我沒有看到的漏洞。