title txtВъведение в книгата. Има много вълнение за биткойн и криптовалути. Чуваме за стартиращи фирми, инвестиции, срещи и дори за купуване на пица с биткойн. Оптимистите твърдят, че биткойнът ще бъде фундаментално разбит и ще претърпи нова политика по света. Песимистите твърдят, че биткойн плащания, икономика , и дори по същество В основата на тези различни възгледи стои значително объркване относно това какво е биткойн и как е написал тази книга, за да помогне да се пресече рекламата и да се стигне до същността на това, което прави биткойн уникален. За да разберем наистина какво е специалното на биткойн, трябва да разберем как работи на техническо ниво Биткойн наистина е нова технология и можем да стигнем толкова далеч, като я обясним чрез аналогии с минали технологии. Ще приемем, че имате основни познания за компютърните науки как работят компютрите
структури и алгоритми и известен опит в програмирането Ако сте бакалавър или студент по компютърни науки, софтуерен разработчик, предприемач или любител, този учебник е за вас. В тази поредица от единадесет глави ще разгледаме важните въпроси относно биткойн Как работи биткойн? Какво го прави различен? Колко сигурни са вашите биткойни? Колко анонимни са потребителите на coIn? Какви приложения можем да създадем, използвайки биткойн като платформа? Могат ли криптовалутите да бъдат забранени? Ако днес проектирахме нова криптовалута, какво щяхме да променим? Какво очаква бъдещето? Всяка глава има поредица от въпроси за домашна работа, които да ви помогнат да разберете тези въпроси на ниво. Горещо ви препоръчваме да работите по тях. Освен това има поредица от пет програмни задачи, в които ще внедрите различни компоненти на биткойн в опростени модели, ако сте слухов обучаем, по-голямата част от материала в тази книга също е достъпен, ако трябва също да допълните информацията си за учене можете да намерите онлайн уики за биткойн, форуми и научни статии и като взаимодействате с вашите колеги биткойн общност
е следното: ако H има n-битов изход, тогава той може да приеме всяка от 2" стойности Решаването на пъзела изисква намиране на вход, така че изходът да попада в набора y, който обикновено е много по-малък от размера на y открийте колко труден е пъзелът. Ако y е setbit streas, ако Y има само 1 елемент, пъзелът е максимално труден. Фактът, че идентификаторът на пъзела има висока минимална ентропия, гарантира, че няма преки пътища. Напротив, ако конкретен, някой може да измами, да речем, като изчисли решение към пъзела. Ако пъзелът за търсене е пъзел-удобен, това означава, че няма стратегия за решаване на този пъзел, която съществува, можем да го направим по този начин, стига да можем да генерираме пъзел- IDs в stse тази идея по-късно, когато говорим за bSHA -256 Обсъдихме три свойства на хеш функциите и едно приложение. Сега нека обсъдим конкретна хеш функция, която ще използваме често в тази книга, съществува много функция за хеш
но това е този, който използва първични данни, наречени sHA-256. Спомнете си, че ние изискваме нашите hasons работни данни с произволна дължина. За щастие, докато можем да изградим хеш функция, която работи на входове с фиксирана дължина, има общ метод за преобразуване на itrks на произволна дължина входове Нарича се преобразуване на Merkle-Damgard. SHA-256 е една от редица комбинирани хеш функции, които използват този методобща терминология, основната устойчива на сблъсък хеш функция с фиксирана дължина се нарича функция за компресиране Доказано е, че ако основната функция за компресиране е сблъсъкttrd tnple Кажете tiakes inputs на lenand произвежда изход с по-малка дължина n входа към хеш функцията, който може да бъде с всякакъв размер, разделен на блоковеconstruction работи както следва, изходът на preere не е предишен изход на блок, вместо това използваме инициализиращ вектор (v) Този номер се използва повторно за всяко извикване на хеш функцията и на практика вие извеждате стандартна документация, която приема 768-битови входни данни и произвежда 256-битови изходни данни,
512 bitsessageMessage(блок 1)(блок 2)(блок n256 бита 256 бита Фигура 13: Хеш функция SHA-256 (опростена/ SHA-256 използва трансформацията на Merkle-Damgard, за да превърне компресирането на коли с фиксирана дължина в хеш функция Говорихме за хеш функции, криптографски hasjons със специални свойства, прилагане на тези свойства и специфична хеш функция, която използваме в биткойн В следващия дискутираме начини за използване на хеш функции за изграждане на по-сложни структури от данни, които се използват12 Хеш указатели и структури от данни за dhash указатели и thA hasha datamply указател където се съхранява някаква информация заедно с криптографска ха-формация
Докато обикновеният указател ви дава начин да извлечете информацията, хеш указателят също ви дава начин да проверите дали информацията не се е променилаH()фигура 1 4 Хеш указател хеш указателят е указател към мястото, където данните се съхраняват заедно с aat данни ae фиксирана точка в til
shbuildds на структури от данни, ние можем да вземем позната структура на данни, използваща указатели като връзка или двоично дърво за търсене, и да ги внедрим с указатели, вместо pBlock chaiФигура 15, ние създадохме списък с помощта на хеш ps Ще структурираме блокова верига, докато като обикновен свързан списък, където има поредица от блокове, eaclblock има dataointer към предишния блок в списъка в блокова верига, theblockeaof thprevious block was, но също така съдържа обобщение на тази стойност, което ни позволява да проверим дали valuee съхранява най-новия блок с данниH(1 )пред.: H()пред.:H()I предиш.: H(dataatadataФигура 15 Блокова верига
веригата на блокове е свързан списък, който е изграден с хеш указатели вместо указатели, а случаят на използване на веригата на блокове е видим за подправяне дневник, което означава, че искаме да изградим дневник с данни от данни и дневникът, ние ще за да го открием, за да разберем защо даден блок нарушава това свойство за видимо подправяне, нека попитаме какво се случва, ако противникът иска да подправи данни, които са в средата. По-конкретно, веригата adversarysdshblock няма да може да открие подправянето. За да постигне тази цел, противникът променя данните на някой блок k Тъй като данните са двойни, хешът в блока k+1ash няма да свърже промененото съдържание, тъй като хеш функцията е устойчива на сблъсък и така ние широко откриваме несъответствието k и тази промяна, като променяме списъка По-конкретно, докато съхраняваме хеш указателя в началото на списъка на място, където ще бъде открит противникът
Резултатът от това е, че ако противникът иска да фалшифицира данни където и да е в тази среда, за да поддържа историята последователна, той ще трябва да фалшифицира елементите чак до началото и в крайна сметка той също се превръща в пречка, за да не може да се справи с главата на списъка Така се оказва, че като просто сме запомнили доказващ подправяне хеш на целия списък, така че можем да изградим блокова верига, която ще наречем генезис блок, а конструкцията на блоковата верига е подобна на раздела за конструкции на Merkle-Damgard Наистина, те са доста сходни и един и същ аргумент за сигурност се прилага и за двата pre H(preAH()atadataФигура 16 Дневник за фалшифициране
Ако противник модифицира данни където и да е във веригата на блокове, това ще доведе до това, че блокът е включен. Ако съхраним главата на противника, който променя всички указатели, за да бъдат в съответствие с модифицираните данни, главата показва, че открива дърветата tampeMerkle. Друга полезна структура от данни, която използването на хеш указатели е двоично дърво Анарното дърво с хеш указатели е известно като дърво на Меркъл, след неговия изобретател Ралф Меркъл. Да предположим, че имаме няколко блока, съдържащи данни, тези блокове данни в двойки по два и след това за всяка двойка изграждаме структура от данни, която има два hasr-а, един от които, благодаря. Тези структури от данни ги групират в групи от по две и forair създават нова структура от данни, която съдържа хеша на всеки. Продължаваме да правим това, докато стигнем до един блок, корена на дървото
H(1)H(1)H(1)H(1)H(1)H(H()H(、)H()H(1)H()H(1))H(、 )(data(data)(data)(dataФигура 1 7 Дърво на Merkle В дърво на Merkle блоковете с данни са групирани, като всеки от тези блокове се съхранява в родителски възел, родителските възли на свой ред са групирани по двойки и техните хешове се съхраняват едно ниво нагоре в дървото
Това продължава по целия път нагоре в дървото, докато стигнем до основния възел. Както преди, помним само хеш-указателя в началото на дървото. Вече имаме способността да прескачаме надолу през хеш-указателите към всяка точка в данните, която не е била подправени поради това, използвайте блокови chaers с някакъв блок данни в долната част на хештера, който не съвпада, и дори ако той продължи да подправя този блок, промяната в крайна сметка ще се разпространи до върха на дървото, където той няма да може да подправя хеш-показателят, който се съхранява Така че отново, всеки опит за манипулиране на която и да е част от данните ще бъде открит само чрез запомнянеopДоказателство за членство Друга хубава характеристика на merkle дърветата е, че за разлика от блоковата верига, която изградихмеoprove, че определено помни justoot, след което се връща по пътя от блока с данни до дървото, тъй като блоковете по този път са достатъчни, за да ни позволят да проверим хешовете по целия път до rks, в дървото има n възли, само около log n) елемента трябва да бъдат показани и тъй като всяка стъпка просто изисква изчисляване на хеша на дъщерния блок, отнема около log(n време, за да го проверим и трезво от блокове сравнително кратко време, проверката по този начин се изпълнява във времето и пространството, които са логаритмични
възли в дървотоH(1)H()H()H(1)Фигура 1 8 Доказателство за членствоe, че блок с данни показва блоковете по пътя от този блок с данни до коренаСортирано merkle дърво е просто merkle дърво където вземаме блоковете в долната част и ги сортираме, като използваме някаква функция за подреждане, това може да бъде азбучен, лексикографски ред, числов ред, или покрив на нечленуване със сортирано дърво на Merkle, става възможно да се провери не-членствотопогаритмично време и пространство, което е , можем да докажем, че конкретен блок не е в дървото на merkle, въпросът би бил и показване на пътя до елемента, който е точно след мястото, където би бил
Ако тези два са между двата показани елемента, но между тях. Обсъдихме използването на хеш указатели в свързани списъци и двоични дървета, но по-общо се оказва, че можем да използваме хеш указатели във всяка базирана на указател структура от данни, стига структурата на данните да не 't haveIf thdata структура thenbe abakehashes съвпадат. Ако мислите за ациклична структура на данни, ние можем да стартираме, но нямаме никаква точка от изчисляването на хешоветеd началото, но в структура с цикли, няма край, с който можем да започнем и да изчислим обратно frobuild a directedof хеш указатели an
можете да проверите членството в тази графика много ефективно и ще бъде лесно да се изчисли. Използването на хеш-указатели по този начин е общ трик, който ще видите времето и контекста на разпределените структури от данни и в целия алгоритъм по-късно в тази глава и13 Digital Signaturesis раздел, ние ще разгледаме digitalisIs функцията secog с хеш блокове forytonproperties от цифрови подписи, които съответстват добре на аналогията на ръкописния подпис, първо уверете, че е валиден подписът да бъде обвързан с конкретен документ, така че подписът да не може да се използва, за да посочи, че свойството е аналогично за да гарантираме, че някой не може да вземе подписа ви и да го отреже от един дъното на друг, можем ли да изградим това в цифрова форма, използвайки криптография Първи предишен интуитивна дискусия малко по-конкретна
Това ще ни позволи да разсъждаваме по-добре относно схемите за цифров подпис ss техните свойства за сигурност Схема за цифров подпис a digital sith(sk, pk): generateKeys(keysize) Методът generateKeys взема размер на ключ и генерираThekey sk е kesig:=sign(sk, message) Методът sign взема съобщение, msg и ключ erify yourrybody Anyoseret, sk, asut и извежда подпис за съобщението под skify(pk, message, sig) Методът verify приема съобщение, подпис и ae isvalidbe truekey pk и невалидните подписи трябва да се проверяват)) Подписите са екзистенциално неподправими. Отбелязваме, че генерирането на ключове и подписването могат да бъдат рандомизирани алгоритми. Наистина генерирането на ключове се е подобрило, защото трябва да генерира различни ключове за различни хора, проверете двете свойства, които изискваме от схема за цифров подпис в повече d
etaie first свойство е просто - че валидните подписи трябва да проверят Ако подпиша съобщение със sk, mysecret ключ и някой по-късно се опита да потвърди този подпис върху същото съобщение, използвайки моя pubГлава 1: Въведение в криптографията Криптовалути за контрол на доставките и rtiesfiat cus контролирайте паричното предлагане, подлежащо на фалшифициране В крайна сметка правилата на правоприлагащите органи предотвратяват хората от хората Ако Алис убеди Боб, че му е платила цифрова услуга, тя не би трябвало да е в състояние да използва криптовалутите в голяма степен криптографията Криптографията е свързана с математически протокол
Преди да успеем да разберем правилно криптовалутите, Cat са известни с фините и сложни за разбиране. За щастие биткойнът разчита само на ефективно изучаване на криптографски хешове и цифрови подписи, два примитиви, които се оказват много въвеждат по-сложни cchofs, които се използват в предложената разширена модификация, след като научихме необходимото cryptographicves, ще обсъдим някои от създадените криптовалути. Ще завършим тази глава с някои примери за 11 криптографски хеш функции. Първият криптографски примитив, който трябва да разберем, е криптографска хеш функция. Ahash функция. че за даден низ вие
tput на този за определяне на хеша на n-битов низ трябва да има време на изпълнение, което е o(n)on криптографски хеш fube криптографски защитено, предполагахме, че има следните три добавки Ще разгледаме по-отблизо всяко от тези свойства, за да разберете защо е полезна функцията, която се държи по този начин, читателят, който е изучавал криптография, трябва да е наясно, че обработката на хеш функциятази книга е малко по-различна от стандартния учебник по криптография Thenctions, но такава, която ще бъде полезна специално за криптовалутите Свойство 1: Сблъсък -устойчивост Първото свойство, от което се нуждаем, е устойчивост на сблъсък
възниква, когато двама различни произвеждат един и същ изход AHsistant if nobody FormallyCollision-resistance: A да бъде устойчив на сблъсък, ако е възможно да се намерят две стойности, x и yatx≠y, все пакH(x)=H(yФигура 11 Хеш сблъсък x и y са различни стойности , ощеnвъведени в хеш функция H, те забелязват, че казахме, че никой не може да намери сблъсък, но не съществуват сблъсъци. Всъщност ние знаем със сигурност, че сблъсъци съществуват и това е чрез сестрини с определена фиксирана дължина, тъй като входното пространство е по-голямо от изходно пространство (наистина tlame изходен низ. Всъщност по принципа на гълъба непременно ще има много голям брой
възможни изходивъзможни входовеФигура 12 Тъй като необходимият брой изходи, за които сме гарантирани, трябва да бъде поне един изход, към който хеш функцията нанася повече от един вход. Сега, за да направим нещата още по-лоши, казахме, че трябва да е невъзможно да се намери сблъсък И все пак трябва да се намери сблъсък. Обмислете метода за финолизия за хеш функция с 256-битов изходен размер: изберете 2 различни стойности, изчислете хеш и проверете дали двата изхода са повече от възможните изхода, някои двойки от тях трябва да се сблъскат, когато приложите метода на хеш функцията по-горе гарантирано ще намери сблъсък, но ако изберем произволни входове и ги изчислим с висока вероятност много преди 2+1 входа. Всъщност, ако произволно изберем само 2+1 входа, се оказва, че има 99
8% шанс поне двама от тях да се сблъскат Фактът, че можем да намерим сблъсък, като изследваме само грубо квадратния корен от възможността, известен като парадокса на рождения ден Във въпросите за домашна работа в края на тази глава ще разгледаме това в повече алгоритъм за откриване на detacollision работи за всяка хеш функция, но, разбира се, проблемът с него е ti6tpnction 2250+1 пъти в най-лошия случай и около 22 типа компютър изчислява 10 000 hdde bybeof tlodds, които установяват, че земният метеор е видял общ практически алгоритъм за намиране на хеш функция за сблъсък Може да се използваdeh theision deithне е възможно да се използва, все пак може да има някакъв друг алгоритъм, който може ефективно да намери сблъсък за afic хеш функция Обмислете за
H(x)=x modfunction отговаря на хеш функция, тъй като въвежда изход с фиксиран размер (256 бита) и е ефективно изчислима. Но тази функция също има ефективен метод за намиране на сблъсък Забележете, че тази функция просто връща последния 256 бита от входа Едно би било стойностите Генеричният метод за откриване на сблъсък не е използваем на практика има поне някои хеш функции за метода съществува такъв показател Въпреки това няма хакове, доказано устойчиви Криптографските хеш функции, на които разчитаме на практика, са само за целта на pd сблъсъци и не са успели в някои случаи, като например старата md5 хеш функция, намерена след като функцията yehe е отхвърлена и постепенно изведена от практическа употреба И затова избираме да вярваме, че това са устойчиви на сблъсъци дайджести Сега, когато знаем какво е полезно за HeАко знаем, че два входа x и устойчивата на сблъсък хеш функция h имат различни хешове, тогава е безопасно да приемем, че x и y са различни - ако някой знае x и y, които са различни, но имат един и същ хеш, това би нарушило нашето предположение, че Аргументът h е устойчив на сблъсък ни позволява да използваме хеш изходите като обобщение на съобщението. Помислете за Secure Box, удостоверена онлайн система за съхранение на файлове, която позволява на потребителите да качват файлове и да гарантират тяхната цялост на този файл, и иска да може да провери, след като файлът, който изтегля, е същият като този, който тя качва
един от начините да направи това би бил да запази файла, който изтегля, докато това работи с целостта, тя може просто да използва локалното копие директно Хешове без сблъсъци pt и ефективно решение Алис просто трябва да изчисли хеша на изтегления файл и да го сравни с този тя е съхранила Ако хешовете са тези, които е качила, но ако са различни, тогава Алиса може да заключи, че файлът е бил манипулиран, запомня хеша, като по този начин й позволява да открие случайно повреда на файла по време на предаване или на сървърите на Secure Box, но също и непреднамерена модификация на файл от сървъра Такива гаранции в лицето на потенциално злонамерено поведение от други субекти Хешът служи като дайджест с фиксирана дължина или недвусмислено резюме на съобщение, което ни дава много ефикасен начин да запомним неща, които сме виждали преди, и да ги разпознаем отново, докато efile може са дълги гигабайти, хешът е с фиксирана дължина, 256-бита за hle. Това значително намалява и в цялата книга ще видим приложения, за които е полезно да се използва хеш като копие на съобщения
Свойство 2: Скриване Второто свойство, което искаме от нашите хеш функции, е свойството hidinghiding твърди, че ако ни бъде даден изходът на хеш функцията y H(x), няма възможност да коригираме формата за въвеждане. Разгледайте следния прост пример: ще направим експеримент, при който обръщаме coire резултат от хвърлянето на монета беше heads щяха да обявят хеша на низа"headsразберете какъв е низът, който беше хеширан (скоро ще видим защо може да искаме да играем игри liketring"tails" и те можеха да видят коя им е дадена Andust няколко стъпки, те разбираха какъв е низът, защото имаше само две възможни стойности на x и за противника беше лесно просто да опита и двете по ред за да можем да постигнем hidingperty, трябва да е така, че няма стойност на x, която е особено вероятно да е, в известен смисъл, много разпръсната. Ако x е избран от такъв набор, този метод. Големият въпрос е: можем ли да постигнем свойството за скриване, когато стойностите, които искаме, не идват от разпределен набор като orrhaput thatad out byspread out Вече можем да бъдем малко по-прецизни meag (двойната vertia обозначава конкатенация) Скриване на хеш фондскриване ако: когато тайна стойност r е избрано от вероятностно разпределение, което има висока минимална ентропия, тогава като се има предвид h(r/x), че е невъзможно да се намери теория на формирането на x, минималната ентропия е мярка за това колко предсказуема извънредна хиглимин-ентропия улавя интуитивната идея, че разпределението разпределението, което е вероятно да се случи Така че, за конкретен пример, ако r е избран равномерно измежду всички низове, които са 256 бита, низът е избран с вероятност 1/2256, wlПриложение: Ангажименти
Сега нека да разгледаме приложението на свойството за скриване. По-специално, какво да правиш ангажимент, ангажиментът е цифрата на вземането, ако направиш това, ти си се ангажирал с това, което е вътре в плика, но не си „отворил, въпреки че“ посветих се на стойност стойността остава тайна за всички останали По-късно можете да отворите плика и да разкриете стойността, която сте поели по-рано
sts of(com): =commit(msg, key) Функцията commit приема съобщение и таен ключ като inputd връща commitmeValid verify(com, key, msg) Функцията verify приема ключ за ангажиране и messageas го въвежда връща true, ако ceWBinding: За всяка стойност на ключ е невъзможно да се намерят две съобщения, msg и msg'such thamsg msgand verify(commit(msg, key), key, msg)==trueeme, едното се ангажира със стойност и публикува ангажимента е аналогичен на поставянето на запечатания плик на масата на по-късен етап, ако искат да публикуват ключовия ключ и стойността, msgможе да провери дали msg наистина е била ангажираната по-рано стойност, този етап е аналогичен на отваряне на upe пликове диктуват че thvelope Първо, като се има предвид com, ангажиментът, някой, който гледа съобщението в плика, е Второто свойство е, че е обвързващо, че когато се ангажирате с това, което е в thevelope, не можете да промените решението си по-късно
Това означава, че е невъзможно да намерите две различни съобщения, като например можете да комулирате съобщение и след това по-късно да заявите, че сте се ангажирали с друго. И така, как да знаем, че тези две свойства са валидни? Преди да можем да отговорим на това, трябва да обсъдим схемата. Можем да го направим с помощта на ангажимент за криптиране schemcommit(msg): =(H(key /msg), keyo, където ключът е произволен 256-битов vi· verify(com, key msg ):= вярно, ако H(key∥com; false в противен случай, генериране на случаен 256-bihich ще служи като ked, тогава ние връщаме хеша на съобщението и те ще бъдат равни на ангажимента, който са видели за инстанцията на ангажиране и проверка, както и h(key l msg) за com, след това тези свойстваHkey∥msg, infeasib|eBinding: За всяка стойност на ключ е невъзможно да се намерят две съобщения, msg и msg, така че msg≠ msg'и H(key∥msg)=H (клавиш∥съобщение
Скриващото свойство на ангажиментите е точно скриващото свойство, което изисквахме за нашите haslfunctions. Ако ключът беше избран като произволна 256-битова стойност, тогава скриващото свойство казва, че ако имаме осъществимо съобщението от hashput И се оказва, че обвързването свойство се подразбира от свойството за устойчивост на сблъсък на хеш функцията, устойчива на хеш функцията, тогава ще бъде невъзможно да се посочат стойности msg и msg', така че h(key msg) =h(key msg), тъй като такива стойности биха били, ако h е хеш функция, която е постоянна и крие този ангажимент schee усеща, че ще има необходимите свойства за сигурност Свойство 3: Удобство за пъзел Третото свойство за сигурност, от което се нуждаем от хеш функциите, е удобно за suzzle
е btedfirst ewhatproperty е полезно Удобство за пъзел хеш функция H се казва, че е удобен за пъзел, ако за всеки възможен n-битов изход, ако k е избрано от разпределение с висока минимална ентропия, тогава е неосъществимо във време, значително по-малко от 2итуитивно ,това означава, че ако има цел хеш функцията да излезе до някаква конкретна изходна стойност y, че ако има част от входа, която е избрана по подходящ рандомизиран начин, стойността на difffinder отговаря точно на тази цел. Приложение: Пъзел за търсене Сега, свойство В това приложение, ние ще изградим пъзел за търсене математически проблем, който, за да намерим преките пътища Това е, че няма начин да намерим валидно решение, освен да търсим това голямо пространствоПъзел за търсене Aonists of the puzzle-/D), selectedch thatH(id‖ x)∈възможно е да намерите колформата hike∥H(ключ∥