RLN or How to Fight Spam in Anonymous Environments

Расул Ибрагимов | Software & ZK Engineer Privacy & Scaling Explorations Ethereum Foundation

RLN — решение, которое помогает бороться со спамом в анонимных окружениях.

Анонимные окружения

Анонимные окружения - это такие окружения, где каждый участник по-настоящему анонимен, то есть никто не может понять кто взаимодействует с системой. Если вы пользуетесь web2 или web3-приложениями, то знаете, что там часто бывает функция анонимного голосования. Люди не могут понять кто именно там голосует и за что, но сервер это понять может. В анонимных окружениях такое сделать невозможно. Это достигается с помощью применения Zero-Knowledge в криптографии. Это так называемые Proof of Membership, то есть доказательство принадлежности множеству. В частности, такой подход используется в TornadoCash. То есть сначала пользователь доказывает то, что он положил деньги в пул, а потом доказывает, что он часть группы, но не раскрывает кто именно он из всех.

Это достигается с помощью нескольких фаз:

• Первая фаза - это регистрация, то есть когда пользователь создаёт какой-то секрет, никому его не рассказывает и отправляет только в общий реестр публичный ключ, например, на смарт-контракт.
• Вторая фаза - он доказывает то, что знает такой секрет, что хэш от него находится в общем реестре. Эффективно это можно делать с помощью деревьев Меркла, и есть такой протокол, который разработан в Privacy & Scaling Explorations, называется Semaphore. Он создан для proof of membership.

Но в анонимных окружениях есть одна очень серьёзная проблема — это спам. В web2 и web3 решениях каждый пользватель аутентифицирован, и если он начинает спамить, то сервер может заблокировать его аккаунт. В анонимных окружениях аутентификации аккаунта нет, поэтому это сделать невозможно. Максимум, что можно сделать — удалить пользователя по его IP адресу, но при этом он сможет включить VPN, зайти через другую сеть и продолжить делать доказательства принадлежности группе, потому что из самой группы никто его не удалял.

Дерево Меркла

Дерево Меркла — это полное двоичное дерево, на нижнем уровне находятся листья, и каждая родительская вершина является хэшом от дочерних вершин.

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

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

Полиномиальная интерполяция

Полиномиальная интерполяция — это очень важный принцип, которая используется в Zero-Knowledge криптографии. Ее смысл в том, что по N+1 точке можно восстановить, найти полином N-ой степени, причём такой полином будет только один. Например, через две точки можно провести только одну прямую. То есть, например, две точки и прямая это полином первой степени.

Разделение Секрета Шамира

Разделение секрета Шамира использует полиномиальную интерполяцию и позволяет разделить секрет на N частей. При этом при предъявлении K любых частей, где K меньше либо равно N, можно восстановить секретное значение. От того, какое мы выбираем значение K, зависит степень полинома. То есть, например, если мы выбрали K равное двум, то будет использован полином первой степени. То есть при предъявлении любых двух точек, мы сможем восстановить секрет.

Предположим, наше секретное значение S равно 30. Разделить секрет можно на любое количество частей. Например, мы хотим разделить на три части, тогда полином можно будет восстановить при предъявлении двух точек. Соответственно, секретный полином первой степени общего вида f(x) равен А1 умножить на x, плюс свободный коэффициент a0, где a0 — это наш секрет, а a1 - это какое-то сгенерированное случайное число. Например, возьмем 5, то есть вот f(x) равно 5 умноженное на x, плюс 30.

Чтобы посчитать части, мы делаем вычисление в трех случайных точках. Например, в точке f(5), в точке f(8) и в точке f(16). У нас получаются три части, и аналитически мы можем восстановить полином по двум точкам.

С помощью функции Базис Лагранжа, при предъявлении двух точек, любых двух частей, мы можем восстановить полином, который был до этого (f(x) = 5x + 30), и, вычислив его в нуле, мы получим наш секрет. Этот протокол позволяет нам реализовать RLN.

Rate-Limiting Nullifier (RLN)

RLN — это Zero-Knowledge протокол, который использует в себе Semaphore и разделение секрета Шамира. Он позволяет ограничить количество взаимодействий с системой в анонимном окружении. Переиспользование системы позволяет восстановить секретный ключ пользователя и удалить его из дерева Меркла. Более того, когда пользователь регистрируется в системе, он кладёт какой-то стейк, и тот, кто владеет секретным ключом пользователя, может удалить его из системы и забрать весь стейк. То есть, если, например, какой-то человек начал спамить и переиспользовать систему, его секрет сразу будет восстановлен, и любой человек сможет его заблокировать и забрать все его деньги. Такая экономическая защита также существует.

С одним и тем же секретом a0 каждую эпоху будет меняться полином, и это не позволит получить две точки. То есть, если мы не спамим, то нас заблокировать никак не смогут.

Существуют ограничения для zk-circuit. Мы подтверждаем, что хэш данного конфиденциального информации является интегральной частью общего дерева Меркла и часть этой конфиденциальной информации, предоставленной пользователем, подлинно является частью конфиденциальной информации. Иными словами, вместе с доказательством принадлежности к данному множеству, мы отправляем сообщение и раскрываем наш полином. Однако, в этом процессе мы также подтверждаем, что часть этого полинома действительно корректна.

Для определения коэффициента a1 используется определенная соль, которая называется externalNullifier. Эта соль необходима для предотвращения возможных коллизий между разными приложениями. Предположим, у нас есть два приложения, использующих RLN, и одна общая конфиденциальная информация для нескольких приложений. Если эпохи совпадут, это может привести к получению двух разных частей одного и того же полинома. Поэтому мы вводим дополнительную соль.

Улучшения RLN

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

Одним из решений для первого вопроса является возможность увеличить степень полинома. Однако здесь возникает проблема, поскольку количество ограничений увеличивается линейно с увеличением степени полинома. Для решения этой проблемы можно внести зависимость коэффициента a1 от ещё одного дополнительного параметра - счетчика messageId. То есть это всего лишь число, которое действует подобно соли, но при этом устанавливается ограничение на его значение так, чтобы оно было больше нуля и меньше максимального значения message-лимита.

Для того чтобы разные rate-лимиты были у разных людей, мы добавляем в дерево не identityCommitment, а rateCommitment, который будет равен хэшу от identityCommitment и userMessageLimit, где userMessageLimit — это лимит сообщений для определённого пользователя.

Например, регистрация происходит через смарт-контракт. Мы отправляем на смарт контракт хэш от нашего identityCommitment и какой-то стейк. Смарт контракт соответственно проверяет, сколько стейка мы приложили, и высчитывает userMessageLimit и аутпут от хэша от этих двух значений. А в дерево Меркл добавляется rateCommitment. Таким образом, мы сохраняем в системе информацию и о нашей идентичности и о нашем MessageLimit. По итогу, мы должны немного изменить constraint. Мы уже доказываем, что дерево Меркла принадлежит не identityCommitment, а rateCommitment.

Для более глубокого изучения темы, рекомендуем просмотреть документацию RLN перейдя по QR-коду ниже.