Topic: Анти-пул алгоритм PoW (Read 18545 times)

Как уже было сказано, вышеописанный анти-пул алгоритм PoW версии 1.0 имеет существенный недостаток, заключающийся в том, что майнеры могут однократно выполнить первый и второй цикл майнинга, после чего игнорировать эти циклы и находить подходящий блок, перебирая не число block_nonce, а число sign_nonce в схеме подписи ECDSA на эллиптической кривой secp256k1, используя специализированное оборудование. Таким образом, некоторые майнеры могут получить многократное превосходство над другими майнерами, у которых нет ASIC, поэтому предлагается следующее решение, устраняющее данный недостаток.

---

Основной проблемой в реализации анти-пул алгоритма PoW версии 1.0 является то, что при использовании асимметричной криптографии ECDSA на эллиптической кривой secp256k1 невозможно подписать хеш (число) одновариантно и одинаково без потери секурности и безопасности, поскольку число sign_nonce в данной схеме должно быть не только рандомным, но и неизвестным третьим лицам. Иначе очень легко вычислить число R, а затем приватный ключ K из числа S. Поэтому основной задачей для решения вышеописанной проблемы является нахождение такой асимметричной криптографии, которая позволяет подписать хеш (число) достаточно секурно и даёт одновариантный и одинаковый результат.

Для имплементации анти-пул алгоритма PoW версии 2.0 предлагается использовать асимметричную криптографию RSA (Rivest-Shamir-Adleman), широко применяемую, например, в известном приложении PGP (Pretty Good Privacy). В этой криптографии число (хеш), являющееся открытым сообщением M, для повышения секурности прежде подписывания обычно инкапсулируется в другое (большее) число методом Probabilistic Signature Scheme (PSS). По умолчанию в данной схеме используется так называемая "соль", которая является рандомным числом (то есть, по сути, sign_nonce), но этот параметр может быть опущен. Таким образом схема PSS без "соли" при подписывании одного и того же (хеша) числа даёт одновариантный и одинаковый результат. Разумеется, отсутствие "соли" в подписи снижает секурность, но не существенно.

---

В целях тестирования анти-пул алгоритма PoW версии 2.0 можно использовать, например, известное приложение OpenSSL. В настоящее время в криптографии RSA обычно используются публичная экспонента E, равная 65537, и публичный ключ N длиной 2048 бит (256 байт).


Чтобы сгенерировать пару ключей RSA, необходимо:

1) Создать приватный ключ, являющийся двумя простыми числами P и Q, каждый длиной по 1024 бит (по 128 байт):


2) Вычислить публичный ключ N длиной 2048 бит (256 байт), являющийся произведением двух чисел P и Q:



Чтобы подписать заголовок хеша блока методом RSA-PSS, необходимо:

1) Вычислить ASIC-устойчивым алгоритмом и записать хеш заголовка блока в текстовый файл, например, "block_header_hash.txt".

2) Подписать хеш заголовка блока и записать сигнатуру в файл "block_header_hash.txt.sig":


Следует отметить, что параметр rsa_pss_saltlen равен нулю, поэтому результат выполнения этой команды при одних и тех же входящих данных файла "block_header_hash.txt" всегда одновариантен и одинаков.


В версии 2.0 структура заголовка блока содержит 7 полей:

• 1) block_version (4 байта)
• 2) previous_block_header_hash (32 байта)
• 3) block_timestamp (8 байт)
• 4) transaction_count (4 байта)
• 5) merkle_root (32 байта)
• 6) required_leading_zero_bit_count_in_rsa_sign (1 байт)
• 7) block_nonce (8 байт)

Затем записывается подпись block_header_hash_rsa_sign_without_salt (256 байт). Итого размер заголовка блока с подписью составляет 89 + 256 = 345 байт.


Для имплементации анти-пул алгоритма PoW версии 2.0 транзакции должны одновременно поддерживать адреса, основанные не только на асимметричной криптографии ECDSA на эллиптической кривой secp256k1, но и на асимметричной криптографии RSA с инкапсуляцией числа (хеша) по схеме PSS. Если рассматривать на примере Bitcoin, то потребуется ввести новый OP_CHECKSIGN_RSA, который верифицирует два последних значения из стека (подпись S и публичный ключ N) по схеме PSS (с "солью") и проверяет валидность входного скрипта транзакции.


Параметр rsa_pss_saltlen, равный -1, в данной команде означает, что длина "соли" будет равна длине хеша SHA256, то есть 32 байтам, поэтому секурность и безопасность будут на высоком уровне.


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

Выходной скрипт scriptPubKey COINBASE-транзакции должен содержать формат PAY-TO-RSA-PUBKEY:


Соответственно, для того, чтобы в будущем потратить этот выход, во входном скрипте scriptSig последующей транзакции нужно будет указать подпись S и публичный ключ N:

---

Представленный анти-пул алгоритм PoW версии 2.0 устраняет указанный существенный недостаток версии 1.0, а также добавляет некоторые усовершенствования. Использование в майнинге асимметричной криптографии RSA по схеме PSS без "соли" не даст возможности майнерам перебирать число sign_nonce вместо перебора числа block_nonce, как это было возможно в анти-пул алгоритме PoW версии 1.0, поэтому они будут вынуждены вычислять хеш заголовка блока многократно, при каждой итерации майнинга проходя через ASIC-устойчивый алгоритм. Кроме этого, администраторы ботнетов и вебсайтов, скорее всего, не будут устанавливать скрытые JS-скрипты, поскольку приватный ключ RSA (то есть числа P и Q) необходимы при каждой итерации майнинга.

Описанная схема позволяет обеспечить ASIC-устойчивость, уменьшить централизацию майнинга и, как следствие, ещё более снизить возможности цензурирования транзакций узким кругом лиц.

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

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


Почему люди соединяются в пулы?
1)Не хотят держать полную ноду (долго скачивать, много держать данных) - использовать остатки, давно известное решение и как вы знаете оно уже работает
2)Хотят периодически (раз в неделю/месяц) получать награду - значит чаще платить. В одном месяце более 2 миллиона секунд, поэтому достаточно чтобы больше половины майнеров имели хотя бы одну миллионную мощность сети, чтобы обеспечить децентрализацию.

Мое решение не противоречит с вашим. Просто я показал достаточность моего предложения в определенных рамках. Точно такое же решение как ваше я продумывал 1,5 года назад когда думал как создать идеальный блокчейн (были ветки на этом форуме), но отказался от него по причине медлительности проверки электронной подписи (порядка тысяч в секунду на одно ядро).

Полагаю, что под выплатой награды подразумевается майнинг нового блока и добавление его в блокчейн. Закономерно, что чем чаще новые блоки добавляются в блокчейн, тем больше орфанов в сети.

Насколько я знаю, например, у Ethereum номинальное время на майнинг одного блока равно примерно 15 секунд, это довольно малый промежуток, но и там тоже майнинг-пулы (согласно статистике, например, у Ethermine 25%, у f2pool 21%, у dwarfpool 13%, и т.д.). Поэтому, на мой взгляд, для анти-пул алгоритма PoW не имеет особого значения, как часто блоки добавляются в блокчейн. По-моему, это должно быть реализовано на уровне вычислительных операций майнинга с использованием подписей.

С какого перепою?

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

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

Какой-то свой говнокойн хочешь прорекламировать? Кому он нужен, Неуловимый Джо?

Смотрите, по теме топика: самый эффективный способ защиты от пула это выплата награды как можно чаще, например раз в секунду. Угадайте где это уже сделано и если там пулы...

Мне бы хотелось в настоящей теме обсуждать именно анти-пул алгоритм PoW, включая его связку с ASIC-устойчивыми математическими операциями. У меня появилась идея, как можно усовершенствовать описанный в первом посте алгоритм, и в будущем я планирую опубликовать здесь версию 2.0.

Поэтому мной в этом разделе была создана новая тема:
Способы отсечения старых блоков в блокчейне

Предлагаю Вам опубликовать способ, реализованный в Вашей монете, в той теме и обсуждать этот вопрос там.

Извиняюсь, но если уже можно сделать без централизованного сервиса (и это уже  реализовано в Тере), то зачем даже думать про централизованное решение??

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

1 Более подробно я писал тут: https://docs.google.com/document/d/1JVYcfggPK-ZiF4cnerr_2-IrK9JyxD7Aw4ihlR2sNjI/edit?usp=sharing
Там есть пример, цитата: "Из примера видно условное постоянство - левые три таблицы не изменились при изменении номера текущего блока с 30001 на 30010"
3 Основная идея такая:
а)При больших объемах данных, которые неминуемо наступят при 1000 tps, новые пользователи должны иметь возможность быстрого скачивания блокчейна, чтобы провалидировать его и приступить к работе с ним. Поэтому порядок скачивания меняется - если он раньше был с начала цепочки, то теперь будет загружаться с конца.
б)Дать пользователям возможность работы с блокчейном при ограниченных размерах емкости диска (HDD/SSD), например 10 Гбайт


Т.е. начальные цепочки не отмирают. Они просто разворачиваются в сторону бесконечности, если так можно выразиться...

Ещё больше вопросов чем ответов, надо код таки смотреть.

1. Три точки 8К, 40К, 3М какова дискретность перескока при условии продвижения основной цепи на один блок?
2. В битке верификация с конца проходит с целью установления реального баланса юзера.
3. Вы таки сделали возможность перезаписи состояния кошелька с целью умерщвления старых частей чейна? Каков критерий окончательного омертвления? Что станет с мёртвыми частями?

Вот вам пример алгоритма и его практической реализации (совсем недавно запилил):
https://medium.com/@progr76/update-teranova-31dd3380f25c

русский текст:
https://docs.google.com/document/d/1SHGJX4YObjcqJwQE4MngX38hwrpT0bMNk0lyyRj_EDY/edit?usp=sharing

"""Такие криптовалюты с отсечением старых блоков существуют"""


Приведите примеры.

можно же хранить контрольную сумму\заголовки блоков в основном чейне, в битке это примерно 4 метра в год, а инфу о доказательстве баланса кинуть на юзеров

Честно говоря, я не имею представления, как именно реализованы указанные Вами монеты, особенно, как решается связка анти-пул механизма и ASIC-устойчивого алгоритма.

Как уже было отмечено в первом посте этой темы, описанный мной анти-пул алгоритм PoW в текущей реализации имеет недостаток, заключающийся в том, что майнеры могут один раз сгенерировать block_nonce и вычислить хеш блока ASIC-устойчивым алгоритмом, а затем находить подпись требуемой сложности, просто перебирая sign_nonce для подписи ECDSA secp256k1. У меня есть почти 100-процентная уверенность, что эти математические операции не являются ASIC-устойчивыми, поэтому представленный мной анти-пул алгоритм версии 1.0 нуждается в доработке до версии 2.0.



Вероятно, Вы имеете в виду отсечение не "хвоста" блокчейна, а его "головы". Такие криптовалюты с отсечением старых блоков существуют, но здесь требуется полное доверие к тому, кто будет создавать такие "контрольные" блоки. Одно из достоинств блокчейн-технологии состоит как раз в том, что можно проверить и верифицировать абсолютно все транзакции с самого Genesis-блока, хотя, как вариант, в качестве "контрольного" блока можно использовать просто список непотраченных выходов транзакций и суммы монет на них в определённый момент времени.



Соглашусь, что CPU-only алгоритм предполагает максимальную децентрализацию в виду большей распространённости процессоров, нежели GPU и ASIC, но и эта опция тоже не идеальна, поскольку производительности современных процессоров существенно различаются.

Алгоритм описанный в статье существует.
Называется монета Spreadcoin существует с 2014 года торгуется на бинансе.
Есть форки Zillioncoin и Zettelkasten. Типа CPU-only. Не торгуются нигде.
Пулов естественно нету. Децентрализации хоть отбавляй.

Еще свои пять копеек добавлю к Вашим рассуждениям.
В идеальной крипте ИМХО должны быть три вещи:
1.Антипул механизм (существует реально по описанной Вами технологии).
2.CPU only майнинг (алгоритм предлагаю 1GB-AES, монетка Hodlcoin например) Чтобы никаких ригов с видяхами.
3.Нужен механизм поддержки одиноких процессородрочеров, чтобы реальная децентрализация была. Предлагаю следующую схему:

Есть в эфире такое понятие как uncle блоки (дядя - брат отеческого блока), это орфаны которые монетизируются на уровне алгоритма, добавляются в блокчейн и повышают его надежность, за счет вложенных в них вычислений. Uncle включенные в блок, получают 7/8 обычной награды блока.
Я предлагаю распространить этот механизм не только на орфаны (идеальные альтернативные решения блока) но и на шары (неидеальные альтернативные решения блока) и выплачивать им награду пропорционально степени идеальности шары, от 7/8 за идеальную и вниз до предельной нижней сложности принятия шар, она задается фиксировано при создании алгоритма и соответствует работе среднестатистического хомячкового процессора за сутки.
Так любой нищеброд будет держать полную ноду и ему будет периодически капать бабло.

Проблему тяжелого блокчейна я предлагаю решить путем отсчечения хвоста блокчейна. Допустим так: каждые 50 тыс.блоков (при времени блока в 1 мин - это около месяца) создается контрольный блок содержащий полный перечень всех ненулевых кошельков и их балансов. А каждые 300 тыс блоков. происходит отсечение, самого древнего 50 тысячного контрольного блока. При этом индексы всех блоков остаются (как в Electrum кошельках)

В остальном это должен быть обычный CPU-only форк спредкоина, типа zillioncoin, чтобы майнился только на CPU и без пулов и никаких видеокарт.
Почему именно на CPU без GPU и без пулов? - для повышения децентрализации, чтобы действовал (насколько это возможно)  принцип одна нода- один голос - равные возможности для нахождения блока. GPU, ASIC и пулы этому принципу противоречат, так как делают систему централизованной за счет концентрации мощностей в одних руках, что противоречит изначальной концепции крипты - распределенные децентрализованные деньги.

Для тех кто хочет, чтобы он оставался валидным без пересчитывания конечно невозможно, остальным это делать никто не запрещает, поэтому да, теоретически можно.

Да, верно. Это моё предложение было зачёркнуто в первом посте.



Тоже верно. Указание о допустимости в COINBASE-транзакции только одного выхода P2PK или P2PKH было добавлено в первый пост.



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



Нет, это невозможно. Любое изменение COINBASE-транзакции пост-фактум приведёт к невалидности поля merkle_root в заголовке блока.

Первое, блоки нужны для того чтобы защитить историю от изменения. Второе ветвление цепочки блоков и майнинг позволяют разрешить конфликт транзакций тратящих одни и те же монеты. Так как если я предоставлю две конкурирующие транзакции, нужен алгоритм позволяющий однозначно сказать что одна из них валидна а вторая нет. Так что без блоков уж работать не будет.
Накамото решил задачу византийских генералов для общего случая, когда количество участников может динамически меняться. Цепочка блоков +  POW ( майнинг) представляют из себя мульти подпись с динамически изменяемым числом участников. У каждого майнера свои интересы финансовые и по сути рациональное поведения каждого майнера урвать себе. Тут и получается что как враги они и договариваются. И так как вся система находиться в равновесии Неша, то наиболее рациональным поведением участника, является следовать правилам, в случае отклонения от правил и попытки придумать свою стратегию поведения он в итоге потерпит убыток.

а тут консенсуса наоборот нет - расчет на то, что транза через какой-то узел, да все равно проскочит...

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


PS  вообще забавляет "консенсус" в этом контексте - когда договариваются враги я еще понимаю...
А тут у вас что, правое полушарие с левым конфликтует чтоли, или печенка с селезенкой?

Да давай адрес, Биток не эфир с Виталиком, и грош цена будет битку после прецедента цензуры.