Vitalik Buterin: reguła N^(1/3) a wydajność kryptografii

Badania Buterina pokazują, że opóźnienie dostępu do pamięci skaluje się jako O(N^1/3), a nie O(1). Przedstawił on model fizyczny wyjaśniający, dlaczego dostęp spowalnia wraz ze wzrostem objętości pamięci, i dodał pomiary dla pamięci podręcznej, pamięci RAM i innych poziomów pamięci. Wyniki były zgodne z wzorcem skalowania sześciennego.

W artykule omówiono wpływ tego zjawiska na inżynierię kryptograficzną. Programiści często tworzą duże, wstępnie obliczone tabele do operacji na krzywych eliptycznych. Wnioski Buterina pokazują, że gdy tabele te przekraczają rozmiar pamięci podręcznej procesora, stają się wolniejsze niż mniejsze tabele, które mieszczą się w pamięci podręcznej. Koszt pobierania danych rośnie wraz z rozmiarem pamięci, co sprawia, że większe tabele są nieefektywne.

Buterin wyjaśnił, że efekt ten wynika z fizycznego rozmieszczenia. Procesory i pamięć znajdują się w różnej odległości, a większa pojemność wymaga więcej przestrzeni fizycznej. Wraz ze wzrostem skali systemów większa odległość oznacza dłuższy czas dostępu. Zauważył, że programiści powinni brać pod uwagę odległość przestrzenną i hierarchię pamięci podczas projektowania algorytmów, a nie zakładać jednakowy czas dostępu.

Artykuł obejmuje praktyczne zastosowania w obciążeniach blockchain i systemach o zerowej jawności, które aktywnie wykorzystują obliczenia wstępne. Analiza Buterina dotyczy wyboru rozmiarów tabel i schematów rozmieszczenia danych w celu zmniejszenia pomyłek pamięci podręcznej w systemach dowodzenia i podczas weryfikacji podpisów.

Buterin regularnie publikuje notatki techniczne dotyczące kryptografii i wydajności Ethereum. Post z 5 października uzupełnia tę pracę modelem i pomiarami skupiającymi się na projektowaniu z uwzględnieniem pamięci. Badanie jest skierowane do klientów blockchain i bibliotek kryptograficznych, które opierają się na strategiach wcześniejszych obliczeń.