Существует ли система доказательства работы, для генерации которой требуется значительно больше памяти, чем для проверки?

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

Другой способ сделать это — использовать большое случайное дерево Меркла . Допустим, кто-то создал дерево Меркла из 2^31 случайных 32-байтовых значений. Принимая во внимание, что ветки merkle также должны храниться, это (1 + 2 + 2^2 + 2^3 + ... + 2^31) * 32 bytesили (2^32-1)*32 ~= 137.4 GBданные в целом. Эти данные очень общедоступны для всех, кто действительно хотел их загрузить и проверить корень merkle. Корень меркла будет известен как корень меркла для добычи полезных ископаемых, и это хорошо известная и согласованная константа. Майнинг включает в себя выборку этого случайного дерева Меркла и хэширование, и при нахождении успешного решения предоставляется ветвь дерева Меркла, доказывающая, что данные, которые были выбраны, действительно находятся в публично согласованном дереве Меркла.

В этой схеме для майнинга требуется ~ 137,4 ГБ памяти, но только ~ 1 КБ данных для проверки решения относительно публично согласованного корня merkle для майнинга.

И цифры, очевидно, могут быть изменены, чтобы люди могли майнить, не отказываясь от 137,4 ГБ своего жесткого диска. Нужно было бы достичь баланса.

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

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

http://www.hashcash.org/papers/momentum.pdf

Соответствующее обсуждение bitcointalk алгоритма Momentum:

https://bitcointalk.org/index.php?topic=313479.0

Я думаю, это забавно, как аспект «импульса» (невозможность обновить merkle после его первого создания) рекламируется как определяющая характеристика алгоритма, хотя на самом деле это довольно существенный недостаток, задержка подтверждения всех транзакций на 1 блок. . Это также может усугубить проблему, когда майнеры не хотят добывать большие блоки, потому что их распространение занимает много времени. т.е. может быть более выгодно продолжать добычу с помощью вашего крошечного блока даже после того, как вы услышали о новом блоке в сети, потому что импульс, который у вас уже есть, облегчает его. Я думаю, что тот факт, что биткойн-алгоритм PoW не имеет импульса, на самом деле является отличной функцией, позволяющей быстро подтверждать транзакции.

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

Для создания Dagger требуется много памяти, но мало для проверки.

Мой «Cuckoo Cycle» https://github.com/tromp/cuckoo — это теоретико-графовое Proof-of-Work с привязкой к памяти, которое тривиально проверить, и AFAIK — единственный, в котором во время выполнения преобладает задержка памяти.