Мы працягваем наш цыкл аб прыладзе блокчейна Monero, і сённяшні артыкул будзе прысвечаны пратаколу RingCT (Ring Confidential Transactions), у якім прадстаўлены канфідэнцыйныя транзакцыі і новыя колцавыя подпісы. Нажаль, у інтэрнэце мала інфармацыі аб тым, як ён працуе, і мы паспрабавалі папоўніць гэты прабел.
Мы пагаворым аб тым, як з дапамогай гэтага пратакола сетка хавае сумы пераводаў, чаму адмовіліся ад класічных для cryptonote колцавых подпісаў і як гэтая тэхналогія будзе развівацца далей.
Паколькі гэты пратакол – адна з самых складаных тэхналогій у Monero, чытачу спатрэбяцца базавыя веды аб прыладзе гэтага блокчейна і павярхоўныя веды ў крыптаграфіі на эліптычных крывых (каб асвяжыць гэтыя веды, можна прачытаць першыя раздзелы нашага папярэдняга артыкула аб ).
Пратакол RingCT
Адна з магчымых нападаў на cryptonote-валюты - аналіз блокчейна, заснаваны на веданні сумы і часу адпраўленай транзакцыі. Гэта дазваляе значна звузіць вобласць пошуку якія цікавяць зламысніка вынахадаў. Для абароны ад такога аналізу ў Monero быў укаранёны пратакол ананімных транзакцый, які цалкам хавае сумы пераводаў у сеткі.
Варта адзначыць, што ідэя ўтойвання сум не новая. Адным з першых яе апісаў распрацоўшчык Bitcoin Core Грег Максвел у сваёй . Цяперашняя рэалізацыя RingCT выступае яе мадыфікацыяй з магчымасцю выкарыстання колцавых подпісаў (куды ўжо без іх), і так і атрымала сваю назву – Ring Confidential Transactions.
Апроч іншага пратакол дапамагае пазбавіцца ад праблем з замешваннем пылавых выхадаў - выхадаў на маленькую суму (звычайна атрымліваюцца ў выглядзе здачы ад транзакцый), якія стваралі праблем больш, чым каштавалі самі.
У студзені 2017 года адбыўся хардфорк сеткі Monero, які дазваляе апцыянальна выкарыстоўваць канфідэнцыйныя транзакцыі. А ўжо ў верасні таго ж года з хардфорка версіі 6 такія транзакцыі сталі адзінымі дазволенымі ў сетцы.
RingCT выкарыстоўвае адразу некалькі механізмаў: шматслойныя звязаныя спантанныя ананімныя групавыя подпісы (Multilayered Linkable Spontaneous Anonymous Group Signature, далей – MLSAG), схема абавязацельстваў (Pedersen Commitments) і range proofs (устоянага перакладу на рускую мову ў гэтага тэрміна).
Пратакол RingCT уводзіць два тыпы ананімных транзакцый: simple і full. Першыя кашалёк генеруе, калі транзакцыя выкарыстоўвае больш аднаго ўваходу, другія - у зваротнай сітуацыі. Адрозніваюцца яны валідацыяй сум транзакцый і падпісанымі MLSAG-подпісам дадзенымі (падрабязней пра гэта пагаворым ніжэй). Прычым транзакцыі тыпу full можна генераваць з любым лікам уваходаў, прынцыповай розніцы няма. У кнізе на гэты конт гаворыцца, што рашэнне абмежаваць full транзакцыі адным уваходам было прынята на хуткую руку і ў будучыні можа змяніцца.
MLSAG-подпіс
Успомнім, што з сябе ўяўляюць падпісаныя ўваходы транзакцыі. Кожная транзакцыя марнуе нейкія сродкі і генеруе. Генерацыя сродкаў адбываецца шляхам стварэння выхадаў транзакцыі (прамая аналогія - купюры), а выхад, які транзакцыя марнуе (бо ў рэальным жыцці трацім мы менавіта грашовыя купюры), становіцца ўваходам (асцярожна, тут вельмі лёгка заблытацца).
Уваход спасылаецца на некалькі выхадаў, але марнуе толькі адзін, такім чынам ствараючы "дымавую заслону", каб абцяжарыць аналіз гісторыі перакладаў. Калі транзакцыя мае больш аднаго ўваходу, то такую структуру можна прадставіць у выглядзе матрыцы, дзе радкі - гэта ўваходы, а слупкі - вымешванні, якія замешваюцца. Каб даказаць сеткі, што транзакцыя марнуе менавіта свае выхады (ведае іх сакрэтныя ключы), уваходы падпісваюць кальцавым подпісам. Такі подпіс дае гарантыю, што падпісант ведаў сакрэтныя ключы ад усіх элементаў якога-небудзь са слупкоў.
Канфідэнцыйныя транзакцыі больш не выкарыстоўваюць класічныя для колцавыя подпісы, на змену ім прыйшлі MLSAG - адаптаваная для некалькіх уваходаў версія аналагічных аднаслаёвых колцавых подпісаў, .
Шматслаёвымі яны завуцца таму, што падпісваюць адразу некалькі ўваходаў, кожны з якіх замяшаны з некалькімі іншымі, т. е. падпісваецца матрыца, а не адзін шэраг. Як мы ўбачым далей, гэта дапамагае зэканоміць на памеры подпісу.
Давайце разгледзім, як фарміруецца колцавы подпіс, на прыкладзе транзакцыі, якая марнуе 2 рэальных выхаду і выкарыстоўвае для замешвання m - 1 выпадковых з блокчейна. Абазначым публічныя ключы выхадаў, якія трацім, як
, а key images для іх адпаведна: Такім чынам, у нас атрымліваецца матрыца памерам 2 х m. Для пачатку нам трэба вылічыць так званыя challenges для кожнай пары выхадаў:
Вылічэнні пачынаем з выхадаў, якія трацім, выкарыстоўваючы іх публічныя ключы:і выпадковыя лікіУ выніку атрымліваем значэнні:
, якія выкарыстоўваем для вылічэння challenge
наступнай пары выхадаў (каб было прасцей зразумець, што куды падстаўляем, мы вылучылі гэтыя значэнні рознымі кветкамі). Усе наступныя значэнні разлічваюцца па крузе па формулах, прыведзеных на першай ілюстрацыі. Апошнім вылічаецца challenge для пары рэальных выхадаў.
Як мы бачым, ва ўсіх слупках, акрамя які змяшчае рэальныя выхады, выкарыстоўваюцца выпадкова згенераваныя лікі. Для π-го слупка яны нам таксама запатрабуюцца. Пераўтвараему s:
Сам подпіс уяўляе з сябе картэж усіх гэтых значэнняў:
Далей гэтыя дадзеныя запісваюцца ў транзакцыю.
Як мы бачым, MLSAG змяшчае ўсяго адзін challenge c0, што дазваляе зэканоміць на памеры подпісы (якія і без таго патрабуюць шмат месца). Далей любы правяраючы, выкарыстоўваючы дадзеныя, аднаўляе значэнні c1,…, cm і правярае, што. Такім чынам, наша кольца замкнулася і подпіс прайшоў праверку.
Для RingCT транзакцый тыпу full дадаецца яшчэ адзін радок да матрыцы з замяшанымі выхадамі, але пра гэта мы раскажам ніжэй.
Абавязацельствы Педэрсана
(часцей выкарыстоўваюць англамоўны тэрмін - commitments) выкарыстоўваюцца для таго, каб адзін бок мог даказаць, што ведае нейкі сакрэт (лік), фактычна не раскрываючы яго. Напрыклад, вы выкідваеце на касьцях нейкі лік, лічыце commitment і перадаеце яго правяраючаму боку. Такім чынам, у момант расчынення сакрэтнага ліку правяраючы самастойна лічыць commitment, тым самым пераконваючыся, што вы яго не падманулі.
У Monero commitments выкарыстоўваюцца для ўтойвання сум перакладаў і ўжываюць самы распаўсюджаны варыянт - Pedersen commitments. Дарэчы, цікавы факт - спачатку распрацоўшчыкі прапаноўвалі хаваць сумы звычайным замешваннем, гэта значыць дадаваць выхады на адвольныя сумы, каб унесці нявызначанасць, але потым перайшлі на commitments (пры гэтым не факт, што зэканомілі на памеры транзакцыі, як мы ўбачым ніжэй).
У агульным выпадку commitment выглядае наступным чынам:
Дзе C - значэнне самога commitment, a - хаваная сума, H - Фіксаваная кропка на эліптычнай крывой (дадатковы генератар), а x - Нейкая адвольная маска, які хавае фактар, які генеруецца выпадковым чынам. Маска тут патрэбна для таго, каб трэці бок не змог простым пераборам падабраць значэнне commitment.
Пры генерацыі новага выйсця кашалёк разлічвае для яго commitment, а пры расходаванні бярэ альбо разлічанае пры генерацыі значэнне, альбо пералічвае яго нанова – у залежнасці ад тыпу транзакцыі.
RingCT simple
У выпадку simple RingCT транзакцый для таго, каб гарантаваць, што транзакцыя стварыла выхады на суму роўную суме ўваходаў (не зрабіла грошы з паветра) трэба, каб сума commitments першых і другіх была аднолькавай, гэта значыць:
Commitment камісіі лічаць крыху інакш - без маскі:
, Дзе a - сума камісіі, яна публічна даступная.
Такі падыход дазваляе даказаць правяраючаму боку, што мы выкарыстоўваем аднолькавыя сумы, не раскрываючы іх.
Каб усё стала больш зразумела, давайце разгледзім прыклад. Дапушчальны, транзакцыя марнуе два вынахаду (гэта значыць яны становяцца ўваходамі) на 10 і 5 XMR і генеруе тры вынахаду на суму 12 XMR: 3, 4 і 5 XMR. Пры гэтым плаціць камісію 3 XMR. Такім чынам, сума выдаткаваных грошай плюс сума згенераваных і камісія роўныя 15 XMR. Давайце паспрабуем разлічыць commitments і паглядзім на рознасць іх сум (успомнім матэматыку):
Тут мы бачым, каб ураўненне сышлося — сумы масак уваходаў і выхадаў нам патрэбны аднолькавымі. Для гэтага кашалёк генеруе выпадковым чынам x1, y1, y2 і y3, а пакінуты x2 разлічвае так:
Выкарыстоўваючы гэтыя маскі, мы можам даказаць любому правяральшчыку, што мы не генеруем сродкаў больш, чым трацім, не раскрываючы сумы. Арыгінальна, праўда?
RingCT full
У full RingCT транзакцыях праверка сум пераводаў праходзіць некалькі больш вычварна. У гэтых транзакцыях кашалёк не пералічвае commitments для ўваходаў, а выкарыстоўвае разлічаныя пры іх генерацыі. Пры гэтым трэба меркаваць, што рознасць сум мы ўжо не атрымаем роўнай нулю, а замест гэтага:
Тут z - рознасць масак уваходаў і выхадаў. Калі разглядаць zG як публічны ключ (чым ён дэ-факта і з'яўляецца), то z - Гэта прыватны ключ. Такім чынам, мы ведаем публічны і адпаведны яму прыватны ключы. Маючы гэтыя дадзеныя, мы можам выкарыстоўваць іх у кальцавой подпісы MLSAG разам з публічнымі ключамі замешваецца выхадаў:
Такім чынам, валідны кальцавы подпіс будзе гарантаваць, што мы ведаем усе прыватныя ключы аднаго са слупкоў, а прыватны ключ у апошнім радку мы можам ведаць толькі калі транзакцыя не генеруе сродкаў больш, чым траціць. Дарэчы, тут жа адказ на пытанне "чаму тут рознасць сум commitments не прыводзяць да нуля" – калі zG = 0, то мы раскрыем слупок з рэальнымі выхадамі.
А як жа атрымальнік сродкаў даведаецца колькі грошай яму даслалі? Тут усё проста - адпраўнік транзакцыі і атрымальнік абменьваюцца ключамі па пратаколе Дыфі-Хеллмана, выкарыстоўваючы ключ транзакцыі і view-ключ атрымальніка і вылічаюць агульны сакрэт. Адпраўнік запісвае ў спецыяльныя палі транзакцыі дадзеныя аб сумах выхадаў, зашыфраваныя гэтым агульным ключом.
Range proofs
А што будзе, калі ў якасці сумы ў commitments выкарыстоўваць адмоўны лік? Гэта можа прывесці да генерацыі дадатковых манет! Такі зыход недапушчальны, таму патрэбна гарантыя, што выкарыстоўваныя намі сумы не адмоўныя (без расчынення гэтых сум, зразумела, інакш гэтулькі працы і ўсё дарма). Іншымі словамі, мы павінны даказаць, што сума знаходзіцца ў інтэрвале [0, 2n - 1].
Для гэтага сума кожнага выхаду разбіваецца на двайковыя разрады і лічыцца commitment па кожным разрадзе асобна. Як гэта адбываецца, лепш разгледзець на прыкладзе.
Дапусцім, што сумы ў нас невялікія і змяшчаюцца ў 4 біта (на практыцы гэта 64 біта), а мы ствараем выхад на суму 5 XMR. Лічым commitments для кожнага разраду і агульны commitment на ўсю суму:
Далей кожны commitment замешваецца з сурагатным (Ci-2iH) і папарна падпісваецца кальцавым подпісам Барамеа (яшчэ адзін кальцавы подпіс), прапанаваным Грегам Максвелам у 2015 годзе (падрабязней пра яго можна пачытаць ):
Усё разам гэта называецца range proof і дазваляе гарантаваць, што ў commitments выкарыстоўваюцца сумы ў інтэрвале [0, 2n - 1].
Што далей?
У бягучай рэалізацыі range proofs займаюць вельмі шмат месца – 6176 байт на адзін выхад. Гэта вядзе да буйных транзакцый і, адпаведна, больш высокім камісіям. Каб знізіць памер транзакцыі Monero распрацоўшчыкі ўводзяць замест подпісаў Баррамеа bulletproofs – механізм range proof без пабітавых commitments. , Яны здольныя скараціць памер range proof да 94%. Дарэчы, у сярэдзіне ліпеня тэхналогія прайшла ад кампаніі Kudelski Security, якая не выявіла істотных недахопаў як у самой тэхналогіі, так і ў яе рэалізацыі. Тэхналогія ўжо прымяняецца ў тэставай сетцы, а з новым хардфоркам, верагодна, можа пераехаць і ў асноўную сетку.
Задавайце свае пытанні, прапануйце тэмы для новых артыкулаў аб тэхналогіях у галіне криптовалют, а таксама падпісвайцеся на нашу групу ў , Каб быць у курсе нашых падзей і публікацый.
Крыніца: habr.com