Признание узла как доказательство работы

23

В настоящее время биткойн имеет систему проверки работоспособности (PoW) с использованием SHA256. Другие хеш-функции используют графы доказательства работы системы, частичное обращение хеш-функций.

Можно ли использовать проблему принятия решений в теории узлов, такую ​​как распознавание узлов, и превратить ее в доказательство работы? Также кто-нибудь делал это раньше? Кроме того, когда у нас будет эта функция Proof of Work, будет ли она более полезной, чем то, что в настоящее время вычисляется?

Джошуа Герман
источник
8
Вас может заинтересовать этот связанный с этим вопрос о биткойнах SE: есть ли способ настроить системы проверки работоспособности без выполнения бесполезной работы?
Артем Казнатчеев
@ArtemKaznatcheev Спасибо плохо смотрю на это.
Джошуа Герман

Ответы:

7

Если существует протокол Артура-Мерлина для узловых узлов, аналогичный протоколам Артур-Мерлина [GMW85] и [GS86] для графического неизоморфизма , то я полагаю, что такое криптовалютное доказательство работы может быть разработано, в котором каждое доказательство работа показывает, что два узла вряд ли будут эквивалентны / изотопны.

Более подробно, как хорошо известно в протоколе неизоморфизма графов [GMW85], Пегги доказатель хочет доказать Вики верификатор, что два (жестких) графа и G 1 на V вершинах не изоморфны. Вики может тайно подбросить случайную монету i { 0 , 1 } вместе с другими монетами, чтобы сгенерировать перестановку π S V , и может представить Пегги новый граф π ( G i ) . Пегги должна вывести меня . Ясно, что Пегги может сделать это только в том случае, если два графа не изоморфны.г0г1Вя{0,1}π SВπ(гя)я

Точно так же и более уместно для целей доказательства работы , как указано в [GS86], версия Артура-Мерлина того же протокола включает Артура, соглашающегося с Мерлином относительно , G 1 , как, например, в матрицах смежности. Артур случайным образом выбирает хеш-функцию H : { 0 , 1 } { 0 , 1 } k вместе с изображением y . Артур предоставляет H и Y Мерлину. Мерлин должен найти ( я , я )г0г1ЧАС:{0,1}*{0,1}КYЧАСY(я,π)такой, что .ЧАС(π(гя))знак равноY

То есть Мерлин ищет прообраз хэша , причем прообраз является перестановкой одной из двух данных матриц смежности. Пока k выбрано правильно, если два графа G 0 и G 1 не изоморфны, тогда будет больше шансов, что будет найден прообраз, потому что число матриц смежности в G 0G 1 может быть в два раза больше больше, чем если бы G 0G 1 .ЧАСКг0г1г0г1г0г1

Чтобы преобразовать вышеупомянутый протокол [GS86] в пробную версию, определите майнеров как Merlin, а другие узлы как Arthur. Согласитесь на хеш , который для всех целей может быть хешем S H A 256, используемым в биткойнах. Аналогично, согласитесь, что у всегда будет 0 , аналогично требованию Биткойн, что хеш начинается с определенного числа ведущих 0 .ЧАСSЧАСA256Y00

  • Сеть соглашается доказать, что два жестких графа и G 1 не изоморфны. Графы могут быть заданы их матрицами смежности.г0г1

  • Майнер использует ссылку на предыдущий блок вместе со своим корнем финансовых транзакций Меркле, назовите его вместе со своим собственным nonce c , чтобы сгенерировать случайное число Z = H ( c B )ВсZзнак равноЧАС(с| |В)

  • Майнер рассчитывает выбрать ( я , я )Wзнак равноZмоd2В!(я,π)

  • Майнер подтверждает, что - то есть, чтобы подтвердить, что случайно выбранный π не является доказательством того, что графы изоморфныπ(гя)г1-яπ

  • Если нет, майнер вычисляет хеш Wзнак равноЧАС(π(гя))

  • Если начинается с соответствующего числа 0 , то майнер «выигрывает», публикуя ( c , B )W0(с,В)

  • Другие узлы могут проверить, что чтобы вывести ( i , π ) , и могут проверить, что W = H ( π ( G i ) ) начинается с соответствующей трудностью 0 'sZзнак равноЧАС(с| |В)(я,π)Wзнак равноЧАС(π(гя))0

Приведенный выше протокол не идеален, некоторые изломы, я думаю, должны быть решены. Например, неясно, как генерировать два случайных графа и G 1 , например, которые удовлетворяют хорошим свойствам жесткости, и неясно, как отрегулировать сложность иначе, чем путем проверки для графов с большим или меньшим количеством вершин. Тем не менее, я думаю, что они, вероятно, преодолимы.г0г1

Но для аналогичного протокола по узловому узлу замените случайные перестановки на матрице смежности одного из двух графов и G 2 некоторыми другими случайными операциями над диаграммами узлов или диаграммами сетки ... или чем-то подобным. Я не думаю, что случайный Рейдемайстер перемещает работу, потому что пространство становится слишком громоздким слишком быстро.г1г2

[HTY05] предложил протокол Артура-Мерлина для связывания узлов, но, к сожалению, произошла ошибка, и они отозвали свое требование.

[Kup11] показал, что, предполагая обобщенную гипотезу Римана, узловатость находится в , и упоминает, что это также помещает узловатость в A M , но я буду честен, я не знаю, как перевести это в вышеупомянутую структуру; М протокол [Kup11] Я думаю , что связанно с нахождением редкого простого р по модулю которого система полиномиальных уравнений является 0 . Простое число p редко встречается в том смысле, что H ( p ) = 0 , а система полиномиальных уравнений соответствует представлению группы дополнения к узлу.NпAMAMп0пЧАС(п)знак равно0

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


Ссылки:

[GMW85] Одед Голдрайх, Сильвио Микали и Ави Вигдерсон. Доказательства, которые не дают ничего, кроме их действительности, 1985.

[GS86] Шафи Голдвассер, Майкл Сипсер. Частные монеты против публичных монет в интерактивных системах доказательств, 1986.

[HTY05] Масао Хара, Сейичи Тани и Макото Ямамото. Незаузленности в , 2005.AMсоAM

[Куп11] Грег Куперберг. Узловатость в , по модулю GRH, 2011.Nп

Метки
источник
1
Как насчет случайных марковских ходов? mathworld.wolfram.com/MarkovMoves.html
Джошуа Херман,
Также вы можете рассматривать узлы как графы, которые являются знаковыми графами с четырьмя валентностями. Так что вам просто нужно применить это ограничение к G1 и G2
Джошуа Херман,
Здесь приведена раскраска квандла для экземпляра SAT. arxiv.org/pdf/1505.06595.pdf
Джошуа Герман
да, это определяет, если у вас есть пере или под пересечением. См. En.wikipedia.org/wiki/Medial_graph
Джошуа Герман
Поможет ли это для проверки на ригидность? Похоже, вам нужно только построить граф Ламана, который прост в 2D (а узлы - это плоские графы). www3.cs.stonybrook.edu/~jgao/CSE590-fall05/notes/lecture3.pdf
Джошуа Херман
1

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

Рольфсен Узел стол

Теперь давайте рассмотрим таблицу узлов, состоящую из мозаичных узлов: мозаика узлов - это тип представления узлов, которые используют плитки вместо того, чтобы быть строками в трехмерном пространстве. Узел Мозаика Стол

Теперь давайте формально определим, что такое мозаика узлов:

Мозаичные плитки

С https://arxiv.org/pdf/1602.03733.pdf Мозаика узлов - это представление узла на сетке n × n, состоящей из 11 плиток, вот они ниже.

Это моя отправная точка в запросе таблицы мозаичных узлов с рядом ограничений. Я хочу попросить вас дать мне таблицу со следующими свойствами

  1. Он должен иметь хотя бы один элемент с номером пересечения С
  2. Он должен иметь хотя бы элемент с размерностью по MNM
  3. Он должен быть окружающим изотопом к узлу который мы отправляемК
  4. ООNК
  5. Все операции должны быть уникальными
  6. Ср
  7. Это должно быть закодировано как мозаика узла.

Итак, давайте закодируем трилистник в машиночитаемом формате. Мы берем каждую плитку и присваиваем им номер (01-11). Используя ракетку языка программирования это будет выглядеть так

(define trefoil (array #[#[00 02 01 00]
                         #[02 10 09 01]
                         #[03 09 04 06]
                         #[00 03 05 04]] : Integer))

31

(struct braidcoin ([source_knot : (Matrix Integer)]
                   [target_knot : (Matrix Integer)]
                   [crossing_number : (Refine [n : Integer] (> n 0))]
                   [dimention : (Refine [n : Integer] (> n 0))]
                   [timestamp : date])

31

Итак, теперь, когда мы установили, каким должен быть результат. Теперь, как мы решаем проблему?

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

Способ, которым мы можем улучшить скорость знания, что узел находится в таблице или нет, состоит в том, чтобы создать хеш-таблицу с индексами как полином Александра. Для каждого экземпляра для него будет вычислен полином Александера, и если они будут использовать один и тот же полином Александра, он будет добавлен в качестве элемента к этой таблице.

У меня есть часть рабочей программы по следующему адресу : https://gist.github.com/zitterbewegung/4152b322eef5ecccdcf3502e8220844b

Джошуа Герман
источник
3
Учитывая две большие случайные ссылки, они вряд ли будут эквивалентны. И они, вероятно, не будут иметь тот же самый многочлен Александера, который позволит вам доказать, что они не эквивалентны в полиномиальном времени. Таким образом, задача проста большую часть времени. Я подозреваю, что крайне маловероятно, что вы создадите действительно сложный пример, взяв случайные ссылки.
Питер Шор
@PeterShor да, я это понимаю. Я не думаю, что я сформулировал это хорошо, но я также делаю произвольное количество этих задач, когда я создаю это, чтобы увеличить твердость. Даже если это произойдет, не станет ли это сложнее?
Джошуа Герман
@PeterShor Кроме того, сертификат заключается не только в том, что оба узла не являются эквивалентными, но я хочу, чтобы набор перемещений узлов к узлу или узлу, который вы могли бы вычислить, что он не является изотопным окружением (таким как трилистник).
Джошуа Герман
1
Для "известного узла в таблице" вы планируете иметь таблицу экспоненциального размера? Потому что существует экспоненциально много узлов данного размера.
Питер Шор
Да и нет. Размер каждого экземпляра использования knothash ограничен количеством операций, а также допустимым экземпляром узла или ссылки, закодированной как мозаика узла. Я планирую использовать эти параметры, чтобы ограничить количество допустимых решений, так что сложность проблемы также является параметром.
Джошуа Герман