В настоящее время биткойн имеет систему проверки работоспособности (PoW) с использованием SHA256. Другие хеш-функции используют графы доказательства работы системы, частичное обращение хеш-функций.
Можно ли использовать проблему принятия решений в теории узлов, такую как распознавание узлов, и превратить ее в доказательство работы? Также кто-нибудь делал это раньше? Кроме того, когда у нас будет эта функция Proof of Work, будет ли она более полезной, чем то, что в настоящее время вычисляется?
Ответы:
Если существует протокол Артура-Мерлина для узловых узлов, аналогичный протоколам Артур-Мерлина [GMW85] и [GS86] для графического неизоморфизма , то я полагаю, что такое криптовалютное доказательство работы может быть разработано, в котором каждое доказательство работа показывает, что два узла вряд ли будут эквивалентны / изотопны.
Более подробно, как хорошо известно в протоколе неизоморфизма графов [GMW85], Пегги доказатель хочет доказать Вики верификатор, что два (жестких) графа и G 1 на V вершинах не изоморфны. Вики может тайно подбросить случайную монету i ∈ { 0 , 1 } вместе с другими монетами, чтобы сгенерировать перестановку π ∈ S V , и может представить Пегги новый граф π ( G i ) . Пегги должна вывести меня . Ясно, что Пегги может сделать это только в том случае, если два графа не изоморфны.г0 г1 В i ∈ { 0 , 1 } π∈ S В π( Gя) я
Точно так же и более уместно для целей доказательства работы , как указано в [GS86], версия Артура-Мерлина того же протокола включает Артура, соглашающегося с Мерлином относительно , G 1 , как, например, в матрицах смежности. Артур случайным образом выбирает хеш-функцию H : { 0 , 1 } ∗ → { 0 , 1 } k вместе с изображением y . Артур предоставляет H и Y Мерлину. Мерлин должен найти ( я , я )г0 г1 ЧАС: { 0 , 1 }*→ { 0 , 1 }К Y ЧАС Y ( я , я) такой, что .ЧАС( π( Gя) ) = у
То есть Мерлин ищет прообраз хэша , причем прообраз является перестановкой одной из двух данных матриц смежности. Пока k выбрано правильно, если два графа G 0 и G 1 не изоморфны, тогда будет больше шансов, что будет найден прообраз, потому что число матриц смежности в G 0 ∪ G 1 может быть в два раза больше больше, чем если бы G 0 ≅ G 1 .ЧАС К г0 г1 г0∪ G1 г0≅г1
Чтобы преобразовать вышеупомянутый протокол [GS86] в пробную версию, определите майнеров как Merlin, а другие узлы как Arthur. Согласитесь на хеш , который для всех целей может быть хешем S H A 256, используемым в биткойнах. Аналогично, согласитесь, что у всегда будет 0 , аналогично требованию Биткойн, что хеш начинается с определенного числа ведущих 0 .ЧАС S H A 256 Y 0 0
Сеть соглашается доказать, что два жестких графа и G 1 не изоморфны. Графы могут быть заданы их матрицами смежности.г0 г1
Майнер использует ссылку на предыдущий блок вместе со своим корнем финансовых транзакций Меркле, назовите его вместе со своим собственным nonce c , чтобы сгенерировать случайное число Z = H ( c ‖ B )В с Z= H( c ∥ B )
Майнер рассчитывает выбрать ( я , я )W= Zм о д2 В! ( я , я)
Майнер подтверждает, что - то есть, чтобы подтвердить, что случайно выбранный π не является доказательством того, что графы изоморфныπ( Gя) ≠ G1 - я π
Если нет, майнер вычисляет хешW= H( π( Gя) )
Если начинается с соответствующего числа 0 , то майнер «выигрывает», публикуя ( c , B )W 0 ( с , B )
Другие узлы могут проверить, что чтобы вывести ( i , π ) , и могут проверить, что W = H ( π ( G i ) ) начинается с соответствующей трудностью 0 'sZ= H( c ∥ B ) ( я , я) W= H( π( Gя) ) 0
Приведенный выше протокол не идеален, некоторые изломы, я думаю, должны быть решены. Например, неясно, как генерировать два случайных графа и G 1 , например, которые удовлетворяют хорошим свойствам жесткости, и неясно, как отрегулировать сложность иначе, чем путем проверки для графов с большим или меньшим количеством вершин. Тем не менее, я думаю, что они, вероятно, преодолимы.г0 г1
Но для аналогичного протокола по узловому узлу замените случайные перестановки на матрице смежности одного из двух графов и G 2 некоторыми другими случайными операциями над диаграммами узлов или диаграммами сетки ... или чем-то подобным. Я не думаю, что случайный Рейдемайстер перемещает работу, потому что пространство становится слишком громоздким слишком быстро.г1 г2
[HTY05] предложил протокол Артура-Мерлина для связывания узлов, но, к сожалению, произошла ошибка, и они отозвали свое требование.
[Kup11] показал, что, предполагая обобщенную гипотезу Римана, узловатость находится в , и упоминает, что это также помещает узловатость в A M , но я буду честен, я не знаю, как перевести это в вышеупомянутую структуру; М протокол [Kup11] Я думаю , что связанно с нахождением редкого простого р по модулю которого система полиномиальных уравнений является 0 . Простое число p редко встречается в том смысле, что H ( p ) = 0 , а система полиномиальных уравнений соответствует представлению группы дополнения к узлу.Н П А М А М п 0 п ЧАС( р ) = 0
Следует отметить, что этот ответ можно найти на аналогичном вопросе на родственном сайте, где также рассматривается полезность таких «полезных» доказательств работы.
Ссылки:
[GMW85] Одед Голдрайх, Сильвио Микали и Ави Вигдерсон. Доказательства, которые не дают ничего, кроме их действительности, 1985.
[GS86] Шафи Голдвассер, Майкл Сипсер. Частные монеты против публичных монет в интерактивных системах доказательств, 1986.
[HTY05] Масао Хара, Сейичи Тани и Макото Ямамото. Незаузленности в , 2005.A M ∩ c o A M
[Куп11] Грег Куперберг. Узловатость в , по модулю GRH, 2011.Н П
источник
Я думаю, что способ сделать это состоит в том, чтобы создать таблицу мозаичных узлов с набором ограничений для запрета ярлыков. Таким образом, таблица узлов - это набор узлов, которые имеют данное свойство. Свойство ниже является основным узлом.
Теперь давайте рассмотрим таблицу узлов, состоящую из мозаичных узлов: мозаика узлов - это тип представления узлов, которые используют плитки вместо того, чтобы быть строками в трехмерном пространстве.
Теперь давайте формально определим, что такое мозаика узлов:
С https://arxiv.org/pdf/1602.03733.pdf Мозаика узлов - это представление узла на сетке n × n, состоящей из 11 плиток, вот они ниже.
Это моя отправная точка в запросе таблицы мозаичных узлов с рядом ограничений. Я хочу попросить вас дать мне таблицу со следующими свойствами
Итак, давайте закодируем трилистник в машиночитаемом формате. Мы берем каждую плитку и присваиваем им номер (01-11). Используя ракетку языка программирования это будет выглядеть так
Итак, теперь, когда мы установили, каким должен быть результат. Теперь, как мы решаем проблему?
Итак, мы знаем, что при окружающей изотопии вы можете перейти к другой диаграмме узлов, используя другую диаграмму узлов в конечном наборе движений Рейдмейстера. Итак, давайте создадим две случайные ссылки. Задача, которую мы определяем, получает две случайные ссылки. Я хочу, чтобы вы показали, что они либо эквивалентны, перечисляя все возможные узлы, которые могут быть выражены, либо демонстрируют, что они не эквивалентны, давая мне набор состояний или путей к известному узлу в стол.
Способ, которым мы можем улучшить скорость знания, что узел находится в таблице или нет, состоит в том, чтобы создать хеш-таблицу с индексами как полином Александра. Для каждого экземпляра для него будет вычислен полином Александера, и если они будут использовать один и тот же полином Александра, он будет добавлен в качестве элемента к этой таблице.
У меня есть часть рабочей программы по следующему адресу : https://gist.github.com/zitterbewegung/4152b322eef5ecccdcf3502e8220844b
источник