Какие математические задачи решаются при майнинге – Что вычисляют майнинг-фермы и какую информацию обрабатывают

Home  /   Какие математические задачи решаются при майнинге – Что вычисляют майнинг-фермы и какую информацию обрабатывают

Содержание

Что вычисляют майнинг-фермы и какую информацию обрабатывают

Если вы интересуетесь современной компьютерной техникой или даже просто регулярно смотрите новости по телевизору, то, конечно же, слышали о криптовалютах и майнинге. Но что это вообще за зверь такой — майнинг? Все эти странные люди «майнеры», которые покупают видеокарты целыми партиями и собирают их в так называемые «фермы», — кто они?

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

Но что вычисляют майнинг-фермы? Для чего все эти жертвы? Большинство людей очень далеки от этой темы, кто-то лишь догадывается, как примерно все это работает, а некоторые строят конспирологические теории о суперкомпьютерах. Какие вычисления происходят при майнинге и зачем майнинг вообще нужен — довольно интересный вопрос, но на самом деле всё куда проще, чем кажется. Усаживайтесь поудобней, в этой статье мы разберем данный вопрос, а также немного поговорим о майнинге в целом.

Майнинг-ферма как новое устройство в мире компьютерной техники

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

Сейчас помимо Биткоина на рынке находится очень много различных криптовалют, и все они предъявляют разные требования к необходимому оборудованию. Пока криптовалюта молодая и сложность ее блокчейна невысокая, операции для ее функционирования вполне можно проводить и на домашнем персональном компьютере. Но со временем сложность расчетов растет и обычного компьютера становится недостаточно, и так происходит в подавляющем большинстве случаев.

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

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

Напрашивается вопрос, майнить в современных реалиях или же не стоит даже пробовать? Ну что ж, данная статья не совсем об этом, и лучше вам все объяснит более узконаправленная статья. Однако стоит сказать: для того чтобы майнить, вам по сути не нужна большая ферма, по крайней мере сразу. Если вы все-таки решитесь попробовать присоединиться к этому «празднику жизни», то вполне резонно сначала будет использовать вашу игровую карту, которая у вас уже есть дабы просто узнать, что это такое. Возможно, это совсем не ваша тема. Но если понравится, тогда уж решайте, вкладывать дополнительные деньги или нет.


Узнай, как зарабатывать на криптовалютах и ICO на бесплатном онлайн мастер-классе

Подробнее

В чем заключается майнинг, и какие задачи в нем решаются?

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

И действительно, если подумать, то мощнейший в мире китайский суперкомпьютер Sunway TaihuLight имеет приблизительную вычислительную мощность 93 Петафлопс, а одна видеокарта GTX 1080Ti — 0,0106 Петафлопс. Это значит, что суперкомпьютер равен по мощности 8774 GTX 1080Ti. Согласитесь, это просто смешно. В одной московской области суммарное количество майнеров значительно превосходит эту мощность, что уж говорить о майнерах всего мира, которых сейчас просто невероятное количество. Ну, вот не может все это быть просто так. Не правда ли?

Выдвигаются самые разные предположения, мол, все это спланированная акция, и криптовалюты придуманы, чтобы завлечь людей предоставить заинтересованным лицам «бесплатный суперкомпьютер», а когда задача будет выполнена, все они резко обесценятся. Что касается самих расчетов, то здесь все ещё веселее: некоторые думают, что так обсчитывают возможный ущерб от ядерных взрывов при начале крупномасштабной войны, вторые предполагают, что таким образом разрабатываются новые виды оружия, и так далее, и тому подобное. Но если посмотреть на все это трезвым взглядом со стороны, то подобное конечно-же кажется не меньшим бредом, чем разговоры о Нибиру и рептилоидов по РЕН-ТВ.

Как мы уже писали выше, майнинг-оборудование помогает функционированию сети блокчейна криптовалюты. А именно, оно помогает решить математические задачи криптографии. Именно из-за того, что данная система строится на принципах криптографии, этот вид электронных денег и получил наименование криптовалюта. Да, да, вы совершенно правильно поняли, на самом деле эта система — близкий родственник Веб Мани, Киви, Яндекс-денег и других подобных систем. С помощью криптовалют точно так же можно проводить транзакции покупки, продажи или обмена товаров, разница заключается только в том, что данная система абсолютно децентрализована и не зависит от банковской системы той или иной страны.

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

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

Майнинг-вычисления распределяются между всеми участниками, которые закрывают блоки транзакций. Но если бы все записывали одинаковые блоки, то рано или поздно в системе наступил бы хаос. Поэтому каждому блоку приписывается свой уникальный, так называемый «красивый» хеш, который и должен отыскать майнер. Это одновременно и служит доказательством работы, и обеспечивает надежность проведенных сделок. Поскольку за каждый блок майнер получает вознаграждение, с каждым закрытым блоком растёт и сложность вычислений в системе. Это сделано для того, чтобы с течением времени эмиссия валюты не росла в геометрической прогрессии и сохранялась стабильность. Также сложность системы растет в случае увеличения количества участников, а награда делится между ними в соответствии с вложенными вычислительными мощностями.

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

На чем зарабатывают майнеры?

Что рассчитывают майнеры, мы объяснили, теперь осталось поговорить о том, как они зарабатывают. Как уже говорилось до этого, награда засчитывается участникам за каждый найденный (или другими словами, открытый, закрытый) блок транзакций внутри блокчейна. Обычно время нахождения блока и награда за него фиксированы, например 10 минут и 50 монет криптовалюты. Эти показатели разнятся от валюты к валюте, но суть остается той же. Чем более молодая криптовалюта, тем меньше вычислительной мощности нужно для нахождения блока, но чем более популярной она становится и чем больше обрастает новыми участниками, тем сложнее становится система, и в конце концов может наступить момент, когда вычислительных мощностей майнера-одиночки просто-напросто не хватит для нахождения нужного значения хеша за отведенное для этого время.

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

Чтобы воспользоваться этим преимуществом, вам необходимо определить, что выгоднее — майнить на вашей ферме, после чего просто подать заявку на вступление в пул. Обычно лучше выбирать пул с самой высокой мощностью. Не всегда такие пулы хотят обзаводиться новыми участниками, однако в большинстве случаев вас примут с распростёртыми объятьями. Сколько именно денег принесет ферма, зависит только от ее вычислительной мощности и общей мощности пула. Чем выше эти показатели, тем выше заработок.

Но мы знаем, что большинству из вас интересны именно конкретные цифры заработка майнеров криптовалюты. Здесь очень важную роль играет сложность добычи и курс валюты относительно доллара США. Когда сложность оптимальна, а курс постоянно растет, то заработок среднестатистического домашнего «фермера» может составлять 20–30 долларов в день. Когда курс падает, а сложность возрастает, то и заработок может падать до 3–4 долларов в день и даже ниже. Большинство майнеров очень сильно зависит от времени окупаемости оборудования, так как покупают сразу много карт и вынуждены обновлять их время от времени.

Майнинг Биткоина

Биткоин — первая и самая популярная криптовалюта в мире. На старте в 2009 году за один Биткоин давали всего пять центов, в 2013 году — уже порядка ста долларов за монету. А сейчас цена на эту монету бьет все мыслимые и немыслимые рекорды, она дорожает с каждым днём и стоит уже больше пятнадцати тысяч долларов.

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

Сейчас из-за сложности системы Биткоин майнить его на видеокартах совершенно нерентабельно. Никто не запрещает обычному майнеру купить себе асик-ферму, и многие так и делают, но цена на них очень высока, и в случае обвала курса валюты такой «фермер» может быстро пойти ко дну.

Рассказывать, что именно вычисляют при майнинге Биткоина, мы не будем, так как в приведённых примерах, по большему счету, описывалась именно его модель. Стоит только отметить, что алгоритм шифрования Биткоина называется SHA-256 и применяется в большом количестве криптовалют, построенных по его прообразу. Написан этот алгоритм был агентством национальной безопасности США задолго до появления самого Биткоина и использовался как механизм шифрования веб-сайтов по протоколу безопасности SSI.

Майнинг Эфириума

Второй по популярности после Биткоина является криптовалюта Эфириум. Это довольно молодой проект, и на свет он появился совсем недавно — в 2015 году. Именно резкое подорожание этой монеты в начале 2017 года с восьми долларов до двухсот и является причиной массовой пропажи видеокарт с полок магазинов. Поскольку криптовалюта молодая, она очень хорошо добывалась на видеокартах, но сейчас, когда все набросились на ее майнинг, сложность сети очень сильно возросла.

В отличие от Биткоина, добыча Эфириума все ещё доступна на видеокартах и будет актуальной еще некоторое время. Причиной этому не в последнюю очередь служит отсутствие асик-микросхем под Эфир.

Математические задачи, которые решаются при майнинге Эфириума, очень похожи на задачи, решаемые в Биткоин. Это все такие же открытия новых блоков блокчейна для подтверждения транзакций. Главным же отличием систем является то, что в Эфириуме используется новый алгоритм DaggerHashimoto. Работа алгоритма выглядит как хеширование метаданных последнего блока системы, для которого используется специальный код под названием Nonce. Нонс представляет собой обычное двоичное число, которое задает уникальное значение хеша. Подбор «красивого» хеша теперь возможен лишь методичным перебором всех возможных вариантов. Такой вариант хеширования очень сильно усложняет шифрование и требует наличия большого количества памяти. В связи с этим внедрение в майнинг Эфира ASIC-систем очень сильно усложняется, что несомненно положительно скажется на децентрализованной криптовалюте.

Майнинг других криптовалют

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

  1. Ripple. Основана в 2013 году. Валюта, предназначенная для банков, чтобы быстрее и лучше совершать транзакции.
  2. Monero. Основана в 2014 году. Основной задачей данной валюты является обеспечение анонимных денежных переводов.
  3. Litecoin. Основана в 2011 году. Один из главных конкурентов Биткоин, но с преимуществом в более быстрых транзакциях.
  4. EthereumClassic. Дата основания — 2015 год. Представляет собой форк Эфириума. Сейчас стоит дешевле основной версии.
  5. Dash. Используется с 2014 года. Предлагает высокую анонимность транзакций. При использовании Dash конечного потребителя практически невозможно отследить.
  6. ByteCoin. 2012 год. Основная задача — защитить деньги пользователя. Для этого система использует самые совершенные криптографические алгоритмы.
  7. VertCoin. 2014 год. Криптовалюта призвана полностью обезопасить себя от ASIC-майнеров, тем самым сохранив высочайшую степень децентрализации.
  8. Dashcoin. Дата основания — 2014 год. Представляет собой анонимную криптовалюту нового поколения.
  9. NEM. Основана в 2015 году. Новая криптосистема, которая предлагает цифровую нотариальную подпись. Кроме того, обладает высочайшей скоростью проведения транзакций и обеспечивает надежное хранение средств.
  10. Decred. 2015 год. Представляет из себя гибрид систем POW и POS. Благодаря этому соблюдает тонкий баланс между майнерами и держателями монет.

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

Единственным принципиальным различием между монетами можно считать применение систем POW (доказательство работой) и POS (доказательство владением). Некоторые из представленных криптовалют требуют вычислений по системе POW, то есть доказательства роботы, это и есть классический майнинг. А некоторые, такие как NEM, построены на системе POS — доказательстве владением. В таком случае для майнинга вам хватит и обычного компьютера, но потребуется для начала купить некоторую сумму монет. В любом случае для заработка на криптовалютах лучше выбирать ту из них, которая демонстрирует медленный, но стабильный рост.


cryptomagic.ru

Какие конкретно математические задачи решаются при майнинге криптовалюты, на что конкретно тратится мощность видеокарт?

.

Мощности компьютера тратятся на транзакции и запись результата в блокчейн.

Конкретно, переписываются номера криптовалютных «купюр» из одного криптовалютного кошелька в другой. То есть в одном криптокошельке номера некоторых «купюр» стираются, а в другой криптокошелёк эти номера записываются. Эти действия в шифрованном виде записываются в блокчейн. Ключом шифрования служит вся предыдущая цепочка блокчейна. А новая запись в блокчейн является номером новой «купюры».

Примерно, это выглядит так. Допустим, все российские копейки пронумерованы уникальными номерами, как бумажные купюры. И никаких других купюр и монет нет, кроме копеек. Вы когда-то принесли в Сбербанк мешок копеек и положили на свой счет. Но банковская программа пишет на счет не число копеек, а все номера этих копеек. Учет будет именно такой по номерам.
Теперь Вы хотите часть этих копеек перечислить на мой счет. Банковская программа стирает с Вашего счета часть уникальных номеров копеек, и записывает эти номера копеек на мой счет.
При этом все действия банковской программы записываются в специальную публичную мониторинговую последовательность, копии которой хранятся не только в Сбербанке, но и во всех банках мира.
Но они не просто так туда пишутся, что программа в такое-то время стёрла такие-то номера на таком-то счете и записывала их на такой-то счет. Вся эта запись шифруется последовательностью нулей и единиц. А ключом шифрования является вся предыдущая последовательность этой мониторинговой записи. То есть ключ шифрования публичный и все желающие могут посмотреть всю историю всех транзакций копеек всех банков.
Вот эта новая шифрованная запись по переводу копеек с Вашего счета на мой счет, будет уникальным номером ещё одной новой копейки (или нескольких копеек). Причем, эта же запись будет говорить ещё и о том, что эти новые копейки достались Сбербанку и Сбербанк положил их себе на свой счет. Это если всю работу по транзакции сделал только один Сбербанк. Если Сбербанку помогали другие банки, то часть этих номеров достанется другим банкам пропорционально их вкладу в работу по транзакции и шифрованию.

.
Источник: Что такое блокчейн. Эта статья написана для людей, которые не имеют образования программиста и математика, поэтому она достаточно понятная.

.

otvet.mail.ru

Какие математические задачи решают процессоры/видеокарты майнеров, чтобы получить биткоин?

Они решают обратную задачу хэширования. 

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

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

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

Когда один из майнеров находит, наконец, подходящее решение, он об этом сообщает всем прочим (передает пароль). А они проверяют правильность (вычисляют хэш и сравнивают с интервалом — это уже просто) и если убеждаются в факте решения, то записывают в своем регистре биткойн на счет майнера, нашедшего решение  («пароль», если угодно). Если запись сделает более половины участников системы, биткойн признается всей системой и его можно тратить тому, кто нашел решение (намайнил биткойн).

Пока никто не контролирует 50% участвующих компьютеров, система остается устойчивой к взлому. Даже если 49% запишут биткойн не на тот счет, владелец нехорошего счета не сможет им воспользоваться. А настояшему владельцу хватит и признания 51% участников. И тем устойчивей система, чем больше в ней независимых участников.

Подробнее:

http://bramaby.com/ls/blog/analytics/7505.html

http://bramaby.com/ls/blog/analytics/7500.html

thequestion.ru

Биткойн-майнинг — NP-полная задача? |

Независимый набор из синих вершин — иллюстрация к одной из подзадач биткойн-майнинга

Биткойн предоставляет ученым широчайшее поле для исследований. Для исследования вопросов, связанных с технологией блокчейна, приходится пользоваться множеством понятий из разных областей математики, computer science, экономики и других наук. Недавно эта многогранность биткойна в очередной раз подтвердилась: выяснилось, что быть идеальным майнером с математической точки зрения невероятно сложно.

В теории оптимизации подробно описан класс NP — класс задач, для решения которых, как предполагается, не существует эффективного (полиномиального) алгоритма. Здесь мы не говорим о широко известной задаче нахождения такого блока, что его хэш меньше заданной величины. Эта задача сложна по своей природе. Но перед тем, как начать что-либо хэшировать, майнер должен выбрать транзакции, которые войдут в блок. Оказывается, что эта задача содержит две оптимизационные подзадачи, обе из которых принадлежат классу NP!

В любой момент времени в биткойн-сети содержится множество транзакций, которые еще не были включены в блок. Майнеры могут включать или не включать транзакции в блок по своему усмотрению, предполагая, что они корректны по форме, ссылаются только на уже опубликованные (возможно, в этом же блоке) транзакции и не конфликтуют с ранее подтвержденными транзакциями. Каждая транзакция содержит комиссию. Размер блока не может превышать 1 мегабайт. Задача майнера — подобрать набор транзакций для блока, максимизируя сумму комиссий. Эта задача содержит две оптимизационные задачи.

Задача о ранце

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

Эта задача полностью эквивалентна широко известной «задаче о ранце». Задача о ранце формулируется так: пусть имеется ранец определенной вместимости и набор предметов, каждый из которых имеет два параметра — вес и ценность. Задача заключается в том, чтобы собрать ранец с максимальной ценностью предметов внутри, соблюдая при этом ограничение на вес ранца. В терминологии биткойна «ранец» — это блок, «вес» — это размер транзакции, «цена» — размер комиссии, а «вместимость ранца» — максимальный размер блока (на данный момент 1 мегабайт).

Задача о ранце хорошо изучена. Нахождение оптимального решения для нее принадлежит классу NP, а поиск ответа на вопрос, существует ли решение с суммарным вознаграждением, превышающим данное, является NP-полной задачей (то есть может быть сведена к другой задаче из класса NP полиномиальным алгоритмом). Следовательно, то же самое верно и для задачи составления биткойн-блока, даже без учета возможных конфликтов между транзакциями.

Задача о независимом множестве

Транзакции могут зависеть друг от друга или конфликтовать.

Рассмотрим сначала конфликты: некоторые транзакции не могут быть включены в один блок из-за запрета двойной траты. Упростим задачу, считая размер блока неограниченным и предполагая, что все транзакции включают одну и ту же комиссию. Если транзакции B и B’ в качестве входов используют один и тот же выход транзакции A, только одна из транзакций B и B’ может быть включена в блок. Предполагая это единственным ограничением на формирование блока, мы можем изобразить множество доступных транзакций в виде графа, где две транзакции соединены ребром, если они конфликтуют. Задача майнера — выделить максимальное подмножество вершин (транзакций), чтобы никакие две вершины из этого подмножества не были соединены ребром (не конфликтовали).

Это не что иное как хорошо изученная задача о независимом множестве! Следовательно, задача поиска оптимального решения принадлежит классу NP, а ответ на вопрос, существует ли решение с суммарной комиссией выше заданного уровня, является NP-полной задачей.

Что касается зависимостей, мы можем учесть и их в графе конфликтов. Зависимости между транзакциями возникают потому, что, если транзакция B использует выход транзакции A, транзакция A должна быть опубликована, если B опубликована. Отобразить это на графе конфликтов мы можем с помощью направленных ребер. Тем не менее, в упрощенной формулировке, не учитывающей ограничения на размер блока, мы можем считать, что, если транзакция B зависит от транзакции A, мы наряду с B автоматически включим в блок и транзакцию A. Здесь мы пользуемся тем, что комиссии за транзакции строго положительны.

Кроме того, нам придется добавить на граф дополнительные ребра (конфликты): ведь если B зависит от A, а A конфликтует с A’, тогда B также конфликтует с A’. Для каждой транзакции B мы должны добавить в граф все транзакции, конфликтующие с транзакциями, от которых зависит B. Такая трансформация может быть проведена за полиномиальное время; для вершин модифицированного графа мы можем искать максимальное подмножество без конфликтов, решая задачу о независимом множестве. Задача принадлежит классу NP даже без учета размера транзакций и величины комиссии, а только лишь из-за наличия конфликтов.

Проблема на практике?

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

Но играет ли это роль на практике? Многие задачи в теории являются NP-сложными, но с практической точки зрения зачастую довольно просто найти достаточно хорошую аппроксимацию решения. Неясно, насколько сложной является задача нахождения «достаточно хорошего» биткойн-блока. Попытки двойной траты встречаются относительно редко, так же как и попытки включения в один блок транзакции и ее непосредственного предка. Так что проблема поиска независимого множества на практике не так сложна.

Что же касается «задачи о ранце» в формировании блока, то на практике она не очевидна. Биткойн-блоки обычно собираются из пула в тысячи или даже десятки тысяч транзакций, размер и комиссии у которых могут существенно различаться.

Текущая версия эталонной реализации биткойн-протокола не пытается решить даже упрощенный вариант этой задачи: транзакции сортируются исходя их эвристической характеристики «приоритета» и добавляются в блок жадным алгоритмом. Возможно, майнеры могли бы немного увеличить свою прибыль, усовершенствовав этот алгоритм, но поскольку сейчас их доход формируется в большей степени за счет награды за блок, а не комиссии за транзакции, у них нет мотивации это делать. С другой стороны, у существующей формулы есть преимущества: она ограничивает минимальный размер комиссии и действует прозрачно для пользователей. Однако по мере того как награда за блок будет уменьшаться, для сохранения прибыли майнерам придется изучить теорию оптимизации и теорию сложности алгоритмов.

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

NP-сложные задачи майнинга — еще один пример того, как биткойн объединяет множество разделов математики и информатики. Поэтому он представляет и еще долго будет представлять огромный интерес для исследователей в этих областях.

По материалам Freedom to Tinker

Поделиться ссылкой:

Related

bitnovosti.com

Какие математические задачи решают процессоры/видеокарты майнеров чтобы получить биткоин? И откуда он генерируется если нет центрального сервера?&nbsp

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

Вычислить хэш по паролю легко, а найти перебором пароль по хэшу — сложно.

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

Когда один из майнеров находит, наконец, подходящее решение, он об этом сообщает всем прочим (передает пароль). А они проверяют правильность (вычисляют хэш и сравнивают с интервалом — это уже просто) и если убеждаются в факте решения, то записывают в своем регистре биткойн на счет майнера, нашедшего решение («пароль», если угодно). Если запись сделает более половины участников системы, биткойн признается всей системой и его можно тратить тому, кто нашел решение (намайнил биткойн).

Пока никто не контролирует 50% участвующих компьютеров, система остается устойчивой к взлому. Даже если 49% запишут биткойн не на тот счет, владелец нехорошего счета не сможет им воспользоваться. А настояшему владельцу хватит и признания 51% участников. И тем устойчивей система, чем больше в ней независимых участников.

Подробнее:

http://bramaby.com/ls/blog/analytics/7505.html

http://bramaby.com/ls/blog/analytics/7500.html

Читайте также

news.rambler.ru

вычислить — Какую математическую задачу нужно решать в биткоин-майнинге (bitcoin mining)?



Может быть человеческий ум справится успешнее комьютерного перебора? (в нахождении метода решения, конечно, а не в переборе)

задан
26 Апр ’15 13:08

Отличается ли Ваш вопрос по содержанию от следующего: «Может ли оказаться, что P=NP, и какой-то человек это докажет?» Если да, то в чём отличие?

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

Мне не известна специфика этой деятельности, но я так понимаю, там специально предлагаются такие задачи, для которых «хороший» алгоритм не известен. Если где-то окажется, что имеется «обходной» путь, то это значит, что задача предложена неудачно.

Вообще, этот вопрос не относится к области математики, так мне кажется.

Неизвестны алгоритмы, но «обходной путь», например, это квантовый комьютер, но мало кому пока доступен. Кроме того, меня интересуют не алгоритмы, знание которых позволит «взломать» систему или нарушить анонимность транзакций (там да, алгоритмы так и подбирались), а как раз наоборот — поддерживать (если ни в чем не ошибаюсь, для этого и служит майнинг). Да, до конца не относится ни к математике, ни к программированию, но пересекается и с тем и другим — смежный вопрос. Все в руках админов.

%COMMENT%




math.hashcode.ru

Биткоин для «чайников»: Майнинг

Но, не все знают истинную сущность этого понятия, а также его предназначения в протоколе (программных правилах) криптовалюты.

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

Действительно, слово «майнинг» (mining) в переводе с английского означает добычу полезных ископаемых. А майнеры (miners) — это шахтеры.

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

Вернемся к денежным переводам (транзакциям), которые составляют главную задачу и цель существования сети Биткоина.

Собственно, процесс денежных переводов в типичной финансовой среде описывается серией из четырех последовательных шагов:

  1. Submission — отправитель посылает в систему платежное сообщение (поручение) о переводе некоторой суммы денег получателю;
  2. Validation — сообщение проходит процедуру проверки отправителя и целостности сообщения;
  3. Conditionality — проверяется наличие достаточного баланса для перевода на счету отправителя;
  4. Settlement — проведение транзакции, перевод денежных средств на счет получателя.

В современной экономике эти процессы обычно поддерживаются финансовыми посредниками, такими как банки.

Отправитель (клиент банка) посылает платежное сообщение или поручение (submission) в платежную систему банка. Это сообщение должно пройти процедуру подтверждения (идентификации) клиента и целостности сообщения (validation). После успешной валидации сообщения банковская система проверяет необходимые условия для платежа (conditionality), а именно — достаточность средств на балансе клиента или наличие кредита. Если все проверки пройдены, банк окончательно (безусловно и безотзывно) проводит платеж (settlement)— пополнение счета получателя и уменьшение баланса счета отправителя.

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

Криптовалюты, в частности Биткоин, являются полностью децентрализованными системами, в которых вопросы доверия решаются криптографическими методами.

Поэтому, процесс денежных переводов в них присходит несколько по-другому, а именно:

  1. Submission — отправитель перевода при помощи программного приложения «биткоин-кошелек» направляет в сеть Биткоина сообщение, в котором указываются биткоин-адреса отправителя и получателя, а также сумма перевода и сумма комиссии за перевод (опционально).

    Это сообщение автоматически подписывается электронной цифровой подписью (ЭЦП) отправителя, которая формируется при помощи закрытого (приватного) ключа отправителя и криптографически связана с его биткоин-адресом. Подробнее см. статью «Электронная цифровая подпись: Просто и наглядно».
  2. Validation — это сообщение проходит проверку в сети по ЭЦП. Тем самым, происходит идентификация отправителя. Для проверки используется биткоин-адрес, поскольку он связан с приватным ключом отправителя при помощи которого он подписал сообщение.

    На самом деле личность отправителя не имеет значения, она остается анонимной. Под идентификацией отправителя понимается соответствие биткоин-адреса отправителя и сообщения (платежного поручения) криптографической подписи (ЭЦП). Тем самым подтверждается, что указанная сумма денег (монет биткоина) должна быть отправлена с конкретного биткоин-адреса.
  3. Conditionality — проверяется наличие достаточного баланса для перевода на счету отправителя. Для этого, согласно протоколу Биткоина, происходит подсчет всех непотраченных Выходов (т.н. UTXOunspent transaction output) этого адреса. Подробнее см. статью «Биткоин за 5 минут: Блок».
  4. Если все проверки прошли, сформированная транзакция ждет добавления в блок и записи в блокчейн.

И вот тут, собственно, и начинается процесс, который получил название «майнинг».

Что же это такое? Попробуем разобраться…

Казалось бы все просто — если платежное сообщение (поручение) прошло все проверки, то его можно записывать в реестр (бухгалтерскую книгу), каковым является блокчейн.

Но, во-первых, мы знаем, что данные (транзакции) в блокчейн записываются в виде блоков (транзакций). Следовательно, надо предварительно сформировать блок. Если блок будет маленьким, например, из нескольких транзакций, то блоки формировались бы с большой скоростью — сотни блоков в минуту.

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

Следовательно, обработка поступивших в сеть платежных поручений о переводе биткоинов, может вестись одновременно на многих узлах. Каждый узел формировал бы и записывал свои блоки.

При этом могла возникнуть ситуация называемая «проблемой двойных трат», когда некий недобросовестный пользователь Биткоин-сети решил отправить со своего биткоин-адреса, баланс которого составляет 1 BTC, одновременно два платежа по 1 BTC на два разных биткоин-адреса.

Эти платежи могли одновременно попасть на обработку в разные узлы и быть записаны в разные блоки. Но, как мы знаем, записанный в блокчейн блок исправлять уже нельзя.

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

Поэтому протоколом Биткоина предусмотрено, что каждые 10 минут в блокчейн может быть записан только один сформированный блок.

Но, какой именно узел будет это делать? Ведь сеть Биткоина одноранговая и все узлы имеют равные права.

Автор Биткоина, некий Сатоши Накамото, предложил в протоколе использовать для определения такого узла алгоритм, который получил название Proof of Work (PoW) — доказательство сделанной работы.

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

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

Такой криптографической задачей в протоколе Биткоина является задача по подбору параметра, называемого nonce, который, будучи добавлен к заголовку сформированного блока, давал хэш-код (см.статью «Хэширование: Просто и наглядно»), начинающийся с заданного количества нулевых битов (bits), что равносильно получению хэша, менее и равного заданного большого числа.

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

Такую задачу можно решить только перебором большого количества разных параметров (nonce). Что очень трудоемко и требует больших вычислительных мощностей.

С другой стороны, проверка правильности решения этой криптографической задачи очень проста — надо просто добавить nonсе в сформированный блок и вычислить его хэш-код при помощи хэш-функции SHA-256.

После того, как один из майнеров (узел) найдет требуемое значение параметра nonce, остальные просто проверяют правильность вычислений и дают подтверждение.

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

Весь этот процесс по «цифроперемалыванию» — подставил новый параметр nonce, вычислил хэш, проверил результат и т.д. до нахождения нужного хэша с нолями в его начале, — и есть пресловутый «майнинг»!

Следует добавить, что сложность решаемой криптографической задачи может изменяться (увеличиваться) в зависимости от суммарной мощности компьютеров узлов, занятых майнингом. С ростом этой мощности количество нулевых битов в искомом хэше растет таким образом, чтобы максимальное время поиска результата (nonce) было не более 10 минут. Это автоматическое изменение сложности зашито программно в протоколе Биткойна.

К слову сказать, растущая вычислительная мощность сети майнеров, а также связанная с ней сложность криптографической задачи и, как следствие, сложность и трудоемкость «добычи» биткоинов приводит к тому, что майнеры объединяются в т.н. пулы, чтобы повысить вероятность решения задачи и получения вознаграждения за блок. При успехе «добытые биткоины», включая и комиссионное вознаграждение, делятся пропорционально вычислительной мощности каждого участника пула.

Но вернемся к майнигу… А где же добытые «шахтерами» (майнерами) деньги (биткоины)?

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

Собственно, новые монеты могут попасть в сеть Биткоина только в результате майнинга. Тем самым осуществляется эмиссия биткоина.

Первоначально (в 2009 году) за каждый новый блок (т.е. каждые 10 минут) манеры, которые добавили его в блокчейн, получали 50 монет BTC. Но, опять же, протоколом Биткоина установлено, что через каждые 210 000 блоков (примерно 4 года) вознаграждение за новый блок уменьшается в 2 раза. Поэтому сейчас (2017 год) майнеры получают за добавленный блок 12,5 BTC. А суммарное количество биткоинов (эмиссия) не может превышать 21 млн монет. Почему это так, я рассказал в статье «Почему количество биткоинов ограничено».

Помимо платы за блок майнеры, добавившие блок в блокчейн Биткоина, получают комиссионное вознаграждение (transaction fee) с каждой транзакции. При этом майнеры стараются наполнить блок в первую очередь транзакциями с максимальной комиссией. Поэтому, если отправитель указал небольшую комиссию, его платежное поручение откладывается в исполнении. В результате некоторые платежи могут идти часами, а то и вовсе не пройти.

Подведем итоги:

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

  • Запись нового блока транзакций в блокчейн.
  • Выпуск новых монет биткоина (эмиссия).
  • Сетевое вознаграждение участникам сети (майнерам) за обработку транзакций и формирование нового блока.
  • Поддержание большого количество копий блокчейна в сети. Это происходит из-за того, что майнерам необходимо иметь полную актуальную (последнюю) версию блокчена для контроля (валидации) новых транзакций.

Ранее по теме «Биткоин за 5 минут»:

 

www.20khvylyn.com

Отправить ответ

avatar
  Подписаться  
Уведомление о