# Побитная точность

Большой вызов в разработке формата или протокола - добиться идентичной обработки разными имплементациями (и разными версиями одной имплементации). Здесь, два моих любимых примера - JSON и Markdown. Оба формата очень просты; у Markdown нет формальной грамматики, но он интуитивно понятен; JSON же имеет формальную грамматику, которая умещается на визитке. Тем не менее, с совместимостью есть очень неожиданные проблемки.
Первый пример: Parsing JSON is a minefield, где автор не нашёл двух реализаций JSON, которые вели бы себя идентично https://seriot.ch/projects/parsing_json.html
Второй пример: CommonMark, попытка стандартизации Markdown, которая длится уже >7 лет, но новые нюансики всё находятся и находятся https://spec.commonmark.org
У обоих случаев есть простое комбинаторное объяснение.
С JSON фокус в том, что в разных его спецификациях есть маленькие разночтения и неточности. Допустим, у вас есть 10 разночтений - пусть самых простых, бинарных, true или false. Например, допустима ли trailing comma? Yes/No. В таком случае, у вас есть уже 2^10 = 1024 вариантов, как себя может вести парсер, оставаясь при этом совместимым со спецификацией. Из 1000 парсеров, может не найтись двух одинаковых!
С Markdown же другая заминка: там у каждого элемента свой синтаксис (а точнее, несколько синтаксисов). Та же звёздочка может быть частью списка, жирного текста, наклонного текста и вроде бы ещё чего-то, точно не помню, нужно проверить спеку. Поэтому, все эти синтаксические правила начинают взаимодействовать комбинаторно - в зависимости от других символов, пробелов, другой разметки. Поэтому, формальную грамматику для Markdown даже не получилось написать. Насколько совместимы реализации? Ну, насколько получилось, настолько и совместимы.
Как RON решает эти проблемки - в следующем тексте...

Тут меня спросили, используется ли RON в новой IDE от JetBrains.
Нет, совсем не используется, но поскольку спрашивают не в первый раз, почему бы не рассказать подробней. Итак, я действительно работал некоторое время в JB (в 2018), и более того, на внутренней конфе делал доклад как раз на эту тему - что IDE должно стать распределённым; и что если у нас есть распределённое CRDT хранилище, которое синхронизируется в реальном времени, то разные части системы могут работать на разных хостах. С упором на контроль версий в реальном времени. (Если кто-то знает, как найти видео доклада, подскажите.) Сразу скажу, что у JetBrains на тот момент было примерно три проекта так или иначе распределённого IDE, в одном из которых я и работал (datalore Костика). Еще были @jetzajac и Жемеров. Но это всё не так важно.
Я столкнулся с рядом проблем при разработке CRDT движка синхронизации и это на мне сказывалось. Но тут произошёл неожиданный сюрприз. Годом ранее я подавал заявку на исследовательский грант, и к сентябрю 2018 все колёса провернулись, я получил бабло. В довольно неплохом количестве. Но из JB меня попросили уйти. (1/4)

Короче, движок я доковырял весной 2019. Но обнаружился нежданчик, как всегда бывает. Я писал поверх LSMT базы данных RocksDB (C++). В таких БД есть операция merge, которую можно переопределять; определяем её в RON CRDT merge и радуемся жизни. В теории всё зашибок, можно тот же фокус проделать с LSMT Cassandra (Java) и будет распределённое хранилище. Очень красиво. Однако же, RocksDB оказалась очень сложным зверем и для нормального функционирования механизма, как оказалось, нужно ещё много её любить. Нарисовалось полгодика работы с кишками продуктовой БД facebook. С точки зрения будущего трудоустройства, конечно, неплохой вариант. Но всё равно, конструкция получалась неприлично сложной. У CRDT есть ряд свойств, который позволял сократить ряд слагаемых, и делать всё проще и надёжней. Одна проблемка - нужно писать этот движок с нуля. Что выберет упоротый? Конечно писать! Удивительно, но с 28 августа 2019 до 28 сентября я написал его в общих чертах и оно заработало. LSMT отправлялся в дупу. 2/4

В общем, за 2020 год я сделал Chronofold (статья и код), пару раз переписал движок, и поправил своё здоровье. В марте 2021 уже демку повесил на сервер, в наличии были RON store (тот движок без ненужных слагаемых) и игрушечная система контроля версий DaRWiN (на основе CRDT). Правда, разговор с JetBrains не получился, и я засел за третий перепис движка и одну статью, про которую я расскажу позже. DaRWiN получил пониженный приоритет, но я к нему вернусь. Чем же RON и DaRWiN так хороши? 3/4

RON позволяет распределённо работать со структурами данных (массивы, тексты, списки, словари) при ненадёжном интернете; local-first CRDT, всё мёржится. Это очень заманчивый субстрат для написания распределённых приложений. При этом, над RON определена криптография. Тот же git криптографию определяет по блобам; RON по операциям. Короче, это как паровоз и шинканшен. Про каждую операцию (в тексте - букву) известно, когда и откуда она пришла, кто подписал. Соответственно, апдейты могут литься в реальном времени, можно произвольно мержить и размерживать бранчи, итд. А поскольку оно realtime, его можно использовать прямо в редакторе для undo/redo, для совместной работы, итд. При этом оверхэды крайне небольшие, в докладе на HighLoad я рассказывал про некоторые фокусы. Блокчейн выглядит как каменный век по сравнению.
Сам RON довольно впрочем низкоуровневый. Примерно как WebAssembly для данных; так же есть текстовая и двоичная версии. При этом крипто считается от RONc - канонической двоичной версии, которая определена побитно (не мной, как правило). На этом уровне абстракции это нормально - two's complement INT, IEEE 754 FLOAT, UUID, UTF-8 STRING). Разработчик работает со структурой данных - допустим, текстом. Под ним chronofold, под ним RON, под ним просто поток бит. 4/4

Соответственно, побитная идентичность нетривиальных форматов - текстового RONt и сжатых двоичных RONv RONp - достигается через сюръективное отображение на канонический двоичный формат RONc, f(RONx)->RONc, и обратное инъективное g(RONc)->RONx. Причём, g(RONc)=RONx' и f(RONx')<->RONc это биекция. Так мы контролируем вольности форматов - компрессию двоичного, whitespace и пунктуацию текстового, итд. Короче, фактически это всё проверяется на корректность фаззингом (кольцевое преобразование). Так решаются проблемки типа JSON и Markdown - канонический формат лишен вольностей и побитно точен, остальные представления эквивалентны ему. Хэши считаем по каноническому формату, и дальше плетём любые криптографические сети. Текстовый формат определяем через формальную грамматику (спасибо, ragel) 5/4

заинтригован

Russ Cox тут твитнул интересное и внезапно оказалось, что моя работа над двоичными Меркелевыми деревьями (2009-2010), которая в результате стала RFC7574, вошла в DAT protocol и немножко в BitTorrent 2.0, очень сильно оверлапит с рядом современных ей и более поздних работ по криптографии
https://research.swtch.com/tlog
https://twitter.com/_rsc/status/1468260916902907914
А вот мой первый драфтик
https://datatracker.ietf.org/doc/html/draft-grishchenko-ppsp-swift-00

# Это называется credibility.

Если у меня есть 10 яблок, а у чувака из Google есть яблоко, то у чувака из Google больше яблок, и он изобрёл яблоки.
Если у меня есть 10 яблок, а у чувака из Оксфорда есть пол-яблока.... та же история.
Если я говорю непонятное - я псих; если чувак из Google говорит непонятное - он гений.
Ну и так далее...
С одной стороны, я привык. С другой стороны, я устал.

Сегодня день ностальгии, видимо; написал про мой rich text CRDT из 2012. https://github.com/gritzko/citrea-model/blob/master/story.md

Заодно нашёл, откуда есть пошёл RON: был у меня и язык запросов для версионированного текста в тот же период. Из CT и этого языка и вырос в результате RON.

# Rust

Неоднократно у меня возникал этот вопрос: писать на Rust или на C++? C++ я использую *очень* ограниченный, C++11 плюс пара забекпорченных фич из более поздних стандартов. Практически, это C с классами и шаблонами. И вот читаю я статью про внедрение Rust в Linux kernel и таки возникает у меня FOMO. Линус за Rust - говорит статья. Читаю чуть повнимательней и понимаю: Линус просто поработал над собой и теперь выражает свои сомнения в позитивном ключе. В духе "начните пока с чего-нибудь неважного, а через 10 лет поговорим".
Очевидные трудноразрешимые проблемы: сложность Rust, необходимость постоянной низкоуровневой работы в ядре, где особо не абстрагируешься, сопряжение с C кодом, отсутствие поддержки архитектур кроме Intel и ARM.
На мой взгляд, сложность кода может оказаться поважнее всего остального, в перспективе, и нивелировать выгоды от более строгой модели работы с памятью. Но результат будет понятен лет через k.
https://www.theregister.com/2021/11/10/where_rust_fits_into_linux/

# Разбор TON whitepaper

Для студентов разобрал TON whitepaper (блокчейн от не-Дурова); продублирую выводы здесь. Уязвимости порой находятся в коде, где казалось бы всё очень прямо и понятно (Diffie-Hellman logjam или на прошлой неделе log4j). А авторы предлагают реализацию трёхэтажного TON блокчейна с гиперкубическим раутингом, виртуальной машиной, цифровыми фонтанами и Kademlia DHT (да, всё сразу). Это имеет нулевую вероятность не только отсутствия уязвимостей, но и общей работоспособности.
Но динамика у whitepaper'а драматическая, конечно: сначала они предлагают крутой механизм... Но, есть маленькая очевидная проблемка. Тогда они предлагают добавить другой, часто более сложный, механизм, для её решения. Но... тут ещё проблемка... И эта история продолжается 120 страниц.
https://www.youtube.com/watch?v=L6DFGSY05IQ

# Консенсус

Классические алгоритмы консенсуса подразумевают ограниченный круг участников. Это предположение, в частности, перешло из классических работ 1980-х в современные Proof of Stake и Паксосы.
А что если нам нужно достичь консенсуса в рое, где точное количество участников и топология сети неизвестны? Как оказалось решение есть и оно очень интересное - консенсус Шмебюлока. О чём мы с Мишей и написали статью.
Удивительно, но в ходе работы мы обнаружили концепцию куда более мощную, чем время Лампорта - время роя. Это логическое время для массивно параллельных само-синхронизирующихся систем.
Кто осилит текст - будем рады отзывам.

https://arxiv.org/abs/2112.07065

чудо само-синхронизации роя (подробности в статье :)

Не очень грамотный обзор по Web 3.0 [1] от К.Сарханянца в Коммерсанте. Вот некоторые говорят, что нельзя журналистам давать что-то писать самим, потому что в чём они разбираются?
Попробую просуммировать эпический твиттер-срач последних двух недель и положение дел с "Web 3.0" в целом.
Центральный твиттер аккаунт в сраче - @kelseyhightower. Это вроде бы девопс в Гугле, большой influencer. Итак, он начал спрашивать в общем-то очевидные вещи относительно блокчейна и "Web 3.0" и поднял нешуточную волну. Включились и Grady Booch и Elon Musk и Jack Dorsey, только Elvis Presley почему-то молчал. Действительно, BitCoin-like блокчейн это принципиально немасштабируемая технология. То, что Джек Дорси - фанат именно BitCoin, это очень интересный факт. Упомянутый в статье "проект децентрализованных соцсетей Bluesky" - это просто одна приятная девушка, реальной работы там не происходит, только говорильня. Вообще, с инженерными успехами у Web 3 пока сложно. IPFS после 7 что ли лет разработки так толком и не используется. Я предлагал им пока выкинуть DHT в пользу Tiered Network [2] чтобы хоть что-то заработало. Поскрипели мозгами и стали искать, кто бы им сделал Tiered DHT. Не комментирую. Ethereum не то чтобы сильно лучше в плане масштабирования чем BitCoin, но там происходит всяческая движуха, по крайней мере. Про TON coin я уже высказывался. Вообще, эта блокчейн волна отличается очень шумным хайпом и очень маленьким выхлопом. Вот помню когда BitTorrent переехал на uTP/LEDBAT, до четверти траффика в интернете разом переключилось с TCP на UDP - а никто и не заметил. Прямая противоположность. Код вроде бы писали два человека - Шалунов и Норберг. Но возвратимся к чейнам. Вся эта тема мне напоминает диалог из фильма Sneakers (1992) [3].
"Not reality but the perception of reality" - это объяснение очень многого, что происходит.

[1]: https://www.kommersant.ru/doc/5152037
[2]: http://replicated.cc/netarch
[3]: https://www.youtube.com/watch?v=coDtzN6bXAM

Новый драфт Swarm consensus уже на arxiv:
https://arxiv.org/abs/2112.07065
Добавлено: Византизм, объяснение swarm time, диаграмма Минковского, многое другое.
P.S. HackerNews: https://news.ycombinator.com/item?id=29711381
Собрал все очевидные вопросы, осталось поправить текст.

Интересное мнение от ветерана Web 1.0, Web 2.0 и Web 3.0 Фреда Вилсона в общем близко к моему.
https://avc.com/2021/12/why-web3/

Полез искать новости про Казахстан, обнаружил, что Nexta не теряет времени даром - рекламируют NFT. https://t.me/nexta_live/15518

Поправьте меня, если я что-то не понимаю, но ведь если "добыча биткойна" в Казахстане остановится, биткойн должен подорожать? 😋