# 資料可得性

在資料分片的環境底下，我們不能讓全節點去完整下載其他分片上所有的資料，否則就失去分片的意義了。

但我們仍然要顧慮一種情況：某個分片上的惡意節點，發佈了承諾，卻窩藏承諾背後的資料沒有發布。如果說在其他分片上的全節點，都乖乖收下了帶有這個承諾的區塊，這會是個危險的情況。相當於整個系統產出了一個區塊，但區塊上屬於該分片上的資料，除了惡意節點外沒有人知道是什麼。

要解決這個問題可以引入兩個機制：抽樣挑戰和糾刪碼。

抽樣挑戰是我們可以把該分片需要發布的資料切成幾等份，並要求全節點對其抽樣。例如切為 256 份，並對其抽取 75 份。全節點必須在抽樣的 75 份的資料都有正確回應的情況下，才能收下區塊。注意這時候惡意節點的選擇變成到底 256 份的資料中要發布幾份和窩藏幾份。抽樣挑戰的好處是全節點只要少少的抽樣，惡意節點必須發布很大比例的資料（例如 250 份），才能讓全網大部分的全節點完成挑戰並收下區塊。

但發布很大比例的資料仍然不夠，只要惡意節點能夠窩藏一份資料，這區塊就是一個資料不完整的不合格區塊。所以我們除了抽樣挑戰外還需要糾刪碼。

糾刪碼是原來資料的延伸，我們可以把原本的 256 份延伸出另外 256 份糾刪碼，總共 512 份。糾刪碼的性質是只要能在 512 份中取得任何 256 份，就能還原出原本資料的 256 份。惡意節點要通過抽樣挑戰，現在必須發布 512 份中大比例的份額，例如 500 份。但這 500 份足夠讓網路中的節點湊出剩下任何窩藏的 12 份了。

網路中的節點必須完成抽樣挑戰才能收下區塊。節點有抽不到的份額而沒辦法完成挑戰時，可以等別的節點分享從糾刪碼還原回來的份額，最終還是能完成。當整個網路都收下某個區塊時，我們可以確認原本資料的 256 份都是有發布出來的。而且這中間滿足擴容的條件，也就是全節點都只有下載少於 256 份的資料。

----

釋出：我目前的理解這個釋出的標準是資料有在其他 subnet 出現，這包含用糾刪碼還原出來的。Dankrad 的解釋是節點沒有窩藏資料。

## 數學細節

### 抽樣挑戰

假設 256 份裡面，惡意節點釋出了 X 比例的份額。節點抽樣 75 份，都沒抽到窩藏部分的機率是 $X^{75}$ 。在 X 為 50% 時，機率是 $10^{-23}$ ，在 X 為 75% 時，機率還是 $10^{-10}$ 的極小數字。但在 X 為 99% 時，機率上升到 0.47 了。

以文章的例子， 256 份裡面發布 250 份，這是 X 為 97% ，完成挑戰的機率 0.17 。換個角度看，全網大概有 17% 的節點完成挑戰而收下區塊，這樣子區塊還是會被拋棄。

但發布到 255 份時，完成挑戰的機率上升到 0.75 了。假設是有抵押的驗證節點，在 75% 有辦法收下這個區塊時，驗證者會對這個有窩藏一份的區塊形成共識，這樣的狀況是不能接受的。

在這邊機率的計算中，我們是當成投返式抽樣在計算，目的是簡化計算流程。實際的行為是不投返，假設窩藏 k 份。在 75 抽的第一抽挑戰成功，則下一次要從剩下的 255 份去抽，成功機率是 $\frac{255-k}{255}$ ，這數字會比 X 再小一點。所以 75 抽挑戰成功的機率還會比前面算的再更低。

### 糾刪碼

定義 X, Y 座標軸都是有限域。選擇的這個有限域大小必須能塞入資料的一份。例如一個有限域中的整數可以用 31 位元組來表達，則資料的一份不能多於 31 位元組。

想像原本的資料為 4 份。或視為一個 4 元素的陣列，每個元素 31 位元組。

想像一個 3 次多項式。我們關心多項式在 X 軸上 1 到 8 的 Y 值。
對於原來的 4 份資料，我們可以用拉格朗日插值法，去得到這個 3 次多項式，使得多項式在 X 軸 1 ~ 4 上面的 Y 值為原本資料陣列中的值。

這個多項式在 X 軸 5~8 上面的 Y 值就是糾刪碼。在 X 軸上 1 到 8 的 Y 值任意取得 4 個值，都可以通過同一條 3 次多項式。最後可以用多項式再去取得 X 軸 1 ~ 4 上面的 Y 值，來還原出原先的資料。