Główny problem, który rozwiązuje RedStuff
Każdy system rozproszonego przechowywania musi rozwiązać trzy wzajemnie sprzeczne cele:
Wysoka dostępność (dane zawsze można pobrać)
Niska nadmiarowość (przechowywanie nie jest nieprzyjemnie kosztowne)
Wytrzymałość na zdrajców (węzły mogą być złośliwe, nie tylko nieaktywne)
Większość systemów oferuje kompromis w jednym z nich:
IPFS → tanio, ale bez gwarancji
Filecoin → gwarancje, ale ogromne obciążenie nadmiarowości
Arweave → stały, ale nieefektywny i archiwalny
RedStuff rozwiązuje wszystkie trzy jednocześnie.
Dlaczego proste kodowanie zamiennikowe nie wystarcza
Klasyczne kodowanie zamiennikowe (Reed–Solomon)
Podziel plik na k fragmentów
Dodaj n−k fragmenty parzystości
Każde k z n może zrekonstruować plik
Problem:
Zakłada uczciwe, ale awaryjne węzły
Łamie się pod działaniem bizantyjskim
Walrus zakłada złośliwe węzły, a nie tylko awarie.
Dwuwymiarowe kodowanie erasure
Zamiast jednowymiarowego paska, RedStuff koduje dane w dwuwymiarowej macierzy.
Krok 1: Blob → Macierz
Załóżmy, że blob jest podzielony na macierz:
D11 D12 D13
D21 D22 D23
D31 D32 D33
Każdy Dij to blok danych.
Krok 2: Kodowanie wierszy i kolumn
RedStuff stosuje kodowanie erasure dwa razy:
Kodowanie wierszy
Każdy wiersz otrzymuje bloki parzystości:
Wiersz 1: D11 D12 D13 | R1
Wiersz 2: D21 D22 D23 | R2
Wiersz 3: D31 D32 D33 | R3
Kodowanie kolumn
Każda kolumna otrzymuje bloki parzystości:
Kol 1: D11 D21 D31 | C1
Kol 2: D12 D22 D32 | C2
Kol 3: D13 D23 D33 | C3
Teraz każdy blok danych jest chroniony poziomo i pionowo.
To jest dwuwymiarowa redundancja.
Dlaczego to jest odporne na bizantyjskie
Analizujmy tryby awarii.
Przypadek A: Węzły przechodzą offline
Kody wierszy odzyskują brakujące bloki
Kody kolumnowe odzyskują brakujące bloki
Przypadek B: Węzły kłamią (bizantyjskie)
Nieprawidłowe kawałki są wykrywane poprzez:
zobowiązania kryptograficzne
kontrole spójności w różnych wymiarach
Przypadek C: Opóźnienie adwersarialne
Węzły nie mogą się doczekać wyzwań
Dowody są asynchroniczne
Opóźnienia = kary
Węzeł musi nieprzerwanie przechowywać dane, a nie udawać je później.
Matematyczne gwarancje
Niech:
f = ułamek węzłów bizantyjskich
n = całkowita liczba węzłów
k = próg danych
RedStuff gwarantuje:
Dostępność danych, jeśli < 1/3 kawałków jest bizantyjskich
Szerokość pasma odzyskiwania proporcjonalna do utraconych danych
Prawdopodobieństwo rekonstrukcji → 1, gdy macierz rośnie
To jest znacznie silniejsze niż jednowymiarowe kodowanie erasure.
