> Поподробнее про критерий и расчёт блока. Удастся оба на O(1) сохранить?

А в чем проблема? Как-то так: блок это минимум {msg, hash, nonce}. Хэш считается как HASHFUNC(msg, nonce). Этот счет всегда O(1). Если совпало, проверяем критерий: если в хэше больше N leading zeros - окей, сохраняем это себе в базу. Это тоже O(1). Проверка pow дешевая операция в отличие от счета.

А как сложность выставлять? Скажем по соотношению размер vs желаемое время хранения vs душняк конкретного пира по доступности места. Если кто хочет большую простынку хранить да еще на толпе народа - пусть посчитает как следует. Не хочет? Тогда может считать поменьше и вылезать в сеть почаще, пересчитывая более легкий pow и заново сохраняя истекшее сообщение если ему это еще актуально. Это не учитывает некоторые детали типа трекинга древности сообщения, чтобы базы расчищать. И да, там не надо именно чейн - это же не про балансы кошелей.

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