Привет, Хабр! Представляю вашему вниманию перевод статьи "Building Blockchain in Go. Part 2: Proof-of-Work".

Содержание

Blockchain на Go. Часть 1: Прототип
Blockchain на Go. Часть 2: Proof-of-Work
Blockchain на Go. Часть 3: Постоянная память и интерфейс командной строки
Blockchain на Go. Часть 4: Транзакции, часть 1
Blockchain на Go. Часть 5: Адреса
Blockchain на Go. Часть 6: Транзакции, часть 2
Blockchain на Go. Часть 7: Сеть

Вступление

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

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

Proof-of-Work(PoW)

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

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

Этот весь «сделай сложную работу и докажи её»-механизм называется Proof-of-Work (доказательство работы). Он сложен, потому что требует больших вычислительных мощностей: даже высокопроизводительные компьютеры не могут его быстро выполнить. Более того, сложность данной работы постепенно возрастает, для того чтобы в среднем создавалось около 6 блоков в час. В Биткоине цель такой работы — это нахождение хеша блока, который удовлетворяет определенным требованиям. Данный хеш и служит доказательством. Таким образом, поиск доказательства и есть фактическая работа.

Необходимо заметить одну вещь: Proof-of-Work алгоритмы должны соответствовать следующему требованию: выполнение работы должно быть сложным, но проверка доказательства должна быть простой. Проверка доказательства обычно передается кому-то стороннему, поэтому у них данная проверка не должна занимать много времени.

Хеширование

Данная часть посвящена хешированию. Те, кто знаком с этой концепцией, может данную часть пропустить.

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

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

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

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

Hashcash

Биткоин использует Hashcash, Proof-of-Work алгоритм, который был разработан для защиты от почтового спама. Алгоритм может быть разделен на следующие шаги:

Взять публично известные данные ( для эмейла — это адрес получателя; для биткоина — это заголовок блока
Добавить к ним счетчик. Счетчик начинается с нуля
Получить хеш от комбинации данные+счетчик
Проверить, отвечает ли хеш определенным требованиям
1. Если да, то все готово
2. Если нет, то увеличить счетчик и повторить шаги 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

Blockchain на Go. Часть 2: Proof-of-Work