Пишем свой блокчейн. Майнинг


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

Вводная

Как и в прошлый раз - рассмотрим именно принцип работы майнинга, без использования реальных блокчейнов.

Теперь в нашем блокчейне у каждого блока будет только номер и хэш.
Для реализации так-же будем использовать PHP+MySQL

Сразу дамп таблицы

CREATE TABLE `mining` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `hash` varchar(255) COLLATE utf8mb4_unicode_ci NOT NULL,
  `counts` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;

Правила блокчейна

Зададим следующие правила. В каждом блоке берется хэш предыдущего и хэш текущего. Склеиваем их в одну строку и хэшируем по sha256.
Затем считаем сколько в хэше единиц, двоек, троек и т.д.
В блоках с 1 по 9 должна быть одна единица.
В блоках с 10 по 19 должна быть одна единица и две двойки.
В блоках с 20 по 29 должна быть одна единица, две двойки и три тройки.
В блоках с 30 по 39 должна быть одна единица, две двойки, три тройки и четыре четвёрки.
И так далее до блоков 80-89.
Таким образом 89 блоков блокчейна делятся на 8 групп по 10 блоков в каждой и в первой группе 9 блоков(так как нет нулевого блока).

В последней девятой группе должно совпадать 45 символов(сумма чисел от 1 до 9)
Всего в sha256 хэше 63 символа из набора: 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f.
45 меньше 63, так что в алгоритм мы укладываемся.

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

Код

Весь код я помещу в четырёх файлах:

  • config.php - подключение к БД (из прошлого урока)
  • mining.php - собственно майнинг
  • mining_functions.php - функции для работы майнинга
  • mining_verify.php - проверка целостности цепочки блокчейна

Листинг config.php

В этом файле только подключение к БД.

$db = new PDO('mysql:dbname=blockchain; host=localhost',"db_user","db_pass",
    array(PDO::MYSQL_ATTR_INIT_COMMAND => "SET NAMES utf8"));

Листинг mining_functions.php

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

//находим hash и id последнего блока. считаем "часть" блоков
function getLastBlock() {
    global $db;

    //для первого блока hash будет пустым и id = 0
    $last_hash = '';
    $last_block_id = 0;

    //тянем hash и id последнего блока
    $sql = "select * from `mining` order by id desc limit 1";
    $sth = $db->prepare($sql);
    $sth->execute();
    $res = $sth->fetch();
    if (!empty($res['hash'])) {
        $last_hash = $res['hash'];
        $last_block_id = $res['id'];
    }

    // определяем к какой "части" относится блок
    $part = (int)(($last_block_id + 10) / 10);

    return [
        'last_hash' => $last_hash,
        'last_block_id' => $last_block_id,
        'part' => $part
    ];
}

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

//формирование рандомного хэша
function generateMiningHash() {
    return hash('sha256', rand());
}

Имея на входе сформированный хэш(не из функции generateMiningHash) и "часть" блокчейна - проверяем выполняются ли на нём правила блокчейна.

// проверка удовлетворяет ли хэш условиям блокчейна
function checkHash($hash, $part) {
    // разбиваем строку на символы
    $symbols = str_split($hash);
    $check = true;
    $ver = 1;
    while ($ver <= $part) {
        // для каждой "части" проверяем количество нужных символов
        $ver_count = $ver;
        foreach ($symbols as $symbol) {
            if ($symbol == $ver) {
                $ver_count--;
            }
        }
        if ($ver_count != 0) {
            // если все правила "части" выполнены - $check останется равным true
            $check = false;
        }
        $ver++;
    }
    return $check;
}

Тут всё просто. После всех проверок просто записываем блок в базу.
hash - найденный хэш
counts - количество переборов(для статистики)

//создание блока
function insertMinedBlock($hash, $counts) {
    global $db;
    $sql = "insert into `mining` (`hash`, `counts`) values (:hash, :counts)";
    $sth = $db->prepare($sql);
    $sth->bindValue(':hash', $hash);
    $sth->bindValue(':counts', $counts);
    $sth->execute();
}

И наконец основная функция - майнинг.
На вход подаём "часть" и хэш предыдущего блока.
$start и $limit необязательны. $limit - отвечает за количество перебираемых блоков. Если сделать его меньше - вы "замедлите" скорость майнинга. $start - будет нужна для правильного подсчёта количества перепробаванных хэшей.

// перебор хэшей и проверка - удовлетворяет ли он условиям блокчейна
function mining($part, $last_hash, $start = 0, $limit = 30000) {
    $finish = $start + $limit;

    while($start < $finish) {
        if ($part > 9) {
            echo 'Blockchain full<br />';
            break;
        }
        $start++;

        //формируем случайный хэш
        $hash = generateMiningHash();

        //хэшируем последний хэш и свежесформированный
        $new_hash = hash('sha256', $last_hash . $hash);

        //проверяем - удовлетворяет ли сформированный хэш условиям блокчейна
        $check = checkHash($new_hash, $part);

        if ($check == true) {
            // блок найден
            echo 'Block found<br />';
            echo '$hash = ' . $hash .'<br>';
            echo '$new_hash = ' . $new_hash .'<br>';
            // сохраняем в таблицу
            insertMinedBlock($hash, $start);
            echo '<meta http-equiv="refresh" content="1;?start=0">';
            break;
        } else {
            //блок не найден
            echo '<meta http-equiv="refresh" content="1;?start=' . $start . '">';
        }
    }
    echo 'Checked ' . $start . ' hashes';
}

Листинг mining.php

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

include_once './config.php';
include_once './mining_functions.php';

//тянем hash и id последнего блока. считаем "часть" блоков
$last_block_data = getLastBlock();

$last_hash = $last_block_data['last_hash'];
$last_block_id = $last_block_data['last_block_id'];
$part = $last_block_data['part'];

$start = 0;
if (!empty($_GET['start'])) {
    $start = (int) $_GET['start'];
}
//перебираем по 30000 хэшей за раз
mining($part, $last_hash, $start,30000);

Листинг mining_verify.php

Проверяем корректность хэшэй блоков.

include_once './config.php';
include_once './mining_functions.php';

$sql = "select * from `mining` order by id asc";
$sth = $db->prepare($sql);
$sth->execute();
$res = $sth->fetchAll();
$last_hash = '';
foreach ($res as $block) {
    $part = (int)(($block['id'] + 9) / 10);
    $check_hash = hash('sha256', $last_hash . $block['hash']);

    //проверяем - удовлетворяет ли сформированный хэш условиям блокчейна
    $check = checkHash($check_hash, $part);

    if ($check == true) {
        echo 'Block ' . $block['id'].' ok<br>';
    } else {
        echo 'Block ' . $block['id'].' fail<br>';
    }

    //"сохраняем" в памяти хэш предыдущего блока
    $last_hash = $block['hash'];
}

Что в итоге получилось у меня

Я "намайнил" 74 блока :)
На самый "сложный" блок потребовалось 52 272 634 переборов. Блок из первой "части" угадал даже с первого раза.

Статистика переборов первых 60 блоков


https://i.imgur.com/t30aAsN.png
Как видите, зависимость номера блока от сложности "не плавная", а скачками меняется каждые 10 блоков.

Статистика переборов блоков с 1 по 74


https://i.imgur.com/rwlEIbN.png

Скачать код

Весь код(вместе с первым уроком) архивом (в архиве есть дамп с 74 намайненными блоками)

Код на gist.github.com - первый урок

Код на gist.github.com - только этот урок

Вывод

Незнаю как вы, а я стал чуточку лучше понимать что такое блокчейн. Если что-то недорассказал или непонятно - спрашивайте. Критика так же приветствуется. Надеюсь в терминологии не сильно ошибся.
В дальнейшем я придумаю более "плавное" усложнение алгоритма и с ним уже проверну майнинг на примере нескольких майнеров, майнящих в пуле. @p2psynergy, @captain - так же в следующих материалах будет "алгоритм консенсуса" и "алгоритма согласования хэшей между нодами"

Ещё раз спасибо @golosmedia за наводку на исходный материал.

vox-populiоткрытый-кодблокчейнпрограммированиеpsk
189
154.155 GOLOS
0
В избранное
Web Development
Тех, кто презирает программистов, программисты презирают сильнее, чем те, кто презирает тех программистов, которые презирают тех, кто их презирает.
189
0

Зарегистрируйтесь, чтобы проголосовать за пост или написать комментарий

Авторы получают вознаграждение, когда пользователи голосуют за их посты. Голосующие читатели также получают вознаграждение за свои голоса.

Зарегистрироваться
Комментарии (8)
Сортировать по:
Сначала старые