Перейти к содержанию
  • записей
    14
  • комментариев
    68
  • просмотра
    88 413

Официальный релиз PrimeCoin. Часть 1


Garrett

4 837 просмотров

Представляю сообществу перевод официального релиза криптовалюты PrimeCoin

Оригинал тут

 

Аннотация

В данной статье представлен новый тип системы proof-of-work для работы с криптовалютой в одноранговых сетях, основанный на поиске простых чисел. К proof-of-work относят систему, основанную на трех типах цепей простых чисел, также известных как цепи Каннингема первого и второго рода, а также двойная цепь простых чисел-близнецов. Цепь простых чисел используется для хэширования блока с целью обеспечить безопасность проекта Bitcoin от Nakamoto, в то время как непрерывная схема оценки сложности создана с целью использовать цепи как PoW инструмент в системах криптовалюты, таких как Bitcoin.

 

Введениe

С момента создания системы Bitcoin [Nakamoto 2008], тип PoW, известный как hashcash [Back 2002] являлся единственным типом proof-of-work разработки для работы с криптовалютой в одноранговых сетях.

Используемая в Bitcoin система proof-of-work принадлежит к типу hashcash SHA-256. В 2011 году, компания ArtForz написала алгоритм хэш-функции для криптовалюты Tenebrix. И хотя с тех пор активно предпринимались попытки разработать другие типы proof-of-work, включая популярные типы с распределенной вычислительной нагрузкой, и типы на основе других научных вычислений, тем не менее, такой проект является «неуловимым» для обеспечения бесперебойной работы и безопасности сетей криптовалют.

В марте 2013 года я осознал, что поиск цепей простых чисел потенциально может быть альтернативным типом системы proof-of-work. Приложив некоторые усилия, я разработал систему, основанную исключительно на работе с простыми числами, что одновременно обеспечивает и работу, и безопасность работы криптовалютных сетей, равно как и hashcash тип системы proof-of-work. Данный проект называется primecoin.

 

 

Простые числа как Одиссея

Простые числа представляют собой основную, однако наиболее глубокую структуру в арифметике, которая приводит в недоумение уже не одно поколение блестящих математиков. Их бесконечное количество было известно науке еще 2 тысячи лет назад, во времена Евклида, однако теорема простых чисел, касающаяся их распределения, была доказана лишь в 1896 году, следом за исследованием Бернхарда Римана о Дзета-функции. Множество гипотез, касающихся простых чисел, не доказаны по сей день. Поиск самого крупного простого числа был во многом основан на формуле простого числа Мерсенна, названной в честь французского монаха Марина Мерсенна (1588 – 1648), благодаря долгой истории этой формуле и ее значимости в теории чисел, а также благодаря тому факту, что коэффициент 2р-1 не может быть вычислен без деления для эффективного теста Лукаса-Лемера.

В настоящее время все 10 наиболее известных простых чисел являются числами Мерсенна. Два известных типа простых пар – это пары простых чисел-близнецов, где p и p+2 являются простыми числами, и числа Софи Жермен, где p и 2p+1 являются простыми числами.

Развивая концепцию чисел Софи Жермен, необходимо обратить внимание на цепь почти удвоенных чисел, названных в честь Аллана Каннингема (1842-1928). Цепь Каннингема первого рода является последовательностью простых чисел, в которой каждый член цепи, кроме последнего, является числом Софи Жермен, и, кроме первого, безопасным простым числом, и где цепь Каннингема второго рода, где каждое простое число на 1 больше чем удвоенное предыдущее простое число в цепи. Вариации формы известны как двойная цепь простых чисел-близнецов, где каждая пара близнецов в основном удваивает предыдущую пару близнецов.

Рассмотрим некоторые примеры для того, чтобы лучше понять данные цепи простых чисел. 5 и 7 являются простыми числами-близнецами, а 6 – их центром. Давайте умножим 6 на 2, что даст нам 12, и при этом числа 11 и 13 снова будут простыми числами-близнецами. Итак, числа 5, 7, 11 и 13 составляют цепь простых чисел-близнецов длины 4, также известную как двойную цепь близнецов одной связи (связи между числами-близнецами 5 и 7, и близнецами 11 и 13). Такая цепь также может отделяться от своих центров, образовывая одну цепь Канннингема первого рода и одну цепь Каннингема второго рода. Теперь, если мы разделим через центры 6, 12 двойной цепи близнецов 5, 7, 11, 13, то получим числа ниже центров – 5, 11, т.е. цепь Каннингема первого рода, и числа выше центров 7, 13 – т.е. цепь Каннингема второго рода.

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

Особый интерес для этих пар и образований представляет то, что их распределение, кажется, следует аналогичному, но более редкому образцу, нежели распределение простых чисел. Были попытки вывести эвристические формулы распределения, однако, их бесконечное существование так и не удалось доказать (среди них наиболее известная гипотеза о простых числах-близнецах [Голдстон, 2009]), не говоря о том, чтобы применить.

 

Эффективная проверка Proof-of-Work

Для того чтобы система могла работать как proof-of-work для криптовалюты, ее функционирование должно быть эффективно проверяемо на всех узлах сети. Это потребует, чтобы простые числа не были рекордно большими. Также, для этого необходимо исключить простые числа Мерсенна, что приведет к использованию простых цепей, как в случае с primecoin. Дело в том, что найти простые цепи становится экспоненциально сложнее по мере увеличения их длины (по крайней мере, с нашим теоретическим и алгоритмическим пониманием на сегодняшний день), когда проверка умеренно больших простых чисел является эффективной.

Таким образом, для разработки primecoin, в качестве proof-of-work принимаются три типа цепей простых чисел: цепи Каннингема первого и второго порядка и двойная цепь простых чисел-близнецов. Простые числа в цепи определяют максимальный размер протокола в целях обеспечения эффективной проверки на всех узлах.

Классический тест Ферма [Caldwell 2002] с основанием степени 2 используется совместно с тестом Эйлера-Лагранжа-Лифшица [Lifchitz 1998] для проверки вероятной простоты для цепей простых чисел. При этом, мы не требуем строгой проверки простоты во время верификации, т.к. это лишь усложнит процесс верификации. Составное число, способное пройти тест Ферма, обычно называют псевдо-простым числом.

Т.к. из работ Эрдёша и Померанса [Pomerance 1981] известно, что псевдо-простые числа с основанием степени 2 являются гораздо более редкими, чем простые числа, то вполне достаточным является лишь проведение теста вероятной простоты.

[/url]

Невозможность повторного использования Proof-of-Work

Еще одной важной особенностью для системы proof-of-work по работе с криптовалютой является невозможность ее повторного использования. Это означает, что proof-of-work в конкретных блоках не должна быть использована в других блоках.

Для достижения этого, цепь простых чисел связана с хэшем заголовка блока и требует, чтобы ее отправная точка была делима на хэш заголовка блока. Частное при делении становится сертификатом proof-of-work.

Хэш блока - значение, встраиваемое в дочерний блок - получается хэшированием заголовка вместе с сертификатом proof-of-work. Это не только предотвращает сертификат proof-of-

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

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

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

 

(Продолжение следует)

2 Комментария


Рекомендуемые комментарии

что в этой валюте такого, что для неё требуется целая запись в блоге, а не скромная темка в разделе "форки" ?

Ссылка на комментарий

что в этой валюте такого, что для неё требуется целая запись в блоге, а не скромная темка в разделе "форки" ?

 

Пусть будет. Для форума слишком объемный материал. Вообще любые толковые материалы по матчасти приветствуются

Ссылка на комментарий

Для публикации сообщений создайте учётную запись или авторизуйтесь

Вы должны быть пользователем, чтобы оставить комментарий

Создать учетную запись

Зарегистрируйте новую учётную запись в нашем сообществе. Это очень просто!

Регистрация нового пользователя

Войти

Уже есть аккаунт? Войти в систему.

Войти
  • Последние посетители   0 пользователей онлайн

    • Ни одного зарегистрированного пользователя не просматривает данную страницу
×
×
  • Создать...