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

Проблема заключается в том, что примитивы ZK и ML трудно совместимы. ZK на фундаментальном уровне оперирует модульной арифметикой (т.е. дискретными значениями над конечным полем), тогда как нейронные сети и большинство моделей машинного обучения выполняют "последовательные" операции над числами с плавающей запятой, называемыми "массой". Существующие подходы пытались сократить этот разрыв путем квантизации "массы" нейронных сетей, чтобы они могли быть представлены как элементы ограниченного поля. Необходимо соблюдать осторожность, чтобы избежать "обхода", возникающего в (теперь уже модульной!) арифметике квантизации сети, и квантизации "масс" может только снизить точность модели. Но больше всего это похоже на попытку впихнуть квадратный колышек в круглое отверстие.

Мы предлагаем другой подход: давайте вернемся во времена до того, как парадигма НН устоялась, во времена, когда по земле бродило большее разнообразие нейронных сетей, и найдем модель машинного обучения, более поддающуюся ZKP. Одной из таких моделей является "Невесомая Нейронная Сеть". Утверждается, что это первая в истории нейронная сеть, которая будет коммерциализирована! Вот это да! Но, опять же, это очень старый динозавр. На протяжении десятилетий ей уделялось очень мало внимания по сравнению с привычными НН. Мы задались целью разработать систему для доказательства выводов этого невесомого чуда... и мы назвали ее... Zero Gravity (Масса исчерпана).

Невесомость означает отсутствие массы, арифметики с плавающей запятой и дорогостоящей линейной алгебры, не говоря уже о нелинейности - поэтому нет ни одной из вышеупомянутых проблем. Будут ли другие проблемы, и будут ли они хуже? Это мы и попытались выяснить на хакатоне ZKHack (Лиссабон, 2023 год).

Что такое Невесомая Нейронная Сеть?

Невесомая Нейронная Сеть (ННС) является полностью комбинаторной. Ее вход - битовая строка (например, кодирующая изображение), а выход - один из нескольких предопределенных классов, например, соответствующий десяти цифрам. Он обучается на наборе данных пар (вход, выход) путем запоминания наблюдаемых паттернов битовых строк в куче устройств, называемых RAM-ячейками, сгруппированных в "дискриминаторы", которые соответствуют каждому выходному классу. Ячейки RAM называются так потому, что на самом деле это просто большие таблицы поиска, индексированные по шаблонам битовых строк и хранящие 1, когда этот шаблон наблюдался во входной строке, помеченной классом данного дискриминатора.

Запоминание паттернов с помощью ячеек RAM

Каждая ячейка RAM подключена только к небольшому количеству входов, т.е. битов входной битовой строки. Это необходимо, поскольку размер ее таблицы поиска "случайного доступа" будет расти экспоненциально с увеличением числа входов (решается с помощью Bloom фильтров, см. ниже). Соединенный маршрут от битов входной битовой строки к ячейкам RAM обычно рандомизируется с помощью фиксированной перестановки...

Важно отметить, что существует только один слой ячеек RAM. Следовательно, ННС может преуспеть в изучении комбинаторных, поверхностных паттернов во входных битах, но не может надеяться на изучение составных, семантически насыщенных характеристик, которые могут быть изучены глубокой нейронной сетью. Почему только один слой? Помните, что ННС появились в те времена, когда метод обратного распространения ошибки и глубокие сети еще не являлись фаворитами. И с тех пор над ними было проделано сравнительно мало работы. Чтобы сделать ННС более глубоким для познания, вам придется изобрести аналог метода обратного распространения ошибки (задача для другого хакатона?). Несмотря на свою простоту, ННС демонстрируют впечатляющие результаты на таких наборах данных, как MNIST(Объёмная база данных образцов рукописного написания цифр) - модель BTHOWeN, о которой пойдет речь ниже, достигает точности на тестовом наборе более 95%.

Bloom-фильтры делают ячейки RAM масштабируемыми

Ячейки RAM занимают мало места, но они очень рассеяны, поскольку большинство битовых шаблонов никогда не наблюдаются. Bloom-фильтры предлагают пространственно-эффективный метод представления данных ячейки RAM, что позволяет ячейкам RAM получать гораздо больше входных данных. Что такое Bloom-фильтры? Bloom-фильтры - это пространственно-эффективные структуры данных для вероятностной проверки принадлежности множества. Ложноположительные результаты возможны, ложноотрицательные - нет, то есть Bloom-фильтры будут (эффективно) отвечать "x точно не входит в набор" или "x входит в набор с высокой вероятностью".

Bloom-фильтры состоят из битового массива фиксированной длины и ряда функций, которые отображают потенциальные элементы множества на позиции в массиве. Эти "хэш-функции" выбираются таким образом, чтобы попасть в каждый индекс битового массива с равномерной вероятностью - хотя они не всегда обладают криптографическими свойствами.

Что делает Zero Gravity (Масса исчерпана)?

Zero Gravity - это система для доказательства выполнения вывода (т.е. классификации) для предварительно обученной публичной ННС и частного входного сигнала. В Zero Gravity проверяющий утверждает, что ему известна входная битовая строка x такой, что публичная модель классифицирует его как класс y . Ввод x может рассматриваться как частный вход, и в этом случае система обладает нулевым знанием: хотя вывод и раскрывает что-то о x верификатору (а именно, его соответствующий выходной класс y ), эта информация уже содержится в доказываемом утверждении.

Zero Gravity основывается на недавней модели BTHOWeN от Zachary Susskind (2022), в которой ещё другие авторы улучшили более ранние модели ННС рядом интересных способов. Что особенно важно для данного проекта хакатона, они предоставляют реализацию с предварительно обученными моделями и воспроизводимыми контрольными показателями.

Интересная проблема доказательства того, что ННС была правильно обучена или обновлена, оставлена для другого хакатона!

Преодоление проблемы: выбор хэш-функции

Хеш-функции в ННС потребляют короткую подстроку перестановочной входной битовой строки, выдавая индекс в Bloom-фильтре. Авторы BTHOWeN выбрали хэш-функцию, соответствующую их целевой области: граничные устройства и, в частности, FPAG. Наша область применения совершенно иная и накладывает другие ограничения. Мы хотим, чтобы хэш-функция подходила для системы доказательства нулевых знаний. Какую хэш-функцию мы должны использовать?

Криптографическая хэш-функция не является подходящим выбором, поскольку их дорого реализовать в системе доказательства ZK, а поскольку хэш-функции потребляют только короткую битовую строку (например, длиной 49 для MNIST), они в любом случае инвертируются перебором. Хеш-функции, включающие разложение по битам, также слишком дороги. Нам нужна хэш-функция H определенная с помощью арифметических операций.

Линейные функции - не лучший выбор.

Как насчет хэш-функции H, определенной z ↦ az+ b (mod 2^L), где a,b - целые числа, а (2^L)*L - длина Bloom-фильтра? Выбор a в качестве небольшого нечетного простого числа гарантирует, что H равномерно отображается на диапазон 0,...,2^L - 1, предполагая, что его входы выбираются с равномерной вероятностью в этой области. Теоретически это минимизирует вероятность коллизий хэша. Однако битовые строки, кодирующие реальные наборы данных (например, MNIST), распределены неравномерно. Первые эксперименты подтвердили, что столкновения хэшей действительно происходят чаще, чем хотелось бы. Это привело нас к выбору хэш-функции, определенной ниже.

Малые мощности как перестановки

Проблема с линейной H (как описано выше) заключается в том, что она не может в достаточной степени "скремблировать" структуру реальных наборов данных. Вместо этого мы рассматриваем функции вида H : z ↦ ((z^3) mod p) mod 2^L, где p>2^L - простое число, выбранное таким образом, что 3 не является делителем p - 1. Если p выбрано таким образом, то z ↦ z^3 является перестановкой Z(p). Это означает, что она равномерно отображается на индексе Bloom-фильтра (как и в линейном случае). Однако, в отличие от этого случая, коллизии хэша не происходят с чрезмерной частотой, и при таком выборе хэш-функции мы можем сравниться с производительностью оригинальной модели BTHOWeN!

Подходящие простые числа p легко найти. Например, если L = 20 (так что 2^L = 1048576), то p = 2097143=2^21 - 9 удовлетворяет этим требованиям.

Мы назвали нашу новую не криптографическую хэш-функцию "MishMash" в честь ее первооткрывателя, члена команды HaMish.

Реализация

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

Участники команды хакатона

Ссылки

• Наша реализация.

• Статья BTHOWeN Susskind et al (2022) и их реализация.

• Реализация оригинальной модели WiSARD.

• ZK Hack.

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

Проблема заключается в том, что примитивы ZK и ML трудно совместимы. ZK на фундаментальном уровне оперирует модульной арифметикой (т.е. дискретными значениями над конечным полем), тогда как нейронные сети и большинство моделей машинного обучения выполняют "последовательные" операции над числами с плавающей запятой, называемыми "массой". Существующие подходы пытались сократить этот разрыв путем квантизации "массы" нейронных сетей, чтобы они могли быть представлены как элементы ограниченного поля. Необходимо соблюдать осторожность, чтобы избежать "обхода", возникающего в (теперь уже модульной!) арифметике квантизации сети, и квантизации "масс" может только снизить точность модели. Но больше всего это похоже на попытку впихнуть квадратный колышек в круглое отверстие.

Мы предлагаем другой подход: давайте вернемся во времена до того, как парадигма НН устоялась, во времена, когда по земле бродило большее разнообразие нейронных сетей, и найдем модель машинного обучения, более поддающуюся ZKP. Одной из таких моделей является "Невесомая Нейронная Сеть". Утверждается, что это первая в истории нейронная сеть, которая будет коммерциализирована! Вот это да! Но, опять же, это очень старый динозавр. На протяжении десятилетий ей уделялось очень мало внимания по сравнению с привычными НН. Мы задались целью разработать систему для доказательства выводов этого невесомого чуда... и мы назвали ее... Zero Gravity (Масса исчерпана).

Невесомость означает отсутствие массы, арифметики с плавающей запятой и дорогостоящей линейной алгебры, не говоря уже о нелинейности - поэтому нет ни одной из вышеупомянутых проблем. Будут ли другие проблемы, и будут ли они хуже? Это мы и попытались выяснить на хакатоне ZKHack (Лиссабон, 2023 год).

Что такое Невесомая Нейронная Сеть?

Невесомая Нейронная Сеть (ННС) является полностью комбинаторной. Ее вход - битовая строка (например, кодирующая изображение), а выход - один из нескольких предопределенных классов, например, соответствующий десяти цифрам. Он обучается на наборе данных пар (вход, выход) путем запоминания наблюдаемых паттернов битовых строк в куче устройств, называемых RAM-ячейками, сгруппированных в "дискриминаторы", которые соответствуют каждому выходному классу. Ячейки RAM называются так потому, что на самом деле это просто большие таблицы поиска, индексированные по шаблонам битовых строк и хранящие 1, когда этот шаблон наблюдался во входной строке, помеченной классом данного дискриминатора.

Запоминание паттернов с помощью ячеек RAM

Каждая ячейка RAM подключена только к небольшому количеству входов, т.е. битов входной битовой строки. Это необходимо, поскольку размер ее таблицы поиска "случайного доступа" будет расти экспоненциально с увеличением числа входов (решается с помощью Bloom фильтров, см. ниже). Соединенный маршрут от битов входной битовой строки к ячейкам RAM обычно рандомизируется с помощью фиксированной перестановки...

Важно отметить, что существует только один слой ячеек RAM. Следовательно, ННС может преуспеть в изучении комбинаторных, поверхностных паттернов во входных битах, но не может надеяться на изучение составных, семантически насыщенных характеристик, которые могут быть изучены глубокой нейронной сетью. Почему только один слой? Помните, что ННС появились в те времена, когда метод обратного распространения ошибки и глубокие сети еще не являлись фаворитами. И с тех пор над ними было проделано сравнительно мало работы. Чтобы сделать ННС более глубоким для познания, вам придется изобрести аналог метода обратного распространения ошибки (задача для другого хакатона?). Несмотря на свою простоту, ННС демонстрируют впечатляющие результаты на таких наборах данных, как MNIST(Объёмная база данных образцов рукописного написания цифр) - модель BTHOWeN, о которой пойдет речь ниже, достигает точности на тестовом наборе более 95%.

Bloom-фильтры делают ячейки RAM масштабируемыми

Ячейки RAM занимают мало места, но они очень рассеяны, поскольку большинство битовых шаблонов никогда не наблюдаются. Bloom-фильтры предлагают пространственно-эффективный метод представления данных ячейки RAM, что позволяет ячейкам RAM получать гораздо больше входных данных. Что такое Bloom-фильтры? Bloom-фильтры - это пространственно-эффективные структуры данных для вероятностной проверки принадлежности множества. Ложноположительные результаты возможны, ложноотрицательные - нет, то есть Bloom-фильтры будут (эффективно) отвечать "x точно не входит в набор" или "x входит в набор с высокой вероятностью".

Bloom-фильтры состоят из битового массива фиксированной длины и ряда функций, которые отображают потенциальные элементы множества на позиции в массиве. Эти "хэш-функции" выбираются таким образом, чтобы попасть в каждый индекс битового массива с равномерной вероятностью - хотя они не всегда обладают криптографическими свойствами.

Что делает Zero Gravity (Масса исчерпана)?

Zero Gravity - это система для доказательства выполнения вывода (т.е. классификации) для предварительно обученной публичной ННС и частного входного сигнала. В Zero Gravity проверяющий утверждает, что ему известна входная битовая строка x такой, что публичная модель классифицирует его как класс y . Ввод x может рассматриваться как частный вход, и в этом случае система обладает нулевым знанием: хотя вывод и раскрывает что-то о x верификатору (а именно, его соответствующий выходной класс y ), эта информация уже содержится в доказываемом утверждении.

Zero Gravity основывается на недавней модели BTHOWeN от Zachary Susskind (2022), в которой ещё другие авторы улучшили более ранние модели ННС рядом интересных способов. Что особенно важно для данного проекта хакатона, они предоставляют реализацию с предварительно обученными моделями и воспроизводимыми контрольными показателями.

Интересная проблема доказательства того, что ННС была правильно обучена или обновлена, оставлена для другого хакатона!

Преодоление проблемы: выбор хэш-функции

Хеш-функции в ННС потребляют короткую подстроку перестановочной входной битовой строки, выдавая индекс в Bloom-фильтре. Авторы BTHOWeN выбрали хэш-функцию, соответствующую их целевой области: граничные устройства и, в частности, FPAG. Наша область применения совершенно иная и накладывает другие ограничения. Мы хотим, чтобы хэш-функция подходила для системы доказательства нулевых знаний. Какую хэш-функцию мы должны использовать?

Криптографическая хэш-функция не является подходящим выбором, поскольку их дорого реализовать в системе доказательства ZK, а поскольку хэш-функции потребляют только короткую битовую строку (например, длиной 49 для MNIST), они в любом случае инвертируются перебором. Хеш-функции, включающие разложение по битам, также слишком дороги. Нам нужна хэш-функция H определенная с помощью арифметических операций.

Линейные функции - не лучший выбор.

Как насчет хэш-функции H, определенной z ↦ az+ b (mod 2^L), где a,b - целые числа, а (2^L)*L - длина Bloom-фильтра? Выбор a в качестве небольшого нечетного простого числа гарантирует, что H равномерно отображается на диапазон 0,...,2^L - 1, предполагая, что его входы выбираются с равномерной вероятностью в этой области. Теоретически это минимизирует вероятность коллизий хэша. Однако битовые строки, кодирующие реальные наборы данных (например, MNIST), распределены неравномерно. Первые эксперименты подтвердили, что столкновения хэшей действительно происходят чаще, чем хотелось бы. Это привело нас к выбору хэш-функции, определенной ниже.

Малые мощности как перестановки

Проблема с линейной H (как описано выше) заключается в том, что она не может в достаточной степени "скремблировать" структуру реальных наборов данных. Вместо этого мы рассматриваем функции вида H : z ↦ ((z^3) mod p) mod 2^L, где p>2^L - простое число, выбранное таким образом, что 3 не является делителем p - 1. Если p выбрано таким образом, то z ↦ z^3 является перестановкой Z(p). Это означает, что она равномерно отображается на индексе Bloom-фильтра (как и в линейном случае). Однако, в отличие от этого случая, коллизии хэша не происходят с чрезмерной частотой, и при таком выборе хэш-функции мы можем сравниться с производительностью оригинальной модели BTHOWeN!

Подходящие простые числа p легко найти. Например, если L = 20 (так что 2^L = 1048576), то p = 2097143=2^21 - 9 удовлетворяет этим требованиям.

Мы назвали нашу новую не криптографическую хэш-функцию "MishMash" в честь ее первооткрывателя, члена команды HaMish.

Реализация

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

Участники команды хакатона

Ссылки

• Наша реализация.

• Статья BTHOWeN Susskind et al (2022) и их реализация.

• Реализация оригинальной модели WiSARD.

• ZK Hack.