Вступление
В предыдущей статье мы построили очень простую структуру данных, которая является основой для базы данных блокчейна. Также мы сделали добавление в нее блоков с цепной связью между ними: каждый блок связан с предыдущим. Увы, наша реализация блокчейна имеет один существенный недостаток: добавление блоков в цепочку слишком простое и дешевое.
Одним из краеугольных камней Биткоина и блокчейна является то, что добавление новых блоков должно быть достаточно сложной работой. И сейчас мы собираемся исправить этот недостаток.
Proof-of-Work(PoW)
Ключевая идея блокчейна заключается в том, что для добавления нового блока необходимо проделать некоторую сложную работу. Именно эта сложная работа делает блокчейн надежным и целостным. Кроме того, за эту сложную работу выплачивается вознаграждение (вот так люди получают монеты за майнинг).
Этот механизм похож на реальную жизнь: надо упорно работать, чтобы получать вознаграждения и обеспечивать себе жизнь. В блокчейне некоторые участники (майнеры) сети работают над поддержанием сети, добавлением в блокчейн новых блоков и получают вознаграждение за свою работу. В результате их работы блок встраивается в блокчейн надежным способом, что обеспечивает стабильность всей базы данных блокчейна. Стоит отметить, что тот, кто выполнил работу, должен также доказать её выполнение.
Этот весь «сделай сложную работу и докажи её»-механизм называется Proof-of-Work (доказательство работы). Он сложен, потому что требует больших вычислительных мощностей: даже высокопроизводительные компьютеры не могут его быстро выполнить. Более того, сложность данной работы постепенно возрастает, для того чтобы в среднем создавалось около 6 блоков в час. В Биткоине цель такой работы — это нахождение хеша блока, который удовлетворяет определенным требованиям. Данный хеш и служит доказательством. Таким образом, поиск доказательства и есть фактическая работа.
Необходимо заметить одну вещь: Proof-of-Work алгоритмы должны соответствовать следующему требованию: выполнение работы должно быть сложным, но проверка доказательства должна быть простой. Проверка доказательства обычно передается кому-то стороннему, поэтому у них данная проверка не должна занимать много времени.
Хеширование
Данная часть посвящена хешированию. Те, кто знаком с этой концепцией, может данную часть пропустить.
Хеширование — это процесс получения хеша для некоторых данных. Хеш — это уникальное представление для данных, для которых он был высчитан. Хеш-функция — это функция, которая для данных произвольного размера получает хеш конкретного размера. Некоторые ключевые особенности хеширования:
- Начальные данные не могут быть восстановлены из хеша. Таким образом, хеширование — это не шифрование
- Хеш для конкретных данных всегда однозначен и уникален
- Изменение одного байта в данных приводит к получению совершенно другого хеша
Функции хеширования широко применяются для проверки целостности данных. Многие поставщики софта публикуют вместе с софтом его контрольные суммы. После скачивания файла, его надо скормить хеш-функции, а затем сравнить полученный хеш с тем, что опубликовал разработчик софта.
В блокчейне хеш используется, чтобы гарантировать целостность блока. Входные данные для хеширующего алгоритма содержат хеш предыдущего блока, что делает невозможным (или, по крайней мере, очень сложным) изменение блока в цепи: придется пересчитывать хеш самого блока, а также хеши всех следующих за ним блоков.
Hashcash
Биткоин использует Hashcash, Proof-of-Work алгоритм, который был разработан для защиты от почтового спама. Алгоритм может быть разделен на следующие шаги:
- Взять публично известные данные ( для эмейла — это адрес получателя; для биткоина — это заголовок блока
- Добавить к ним счетчик. Счетчик начинается с нуля
- Получить хеш от комбинации
данные+счетчик
- Проверить, отвечает ли хеш определенным требованиям
- Если да, то все готово
- Если нет, то увеличить счетчик и повторить шаги 3 и 4
Таким образом, это брутфорс алгоритм: изменить счетчик, вычислить хеш, проверить его, увеличить счетчик, снова вычислить хеш и так далее. Именно поэтому алгоритм вычислительно затратный.
Теперь рассмотрим требования, которым должен удовлетворять хеш. В оригинальной Hashcash реализации требование звучит как «первые 20 бит хеша должны быть нулевыми». В Биткоине требование время от времени корректируется, потому что по замыслу блок должен генерироваться каждые 10 минут, несмотря на то, что мощность вычислений растет со временем и все больше и больше майнеров присоединяются к сети.
Для демонстрации алгоритма, возьмем предыдущий пример («I like donuts») и найдем хеш, который начинается с трех нулевых байтов.
ca07ca
— это шестнадцатеричное представления счетчика, что соответствует числу 13240266 в десятичной системе счисления.
Реализация
Итак, с теорией покончено, приступим к коду. Для начала определим сложность майнинга:
const targetBits = 24
В Биткоине, «target bits» — это поле заголовка блока, которое хранит сложность, на которой блок был добыт. Мы не будем строить корректирующийся алгоритм, поэтому определим сложность, как глобальную константу.
24 — это произвольное число, наша цель — это иметь сложность, которая занимает менее 256 бит в памяти. И мы хотим, чтобы разница была достаточно значительной, но не слишком большой, потому что, чем больше разница, тем труднее найти правильный хеш.
type ProofOfWork struct {
block *Block
target *big.Int
}
func NewProofOfWork(b *Block) *ProofOfWork {
target := big.NewInt(1)
target.Lsh(target, uint(256-targetBits))
pow := &ProofOfWork{b, target}
return pow
}
Здесь мы создаем создаем
ProofOfWork
, которая содержит указатель на указатель на блок и указатель на цель. «Цель» — это другое имя для требований, описанных в предыдущей части. Мы используем big integer из-за способа сравнения хеша с целью: мы ковертируем хеш в big integer и проверить, меньше ли оно, чем цель.В функции
NewProofOfWork
мы проинициализируем big.Int
значением 1, а потом сдвинуть на 256-targetBits
битов. 256
— это длина SHA-256 хеша в битах, и данный алгоритм хеширования мы будем использовать. 16-ричное представление target
:
0x10000000000000000000000000000000000000000000000000000000000
И оно занимает 29 байтов в памяти. А здесь визуальное сравнение с хешами из предыдущих примеров:
0fac49161af82ed938add1d8725835cc123a1a87b1b196488360e58d4bfb51e3
0000010000000000000000000000000000000000000000000000000000000000
0000008b0f41ec78bab747864db66bcb9fb89920ee75f43fdaaeb5544f7f76ca
Первый хеш( подсчитан для «I like donuts») больше, чем цель, так что это неверное доказательство работы. Второй хеш ( подсчитан для «I like donutsca07ca») меньше цели, так что это верное доказательство.
Можно считать цель как верхнюю границу диапазона: если число ( хеш) меньше, чем граница, то оно подходит, и наоборот. Понижение границы приведет к уменьшению количества подходящих чисел, тем самым повышая сложность поиска подходящего.
Теперь нам нужны данные для хеширования. Давайте подготовим их:
func (pow *ProofOfWork) prepareData(nonce int) []byte {
data := bytes.Join(
[][]byte{
pow.block.PrevBlockHash,
pow.block.Data,
IntToHex(pow.block.Timestamp),
IntToHex(int64(targetBits)),
IntToHex(int64(nonce)),
},
[]byte{},
)
return data
}
Этот кусок кода достаточно простой. Мы просто объединяем поля блока с целью и «nonce».
nonce
— это счетчик из описания Hashcash, это такой криптографический термин.
Так, все приготовления выполнены. Теперь реализуем ядро Proof-of-Work алгоритма:
func (pow *ProofOfWork) Run() (int, []byte) {
var hashInt big.Int
var hash [32]byte
nonce := 0
fmt.Printf("Mining the block containing \"%s\"\n", pow.block.Data)
for nonce < maxNonce {
data := pow.prepareData(nonce)
hash = sha256.Sum256(data)
fmt.Printf("\r%x", hash)
hashInt.SetBytes(hash[:])
if hashInt.Cmp(pow.target) == -1 {
break
} else {
nonce++
}
}
fmt.Print("\n\n")
return nonce, hash[:]
}
Сначала мы инициализируем переменные.
hashInt
— это целочисленное представление для hash
. nonce
— это счетчик. Затем мы запускаем «бесконечный» цикл: он ограничен константой maxNonce
, значение которой равно math.MaxInt64
. Это сделано, чтобы избежать возможное переполнение nonce
. Хотя сложность нашей PoW реализации слишком мала для переполнения счетчика, на всякий случай лучше иметь такую проверку.
В цикле мы делаем следующее:
- Подготовить данные
- Захешировать их Hash256
- Конвертировать хеш в big integer
- Сравнить полученное целое число с целью
Так же легко, как было объяснено ранее. Теперь можно удалить метод
SetHash
у Block
и изменить функцию NewBlock
:
func NewBlock(data string, prevBlockHash []byte) *Block {
block := &Block{time.Now().Unix(), []byte(data), prevBlockHash, []byte{}, 0}
pow := NewProofOfWork(block)
nonce, hash := pow.Run()
block.Hash = hash[:]
block.Nonce = nonce
return block
}
Можно заметить, что
nonce
сохранен как свойство Block
. Это необходимо, потому что nonce
требуется для проверки доказательства. Структура Block
теперь выглядит так:
type Block struct {
Timestamp int64
Data []byte
PrevBlockHash []byte
Hash []byte
Nonce int
}
А теперь запустим нашу программу и проверим, что все хорошо работает:
Mining the block containing "Genesis Block"
00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1
Mining the block containing "Send 1 BTC to Ivan"
00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804
Mining the block containing "Send 2 more BTC to Ivan"
000000b33185e927c9a989cc7d5aaaed739c56dad9fd9361dea558b9bfaf5fbe
Prev. hash:
Data: Genesis Block
Hash: 00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1
Prev. hash: 00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1
Data: Send 1 BTC to Ivan
Hash: 00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804
Prev. hash: 00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804
Data: Send 2 more BTC to Ivan
Hash: 000000b33185e927c9a989cc7d5aaaed739c56dad9fd9361dea558b9bfaf5fbe
Ура! Теперь можно заметить, что каждый хеш начинается с трех нулевых байтов и поиск хешей занимает некоторое время.
Осталось еще кое-что сделать: давайте сделаем возможной проверку доказательств работы:
func (pow *ProofOfWork) Validate() bool {
var hashInt big.Int
data := pow.prepareData(pow.block.Nonce)
hash := sha256.Sum256(data)
hashInt.SetBytes(hash[:])
isValid := hashInt.Cmp(pow.target) == -1
return isValid
}
Именно здесь нам понадобится сохраненная
nonce
.
Проверим, что все в порядке:
func main() {
...
for _, block := range bc.blocks {
...
pow := NewProofOfWork(block)
fmt.Printf("PoW: %s\n", strconv.FormatBool(pow.Validate()))
fmt.Println()
}
}
Output:
...
Prev. hash:
Data: Genesis Block
Hash: 00000093253acb814afb942e652a84a8f245069a67b5eaa709df8ac612075038
PoW: true
Prev. hash: 00000093253acb814afb942e652a84a8f245069a67b5eaa709df8ac612075038
Data: Send 1 BTC to Ivan
Hash: 0000003eeb3743ee42020e4a15262fd110a72823d804ce8e49643b5fd9d1062b
PoW: true
Prev. hash: 0000003eeb3743ee42020e4a15262fd110a72823d804ce8e49643b5fd9d1062b
Data: Send 2 more BTC to Ivan
Hash: 000000e42afddf57a3daa11b43b2e0923f23e894f96d1f24bfd9b8d2d494c57a
PoW: true
Заключение
Наш блокчейн еще на шаг ближе к актуальной архитектуре: добавление блоков требует вычислительной работы, поэтому возможен майнинг. Но в нем по-прежнему отсутствуют некоторые важные функции: база данных блокчейна не является постоянной, нет кошельков, адресов, транзакций и нет механизма консесуса. Все эти вещи мы рассмотрим вследующих статьях.
Ссылки
Первая часть
Оригинальная статья
Исходные коды для статьи
Алгоритм хеширования блокчейна
Proof of Work
Hashcash
Комментариев нет:
Отправить комментарий