Проблемы и их решения - snordenstorm/notable GitHub Wiki

Англоязычный оригинал здесь.

Мы всегда работаем в каком-то предположении, в рамках какой-то модели. В традиционной криптографии они имеют такой вид:

1. Никто не может проделать более чем 2⁷⁹ вычислительных шагов.
2. Разложение на множители трудновыполнимо (сверхполиномиально во времени = не существует полинома, который бы ограничивал его сверху). Примеры сверхполиномиальных задач — имеющие время выполнения 2ⁿ, n^{log log n} (n — параметр битов, поданных на вход).
3. Taking nth roots modulo composites is hard
4. The elliptic curve discrete logarithm problem cannot be solved faster than in 2^n/2 time

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

1. Лица, владеющие более чем 25% вычислительных мощностей сети, не могут договариваться
2. Лица, владеющие более чем 25% всей валюты, не могут договариваться
3. The amount of computation of a certain proof of work function that can be accomplished with a given amount of money is not superlinear beyond a point which is reasonably low
4. Существует какое-то количество альтруистов и какое-то количество лиц, стремящихся эту систему уничтожить. Решения большинства же будут экономически рациональны.
5. Число пользователей велико, пользователи могут появляться и покидать сеть в любой момент времени, но хотя бы некоторые не выходят никогда.
6. Цензура невозможна
7. Те, кому нужно, с лёгкостью могут нагенерировать себе сколько угодно IP-адресов, а также приобрести трафик неограниченно широкой полосы пропускания
8. Большая часть пользователей анонимны, так что отрицательные очки репутации и долги не беспокоят этих пользователей

Технология, на которой основан Биткойн, является крайне впечатляющей в том числе по причине своей простоты. Проблема 30-летней давности в computer science была решена простым во внедрении и настолько простым для понимания способом, что даже некоторые подростки могут объяснить принцип работы протокола во всей полноте. Однако в то же время эта технология в своей текущей форме достаточно сильно ограничена. Не продумана масштабируемость Биткойна; тот факт, что каждая полная нода должна проводить каждую транзакцию является серьёзным препятствием на пути к успеху платформы и фактором, the fact that every full node needs to process every transaction is a large roadblock to the future success of the platform, and a factor preventing its effective use in micropayments (arguably the one place where it is the most useful). Timestamping is flawed, and proof-of-computation algorithms are very limited in the types of computation that they can support. Тот факт, что исходное решение было столь "простым" уже сам по себе означает, что его есть куда улучшать, и далее в этом документе описываются направления, в которых улучшение необходимо.

Одной из главных проблем мира криптовалют сейчас является масштабируемость. Есть расхожее утверждение, что если мейнстримовые платёжные сети (Visa, Mastercard (ведь именно они, не Paypal?)) проводят порядка 2000 транзакций в секунду, в своей текущей форме сеть Биткойн может производить только 7. Это не фундаментальное ограничение — изменив block size limit, Биткойн сможет поддерживать 70 и даже 7000 транзакций в секунду. (А сколько транзакций в секунду на данный момент ему нужно, сколько происходит? Мы уже упираемся сейчас в этот лимит?) Проблема в том, что тогда среднестатистический пользователь не сможет запустить полную ноду, потому что она раздуется до терабайтов. Полную ноду сможет держать лишь ограниченное количество бизнесов, могущих себе позволить расходы. Поскольку для майнинга не нужно загружать весь блокчейн (достаточно заголовка предыдущего блока), майнеры также не будут держать полную ноду (и сейчас большинство не держит).

Понятно, почему сообщество этим обеспокоено: если крайне малое количество лиц будут держать полную ноду, они могут вступить в сговор и перерисовать блокчейн(=единственное место учёта транзакций, определяющее балансы всех пользователей) как им вздумается, и другие пользователи не смогут убедиться, что блок невалиден, не обсчитывая (?) его самостоятельно. Хотя такое мошенничество может быть обнаружено, . Таким образом, Биткойн с 7000 транзакциями в секунду примерно настолько же безопасен, децентрализован и независим, как Paypal, в то время как то, чего мы хотим — систему с 7000 транзакциями в секунду того же уровня децентрализации .

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

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

Проблема: создать блокчейн

Дополнительные допущения и требования:

• Майнеров в сети много
• Майнеры могут использовать специализированное и неспециализированное оборудование. Специализированное следует полагать примерно в 10000 раз более мощным для конкретных задач.
• Обычные пользователи будут использовать неспециализированное оборудование

Важным свойством протокола Биткойна является то, что нахождение одного блока в среднем занимает 10 минут; если бы поиск блока занимал день, платежи бы осуществлялись слишком медленно (платежи всегда осуществляются не раньше, чем будет найден следующий блок); если бы блоки генерировались каждую секунду, проблемы централизации и сетевой эффективности сделали бы систему нежизнеспособной даже в отсутствие злоумышленников и их любви к "атаке 51%". Чтобы добиться значения block time в 10 минут, сеть Биткойн раз в две недели производит подстройку сложности — если нахождение блоков стало слишком быстрым, сложность увеличивается, если слишком медленным, сложность уменьшается.

Одной из смутных угроз всем современным криптовалютам, и криптографии в целом, является квантовый компьютер. На данный момент угроза не кажется серьёзной; на июль 2014 года все квантовые компьютеры — либо "адиабатические квантовые компьютеры", эффективные только для крайне ограниченного круга задач и, возможно, не более эффективные для них, чем обычные компьютеры, либо машины с крайне малым числом кубитов, неспособные разложить на множители число выше 35. В будущем, однако, квантовые компьютеры могут стать намного более мощными; недавние разоблачения активности правительственных агентств, таких как АНБ, породило опасения (правда, маловероятные), что американские военные уже могут контролировать квантовый компьютер. Имея это в виду, понятно, почему защищённая от квантовых компьютеров криптография становится всё более приоритетной.

Предположим, в системе n нодов. Тогда злоумышленник может создать 5n нодов и получить контроль над сетью. Единственный известный выход здесь — вклад, базирующийся на ресурсах.

Один из подходов, решаю, заключается в создании PoW-алгоритма, базирующегося на трудноспециализируемом типе вычисления. Другая идея заключается в создании "требовательной к памяти" функции хеширования, что значительно усложнило бы создание АСИКа. Идея эта проста, но фундаментально ограничена — если функция нуждается в большом количестве памяти для вычисления, как правило, для проверки такого вычисления также нужно очень большое количество памяти. Кроме того, возможны специализированные устройства, основанные не только на идее гиперпараллелизации. Другой подход — случайно генерировать майнинг-алгоритмы каждый блок, пытаясь сделать выгоду от специализации оборудования невозможной, потому АСИК, подходящий для выполнения произвольных вычислений — это, по определению, обычный процессор. Помимо этих двух, возможны ещё какие-то стратегии.

В конечном счёте, полная ASIC-resistance невозможна; у любого алгоритма всегда есть какие-то "нехоженные тропы", которые можно обрезать для сокращения стоимости спецоборудования. Однако то, чего нам хотелось бы — не полная защита от АСИКов, а скорее экономическая. Дадим определение последней.

Для более глубокой дискуссии on ASIC-resistant hardware, see https://blog.ethereum.org/2014/06/19/mining/

Problem: Придумать две функции PoWProduce(data,diff) -> nonce и PoWVerify(data,nonce,diff) -> { 0, 1 }, которые могли бы быть альтернативой Hashcash, такие, что производство АСИКа для PoWProduce экономически непривлекательно.

Недоброжелатели Биткойна любят подчёркивать, что проделываемые майнерами вычисления являются пустой тратой электроэнергии (на миллионы долларов ежедневно). Майнеры круглыми сутками вычисляют SHA-256 (или scrypt, или любого другого алгоритма) хэши (совокупная мощность биткойн-майнеров сейчас имеет порядок 10¹⁵ хэш/с), пытаясь подобрать подходящий (являющийся достаточно малым как 16-ричное число) хэш, и абсолютно вся эта работа не несёт никакой пользы мировому сообществу. Традиционные централизованные сети, такие как PayPal или сети, обслуживающие кредитные карты, обходятся вообще без proof-of-work-вычислений, в то время как в экосистеме Биткойн на электричество и оплату специализированных устройств тратится порядка миллиона долларов в день.

Один из способов решения проблемы — сделать функцию proof-of-work осуществляющей полезные вычисления. Стандартный пример здесь — Folding@home, проект, предлагающий всем желающим загрузить ПО, симулирующее фолдинг белка, проделать вычисления, переслать результаты учёным и тем самым помочь им в понимании, а, следовательно, и в излечении, болезней. Проблема, правда, в том, что добросовестность вычислений Folding@home нельзя быстро проверить; проверка вычисления Folding@home, проверка того, что вычислявший "не срезал углы" для увеличения демонстрируемой скорости, занимает в точности столько же, сколько само вычисление. Если быстропроверяемое proof-of-computation для Folding@home может быть придумано, или если удастся найти другое полезное вычисление, проверка которого занимала бы гораздо меньше времени, чем само вычисление, майнинг криптовалют станет огромным благом для общества. Это не только уберёт возражение "майнинг тратит электроэнергию", но и будет производить общественное благо.

Но тут есть такое соображение: если полезный PoW будет полезен для узкого круга лиц (а не абстрактных "нужд науки"), это уменьшит стоимость потенциальной атаки на сеть. Если полезный PoW полезен настолько, что проделывать вычисления этому кругу лиц будет выгодно даже без оглядки на криптовалютные выплаты . Простой, пусть и грубый, неидеальный, способ решения этой проблемы — сделать PoW наполовину полезным и наполовину бесполезным, что уменьшит стоимость атаки как минимум на 50%. Другое экономическое решение — сделать вычисление "чистым" общественным благом, в том смысле, чтобы вычислять нечто такое, от чего ни один конкретный человек профита получать не будет. Предлагаемое решение должно включать в себя строгий анализ того, кому предлагаемый PoW-механизм мог бы быть выгоден.

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

Задача: Создать две функции, PoWProduce(data,diff) -> nonce и PoWVerify(data,nonce,diff) -> { 0, 1 }, которые стали бы успешной альтернативой для Hashcash, такие, что результат вычисления PoWProduce полезен не только для поддержки работы криптовалютной сети.

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

Одной из главных проблем Биткойна является волатильность цены. (Это отпугивает широкие массы.) Стоимость 1 BTC по отношению к доллару часто испытывает очень большие флуктуации, возрастая или падая на 25% за день, или возрастая на 300% за месяц. Основная причина этого в том, что количество биткойнов строго фиксировано, так что цена прямо пропорциональна спросу (and therefore, by efficient market hypothesis, the expected discounted future demand), а спрос крайне непредсказуем. Неизвестно, будет ли Биткойн нишевым платёжным средством для проведения транзакций высокой степени приватности, заменой Western Union, мейнстримовой платёжной системой или резервной мировой валютой, — и ожидаемая стоимость биткойна для людей, думающих на этот счёт по-разному, как вы понимаете, различается в тысячи раз.

Для решения этой проблемы есть два пути.

Проблема: построить криптоактив со стабильной ценой.

Видны два пути решения этой проблемы:

1. Научить сеть делать допэмиссию валюты, если спрос увеличивается.

Вместо <<one unit of CPU power, one vote>> <<one currency unit, one vote>>.

Несправедливость: даже ПК наиболее бедных людей хуже (подходят для майнинга). Выход: PoW, но of human work, человеческого труда.

Фантазия на тему привязки кошелька к GPS-координатам. Представляю какую беготню по городу можно развернуть среди участников гипотетической офлайновой игры <<Поймай свой Бит>>. А если ещё биты визуализировать через очки Google Glass, то можно прям воплотить мечту детства и бегать как в Марио собирая монетки.

Ютубу срочно нужна p2p-альтернатива. Он мёртв (цензурируется).

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

Купить на бирже и оплатить инфу. Расшарить свои ресурсы(как вы это всегда делаете в торрентах и тп), получить за это CRU которыми и оплатить ресурсы