Может ли какая-либо вычислительная задача быть преобразована в доказательство работы?

Казалось бы, бессмысленность майнинга криптовалюты подняла вопрос о полезных альтернативах, см. Эти вопросы на Bitcoin , CST , MO . Интересно, существует ли алгоритм, который может преобразовать практически любую вычислительную задачу (решение которой может быть эффективно проверено) в другую такую ​​задачу (которая используется для проверки работы), такую, что$\mathcal C$$\Psi(\mathcal C)$

1. Функция$\Psi$ рандомизирована с использованием некоторой (публичной) случайной последовательности $r$ .
2. Решение $\Psi(\mathcal C)$ является , как правило , столь же трудно , как решение $\mathcal C$ .
3. Если решение будет найдено , то решение может быть эффективно вычислено для исходной задачи .$x$$\Psi(\mathcal C)$$\Psi^{-1}(x)$$\mathcal C$
4. Знание решения для не помогает найти решение для .$\mathcal C$$\Psi(\mathcal C)$

$\;\:\:$ 4 '(обновление). Как отметил Ной в комментарии, предыдущее условие должно быть усилено так, чтобы предварительная обработка также не давала никаких преимуществ при решении .$\mathcal C$$\Psi(\mathcal C)$

Это последнее условие необходимо для того , что никто не может быть введен в выгодное положение только потому , что они знают решение . Используя этот метод, люди могут представлять вычислительные проблемы, которые они хотят решить, и центральный орган может выбрать некоторые достойные решения (например, поиск инопланетян или взлом паролей). Обратите внимание, что это не проблема, если на решение проблемы уходит даже неделя (я думаю, что эти инопланетяне не могут так хорошо скрываться;), поскольку это может привести к большей награде за решение. В любом случае, эти темы не имеют отношения к решению моей теоретической проблемы, но, конечно, я рад обсудить их в комментариях / на форуме.$\mathcal C$

Возможное решение будет следующим: отображает в , то есть, решает и некоторые другие сложные вычислительные задачи. Одна проблема состоит в том , что зная решение C делает решающий Ф ( С ) несколько проще (насколько легче зависит от сложности H S H г ). Другая проблема заключается в том , что Ψ ( C ) стало более трудным , чем C .$\Psi$$\mathcal C$$(\mathcal C,HASH_r)$$\mathcal C$$\mathcal C$$\Psi(\mathcal C)$$HASH_r$$\Psi(\mathcal C)$$\mathcal C$

( Примечание : Андреас Бьёрклунд предложил в комментариях решение, которое, на мой взгляд, лучше, чем описанное ниже. См. Http://eprint.iacr.org/2017/203 от Ball, Rosen, Sabin и Vasudevan. Короче говоря, они дают доказательства работы, основанные на таких проблемах, как ортогональные векторы, твердость которых хорошо понятна и к которым многие проблемы (например, k-SAT) могут быть сравнительно эффективно сведены. Их экземпляр PoW столь же сложен, как и ортогональный в худшем случае Векторы, даже если входной экземпляр C прост, поэтому они позволяют избежать существенного недостатка решения, описанного ниже.$\Psi(\mathcal{C})$$\mathcal{C}$

Решение, описанное ниже, могло бы извлечь выгоду из его простоты - оно может быть описано не экспертом - но оно кажется мне гораздо менее интересным теоретически.)

Решение возможно, если сделать строгое предположение, что «самый быстрый алгоритм для фундаментально рандомизирован» (и если мы смоделируем криптографическую хеш-функцию как случайный оракул). Один из способов формализовать это - сказать, что$\mathcal{C}$

1. (в противном случае, я думаю, это не совсем правильный вызов);$\mathcal{C} \in \mathsf{TFNP} \setminus \mathsf{FP}$
2. самый быстрый рандомизированный алгоритм для выполняется в ожидаемое время T в типичном случае; и$\mathcal{C}$$T$
3. существует эффективная вычислимая функция из { 0 , 1 } k в область решений C для k ≈ log 2 T такая, что всегда существует s ∈ { 0 , 1 } k с f ( s ) решением для C ,$f$$\{0,1\}^k$$\mathcal{C}$$k \approx \log_2 T$$s \in \{0,1\}^k$$f(s)$$\mathcal{C}$

Заметим , что предположение , что означает , что полный перебор из { 0 , 1 } к , по существу , оптимальный алгоритм C . Итак, это довольно сильное предположение. С другой стороны, если C не удовлетворяет этим свойствам, то мне трудно представить, чтобы выполнялись оба ваших условия (2) и (4).$k \approx \log_2 T$$\{0,1\}^k$$\mathcal{C}$$\mathcal{C}$

Тогда для заданной хеш-функции , которую мы моделируем как случайный оракул, определим Ψ H ( C ; r ) следующим образом, где r ∈ { 0 , 1 } ℓ для некоторого л » к является случайной вход ф Н . Цель состоит в том, чтобы вывести x ∈ { 0 , 1 } ∗ так , чтобы$H : \{0,1\}^* \to \{0,1\}^k$$\Psi_H(\mathcal{C}; r)$$r \in \{0,1\}^\ell$$\ell \gg k$$\Psi_H$$x \in \{0,1\}^*$ является решением C . Другими словами, ( r , x ) должен хешировать «хорошие случайные монеты» для вышеуказанного алгоритма.$f(H(r,x))$$\mathcal{C}$$(r,x)$

Давайте посмотрим, что это удовлетворяет всем вашим условиям.

1. «Функция рандомизируется, используя некоторые (общественный) случайная последовательность г .» Проверьте!$\Psi$$r$
2. «Решение обычно так же сложно, как и решение C ». Обратите внимание , что простой алгоритм рандомизированы ф Н ( С , г ) работает в ожидаемое время не более 2 K плюс полиномиальных накладные расходы, а также предположение 2 к ≈ Т , по существу , время работы алгоритма оптимального для C .$\Psi(\mathcal{C})$$\mathcal{C}$$\Psi_H(\mathcal{C},r)$$2^k$$2^k \approx T$$\mathcal{C}$
3. «Если решение найдено для Ψ ( C ) , то решение Ψ - 1 ( x ) может быть эффективно вычислено для исходной задачи C ». Это может быть сделано путем вычисления f ( H ( r , x ) ) , который является решением C по предположению.$x$$\Psi(\mathcal{C})$$\Psi^{-1}(x)$$\mathcal{C}$$f(H(r,x))$$\mathcal{C}$
4. «Знание решения для не помогает найти решение для Ψ ( C ) ». По определению, решение Ψ Н ( С ; г ) требует нахождения х таких , что F ( Н ( г , х ) ) является решением C . Поскольку мы смоделировали H как случайного оракула, мы можем понизить ожидаемое время выполнения любого алгоритма, который решает эту проблему, на оптимальную ожидаемую сложность запроса для задачи запроса, в которой $\mathcal{C}$$\Psi(\mathcal{C})$$\Psi_H(\mathcal{C}; r)$$x$$f(H(r,x))$$\mathcal{C}$$H$$H$определяется черным ящиком, и нас просят найти решение той же проблемы. И, опять же, поскольку - случайный оракул, ожидаемая сложность запроса - это как раз обратная доля элементов x ∈ { 0 , 1 } k, которые являются решениями (с точностью до постоянного множителя). По предположению, оптимальное ожидаемое время работы любого алгоритма для C составляет T ≈ 2 k , что означает, что эта доля не может быть намного больше, чем 2 - k . Так как ℓ ≫ k и r ∈ { 0 , $H$$x \in \{0,1\}^k$$\mathcal{C}$$T \approx 2^{k}$$2^{-k}$$\ell \gg k$ случайным образом выбирается равномерно, это даже верно для предварительной обработки, которая может зависеть от H и C (но не от r ), и, в частности, это верно, даже если мызаранеезнаем решение для$r \in \{0,1\}^\ell$$H$$\mathcal{C}$$r$$\mathcal{C}$

Следующая простая техника, которую я называю техникой лотереи решений (SLT), может использоваться в сочетании с другими техниками (такими как наличие множества проблем военнопленных, техника, упомянутая в ответе Ноа Стивенса-Давидовича и т. Д.), Чтобы помочь преобразовать вычислительные задачи в жизнеспособное доказательство рабочих проблем. SLT помогает улучшить проблемы с проблемами майнинга криптовалюты, кроме условий 1-4.

Предположим, что является вычислительной задачей вида «найдите подходящий хеш k вместе со строкой x такой, что ( k , x ) ∈ D ».$\mathcal{C}$$k$$x$$(k,x)\in D$

Проблема настройки: Предположим , что D представляет собой набор, Н представляет собой криптографический хэш - функция, а С есть некоторая постоянная. Предположим, кроме того, что Data ( k , x ) является частью информации, которую легко получить после того, как определено, что ( k , x ) ∈ D, но которую нельзя получить иначе.$\Psi(\mathcal{C})$$D$$H$$C$$\textrm{Data}(k,x)$$(k,x)\in D$

Задача Цель: найти пару ( k , x ) , для которой k является подходящим хешем и где ( k , x ) ∈ D и где H ( k | | x | | Data ( k , x ) ) < C .$\Psi(\mathcal{C})$$(k,x)$$k$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$

Теперь рассмотрим, как задача удовлетворяет требованиям 1-4.$\Psi(\mathcal{C})$

1. Мы должны предположить, что уже рандомизирован для SLT, чтобы удовлетворить это свойство.$\mathcal{C}$

2-3. , как правило, станет сложнее, чем C, и это хорошо. Сложность задачи «Доказательство работы» должна быть точно настраиваемой, но исходная задача C может иметь или не иметь точно настраиваемый уровень сложности (помните, что сложность майнинга Биткойна корректируется каждые две недели). Сложность задачи Ψ ( C ) равна сложности нахождения некоторого подходящего ( k , x ) ∈ D, умноженного на 2 $\Psi(\mathcal{C})$$\mathcal{C}$$\mathcal{C}$$\Psi(\mathcal{C})$$(k,x)\in D$ . Следовательно, поскольку постояннаяCявляется тонко перестраиваемой, сложностьΨ(C)также является тонко перестраиваемой.$\frac{2^{n}}{C}$$C$$\Psi(\mathcal{C})$

Даже если задача сложнее, чем исходная задача C , почти вся работа по решению проблемы Ψ ( C ) будет потрачена на простое нахождение пары ( k , x ) с ( k , x ) ∈ D вместо вычисления хешей (нельзя вычислить, является ли H ( k | | x | | Data ( k , x ) ) < $\Psi(\mathcal{C})$$\mathcal{C}$$\Psi(\mathcal{C})$$(k,x)$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$или нет, пока кто-то не вычислил и не сможет вычислить Данные ( k , x ), пока не проверит, что Данные ( k , x ) ∈ D ).$\textrm{Data}(k,x)$$\textrm{Data}(k,x)$$\textrm{Data}(k,x)\in D$

Конечно, тот факт, что сложнее, чем C, вызывает некоторые новые опасения. Для полезной задачи наиболее вероятно, что в какой-то базе данных нужно будет хранить пары ( k , x ), где ( k , x ) ∈ D. Однако, чтобы получить награду за блок, майнер должен раскрыть только пару ( k , x ), где ( k , x ) ∈ D и H ( k | $\Psi(\mathcal{C})$$\mathcal{C}$$(k,x)$$(k,x)\in D$$(k,x)$$(k,x)\in D$ вместо всех пар ( k , x ) ∈ D независимо от того, H ( k | | x | | Data ( k , x ) ) < C или нет. Одним из возможных решений этой проблемы для майнеров является просто выявление всех пар ( k , x ), где ( k , x $H(k||x||\textrm{Data}(k,x))<C$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$$(k,x)$ из вежливости. Шахтеры также будут иметь возможность отклонять цепиесли шахтеры не отправили свою справедливую долю пара ( к , х ) ∈ D . Возможно, следует подсчитать количество пар ( k , x ) ∈ D для расчета того, кто имеет самую длинную действительную цепочку. Если большинство шахтеров размещать свои решения, то процесс решения Ф ( С ) будет производить так жекак многие решениякак процесс решения C .$(k,x)\in D$$(k,x)\in D$$(k,x)\in D$$\Psi(\mathcal{C})$$\mathcal{C}$

В сценарии, где майнеры размещают все пары , Ψ ( C ) удовлетворяет духу условий 2-3.$(k,x)\in D$$\Psi(\mathcal{C})$

4. может или не может удовлетворять условию 4 в зависимости от конкретной проблемы.$\Psi(\mathcal{C})$$4$

$\textbf{Other Advantages of this technique:}$

SLT предлагает другие преимущества, чем условия 1-4, которые являются желательными или необходимыми для задачи проверки работы.

1. Улучшение баланса между безопасностью и эффективностью: SLT поможет в случае, когда может быть слишком легко решить или слишком сложно проверить. В общем, Ψ ( C ) гораздо сложнее решить , чем C , но Ψ ( C ) примерно так же легко проверить , как C .$\mathcal{C}$$\Psi(\mathcal{C})$$\mathcal{C}$$\Psi(\mathcal{C})$$\mathcal{C}$

2. Устранение неисправной / небезопасной проблемы: SLT можно использовать для алгоритмического устранения проблем с плохим военнопленным в криптовалюте с резервной проблемой POW и множественными проблемами POW. Предположим , что предприятие находит очень быстрый алгоритм для решения задачи . Тогда такая проблема больше не является подходящей проблемой доказательства работы и должна быть удалена из криптовалюты. Поэтому криптовалюта должен иметь алгоритм , который удаляет C из криптовалюта всякий раз , когда кто - то разместил алгоритм , который решает проблемы C слишком быстро , но который никогда не снимает проблему C иначе. Вот схема такого алгоритма удаления проблемы используется для удаления проблемы , которую мы будем называть Problem А .$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$A$

а. Алиса платит большую плату (плата покрывает расходы, которые несут майнеры за проверку алгоритма), а затем публикует алгоритм, который мы назовем Алгоритм K, который разбивает проблему в блокчейне. Если алгоритм К опирается на большое количество предварительно вычисленных данных Р С , затем Алиса сообщений корень Меркл этого предварительно вычисленных данных Р С .$A$$PC$$PC$

б. Случайные экземпляры проблемы А создаются блокчейном. Затем Алиса сообщения участки предварительно вычисленные данные , которые необходимы для алгоритма K работать правильно наряду с их ветви Merkle, чтобы доказать , что данные на самом деле пришли из . Если алгоритм Алисы быстро получает предварительно вычисленные данные P C , проблема устраняется, и Алиса получает вознаграждение за публикацию алгоритма, который устраняет проблему из блокчейна.$PC$$PC$

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

3. Майнинг пулы более выполнимы: в криптовалютах зачастую очень трудно получить награду за блок. Поскольку награды за блок очень трудно выиграть, майнеры часто добывают то, что называется майнинг-пулами, в которых майнеры объединяют свои ресурсы для решения проблемы и в которых они делят награду за блок пропорционально количеству «промахов», которые они нашли. , Возможная проблема для является то , что это может быть трудно получить качественное представление о том , что представляет собой как «у промаха» для задачи C и алгоритм для нахождения рядом промаха может отличаться от алгоритма решения C . Так как майнеры пула будут искать промахи, они могут быть не очень эффективны в решении $\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$(и, следовательно, мало кто присоединится к майнинг-пулам). Однако для существует четкое понятие о близком промахе, а именно, о близком промахе есть пара ( k , x ), где ( k , x ) ∈ D, но где H ( k | | x | | Данные ( k , x ) ) ≥ C и алгоритм поиска ближних промахов для Ψ ( C$\Psi(\mathcal{C})$$(k,x)$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))\geq C$$\Psi(\mathcal{C})$будет таким же, как алгоритм поиска решения .$\Psi(\mathcal{C})$

4. Свобода хода выполнения: задача доказательстве работы называется свободной от прогресса, если количество времени, которое требуется объекту или группе объектов для поиска следующего блока в цепочке блоков, следует экспоненциальному распределению e - λ x, где постоянная λ прямо пропорциональна количеству вычислительной мощности , что юридическое лицо использует для решения задачи P . Свобода прогресса необходима для решения задач майнинга криптовалюты, чтобы майнеры могли получать вознаграждение за блок пропорционально их мощности майнинга для достижения децентрализации. SLT, безусловно, помогает минировать проблемы достижения прогресса.$P$$e^{-\lambda x}$$\lambda$$P$