Пишем свой блокчейн. Майнинг
В прошлом материале я рассказывал как хранить данные в формате блокчейна. Сейчас рассмотрим алгоритм майнинга.
Вводная
Как и в прошлый раз - рассмотрим именно принцип работы майнинга, без использования реальных блокчейнов.
Теперь в нашем блокчейне у каждого блока будет только номер и хэш.
Для реализации так-же будем использовать 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 за наводку на исходный материал.