BLAKE3 (надеюсь доступно)

Чуток поковырялся с хеш алгоритмом BLAKE3.

Интересный хеш. Криптографически стойкий (пока не доказана эффективность но и обратного тоже нет). Но быстрее SHA-256, SHA-512, SHA1 и даже MD5.

Из полезного.

0. Очень быстрый алгоритм.
Операции проводятся над 32-битными целыми числами без знака.
Используются только операции:
ADD сложение "+",
XOR исключающее-или "^",
ROR циклический сдвиг ">>",
операция перемешивания слов по фиксированной таблице (всего 16 значений).

Всё это сопровождается весьма малым числом раундов (всего 7).

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

В итоге всё очень хорошо укладывается в целочисленные операции SIMD современных процессоров и их кеш память.

Но и этого разработчикам показалось мало, так как алгоритм ещё и практически неограниченно распараллеливается из-за использования бинарного дерева Меркла (блоками по 1024 байта).

1. Произвольная длина хеша. От 256 бит (32 байта) до... вам по пояс будет. Де-факто можно использовать как генератор псевдослучайных чисел - причём очень быстрого (см. п.0) блоками по 64 байта. Остаётся маленький шажок до шифрования.

2. Встроенные алгоритмы деривации (наследования) ключей KDF и MAK. Кому это надо - знают зачем. См. п.0. Фактически проводится стандартные раунды хеширования, меняются только флаги (и/или используется хеш ключевого материала в поле CV вместо IV).

3. При хранении значений бинарного дерева произвольного уровня можно не пересчитывать весь хеш заново (при отсутствии изменений внутри некоторых блоков(. Похоже на то, что используется в BitTorrent (там считается и хранится SHA1 хеш каждого блока отдельно), TTH и AICH. Но в отличии от них - хеши одинаковых блоков будут разными, если они находятся по разным смещениям (внутри блока состояния, участвующего в вычислении хеша есть меняющийся счётчик 1024-байтных блоков-чанков).

Ещё раз - алгоритм ОЧЕНЬ быстрый. Быстрее даже MD5. Авторы обещают, что большая длинна хеша важнее количества раундов - и алгоритм пройдёт инспекцию криптоаналитиков.
Очень на это надеюсь. И думаю что за алгоритмом есть хорошее будущее.

== tldr; BEGIN ==

Из плохого. Рефренная реализация на языке rust. Быстрая SIMD реализация b3sum и библиотека blake3 - на языке rust. Готовых модулей Perl пока нет. Встречались реализации на других языках (C#/Blake3.NET .NET 5.0 wtf), но они использовали внешнюю библиотеку blake3 на rust.

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

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

Установка среды rust, настройка окружения, первая сборка. Копание в библиотеке blake3. Первый println! внутри функции компрессии. И до готового решения (очень пока грязного - не нашёл способа как потокобезопасно передавать открытые файлы вглубь функций, которые делают параллельные вычисления) чтобы b3sum выдала в mailslot на perl дерево Меркла блоков файла (который кладёт это дерево в sqlite базу). Переписывание библиотеки Win32::Mailslot - понимание того, что я не знаю perl xs и не знаю как её поправить чтобы понимала строки с нулями. Как использовать функцию newSVpn если нет нормальных примеров а автор Mailslot про неё вообще не знал (он честно сказал что это его первый подход к XS - и судя по коду он нормально знал только msvc). Неспроста этого модуля нет в cpan. Но тут вспомнил про Win32API::File - спасибо автору за чистый и понятный код, который я уже когда-то даже правил (очень нужная мне в моей считалке хешей функция SetEndOfFile).

И в итоге b3sum уделывает мою старую считалку стоя и в рост (которую, как я думал, ограничивает лишь производительность диска) - даже с чудовищно вкряченным и отвратительным решением, с тремя переходами на unsafe код и обратно, открывающим и закрывающим mailslot на каждый чих расчёта суммы блока дерева.

== tldr; END ==

Итак. Алгоритм BLAKE3.

Используемые обозначения:
блок - 64 байта, обработка хешируемых данных идёт такими "кусочками". Может быть меньше, если входных данных не хватает - тогда недостающая часть заполняется нулями до 64 байт.
чанк - 1024 байта (1 килобайт или по рекомендациям МЭК кибибайт 1 КиБ или KiB) - набор из 16 блоков по 64 байта. Может быть меньше (до 1), если блоков не хватает. Используется для "нулевого" уровня дерева Меркла - хеши чанков попарно объединяются для получения корневого хеша.
u8/u32/u64 - беззнаковые целые, соответственно 8 бит (байт), 32 бита (двойное слово, DWORD), 64 бита (unsigned long, QWORD).

1. IV инициализационный вектор - 256 бит или 8 u32.
Он используется много где - гугл даёт ссылки на него же в SHA256 и BitCoin - пишут это набор первых 32 бит дробной части (иррациональных) квадратных корней простых чисел по возрастанию: 2, 3, 5, 7, 11, 13, 17, 23):

67e6096a85ae67bb72f36e3c3af54fa57f520e518c68059babd9831f19cde05b

Ну или как он же записан как u32 в шестнадцатеричном виде:

const IV: [u32; 8] = [
  0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A,
  0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19,
];

Он используется как ключ (первые 4 u32 - кроме случаев MAK и KDF) и как начальный CV каждого чанка (все 8 слов).

2. Функция компрессии compress.

На вход подаются:

    $block_words,    # [u32; 16]
    $chaining_value, # [u32; 8]
    $counter,        # u64
    $block_len,      # u32
    $flags,          # u8

block_words - блок хешируемых данных (512 бит / 64 байт / 16 u32).
Zero filled: если данных не достаточно (менее 64 байт), остаток блока заполняется нулями до 64 байт. Пустой блок соответственно 64 нулевых байта.

chaining_value - значение хеша предыдущего 64-байтного блока (256 бит / 8 u32).
Сюда же подсовывается IV для первого блока или хеш ключа для HMAK/KDF.

counter - счётчик 1024-байтных чанков (chunks, тут используются как блоки дерева Меркла) (64 бита / 1 u64). Для цепочки из 64-байтных блоков внутри одного чанка этот счётчик не изменяется. Для компрессии пар хешей (с флагом "PARENT") тут ставят ноль. Для получения "продолжения" корневого (выходного) хеша - используется как инкрементный счётчик.

block_len - длина блока данных (block_words) в байтах. Отведено 32 бита, но размер блока ограничен числом 64 (0x40). Компрессия пар хешей в дереве Меркла - 2 хеша по 32 байта итого те же 64 байта. Если обрабатывается "хвост" файла (или сам файл короткий) - может быть число меньше 64 (вплоть до 0 для пустого блока).

flags - тоже расширяется до 32 бит, но в алгоритме сейчас используются только 7 бит.

Возможные значения и назначения битовых полей flags (константы):

CHUNK_START 1 << 0 (x01)

        начальный блок чанка

CHUNK_END 1 << 1 (x02)

        конечный блок чанка

PARENT         1 << 2 (x04)

        признак компрессии хешей в дереве меркла

ROOT         1 << 3 (x08)

        выходной "корневой" узел (получение итогового хеша)

KEYED_HASH 1 << 4 (x10)

        признак KDF (вместо IV для CV берётся хеш ключа)

DERIVE_KEY_CONTEXT  1 << 5 (x20)

        признак HMAK (вместо IV для CV берётся хеш статического ключа)

DERIVE_KEY_MATERIAL 1 << 6 (x40)

        хеширование ключа для HMAK/KDF

Флаги объединяются по ИЛИ. Например для короткого чанка (до 64 байт):
    CHUNK_START | CHUNK_END  = x03
Если это окажется ещё и выходной хеш (для короткого или пустого файла):
    CHUNK_START | CHUNK_END | ROOT = x0B

Функция компрессии собирает из входных значений блок внутреннего состояния (state) и он будет модифицироваться функцией g на основе хешируемых данных (block_words). Сами данные перемешиваются функцией permute между раундами хеширования.

Размер блока state тот же, что и блок данных - 64 байта или 16 DWORD.

CVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCV

IVIVIVIVIVIVIVIVIVIVIVIVIVIVIVIVCCCCCCCCCCCCCCCCSSSSSSSSFLFLFLFL

CV - хеш предыдущего блока chaining_value,

IV - "ключ" хеша - первые 4 слова IV,

CC - счётчик чанков counter (u64),

SS - размер блока данных block_len (0-64),

FL - флаги блока flags

Для примера, вот state начального блока нулевого чанка файла:

67e6096a85ae67bb72f36e3c3af54fa57f520e518c68059babd9831f19cde05b

67e6096a85ae67bb72f36e3c3af54fa500000000000000004000000001000000

CV=IV, CC=0, SS=x40 (64 байта), FL=01 (CHUNK_START)

Затем блок state подвергается 7 одинаковым раундам компрессии с последующим перемешиванием входных данных block:

    round(&mut state, &block); // round 1

    permute(&mut block);

    round(&mut state, &block); // round 2

    permute(&mut block);

    round(&mut state, &block); // round 3

    permute(&mut block);

    round(&mut state, &block); // round 4

    permute(&mut block);

    round(&mut state, &block); // round 5

    permute(&mut block);

    round(&mut state, &block); // round 6

    permute(&mut block);

    round(&mut state, &block); // round 7

Старшие 8 слов state накладываются (через XOR) на младшие 8 слов state и результат используется в дальнейшем как "промежуточный" 256-битный хеш блока, а на старшие 8 слов (тоже через XOR) накладывается входной хеш CV (чтобы сформировать очередной 64 байтный кусок выходного хеша).

Отсутствие необходимости накладывать и хранить входной хеш CV на "старшие" 32 байта выходного хеша и даёт разделение "оптимизированных" алгоритмов на похожие внешне функции compress_inplace (меняет входной массив CV на выходной хеш и ничего не возвращает) и compress_xof (возвращает 64 байта "полного" хеша но не трогает входной хеш).

Для полноты картины приведу все три "внутренних функции": g, round, permute.

// The mixing function, G, which mixes either a column or a diagonal.

fn g(state: &mut [u32; 16],

    a: usize, b: usize, c: usize, d: usize, mx: u32, my: u32) {

    state[a] = state[a] + state[b] + mx;

    state[d] = rotr32(state[d] ^ state[a], 16);

    state[c] = state[c] + state[d];

    state[b] = rotr32(state[b] ^ state[c], 12);

    state[a] = state[a] + state[b] + my;

    state[d] = rotr32(state[d] ^ state[a], 8);

    state[c] = state[c] + state[d];

    state[b] = rotr32(state[b] ^ state[c], 7);

}

fn round(state: &mut [u32; 16], m: &[u32; 16]) {

    // Mix the columns.

    g(state, 0, 4,  8, 12, m[0], m[1]);

    g(state, 1, 5,  9, 13, m[2], m[3]);

    g(state, 2, 6, 10, 14, m[4], m[5]);

    g(state, 3, 7, 11, 15, m[6], m[7]);

    // Mix the diagonals.

    g(state, 0, 5, 10, 15, m[8], m[9]);

    g(state, 1, 6, 11, 12, m[10], m[11]);

    g(state, 2, 7,  8, 13, m[12], m[13]);

    g(state, 3, 4,  9, 14, m[14], m[15]);

}

const MSG_PERMUTATION: [usize; 16] =

[2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8];

fn permute(m: &mut [u32; 16]) {

    let mut permuted = [0; 16];

    for i in 0..16 {

        permuted[i] = m[MSG_PERMUTATION[i]];

    }

    *m = permuted;

}

Необходимые примечания:
Все операции проводят над беззнаковыми целыми 32-битными числами u32.

Сложение в функции g допускает переполнение данных - следует это игнорировать. Если компилятор языка программирования пытается как-то обработать это событие (как rust) приходится использовать обработчик, например: a.wrapping_add(b).wrapping_add(с);.

Циклический сдвиг вправо rotr32 часто реализуется в железе процессоров, но в языках программирования обычно приходится его имитировать:

rotr32($w, $c) {

    return ($w >> $c) | ($w << (32 - $c))

}

У rust есть w.rotate_right(c), но без знания языка думаю проще так, как я привёл в алгоритме.
Работающую реализацию для rust берите из рефрена.

2. Работа алгоритма.

Для примера - файл из 4 КиБ нулей.

Чанк 0:

Блок 0:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s67e6096a85ae67bb72f36e3c3af54fa57f520e518c68059babd9831f19cde05b67e6096a85ae67bb72f36e3c3af54fa500000000000000004000000001000000

=9231a599f35b97d564eb5fdfa8ff50b7387df3bba731d079a2bdfc062c391746

В поле CV=IV, flag=01 (CHUNK_START). CC=0, SS=64. Результат уходит в CV следующего блока.

Блок 1:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s9231a599f35b97d564eb5fdfa8ff50b7387df3bba731d079a2bdfc062c39174667e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=51df97ebd73fca0cbdb54464751250262e10e08821594a95a733d850472be538

В поле CV перешло значение хеша предыдущего блока, flag=00 (нет флагов - это ни начальный блок, ни конечный блок). CC=0, SS=64. Результат уходит в следующий блок.

Блок 2:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s51df97ebd73fca0cbdb54464751250262e10e08821594a95a733d850472be53867e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=c96ad7d259f51db5a0a588aa0dccb1aefc96ed2be293492ee57cb9af3dce3fcb

Блок 3:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sc96ad7d259f51db5a0a588aa0dccb1aefc96ed2be293492ee57cb9af3dce3fcb67e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=dc31895819eb00eff3ce2fe529ec6b62e82235af29a3079c4d6973e859d47f29

Блок 4:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sdc31895819eb00eff3ce2fe529ec6b62e82235af29a3079c4d6973e859d47f2967e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=d33a742003892cace13957e2aa6e62678e217d02d1cfab903df7497f1547a339

Блок 5:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sd33a742003892cace13957e2aa6e62678e217d02d1cfab903df7497f1547a33967e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=cb8e7ad10ab1278aa325c60fdc80cb08dd6817fcebaf6d8d530dacf465d391af

Блок 6:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

scb8e7ad10ab1278aa325c60fdc80cb08dd6817fcebaf6d8d530dacf465d391af67e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=55f4038fbe2a8a69c82bc85921eb13383ece3a00efbb55e094c7de109a32a06b

Блок 7:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s55f4038fbe2a8a69c82bc85921eb13383ece3a00efbb55e094c7de109a32a06b67e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=cdccced87c71be1ddce70a516d4e7fe999db28a305dd24ec000df3b9814f06be

Блок 8:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

scdccced87c71be1ddce70a516d4e7fe999db28a305dd24ec000df3b9814f06be67e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=1fd462eceb0f82406066ade50b951b1e6444e0d29bcd52ebea1dafcd7187e641

Блок 9:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s1fd462eceb0f82406066ade50b951b1e6444e0d29bcd52ebea1dafcd7187e64167e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=c42e11b60b4990b7a98d51413e45c2b0975fb169744a1e140ae269e55f9b4762

Блок 10:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sc42e11b60b4990b7a98d51413e45c2b0975fb169744a1e140ae269e55f9b476267e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=7c27dde46486e97ed86b80fd0dc006d069aeef9fc2e59fe7decbf28d21a15ec8

Блок 11:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s7c27dde46486e97ed86b80fd0dc006d069aeef9fc2e59fe7decbf28d21a15ec867e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=73fbc93b838ed503ff81772684f5006e3ddd3ce5328404ce9dd091c4118abd78

Блок 12:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s73fbc93b838ed503ff81772684f5006e3ddd3ce5328404ce9dd091c4118abd7867e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=33d13f301543053763674eac769711fbbe2a2ade5ab40ce6b8ff1e5cd086175e

Блок 13:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s33d13f301543053763674eac769711fbbe2a2ade5ab40ce6b8ff1e5cd086175e67e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=c0f0286d206316ed8390232eaa002265703739d896b6f6ba68eb8b4401253529

Блок 14:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sc0f0286d206316ed8390232eaa002265703739d896b6f6ba68eb8b440125352967e6096a85ae67bb72f36e3c3af54fa500000000000000004000000000000000

=4d40bcb0ea55c14046ccb2966abc2ce83f6ff41d319b350da0dd1e2128ed9e55

Блок 15:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s4d40bcb0ea55c14046ccb2966abc2ce83f6ff41d319b350da0dd1e2128ed9e5567e6096a85ae67bb72f36e3c3af54fa500000000000000004000000002000000

=91715ad631c858232d522cc2ff678052288c8c540fc6ab6c5fa5104cb63e0d39

Последний 15 блок чанка 0. flag=02 (CHUNK_END). CC=0, SS=64. Результат - хеш чанка 0 запоминаем его в стеке дерева хешей.

 

Чанк 1:

Блок 16:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s67e6096a85ae67bb72f36e3c3af54fa57f520e518c68059babd9831f19cde05b67e6096a85ae67bb72f36e3c3af54fa501000000000000004000000001000000

=add617a39b1369d50c193577d7dd35155bbfc02569dfc87a9703447110197222

В поле CV снова IV, flag=01 (CHUNK_START). Теперь CC=1, SS=64. Результат уходит в CV следующего блока.

Блок 17:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sadd617a39b1369d50c193577d7dd35155bbfc02569dfc87a970344711019722267e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=358744d9a4600e85e639961a8058462acd4b000f66f1839692a08267d66e78fc

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s358744d9a4600e85e639961a8058462acd4b000f66f1839692a08267d66e78fc67e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=64d3367323e28e75c4cd3c5ca96c2ac36b5636fcd7a370e4769a964907ace752

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s64d3367323e28e75c4cd3c5ca96c2ac36b5636fcd7a370e4769a964907ace75267e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=dab384f0e7dec7573af7b10afa61c4678993fd6264d246fdca09d8ced61c2049

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sdab384f0e7dec7573af7b10afa61c4678993fd6264d246fdca09d8ced61c204967e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=ce358e6066c6790b3d7c9651875884d9ac4e2ceb88245c4ca0d13a04609d9104

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sce358e6066c6790b3d7c9651875884d9ac4e2ceb88245c4ca0d13a04609d910467e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=10e36eb93988e638b53e695d10bd8ee62fe00e800266140f6ed6d7ad793d4819

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s10e36eb93988e638b53e695d10bd8ee62fe00e800266140f6ed6d7ad793d481967e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=5d6d24cabaf7592c136ad1c3b741da309cfdb170ae1f56d7ab73c03999122823

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s5d6d24cabaf7592c136ad1c3b741da309cfdb170ae1f56d7ab73c0399912282367e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=1b45267e4479190c15ec38885f556c8d797eb4a06bb1690226e752c3deb76ad7

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s1b45267e4479190c15ec38885f556c8d797eb4a06bb1690226e752c3deb76ad767e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=02e013f1ee88abc5707c5b7e48a65d208a9c80ba7f8eeb8c848d69cd24cd83e6

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s02e013f1ee88abc5707c5b7e48a65d208a9c80ba7f8eeb8c848d69cd24cd83e667e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=bc25b0862aaf09c0ea9a7e06b8de2de4f8042d62ed8d5fd0d735f55ae7e78877

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sbc25b0862aaf09c0ea9a7e06b8de2de4f8042d62ed8d5fd0d735f55ae7e7887767e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=e69759670ca133f45e71b53eb10893bc599c2f0b7a9ec234e6aeedb99cb42d9e

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

se69759670ca133f45e71b53eb10893bc599c2f0b7a9ec234e6aeedb99cb42d9e67e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=17e96554e91e4672088c54cb8cda9e4bef0d6eb03aca535e47320bdf3c4fa623

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s17e96554e91e4672088c54cb8cda9e4bef0d6eb03aca535e47320bdf3c4fa62367e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=c74b056bea8f62c3c3666d9964a3dde21bac2050a1d7efb84df5f0a40fc75fe6

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sc74b056bea8f62c3c3666d9964a3dde21bac2050a1d7efb84df5f0a40fc75fe667e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=ab342e114522c87a27e5dbb4c5e764b5833587234d08d43de7a157a3b75dbfe4

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sab342e114522c87a27e5dbb4c5e764b5833587234d08d43de7a157a3b75dbfe467e6096a85ae67bb72f36e3c3af54fa501000000000000004000000000000000

=8b57c6d0da0f861c83e9dc199f943ebfb53b55817df4f821405373fff2e44381

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s8b57c6d0da0f861c83e9dc199f943ebfb53b55817df4f821405373fff2e4438167e6096a85ae67bb72f36e3c3af54fa501000000000000004000000002000000

=f0eef3b0033abb623278828fcc75f90c65bde353141ec7c6854eae1c515b93ca

Последний блок чанка CC=1. Видим flag=02 (CHUNK_END). Результат функции компрессии - хеш чанка. Помещаем его в стек. Видим в стеке два хеша уровня 0. Можем их сжать на первый уровень.

w91715ad631c858232d522cc2ff678052288c8c540fc6ab6c5fa5104cb63e0d39f0eef3b0033abb623278828fcc75f90c65bde353141ec7c6854eae1c515b93ca

s67e6096a85ae67bb72f36e3c3af54fa57f520e518c68059babd9831f19cde05b67e6096a85ae67bb72f36e3c3af54fa500000000000000004000000004000000

=a04fc7e7e6831a11965e686a56952b0830aadd1555beabcc79b8db5c93e680d3

В данные для сжатия помещаем два хеша - чанка 0 и чанка 1. CV=IV, CC=0, SS (block_len) = 32+32=64 (x40), flag=04 (PARENT). Результат опять помещаем в кеш, но уже уровень хеша 1. 

Чанк 2:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s67e6096a85ae67bb72f36e3c3af54fa57f520e518c68059babd9831f19cde05b67e6096a85ae67bb72f36e3c3af54fa502000000000000004000000001000000

=7f821a86de35c192613c3e103f382ef6a7df07230051086271bb994ff9c0ba39

Видим опять начало, flag=01, CV=IV, CC=2. Всё стандартно.

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s7f821a86de35c192613c3e103f382ef6a7df07230051086271bb994ff9c0ba3967e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=ebd2d22250f4f6d6e8d7b9fd4ae34beb988b756b5c87a4e7265fa920c0423164

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sebd2d22250f4f6d6e8d7b9fd4ae34beb988b756b5c87a4e7265fa920c042316467e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=05431ccfb5eed2fcdedc84e404d4d0024e54781848d483ee14c8f9bdde554dc6

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s05431ccfb5eed2fcdedc84e404d4d0024e54781848d483ee14c8f9bdde554dc667e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=f79e1f84c89f3f7e95ae8e31c6a1c04f326de78e5653959ac72ee4531060258a

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sf79e1f84c89f3f7e95ae8e31c6a1c04f326de78e5653959ac72ee4531060258a67e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=8c3ee51d6747319d72ad18708215c906bc26b1f90d1cde1eb4cd927e0de508c4

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s8c3ee51d6747319d72ad18708215c906bc26b1f90d1cde1eb4cd927e0de508c467e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=1e063b48476c20245fd23ab63065f9214e5b7ec50e8975ddbd6743a241ff4265

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s1e063b48476c20245fd23ab63065f9214e5b7ec50e8975ddbd6743a241ff426567e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=4d0f586ffa2249a1feb1fe0aed06dc70fe065c4c0ce15fab3236a9477deaf639

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s4d0f586ffa2249a1feb1fe0aed06dc70fe065c4c0ce15fab3236a9477deaf63967e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=698d5aa32a96b4898829718c52ed5715b55a0085caced06f5ff60af9ce688ae1

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s698d5aa32a96b4898829718c52ed5715b55a0085caced06f5ff60af9ce688ae167e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=7000ef9435bf8200074e600d473518eb67c37713f5b23ab61738accab34679a2

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s7000ef9435bf8200074e600d473518eb67c37713f5b23ab61738accab34679a267e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=c3eeef621f954007a33219b9a764ef12853b0565bf8a64bd70ccb9b4e9270707

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sc3eeef621f954007a33219b9a764ef12853b0565bf8a64bd70ccb9b4e927070767e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=9a8bda17191b163ecdad499b6a78d6df069cee3460ae152f40d1848079932ddb

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s9a8bda17191b163ecdad499b6a78d6df069cee3460ae152f40d1848079932ddb67e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=ab33a88ea4b17897e20d47b4196795de5b3e0a241b4d8c6058b4bf12fcc68a66

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sab33a88ea4b17897e20d47b4196795de5b3e0a241b4d8c6058b4bf12fcc68a6667e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=fbee852ea87041e006bc4711b1ee8f6ee867db6b0b7b3e718f143fa215da980f

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sfbee852ea87041e006bc4711b1ee8f6ee867db6b0b7b3e718f143fa215da980f67e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=6d442b7526ec31addc6ea4a9572c152a00b2618f148c819498db6ad6b3df4689

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s6d442b7526ec31addc6ea4a9572c152a00b2618f148c819498db6ad6b3df468967e6096a85ae67bb72f36e3c3af54fa502000000000000004000000000000000

=a933911631986c5bf5eb3d565b8272b7548f06c91243599228fe00a9364a1cdd

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sa933911631986c5bf5eb3d565b8272b7548f06c91243599228fe00a9364a1cdd67e6096a85ae67bb72f36e3c3af54fa502000000000000004000000002000000

=252ebfbe777d31bcfb3180109814eaccf5958ef2878c36bbe1415289dce2b88c

Конец чанка 2, flag=02, результат в кеш.

Чанк 3:

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s67e6096a85ae67bb72f36e3c3af54fa57f520e518c68059babd9831f19cde05b67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000001000000

=14c71b1e1990510bbe49818a62f0a3ee72ac490d314b5029bcac56e577eedcaf

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s14c71b1e1990510bbe49818a62f0a3ee72ac490d314b5029bcac56e577eedcaf67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=9e03744b1e18ec692bd94f3f0294f5fb430cfb02f6f3403db27318835c83ea8c

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s9e03744b1e18ec692bd94f3f0294f5fb430cfb02f6f3403db27318835c83ea8c67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=b2de534a865036900d6734d18c0598cb6d73e5e2f8625c2b4e82ce3623a0fa5e

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sb2de534a865036900d6734d18c0598cb6d73e5e2f8625c2b4e82ce3623a0fa5e67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=19d48611dc5fc81a813227ef8bf18f7ad3daedd6dc55f351bda1e6624d311536

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s19d48611dc5fc81a813227ef8bf18f7ad3daedd6dc55f351bda1e6624d31153667e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=b1f2b77ae67a7d343a6b9fe8038aac43a8abc7918734f2ee0d4c029df6d7fdf5

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

sb1f2b77ae67a7d343a6b9fe8038aac43a8abc7918734f2ee0d4c029df6d7fdf567e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=9572c6222251c613c911350ad6a389756658ee300f4cf39b514f6e2181a2f1b3

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s9572c6222251c613c911350ad6a389756658ee300f4cf39b514f6e2181a2f1b367e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=3dec0615ce2cd5b923e1b72bb65b5b772f9b38f2a9830dc785709c1ba6173bea

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s3dec0615ce2cd5b923e1b72bb65b5b772f9b38f2a9830dc785709c1ba6173bea67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=2b9098ee566fc965ea341b2d295f2e96239f5efa1c76e72823c488f6527cd3fe

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s2b9098ee566fc965ea341b2d295f2e96239f5efa1c76e72823c488f6527cd3fe67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=54c54d9be2c8a07abf78f5680d6595670fbab016c909c0584fb138eb0e6a046d

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s54c54d9be2c8a07abf78f5680d6595670fbab016c909c0584fb138eb0e6a046d67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=234e24b7027729a5012b0fb569addeee90fca6e2aacb2f372cef1a9132a4f90a

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s234e24b7027729a5012b0fb569addeee90fca6e2aacb2f372cef1a9132a4f90a67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=651d261375454b846f30c6fce47b97538b83838f21f0930e5b791cbc80ac0344

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s651d261375454b846f30c6fce47b97538b83838f21f0930e5b791cbc80ac034467e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=47076480adad22dbb3499bac0e49c4dbd54bedce127ddb95cbb5ba374f16a2cd

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s47076480adad22dbb3499bac0e49c4dbd54bedce127ddb95cbb5ba374f16a2cd67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=8c56a4205ada710a66652ad28565836dd3d91dbdaa6d8e8667bf93432a40003e

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s8c56a4205ada710a66652ad28565836dd3d91dbdaa6d8e8667bf93432a40003e67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=caaeee3b896bbfc03543304e8414db7663fbab11032da8d538e1faab4a052f4b

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

scaaeee3b896bbfc03543304e8414db7663fbab11032da8d538e1faab4a052f4b67e6096a85ae67bb72f36e3c3af54fa503000000000000004000000000000000

=127c8d909ba4c62c4806faf54d0025591764138686b9cbb1bdf9c5f62a0408b7

w00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

s127c8d909ba4c62c4806faf54d0025591764138686b9cbb1bdf9c5f62a0408b767e6096a85ae67bb72f36e3c3af54fa503000000000000004000000002000000

=48dc5df2fd74599ae870a2c1086d39fa117aa91084f0687c49c6439c90e31863

Конец чанка 3. flag=02. Хеш в стек и видим там снова два хеша нулевого уровня. Сжимаем.

w252ebfbe777d31bcfb3180109814eaccf5958ef2878c36bbe1415289dce2b88c48dc5df2fd74599ae870a2c1086d39fa117aa91084f0687c49c6439c90e31863

s67e6096a85ae67bb72f36e3c3af54fa57f520e518c68059babd9831f19cde05b67e6096a85ae67bb72f36e3c3af54fa500000000000000004000000004000000

=580f4b19f0952c41fccedc302ae73758cfa2ab094deead97b2c25b6f6829ecd1

Ещё одно сжатие хешей уровня 0. Данные - хеши чанка 2 и чанка 3. CV=IV, CC=0, flag=4 (PARENT).  Результат в стек и видим там два хеша 1 уровня. Сжимаем и их. Поскольку входные данные кончились и стек будет пуст - результат и будет наш корневой хеш.

wa04fc7e7e6831a11965e686a56952b0830aadd1555beabcc79b8db5c93e680d3580f4b19f0952c41fccedc302ae73758cfa2ab094deead97b2c25b6f6829ecd1

s67e6096a85ae67bb72f36e3c3af54fa57f520e518c68059babd9831f19cde05b67e6096a85ae67bb72f36e3c3af54fa50000000000000000400000000c000000

=b6fb73fc46938c981e2b0b4b1ef282adcfc89854d01bfe3972fdc4785b41b2c79a6b6935c6f03d4d7933b9e798a866fc32fa6138b1ab393ee073b3e568a81fa6

Вызываем функцию сжатия хеша. В данных - сжатые хеши уровня 1 чанков 0+1 и 2+3.  

Сжатие "корневое", так что в flags=0C (PARENT=4 | ROOT=8). Результат обрезаем до 32 байт:

b6fb73fc46938c981e2b0b4b1ef282adcfc89854d01bfe3972fdc4785b41b2c7

Это и есть итоговый 256 битный хеш BLAKE3.

Итог. На уровне чанков мы имеем такую картину:

LEVEL 0

CHUNK 0: 91715ad631c858232d522cc2ff678052288c8c540fc6ab6c5fa5104cb63e0d39

CHUNK 1: f0eef3b0033abb623278828fcc75f90c65bde353141ec7c6854eae1c515b93ca

CHUNK 2: 252ebfbe777d31bcfb3180109814eaccf5958ef2878c36bbe1415289dce2b88c

CHUNK 3: 48dc5df2fd74599ae870a2c1086d39fa117aa91084f0687c49c6439c90e31863

LEVEL 1

CHUNK0+1: a04fc7e7e6831a11965e686a56952b0830aadd1555beabcc79b8db5c93e680d3

CHUNK2+3: 580f4b19f0952c41fccedc302ae73758cfa2ab094deead97b2c25b6f6829ecd1

LEVEL 2

ROOT: b6fb73fc46938c981e2b0b4b1ef282adcfc89854d01bfe3972fdc4785b41b2c7

Если интересна тема, дам как меняется состояние при несбалансированном дереве, неполных чанках, MAK, KDF. Чуть позже.