Выпуск №9 (Май) / Научный журнал "Интернаука" (2018 год) / Публикации журналов Издательского дома "Интернаука" / Internauka

Анотація. У даній статті розглянуто практичне застосування методу кластеризації адрес в мережі блокчейн на прикладі задачі визначення кількох адрес одного користувача. Результати дослідження показують доцільність пропонованого підходу до кластеризації адрес Bitcoin. Користувачам може бути корисно уникнути небезпечних моделей використання Bitcoin, а дослідникам провести більш розширений аналіз анонімності.

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

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

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

Summary. In this article, the practical application of the method of clustering of addresses in the blockade network is considered on the example of the task of determining the multiple addresses of one user. The results of the study show the appropriateness of the proposed approach to clustering Bitcoin addresses. It may be useful for users to avoid dangerous patterns of Bitcoin use, and for researchers to conduct a more advanced analysis of anonymity.

Key words: blockchain technology, blocking, storage of data, block, miner, participants, records, key, compatibility of the network, compatibility of hashing.

Вступ. Blockchain (з англ. block - блок, chain - ланцюг) - це ланцюжок блоків транзакцій, які зберігаються на комп'ютерах учасників ланцюжка. Кожен наступний блок пов'язаний з попереднім і складається з набору записів. Нові блоки завжди додаються лише в кінець цього ланцюжка [1].

Ланцюжок даних має три основні принципи:

захищеність;
розподіленість;
відкритість.

Всі учасники блокчейну об'єднуються в комп'ютерну мережу. На кожному сервері зберігається копія всіх даних блоку. Це і є основою надійності blockchain.

Адже, щоб зламати ланцюжок, потрібно отримати доступ до бази даних всіх комп'ютерів мережі.

Всі дані, що з'являються в блоках відкриті (користувачі бачать їх) і зашифровані (користувачі не знають, кому вони належать).

Приклад запису в мережі блокчейн: "Користувач з ключем К отримав у кредит телефон з ключем S".

Кожен користувач може мати декілька різних ключів. Тобто, навіть знаючи ключ власника телефону, не можна дізнатися про наявність у нього штрафу за порушення правил дорожнього руху.

Підходи до вирішення задачі кластеризації

На рисунку 1 представлена класифікація алгоритмів та методів кластерного аналізу.

Сутність ієрархічних агломеративних методів полягає у тому, що на першому кроці кожний об’єкт вибірки розглядається як окремий кластер. Процес об’єднання кластерів відбувається послідовно, на підставі матриці відстаней або матриці подібності поєднуються найбільш близькі об’єкти. Послідовність об’єднання легко піддається геометричній інтерпретації й може бути представлена у вигляді графа-дерева. Основною передумовою ієрархічних дивізивних методів є те, що спочатку всі об’єкти належать до одного кластеру. У процесі класифікації за певними правилами поступово від цього кластера відокремлюються групи схожих між собою об’єктів [2]. Так, на кожному кроці кількість кластерів зростає, а міра відстані між кластерами зменшується. Складнощі ієрархічних методів кластеризації наступні:

обмеження обсягу набору даних;
вибір міри близькості;
негнучкість отриманих класифікацій.

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

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

Алгоритм кластеризації адресів

Рис. 1. Класифікація алгоритмів та методів кластерного аналізу

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

Для аналізу транзакцій, окрема транзакція розглядається як упорядкована та складається з:

кінцевого багатоступеневого транзакційного входу A, де кожен вхід – упорядкована пара адреси і значення вхідного > 0.
кінцевого багатоступеневого транзакційного виходу B, де кожен вихід – це упорядкована пара адреси і значення вихідного ≥ 0.
плати за транзакцію

Для довільної множини транзакційних входів або виходів A позначаємо мультимережний адрес в A, як Addr(A).

Найбільш очевидною ідеєю для кластеризації адрес блокчейну є з'єднання всіх вхідних адрес однієї транзакції. Якщо дві або більше адрес є входами однієї транзакції з одним виходом, то всі ці адреси керуються тим самим користувачем [3].

Розглянемо транзакцію t = (A, B, c), що задовольняє умови одноразової зміни.

#Addr (B) = 2, тобто транзакція t має рівно два виходи.
#Addr(A) = 6 ≠ 2, тобто кількість входів t не є рівною двом. Якщо #Addr(A) = #Addr(B) = 2, транзакція, швидше за все, поділиться міткою передачі.
Обидва виходи транзакції t, B1 та B2 не є обмінними адресами, тобто.
Один вихід транзакції B1 не існував до транзакції t, а десяткове подання значення b1 має більше ніж 4 цифри після крапки.
Інший вихід транзакції B2 раніше був частиною мережі, і в попередніх транзакціях він не був адресований поза обліковим записом.

Розглянемо алгоритм кластеризації адрес на прикладі мережі Bitcoin, який регулює баланс інформації, що надходить безпосередньо з блоків Bitcoin (CS та OTC) та додаткову інформацію, зібрану з Інтернету у вигляді тегів.

Нехай T = {tj} і є набором всіх транзакцій в блоці біткойн, тоді як А є набором всіх адрес, що присутні в транзакції з T.

Кластеризація адрес Bitcoin – це розбивка на непересічні підмножини для j. За допомогою ⊂ T позначимо сукупність всіх транзакцій, які задовольняють CS, або OTC. Для транзакції t ∈, через позначимо множину всіх адрес, які слід віднести до одного користувача відповідно.

Інформація про теги представлена як сукупність негативних пар L = {()}. Пара адрес) ∈ L, якщо у нас є частина інформації про те, що ці адреси не контролюються одним і тим самим користувачем.

Слід зазначити, що як CS і OTC, так і позабіржова евристика і набір негативних пар L можуть містити помилкову інформацію.

Розглянемо різні типи спостережень:

у випадку, якщо всі адреси (t) для деяких t ∈ дійсно належать одному і тому ж користувачу з ймовірністю р;
у випадку, якщо дві адреси контролюються тим самим користувачем з ймовірністю q.

В інших випадках інформація про негативне об'єднання між будь-якою парою адрес в L перевіряється шляхом 1 - q.

Нехай ймовірність буде функцією від кластеризації A, транзакції та негативних пар L

де для деякого набору Bitcoin адреси S позначення S ⊂ Cl (A) означає, що існує кластер, такий, що S ⊆.

Отже, log-правдоподібність співвідноситься як

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

Максимізація log-правдоподібності – це задача дискретної оптимізації, яка фактично NP-повна.

Розглянемо ретроспективно всі транзакції в мережі Bitcoin, які задовольняють одну евристику. На кожному етапі вирішується, чи приєднуються кластери, що відповідають адресі) до розглянутої транзакції.

Нехай – об'єднання всіх кластерів, представники яких належать ().

Знайдемо зміни кількості негативних пар, що відповідають () в один кластер :

де Δ - це кількість негативних пар в кластері.

Тепер об'єднаємо всі кластери, що відповідають (), а отже зміна log-правдоподібності дорівнює

Таким чином, якщо є позитивним, то ми зливаємо всі кластери, що відповідають (), в іншому випадку потрібно продовжувати наступну транзакцію.

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

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

Література

Nakamoto S. (2008) Bitcoin: A peer-to-peer electronic cash system.
Інформаційні технології УДК 004,825 к.т.н. Волосюк Ю.В. (ЄУ, м. Миколаїв) Аналіз алгоритмів кластеризації для задач інтелектуального аналізу даних.
Ron D. and Shamir A. (2012) Quantitative analysis of the full bitcoin transaction graph. Cryptology ePrint Archive, Report 2012/584.