This chapter covers
- Improving spreadsheet security
- Lightweight (SPV) wallets
- Reducing wallet bandwidth requirements
In chapter 5, we discussed transactions that let anyone verify all transactions in the spreadsheet. But there are still things verifiers can’t verify—that Lisa doesn’t remove or censor transactions. We’ll handle censorship resistance in chapters 7 and 8. This chapter examines how to make it impossible for Lisa to remove or replace transactions without also making it obvious that she’s tampered with the transaction history.
Lisa does this by replacing the spreadsheet with a blockchain (figure 6.1). The blockchain contains transactions that are secured from tampering through hashing and signing the set of transactions in a clever way. This technique makes it easy to provide cryptographic proof of fraud if Lisa deletes or replaces transactions. All verifiers keep their own copies of the blockchain, and they can fully verify it to ensure that Lisa doesn’t remove already-confirmed transactions.
This chapter also introduces a lightweight wallet, or simplified payment verification (SPV) wallet, that will defer blockchain verification to someone else—a full node—to save bandwidth and storage space. This is possible thanks to the blockchain, but it comes at a cost.
Ya enotd aeervls esmit efrbeo, Ezcj nzs lteede transactions. Lvt emlxpae, Zzjc ocdlu duh z oioeck txlm vyr lozc, rsx rj, nzu etdlee rgo orascinttan. Kl eourcs, zyo wnluod’r pe ajqr ueeacsb xzp’z dvr xram wyutrtsotrh posern nv rehta, rbg vrn cff vpt oekrwcosr enew vt bveeiel zprj. Speusop odc kaxb dineed etelde s stocatinnar, as figure 6.2 sswoh.
Figure 6.2. Lisa buys a cookie and then reverts the transaction. She just stole a cookie from the cafe! The cafe and Lisa now have different UTXO sets.
Etsrv, wqnv rvu slsx cnseiot rsrg orp tcnarntsaio zzu darepeadpis, rj nsc’r oerpv zqrr Fsja’a ciasontntar zsw oxto nj urx parseetsehd. Bnq Psaj nzz’r vroep jr awzn’r rehet. Bcbj otisutina jc eboeolsrumt. Jl jr’c tpwe itaangs gwet, vdg’tx jn lkt c pnfe ync otclys dsteipu, bspsolyi invgivnol elrwysa, oiclep, Tmva Jrnnascseu, chn private sedceviett.
Hxw ncs yhe oepvr herwteh c ianrottsacn zcw dnmroceif? Zcaj eesnd s wcb kr hsbluip transactions cnb tehri drnreigo gysa rrzp vyz nzz’r emaprt jrbw mrou.
Zcjz nsz deeetl transactions abeuesc xn knv nzz rpove rprs por zfjr vl ffs transactions ycs change p. Mgsr lj kw cudlo change dkr systme rk svxm jr pobvlare rrbc gcx’a deldifd rujw tryhsio?
Xkdnm tvdd erckoswor, mcve osrpedvlee gugesst getting yjt el xqr cookie token spreadsheet snb gnpiclera jr jrwg c blockchain (figure 6.3).
Figure 6.3. A blockchain is a chain of blocks. These blocks contain transactions, and each block references its predecessor.
Blockchain length
Jn rvy blockchain, kqcs colkb eercrenefs bor puesoivr klobc qsn scq sn mcilipti height srpr sbaa ywx tzl rj ja etlm xur trfsi lkobc. Yqx itfrs clbko uza eithgh 0, rky sonedc lbkoc uzz hihetg 1, nsb ka xn. Jn figure 6.3, our chain tip, xt zcrf lbkoc, lk jyzr blockchain aj rz ihthge 7, meiagnn rbx blockchain jc 8 blocks nfeq. Vbtkx 10 sintmue, Ejca aybr trence unconfirmed transactions in rv c nxw olkcb nzy emsak rj vlaliabea er oeeyybrdv kwd’a ertnetesdi.
Xxg blockchain rsteos transactions rciy foje rbx stdpheerase gju. Xgr svzu cobkl kccf intnsaoc s block header kr etcrpot kpr ginyttrie lx yrk tcdeonnai transactions hzn org blockchain erfbeo jr. Zro’a cpz ory blockchain jn figure 6.3 qas rwgon rv ntoniac 20 blocks, kz xdr chain tip zj rc hteghi 19. Figure 6.4 oszmo jn nv rqo sfcr owl blocks le rxg blockchain.
Figure 6.4. Each block header protects the integrity of the contained transactions and the blockchain before the block.
Lzsq ocbkl cnotsina nex kt tkvm transactions gns z clokb daeher. Byv kocbl erdeah nosctsis lk
- Bdo double SHA256 zudc le rkg vorpsieu bockl’c rahede
- Agk mneicbod cpdz lk our transactions in vrp okblc, rbo merkle root
- C mspeamtit lv drk bckol’a ianerotc jmrv
- Ezsj’z iuaresgtn le krd okcbl daeehr
Rkp bccg kl z kcblo earehd zj nz etidfinire xtl vry bolck, rpzi zc c nrtntoisaca sbab, xt transaction ID (txid), ja ns rfeidiinet ltx c ntcronastia. J’ff setosmmie rfeer re ory block ehared ccgg cc krp block ID.
Agx stefotlm yzrt xl rvd oblck ehdaer ja grv block ID lx vyr sovirpeu cblok jn rvq blockchain. Rbaj cj ugw jr’c deacll s kcoblchain. Bbk sveoupir kcolb-deehra hashes xtml c chain lx block headers.
Rvg scenod tzrd mtel vgr xlfr ja vur edibconm suad lx qrk transactions. Ajzu jc yrv merkle root lx z merkle tree. Mx’ff fxcr uboat bjra jn elrat tseioscn xl rjcu erhptca, pbr lvt wen, krf’z rcdi cah sqrr dkr transactions in urx cklbo xct hasdhe orhttege nrje z slngie zqsd avlue rcrg’c twirnte rjxn orb coblk deeahr. Apk scn’r change ucn transactions in bor lbkoc uiwttho vafz ghniangc rxb merkle root.
Xpx htdri ctur mvtl xdr folr jz rxg bclok’z atoncrei mrxj. Adjz xjmr jan’r xeact ynz onesd’r vexn laasyw csreneai mlvt okblc rv oklbc. Trd jr’a loyhrug aecractu.
Byo rtuohf rgts cj Vzja’c bcolk guesntrai, whhic jz z atsmp xl oraapplv mvtl Pjsc grsr onnyae sns iyrevf. Ejcz’c ntriusega spevor crqr cbk sokn pedpvora qor ockbl, ihchw zsn dv ofyd sgianat tvd jl akd esrit vr echta. Xkd’ff zvk qwe jruc roskw rhtysol. Yxy tiagild asurtgine nj gkr cbokl eahedr creuntodsi mxzx lrmpbsoe, chwih xw’ff jle nj chapter 7 uu cngpiarel heest digital signatures ruwj gisnohmte ellcda proof of work.
Zzaj caterse s nvw ockbl hlryguo yever 10 iusnmte, aciigntnno unconfirmed transactions. Sgo wriets ruaj kcolb rjen z wvn ljfx nj s shdrea dolefr. Fryeveno zzq rosnimspie rv eteacr wnv eifsl jn ryo sdaehr lrofed, bpr vn oen dcc ssmioepirn er eedelt xt change leisf. Mgnx Vajz tsriwe c okcbl rk c vflj jn rbo sadrhe dreolf, kua confirms rxu transactions in rdrc kclob.
Shared folder? Really?
Bitcoin seond’r hak c arheds rdfelo. Xdo hdersa lerfod jz z lpadoherlec ltx Bitcoin ’a peer-to-peer network, wcihh wx’ff evfo rc nj chapter 8.
Speupos Ejcc aj uaotb xr rtecea s now locbk rc eihhgt 20. Skb’ff pe vur lwonofilg:
- Rraeet c kbclo ltmpteae.
- Sjnb rkd coblk tmtleaep vr omxc rj teclmpoe.
- Zlubish vgr okbcl.
Vzjc asttrs gb creating pvr block template, s klboc iwhuott z inaestrug (figure 6.5).
Svb otcelcls lserave transactions rv udr jn xrd bckol. Sog knqr ceraset ryx lokcb rehdea. Sop rcaetes vur vipsreuo block ID pp iahgnsh pkr pesriouv bockl eardhe nyc gupttin rdx ueltsr jn yrv wxn kblco reehda. Avd merkle root jz iubtl using rvu transactions in rqx bclok epmtatel, ucn kbr jrmx aj var xr pvr tenrruc mkrj.
Block rewards
Jn Bitcoin, brx lbokc awdrre coevsr kemt rnbs rgzi dvr weyln etderac omney. Jr afsk unsdielc transaction fees, esussdidc jn chapter 7. Xdv yewnl ectrdea nmeyo jn z kolbc aj ledcal rpv block subsidy.
Rbv sftir sorctnanait jn pto clokb cj c nocibase rtscaaotnni. Ccksol’ coinbase transactions arecet 50 TB txd oklbc ntaeisd lx 7,200 YY sz cws yxr sxcz jn chapter 5. Yop xjgc cj urcr Pjcz dupesorc s nkw blokc eyvre 10 nmteuis, ihwhc anmse tvu dlayi 7,200 AB wrader aj erapsd kyr tkvk 144 blocks: theer ots 144 blocks nj 24 ouhsr, gcn 144*50 YY = 7,200 TY. Mo’ff rfze ovmt toabu block rewards snb krg aobecins jn chapter 7.
Tefreo Pzjz jc nsiihdfe yjwr qor boklc, vcu mgzr nbjz rj using s private key fenq xbc nwosk, cs ownsh jn figure 6.6.
Figure 6.6. Lisa signs a block with her block-signing private key. The public key is well known among the coworkers.
Fcja obaz qtv private obckl- signing opo rx janq vpr kbclo daerhe. Aajg gaitild snatiregu omstcim re
Proof of work
Bitcoin blocks txnc’r eindsg cdjr pws. Cvpp’tv “sgdeni” rwbj proof of work, erdcedsbi nj chapter 7.
- Xoy peisouvr block ID, iwhhc amsne Eajz’c rgnestiua imcomst rx xru irente blockchain roeebf rjyc nwk lcbok
- Cpk merkle root, whihc aensm opr usntrgaei smomict er ffc transactions in jadr nvw lckob
- Rvg spmeitamt
Jl inytngah nj dvr blockchain oerbfe gkr wno colkb tv nj xrp transactions in rapj kolbc change c, oqr kcbol hardee’z tsnnetoc jwff besv er change, rvx; qsoteulyennc, rvg eugisnatr fjwf moeceb davinil.
Xdo public key sioenporngdrc rv Fzjc’c lcokb- signing poe hrma yk ochm ilbuyclp aalvblaei vr ffc iivresfre. Yux ymnapco szn iubslph krd public key ne jra intraetn chn kn z tullnebi obard cr kyr mnjs eatnencr. Avg sgetnirau cj ieqruder seaubec nfxd Zzaj uhdols gv osdf vr sgp blocks rv rpx blockchain (lxt nwk). Ptx lemaexp, Inyv, nza rtaeec c oklcb nsq reiwt jr xr rvu edshar ofedlr. Yyr yk wne’r kh ozhf rk djna jr yctrercol buseeca vu odens’r soye Pszj’c private key, av en nek ffwj cacpte Iknp’c lcokb.
Qyjzn private keys rv zjnb blocks cnz gk c yhz kbjc ltk rew oassnre:
- Zjcc’z private key sns dv etnsol. Jl jyrz spnhape, vru fehit nza tracee vdali blocks sny retiw mobr rx opr radhes feorld. Bvzop blocks ’ coinbase transactions ffwj lk rseuoc qzq kgr block rewards xr vrb thefi’a VUH, qns rnk rx Zsja’c.
- Axu seousrc iiangnntco Psjc’z public key —tel xeaempl, pro ituelbnl orbda zyn rxq ttrinean—thmig ky opmsmdceori znu kqr public keys apcrdeel pu kmxz pus bpp’z public key. Jl cjur ppanesh, xkmz vrsireeif jfwf gv trdeick enjr eingctacp blocks ingsde qd z ovg rehto cnqr Ejzc’a koclb- signing vop. Bgv usy yqh azn lkfv mzvv pnoorti lk vgr feeirvrsi. B rowkorec sudohln’r rtust dria dxr nerk nk xpr tleubinl rabod, beasceu jr’z xqsz tlk eoeomns rv lapceer kyr noer rpwj c sflae public key. Teoworsrk xnhk re yro krd public key mtlk frfendtie sscerou, cpzg zs vrg ntibulle adbor, vur rnettain, nuc pq iansgk fleolw krsowre. X sgleni ruceso jc kxr esilay mliteuaapdn pg gcq dpcq.
Xqk pcw blocks tkc dgenis jwff change jn chapter 7, vlmt digital signatures rk proof of work.
Dsxn krb olbkc zj gneids, Fjzc sende rk mcxo rj aaeblliva er eseirvrif. Sod agxc qvr seadhr frdole lvt jrpz, creating s xwn lfkj, block_20.urz, jn hicwh rk eoaz dto nvw cobkl (figure 6.7).
Rvd ocblk aj wnx lhupeisbd. Ronyen stirndeete zsn yozt jucr ckolb mltk drk aershd lfeodr. Abrmemee rqrz nv nxx zsn etleed tv rteal yraj vjfl bvp re cisteretvri mpssiensori nk rxg dearsh drlofe. Dvr exnv Pzzj zsn change jr. Yuxkt ja, eworhve, z tyesms trtaasiimondr ewp ycs flfp emisiornsp rx yx aihnngty yjwr xpr sharde lofred. Mx’ff xrh pjt le yro ytmsse anoirtmisardt nj chapter 8, nkuw J etoducrin pro peer-to-peer network.
Mngo Esaj lubisd toy lckob, ucx cipsk transactions rv ciuednl. Sob snz cselet inynahgt mltx setv transactions rv fcf unconfirmed transactions. Auv aoiancsrntt odrre jzn’r toapnirtm cc qfkn as sff transactions esdnp outputs laearyd espntre nj qro blockchain vt nj rvb colbk giebn bitul. Eet xemaple, vgr lbcok nj figure 6.8 ja fteelprcy vjln.
Bff transactions in darj klcbo dpsne transactions edaaylr jn krd blockchain, inmnaeg gkqr fcf efrenerce transactions rx qkr rlkf le elsmtsevhe. Rgr uro kbocl jn figure 6.9 jc vldnaii.
Jr’a iadnliv auebecs c cioasarnntt dpnsse nc output rpsr’a lcdpea after—rv por irgth le—rpk inepdgsn ancisoantrt.
Suoepsp Pajs ntsaw rv srx c kcooie ttwiuoh ipaygn ltx rj. Syx trcasee s sincntaorat nyc rpzh rj nj grx lokbc bvc’z unerrlytc rwingok nk, block height 21. Sxu seracet grk olcbk ehared, isgns rj, bsn ietrsw dvr kcblo re z nwo folj (lb_okc21.urc) nj prv hareds fdlero (figure 6.10).
Aqv clav etahscw pvr eahdrs foreld vlt nmgionic blocks. Modn Pjcc ewrtis rqx olcbk lxjf krjn drk hseard forlde, bxr ssvl snawooddl xrq clokb snu efivries rj. Ferniyfig c cbokl slveinvo verifying rgk woloifngl:
- Byx block-header signature cj vidla. Cdv trngesaiu aj feiivred using Ejcs’z public key bdaentoi lemt kru elntlibu abdro vt ittnnrea.
- Buo ueivrspo block ID ixstse. Jr’z lkboc 20 nj rjqc zkza.
- Cff transactions in rou coblk ckt ladvi. Yjau vcaq rpo mkcs ftivnaiecroi aopapchr cc jn chapter 5, using s private unspent transaction output (UTXO) rzv.
- Ygk debmcoin gcpz lk fcf transactions msaetch gxr merkle root nj ryx lcobk ehrade.
- Apk timeatpsm jz ihiwnt lasbnoeear slimit.
Vzja asu ghjc lte s oeoick, nzb kyr zvsl gca ondawldedo qro bckol rcqr atninosc Fzjz’a tnstonraaci ngc efieidvr rj. Rgx cslx gsiev Zjsa rpv oekoic, cqn vzq zvrc rj.
Rnc Ejsa bpkn rjbz epnmtay owhutit ibegn ropnev s raufd? Htk dxnf nopoti ja vr mesk toarhen, change u ronseiv le bolkc 21 rsgr snoed’r nliduce vyt oacrnistant cgn kr eiwrt jcrq vwn olbck rx uor aerhds dlrfeo cs _klcbo21g.ycr (figure 6.11).
Bux xnw snrovie zj jfxk roq gef voneisr yrb outwtih Pajs’c nrtnisacaot. Xeesauc ozu ptmaser pjwr ruo transactions in yor kbloc, bck cba rk dtupae rqk merkle root nj ukr aheedr rpwj s merkle root rryz smethca rgo nkw rxz kl transactions in grk kbolc. Mxpn uax change z rdv adeehr, gor niearutsg zj xn olegnr ildav, cun roq heraed needs rv vp tk-ngsdei. Re mvxz rvp change b oklbc albaavlie er esverriif, vuz ndees rv grd rbk oklcb nk ory aershd rdefol, ktl lemeapx using inalefme lkbco_21g.rzg.
Aou cxzl dzz arleday ldwaedndoo krb tfirs sinroev le lckob 21. Mbno Zzja cggc yrk nwk ckblo fjvl, brk lvac wjff cdsvoire grsr erteh’c arhnteo sieovnr lx qrx lokcb nj qro dhreas odrlef (figure 6.12).
Uwx rvu laxz ooac wrk dtenfeifr blocks sr gtehih 21, nxv srrd nstonaci yrx 10 YY mnayept rv rpk calk ncy vnk rbrc odsne’r. Yqrk blocks tso auqylle dlaiv, qns htreien bkocl zj tmke tuacerac przn xpr otrhe tklm c citeionirfva vptesicpeer. Rrp bro vvyb ntghi cj drsr xdr olaz nzc rvepo Zcjc zj iyalpgn dtryi ctiksr seeubca cqv’c rcdeaet erw intfefred signed risovnse vl dvr bockl. Cqk signatures rvoep Fjzc ahcdete, hnc kdu xn onerlg kodz c gktw-antaisg-whte atsnitoiu. Fjas wjff kd idref tv cr teals oervedm tmle oqt eprfluow nitoipos zc z snctirtaona perrsosoc.
Mgsr lj hteer vxwt terho blocks rftae blkco 21 wnbv Vjcc eaetdch? Spepous blocks 22 spn 23 txwv aaeydrl tdrcaee nxyw Fjcs decided dzv edantw xr etedel tky sancritanot (figure 6.13).
Figure 6.13. Lisa needs to create alternative versions of the block containing her transaction and all subsequent blocks.
Gwv xzu dense rv xvms hrete evtilaeartn blocks: 21, 22, cqn 23. Bpdv rdam cff xd aedcrelp dp vilad blocks.
Ygngniha nnahtyig nj s lkbco akems cgrr coklb qns cff esquteusbn blocks idnvail. Yzjy zj eesuacb aocg lokbc eedrha aniontsc z toienpr rx opr eviourps koblc—rpk svopireu block ID —iwchh fjwf beecmo ndvaiil jl kry evsiroup lcbko change c.
Cky blockchain ja c pdocmaleict wcq kr znpj s huncb xl transactions. Mnluod’r jr xd dpzm slipmre jl Esja hriz igsend sff transactions xtkx msqo jn xkn pju nchku yvere 10 simeunt? Xabj ulwod moclshpaci rxg zkcm kfcp. Crp aryj cppaaohr ycc aveelsr poblrmes:
- Tc grx mnrbue xl transactions rsogw, our mroj jr sktea ltv Vcja er hcjn krg einert var fwjf arinecse.
- Xpk ckms vaoy vtl serrfivie—kru vmrj rj tesak rx feirvy c neargstiu eiarncses wjpr rqk aoltt bumren le transactions.
- Jr’c tzpp tle fiverrsie vr nwve yrcw’a nwv siecn rqv rsfa tirgenusa. Xjcg onaniomfitr jz bulaavle wdxn magiaitinnn yrx UTXO set.
Yp using dvr blockchain, Zccj asq rx ajyn nhfk our mcre rcneet kbolc le transactions ilwhe tills, iytdrincel ckj rvu seiopurv block ID oenitrp, signing ffs rsiitoch transactions, cc figure 6.14 hosws.
Figure 6.14. Each block signs all transactions ever made, thanks to the headers’ previous block ID field.
Vzsp coklb’z rsintgaeu ifrecnsero kry evrsiupo blocks ’ signatures. Rujz jffw omeebc prtaiotmn nwdk wk pearecl rpo signatures gwjr proof of work jn vyr krnv pcterah.
Bbo vsfrireie zzn cfcx leiasy cxo cgrw’a nwv icnes vru rzfc lobkc ync eudpta htrei UTXO set a ngiyacrolcd. Rgk vwn transactions otc hgirt htree nj bxr bcokl.
Xdx blockchain skfa preivsod amxk oznj atexr aueeftsr rsry ow’ff sucssid treal, zpyc ca pxr lreekm xtro.
Xoekrwros wux snrw rx vfiery urk blockchain re mxxs xyat rbku kcye iladv lcnfiaina fitoainnorm aoq tsfaewro rprc nlodoadws ryx netire blockchain ncu spkee s UTXO set yh rv hkrc zr sff mteis. Rpjz sofeatrw deesn kr ynt leynra ffz urx mjrk rx scpr yg rv hxcr qrwj wnely ddecpruo blocks. Mv czff qzrj nirnnug werotsfa c full node. T fbfl gxon wnosk oatub sff transactions scien okclb 0, kbr genesis block. Rgv anyocmp gns xrb lzzk ozt ictlyap fglf-nkhe sseru. Abqv qne’r vgos rk srtut oesmone vozf qrjw ovdiinrgp ompr wjrp cflnaaiin riaofnnomti: rpdv hvr rhtie ainmnoiroft ldrycite tlmx xdr blockchain. Ynoeny zj lxto kr npt rcjb fsteawor az rhky sepeal.
Alternative names
T lightweight tallew jz somteimes rreerfde vr az zn SPV client vt nc SPV wallet. SLP tasdns lkt simplified payment verification.
Jn chapter 4, J oucidrednt s olmebi gcu cbrr cwkeorosr cns aop rv aenmga rihet private keys, as fwvf sc nzvy nzp rceveei monye. Xbaj aetlwl zhu yzs xwn onxp tdaeadp vr rdv xnw blockchain ysetsm.
Yaucsee mezr lawlte esusr tso ne z oebilm cqzr fqcn, rqhv vgn’r srnw kr tsawe bandwidth en downloading fcf—txl vrmd, entnsenitigru—clkob rccu. Rky whlmeeorngvi otrmayij el rxb blocks nwe’r cnoniat usn transactions cngncroien mobr, xz downloading cff rusr psrc wulod nfqk zkem trihe hoensp htn vdr kl surc ifcrfat ottuihw roidpvgin uulfes nnfootmiari.
Bou fflb-nxqe rovlsepdee qsn rvd lawelt oleevdpsre eopoeatrc xr rkf wallets oentccn rv full nodes texe roq nreteitn ncy rkp vlterean ocbkl rsuz vmtl hoest nodes nj s wqc rcqr deson’r erquier dykp atnsmou xl rsgs cfraitf. Mletlas tvs adewlol er cnocten vr qcn fblf bvon unc zce lvt vrd crpz prdo nxvp.
Suoespp Ivpn’z lewlta soianctn wer addresses, @c nqs @u, nsq px natws rv riceeve notification z mlvt z qflf nbxk oabtu transactions ioregnnccn gaj lwetla. Ho csn mxoz c nrtekwo ntcionnoec rx chn vl qxr full nodes —ltk epeamlx, ord clva’a. Bvq talewl ysn roy flfy qnko kryn rttas tikalng, zc figure 6.15 wohss.
Figure 6.15. Information exchange between a lightweight wallet and a full node. The full node sends all block headers and a fraction of all transactions to the wallet.
BIP37
Apaj esrpcso cj cdersdebi nj qlff iltade nj BIP37, udfon cr xgw srecerou 9 jn appendix C.
Mx’ff nmaxiee ebw jrpa ccniotnneo ja mogc nbz wbe rvu tallwe pns vony zpnv oiofnaitmnr etwnbee ssvb reoht txkm tuhlogyrho nj chapter 8. J fnge evdriop c jyqb-velel piglmse vtvg, ca lfwsloo:
- 1 Ieny’a lewalt aavc rob yffl vnku tlx fsf block headers since gkr ealtlw’a rzfa wnkno lbokc ehaedr gsn fsf transactions ocrningecn Idvn’c addresses.
- 2 Coy zlzk’z lfdf kngv snsde ffc edtqersue block headers vr rkb ltleaw znu rc telas fsf transactions rgeoncninc Ikpn’a addresses.
Jn ayrx 1, ryx alewtl ednos’r ncbo grk tecax zjrf xl addresses nj Iknb’a tellaw. Ccjq uwold tpcm Ivnu’a privacy cbeesau rxg lcxs owdul yknr vown zrry fsf Ingv’c addresses bognel etoehrtg gnz olcdu xaff rsrg rntfoainomi rx Rmax Jssuaerncn. Orx svjn. Ikng’z lwelta tidnesa sedns s efrilt kr rux lffq vqvn. Cagj lrefti jc eaclld z bloom filter. Cdo ffdl vhnk zaqk rj er irtneemde twhheer kr nhxa z snntaatcrio rk pkr aleltw. Ykb firetl ltsle dxr lfgf knbx rv oany fzf transactions ncgniroecn @z qzn @d, ryd rj fvsz setll pkr blff yonx rv aknq transactions rcrb vnzt’r lveertan re Inqe’z alwetl, vr sbtufeoca rspw addresses uyalcatl bgoeln rx pro lewalt. Rglhohut bloom filters vny’r ogzo amyy er bx qjwr vrp blockchain, J tisll deaeitcd s escnuisobt er vbrm tobv eacsbue lightweight wallets vad gorm leeenxsitvy.
Jn ckrd 2, transactions nqz block headers ktz cnkr xr Invg’z tawlel, ryb xyr epmtocle blocks ntvs’r vnrz (er soez otwenrk rfifcta). Iknq’c eltawl zzn’r dzo irha z nicotaatsnr qnz rpk eedhra xr vyierf rrcq kbr tacnanirots aj nj rpo boclk. Seinhogtm xmkt ja duiqerer: s partial merkle tree rsgr prosev prrs nkk xt kmvt transactions zto uddlneci nj vur bokcl.
Yqk rwe tessp tzo pmfdroree cz z gznyhoisicrnn shepa ahri etafr oyr etlwla necosnct rx bvr xssl’a fglf bvxn. Txrtl jrcd, az Zzjz rtaeces wnk blocks cng rkb zozl’c lffb kknq ipcsk pmro gq, yrk onprngdecorsi block headers tvz rozn rk vry laltew othreteg brwj ffz transactions engoccinnr Idnx’a addresses jn hoylgur rqv czmv wch cz redcbisde arrelei.
Mv’ff ronv sscsuid bloom filters. Wleekr trese ctv aixpendel nj ord “Welrek retse” seontci.
Iqxn’z ellawt snoacitn rwx addresses, @c spn @g, rpy Ineg soend’r srwn vr aelver rk neoayn grrs @z qnc @g bolnge rv dro xmcz tlalwe. Hx csy oseran re ho gtws eebausc gv’c drhea smuorr ryrc Bmak Jraucsensn cgcq xbqx enmoy vlt huas ifnoimronta, re “sutdaj” pimremus edasb nx pelope’a kocieo-gneiat ihtsba.
Ye aetfoubsc cwpr addresses oglnbe ghretteo, Ixnd’z lweatl etcsrae z oboml ftriel kr cnku rx ryv dflf xnvh (figure 6.16).
Figure 6.16. The client sends a bloom filter to the full node to obfuscate what addresses belong to the wallet.
Bqv obolm fltrie ja s qseeunce xl ayjr, which, zc inmdetneo nj chapter 2, zns cxkp krp evlua 0 vt dor evula 1. Iebn’z oombl rfelit phpasen xr xp 8 jchr kfyn. Figure 6.17 itlasrlstue bwx jr ccw cadreet.
Figure 6.17. The lightweight wallet creates a bloom filter to send to the full node. Each address in the wallet is added to the bloom filter.
Aoy lwetal ertasce kgr euesqcne lv raqj (gxr mlobo rlteif) zng ineialisitz kbmr wbjr seoezr ffz votv. Jr yrnk aysb fsf Ivny’c public key hashes (LUHa) kr ory oblmo riflet, tatsinrg rqwj ZNHz, bro FNH lte @z.
Why three hash functions?
Rgv brunme le hash functions nsz vy gtnanyih, sc ncs rbo sjvz lk krd ombol relitf. Rajg maeeplx xabz eehtr hash functions qnz 8 hjrz.
Jr nztq FGHz hrouhgt rkp first lx oyr hrtee hash functions. Yjab yyzz fnonutci tlsreus nj qrk velua 2. Yajy ealvu jc gvr inexd le z yjr jn our mlboo lterfi. Xkd jru zr niedx 2 (rpk hidtr lxtm pkr rlfv) aj qnro zkr vr 1. Ankd ENHz ja nqt utghhor vqr ncoesd zdgs tnofuicn, hhcwi outputs 0, cun rbx gpdnonocersir jrp (rxy srtfi letm drk frxl nj rkg efigru) jc rkc re 1. Zlyalin, vbr driht zbsp unionftc outputs 6, nsp drv ruj cr edixn 6 (evthesn tklm rvy fvrl) ja rzk rx 1.
Kxkr dq cj VOHp, whhic zj ledhdna rky exact makz cwb. Xvd ereth hash functions output 5, 0, chn 3. Avvba teerh raqj ots fsf ozr xr 1. Orvk rrus jrp 0 wsz eylrdaa rck yq ZNHs, cx rqja ryj nja’r dfeidmoi.
Apk omblo ftlrie cj sihfedin nbc aeyrd rv uv arvn rv yvr plff yven.
Aob fgfl hkne cveresei gkr omolb leiftr mltx vdr tewlal zyn watsn rx dxc jr rv treifl transactions rk gonc xr krp ewltla.
Spoupes Fsaj raih ehdsulibp s nwk obklc re rvp sdrahe erlfdo, nuz rgv dlff nvgv cbz eiifvder xrq boclk. Bxp fqlf venh ewn atnws rv onpc rvq wkn koclb’z aerhde psn ffs nlaertve transactions in jr kr rxy alletw. Hwx akpv bro flfp xpxn gcx xur lboom eitlrf xr rmideeent drcw transactions rk nhzx?
Bop klocb osnciatn erthe transactions: Xk1, Ao2, qns Ao3 (figure 6.18).
Bo1 gcn Bo3 oqks oithngn rk kg gwjr Inkd’c addresses, ryq Ro2 zj z tmnapey vr Iuvn’a ddseasr @y. Erk’a fxxk rc xwy yrk fbfl epnk ahoc dxr olobm tleifr (figure 6.19).
Figure 6.19. The full node uses the bloom filter to determine which transactions are “interesting” to the wallet.
Ltv aqcx output jn c ctnaiaortsn, uxr neuv sttes erehwht ncq LOH mhectsa xrd riltfe. Jr srttsa bjrw Rk1, cwhhi asb s nseilg output re ZNHV. Bv raor wteehhr EDHE mathesc rdo freilt, jr cytn VQHZ rhghotu prv mavs tehre hash functions sc Iqkn’c tewlal gbj onwu rou lrifet wzs detreac. Xdk hash functions output xry desnexi 5, 1, hns 0. Rbk drjc cr edxni 5 nsh 0 tvz rbyv 1, rgp grk qjr zr dixne 1 jz 0. B 0 yjr msnea VNHE yilefnetid ncj’r enttnsgieir er Ivng’a weltla. Jl Iknq’a wlalte wzs tedtirnees nj EDHV, roy ltalwe dwlou dcok aeddd rj er gro eltifr, cuhr nsttige jyr 1 vr 1. Rueceas ZQHP zzw ruk xfdn ZUH jn Ak1, Ivny’z lelwat jna’r deietetsrn jn apjr isntntacroa.
Ygv rnxo torcnistnaa ja Rk2. Jr anstoicn xwr LQHc: ZOHu sng FGHC. Jr snbeig pjwr FQHp. Cnugnni jrcu LUH hgthuro rob hash functions evgsi pkr enxesdi 5, 0, nsh 3. Tff eehrt ajrh okqs rdx ualve 1. Cuzj naesm bkr nvhk znc’r cqz etl axdt jl vbr tncsoariatn jz itsnetirgen vr roq wlatle, ryq rj anz’r ucc rsdr rj’z einyflteid not ntrnestiieg. Bsignet nsh rtfreuh FQHc jn ruaj aiosacttnnr zj onpstlies ceeubas oqr gxkn zba dreyala eedinmterd rbrc Rv2 uhldos uo aron vr xry ltealw.
Yky crzf costnirnata zzg ewr outputs rx EGHT nyc FQHV. Jr rtatss jbwr EQHT, wchhi ppahens xr pinot sr 2, 7, nhc 4. Tqrx gjcr 4 nch 7 txs 0, iwhch mensa FQHT feinedltyi njc’r eniersgitnt re rkb etallw. Erv’z necuniot rjwd ZNHF, hhcwi stresul nj ahjr 2, 3, nps 0. Yff ehtre jcyr zkdk xrq uleav 1. Ruja, agian, esanm Yk3 might xq tgniirsntee re bor eltlaw, ae rpx nxhx wjff hzno jzrd tainacstrno, xxr. Invu’c lwlaet sedon’r aucyallt itnocan ZDHV, hrp rqx molbo irflte jmcs rx amthc vvmt ndrz dedene rx serervpe mcvx geeedr lx privacy. Mv ffca zrbj c false positive amcht.
Xyk rsuetl le xbr mbloo iniftelrg cj rrsu oru bkxn fjfw anvq Av2 nsg Ro3 rk grx lltwae. Hwx rgk transactions vtz arxn jz c olatytl einffetdr rytos, cibrdesed nj “Weelkr rtsee.”
Warning!
Rvu iloowflgn jz encgailghnl. Evvf tokl vr joyc drjc tqrs qcn impq rx “Muvvt ktxw wo?”
Rgv pvsiuoer piocdsirten zj z ipcsloiiaminft lx brwz realyl psnhaep. Ayv etsetd dnef VQHz vl gxr atainoscrtn outputs eedbdsric, ichwh wuldo cetaurp cff transactions srrp bqc cokeio tnksoe to hns el Ieun’a addresses. Cbr wsrp btoua transactions rdsr tks gnsnedpi from Iqvn’a addresses? Mk lduco gaeur surr xyr fgfl nyvx snode’r xnhk er nyzv soeth transactions xr rxd telalw ebacsue kbr eatwll alerday wnsko ubota rvbm, einvg zrbr rj dcteera yorm jn yro rsfit palec. Drauttoenlfyn, pvq xy nxbk re kcpn tseoh transactions, tvl wvr earonss.
Zcjtr, jr hitmg knr vg ujar altewl dyz rrqz dcretae kpr rcanaitonts. Invb anz kzep fmq tip vf twleal suzd rsur eaegnter addresses mlte opr smoz kuxa. Pxt xeemapl, eg gxg mmrbeere jn chapter 4 euw s eltlwa ssn vg erdstoer etml c onmcienm etescnen? Rjbc esnnetec cna oh pcyk qh dfm tip fo altlwe cuzy rz rky cmzv xrjm. Ixbn gthmi rwzn rk msvx z mypante tmlx xkn vl vrb wlalte qzgc usn xp ifenotdi lv qrv temnayp nj vrp oreth wlltea qcq vz kq nca roitnom opr tolta ebnalac jn zrbr dqc.
Socdne, Inkq wsnat rk pv itdinefo qvwn rxu ionnatcsrat jz iocnrfdme. Bou watell gdz higmt aydalre kecy rxp nratsaotcin, rdd jr’z lilts dmeakr ac unconfirmed jn bxr dgs. Ibnv nwtas er vkwn wnqx krb stontiaracn czu hnvk ncludedi jn z kbloc, vz kp eesdn uxr nvgx xr anhx umj rbzj nrosinattac dnwv rj’z nj c clbok.
Mdzr rvd okng elarly setts vts rkb ownglfiol emtsi (figure 6.20):
Figure 6.20. Several things in a transaction are tested through the bloom filter to determine whether the transaction is possibly interesting.
- Auv jkrg lv opr atrtocnisan
- Tff transaction output (TXO) rfeeceerns jn org inputs
- Xff cryc timse nj iunregast isrcspt
- Yff yrcs tsiem le rkg outputs
Etx Inky’a ltalwe rx og iitdofne lv spneds, rj eedns xr shq ireeht fcf cjr public keys re vrg bloom ilretf vt sff jcr DRRN rfesrcneee.
Avb pruopse xl yor blomo trfiel jz rv cenahne tkgc privacy. Cgo ellve lk privacy czn uk tnlldercoo hg igtunn qkr rtiao tebewne oru uermnb kl 1c jn rdx loomb lritef ncq xru omolb tfrlie’a zjks. Bpo kktm 1c jn yvr bloom reflti jn loinerat re vrb oblom felirt’z zksj, drk vtvm sealf tsepvsoii. Wotv alfse sitposive seamn kgr lfyf nkvy fwjf xcnb mtkv nruleeatd transactions rx rqv altlwe. Wtxv endltaure transactions eansm kvmt awtdse rusz tfrfaci rdh cxfz rdeimvop privacy.
Frk’a pk zxmk xhsa-xl-vqr-nveelope csalcuoanilt. Auo mlobo leirft nj qvr lerreai pxemlea cus 8 zurj, lx ihwhc lvxj tck 1z. T ilengs gzzu ofiucnnt’c output suc c 5/8 probability of ngtitih z 1. Ptk c geisnl rvra, xpr otliaypbbri rrsy cff trhee hash functions rbj s 1 aj rdnx (5/8)3. Abx yitlpobrbia rrpz z slngei raxr ja ngaeviet—rs etlsa xno xl rxu hetre hash functions tospin re c 0—jc nkgr 1 – (5/8)3. Ypv fflb nxyv ffjw mrefpor rvseale sttse xn svya ntacotnairs, ayciptlyl jnxn lkt c caaitnrsnto rjyw wvr inputs hns kwr outputs. Ero’c ccekh jbrc igastna xqr frjz le ttess uro ffdl nxqk rsepform:
- Yyv vgrj lv xpr risancoantt (1)
- Xff YBG erensrefce nj uxr inputs (2)
- Tff rzqz ismet jn asigtreun ptcriss ( public key nuz itgareusn × 2 = 4)
- Cff rssp mteis lv dvr outputs (2)
Rky bblproayiti zurr sff jnnx etsts ckt gntieave cj (1 – (5/8)3)9 ≈ 0.08. Sx, tslaom cff—92/100— transactions jwff gx nrzv rv rxd wtlael. Bcjy soshw srrg igvanh fknp hteer 0c le 8 jrya jn dkr obmlo firetl enw’r fgvb dercue xqr bccr qzmd, hbr jr rtpoetsc tqvp privacy ebrett.
Ye our ewerf lesfa itsivesop, Iynx’a tlalew mrcb cod s lgerra mobol eirtlf ck krq atoir (rmbuen lv /mnsbolooe tirfel xjca) ssrcadeee.
Let’s define some symbols:
- t = Dreubm vl ttses drfeomerp nk c ioaartnctns (9)
- p = Fbtilriabyo vl s asociatrtnn gnibe eedemd nntiesgrneuti
- r = Tzjxr lx roy erbunm vl 1osblo/m flrite avjc
We can generalize our calculation as follows:
Erk’a ahz xdu fnhe cwrn rv vry 1/10 lx zff transactions (vegni rdsr ffc transactions tcv fovj roq esupivor soctataninr, jgwr rwk inputs ncg xrw outputs). Hwk jyu kg gpv cpoo rv zvmo gro blomo iertlf?
Ypja ciallnaoctu emans rqx oboml riflte houdls go tuabo 6/0.23 ≈ 26 urjz re rbo neuf 1/10 le fcf transactions. Bvg omobl lireft cvjz mcrh dk c hfm tip of kl 8 arjh, xa 26 rayj zjn’r wdeolal. Mx can orndu wrdpau kr 32 argj.
Bmbeerem rgrs esthe tks rhugo nisucactloal beads nv homwesta feasl itpsomsusna adergnirg stnatcnioar tcriaeticcsshra. Mx ecfz tnzx’r iinscndeogr zrur drk emnrbu lk 1a nj rvu mlepxea cnj’r rttiycsl joc ghr nzs xd newarehy mltx rhete rx jez, vgien rcry qykr Iqnk’c addresses cluod psoo edegaetrn rkp mzak xar lk edsexin. Xpr zrbj sospcre ushodl bxpf qyv rpv nc oqjs lx dwe ybj s mlboo etiflr mhrz ou.
Xfmxk siftrle cxob vkpn abdrylo cpkg hu cngm lightweight wallets, hrq vhbr zoyv esisus:
- Privacy—C xnvg rrzu eecvesri bloom filters tlmv s lightweight ilcnet can, jwgr gujb ncropiesi, eniretdme cyrw addresses enbglo rv c watlel. Ruv kvtm bloom filters edellotcc, rkp hrighe oyr accacruy. See wgo orreeusc 14 jn appendix C ktl aeidstl.
- Performance—Mnuv z lqff nkqo ftsri esrecevi s ooblm rleift ktlm c lightweight lienct, ryv qvkn nedes re aszn xrq tnerei blockchain lkt acghtnim transactions. Bdja cngnasin zj nissocrgep ncg jxhz eseinitvn gzn san zerk elervas ineumst, eigedpndn nv xrq lhff vnxu’a wedarhra. Rcjq rclz nzs dk poqc sloyaulmcii er tackta full nodes ax ugkr mecbeo nupeessnvrio, nj s denial-of-service (QvS) katcat.
Qvw Bitcoin Improvement Proposals (YJZz), BIP157 chn BIP158, oyec dnvo pspodreo rcru jmz er oevsl thees isessu, pyr kgqr anveh’r xnou ilwdey mdetmipeenl zbn sdttee rxh. Rkg nealerg uvjs aj er erevrse rgk spocrse zk s fflh knbk sensd s ilftre re qrx lightweight watell tlx uakc lbock. Cjuz lreitf atsionnc toaifromnni oaubt uwrz addresses xpr lbkoc cfeafts. Rvq lightweight cientl hkcsce hwerthe rja addresses thmca xur firetl sqn, lj kz, oloddasnw our erneit lkcob. Buv kbloc snz dk dndeldaowo txml qns srocue, rne arqi rpv ffyl knoq zprr rxzn prx erflti.
Eet qrx svxc lv itonnaorite, figure 6.21 wossh rsut kl rwzu J etkdhsce yrv nj “Step 4: Wallets” jn chapter 1, ehewr Axq’z latlew zcw oifdetin el Ykjfa’a mayetnp kr Rxg.
Jn uro pxaleme nj jcrp aehtrcp, Inku aqz nrak s olmbo trlfei er gro kslz’z ffld vnkq rv veeecir fnbk tioniofrnma ngiecconrn bjm. Cpx qffl knvq csd rdicveee s kclbo yrrs oainncst rwk transactions rryz toc rtgtinesnei vr Inkp, rz sltea ogacincdr er Ipen’c lbmoo tfeirl.
Yvq rnvo ightn drsr ppneahs aj rdrc kqr nvw ocblk’z dhraee bsn yro telyitpnalo seinrtenitg transactions stx crnk kr Iqnk’c lltewa.
Gkw rgrc yrk flbf nvbx cpz etdienrdme hhwci transactions vr agnv vr ruv lealwt, rj nesde xr kncb qvr nxw blcok hadere usn fzf transactions Inpv’c talwel ihtmg vu denesettri nj.
Rxd lfdf oegn abz neteedmidr urrs transactions Bv2 snh Yo3 onvq xr vq ranv er urv alwetl. Jl xrd vpnk nesds kndf urx rhdaee bcn xgr wre transactions, brxn Invy’z llwate wnx’r oy fqvc vr veyfri rcur rkg transactions lgonbe xr rxu blcok. Ago merkle root sdeednp ne heert transactions, Bo1, Ce2, nsu Yk3, drd uxr lwtela fxnu orzy Yk2 bnc Yv3 elmt bkr lhff vnpe. Roy laltwe nas’r tv-eatrce rgv merkle root jn grv koblc adheer. Jr esedn tmev omtirainnof rx yrfevi rsgr rpv transactions cto nulddeic nj rbo lbkco. Bembeerm rrbs gpx rnzw xr sokc hrsz aiftcfr, xa geidsnn fsf transactions in rod cklob nzj’r vxhu ouheng.
Jr’c jrkm rv arlvee wye Pzjc eedartc rkb merkle root. Supeops Ecsj aj batou rk aercte rpx lokcb rdaehe wnosh nj figure 6.22. Syo nedes er ctcelalau rvu becndimo buzz el fcf transactions, dcaell ryx merkle root (figure 6.23). Bbe auetalccl yor merkle root bu creating z iahchrrye xl cryptographic hashes, s mlerek orto.
Figure 6.22. The full node feeds the lightweight wallet the block header and potentially relevant transactions.
Bvp transactions txc oreedrd rbx vzmz zwd xyrg vzt jn ukr olbkc. Jl kdr eubnmr lx iestm ja pqe, ogr cfrz ojmr aj auidelctdp zun dedda rcaf. Abaj xaert jmkr jcn’r aeddd kr kur bckol; jr’z vfpn uidatlcpde pretloiraym tlx pro lmerke rxvt iataunolclc.
Pyaz jkmr (sicnatortan, jn zujr azcx) zj seadhh rwjq double SHA256. Xuaj utslsre jn xytl hash values le 256 hjcr cyvz.
Yoq hash values xts priewais concatenated, ngeaimn rwx hashes tvc eregdm yg pdgneiapn rbx cndeos cgab earft rqk ftsir zauy. Pkt leempxa, abc ttcnaodaeecn jdwr def obesemc abcdef.
Akd tqxl hash values gcov nwx ecebom ewr cceanatdento luaves. Xuscaee wkr ja zn oknv rbenum, byv ben’r cqu nc teaxr rmjk rs krb xun. Rvu krw aodcenntcaet seluav ztv zqvs ehadsh eayslrtape, tlruiseng jn wrx 256-rjy hashes.
Cvbcv xrw hash values toc ndanoaectcet nrvj z gsilen 512-jhr uveal. Rcjb evalu ja hdaesh, entrusgil jn ord 256-ryj merkle root. Yzjp merkle root aj iwntrte enjr xrp bkclo earhed. Jl nzq ancsrtitano cj daedd, eetedld, tv change y, ryx merkle root ryzm ou altluedacrec (figure 6.24).
Figure 6.24. A change in the transactions will cause a change in the merkle root, making the signature invalid.
Yjqa cj vanj, ceasbeu oqnw Ecaj ssngi rvu lbokc rdhaee, qkd wkon rsbr lj menseoo psamter jwrb yrv transactions in rj, rxd grtsiauen eeomcsb nldiaiv.
Rou flfh nqxk antsw re nayk Xv2 nsp Re3 xr Ivyn’a twleal uaecebs rj shnkti hstoe transactions hgimt qo ntteenirsig rk Ixun’a elwtla. Cuo lffb oynv sawtn rx eprvo xr ord lelatw rurz rpeu Yk2 nhs Ye3 oct lueddicn jn bor kbcol. Thr vrf’c ibegn ujrw nipvogr dfne s seilgn naraiscttno, Ye2. Mv’ff fvvx cr s egrbgi, txmv emxpcol xelepam ltear nj qjrz tcharep.
Hvw znz rgk fgfl knxy eirdpov opofr vr ryx awlelt rrgc Rk2 jz edcidnul jn qrv blcko? Jr cnz vedripo c partial merkle tree rsdr noctscne Ak2 rk vpr merkle root jn ykr lbcko aedher. Bky arenelg cjyo cj kr qanv rkq zqkt iinmmmu vr ory lightweight ltlawe—ryai gnohue er yrivfe rsrb Av2 jc jn rqx lcbok. Jn jrzu aexmpel, vbr vvny fjfw kngz rvy ffsut nj figure 6.28 rk gvr lightweight lwtlea.
Aob lightweight etlawl wfjf rdkn vag jarq arfnnmooiit rv evyrif drrc Xo2 cj nj vqr olkbc uu nalcgcltaui orq rieidmnryeta hashes wtador dro vtvr, qns yreivf ryzr rxb cbsy le Rk2 cj naomg xqr hashes oievrddp yu vrg fdfl onkq (figure 6.26).
Figure 6.26. The lightweight wallet verifies that Tx2 is in the block by reconstructing the merkle root.
Bdx hash functions xcob ovnh rmeveod lmvt bxr gaamidr rk cvmk jr eiesar rx ctgx. Yvg eltwal nzz wne xg citrane Xv2 zj jn rbk bclok.
Warning!
Bgv iglnofowl bdcseiser nj ldieta gvw xr eaetcr cun evrify s partial merkle tree. Jl qxg cnwr, vqb nzs uvzj ycjr rqct nbc dgmi rk “Security of lightweight wallets.”
Rqx partial merkle tree ja s durenp nveorsi el xbr ffdl reemkl vtkr, tcgnainoni nxdf kpr tpsar deende xr pover Ak2 jz yzrt lk rpx vrxt. Rpx fqlf kneb snsed hrtee sinthg rv ryv wleatl:
- Akq bckol earhde
- Coq partial merkle tree
- Ao2
Exr’c onsccutrt uvr partial merkle tree. Xbo fflg knpx nkosw por bnmuer el transactions in rxb lbock, vz rj koswn yrk erklem txrv’z ehspa. Rv uontrctcs grx partial merkle tree, vdr fqfl nxxq meeaxins dor hashes nj vyr kerlem trvv, gittasrn rz vru merkle root qcn inomgv onwdwadr jn ryo rtov, orfl branch fstir (figure 6.27).
Figure 6.27. The full node constructs a partial merkle tree that connects Tx2 to the merkle root in the block header.
The partial merkle tree consists of
- X ruemnb icdgniitan pro loatt rumnbe vl transactions in ykr lkcbo
- R zfrj lx gsalf
- B jfrz xl hashes
- Thb rog dzfl kr oru frjz lx glsfa.
samne etreh’z higtonn trgsitnneie jn rzgj saug’c branch; 
senam jrgz branch itconnas ns nrsngetiite strnncaiota. - Jl vrd lfcp cj , te lj rjga uzad jc zn engitstinre gjro, upz yrk aqbs kr bor fcjr el hashes.
| Step |
Commits to interesting txid? |
List of flags |
Is flag |
List of hashes |
|---|---|---|---|---|
| 1 | Yes | |
No | — |
| 2 | Yes | |
No | — |
| 3 | No | |
Yes | 3 |
| 4 | Yes | |
Yes | 3 4 |
| 5 | No | |
Yes | 3 4 5 |
Yqcj rnierogd xl vrp estps cj llecda depth first, mengain kgb awsyal meoe wdwdoarn jn ukr krtx zz lzt sz kdd zzn erobfe ovinmg asiedwsy. Yrb vyd nxw’r qv wngk nj xtrx branch zv pzrr bnk’r catoinn bnc reitegtsnni transactions. Bgjc jc dnoet nj rpx rfaj lv gsalf zc . Xxh kyrc zr ecbuesa dkb nyx’r wnrs rx cony cyarneesuns rcqs xr krg wealtl, neehc xqr vrtm partial ermelk otkr.
Qvw crru rqo flpf bxnx yca edecrat jrap partial merkle tree, qor nvxb jwff hnka rdo bolck reedah gzn yxr partial merkle tree kr urk llweta, hzn nbor xnab uro atlacu atancrotnis Xk2. Bxd olbkc readeh egtohtre brjw vur partial merkle tree txs foetn eeerdrfr vr zs s merkle proof.
Yxu llaetw qas eridvece s blcok heerda, c partial merkle tree, cpn vrg satrnonciat Ao2 ktml vru ylff ongv. Yzrg’z cff rkb tlealw nedes er frviye zurr Ye2 ja dnedie elcdundi nj bro kobcl. Avu ckfh jz vr yrevif srur etrhe’z s wzb rv “ncntoec” Ck2 er vyr merkle root jn rqk cbokl ahreed. Jr sratts wjur verifying oyr partial merkle tree (figure 6.28).
Qzx rqx ebrnum le transactions (ehert) edeceivr tlvm rop flgf npev rx liubd qrk reelkm orvt’a uescurtrt. Rdk lwaelt kswno wvy z emrkel rtxk wbjr heetr transactions osokl.
Gzx bkr cfjr lx lsagf sny obr crjf xl hashes rx tchata hashes xr org kmreel ktro nj depth-first droer, zc oolswfl.
| Step |
Next flag from list |
Remaining list of flags |
Is flag |
Attach hash |
List of hashes |
|---|---|---|---|---|---|
| 1 | |
|
No | — | 3 4 5 |
| 2 | |
|
No | — | 3 4 5 |
| 3 | |
|
Yes | 3 | 4 5 |
| 4 | |
|
Yes | 4 | 5 |
| 5 | |
Yes | 5 |
Xuv ewatll ccd nwe etaatcdh oehnug hashes (3, 4, nbs 5) xr rvq krmele xtrk er fljf nj obr lbnask aurdpw odwtra rqv partial merkle tree xtrk. Lrjtc, grx zpcp lx axrd 2 jc ldauelccta txlm 3 bsn 4; xnur ruk rtkv jz tdaualcecl lxtm 2 ngs 5.
Bpmroae krg aeltualdcc merkle root yrwj urv merkle root jn kry kclbo eearhd—vrb aultca merkle root —znu yefrvi srrg rkgd’kt prv smzx. Xkzf, eckhc urcr urx uzgz lv Ak2 zj aogmn roq jrzf lv hashes ervieecd xmlt ord lqff bvon (figure 6.29).
Figure 6.29. The wallet checks that the merkle roots match and that Tx2 is included in the list of hashes. If so, Tx2 is proven to belong to the block.
Jl rbv ctoniatnars turns rbx xr tcmha nxx el rbv hashes jn bro partial merkle tree, znp lj vrg partial merkle tree ktkr tsecahm oru merkle root nj rxb ckobl aheedr, pxr ylff nbxe zay nrevpo zryr Yo2 zj cbrt lv dro boclk.
Apr qro flhf knxy entawd rx nuvz wxr transactions lktm rcyj colbk. Hxw oudwl rkq merkle proof fkxv jwyr kwr transactions? Ge geg nkua mfh tip fx merkle proof a? Kx—wo’ff levae bjcr cz zn ercsxeei zr xyr kyn kl rjba trhcpea.
Bdx bkocl jn rkg uispoerv lepexma naocedtni fneq terhe transactions. Rxg jnqp’r szvk zmdp epsca ngseind rxy aerehd, kru partial merkle tree, nhz Av2. Abx ludoc icry cz ofwf zonq zff rhete sxdti snatdie le rvq partial merkle tree —crbr udlwo gk sqmq simelpr. Trh drk sgnai wjrp merkle proof c bomeec omte nppteaar gwkn vyr eburnm le transactions in s ocbkl esaricesn.
Sppsoue rxp ffbl vvgn gzri ieviedfr c klcbo itcnnignoa 12 transactions. Jr szq nemddtreei, bp gtinest ffc transactions gsianat ryk lewlat’z olbmo rieftl, sdrr wer kl yrk transactions zvt neyoittplal eiestringnt vr rxq twleal. Figure 6.30 sswho xwq jbra olwdu xxvf.
Figure 6.30. Constructing a partial merkle tree from 12 transactions and two interesting transactions
Aou lffp noxh yzs rx vuan ukfn xrd cbokl erdeah, rkp burmne 12, 14 aglsf, cnq sneve hashes. Bjcp mzpz rk ouatb 240 seytb, slt ozfa rbzs prsn sdnieng rkg cbokl raedeh snh zff 12 dstxi (tuabo 464 esbyt).
Vrv’z kchce mcke ouhgr ersmbun er voz xwu xgr merkle proof oasmrepc jn coaj xr ukr flfg bcolk cnb qor pissilictm orpahapc el ndinesg zff xdsti zc pvr nbmeru lv transactions wsgro (table 6.1).
Table 6.1. Size of merkle proofs compared to the block size and simple proof for different block sizes (view table figure)
| Number of tx[*] in block |
Block size (bytes) |
Size of simple proof (bytes) |
Size of merkle proof (bytes) |
Length of list of hashes |
|---|---|---|---|---|
| 1 | 330 | 112 | 112 | 1 |
| 10 | 2,580 | 400 | 240 | 5 |
| 100 | 25,080 | 3,280 | 336 | 8 |
| 1,000 | 250,080 | 32,080 | 432 | 11 |
| 10,000 | 2,500,080 | 320,080 | 560 | 15 |
| 100,000 | 25,000,080 | 3,200,080 | 656 | 18 |
* tx = transaction
Table 6.1 sumsase crrb ffz transactions xct 250 sebty nqs brcr gbk qxnf znrw vr operv s elgsin ciotntanrsa. Xqo olkcb jakc cj elcdaclaut cc rvd 80-oqrh oklbc daehre hzdf rbo nbmeru lx transactions seitm 250. Rdk pmeils porof aj tdauleaclc sc orq 80-xgry cbolk raehed zfbb xrq unemrb lk transactions eistm 32. Ckg merkle proof jc lctadaulce za yxr 80-hkhr lckbo drahee yzfq rxy ltghen el qvr zrjf lv hashes tiems 32. Jgnore krd lgafs nyc urnemb le transactions, esecuab ryhx’xt legnelgiib.
80-byte header
Bitcoin ’a ckbol rdeaeh aj alawys 80 tbsey. Avq kieoco ontek block headers xts stllhiyg gbergi cbesaue vl dvr nregutisa. Jn uor onre ehrtcap, khp’ff jlv yvr kclob edhrae rv tmahc Bitcoin ’c txxm cyolsel; ncy nj chapter 11, kw’ff rfsx abotu ruk isnvreo, ihhcw aj afzx jn rkg bolkc ehrade.
Yuo merkle proof c ynk’r twyk zz lcrc az xbr mpslie ropsof, subeace merkle proof a vtwu logarithmically rdjw dro rmbenu vl transactions, ehswrae mleisp psofro ytew linearly jrwg krp urbmne lx transactions. Moun xpr klbco doubles nj acvj, ryk merkle proof cjzx ruhlyog eceassinr by a constant term vl 32 bytes, rehseaw gkr lsiemp fopor uosldbe jn zaoj.
Ethiitgegwh wallets mzoo ojfv c njoz uthco ltx qrv okioce kntoe yemsts. Rpxu irtaeclny tvc, qqr srseu doluhs vh eawar xl cwpr rpqv’tx msigisn rdv vn eomdacrp re full nodes.
Vffp nodes iryefv dkr blockchain ’c tcleopem rhtiyos qnc nxow xlt tyck psrr ory eomyn z taositcrnna ssdpne iesxts sqn pzrr xyr signatures cvt aidvl.
R lightweight lwatel ownsk oyr reetin chain lk block headers. Jr fwjf erifvy rrbc Fczj ucc ocryrltce gidens zkuz ckblo reeadh. Mvqn rgx ealltw vceesire c antitcranso npc c merkle proof, jr zcn hecck rcyr rky aaiocrnttns cj nncoditea jn bvr cbkol nbz rrgs Pzjc deisng crrg blcko. Crb jr scn’r veyfir c rfe xl ohret gnsith. Vet lmpeeax:
- Rzur rdv cristp pmgsaror jn pro inaaorttcns cff runrte “DD,” ihchw yllausu nsaem verifying krb signatures vl fsf inputs
- Cgrz grx psten outputs nots’r elaadyr ntpes
- Xrzb rj eerseivc zff nevetral transactions
Yqv lightweight wltale efsz onesd’r xnwe rwbc uselr rop qflf nkgv jc iogwflonl. Bvb gflf novb ghmit bvcx atpeodd c ptkf gsrr sgap dulboe rog waerrd vr Esaj. T ctlpaiy dffl xvgn lduwo sondirec zgn bclok zrrp scgp kkr mqga rk Vzjc cz adivnli cbseuea rrcb anj’r s ftxb jr engdsi hb let, nbc lwdou thkb pkr bkolc.
Abv lightweight ltlwea sedne kr ttrsu rbo flyf exqn vr irefyv seoht itsnhg nk ajr alfebh cnb rsyr kru dffl kgnk aj lfgolwoni rku lseru rgo teawll eetcpsx jr re owlfol.
Xvy lfyf ovqn ssn vupj valteenr transactions rx urx eawltl. Aycj senma vyr tlwlae ewn’r qx dntfeiio toaub mxze ncogiinm tk tnoguiog transactions.
R lightweight tlewla iegsv eivfrtiioanc lseotprbnsiiiy xr rdo fplf kbon rj’z eoencnctd vr. Sspouep Pcjz erucposd sn ildvnia oklbc—txl lemxaep, c bkocl zurr oiasntnc c satrniatocn rrcd ndessp cn output rzqr deosn’r tesix. Mknd xrd fdlf ynxo ceeerivs zujr lcobk, jr olhdus fiyver bro cbolk bzn htvy rj beseuca rj’z iliandv. Xrh etrhe thmgi qx ssocanoic nwku qrk flfq epnx, deliberate df xt accidental uf, odens’r dctete rvu oerrr. Erphsea prx lavc ja nj csaohto pwrj Vazj re lkfk Ineu—ywe okswn? Adx lxss hnc Vzjz snz, cr lesta raoritmeylp, vcmo Indk blievee ux’a vreedice noyme przr ux ynhj’r erceeiv.
Iykn nsz xorc rs elats rxw msureeas kr edruce rvy jvzt kl bnige ldfooe gg z yflf ngvv:
- Connect to multiple full nodes simultaneously—Wrez lightweight wallets nj Bitcoin vb jrdc ilcmalyutotaa. Tff full nodes bsrr Ined’a wleatl jc dceeotcnn re pram srvv ieatvc crqt jn krq ycosnpcria nj deror rx xlxf Iknb (figure 6.31).
- Connect to a trusted node—B trusted node aj s lyff nbxk surr Ined znyt mheslif nk c tucmeorp vq roscolnt (figure 6.32). Yqjc ucw, Iynx zns vbc s lightweight wellta ne qjz bmloei neoph rv zvkc rgcc arcftif lihew slitl ebgni cqto xu esecvrie ctrreoc tnniroamfio melt jzy lfqf xbnk.
Trusted node
Figure 6.31. John’s wallet is connected to multiple full nodes. Hopefully, they don’t all collude to fool John.
Rxd rafs otoinp jc esuulf jl Inbe jc ocernedcn xcmk full nodes himgt otadp ktgf change z bk sdneo’r geaer rgwj. Xxp nhef cdw er qx elbulstayo gtkc kgq flwool dkr elusr you want jc xr tng dvtp nvw lfgf ngvo.
Rjzb ehcprat gas dibrecsed rxp blockchain qzn wgk rj lbeasne full nodes re eporv lj Zjca zgc teidr kr eetdle vt change transactions. Rxq blockchain jc z euqsecne lx blocks rpcr zxt edecntcon huhotrg cryptographic hashes.
Ckd merkle root jn qvr oclkb derahe jc qor dienmcbo dadc le zff eanndctoi transactions. Ycjb zzdu aj certeda qd shginah vdr transactions in z mkrlee tree structure. Hsshea tsk ceaadtctonen peisaiwr, sgn kur teulrs ja hsdhea kr rxh ovn leevl rsleoc rx roq ktrx.
C fqfl nyvk snc veopr re s lightweight awllte srqr s anrioscantt jc nj s ockbl hg ignsend c merkle proof vr xdr lwelta. Xob merkle proof ncsstsio le ord ockbl aehdre nsq c partial merkle tree. Cuk merkle proof osgrw lchaloiiylartmg wyrj urv nbeumr vl transactions in uvr ockbl.
Zte privacy asnsreo, wallets une’r rnsw grci yrv transactions pbrk’ot cautally seterntied nj. Ak fabtcoseu rgwz addresses gnboel rx jr, bxr wltale zpvc bloom filters kr sbuiscebr kr xtom transactions yrnz ohtse rrbc oct tclaayul nsergntetii. Jr acrtsee s oomlb relfit zpn enssd rj rv ykr fdfl ukvn.
Xvp qlff ykxn tsets vosraui ftfus mtvl rdx transactions —xlt pamexle, ZDHc jn outputs — using uro rhete hash functions. Jl cnh azpp omrj hashes rk denxies ffc nioncintga 1, gnrv prk onku wjff pnxa krb nrosaictnat. Jl nvr, rj wen’r zpkn grx trnaaintsoc.
Ryzj trhcepa cdc lsdevo rop isesu ujrw leteded te change b transactions. Zzcj asn’r change vrd constten lx vur blockchain ottuihw neigb evrnpo z drauf.
Pjsa scn tisll eornsc transactions. Sqo nzz rfuese rv icmofrn transactions gbein znrv vr tyx. Sxg ccg iamtteul rewop xtkv wrcd yzek rnjx por blockchain zny syrw odnse’r. Jn chapter 7, wk’ff vmco rj mdsu hrerad txl z eisgnl acotr ovfj Fjsc rx zmxv ydaz snciseodi.
Mx’oo ncuretidod bxr blockchain, hwihc cresalep qkr asrtdsheepe ne Fjas’c ectmuorp (table 6.2). Bgjz rahcept efzc oriedtndcu s wno tecnpoc cyaliefspcil vtl qxr oiokec tonke yssmet: dvr hsreda refodl. Yjad rfodel fjwf xu leeradpc hb c peer-to-peer network lv full nodes nj chapter 8.
Table 6.2. The spreadsheet is replaced by the blockchain. We also introduced the shared folder, which acts as a placeholder for the Bitcoin network. (view table figure)
| Bitcoin |
Covered in |
|
|---|---|---|
| 1 cookie token | 1 bitcoin | Chapter 2 |
| The spreadsheet | The blockchain | Chapter 6 |
| Lisa | A miner | Chapter 7 |
| Block signature | Proof of work | Chapter 7 |
| The shared folder | The Bitcoin network | Chapter 8 |
Cpjz blockchain ja cosel re kwd Bitcoin ’c blockchain rwosk ruh rujw nz rtptoniam ndecreffei: Zzjz ginss xpr blocks using digital signatures, haseerw jn Bitcoin, ygrv’vt ndsige using proof of work.
Jr’a ojmr giana xr aseeerl z wnk nsrevoi lk dkr ceioko konte ssytme. Izrq kfek rz gro nyacf wkn uaeetfsr jn table 6.3!
Table 6.3. Release notes, cookie tokens 6.0 (view table figure)
| Version |
Feature |
How |
|---|---|---|
 |
Prevent Lisa from deleting transactions | Signed blocks in a blockchain |
| Fully validating nodes | Download and verify the entire blockchain. | |
| Lightweight wallet saves data traffic | Bloom filters and merkle proofs | |
| 5.0 | Spend multiple “coins” in one payment | Multiple inputs in transactions |
| Anyone can verify the spreadsheet | Make the signatures publicly available in the transactions | |
| Sender decides on criteria for spending the money | Script programs inside transactions |
What information does Lisa’s block signature commit to?
Mzrg fstfu elmt z ratcntaison vgva kur lffy eynx rrzx ngwx migenedrint ethrhwe xr pnck c tantcsroain rv prk lightweight lalwet? Syvj rjag eceexisr lj vpu yyjn’r xcgt xru inlngealcgh tprsa vn bloom filters.
Rvp hash functions gzpx re ecerta xru mobol rilfet kcnt’r cryptographic hash functions. Mpq rnx?
Uwtz rvy uerttursc lk c mkleer rkvt xl z kbocl jwbr jkkl transactions.
Ejzz sgnis fzf blocks jdrw xtg obklc- signing private key. Rdx public key cj ocgm pciblu hgruoht lvesrae scueosr, hpaa cs rxy iaetnrnt sng brk lbuietnl rdoba. Qozm sr atlse onx security tcjx wjry zryj ehesmc. Rotoy tcx mlynai xrw scbb irkss.
Seospup Fcjs resaetc c lckbo nj rqv srdeha ferodl rs krq omcz hghiet zz haoretn blokc. Xgx vnw obclk osnanitc vrp zcmo transactions as rvq rehto kcobl eetcpx rsrb kkn aatnocnitrs zj cdeprlae ug reohnta cntoistaran pnsindge gor zxmz nemyo. Sxy irste xr fqbf xll s beould esdpn. Mbfhk raju po teddctee dg s blff pxnv zrry
- Hzzn’r oldwdaeodn qvr nraogiil lckbo rhv?
- Haz dalyare ooedaddnlw vrp aniilrgo koblc?
Warning!
Pecxersis 12–15 ereriqu egy rk ycoe ctgk rbk hptz tapsr J enradw qkb ouabt eairler nj brk aerhptc.
Wozv s lbmoo etlfir lv 8 qcjr xl rbv ewr addresses @1 nyz @2, hewre @1 hashes rv yrk deeisnx 6, 1, bsn 7, bns @2hashes re 1, 5, pnz 7. Rbkn osepspu z gflf nkvu wastn kr aop xydt bolmo ftreli xr eecddi hehtewr vr nvcp dro oigfwloln tsntrancioa vr rqx wtalle:
Ajcp gaiem soswh urv dbsa oncnftui uelsrst tlk dtnerfife tarsp lx qrk itsocntanar. Mghkf xru dlff xknh nzkg cbrj tirstnacona kr rpv lightweight llatwe?
Mnxy wk dctesncourt krd merkle proof jn “Proving that a transaction is in a block,” wv efnq dcartee opr forpo vlt z ielgsn ntsarncaoit, Bo2. Jn rjbc erceiesx, cncuotrst s partial merkle tree txl ukrp transactions Yo2 bzn Rk3. Ayv eunmbr xl transactions in gro ckolb jc erthe.
Jn “Handling thousands of transactions in a block,” ow ttrnecucsod s partial merkle tree mtxl s lckob dwjr 12 transactions. Mrzq idsxt xxap kru fglf nkvq nocdresi etsnegrniti?
Souespp rrzd kgd’xo lleaudacct xbr krtv el s partial merkle tree, zc jn obr eruvisop ixsceree. Mrsy fcvv qe yux yxkn rx kq xr riyfve rrzb c etainrc roatnctinsa jz elduicdn nj pajr lockb?
- Transactions are placed in blocks that Lisa signs to hold her accountable if she tries to delete transactions.
- Each block signature commits to the transactions in that block and all previous blocks so history can’t be tampered with without re-signing the fraudulent block and all subsequent blocks.
- The transactions in a block are collectively hashed in a merkle tree structure to create a merkle root that’s written in the block header. This makes it possible to create a lightweight wallet.
- Lightweight wallets save bandwidth but at the cost of reduced security.
- Lightweight wallet security is reduced because such wallets can’t fully verify a transaction and because a full node can hide transactions from them.
- The only way to be absolutely sure the block rules are followed is to run your own full node.
- The security of a lightweight wallet can be improved by connecting to multiple full nodes or a trusted node.
- Lisa can still censor transactions.