Как стать автором
Обновить
168
0
Александр Скиданов @SkidanovAlex

Системный Программист

Отправить сообщение

Нерешенные проблемы шардинга в блокчейне

Время на прочтение14 мин
Количество просмотров3.8K

Введение

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

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

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

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

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

Читать далее
Всего голосов 13: ↑13 и ↓0+13
Комментарии3

NEAR запустился! И теперь строить открытый и свободный интернет намного проще

Время на прочтение5 мин
Количество просмотров12K

Вчера произошел запуск NEAR, проекта, над которым я и мои коллеги работали последние 2 года.

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

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

Зачем нужны протоколы блокчейна

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

В краткосрочной перспективе это уже используется для построения финансовых сервисов, которые не контролируются банками и государствами. На Ethereum – самой популярной на сегодня платформе для децентрализованных приложений – за последние два года появилось огромное количество интересных финансовых сервисов: MakerDAO построили децентрализованную валюту, чья цена почти точно равна одному доллару, позволяя использовать финансовые сервисы на платформе с использованием неволатильных активов. Compound построили возможность класть деньги в их сервис, и получать почти гарантированный доход, Augur и Flux построили сервисы, на которых можно делать ставки на различные события в реальном мире. Помимо этого на Ethereum запущено большое количество различных децентрализованных бирж. Все эти сервисы либо автономны и не контролируются никем, либо контролируются коллективно участниками сервиса.

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

Читать далее
Всего голосов 12: ↑9 и ↓3+9
Комментарии6

Можно ли генерировать случайные числа, если мы не доверяем друг другу? Часть 2

Время на прочтение7 мин
Количество просмотров3.2K

Привет, Хабр!

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

В этой части статьи мы подробно рассмотрим еще один подход, который использует пороговые подписи.

Читать далее
Всего голосов 19: ↑19 и ↓0+19
Комментарии17

Можно ли генерировать случайные числа, если мы не доверяем друг другу? Часть 1

Время на прочтение9 мин
Количество просмотров6.3K

Привет, Хабр!

В этой статье мы обсудим генерацию псевдо-случайных чисел участниками, которые не доверяют друг другу. Как мы увидим ниже, реализовать “почти” хороший генератор достаточно просто, а вот очень хороший – сложно.

Зачем вообще нужно генерировать случайные числа участникам, не доверяющим друг другу? Одна из областей применения -- это децентрализованные приложения. Например, рассмотрим децентрализованное приложение, которое принимает ставку от участника и либо удваивает сумму с вероятностью 49%, либо забирает с 51%. Приложение будет работать только если алгоритм может непредвзято получить случайное число. Если злоумышленник сможет повлиять на результат или предсказать случайное число, и даже незначительно увеличить свой шанс получить выплату в приложении, он получит возможность опустошить его.

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

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

Он должен быть непредсказуемым. Другими словами, ни один участник не должен иметь возможность предугадать, какое число будет сгенерировано (или вывести какие-либо его свойства) до того, как оно будет сгенерировано.

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

В этой статье мы рассмотрим два подхода: RANDAO + VDF и подход, основанный на стирающих кодах. В следующей части мы подробно разберем подход, основанный на пороговых подписях.

Читать далее
Всего голосов 30: ↑30 и ↓0+30
Комментарии7

Как мы строили компанию в Кремниевой долине

Время на прочтение16 мин
Количество просмотров14K

Привет Хабр,

В этом посте я расскажу о том, как мы строили компанию в кремниевой долине. За четыре года мы прошли путь от стартапа из двух человек в подвале одного из зданий в Сан-Франциско до большой узнаваемой компании с инвестициями в более чем $30M от известных фондов, включая таких гигантов, как a16z.

Под катом много интересных историй про Y Combinator, венчурные инвестиции, поиск команды, и другие аспекты жизни и работы в долине.

Читать далее
Всего голосов 26: ↑23 и ↓3+29
Комментарии18

Шардинг в Блокчейне

Время на прочтение12 мин
Количество просмотров11K

Всем привет, я один из разработчиков Near Protocol, который, среди прочего, реализует шардинг, и в этой статье хочу подробно рассказать что вообще такое шардинг в блокчейне, как он работает, и коснуться ряда проблем, которые возникают при попытке его построить.


Хорошо известно, что Ethereum, самая популярная dApps платформа, обрабатывает меньше чем 20 транзакций в секунду. Из-за этого ограничения цена транзакций и время на их подтверждение очень высоки: несмотря на то, что блок в Ethereum публикуется раз в 10-12 секунд, согласно ETH Gas Station время между отправкой транзакции и тем как она действительно попадает в блок в среднем 1.2 минуты. Низкая пропускная способность, высокие цены и долгое подтверждение транзакций не позволяет запускать на Ethereum какие-либо высокопроизводительные сервисы.


Основная причина того, что Ethereum не может обрабатывать больше 20 транзакций в секунду заключается в том, что каждая нода в Ethereum должна проверить каждую транзакцию. За пять лет с выхода Ethereum было предложено много идей как решить эту проблему. Эти решения можно грубо разбить на две группы: те, которые предлагают делегировать выполнение транзакций небольшой группе нод с очень хорошим железом, и те, которые предлагают каждой ноде обрабатывать только подмножество всех транзакций. Пример первого подхода — это Thunder, в котором блоки создаются только одной нодой, что позволяет, по утверждениям разработчиков, получать 1200 транзакций в секунду, что в 100 раз больше чем у Ethereum. Другие примеры из первой категории — это Algorand, SpaceMesh, Solana. Все эти протоколы улучшают разные аспекты протокола и позволяют выполнять больше транзакций чем в Ethereum, но все ограничены скоростью одной (пусть и очень мощной) машины.

Читать дальше →
Всего голосов 20: ↑19 и ↓1+18
Комментарии5

The authoritative guide to Blockchain Sharding

Время на прочтение12 мин
Количество просмотров1.3K

Hi, I'm one of the developers of the sharded blockchain Near Protocol, and in this article want to talk about what blockchain sharding is, how it is implemented, and what problems exist in blockchain sharding designs.


It is well-known that Ethereum, the most used general purpose blockchain at the time of this writing, can only process less than 20 transactions per second on the main chain. This limitation, coupled with the popularity of the network, leads to high gas prices (the cost of executing a transaction on the network) and long confirmation times; despite the fact that at the time of this writing a new block is produced approximately every 10–20 seconds the average time it actually takes for a transaction to be added to the blockchain is 1.2 minutes, according to ETH Gas Station. Low throughput, high prices, and high latency all make Ethereum not suitable to run services that need to scale with adoption.

Read more →
Всего голосов 15: ↑14 и ↓1+13
Комментарии0

Несколько интересных особенностей MySQL

Время на прочтение8 мин
Количество просмотров63K
В не очень далеком прошлом мне пришлось покопаться немного в исходном коде MySQL, и разобраться в некоторых аспектах его работы. В ходе работы лопаткой, и эксперимeнтов, я наткнулся на несколько очень интересных особенностей, часть из которых просто забавна, а в случае некоторых бывает очень интересно понять, чем руководствовался программист, который принимал решение сделать именно так.

Начнем с такого интересного типа, как ENUM.

mysql> CREATE TABLE enums(a ENUM('c', 'a', 'b'), b INT, KEY(a));
Query OK, 0 rows affected (0.36 sec)

mysql> INSERT INTO enums VALUES('a', 1), ('b', 1), ('c', 1);
Query OK, 3 rows affected (0.05 sec)
Records: 3  Duplicates: 0  Warnings: 0


Итак, у нас есть таблица, в ней есть два столбца. У первого, a, тип ENUM, у второго, b, INT. В таблице три строки, у всех трех значение b равно 1. Интересно, чему равны минимальный и максимальный элементы в столбце a?

mysql> SELECT MIN(a), MAX(a) FROM enums;
+--------+--------+
| MIN(a) | MAX(a) |
+--------+--------+
| c      | b      |
+--------+--------+
1 row in set (0.00 sec)


Кажется странным, было бы разумно, если бы самым маленьким был 'a', а самым большим — 'c'.
А что если выбрать минимум и максимум только среди тех строк, где b = 1? То есть, среди всех строк?

mysql> SELECT MIN(a), MAX(a) FROM enums WHERE b = 1;
+--------+--------+
| MIN(a) | MAX(a) |
+--------+--------+
| a      | c      |
+--------+--------+
1 row in set (0.00 sec)


Вот так мы заставили MySQL поменять свое мнение о том, как сравнивать поля в ENUM, просто добавив предикат.
Разгадка такого поведения заключается в том, что в первом случае MySQL использует индекс, а во втором нет. Это, конечно, не объясняет, почему MySQL сравнивает ENUMы по разному для сортировки в индексе, и при обычном сравнении.

Второй пример проще и лаконичнее:

mysql> (SELECT * FROM moo LIMIT 1) LIMIT 2;
+------+
| a    |
+------+
|    1 |
|    2 |
+------+
2 rows in set (0.00 sec)


Когда я показал этот запрос своему коллеге, который занимается разработкой парсера SQL, его вопрос был не «почему этот запрос возвращает две строки», а «как надо написать SQL парсер так, чтобы такой запрос был валидным, без того, чтобы написать правило, специально разрешающее такой запрос».

Интересно, что далеко не любой SELECT в скобках сработает, в частности, UNION в скобках — это синтаксическая ошибка:

mysql> (SELECT * FROM moo UNION ALL SELECT * FROM hru) LIMIT 2;
ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'UNION ALL SELECT * FROM hru) LIMIT 2' at line 1


Еще несколько интересных примеров под катом
Читать дальше →
Всего голосов 113: ↑110 и ↓3+107
Комментарии95

Об удобной навигации и отладке C++ кода в Vim

Время на прочтение7 мин
Количество просмотров41K
Компания, где я работаю, разрабатывает программное обеспечение на C++ под Linux. Долгое время мы использовали Qt Creator, с редкими ребятами работающими из Emacs и Vim. Когда я сам попытался пересесть на Vim, я понял, что ситуация с плагинами для разработки на С++ очень не простая. Поработав немного с CTags, я быстро понял, что без напильника работать в Vim будет очень сложно.
К сожалению, с ростом опыта работы с Vim редактор в Qt Creator в режиме эмуляции устраивал меня все меньше, и в какой-то момент я решил потратить немного времени и разобраться, как же сделать из Vim нормальную среду.
Я очертил для себя четыре вещи, которые я бы хотел от среды разработки, и которых мне бы хватило в Vim, чтобы полностью на него перейти:

1. Автодополнение
2. Навигация по коду
3. Отладка прямо из среды
4. Интеграция с Git (в частности Blame прямо в редакторе, и Git Grep)

Автодополнение в Vim — это решенная проблема, и название у решения YouCompleteMe. Это очень качественный плагин, который реализует автодополнение для большого количества языков программирования, в частности Python и C++. Ходят слухи, что внутри Google YouCompleteMe решает и вторую проблему с навигацией кода, но использует для этого внутренные инструменты гугла для индексирования.

Интеграция с Git в какой-то степени решена с помощью vim-fugitive. Это не такая комплексная интеграция, как бывает у Jet Brains, или в Visual Studio, но сравнимая с тем, что предлагает Qt Creator. Те два сценария, которые нужны были мне: blame и grep — работают хорошо.

Отладка и навигация были проблемами, решенными гораздо хуже. В этой статье я расскажу о плагине, который мы написали для навигации по С++ коду. В конце статьи я также расскажу о том, как мы для себя решили проблему с интегрированным отладчиком.
Читать дальше →
Всего голосов 56: ↑51 и ↓5+46
Комментарии92

Как мы запрос в 100 раз ускоряли, или не все хеш-функции одинаково плохи

Время на прочтение4 мин
Количество просмотров37K
Мы разрабатываем базу данных. Однажны к нам обратилась компания, которая столкнулась со следующей задачей:

Есть некоторое множество объектов, и некоторое множество тегов. Каждый объект может содержать несколько тегов. Какие-то теги очень редкие, а какие-то встречаются часто. Одному объекту один тег может быть сопоставлен несколько раз.
Новые объекты, теги и связи между ними непрерывно добавляются.
Задача — очень быстро отвечать на вопросы вида: «сколько есть объектов, у которых есть тег А или B, но нету тега С» и похожие. На такие запросы хотелось бы отвечать за десятые доли секунды, при этом не останавливая загрузку данных.

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

SELECT 
    COUNT(*) 
FROM (
    SELECT 
        object_id, 
        (MAX(tag == A) OR MAX(tag == B)) AND MIN(tag != C) AS good
    FROM tags
    WHERE tag IN (A, B, C)
    GROUP BY object_id
) WHERE good == 1;


Чтобы такой запрос выполнялся быстро, мы разбили данные между серверами кластера по object_id, а внутри каждого сервера отсортировали их по тегам. Таким образом сервер, выполняющий запрос, может отправить запрос без изменений на все сервера с данными, а затем просто сложить их результаты. На каждом сервере с данными для выполнения запроса достаточно найти строки для тегов A, B и C (а так как данные по тегу отсортированы, это быстрая операция), после чего выполнить запрос за один проход по этим строкам. Худший тег имеет несколько десятков миллионов объектов, несколько десятков миллионов строк обработать за десятые доли секунды видится возможным.
Стоит отметить, что подзапрос содержит GROUP BY object_id. GROUP BY в данной ситуации можно выполнить несколькими способами, например, если данные после тега отсортированы по object_id, то можно выполнить что-то похожее на merge sort. В данной ситуации, однако, мы данные по object_id не отсортировали, и оптимизатор разумно решил, что для выполнения GROUP BY надо построить хеш-таблицу.

Мы загрузили все данные в кластер, и запустили запрос. Запрос занял 25 секунд.
Читать дальше →
Всего голосов 107: ↑104 и ↓3+101
Комментарии4

Частые ошибки при разработке lockfree-алгоритмов и их решения

Время на прочтение13 мин
Количество просмотров59K
На хабре уже было несколько статей про lock-free алгоритмы. Этот пост — это перевод статьи моего коллеги, которую мы планируем публиковать в нашем корпоративном блоге. По роду деятельности мы пишем огромное количество lock-free алгоритмов и структур данных, и этой статьей хочется показать, насколько это интересно и сложно одновременно.



Эта статья во многом похожа на эту статью, но в той статье рассматриваются не все проблемы, с которыми можно столкнуться, разрабатывая lock-free структуры данных, и уделяется очень мало внимания решению этих проблем. В этой статье хочется детально остановиться на некоторых решениях, которые мы используем в реальной реализации lock-free структур данных в нашем продукте, и больше внимания уделить оценке производительности.
Читать дальше →
Всего голосов 148: ↑147 и ↓1+146
Комментарии52

Как, зная только имя и email человека, злоумышленники получили доступ ко всем его аккаунтам и удаленно уничтожили информацию на всех его устройствах

Время на прочтение2 мин
Количество просмотров177K
Очень интересная статья появилась сегодня на wired.com. Буквально за один час у автора статьи Мэта Хонана были взломаны Amazon, GMail, Apple и Twitter аккаунты и была удаленно уничтожена информация на его iPad, iPhone и MacBook. Среди прочего он потерял все фотографии своей дочки с ее рождения, многие документы и большую часть переписки. Очень интересно в этой истории то, как злоумышленник получил доступ к Amazon аккаунту и AppleID — для этого не понадобилась ничего, кроме доступной в сети информации и телефона.
Читать дальше →
Всего голосов 341: ↑338 и ↓3+335
Комментарии329

Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования

Время на прочтение6 мин
Количество просмотров36K
Недавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.

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

loop 1000000000
  loop 1000000000
    loop 1000000000
      a += 1
      b += a
    end
  end
end
end


Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.
Читать дальше →
Всего голосов 173: ↑169 и ↓4+165
Комментарии55

Информация

В рейтинге
Не участвует
Откуда
San Francisco, California, США
Зарегистрирован
Активность