Задача кластеризації адрес в мережі блокчейн

Размещено на http://www.allbest.ru/

Задача кластеризації адрес в мережі блокчейн

Данильчук Руслан Костянтинович, студентНаціонального технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського»

Жураковська Оксана Сергіївна, доцент кафедри автоматизованих систем обробки інформації та управління, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

«КиевскийполитехническийинститутимениИгоряСикорского»

Анотація

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

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

Задача кластеризации адресов в сети блокчейн

Данильчук Руслан Константинович, студент, НациональноготехническогоуниверситетаУкраины «КиевскийполитехническийинститутимениИгоряСикорского»

Жураковская Оксана Сергеевна, доцент кафедрыавтоматизированных систем обработкиинформации и управления, НациональныйтехническийуниверситетУкраины

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

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

BLOCKCHAIN TRANSACTIONS ANALYSIS SYSTEM

DanylchukRuslan, StudentofNationalTechnicalUniversityofUkraine «IgorSikorskyKyivPolytechnicInstitute»

ZhurakovskaOksana, AssociateProfessoroftheDepartment ASOIU NationalTechnicalUniversityofUkraine «IgorSikorskyKyivPolytechnicInstitute»

Summary. Inthisarticle, thepracticalapplicationofthemethodofclusteringofaddressesintheblockadenetworkisconsideredontheexampleofthetaskofdeterminingthemultipleaddressesofoneuser. TheresultsofthestudyshowtheappropriatenessoftheproposedapproachtoclusteringBitcoinaddresses. ItmaybeusefulforuserstoavoiddangerouspatternsofBitcoinuse, andforresearcherstoconduct a moreadvancedanalysisofanonymity.

Keywords: blockchaintechnology, blocking, storageofdata, block, miner, participants, records, key, compatibilityofthenetwork, compatibilityofhashing.

Вступ

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

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

* захищеність;

* розподіленість;

* відкритість.

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

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

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

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

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

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

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

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

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

* обмеження обсягу набору даних;

* вибір міри близькості;

* негнучкість отриманих класифікацій.

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

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

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

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

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

*кінцевого багатоступеневого транзакційного входу А, де кожен вхід -- упорядкована пара адреси Аі і значення вхідного аі> 0.

*кінцевого багатоступеневого транзакційного виходу В, де кожен вихід -- це упорядкована пара адреси Ві і значення вихідного ві > 0.

*плати за транзакцію .

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

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

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

*тобто транзакція ї має рівно два виходи.

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

*Обидва виходи транзакції і, Вr та В2 не є обмінними адресами, тобто B1,B2rAddr(А).

*Один вихід транзакції Вr не існував до транзакції і, а десяткове подання значення Ь має більше ніж 4 цифри після крапки.

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

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

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

Кластеризація адрес Bitcoin, -- це розбивка на непересічні підмножини За допомогою позначимо сукупність всіх транзакцій, які задовольняють CS, або ОТС. Для транзакції і є Тн , через Addr_H (t) позначимо множину всіх адрес, які слід віднести до одного користувача відповідно.

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

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

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

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

*у випадку, якщо дві адреси (аі,а])?L контролюються тим самим користувачем з ймовірністю q.

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

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

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

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

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

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

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

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

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

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

Ат .

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

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

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

Висновки

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

Література

1. Nakamoto S. (2008) Bitcoin: A peer-to-peerelectroniccashsystem.

2. Інформаційні технології УДК 004,825 к.т.н. Волосюк Ю. В. (ЄУ, м. Миколаїв) Аналіз алгоритмів кластеризації для задач інтелектуального аналізу даних.

3. Ron D. andShamir A. (2012) Quantitativeanalysisofthefullbitcointransactiongraph. CryptologyePrintArchive, Report 2012/584.

Размещено на Allbest.ru