Крипто Марк Дмитриев
22

zk — STARKs

Достижение анонимности, масштабируемости и безопасности путем эффективных вычислений многочленов.

В закладки

zk-STARKs решает проблему SNARKs, которая состоит в «доверительной установке». STARKs не требуются сложные элиптические кривые, и другие сложные вычисления, вместо этого STARKs полагается только на хеш-дерево Merkle и получаемую информацию, используя этот способ доказательства, STARKs устойчив к атаке от суперкомпьютеров.

Платой за полученные преимущества — увеличенный размер доказательства, которые составляет не 288 байт, как у SNARK, а несколько сотен килобайт.

Как выглядит доказательство нулевого знания?

Мы имеем публичную функцию f, неизвестный вход x и публичный выход y. Вы хотите доказать, что вы знаете x, то есть f(x) = y, при этом, не раскрывая информации о значении x. Кроме того, чтобы доказательство было легким, оно должно проверяться гораздо быстрее, чем вычисление f.

Рассмотрим несколько примеров:

  • F — это вычисление, которое выполняется в течении двух недель на обычном компьютере, и два часа у компании, которая содержит огромный data-center. Вы отправляете задачу данной компании, (т.е код для запуска функции f), компания запускает его и возвращает ответ с доказательством. Вы проверяете доказательство за несколько миллисекунд и убеждаетесь в правильности ответа.
  • У вас есть зашифрованная транзакция вида «X1 был первоначальным балансом, X2 старый баланс, X3 — мой новый баланс, X4 мой актуальный баланс». Вы хотите создать доказательство того, что транзакция валидна (старые и новые балансы не отрицательны). X может быть парой ключей шифрования, а f может быть функцией, которая содержит в себе публичный ключ транзакции, принимает в качестве входных данных пару ключей, дешифрует транзакцию, выполняет проверку и возвращает 1 — если все верно, 0 — если нет. Y, конечно, должен быть 1.
  • У нас есть блокчейн, например, Ethereum, и вы загружаете последний блок. Вам нужно доказательство того, что этот блок валиден, и что этот блок находится последним в сети, где каждый блок валиден. Вы просите работающий узел предоставить доказательство. X — это весь блокчейн (да, все “1000 ТБ”), f — функция, которая обрабатывает все блоки, проверяет валидность и выводит хеш последнего блока, а y — хеш блока, который вы только что загрузили.

Так что это дает?

При этих действиях предоставляется 0 информации, которая позволила бы деаномизировать информацию о блоках / транзакциях и других данных. Полная анонимность. (Пример трехцветного графа).

Главной сложностью в работе этого доказательства — хрупкость данных. Т.к мы производим очень сложное вычисление, если мы имеем очень длинное, сложное доказательство, то изменяя лишь 1 бит данных в любой части этого доказательства, мы получаем совершенно разные результаты. Следовательно, нам необходимо создать что-то вроде «случайной трассировки», чтобы убедиться в ее правильности, так как легко получить изменения разницей в 1 бит. Используя математику, мы можем добиться этих результатов.

Общая схема этого решения заключается в стирании данных на определенных участках. Т.е у нас имеется отрезок длиной в 1000 блоков, мы знаем конечный результат, который утверждает, что эта цепочка валидна. Чтобы проверить всю цепочку и убедиться в ее валидности, мы начинаем проверку случайных отрезков, чтобы восстановить исходное состояние сети. Из этого мы получаем решение, которое позволяет нам проверить истинность полученного результата, т.к мы проверяем отдельные участки, то малейшая разница в данных приведет к абсолютно разным результатам.

Другой простой пример.

У нас есть многочлен P(x), который является целым числом 1 до 1.000.000. Это простой пример задачи «проверки диапазона», такая проверка может быть использована для установления остатков на балансе, например, того, что баланс пользователя все еще является положительным, после проведения нескольких транзакций.

«Традиционным» способом доказать это — посмотреть все 1.000.000 точек и проверить их значения. Но наша задача состоит в том, чтобы произвести проверку более эффективным способом, нежели совершать проверку каждого числа, тем самым выполнив 1.000.000 действий. Если мы будем использовать проверку точек путем случайной выборки, то всегда будет вероятность, что проверяющий (Prover), придумал такое значение P, которое удовлетворяет в 999.999 случаях, но не удовлетворяет в последнем. Что мы можем сделать?

Мы преобразовываем задачу в математические примеры, которые будут правильны решены только при условии, если будут использованы правильные значения, которые приведут нас к правильному решению.

Каким образом будет решен пример и доказано утверждение? Алгоритм проверки утверждения будет происходить в 3-этапа между проверяющим и верифицирующим (prover & verifier):

1. Проверяющий отправляет некоторую информацию;

2. Верифицирующий отправляет некоторые запросы;

3. Проверяющий отправляет еще некоторую информацию.

Во-первых, Проверяющий создает коммит (т.е создает хеш-дерево Merkle и отправляет верифицирующему корневой хеш). Этот хеш хранит в себе все 1.000.000 точек. После получения корневого хеша, проверяющий должен предоставить также все дочерние хеши, которые входят в состав корневого хеша. После получения этих данных, т.е коммита, проверка валидности является достаточно простой. Верифицирующий выбирает случайные значения (например, 16 чисел в диапазоне от 1 до 1 миллиарда) и просит, чтобы проверяющий предоставил соответствующие числа и их значения, тогда верифицирующий проверяет условия:

Дерево Меркл

1. Ветви соответствуют корню Меркл, который был предоставлен проверяющим;

2. Верифицирующий проверяет, что все точки, во всех случаях совпадают с предоставленными значениями во всех 16 случаях.

Поэтому, если вы предоставляете правильное значение P(x) для вычислений D(x), вы сможете пройти 16/16 проверок и получить верное доказательство. Но как насчет безопасности, если данные будут некорректными? Например, мы получаем некорректное P(x), какова минимальная вероятность того, что злоумышленник, который использует неправильные данные, будет найден? Поскольку наше доказательство, это следствие вычисления многочленов путем проверки заложенных условий, мы знаем, что к правильному решению нас может привести только одно значение — истинное, все другие значения приведут к абсолютно другим результатам. Следовательно, вероятность того, что некорректное значение P(x) будет определено как неверное, составляет 99%. Т.е это настолько же трудно, как вычислить коллизию хеш-функции.

Мы используем многочлены для повышения нахождения ошибки в любом некорректном решении, так что любое неправильное вычисление, для которого необходимо миллион проверок, превращается в уравнение, которое может быть определено как неверное в 99% случаях при первой же проверке.

Для улучшения алгоритма по вычислению многочлена, мы делаем его «non-interactive», которое может быть получено любым узлом, а затем проверено, используя слепую подпись Шнорры. Проверяющий сначала строит хеш-дерево Меркл и вычисляет корневой хеш. Сам корень используется в качестве источника энтропии, который определяет, какие ветви дерева должен предоставить проверяющий. Затем проверяющий передает корень Меркла и его ветви вместе в качестве доказательства. Вычисления происходят на стороне проверяющего; Далее происходит процесс вычисления корня Меркл, путем использования случайный ветвей, которые проверяются и эффективно заменяют необходимость специального верификатора.

Слепая подпись Шнорры

Единственное, что может использовать атакующий, без валидного значения P(x), так это повторять процесс проверки столько раз, пока ему не повезет в один из моментов и он не получит нужные ему ветви Меркла, которые он сможет вычислить, чтобы предоставить доказательство. Данная атака может занять миллиарды лет, чтобы атакующему повезло.

Вывод: технология STARKs позволяет нам с высокой долей вероятности узнать, когда нас пытаются обмануть за очень небольшой отрезок времени используя минимальные вычислительные ресурсы. В этой статье мы рассматриваем лишь поверхностную работу алгоритма, его заложенные принципы и применение, если вы интересуетесь более глубоким изучением STARKs, а также получение более весомых доказательств его работоспособности, советуем вам обратиться к Google. STARKs универсален, существует множество вариантов его настройки, способов вычислений и т.д.

Материал опубликован пользователем. Нажмите кнопку «Написать», чтобы поделиться мнением или рассказать о своём проекте.

Написать
{ "author_name": "Марк Дмитриев", "author_type": "self", "tags": [], "comments": 0, "likes": -1, "favorites": 0, "is_advertisement": false, "subsite_label": "crypto", "id": 50433, "is_wide": false, "is_ugc": true, "date": "Thu, 08 Nov 2018 13:29:57 +0300" }
{ "id": 50433, "author_id": 205350, "diff_limit": 1000, "urls": {"diff":"\/comments\/50433\/get","add":"\/comments\/50433\/add","edit":"\/comments\/edit","remove":"\/admin\/comments\/remove","pin":"\/admin\/comments\/pin","get4edit":"\/comments\/get4edit","complain":"\/comments\/complain","load_more":"\/comments\/loading\/50433"}, "attach_limit": 2, "max_comment_text_length": 5000, "subsite_id": 199126 }

Комментариев нет 0 комм.

Популярные

По порядку

0
{ "page_type": "article" }

Прямой эфир

[ { "id": 1, "label": "100%×150_Branding_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox_method": "createAdaptive", "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "ezfl" } } }, { "id": 2, "label": "1200х400", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "ezfn" } } }, { "id": 3, "label": "240х200 _ТГБ_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fizc" } } }, { "id": 4, "label": "240х200_mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "flbq" } } }, { "id": 5, "label": "300x500_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "ezfk" } } }, { "id": 6, "label": "1180х250_Interpool_баннер над комментариями_Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "bugf", "p2": "ffyh" } } }, { "id": 7, "label": "Article Footer 100%_desktop_mobile", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fjxb" } } }, { "id": 8, "label": "Fullscreen Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fjoh" } } }, { "id": 9, "label": "Fullscreen Mobile", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fjog" } } }, { "id": 10, "disable": true, "label": "Native Partner Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyb" } } }, { "id": 11, "disable": true, "label": "Native Partner Mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyc" } } }, { "id": 12, "label": "Кнопка в шапке", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "p1": "bscsh", "p2": "fdhx" } } }, { "id": 13, "label": "DM InPage Video PartnerCode", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox_method": "createAdaptive", "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "bugf", "p2": "flvn" } } }, { "id": 14, "label": "Yandex context video banner", "provider": "yandex", "yandex": { "block_id": "VI-223676-0", "render_to": "inpage_VI-223676-0-1104503429", "adfox_url": "//ads.adfox.ru/228129/getCode?pp=h&ps=bugf&p2=fpjw&puid1=&puid2=&puid3=&puid4=&puid8=&puid9=&puid10=&puid21=&puid22=&puid31=&puid32=&puid33=&fmt=1&dl={REFERER}&pr=" } }, { "id": 15, "label": "Плашка на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byudx", "p2": "ftjf" } } }, { "id": 16, "label": "Кнопка в шапке мобайл", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byzqf", "p2": "ftwx" } } }, { "id": 17, "label": "Stratum Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fzvb" } } }, { "id": 18, "label": "Stratum Mobile", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fzvc" } } }, { "id": 19, "label": "Тизер на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "p1": "cbltd", "p2": "gazs" } } } ]
Команда калифорнийского проекта
оказалась нейронной сетью
Подписаться на push-уведомления
{ "page_type": "default" }