Биткойн: доказателство за работа

Протоколът за доказване на извършената работа е метод, чрез който всеки може да докаже изчислителната работа, която е свършил. Тези протоколи често представляват пъзели, които, от една страна, са предизвикателни, тоест изискват сериозна изчислителна мощ и не предлагат възможност за намиране на бързо решение. От друга страна, свършената работа трябва да може да се верифицира лесно, много по-бързо от извършването на самата работа. Добре. Тези протоколи имат редица приложения. Биткойн например е система за електронни плащания, която използва схема за доказване на свършената работа в контекста на създаването на т.нар. низове от транзакционни блокове. Освен в Биткойн, който е от най-новите потребители на този вид схеми за доказване на свършената работа, те са били предлагани и за други приложения в миналото. Схемите за доказване на свършената работа са предлагани за неща от типа на възпиране на атаки с отказ на услуга. Тук идеята е, че този, който заявява определена услуга, трябва да реши дадена изчислителна задача (пъзел за доказване на свършената работа), преди да му бъде позволено да използва услугата. Идеята е да ограничиш заявителя чрез изчислителната работа, която той извършва. От своя страна отговарящият може лесно да провери дали заявителят е извършил изисканата работа и да отговори на заявката само ако работата е била свършена. Първоначалното приложение на този тип протоколи за извършена работа или поне първото, за което съм видял да се предлагат, е в контекста на ограничаване на спама в електронните пощи. Надявам се, че всички знаем какво означава това. Това са съобщенията в пощенската ти кутия, които не желаеш, които са пристигнали без твоето съгласие. Идеята тук е, че протоколът за извършена работа може да бъде обвързан с определено електронно писмо. Концептуално това е аналогично на слагането на пощенска марка, но вместо да платиш за нея с пари, използваш процесорни цикли. За един легитимен изпращач, който изпраща малък на брой съобщения, този протокол няма да струва скъпо. Ще го забави съвсем малко, защото ще се изпълни много малко на брой пъти. Ограничение е, но не е прекомерно. Но за човек, който изпраща голям брой спам съобщения, в порядъка на стотици хиляди или милиони съобщения, може да е прекалено скъпо да заделя толкова много процесорни цикли за всяко едно съобщение и получател. Надявам се, че това ти дава представа за начина, по който тези протоколи за извършена работа се използват. Нека навляза в същината на практическата им работа. Преди всичко, тези протоколи обикновено работят спрямо даден низ от символи на заданието. Ще го нарека символен низ на заданието и ще го обознача с буквата "с". "С" ще е символният низ на заданието. Човек, който използва този протокол и доказва извършената от него работа, ще се опита да създаде доказателство, което съответства на този символен низ. Това е нещо като решение на задача. Доказателството ще има конкретно математическо отношение спрямо символния низ за заданието. Когато говоря за него тук, в контекста на спам съобщенията, този символен низ може да представлява електронно писмо. Той ще е специфичен за съответната задача. Този, който доказва извършената работа, ще генерира реципрочен символен низ, който ще наречем "р". Можем да гледаме на него като на доказателство или отговор. Реципрочният символен низ ще бъде представен като доказателство и той трябва да бъде такъв, че да се комбинира успешно с дадения низ на заданието. Ако вземеш двата низа и приложиш криптографска хеш функция… Да кажем, че използвам криптографска хеш функция като SHA-256 или подобна на нея. Ако приложа криптографската хеш функция (или математическите трансформации, които тя представлява) върху комбинацията от символните низове на заданието и за доказателство, искам резултатът от тази хеш функция да притежава конкретно свойство. Префиксът на резултата или голям брой от водещите битове трябва да са нули. Да кажем, че първите 40, 30 или друг определен брой битове трябва да са нули. Останалите битове могат да са с обичайната си стойност. Очевидно се опитваме да създадем такъв реципрочен низ, който има връзка с низа на заданието. Тази връзка е осъществена спрямо конкретна хеш функция и по-точно чрез нейния резултат, когато тя се приложи върху комбинацията от символните низове на заданието и за доказателство. Ако имаш добра криптографска хеш функция, единственият известен начин да намериш доказателство от този тип е да опиташ много различни възможности, като на практика изреждаш последователно всички такива, докато не намериш тази, която работи. Ако трябва да намериш резултат, който съдържа, да кажем, 40 последователни нули, това ще изисква 2 на степен 40 брой стъпки или 2 на степен 40 различни резултата от хеш функцията. Ако опиташ 2 на степен 40 различни низа, един от тях вероятно ще сработи. За да придобиеш реална представа, това всъщност означава да направиш приблизително един трилион опита. Ако опиташ с един трилион различни низа и изчислиш хеш стойността за всеки един от тях, вероятно ще има един резултат, чиито първи 40 бита са нули. Понякога това ще изисква много по-малко от един трилион стъпки, а може да отнеме и малко повече. Може да извадиш късмет. Може да извадиш голям късмет. Но по принцип ще ти отнема средно 1 трилион стъпки, за да намериш низ, за който първите 40 бита от резултата са нули. Така че това не е лесно, но също така и не е напълно невъзможно. За да разбереш защо е трудно да се решават подобни проблеми по по-ефективен начин от последователното обхождане на всички варианти, според мен е полезно да си припомним, че резултатът от криптографската хеш функция до голяма степен изглежда произволен. Всъщност битовете от резултата изглеждат като последователни хвърляния на монета. Прилича на хвърляне на монета – ако се падне ези, имаш нула, а ако се падне тура, я възприемаш като единица. Така че въпросът всъщност е какви са шансовете да се падне ези 40 последователни пъти при 40 хвърляния на монетата. Очевидно, шансовете са много малки, но не е напълно невъзможно. Ако направиш тези 40 хвърляния около един трилион пъти, се очаква да има един случай, при който ще получиш 40 пъти поред ези. Интересното при тези схеми за доказване на извършената работа е, че могат да бъдат подсилвани и отслабвани. Да кажем, че искаш още по-значителна изчислителната мощ за генерирането на правилен низ за доказване. Да кажем, че искаш да увеличиш работата, която трябва да се докаже. В този случай ти можеш просто да увеличиш броя на изискваните нули в началото на числото. При всяка добавена нула удвояваш средната изчислителна мощ, която се изисква. Това е така, понеже се изисква още едно ези, което води до удвояване на броя на необходимите хвърляния като цяло. Ако трябва 41 последователни хвърляния на монета да се паднат ези, това ще изисква двойно повече усилия от постигането на 40 такива. Аналогично, при всяко премахване на една нула от очакванията (или от изискването), това ще редуцира необходимата изчислителна мощ наполовина. Например, ако се изискваше само първите 39 бита да са нули, това ще налага половината от хвърлянията, нужни за постигането на 40 нули. Хубавото е, че щом веднъж намериш решение... Да кажем, че някой е опитал един трилион пъти и е намерил низ за доказване, който работи. Много е лесно да се провери, че този низ действително е правилен. Само трябва да вземеш низовете на заданието и доказването и да изчислиш общата им хеш стойност. Ако някой предложи даден низ, да го наречем р', трябва само да вземеш низа на заданието и р', да ги подадеш като входни данни на хеш функцията и да видиш дали първите 40 бита са нули. Всичко, което трябва да направиш, е да приложиш хеш функцията веднъж върху комбинацията от с и р' и да провериш, че резултатът наистина започва с необходимия брой нули. Ако резултатът съдържа нужния брой нули, можеш да считаш доказателството за извършена работа за валидно, защото знаеш, че е отнело много време (или много опити) да се открие такъв низ р', чиято комбинация с низа с да произвежда необходимия брой нули след прилагането на тази криптографска хеш функция. Както виждаш, тези схеми са доста прости, но и доста хитри в същото време. Реално се свеждат до намирането на низ за доказване, който има много специфично математическо отношение към първоначалния низ на заданието. Надявам се, че това видео ти даде представа за начина на работа на тези протоколи за доказване на извършената работа.