Bitcoin: однорангова електронна грошова система

Сатоші Накамото
satoshin@gmx.com
www.bitcoin.org

1. Вступ

Інтернет-комерція в більшості випадків спирається на фінансові установи, які виконують функцію довірених посередників для проведення електронних платежів. Така схема працює для більшості транзакцій, але в її основі закладена довіра посереднику, що тягне за собою певні проблеми. Посередники контролюють транзакції та ускладнюють проведення незворотних транзакцій. Ціна послуг посередника збільшує вартість транзакцій та встановлює їх мінімальну вартість, що унеможливлює проведення мікроплатежів. Також, відсутність незворотних транзакцій збільшує вартість послуг сервісів, чиї послуги не можна відмінити. Оскільки платіж можна відмінити, а послугу ні, продавець повинен бути насторожі, вимагаючи від покупця більше особистої інформації для верифікації. При цьому, певний відсоток шахрайства компенсується за рахунок збільшення ціни такої послуги. Такі незручності у комерційних відносинах зникають при використанні готівки. Механізму для проведення прямих електронних не існує.

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

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

2. Транзакції

Визначимо електронну монету як послідовність цифрових підписів. Черговий власник відправляє монету наступному власнику, підписуючи хеш попередньої транзакції та публічний ключ майбутнього власника, приєднує цю інформацію до суми переказу. Отримувач може перевірити кожний підпис, щоб підтвердити коректність всього ланцюга власників монет.

Проблема полягає в тому, що отримувач не може визначити, скільки разів попередній власник витратив цю монету. Традиційне рішення полягає в перевірці витрат центральною довіреною особою (“монетний двір”, емітент) кожної транзакції. Після будь-якого платежу монета повертається до емітента, який створює нову її версію; і тільки отриманим напряму таким монетам можна довіряти. Недолік такої схеми полягає в централізації, бо від компанії-емітента залежить доля всієї грошової системи, оскільки тільки нею контролюється кожна транзакція.

Отримувач платежу повинен знати, що ніхто з попередніх власників не підписав транзакцію раніше за ту, яка знаходиться в ланцюзі відправленій йому монеті. В нашій системі, лише перша транзакція з декількох є істиною, тому всі наступні транзакції з цими монетами вважатимуться подвійною тратою. В централізованій моделі емітент вів облік транзакцій та вирішував в якій послідовності вони записані. Щоб позбавитись від посередника, учасникам необхідно відкрито публікувати транзакції [1], та мати згоду в їх послідовності. Отримувач потребує доказ того, що для кожної транзакції з ланцюга більшість учасників системи вважають її першою.

3. Сервер міток часу

Функціонування серверу міток часу засновано на хешуванні блоків даних, на які необхідно поставити мітку часу, та відкритій публікації цього хешу, так само як в газеті чи Uneset-повідомленнях [2-5]. Мітка часу показує, що в даний момент часу існували певні транзакції, саме тому вони потрапили в блок і були хешовані. Кожен наступний блок містить хеш попереднього блоку, таким чином створюється ланцюг взаємопов’язаних хешами блоків з транзакціями позначених мітками часу.

4. Доказ виконаною роботою Proof-of-Work

Щоб реалізувати розподілений одноранговий сервер міток часу, використовується схема “доказ виконаної роботи”, подібна до системи Hashcash Адама Бека [6]. Сутність цієї схеми полягає в знаходженні значення, хеш якого (наприклад за алгоритмом SHA-256) буде починатись з певної кількості нульових бітів. Об’єм роботи, який необхідно виконати щоб знайти таке значення, експотенційно залежить від кількості нулів в хеші бо виконується шляхом звичайного перебору значень, а для перевірки знайденого значення достатньо вирахувати його хеш.

В запропонованому сервері міток часу пошук значення, хеш якого відповідатиме вимогам по кількості нулів, відбувається шляхом перебору змінної Nonce, яка частиною даних блоку з транзакціями. Як тільки знайдено значення змінної Nonce, з якою дані блоку дають хеш який задовольняє вимогам кількості нулів, блок відправляється в мережу вузлам для приєднання до ланцюга блоків. Після цього, будь-які зміни інформації в блоку з транзакціями потребуватимуть витрати розрахункових потужностей за для пошуку нового значення Nonce, з яким хеш зміненого блоку відповідатиме вимогам системи. Якщо ж змінений блок не є останнім в ланцюгу, то перерахунку потребуватимуть всі наступні за зміненим блоки.

Доказ виконаної роботи хешуванням вирішує питання справедливої для всіх версії транзакції, яку підтримує більшість. Якщо за голос вважати одну IP-адресу, то скомпрометувати таку схему можна через контроль великого діапазону IP-адрес. Наведена схема побудована за принципом “один процесор – один голос”. Найдовший ланцюг блоків відображає рішення більшості розрахункових потужностей. Якщо більше половини розрахункових потужностей належить чесним вузлам, то ланцюг чесних транзакцій буде збільшуватись швидше та випереджатиме будь-який конкуруючий ланцюг. Щоб змінити інформацію в блоці ланцюга, атакуючому необхідно буде виконати всю розрахункову роботу над блоком зі змінами та всіма наступними блоками до останнього актуального блоку. Атакуючий повинен догнати та випередити чесних учасників за розрахунковими потужностями в пошуку нових блоків. Вірогідність здійснення такої атаки зловмисником експоненційно зменшується в залежності від кількості блоків.

Для компенсації зростаючої розрахункової потужності та коливань кількості розрахункових вузлів в мережі, складність хешування (кількість нульових значень на початку хешу) повинна змінюватись, щоб забезпечити рівномірну швидкість знаходження змінної Nonce (генерації блоків). Якщо блоки з’являються занадто часто – складність збільшується та навпаки.

5. Мережа

Система працює за такими правилами:

1. Нові транзакції розсилаються всім вузлам.
2. Кожен розрахунковий вузол об’єднує транзакції в блок.
3. Кожен розрахунковий блок намагається підібрати Nonce з яким інформація блоку дає хеш що задоволяє вимогам складності.
4. Знайдений блок відправляється вузлам мережі.
5. Вузол перевіряє отриманий блок та транзакції в ньому на відповідність правилам системи та відсутність подвійних витрат. Валідний блок вузол додає до ланцюга блоків.
6. Після додавання блоку до ланцюга на більшості вузлів мережі, розрахунковий вузол починає підбір нової змінної Nonce для блоку з новими транзакціями, використовуючи в якості частини даних хеш доданого до ланцюга валідного блоку.

Вузли мережі завжди вважають істинним найдовший ланцюг блоків та працюють над його збільшенням. Якщо два розрахункових вузла одночасно опублікують в мережу різні версії наступного блоку, то деякі вузли отримають одну версію, а деякі – іншу версію блоку. В такому випадку кожний вузол почне працювати над власною версією ланцюга блоків, але збереже іншу версію на випадок, якщо вона виявиться довшою у більшості вузлів. Така подвійність одразу зникне, як тільки буде згенеровано новий блок, який буде додано до однієї з версій, і всі вузли які працювали над конкуруючою версією автоматично перемикаються на актуальну.

Нові транзакції не обов’язково повинні досягати всіх вузлів. Коли транзакції розповсюджуються по мережі та потрапляють до достатньої кількості вузлів (мемпул), вони додаються до чергового блоку з транзакціями. Правила розсилки блоків також не є строгими по відношенню до втрачених повідомлень про нові блоки. Як тільки вузол, який пропустив блок, отримує новий блок, він додає пропущені блоки копіюючи їх з мережі.

6. Матеріальні стимули

По замовченню, перша транзакція в блоці є спеціальною, яка створює нові монети, та передає їх на адресу того хто створює блок. Така схема стимулює чесних учасників мережі до виконання розрахункової роботи по пошуку змінної Nonce, та підтримки загальної потужності мережі. Також, така схема винагородження вирішує питання початкового розподілу грошової маси за умови відсутності центрального емітенту. Поступове збільшення числа монет в обігу можна порівняти з видобутком золота, в який золотошукачі вкладають власні ресурси. В нашому випадку, майнери вкладають процесорний час та витрати електроенергії.

Іншим способом стимулювання розрахункової роботи є комісійні за транзакції. Якщо вхідна сума платежу більша за вихідну, різниця є комісією за переказ та додається до базового значення винагороди за знайдений блок в першій транзакції. Коли сумарний об’єм грошової маси досягне заздалегідь встановленого значення (наприклад 21 000 000) єдиним джерелом винагороди залишаться комісії, при цьому позбавлені від інфляції.

Така форма стимулювання сприяє зменшенню випадків шахрайських дій. Якщо жадібний зловмисник здатен виділити більшу долю розрахункових потужностей за всіх чесних учасників, він може певний час ошукувати продавців та повертати власні кошти, або направити свої потужності на генерацію нових блоків та монет. Більш вигідним для ньго буде варіант “гри за правилами”, який забезпечить отримання половини всіх нових грошей, замість саботажу та підтримці свого капіталу на постійному рівні.

7. Економія дискового простору

Достатньо старі транзакції в ланцюзі блоків можна видалити з метою звільнення дискового простору. Щоб хеш блоку залишився незмінним, всі транзакції в блоці зберігаються у вигляді дерева Меркла [7][2][2], лише його корінь входить до складу блоку. Розмір старих блоків можна зменшити за рахунок видалення непотрібних гілок цього дерева, зберігати проміжні хеші необов’язково.

Заголовок порожнього блоку беде займати обсяг пам’яті 80 байт. З урахуванням швидкості генерації блоку 1 блок кожні 10 хвилин отримаємо 80 * 6 * 24 * 365 = 4.2 Мб/рік. На 2008 рік середній комп’ютер має 2 Гб оперативної пам’яті. З урахуванням закона Мура, зріст оперативної пам’яті кожного року збільшуватиметься на 1.2 Гб, зберігання даних не є проблемою, навіть якщо всі заголовки будуть знаходитись в пам’яті.

8. Спрощена перевірка платежів

Перевірка транзакцій можлива без наявності повнофункціонального вузла. Необхідно зберігати лише заголовки блоків найдовшого ланцюга та робити запити хешу для необхідної транзакції. При спрощеній перевірці транзакцій не можна перевірити коректність самої транзакції, але маючи посилання на блок в якому ця транзакція знаходиться, можна впевнитись, що цей блок і всі наступні блоки відповідно з транзакціями прийняті та підтверджені мережею.

Спрощений метод підходить тільки в тому разі, якщо мережа знаходиться під контролем чесних вузлів, тобто поки зловмисник не заволодіє більшими ресурсами. Вузли (ноди) перевіряють безпосередньо транзакції, дії зловмисника їм не загрожують, але якщо зловмисник генерує найдовший ланцюг блоків з фейковими транзакціями, він компрометує спрощену схему. Захистом від зловмисника в цьому випадку може бути розсилка сигналів тривоги від вузлів які отримують блок з фейковими транзакціями. За таким сигналом програма-клієнт завантажить блок повністю для перевірки транзакцій на валідність. Компанії які прийматимуть платежі підключатимуться до мережі через власні повні вузли за для безпеки та швидкості перевірки транзакцій.

9. Об’єднання та поділ сум транзакцій

Створювати окрему спеціальну транзакцію для найменшої долі монети з метою передачі певної кількості монет не зручно. Для підтримки об’єднання та поділу сум транзакції містять кілька входів та виходів. Звичайна транзакція виглядатиме так: або один вхід від попереднього крупного платежу, або кілька входів від з невеликими сумами та не більше двох виходів. Один з виходів, це безпосередньо платіж, а другий вихід, за потребою, повертає “сдачу” відправнику.

Випадок збільшення зв’язків, коли транзакція формується з кількох попередніх, а ті в свою чергу, ще з кількох кожна не є проблемою, оскільки немає необхідності отримувати повну, незалежну копію історії транзакцій.

10. Конфіденційність

Традиційна банківська модель підтримує необхідний рівень конфіденційності, надаючи доступ до інформації про транзакції лише її учасникам та довіреній третій особі. Необхідність відкритої публікації транзакцій виключає такий підхід. Приватність в нашій схемі зберігається завдяки анонімності публічних ключів. Відкритою є інформація про те, що хтось комусь відправив певну суму, але без прив’язки до особистостей. Така ж кількість даних розкривається на фондових біржах, де вказують час та об’єм приватних угод, але не вказують між ким ці угоди були здійснені.

Ще одним елементом захисту анонімності є генерація нової пари публічний/приватний ключ для кожної нової транзакції. Це унеможливлює зв’язок різних платежів з їх спільним відправником чи отримувачем. Деякого публічного зв’язування транзакцій з особистістю неможливо уникнути. Транзакції з кількома входами доводять, що ці суми належать одній особі. Ризик полягає в тому, що розкриття особи власника публічного ключа може привести до відстеження всіх транзакцій з його участю. З іншого боку, приналежність публічного ключа певній особі можна довести лише підтвердивши наявність в його розпорядженні приватного ключа, який є парою публічному. Останнє здійснити майже неможливо, при виконанні особою певних дій безпеки.

11. Розрахунки

Ситуація, при якій зловмисник намагається згенерувати довший ланцюг блоків за ланцюг який мають чесні учасники. Навіть якщо зловмисник сформує довший ланцюг, це не призведе до того, що він зможе створювати гроші з повітря, привласнювати собі чужі монети чи вносити будь-які інші зміни в систему. Вузли ніколи не приймуть некоректну транзакцію чи блок який її містить. Єдине що зможе зловмисник, це намагатись змінити одну з власних транзакцій з метою повернути собі кошти.

Змагання між чесними учасниками та зловмисником можна уявити як біномінальне випадкове блукання. Успішна подія, коли “хороший” ланцюг збільшується на один блок, призведе до збільшення відриву на одиницю, а не успішне, коли черговий блок створює зловмисник – до зменшення на одиницю.

Вірогідність зловмисника наздогнати різницю в кілька блоків така сама, як і задачі про “розорення гравця”. Уявімо, що гравець має необмежений кредит, починає гру з деяким дефіцитом та має необмежену кількість спроб щоб відігратись. Вірогідність того, що гравець відіграється, так само як і зловмисника наздогнати чесних учасників, розраховується наступним чином [8]:

p = вірогідність появи блоку в чесному ланцюзі блоків
q = вірогідність створення блоку зловмисником
q_z = вірогідність того, що зловмисник наздожене ланцюг чесних учасників з відставанням в z блоків

В випадку p > q, вірогідність зменшується експоненційно з ростом числа блоків на яке відстає зловмисник. Без початкового успішного ривку на початку атаки, шанси зловмисника нанести школу стають мізерними.
Як довго отримувачу платежу чекати, щоб бути впевненим, що попередній власник вже не зможе відмінити транзакцію?
Ми припускаємо, що зловмисник-відправник дозволяє адресату деякий час вірити, що платіж був проведений, після чого повертає гроші собі. Одержувач дізнається про це, але шахрай сподівається, що буде вже занадто пізно. Адресат створює нову пару ключів і повідомляє свій публічний ключ відправнику прямо перед підписанням транзакції. Це не дозволить відправнику заздалегідь почати працювати над паралельним ланцюгом і зробити ривок вперед. Після відправки платежу шахрай починає потай працювати над паралельною версією ланцюга, що містить альтернативну транзакцію. Одержувач чекає, поки транзакція буде додана в блок і поки той не буде продовжений ще z блоками. Йому невідомий прогрес зловмисника, але якщо середня швидкість генерації чесних блоків – відома величина, то число блоків нападника підпорядковується розподілу Пуассона з математичним очікуванням:

Щоб отримати можливість того, що атакуючий обжене чесних учасників, ми множимо значення випадкової величини (число створених ним блоків) на ймовірність того, що він зможе надолужити різницю, що залишилася:

Перегрупувавши складові і позбувшись від безкінечного ряду, отримуємо…

Код програми на Си…

#include double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 – q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k <= z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i <= k; i++)
poisson *= lambda / i;
sum -= poisson * (1 – pow(q / p, z – k));
}
return sum;
}

Запустивши програму, ми бачимо, що ймовірність експоненціально падає з ростом z.

q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012

q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006

Вирішуя рівняння відносно P < 0.1%, отримуєм…

P < 0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340

12. Висновок

В даній роботі нами була запропонована система електронних транзакцій без довіри. Побудова схеми почалась з уявлення про монети як послідовність цифрових підписів, що забезпечує контроль володіння, але допускає подвійну витрату. Цю проблему ми вирішили за допомогою розподіленої мережі і схеми «доказ виконаною роботою» для запису публічної історії транзакцій. Спроба зловмисника, який має більшість ресурсів мережі, змінити старі записи, є практично неможливою. Сильною стороною мережі є простота її структури. Всі вузли працюють самостійно, іноді обмінюючись інформацією. Немає необхідності в ідентифікації, оскільки повідомлення не йдуть по якомусь певному маршруту, а поширюються за принципом «найменших витрат». Вузли можуть залишати мережу і знову підключатися, приймаючи найдовший ланцюг блоків як підтвердження пропущеної історії транзакцій. Вузли висловлюють свою згоду через приєднання коректного блоку в ланцюг блоків, використовуючи свої обчислювальні потужності для подовження цього ланцюга, а незгоду (якщо блок містить невірні дані) – не приєднуючи некоректний блок до ланцюга блоків. Будь-які необхідні правила протоколу можуть бути реалізовані через цей механізм голосування.

Литература
[1] W. Dai, “b-money,” http://www.weidai.com/bmoney.txt, 1998.
[2] H. Massias, X.S. Avila, and J.-J. Quisquater, “Design of a secure timestamping service with minimal trust requirements,” In 20th Symposium on Information Theory in the Benelux, May 1999.
[3] S. Haber, W.S. Stornetta, “How to time-stamp a digital document,” In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
[4] D. Bayer, S. Haber, W.S. Stornetta, “Improving the efficiency and reliability of digital time-stamping,” In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
[5] S. Haber, W.S. Stornetta, “Secure names for bit-strings,” In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.
[6] A. Back, “Hashcash – a denial of service counter-measure,” http://www.hashcash.org/papers/hashcash.pdf, 2002.
[7] R.C. Merkle, “Protocols for public key cryptosystems,” In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.
[8] W. Feller, “An introduction to probability theory and its applications,” 1957.