dirvote.c 162 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572457345744575457645774578457945804581458245834584458545864587458845894590459145924593459445954596459745984599460046014602460346044605460646074608460946104611461246134614461546164617461846194620462146224623462446254626462746284629463046314632463346344635463646374638463946404641464246434644464546464647464846494650465146524653465446554656465746584659
  1. /* Copyright (c) 2001-2004, Roger Dingledine.
  2. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  3. * Copyright (c) 2007-2018, The Tor Project, Inc. */
  4. /* See LICENSE for licensing information */
  5. #define DIRVOTE_PRIVATE
  6. #include "core/or/or.h"
  7. #include "app/config/config.h"
  8. #include "core/or/policies.h"
  9. #include "core/or/protover.h"
  10. #include "core/or/tor_version_st.h"
  11. #include "core/or/versions.h"
  12. #include "feature/dirauth/bwauth.h"
  13. #include "feature/dirauth/dircollate.h"
  14. #include "feature/dirauth/dsigs_parse.h"
  15. #include "feature/dirauth/guardfraction.h"
  16. #include "feature/dirauth/recommend_pkg.h"
  17. #include "feature/dirauth/voteflags.h"
  18. #include "feature/dircache/dirserv.h"
  19. #include "feature/dirclient/dirclient.h"
  20. #include "feature/dircommon/directory.h"
  21. #include "feature/dirparse/microdesc_parse.h"
  22. #include "feature/dirparse/ns_parse.h"
  23. #include "feature/dirparse/parsecommon.h"
  24. #include "feature/dirparse/signing.h"
  25. #include "feature/nodelist/authcert.h"
  26. #include "feature/nodelist/dirlist.h"
  27. #include "feature/nodelist/fmt_routerstatus.h"
  28. #include "feature/nodelist/microdesc.h"
  29. #include "feature/nodelist/networkstatus.h"
  30. #include "feature/nodelist/nodelist.h"
  31. #include "feature/nodelist/routerlist.h"
  32. #include "feature/relay/router.h"
  33. #include "feature/relay/routerkeys.h"
  34. #include "feature/stats/rephist.h"
  35. #include "feature/client/entrynodes.h" /* needed for guardfraction methods */
  36. #include "feature/nodelist/torcert.h"
  37. #include "feature/dircommon/voting_schedule.h"
  38. #include "feature/dirauth/dirvote.h"
  39. #include "feature/dirauth/authmode.h"
  40. #include "feature/dirauth/shared_random_state.h"
  41. #include "feature/nodelist/authority_cert_st.h"
  42. #include "feature/dircache/cached_dir_st.h"
  43. #include "feature/dirclient/dir_server_st.h"
  44. #include "feature/nodelist/document_signature_st.h"
  45. #include "feature/nodelist/microdesc_st.h"
  46. #include "feature/nodelist/networkstatus_st.h"
  47. #include "feature/nodelist/networkstatus_voter_info_st.h"
  48. #include "feature/nodelist/node_st.h"
  49. #include "feature/dirauth/ns_detached_signatures_st.h"
  50. #include "feature/nodelist/routerinfo_st.h"
  51. #include "feature/nodelist/routerlist_st.h"
  52. #include "feature/dirauth/vote_microdesc_hash_st.h"
  53. #include "feature/nodelist/vote_routerstatus_st.h"
  54. #include "feature/dircommon/vote_timing_st.h"
  55. #include "lib/container/order.h"
  56. #include "lib/encoding/confline.h"
  57. #include "lib/crypt_ops/crypto_format.h"
  58. /**
  59. * \file dirvote.c
  60. * \brief Functions to compute directory consensus, and schedule voting.
  61. *
  62. * This module is the center of the consensus-voting based directory
  63. * authority system. With this system, a set of authorities first
  64. * publish vote based on their opinions of the network, and then compute
  65. * a consensus from those votes. Each authority signs the consensus,
  66. * and clients trust the consensus if enough known authorities have
  67. * signed it.
  68. *
  69. * The code in this module is only invoked on directory authorities. It's
  70. * responsible for:
  71. *
  72. * <ul>
  73. * <li>Generating this authority's vote networkstatus, based on the
  74. * authority's view of the network as represented in dirserv.c
  75. * <li>Formatting the vote networkstatus objects.
  76. * <li>Generating the microdescriptors that correspond to our own
  77. * vote.
  78. * <li>Sending votes to all the other authorities.
  79. * <li>Trying to fetch missing votes from other authorities.
  80. * <li>Computing the consensus from a set of votes, as well as
  81. * a "detached signature" object for other authorities to fetch.
  82. * <li>Collecting other authorities' signatures on the same consensus,
  83. * until there are enough.
  84. * <li>Publishing the consensus to the reset of the directory system.
  85. * <li>Scheduling all of the above operations.
  86. * </ul>
  87. *
  88. * The main entry points are in dirvote_act(), which handles scheduled
  89. * actions; and dirvote_add_vote() and dirvote_add_signatures(), which
  90. * handle uploaded and downloaded votes and signatures.
  91. *
  92. * (See dir-spec.txt from torspec.git for a complete specification of
  93. * the directory protocol and voting algorithms.)
  94. **/
  95. /** A consensus that we have built and are appending signatures to. Once it's
  96. * time to publish it, it will become an active consensus if it accumulates
  97. * enough signatures. */
  98. typedef struct pending_consensus_t {
  99. /** The body of the consensus that we're currently building. Once we
  100. * have it built, it goes into dirserv.c */
  101. char *body;
  102. /** The parsed in-progress consensus document. */
  103. networkstatus_t *consensus;
  104. } pending_consensus_t;
  105. /* DOCDOC dirvote_add_signatures_to_all_pending_consensuses */
  106. static int dirvote_add_signatures_to_all_pending_consensuses(
  107. const char *detached_signatures_body,
  108. const char *source,
  109. const char **msg_out);
  110. static int dirvote_add_signatures_to_pending_consensus(
  111. pending_consensus_t *pc,
  112. ns_detached_signatures_t *sigs,
  113. const char *source,
  114. int severity,
  115. const char **msg_out);
  116. static char *list_v3_auth_ids(void);
  117. static void dirvote_fetch_missing_votes(void);
  118. static void dirvote_fetch_missing_signatures(void);
  119. static int dirvote_perform_vote(void);
  120. static void dirvote_clear_votes(int all_votes);
  121. static int dirvote_compute_consensuses(void);
  122. static int dirvote_publish_consensus(void);
  123. /* =====
  124. * Certificate functions
  125. * ===== */
  126. /** Allocate and return a new authority_cert_t with the same contents as
  127. * <b>cert</b>. */
  128. STATIC authority_cert_t *
  129. authority_cert_dup(authority_cert_t *cert)
  130. {
  131. authority_cert_t *out = tor_malloc(sizeof(authority_cert_t));
  132. tor_assert(cert);
  133. memcpy(out, cert, sizeof(authority_cert_t));
  134. /* Now copy pointed-to things. */
  135. out->cache_info.signed_descriptor_body =
  136. tor_strndup(cert->cache_info.signed_descriptor_body,
  137. cert->cache_info.signed_descriptor_len);
  138. out->cache_info.saved_location = SAVED_NOWHERE;
  139. out->identity_key = crypto_pk_dup_key(cert->identity_key);
  140. out->signing_key = crypto_pk_dup_key(cert->signing_key);
  141. return out;
  142. }
  143. /* =====
  144. * Voting
  145. * =====*/
  146. /* If <b>opt_value</b> is non-NULL, return "keyword opt_value\n" in a new
  147. * string. Otherwise return a new empty string. */
  148. static char *
  149. format_line_if_present(const char *keyword, const char *opt_value)
  150. {
  151. if (opt_value) {
  152. char *result = NULL;
  153. tor_asprintf(&result, "%s %s\n", keyword, opt_value);
  154. return result;
  155. } else {
  156. return tor_strdup("");
  157. }
  158. }
  159. /** Format the recommended/required-relay-client protocols lines for a vote in
  160. * a newly allocated string, and return that string. */
  161. static char *
  162. format_protocols_lines_for_vote(const networkstatus_t *v3_ns)
  163. {
  164. char *recommended_relay_protocols_line = NULL;
  165. char *recommended_client_protocols_line = NULL;
  166. char *required_relay_protocols_line = NULL;
  167. char *required_client_protocols_line = NULL;
  168. recommended_relay_protocols_line =
  169. format_line_if_present("recommended-relay-protocols",
  170. v3_ns->recommended_relay_protocols);
  171. recommended_client_protocols_line =
  172. format_line_if_present("recommended-client-protocols",
  173. v3_ns->recommended_client_protocols);
  174. required_relay_protocols_line =
  175. format_line_if_present("required-relay-protocols",
  176. v3_ns->required_relay_protocols);
  177. required_client_protocols_line =
  178. format_line_if_present("required-client-protocols",
  179. v3_ns->required_client_protocols);
  180. char *result = NULL;
  181. tor_asprintf(&result, "%s%s%s%s",
  182. recommended_relay_protocols_line,
  183. recommended_client_protocols_line,
  184. required_relay_protocols_line,
  185. required_client_protocols_line);
  186. tor_free(recommended_relay_protocols_line);
  187. tor_free(recommended_client_protocols_line);
  188. tor_free(required_relay_protocols_line);
  189. tor_free(required_client_protocols_line);
  190. return result;
  191. }
  192. /** Return a new string containing the string representation of the vote in
  193. * <b>v3_ns</b>, signed with our v3 signing key <b>private_signing_key</b>.
  194. * For v3 authorities. */
  195. STATIC char *
  196. format_networkstatus_vote(crypto_pk_t *private_signing_key,
  197. networkstatus_t *v3_ns)
  198. {
  199. smartlist_t *chunks = smartlist_new();
  200. char *packages = NULL;
  201. char fingerprint[FINGERPRINT_LEN+1];
  202. char digest[DIGEST_LEN];
  203. uint32_t addr;
  204. char *protocols_lines = NULL;
  205. char *client_versions_line = NULL, *server_versions_line = NULL;
  206. char *shared_random_vote_str = NULL;
  207. networkstatus_voter_info_t *voter;
  208. char *status = NULL;
  209. tor_assert(private_signing_key);
  210. tor_assert(v3_ns->type == NS_TYPE_VOTE || v3_ns->type == NS_TYPE_OPINION);
  211. voter = smartlist_get(v3_ns->voters, 0);
  212. addr = voter->addr;
  213. base16_encode(fingerprint, sizeof(fingerprint),
  214. v3_ns->cert->cache_info.identity_digest, DIGEST_LEN);
  215. client_versions_line = format_line_if_present("client-versions",
  216. v3_ns->client_versions);
  217. server_versions_line = format_line_if_present("server-versions",
  218. v3_ns->server_versions);
  219. protocols_lines = format_protocols_lines_for_vote(v3_ns);
  220. if (v3_ns->package_lines) {
  221. smartlist_t *tmp = smartlist_new();
  222. SMARTLIST_FOREACH(v3_ns->package_lines, const char *, p,
  223. if (validate_recommended_package_line(p))
  224. smartlist_add_asprintf(tmp, "package %s\n", p));
  225. smartlist_sort_strings(tmp);
  226. packages = smartlist_join_strings(tmp, "", 0, NULL);
  227. SMARTLIST_FOREACH(tmp, char *, cp, tor_free(cp));
  228. smartlist_free(tmp);
  229. } else {
  230. packages = tor_strdup("");
  231. }
  232. /* Get shared random commitments/reveals line(s). */
  233. shared_random_vote_str = sr_get_string_for_vote();
  234. {
  235. char published[ISO_TIME_LEN+1];
  236. char va[ISO_TIME_LEN+1];
  237. char fu[ISO_TIME_LEN+1];
  238. char vu[ISO_TIME_LEN+1];
  239. char *flags = smartlist_join_strings(v3_ns->known_flags, " ", 0, NULL);
  240. /* XXXX Abstraction violation: should be pulling a field out of v3_ns.*/
  241. char *flag_thresholds = dirserv_get_flag_thresholds_line();
  242. char *params;
  243. char *bw_headers_line = NULL;
  244. authority_cert_t *cert = v3_ns->cert;
  245. char *methods =
  246. make_consensus_method_list(MIN_SUPPORTED_CONSENSUS_METHOD,
  247. MAX_SUPPORTED_CONSENSUS_METHOD, " ");
  248. format_iso_time(published, v3_ns->published);
  249. format_iso_time(va, v3_ns->valid_after);
  250. format_iso_time(fu, v3_ns->fresh_until);
  251. format_iso_time(vu, v3_ns->valid_until);
  252. if (v3_ns->net_params)
  253. params = smartlist_join_strings(v3_ns->net_params, " ", 0, NULL);
  254. else
  255. params = tor_strdup("");
  256. tor_assert(cert);
  257. /* v3_ns->bw_file_headers is only set when V3BandwidthsFile is
  258. * configured */
  259. if (v3_ns->bw_file_headers) {
  260. char *bw_file_headers = NULL;
  261. /* If there are too many headers, leave the header string NULL */
  262. if (! BUG(smartlist_len(v3_ns->bw_file_headers)
  263. > MAX_BW_FILE_HEADER_COUNT_IN_VOTE)) {
  264. bw_file_headers = smartlist_join_strings(v3_ns->bw_file_headers, " ",
  265. 0, NULL);
  266. if (BUG(strlen(bw_file_headers) > MAX_BW_FILE_HEADERS_LINE_LEN)) {
  267. /* Free and set to NULL, because the line was too long */
  268. tor_free(bw_file_headers);
  269. }
  270. }
  271. if (!bw_file_headers) {
  272. /* If parsing failed, add a bandwidth header line with no entries */
  273. bw_file_headers = tor_strdup("");
  274. }
  275. /* At this point, the line will always be present */
  276. bw_headers_line = format_line_if_present("bandwidth-file-headers",
  277. bw_file_headers);
  278. tor_free(bw_file_headers);
  279. }
  280. smartlist_add_asprintf(chunks,
  281. "network-status-version 3\n"
  282. "vote-status %s\n"
  283. "consensus-methods %s\n"
  284. "published %s\n"
  285. "valid-after %s\n"
  286. "fresh-until %s\n"
  287. "valid-until %s\n"
  288. "voting-delay %d %d\n"
  289. "%s%s" /* versions */
  290. "%s" /* protocols */
  291. "%s" /* packages */
  292. "known-flags %s\n"
  293. "flag-thresholds %s\n"
  294. "params %s\n"
  295. "dir-source %s %s %s %s %d %d\n"
  296. "contact %s\n"
  297. "%s" /* shared randomness information */
  298. "%s" /* bandwidth file headers */
  299. ,
  300. v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion",
  301. methods,
  302. published, va, fu, vu,
  303. v3_ns->vote_seconds, v3_ns->dist_seconds,
  304. client_versions_line,
  305. server_versions_line,
  306. protocols_lines,
  307. packages,
  308. flags,
  309. flag_thresholds,
  310. params,
  311. voter->nickname, fingerprint, voter->address,
  312. fmt_addr32(addr), voter->dir_port, voter->or_port,
  313. voter->contact,
  314. shared_random_vote_str ?
  315. shared_random_vote_str : "",
  316. bw_headers_line ?
  317. bw_headers_line : "");
  318. tor_free(params);
  319. tor_free(flags);
  320. tor_free(flag_thresholds);
  321. tor_free(methods);
  322. tor_free(shared_random_vote_str);
  323. tor_free(bw_headers_line);
  324. if (!tor_digest_is_zero(voter->legacy_id_digest)) {
  325. char fpbuf[HEX_DIGEST_LEN+1];
  326. base16_encode(fpbuf, sizeof(fpbuf), voter->legacy_id_digest, DIGEST_LEN);
  327. smartlist_add_asprintf(chunks, "legacy-dir-key %s\n", fpbuf);
  328. }
  329. smartlist_add(chunks, tor_strndup(cert->cache_info.signed_descriptor_body,
  330. cert->cache_info.signed_descriptor_len));
  331. }
  332. SMARTLIST_FOREACH_BEGIN(v3_ns->routerstatus_list, vote_routerstatus_t *,
  333. vrs) {
  334. char *rsf;
  335. vote_microdesc_hash_t *h;
  336. rsf = routerstatus_format_entry(&vrs->status,
  337. vrs->version, vrs->protocols,
  338. NS_V3_VOTE,
  339. ROUTERSTATUS_FORMAT_NO_CONSENSUS_METHOD,
  340. vrs);
  341. if (rsf)
  342. smartlist_add(chunks, rsf);
  343. for (h = vrs->microdesc; h; h = h->next) {
  344. smartlist_add_strdup(chunks, h->microdesc_hash_line);
  345. }
  346. } SMARTLIST_FOREACH_END(vrs);
  347. smartlist_add_strdup(chunks, "directory-footer\n");
  348. /* The digest includes everything up through the space after
  349. * directory-signature. (Yuck.) */
  350. crypto_digest_smartlist(digest, DIGEST_LEN, chunks,
  351. "directory-signature ", DIGEST_SHA1);
  352. {
  353. char signing_key_fingerprint[FINGERPRINT_LEN+1];
  354. if (crypto_pk_get_fingerprint(private_signing_key,
  355. signing_key_fingerprint, 0)<0) {
  356. log_warn(LD_BUG, "Unable to get fingerprint for signing key");
  357. goto err;
  358. }
  359. smartlist_add_asprintf(chunks, "directory-signature %s %s\n", fingerprint,
  360. signing_key_fingerprint);
  361. }
  362. {
  363. char *sig = router_get_dirobj_signature(digest, DIGEST_LEN,
  364. private_signing_key);
  365. if (!sig) {
  366. log_warn(LD_BUG, "Unable to sign networkstatus vote.");
  367. goto err;
  368. }
  369. smartlist_add(chunks, sig);
  370. }
  371. status = smartlist_join_strings(chunks, "", 0, NULL);
  372. {
  373. networkstatus_t *v;
  374. if (!(v = networkstatus_parse_vote_from_string(status, NULL,
  375. v3_ns->type))) {
  376. log_err(LD_BUG,"Generated a networkstatus %s we couldn't parse: "
  377. "<<%s>>",
  378. v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion", status);
  379. goto err;
  380. }
  381. networkstatus_vote_free(v);
  382. }
  383. goto done;
  384. err:
  385. tor_free(status);
  386. done:
  387. tor_free(client_versions_line);
  388. tor_free(server_versions_line);
  389. tor_free(protocols_lines);
  390. tor_free(packages);
  391. SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
  392. smartlist_free(chunks);
  393. return status;
  394. }
  395. /** Set *<b>timing_out</b> to the intervals at which we would like to vote.
  396. * Note that these aren't the intervals we'll use to vote; they're the ones
  397. * that we'll vote to use. */
  398. static void
  399. dirvote_get_preferred_voting_intervals(vote_timing_t *timing_out)
  400. {
  401. const or_options_t *options = get_options();
  402. tor_assert(timing_out);
  403. timing_out->vote_interval = options->V3AuthVotingInterval;
  404. timing_out->n_intervals_valid = options->V3AuthNIntervalsValid;
  405. timing_out->vote_delay = options->V3AuthVoteDelay;
  406. timing_out->dist_delay = options->V3AuthDistDelay;
  407. }
  408. /* =====
  409. * Consensus generation
  410. * ===== */
  411. /** If <b>vrs</b> has a hash made for the consensus method <b>method</b> with
  412. * the digest algorithm <b>alg</b>, decode it and copy it into
  413. * <b>digest256_out</b> and return 0. Otherwise return -1. */
  414. static int
  415. vote_routerstatus_find_microdesc_hash(char *digest256_out,
  416. const vote_routerstatus_t *vrs,
  417. int method,
  418. digest_algorithm_t alg)
  419. {
  420. /* XXXX only returns the sha256 method. */
  421. const vote_microdesc_hash_t *h;
  422. char mstr[64];
  423. size_t mlen;
  424. char dstr[64];
  425. tor_snprintf(mstr, sizeof(mstr), "%d", method);
  426. mlen = strlen(mstr);
  427. tor_snprintf(dstr, sizeof(dstr), " %s=",
  428. crypto_digest_algorithm_get_name(alg));
  429. for (h = vrs->microdesc; h; h = h->next) {
  430. const char *cp = h->microdesc_hash_line;
  431. size_t num_len;
  432. /* cp looks like \d+(,\d+)* (digesttype=val )+ . Let's hunt for mstr in
  433. * the first part. */
  434. while (1) {
  435. num_len = strspn(cp, "1234567890");
  436. if (num_len == mlen && fast_memeq(mstr, cp, mlen)) {
  437. /* This is the line. */
  438. char buf[BASE64_DIGEST256_LEN+1];
  439. /* XXXX ignores extraneous stuff if the digest is too long. This
  440. * seems harmless enough, right? */
  441. cp = strstr(cp, dstr);
  442. if (!cp)
  443. return -1;
  444. cp += strlen(dstr);
  445. strlcpy(buf, cp, sizeof(buf));
  446. return digest256_from_base64(digest256_out, buf);
  447. }
  448. if (num_len == 0 || cp[num_len] != ',')
  449. break;
  450. cp += num_len + 1;
  451. }
  452. }
  453. return -1;
  454. }
  455. /** Given a vote <b>vote</b> (not a consensus!), return its associated
  456. * networkstatus_voter_info_t. */
  457. static networkstatus_voter_info_t *
  458. get_voter(const networkstatus_t *vote)
  459. {
  460. tor_assert(vote);
  461. tor_assert(vote->type == NS_TYPE_VOTE);
  462. tor_assert(vote->voters);
  463. tor_assert(smartlist_len(vote->voters) == 1);
  464. return smartlist_get(vote->voters, 0);
  465. }
  466. /** Temporary structure used in constructing a list of dir-source entries
  467. * for a consensus. One of these is generated for every vote, and one more
  468. * for every legacy key in each vote. */
  469. typedef struct dir_src_ent_t {
  470. networkstatus_t *v;
  471. const char *digest;
  472. int is_legacy;
  473. } dir_src_ent_t;
  474. /** Helper for sorting networkstatus_t votes (not consensuses) by the
  475. * hash of their voters' identity digests. */
  476. static int
  477. compare_votes_by_authority_id_(const void **_a, const void **_b)
  478. {
  479. const networkstatus_t *a = *_a, *b = *_b;
  480. return fast_memcmp(get_voter(a)->identity_digest,
  481. get_voter(b)->identity_digest, DIGEST_LEN);
  482. }
  483. /** Helper: Compare the dir_src_ent_ts in *<b>_a</b> and *<b>_b</b> by
  484. * their identity digests, and return -1, 0, or 1 depending on their
  485. * ordering */
  486. static int
  487. compare_dir_src_ents_by_authority_id_(const void **_a, const void **_b)
  488. {
  489. const dir_src_ent_t *a = *_a, *b = *_b;
  490. const networkstatus_voter_info_t *a_v = get_voter(a->v),
  491. *b_v = get_voter(b->v);
  492. const char *a_id, *b_id;
  493. a_id = a->is_legacy ? a_v->legacy_id_digest : a_v->identity_digest;
  494. b_id = b->is_legacy ? b_v->legacy_id_digest : b_v->identity_digest;
  495. return fast_memcmp(a_id, b_id, DIGEST_LEN);
  496. }
  497. /** Given a sorted list of strings <b>in</b>, add every member to <b>out</b>
  498. * that occurs more than <b>min</b> times. */
  499. static void
  500. get_frequent_members(smartlist_t *out, smartlist_t *in, int min)
  501. {
  502. char *cur = NULL;
  503. int count = 0;
  504. SMARTLIST_FOREACH_BEGIN(in, char *, cp) {
  505. if (cur && !strcmp(cp, cur)) {
  506. ++count;
  507. } else {
  508. if (count > min)
  509. smartlist_add(out, cur);
  510. cur = cp;
  511. count = 1;
  512. }
  513. } SMARTLIST_FOREACH_END(cp);
  514. if (count > min)
  515. smartlist_add(out, cur);
  516. }
  517. /** Given a sorted list of strings <b>lst</b>, return the member that appears
  518. * most. Break ties in favor of later-occurring members. */
  519. #define get_most_frequent_member(lst) \
  520. smartlist_get_most_frequent_string(lst)
  521. /** Return 0 if and only if <b>a</b> and <b>b</b> are routerstatuses
  522. * that come from the same routerinfo, with the same derived elements.
  523. */
  524. static int
  525. compare_vote_rs(const vote_routerstatus_t *a, const vote_routerstatus_t *b)
  526. {
  527. int r;
  528. tor_assert(a);
  529. tor_assert(b);
  530. if ((r = fast_memcmp(a->status.identity_digest, b->status.identity_digest,
  531. DIGEST_LEN)))
  532. return r;
  533. if ((r = fast_memcmp(a->status.descriptor_digest,
  534. b->status.descriptor_digest,
  535. DIGEST_LEN)))
  536. return r;
  537. /* If we actually reached this point, then the identities and
  538. * the descriptor digests matched, so somebody is making SHA1 collisions.
  539. */
  540. #define CMP_FIELD(utype, itype, field) do { \
  541. utype aval = (utype) (itype) a->status.field; \
  542. utype bval = (utype) (itype) b->status.field; \
  543. utype u = bval - aval; \
  544. itype r2 = (itype) u; \
  545. if (r2 < 0) { \
  546. return -1; \
  547. } else if (r2 > 0) { \
  548. return 1; \
  549. } \
  550. } while (0)
  551. CMP_FIELD(uint64_t, int64_t, published_on);
  552. if ((r = strcmp(b->status.nickname, a->status.nickname)))
  553. return r;
  554. CMP_FIELD(unsigned, int, addr);
  555. CMP_FIELD(unsigned, int, or_port);
  556. CMP_FIELD(unsigned, int, dir_port);
  557. return 0;
  558. }
  559. /** Helper for sorting routerlists based on compare_vote_rs. */
  560. static int
  561. compare_vote_rs_(const void **_a, const void **_b)
  562. {
  563. const vote_routerstatus_t *a = *_a, *b = *_b;
  564. return compare_vote_rs(a,b);
  565. }
  566. /** Helper for sorting OR ports. */
  567. static int
  568. compare_orports_(const void **_a, const void **_b)
  569. {
  570. const tor_addr_port_t *a = *_a, *b = *_b;
  571. int r;
  572. if ((r = tor_addr_compare(&a->addr, &b->addr, CMP_EXACT)))
  573. return r;
  574. if ((r = (((int) b->port) - ((int) a->port))))
  575. return r;
  576. return 0;
  577. }
  578. /** Given a list of vote_routerstatus_t, all for the same router identity,
  579. * return whichever is most frequent, breaking ties in favor of more
  580. * recently published vote_routerstatus_t and in case of ties there,
  581. * in favor of smaller descriptor digest.
  582. */
  583. static vote_routerstatus_t *
  584. compute_routerstatus_consensus(smartlist_t *votes, int consensus_method,
  585. char *microdesc_digest256_out,
  586. tor_addr_port_t *best_alt_orport_out)
  587. {
  588. vote_routerstatus_t *most = NULL, *cur = NULL;
  589. int most_n = 0, cur_n = 0;
  590. time_t most_published = 0;
  591. /* compare_vote_rs_() sorts the items by identity digest (all the same),
  592. * then by SD digest. That way, if we have a tie that the published_on
  593. * date cannot break, we use the descriptor with the smaller digest.
  594. */
  595. smartlist_sort(votes, compare_vote_rs_);
  596. SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
  597. if (cur && !compare_vote_rs(cur, rs)) {
  598. ++cur_n;
  599. } else {
  600. if (cur && (cur_n > most_n ||
  601. (cur_n == most_n &&
  602. cur->status.published_on > most_published))) {
  603. most = cur;
  604. most_n = cur_n;
  605. most_published = cur->status.published_on;
  606. }
  607. cur_n = 1;
  608. cur = rs;
  609. }
  610. } SMARTLIST_FOREACH_END(rs);
  611. if (cur_n > most_n ||
  612. (cur && cur_n == most_n && cur->status.published_on > most_published)) {
  613. most = cur;
  614. // most_n = cur_n; // unused after this point.
  615. // most_published = cur->status.published_on; // unused after this point.
  616. }
  617. tor_assert(most);
  618. /* Vote on potential alternative (sets of) OR port(s) in the winning
  619. * routerstatuses.
  620. *
  621. * XXX prop186 There's at most one alternative OR port (_the_ IPv6
  622. * port) for now. */
  623. if (best_alt_orport_out) {
  624. smartlist_t *alt_orports = smartlist_new();
  625. const tor_addr_port_t *most_alt_orport = NULL;
  626. SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
  627. tor_assert(rs);
  628. if (compare_vote_rs(most, rs) == 0 &&
  629. !tor_addr_is_null(&rs->status.ipv6_addr)
  630. && rs->status.ipv6_orport) {
  631. smartlist_add(alt_orports, tor_addr_port_new(&rs->status.ipv6_addr,
  632. rs->status.ipv6_orport));
  633. }
  634. } SMARTLIST_FOREACH_END(rs);
  635. smartlist_sort(alt_orports, compare_orports_);
  636. most_alt_orport = smartlist_get_most_frequent(alt_orports,
  637. compare_orports_);
  638. if (most_alt_orport) {
  639. memcpy(best_alt_orport_out, most_alt_orport, sizeof(tor_addr_port_t));
  640. log_debug(LD_DIR, "\"a\" line winner for %s is %s",
  641. most->status.nickname,
  642. fmt_addrport(&most_alt_orport->addr, most_alt_orport->port));
  643. }
  644. SMARTLIST_FOREACH(alt_orports, tor_addr_port_t *, ap, tor_free(ap));
  645. smartlist_free(alt_orports);
  646. }
  647. if (microdesc_digest256_out) {
  648. smartlist_t *digests = smartlist_new();
  649. const uint8_t *best_microdesc_digest;
  650. SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
  651. char d[DIGEST256_LEN];
  652. if (compare_vote_rs(rs, most))
  653. continue;
  654. if (!vote_routerstatus_find_microdesc_hash(d, rs, consensus_method,
  655. DIGEST_SHA256))
  656. smartlist_add(digests, tor_memdup(d, sizeof(d)));
  657. } SMARTLIST_FOREACH_END(rs);
  658. smartlist_sort_digests256(digests);
  659. best_microdesc_digest = smartlist_get_most_frequent_digest256(digests);
  660. if (best_microdesc_digest)
  661. memcpy(microdesc_digest256_out, best_microdesc_digest, DIGEST256_LEN);
  662. SMARTLIST_FOREACH(digests, char *, cp, tor_free(cp));
  663. smartlist_free(digests);
  664. }
  665. return most;
  666. }
  667. /** Sorting helper: compare two strings based on their values as base-ten
  668. * positive integers. (Non-integers are treated as prior to all integers, and
  669. * compared lexically.) */
  670. static int
  671. cmp_int_strings_(const void **_a, const void **_b)
  672. {
  673. const char *a = *_a, *b = *_b;
  674. int ai = (int)tor_parse_long(a, 10, 1, INT_MAX, NULL, NULL);
  675. int bi = (int)tor_parse_long(b, 10, 1, INT_MAX, NULL, NULL);
  676. if (ai<bi) {
  677. return -1;
  678. } else if (ai==bi) {
  679. if (ai == 0) /* Parsing failed. */
  680. return strcmp(a, b);
  681. return 0;
  682. } else {
  683. return 1;
  684. }
  685. }
  686. /** Given a list of networkstatus_t votes, determine and return the number of
  687. * the highest consensus method that is supported by 2/3 of the voters. */
  688. static int
  689. compute_consensus_method(smartlist_t *votes)
  690. {
  691. smartlist_t *all_methods = smartlist_new();
  692. smartlist_t *acceptable_methods = smartlist_new();
  693. smartlist_t *tmp = smartlist_new();
  694. int min = (smartlist_len(votes) * 2) / 3;
  695. int n_ok;
  696. int result;
  697. SMARTLIST_FOREACH(votes, networkstatus_t *, vote,
  698. {
  699. tor_assert(vote->supported_methods);
  700. smartlist_add_all(tmp, vote->supported_methods);
  701. smartlist_sort(tmp, cmp_int_strings_);
  702. smartlist_uniq(tmp, cmp_int_strings_, NULL);
  703. smartlist_add_all(all_methods, tmp);
  704. smartlist_clear(tmp);
  705. });
  706. smartlist_sort(all_methods, cmp_int_strings_);
  707. get_frequent_members(acceptable_methods, all_methods, min);
  708. n_ok = smartlist_len(acceptable_methods);
  709. if (n_ok) {
  710. const char *best = smartlist_get(acceptable_methods, n_ok-1);
  711. result = (int)tor_parse_long(best, 10, 1, INT_MAX, NULL, NULL);
  712. } else {
  713. result = 1;
  714. }
  715. smartlist_free(tmp);
  716. smartlist_free(all_methods);
  717. smartlist_free(acceptable_methods);
  718. return result;
  719. }
  720. /** Return true iff <b>method</b> is a consensus method that we support. */
  721. static int
  722. consensus_method_is_supported(int method)
  723. {
  724. return (method >= MIN_SUPPORTED_CONSENSUS_METHOD) &&
  725. (method <= MAX_SUPPORTED_CONSENSUS_METHOD);
  726. }
  727. /** Return a newly allocated string holding the numbers between low and high
  728. * (inclusive) that are supported consensus methods. */
  729. STATIC char *
  730. make_consensus_method_list(int low, int high, const char *separator)
  731. {
  732. char *list;
  733. int i;
  734. smartlist_t *lst;
  735. lst = smartlist_new();
  736. for (i = low; i <= high; ++i) {
  737. if (!consensus_method_is_supported(i))
  738. continue;
  739. smartlist_add_asprintf(lst, "%d", i);
  740. }
  741. list = smartlist_join_strings(lst, separator, 0, NULL);
  742. tor_assert(list);
  743. SMARTLIST_FOREACH(lst, char *, cp, tor_free(cp));
  744. smartlist_free(lst);
  745. return list;
  746. }
  747. /** Helper: given <b>lst</b>, a list of version strings such that every
  748. * version appears once for every versioning voter who recommends it, return a
  749. * newly allocated string holding the resulting client-versions or
  750. * server-versions list. May change contents of <b>lst</b> */
  751. static char *
  752. compute_consensus_versions_list(smartlist_t *lst, int n_versioning)
  753. {
  754. int min = n_versioning / 2;
  755. smartlist_t *good = smartlist_new();
  756. char *result;
  757. SMARTLIST_FOREACH_BEGIN(lst, const char *, v) {
  758. if (strchr(v, ' ')) {
  759. log_warn(LD_DIR, "At least one authority has voted for a version %s "
  760. "that contains a space. This probably wasn't intentional, and "
  761. "is likely to cause trouble. Please tell them to stop it.",
  762. escaped(v));
  763. }
  764. } SMARTLIST_FOREACH_END(v);
  765. sort_version_list(lst, 0);
  766. get_frequent_members(good, lst, min);
  767. result = smartlist_join_strings(good, ",", 0, NULL);
  768. smartlist_free(good);
  769. return result;
  770. }
  771. /** Given a list of K=V values, return the int32_t value corresponding to
  772. * KEYWORD=, or default_val if no such value exists, or if the value is
  773. * corrupt.
  774. */
  775. STATIC int32_t
  776. dirvote_get_intermediate_param_value(const smartlist_t *param_list,
  777. const char *keyword,
  778. int32_t default_val)
  779. {
  780. unsigned int n_found = 0;
  781. int32_t value = default_val;
  782. SMARTLIST_FOREACH_BEGIN(param_list, const char *, k_v_pair) {
  783. if (!strcmpstart(k_v_pair, keyword) && k_v_pair[strlen(keyword)] == '=') {
  784. const char *integer_str = &k_v_pair[strlen(keyword)+1];
  785. int ok;
  786. value = (int32_t)
  787. tor_parse_long(integer_str, 10, INT32_MIN, INT32_MAX, &ok, NULL);
  788. if (BUG(! ok))
  789. return default_val;
  790. ++n_found;
  791. }
  792. } SMARTLIST_FOREACH_END(k_v_pair);
  793. if (n_found == 1) {
  794. return value;
  795. } else {
  796. tor_assert_nonfatal(n_found == 0);
  797. return default_val;
  798. }
  799. }
  800. /** Minimum number of directory authorities voting for a parameter to
  801. * include it in the consensus, if consensus method 12 or later is to be
  802. * used. See proposal 178 for details. */
  803. #define MIN_VOTES_FOR_PARAM 3
  804. /** Helper: given a list of valid networkstatus_t, return a new smartlist
  805. * containing the contents of the consensus network parameter set.
  806. */
  807. STATIC smartlist_t *
  808. dirvote_compute_params(smartlist_t *votes, int method, int total_authorities)
  809. {
  810. int i;
  811. int32_t *vals;
  812. int cur_param_len;
  813. const char *cur_param;
  814. const char *eq;
  815. const int n_votes = smartlist_len(votes);
  816. smartlist_t *output;
  817. smartlist_t *param_list = smartlist_new();
  818. (void) method;
  819. /* We require that the parameter lists in the votes are well-formed: that
  820. is, that their keywords are unique and sorted, and that their values are
  821. between INT32_MIN and INT32_MAX inclusive. This should be guaranteed by
  822. the parsing code. */
  823. vals = tor_calloc(n_votes, sizeof(int));
  824. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  825. if (!v->net_params)
  826. continue;
  827. smartlist_add_all(param_list, v->net_params);
  828. } SMARTLIST_FOREACH_END(v);
  829. if (smartlist_len(param_list) == 0) {
  830. tor_free(vals);
  831. return param_list;
  832. }
  833. smartlist_sort_strings(param_list);
  834. i = 0;
  835. cur_param = smartlist_get(param_list, 0);
  836. eq = strchr(cur_param, '=');
  837. tor_assert(eq);
  838. cur_param_len = (int)(eq+1 - cur_param);
  839. output = smartlist_new();
  840. SMARTLIST_FOREACH_BEGIN(param_list, const char *, param) {
  841. /* resolve spurious clang shallow analysis null pointer errors */
  842. tor_assert(param);
  843. const char *next_param;
  844. int ok=0;
  845. eq = strchr(param, '=');
  846. tor_assert(i<n_votes); /* Make sure we prevented vote-stuffing. */
  847. vals[i++] = (int32_t)
  848. tor_parse_long(eq+1, 10, INT32_MIN, INT32_MAX, &ok, NULL);
  849. tor_assert(ok); /* Already checked these when parsing. */
  850. if (param_sl_idx+1 == smartlist_len(param_list))
  851. next_param = NULL;
  852. else
  853. next_param = smartlist_get(param_list, param_sl_idx+1);
  854. if (!next_param || strncmp(next_param, param, cur_param_len)) {
  855. /* We've reached the end of a series. */
  856. /* Make sure enough authorities voted on this param, unless the
  857. * the consensus method we use is too old for that. */
  858. if (i > total_authorities/2 ||
  859. i >= MIN_VOTES_FOR_PARAM) {
  860. int32_t median = median_int32(vals, i);
  861. char *out_string = tor_malloc(64+cur_param_len);
  862. memcpy(out_string, param, cur_param_len);
  863. tor_snprintf(out_string+cur_param_len,64, "%ld", (long)median);
  864. smartlist_add(output, out_string);
  865. }
  866. i = 0;
  867. if (next_param) {
  868. eq = strchr(next_param, '=');
  869. cur_param_len = (int)(eq+1 - next_param);
  870. }
  871. }
  872. } SMARTLIST_FOREACH_END(param);
  873. smartlist_free(param_list);
  874. tor_free(vals);
  875. return output;
  876. }
  877. #define RANGE_CHECK(a,b,c,d,e,f,g,mx) \
  878. ((a) >= 0 && (a) <= (mx) && (b) >= 0 && (b) <= (mx) && \
  879. (c) >= 0 && (c) <= (mx) && (d) >= 0 && (d) <= (mx) && \
  880. (e) >= 0 && (e) <= (mx) && (f) >= 0 && (f) <= (mx) && \
  881. (g) >= 0 && (g) <= (mx))
  882. #define CHECK_EQ(a, b, margin) \
  883. ((a)-(b) >= 0 ? (a)-(b) <= (margin) : (b)-(a) <= (margin))
  884. typedef enum {
  885. BW_WEIGHTS_NO_ERROR = 0,
  886. BW_WEIGHTS_RANGE_ERROR = 1,
  887. BW_WEIGHTS_SUMG_ERROR = 2,
  888. BW_WEIGHTS_SUME_ERROR = 3,
  889. BW_WEIGHTS_SUMD_ERROR = 4,
  890. BW_WEIGHTS_BALANCE_MID_ERROR = 5,
  891. BW_WEIGHTS_BALANCE_EG_ERROR = 6
  892. } bw_weights_error_t;
  893. /**
  894. * Verify that any weightings satisfy the balanced formulas.
  895. */
  896. static bw_weights_error_t
  897. networkstatus_check_weights(int64_t Wgg, int64_t Wgd, int64_t Wmg,
  898. int64_t Wme, int64_t Wmd, int64_t Wee,
  899. int64_t Wed, int64_t scale, int64_t G,
  900. int64_t M, int64_t E, int64_t D, int64_t T,
  901. int64_t margin, int do_balance) {
  902. bw_weights_error_t berr = BW_WEIGHTS_NO_ERROR;
  903. // Wed + Wmd + Wgd == 1
  904. if (!CHECK_EQ(Wed + Wmd + Wgd, scale, margin)) {
  905. berr = BW_WEIGHTS_SUMD_ERROR;
  906. goto out;
  907. }
  908. // Wmg + Wgg == 1
  909. if (!CHECK_EQ(Wmg + Wgg, scale, margin)) {
  910. berr = BW_WEIGHTS_SUMG_ERROR;
  911. goto out;
  912. }
  913. // Wme + Wee == 1
  914. if (!CHECK_EQ(Wme + Wee, scale, margin)) {
  915. berr = BW_WEIGHTS_SUME_ERROR;
  916. goto out;
  917. }
  918. // Verify weights within range 0->1
  919. if (!RANGE_CHECK(Wgg, Wgd, Wmg, Wme, Wmd, Wed, Wee, scale)) {
  920. berr = BW_WEIGHTS_RANGE_ERROR;
  921. goto out;
  922. }
  923. if (do_balance) {
  924. // Wgg*G + Wgd*D == Wee*E + Wed*D, already scaled
  925. if (!CHECK_EQ(Wgg*G + Wgd*D, Wee*E + Wed*D, (margin*T)/3)) {
  926. berr = BW_WEIGHTS_BALANCE_EG_ERROR;
  927. goto out;
  928. }
  929. // Wgg*G + Wgd*D == M*scale + Wmd*D + Wme*E + Wmg*G, already scaled
  930. if (!CHECK_EQ(Wgg*G + Wgd*D, M*scale + Wmd*D + Wme*E + Wmg*G,
  931. (margin*T)/3)) {
  932. berr = BW_WEIGHTS_BALANCE_MID_ERROR;
  933. goto out;
  934. }
  935. }
  936. out:
  937. if (berr) {
  938. log_info(LD_DIR,
  939. "Bw weight mismatch %d. G=%"PRId64" M=%"PRId64
  940. " E=%"PRId64" D=%"PRId64" T=%"PRId64
  941. " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
  942. " Wgd=%d Wgg=%d Wme=%d Wmg=%d",
  943. berr,
  944. (G), (M), (E),
  945. (D), (T),
  946. (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
  947. (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg);
  948. }
  949. return berr;
  950. }
  951. /**
  952. * This function computes the bandwidth weights for consensus method 10.
  953. *
  954. * It returns true if weights could be computed, false otherwise.
  955. */
  956. int
  957. networkstatus_compute_bw_weights_v10(smartlist_t *chunks, int64_t G,
  958. int64_t M, int64_t E, int64_t D,
  959. int64_t T, int64_t weight_scale)
  960. {
  961. bw_weights_error_t berr = 0;
  962. int64_t Wgg = -1, Wgd = -1;
  963. int64_t Wmg = -1, Wme = -1, Wmd = -1;
  964. int64_t Wed = -1, Wee = -1;
  965. const char *casename;
  966. if (G <= 0 || M <= 0 || E <= 0 || D <= 0) {
  967. log_warn(LD_DIR, "Consensus with empty bandwidth: "
  968. "G=%"PRId64" M=%"PRId64" E=%"PRId64
  969. " D=%"PRId64" T=%"PRId64,
  970. (G), (M), (E),
  971. (D), (T));
  972. return 0;
  973. }
  974. /*
  975. * Computed from cases in 3.8.3 of dir-spec.txt
  976. *
  977. * 1. Neither are scarce
  978. * 2. Both Guard and Exit are scarce
  979. * a. R+D <= S
  980. * b. R+D > S
  981. * 3. One of Guard or Exit is scarce
  982. * a. S+D < T/3
  983. * b. S+D >= T/3
  984. */
  985. if (3*E >= T && 3*G >= T) { // E >= T/3 && G >= T/3
  986. /* Case 1: Neither are scarce. */
  987. casename = "Case 1 (Wgd=Wmd=Wed)";
  988. Wgd = weight_scale/3;
  989. Wed = weight_scale/3;
  990. Wmd = weight_scale/3;
  991. Wee = (weight_scale*(E+G+M))/(3*E);
  992. Wme = weight_scale - Wee;
  993. Wmg = (weight_scale*(2*G-E-M))/(3*G);
  994. Wgg = weight_scale - Wmg;
  995. berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
  996. weight_scale, G, M, E, D, T, 10, 1);
  997. if (berr) {
  998. log_warn(LD_DIR,
  999. "Bw Weights error %d for %s v10. G=%"PRId64" M=%"PRId64
  1000. " E=%"PRId64" D=%"PRId64" T=%"PRId64
  1001. " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
  1002. " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
  1003. berr, casename,
  1004. (G), (M), (E),
  1005. (D), (T),
  1006. (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
  1007. (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
  1008. return 0;
  1009. }
  1010. } else if (3*E < T && 3*G < T) { // E < T/3 && G < T/3
  1011. int64_t R = MIN(E, G);
  1012. int64_t S = MAX(E, G);
  1013. /*
  1014. * Case 2: Both Guards and Exits are scarce
  1015. * Balance D between E and G, depending upon
  1016. * D capacity and scarcity.
  1017. */
  1018. if (R+D < S) { // Subcase a
  1019. Wgg = weight_scale;
  1020. Wee = weight_scale;
  1021. Wmg = 0;
  1022. Wme = 0;
  1023. Wmd = 0;
  1024. if (E < G) {
  1025. casename = "Case 2a (E scarce)";
  1026. Wed = weight_scale;
  1027. Wgd = 0;
  1028. } else { /* E >= G */
  1029. casename = "Case 2a (G scarce)";
  1030. Wed = 0;
  1031. Wgd = weight_scale;
  1032. }
  1033. } else { // Subcase b: R+D >= S
  1034. casename = "Case 2b1 (Wgg=weight_scale, Wmd=Wgd)";
  1035. Wee = (weight_scale*(E - G + M))/E;
  1036. Wed = (weight_scale*(D - 2*E + 4*G - 2*M))/(3*D);
  1037. Wme = (weight_scale*(G-M))/E;
  1038. Wmg = 0;
  1039. Wgg = weight_scale;
  1040. Wmd = (weight_scale - Wed)/2;
  1041. Wgd = (weight_scale - Wed)/2;
  1042. berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
  1043. weight_scale, G, M, E, D, T, 10, 1);
  1044. if (berr) {
  1045. casename = "Case 2b2 (Wgg=weight_scale, Wee=weight_scale)";
  1046. Wgg = weight_scale;
  1047. Wee = weight_scale;
  1048. Wed = (weight_scale*(D - 2*E + G + M))/(3*D);
  1049. Wmd = (weight_scale*(D - 2*M + G + E))/(3*D);
  1050. Wme = 0;
  1051. Wmg = 0;
  1052. if (Wmd < 0) { // Can happen if M > T/3
  1053. casename = "Case 2b3 (Wmd=0)";
  1054. Wmd = 0;
  1055. log_warn(LD_DIR,
  1056. "Too much Middle bandwidth on the network to calculate "
  1057. "balanced bandwidth-weights. Consider increasing the "
  1058. "number of Guard nodes by lowering the requirements.");
  1059. }
  1060. Wgd = weight_scale - Wed - Wmd;
  1061. berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
  1062. Wed, weight_scale, G, M, E, D, T, 10, 1);
  1063. }
  1064. if (berr != BW_WEIGHTS_NO_ERROR &&
  1065. berr != BW_WEIGHTS_BALANCE_MID_ERROR) {
  1066. log_warn(LD_DIR,
  1067. "Bw Weights error %d for %s v10. G=%"PRId64" M=%"PRId64
  1068. " E=%"PRId64" D=%"PRId64" T=%"PRId64
  1069. " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
  1070. " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
  1071. berr, casename,
  1072. (G), (M), (E),
  1073. (D), (T),
  1074. (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
  1075. (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
  1076. return 0;
  1077. }
  1078. }
  1079. } else { // if (E < T/3 || G < T/3) {
  1080. int64_t S = MIN(E, G);
  1081. // Case 3: Exactly one of Guard or Exit is scarce
  1082. if (!(3*E < T || 3*G < T) || !(3*G >= T || 3*E >= T)) {
  1083. log_warn(LD_BUG,
  1084. "Bw-Weights Case 3 v10 but with G=%"PRId64" M="
  1085. "%"PRId64" E=%"PRId64" D=%"PRId64" T=%"PRId64,
  1086. (G), (M), (E),
  1087. (D), (T));
  1088. }
  1089. if (3*(S+D) < T) { // Subcase a: S+D < T/3
  1090. if (G < E) {
  1091. casename = "Case 3a (G scarce)";
  1092. Wgg = Wgd = weight_scale;
  1093. Wmd = Wed = Wmg = 0;
  1094. // Minor subcase, if E is more scarce than M,
  1095. // keep its bandwidth in place.
  1096. if (E < M) Wme = 0;
  1097. else Wme = (weight_scale*(E-M))/(2*E);
  1098. Wee = weight_scale-Wme;
  1099. } else { // G >= E
  1100. casename = "Case 3a (E scarce)";
  1101. Wee = Wed = weight_scale;
  1102. Wmd = Wgd = Wme = 0;
  1103. // Minor subcase, if G is more scarce than M,
  1104. // keep its bandwidth in place.
  1105. if (G < M) Wmg = 0;
  1106. else Wmg = (weight_scale*(G-M))/(2*G);
  1107. Wgg = weight_scale-Wmg;
  1108. }
  1109. } else { // Subcase b: S+D >= T/3
  1110. // D != 0 because S+D >= T/3
  1111. if (G < E) {
  1112. casename = "Case 3bg (G scarce, Wgg=weight_scale, Wmd == Wed)";
  1113. Wgg = weight_scale;
  1114. Wgd = (weight_scale*(D - 2*G + E + M))/(3*D);
  1115. Wmg = 0;
  1116. Wee = (weight_scale*(E+M))/(2*E);
  1117. Wme = weight_scale - Wee;
  1118. Wmd = (weight_scale - Wgd)/2;
  1119. Wed = (weight_scale - Wgd)/2;
  1120. berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
  1121. Wed, weight_scale, G, M, E, D, T, 10, 1);
  1122. } else { // G >= E
  1123. casename = "Case 3be (E scarce, Wee=weight_scale, Wmd == Wgd)";
  1124. Wee = weight_scale;
  1125. Wed = (weight_scale*(D - 2*E + G + M))/(3*D);
  1126. Wme = 0;
  1127. Wgg = (weight_scale*(G+M))/(2*G);
  1128. Wmg = weight_scale - Wgg;
  1129. Wmd = (weight_scale - Wed)/2;
  1130. Wgd = (weight_scale - Wed)/2;
  1131. berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
  1132. Wed, weight_scale, G, M, E, D, T, 10, 1);
  1133. }
  1134. if (berr) {
  1135. log_warn(LD_DIR,
  1136. "Bw Weights error %d for %s v10. G=%"PRId64" M=%"PRId64
  1137. " E=%"PRId64" D=%"PRId64" T=%"PRId64
  1138. " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
  1139. " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
  1140. berr, casename,
  1141. (G), (M), (E),
  1142. (D), (T),
  1143. (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
  1144. (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
  1145. return 0;
  1146. }
  1147. }
  1148. }
  1149. /* We cast down the weights to 32 bit ints on the assumption that
  1150. * weight_scale is ~= 10000. We need to ensure a rogue authority
  1151. * doesn't break this assumption to rig our weights */
  1152. tor_assert(0 < weight_scale && weight_scale <= INT32_MAX);
  1153. /*
  1154. * Provide Wgm=Wgg, Wmm=weight_scale, Wem=Wee, Weg=Wed. May later determine
  1155. * that middle nodes need different bandwidth weights for dirport traffic,
  1156. * or that weird exit policies need special weight, or that bridges
  1157. * need special weight.
  1158. *
  1159. * NOTE: This list is sorted.
  1160. */
  1161. smartlist_add_asprintf(chunks,
  1162. "bandwidth-weights Wbd=%d Wbe=%d Wbg=%d Wbm=%d "
  1163. "Wdb=%d "
  1164. "Web=%d Wed=%d Wee=%d Weg=%d Wem=%d "
  1165. "Wgb=%d Wgd=%d Wgg=%d Wgm=%d "
  1166. "Wmb=%d Wmd=%d Wme=%d Wmg=%d Wmm=%d\n",
  1167. (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale,
  1168. (int)weight_scale,
  1169. (int)weight_scale, (int)Wed, (int)Wee, (int)Wed, (int)Wee,
  1170. (int)weight_scale, (int)Wgd, (int)Wgg, (int)Wgg,
  1171. (int)weight_scale, (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale);
  1172. log_notice(LD_CIRC, "Computed bandwidth weights for %s with v10: "
  1173. "G=%"PRId64" M=%"PRId64" E=%"PRId64" D=%"PRId64
  1174. " T=%"PRId64,
  1175. casename,
  1176. (G), (M), (E),
  1177. (D), (T));
  1178. return 1;
  1179. }
  1180. /** Update total bandwidth weights (G/M/E/D/T) with the bandwidth of
  1181. * the router in <b>rs</b>. */
  1182. static void
  1183. update_total_bandwidth_weights(const routerstatus_t *rs,
  1184. int is_exit, int is_guard,
  1185. int64_t *G, int64_t *M, int64_t *E, int64_t *D,
  1186. int64_t *T)
  1187. {
  1188. int default_bandwidth = rs->bandwidth_kb;
  1189. int guardfraction_bandwidth = 0;
  1190. if (!rs->has_bandwidth) {
  1191. log_info(LD_BUG, "Missing consensus bandwidth for router %s",
  1192. rs->nickname);
  1193. return;
  1194. }
  1195. /* If this routerstatus represents a guard that we have
  1196. * guardfraction information on, use it to calculate its actual
  1197. * bandwidth. From proposal236:
  1198. *
  1199. * Similarly, when calculating the bandwidth-weights line as in
  1200. * section 3.8.3 of dir-spec.txt, directory authorities should treat N
  1201. * as if fraction F of its bandwidth has the guard flag and (1-F) does
  1202. * not. So when computing the totals G,M,E,D, each relay N with guard
  1203. * visibility fraction F and bandwidth B should be added as follows:
  1204. *
  1205. * G' = G + F*B, if N does not have the exit flag
  1206. * M' = M + (1-F)*B, if N does not have the exit flag
  1207. *
  1208. * or
  1209. *
  1210. * D' = D + F*B, if N has the exit flag
  1211. * E' = E + (1-F)*B, if N has the exit flag
  1212. *
  1213. * In this block of code, we prepare the bandwidth values by setting
  1214. * the default_bandwidth to F*B and guardfraction_bandwidth to (1-F)*B.
  1215. */
  1216. if (rs->has_guardfraction) {
  1217. guardfraction_bandwidth_t guardfraction_bw;
  1218. tor_assert(is_guard);
  1219. guard_get_guardfraction_bandwidth(&guardfraction_bw,
  1220. rs->bandwidth_kb,
  1221. rs->guardfraction_percentage);
  1222. default_bandwidth = guardfraction_bw.guard_bw;
  1223. guardfraction_bandwidth = guardfraction_bw.non_guard_bw;
  1224. }
  1225. /* Now calculate the total bandwidth weights with or without
  1226. * guardfraction. Depending on the flags of the relay, add its
  1227. * bandwidth to the appropriate weight pool. If it's a guard and
  1228. * guardfraction is enabled, add its bandwidth to both pools as
  1229. * indicated by the previous comment.
  1230. */
  1231. *T += default_bandwidth;
  1232. if (is_exit && is_guard) {
  1233. *D += default_bandwidth;
  1234. if (rs->has_guardfraction) {
  1235. *E += guardfraction_bandwidth;
  1236. }
  1237. } else if (is_exit) {
  1238. *E += default_bandwidth;
  1239. } else if (is_guard) {
  1240. *G += default_bandwidth;
  1241. if (rs->has_guardfraction) {
  1242. *M += guardfraction_bandwidth;
  1243. }
  1244. } else {
  1245. *M += default_bandwidth;
  1246. }
  1247. }
  1248. /** Considering the different recommended/required protocols sets as a
  1249. * 4-element array, return the element from <b>vote</b> for that protocol
  1250. * set.
  1251. */
  1252. static const char *
  1253. get_nth_protocol_set_vote(int n, const networkstatus_t *vote)
  1254. {
  1255. switch (n) {
  1256. case 0: return vote->recommended_client_protocols;
  1257. case 1: return vote->recommended_relay_protocols;
  1258. case 2: return vote->required_client_protocols;
  1259. case 3: return vote->required_relay_protocols;
  1260. default:
  1261. tor_assert_unreached();
  1262. return NULL;
  1263. }
  1264. }
  1265. /** Considering the different recommended/required protocols sets as a
  1266. * 4-element array, return a newly allocated string for the consensus value
  1267. * for the n'th set.
  1268. */
  1269. static char *
  1270. compute_nth_protocol_set(int n, int n_voters, const smartlist_t *votes)
  1271. {
  1272. const char *keyword;
  1273. smartlist_t *proto_votes = smartlist_new();
  1274. int threshold;
  1275. switch (n) {
  1276. case 0:
  1277. keyword = "recommended-client-protocols";
  1278. threshold = CEIL_DIV(n_voters, 2);
  1279. break;
  1280. case 1:
  1281. keyword = "recommended-relay-protocols";
  1282. threshold = CEIL_DIV(n_voters, 2);
  1283. break;
  1284. case 2:
  1285. keyword = "required-client-protocols";
  1286. threshold = CEIL_DIV(n_voters * 2, 3);
  1287. break;
  1288. case 3:
  1289. keyword = "required-relay-protocols";
  1290. threshold = CEIL_DIV(n_voters * 2, 3);
  1291. break;
  1292. default:
  1293. tor_assert_unreached();
  1294. return NULL;
  1295. }
  1296. SMARTLIST_FOREACH_BEGIN(votes, const networkstatus_t *, ns) {
  1297. const char *v = get_nth_protocol_set_vote(n, ns);
  1298. if (v)
  1299. smartlist_add(proto_votes, (void*)v);
  1300. } SMARTLIST_FOREACH_END(ns);
  1301. char *protocols = protover_compute_vote(proto_votes, threshold);
  1302. smartlist_free(proto_votes);
  1303. char *result = NULL;
  1304. tor_asprintf(&result, "%s %s\n", keyword, protocols);
  1305. tor_free(protocols);
  1306. return result;
  1307. }
  1308. /** Given a list of vote networkstatus_t in <b>votes</b>, our public
  1309. * authority <b>identity_key</b>, our private authority <b>signing_key</b>,
  1310. * and the number of <b>total_authorities</b> that we believe exist in our
  1311. * voting quorum, generate the text of a new v3 consensus or microdescriptor
  1312. * consensus (depending on <b>flavor</b>), and return the value in a newly
  1313. * allocated string.
  1314. *
  1315. * Note: this function DOES NOT check whether the votes are from
  1316. * recognized authorities. (dirvote_add_vote does that.)
  1317. *
  1318. * <strong>WATCH OUT</strong>: You need to think before you change the
  1319. * behavior of this function, or of the functions it calls! If some
  1320. * authorities compute the consensus with a different algorithm than
  1321. * others, they will not reach the same result, and they will not all
  1322. * sign the same thing! If you really need to change the algorithm
  1323. * here, you should allocate a new "consensus_method" for the new
  1324. * behavior, and make the new behavior conditional on a new-enough
  1325. * consensus_method.
  1326. **/
  1327. STATIC char *
  1328. networkstatus_compute_consensus(smartlist_t *votes,
  1329. int total_authorities,
  1330. crypto_pk_t *identity_key,
  1331. crypto_pk_t *signing_key,
  1332. const char *legacy_id_key_digest,
  1333. crypto_pk_t *legacy_signing_key,
  1334. consensus_flavor_t flavor)
  1335. {
  1336. smartlist_t *chunks;
  1337. char *result = NULL;
  1338. int consensus_method;
  1339. time_t valid_after, fresh_until, valid_until;
  1340. int vote_seconds, dist_seconds;
  1341. char *client_versions = NULL, *server_versions = NULL;
  1342. smartlist_t *flags;
  1343. const char *flavor_name;
  1344. uint32_t max_unmeasured_bw_kb = DEFAULT_MAX_UNMEASURED_BW_KB;
  1345. int64_t G, M, E, D, T; /* For bandwidth weights */
  1346. const routerstatus_format_type_t rs_format =
  1347. flavor == FLAV_NS ? NS_V3_CONSENSUS : NS_V3_CONSENSUS_MICRODESC;
  1348. char *params = NULL;
  1349. char *packages = NULL;
  1350. int added_weights = 0;
  1351. dircollator_t *collator = NULL;
  1352. smartlist_t *param_list = NULL;
  1353. tor_assert(flavor == FLAV_NS || flavor == FLAV_MICRODESC);
  1354. tor_assert(total_authorities >= smartlist_len(votes));
  1355. tor_assert(total_authorities > 0);
  1356. flavor_name = networkstatus_get_flavor_name(flavor);
  1357. if (!smartlist_len(votes)) {
  1358. log_warn(LD_DIR, "Can't compute a consensus from no votes.");
  1359. return NULL;
  1360. }
  1361. flags = smartlist_new();
  1362. consensus_method = compute_consensus_method(votes);
  1363. if (consensus_method_is_supported(consensus_method)) {
  1364. log_info(LD_DIR, "Generating consensus using method %d.",
  1365. consensus_method);
  1366. } else {
  1367. log_warn(LD_DIR, "The other authorities will use consensus method %d, "
  1368. "which I don't support. Maybe I should upgrade!",
  1369. consensus_method);
  1370. consensus_method = MAX_SUPPORTED_CONSENSUS_METHOD;
  1371. }
  1372. if (consensus_method >= MIN_METHOD_FOR_INIT_BW_WEIGHTS_ONE) {
  1373. /* It's smarter to initialize these weights to 1, so that later on,
  1374. * we can't accidentally divide by zero. */
  1375. G = M = E = D = 1;
  1376. T = 4;
  1377. } else {
  1378. /* ...but originally, they were set to zero. */
  1379. G = M = E = D = T = 0;
  1380. }
  1381. /* Compute medians of time-related things, and figure out how many
  1382. * routers we might need to talk about. */
  1383. {
  1384. int n_votes = smartlist_len(votes);
  1385. time_t *va_times = tor_calloc(n_votes, sizeof(time_t));
  1386. time_t *fu_times = tor_calloc(n_votes, sizeof(time_t));
  1387. time_t *vu_times = tor_calloc(n_votes, sizeof(time_t));
  1388. int *votesec_list = tor_calloc(n_votes, sizeof(int));
  1389. int *distsec_list = tor_calloc(n_votes, sizeof(int));
  1390. int n_versioning_clients = 0, n_versioning_servers = 0;
  1391. smartlist_t *combined_client_versions = smartlist_new();
  1392. smartlist_t *combined_server_versions = smartlist_new();
  1393. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1394. tor_assert(v->type == NS_TYPE_VOTE);
  1395. va_times[v_sl_idx] = v->valid_after;
  1396. fu_times[v_sl_idx] = v->fresh_until;
  1397. vu_times[v_sl_idx] = v->valid_until;
  1398. votesec_list[v_sl_idx] = v->vote_seconds;
  1399. distsec_list[v_sl_idx] = v->dist_seconds;
  1400. if (v->client_versions) {
  1401. smartlist_t *cv = smartlist_new();
  1402. ++n_versioning_clients;
  1403. smartlist_split_string(cv, v->client_versions, ",",
  1404. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  1405. sort_version_list(cv, 1);
  1406. smartlist_add_all(combined_client_versions, cv);
  1407. smartlist_free(cv); /* elements get freed later. */
  1408. }
  1409. if (v->server_versions) {
  1410. smartlist_t *sv = smartlist_new();
  1411. ++n_versioning_servers;
  1412. smartlist_split_string(sv, v->server_versions, ",",
  1413. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  1414. sort_version_list(sv, 1);
  1415. smartlist_add_all(combined_server_versions, sv);
  1416. smartlist_free(sv); /* elements get freed later. */
  1417. }
  1418. SMARTLIST_FOREACH(v->known_flags, const char *, cp,
  1419. smartlist_add_strdup(flags, cp));
  1420. } SMARTLIST_FOREACH_END(v);
  1421. valid_after = median_time(va_times, n_votes);
  1422. fresh_until = median_time(fu_times, n_votes);
  1423. valid_until = median_time(vu_times, n_votes);
  1424. vote_seconds = median_int(votesec_list, n_votes);
  1425. dist_seconds = median_int(distsec_list, n_votes);
  1426. tor_assert(valid_after +
  1427. (get_options()->TestingTorNetwork ?
  1428. MIN_VOTE_INTERVAL_TESTING : MIN_VOTE_INTERVAL) <= fresh_until);
  1429. tor_assert(fresh_until +
  1430. (get_options()->TestingTorNetwork ?
  1431. MIN_VOTE_INTERVAL_TESTING : MIN_VOTE_INTERVAL) <= valid_until);
  1432. tor_assert(vote_seconds >= MIN_VOTE_SECONDS);
  1433. tor_assert(dist_seconds >= MIN_DIST_SECONDS);
  1434. server_versions = compute_consensus_versions_list(combined_server_versions,
  1435. n_versioning_servers);
  1436. client_versions = compute_consensus_versions_list(combined_client_versions,
  1437. n_versioning_clients);
  1438. packages = compute_consensus_package_lines(votes);
  1439. SMARTLIST_FOREACH(combined_server_versions, char *, cp, tor_free(cp));
  1440. SMARTLIST_FOREACH(combined_client_versions, char *, cp, tor_free(cp));
  1441. smartlist_free(combined_server_versions);
  1442. smartlist_free(combined_client_versions);
  1443. smartlist_add_strdup(flags, "NoEdConsensus");
  1444. smartlist_sort_strings(flags);
  1445. smartlist_uniq_strings(flags);
  1446. tor_free(va_times);
  1447. tor_free(fu_times);
  1448. tor_free(vu_times);
  1449. tor_free(votesec_list);
  1450. tor_free(distsec_list);
  1451. }
  1452. chunks = smartlist_new();
  1453. {
  1454. char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
  1455. vu_buf[ISO_TIME_LEN+1];
  1456. char *flaglist;
  1457. format_iso_time(va_buf, valid_after);
  1458. format_iso_time(fu_buf, fresh_until);
  1459. format_iso_time(vu_buf, valid_until);
  1460. flaglist = smartlist_join_strings(flags, " ", 0, NULL);
  1461. smartlist_add_asprintf(chunks, "network-status-version 3%s%s\n"
  1462. "vote-status consensus\n",
  1463. flavor == FLAV_NS ? "" : " ",
  1464. flavor == FLAV_NS ? "" : flavor_name);
  1465. smartlist_add_asprintf(chunks, "consensus-method %d\n",
  1466. consensus_method);
  1467. smartlist_add_asprintf(chunks,
  1468. "valid-after %s\n"
  1469. "fresh-until %s\n"
  1470. "valid-until %s\n"
  1471. "voting-delay %d %d\n"
  1472. "client-versions %s\n"
  1473. "server-versions %s\n"
  1474. "%s" /* packages */
  1475. "known-flags %s\n",
  1476. va_buf, fu_buf, vu_buf,
  1477. vote_seconds, dist_seconds,
  1478. client_versions, server_versions,
  1479. packages,
  1480. flaglist);
  1481. tor_free(flaglist);
  1482. }
  1483. {
  1484. int num_dirauth = get_n_authorities(V3_DIRINFO);
  1485. int idx;
  1486. for (idx = 0; idx < 4; ++idx) {
  1487. char *proto_line = compute_nth_protocol_set(idx, num_dirauth, votes);
  1488. if (BUG(!proto_line))
  1489. continue;
  1490. smartlist_add(chunks, proto_line);
  1491. }
  1492. }
  1493. param_list = dirvote_compute_params(votes, consensus_method,
  1494. total_authorities);
  1495. if (smartlist_len(param_list)) {
  1496. params = smartlist_join_strings(param_list, " ", 0, NULL);
  1497. smartlist_add_strdup(chunks, "params ");
  1498. smartlist_add(chunks, params);
  1499. smartlist_add_strdup(chunks, "\n");
  1500. }
  1501. {
  1502. int num_dirauth = get_n_authorities(V3_DIRINFO);
  1503. /* Default value of this is 2/3 of the total number of authorities. For
  1504. * instance, if we have 9 dirauth, the default value is 6. The following
  1505. * calculation will round it down. */
  1506. int32_t num_srv_agreements =
  1507. dirvote_get_intermediate_param_value(param_list,
  1508. "AuthDirNumSRVAgreements",
  1509. (num_dirauth * 2) / 3);
  1510. /* Add the shared random value. */
  1511. char *srv_lines = sr_get_string_for_consensus(votes, num_srv_agreements);
  1512. if (srv_lines != NULL) {
  1513. smartlist_add(chunks, srv_lines);
  1514. }
  1515. }
  1516. /* Sort the votes. */
  1517. smartlist_sort(votes, compare_votes_by_authority_id_);
  1518. /* Add the authority sections. */
  1519. {
  1520. smartlist_t *dir_sources = smartlist_new();
  1521. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1522. dir_src_ent_t *e = tor_malloc_zero(sizeof(dir_src_ent_t));
  1523. e->v = v;
  1524. e->digest = get_voter(v)->identity_digest;
  1525. e->is_legacy = 0;
  1526. smartlist_add(dir_sources, e);
  1527. if (!tor_digest_is_zero(get_voter(v)->legacy_id_digest)) {
  1528. dir_src_ent_t *e_legacy = tor_malloc_zero(sizeof(dir_src_ent_t));
  1529. e_legacy->v = v;
  1530. e_legacy->digest = get_voter(v)->legacy_id_digest;
  1531. e_legacy->is_legacy = 1;
  1532. smartlist_add(dir_sources, e_legacy);
  1533. }
  1534. } SMARTLIST_FOREACH_END(v);
  1535. smartlist_sort(dir_sources, compare_dir_src_ents_by_authority_id_);
  1536. SMARTLIST_FOREACH_BEGIN(dir_sources, const dir_src_ent_t *, e) {
  1537. char fingerprint[HEX_DIGEST_LEN+1];
  1538. char votedigest[HEX_DIGEST_LEN+1];
  1539. networkstatus_t *v = e->v;
  1540. networkstatus_voter_info_t *voter = get_voter(v);
  1541. base16_encode(fingerprint, sizeof(fingerprint), e->digest, DIGEST_LEN);
  1542. base16_encode(votedigest, sizeof(votedigest), voter->vote_digest,
  1543. DIGEST_LEN);
  1544. smartlist_add_asprintf(chunks,
  1545. "dir-source %s%s %s %s %s %d %d\n",
  1546. voter->nickname, e->is_legacy ? "-legacy" : "",
  1547. fingerprint, voter->address, fmt_addr32(voter->addr),
  1548. voter->dir_port,
  1549. voter->or_port);
  1550. if (! e->is_legacy) {
  1551. smartlist_add_asprintf(chunks,
  1552. "contact %s\n"
  1553. "vote-digest %s\n",
  1554. voter->contact,
  1555. votedigest);
  1556. }
  1557. } SMARTLIST_FOREACH_END(e);
  1558. SMARTLIST_FOREACH(dir_sources, dir_src_ent_t *, e, tor_free(e));
  1559. smartlist_free(dir_sources);
  1560. }
  1561. {
  1562. char *max_unmeasured_param = NULL;
  1563. /* XXXX Extract this code into a common function. Or don't! see #19011 */
  1564. if (params) {
  1565. if (strcmpstart(params, "maxunmeasuredbw=") == 0)
  1566. max_unmeasured_param = params;
  1567. else
  1568. max_unmeasured_param = strstr(params, " maxunmeasuredbw=");
  1569. }
  1570. if (max_unmeasured_param) {
  1571. int ok = 0;
  1572. char *eq = strchr(max_unmeasured_param, '=');
  1573. if (eq) {
  1574. max_unmeasured_bw_kb = (uint32_t)
  1575. tor_parse_ulong(eq+1, 10, 1, UINT32_MAX, &ok, NULL);
  1576. if (!ok) {
  1577. log_warn(LD_DIR, "Bad element '%s' in max unmeasured bw param",
  1578. escaped(max_unmeasured_param));
  1579. max_unmeasured_bw_kb = DEFAULT_MAX_UNMEASURED_BW_KB;
  1580. }
  1581. }
  1582. }
  1583. }
  1584. /* Add the actual router entries. */
  1585. {
  1586. int *size; /* size[j] is the number of routerstatuses in votes[j]. */
  1587. int *flag_counts; /* The number of voters that list flag[j] for the
  1588. * currently considered router. */
  1589. int i;
  1590. smartlist_t *matching_descs = smartlist_new();
  1591. smartlist_t *chosen_flags = smartlist_new();
  1592. smartlist_t *versions = smartlist_new();
  1593. smartlist_t *protocols = smartlist_new();
  1594. smartlist_t *exitsummaries = smartlist_new();
  1595. uint32_t *bandwidths_kb = tor_calloc(smartlist_len(votes),
  1596. sizeof(uint32_t));
  1597. uint32_t *measured_bws_kb = tor_calloc(smartlist_len(votes),
  1598. sizeof(uint32_t));
  1599. uint32_t *measured_guardfraction = tor_calloc(smartlist_len(votes),
  1600. sizeof(uint32_t));
  1601. int num_bandwidths;
  1602. int num_mbws;
  1603. int num_guardfraction_inputs;
  1604. int *n_voter_flags; /* n_voter_flags[j] is the number of flags that
  1605. * votes[j] knows about. */
  1606. int *n_flag_voters; /* n_flag_voters[f] is the number of votes that care
  1607. * about flags[f]. */
  1608. int **flag_map; /* flag_map[j][b] is an index f such that flag_map[f]
  1609. * is the same flag as votes[j]->known_flags[b]. */
  1610. int *named_flag; /* Index of the flag "Named" for votes[j] */
  1611. int *unnamed_flag; /* Index of the flag "Unnamed" for votes[j] */
  1612. int n_authorities_measuring_bandwidth;
  1613. strmap_t *name_to_id_map = strmap_new();
  1614. char conflict[DIGEST_LEN];
  1615. char unknown[DIGEST_LEN];
  1616. memset(conflict, 0, sizeof(conflict));
  1617. memset(unknown, 0xff, sizeof(conflict));
  1618. size = tor_calloc(smartlist_len(votes), sizeof(int));
  1619. n_voter_flags = tor_calloc(smartlist_len(votes), sizeof(int));
  1620. n_flag_voters = tor_calloc(smartlist_len(flags), sizeof(int));
  1621. flag_map = tor_calloc(smartlist_len(votes), sizeof(int *));
  1622. named_flag = tor_calloc(smartlist_len(votes), sizeof(int));
  1623. unnamed_flag = tor_calloc(smartlist_len(votes), sizeof(int));
  1624. for (i = 0; i < smartlist_len(votes); ++i)
  1625. unnamed_flag[i] = named_flag[i] = -1;
  1626. /* Build the flag indexes. Note that no vote can have more than 64 members
  1627. * for known_flags, so no value will be greater than 63, so it's safe to
  1628. * do UINT64_C(1) << index on these values. But note also that
  1629. * named_flag and unnamed_flag are initialized to -1, so we need to check
  1630. * that they're actually set before doing UINT64_C(1) << index with
  1631. * them.*/
  1632. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1633. flag_map[v_sl_idx] = tor_calloc(smartlist_len(v->known_flags),
  1634. sizeof(int));
  1635. if (smartlist_len(v->known_flags) > MAX_KNOWN_FLAGS_IN_VOTE) {
  1636. log_warn(LD_BUG, "Somehow, a vote has %d entries in known_flags",
  1637. smartlist_len(v->known_flags));
  1638. }
  1639. SMARTLIST_FOREACH_BEGIN(v->known_flags, const char *, fl) {
  1640. int p = smartlist_string_pos(flags, fl);
  1641. tor_assert(p >= 0);
  1642. flag_map[v_sl_idx][fl_sl_idx] = p;
  1643. ++n_flag_voters[p];
  1644. if (!strcmp(fl, "Named"))
  1645. named_flag[v_sl_idx] = fl_sl_idx;
  1646. if (!strcmp(fl, "Unnamed"))
  1647. unnamed_flag[v_sl_idx] = fl_sl_idx;
  1648. } SMARTLIST_FOREACH_END(fl);
  1649. n_voter_flags[v_sl_idx] = smartlist_len(v->known_flags);
  1650. size[v_sl_idx] = smartlist_len(v->routerstatus_list);
  1651. } SMARTLIST_FOREACH_END(v);
  1652. /* Named and Unnamed get treated specially */
  1653. {
  1654. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1655. uint64_t nf;
  1656. if (named_flag[v_sl_idx]<0)
  1657. continue;
  1658. nf = UINT64_C(1) << named_flag[v_sl_idx];
  1659. SMARTLIST_FOREACH_BEGIN(v->routerstatus_list,
  1660. vote_routerstatus_t *, rs) {
  1661. if ((rs->flags & nf) != 0) {
  1662. const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
  1663. if (!d) {
  1664. /* We have no name officially mapped to this digest. */
  1665. strmap_set_lc(name_to_id_map, rs->status.nickname,
  1666. rs->status.identity_digest);
  1667. } else if (d != conflict &&
  1668. fast_memcmp(d, rs->status.identity_digest, DIGEST_LEN)) {
  1669. /* Authorities disagree about this nickname. */
  1670. strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
  1671. } else {
  1672. /* It's already a conflict, or it's already this ID. */
  1673. }
  1674. }
  1675. } SMARTLIST_FOREACH_END(rs);
  1676. } SMARTLIST_FOREACH_END(v);
  1677. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1678. uint64_t uf;
  1679. if (unnamed_flag[v_sl_idx]<0)
  1680. continue;
  1681. uf = UINT64_C(1) << unnamed_flag[v_sl_idx];
  1682. SMARTLIST_FOREACH_BEGIN(v->routerstatus_list,
  1683. vote_routerstatus_t *, rs) {
  1684. if ((rs->flags & uf) != 0) {
  1685. const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
  1686. if (d == conflict || d == unknown) {
  1687. /* Leave it alone; we know what it is. */
  1688. } else if (!d) {
  1689. /* We have no name officially mapped to this digest. */
  1690. strmap_set_lc(name_to_id_map, rs->status.nickname, unknown);
  1691. } else if (fast_memeq(d, rs->status.identity_digest, DIGEST_LEN)) {
  1692. /* Authorities disagree about this nickname. */
  1693. strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
  1694. } else {
  1695. /* It's mapped to a different name. */
  1696. }
  1697. }
  1698. } SMARTLIST_FOREACH_END(rs);
  1699. } SMARTLIST_FOREACH_END(v);
  1700. }
  1701. /* We need to know how many votes measure bandwidth. */
  1702. n_authorities_measuring_bandwidth = 0;
  1703. SMARTLIST_FOREACH(votes, const networkstatus_t *, v,
  1704. if (v->has_measured_bws) {
  1705. ++n_authorities_measuring_bandwidth;
  1706. }
  1707. );
  1708. /* Populate the collator */
  1709. collator = dircollator_new(smartlist_len(votes), total_authorities);
  1710. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1711. dircollator_add_vote(collator, v);
  1712. } SMARTLIST_FOREACH_END(v);
  1713. dircollator_collate(collator, consensus_method);
  1714. /* Now go through all the votes */
  1715. flag_counts = tor_calloc(smartlist_len(flags), sizeof(int));
  1716. const int num_routers = dircollator_n_routers(collator);
  1717. for (i = 0; i < num_routers; ++i) {
  1718. vote_routerstatus_t **vrs_lst =
  1719. dircollator_get_votes_for_router(collator, i);
  1720. vote_routerstatus_t *rs;
  1721. routerstatus_t rs_out;
  1722. const char *current_rsa_id = NULL;
  1723. const char *chosen_version;
  1724. const char *chosen_protocol_list;
  1725. const char *chosen_name = NULL;
  1726. int exitsummary_disagreement = 0;
  1727. int is_named = 0, is_unnamed = 0, is_running = 0, is_valid = 0;
  1728. int is_guard = 0, is_exit = 0, is_bad_exit = 0;
  1729. int naming_conflict = 0;
  1730. int n_listing = 0;
  1731. char microdesc_digest[DIGEST256_LEN];
  1732. tor_addr_port_t alt_orport = {TOR_ADDR_NULL, 0};
  1733. memset(flag_counts, 0, sizeof(int)*smartlist_len(flags));
  1734. smartlist_clear(matching_descs);
  1735. smartlist_clear(chosen_flags);
  1736. smartlist_clear(versions);
  1737. smartlist_clear(protocols);
  1738. num_bandwidths = 0;
  1739. num_mbws = 0;
  1740. num_guardfraction_inputs = 0;
  1741. int ed_consensus = 0;
  1742. const uint8_t *ed_consensus_val = NULL;
  1743. /* Okay, go through all the entries for this digest. */
  1744. for (int voter_idx = 0; voter_idx < smartlist_len(votes); ++voter_idx) {
  1745. if (vrs_lst[voter_idx] == NULL)
  1746. continue; /* This voter had nothing to say about this entry. */
  1747. rs = vrs_lst[voter_idx];
  1748. ++n_listing;
  1749. current_rsa_id = rs->status.identity_digest;
  1750. smartlist_add(matching_descs, rs);
  1751. if (rs->version && rs->version[0])
  1752. smartlist_add(versions, rs->version);
  1753. if (rs->protocols) {
  1754. /* We include this one even if it's empty: voting for an
  1755. * empty protocol list actually is meaningful. */
  1756. smartlist_add(protocols, rs->protocols);
  1757. }
  1758. /* Tally up all the flags. */
  1759. for (int flag = 0; flag < n_voter_flags[voter_idx]; ++flag) {
  1760. if (rs->flags & (UINT64_C(1) << flag))
  1761. ++flag_counts[flag_map[voter_idx][flag]];
  1762. }
  1763. if (named_flag[voter_idx] >= 0 &&
  1764. (rs->flags & (UINT64_C(1) << named_flag[voter_idx]))) {
  1765. if (chosen_name && strcmp(chosen_name, rs->status.nickname)) {
  1766. log_notice(LD_DIR, "Conflict on naming for router: %s vs %s",
  1767. chosen_name, rs->status.nickname);
  1768. naming_conflict = 1;
  1769. }
  1770. chosen_name = rs->status.nickname;
  1771. }
  1772. /* Count guardfraction votes and note down the values. */
  1773. if (rs->status.has_guardfraction) {
  1774. measured_guardfraction[num_guardfraction_inputs++] =
  1775. rs->status.guardfraction_percentage;
  1776. }
  1777. /* count bandwidths */
  1778. if (rs->has_measured_bw)
  1779. measured_bws_kb[num_mbws++] = rs->measured_bw_kb;
  1780. if (rs->status.has_bandwidth)
  1781. bandwidths_kb[num_bandwidths++] = rs->status.bandwidth_kb;
  1782. /* Count number for which ed25519 is canonical. */
  1783. if (rs->ed25519_reflects_consensus) {
  1784. ++ed_consensus;
  1785. if (ed_consensus_val) {
  1786. tor_assert(fast_memeq(ed_consensus_val, rs->ed25519_id,
  1787. ED25519_PUBKEY_LEN));
  1788. } else {
  1789. ed_consensus_val = rs->ed25519_id;
  1790. }
  1791. }
  1792. }
  1793. /* We don't include this router at all unless more than half of
  1794. * the authorities we believe in list it. */
  1795. if (n_listing <= total_authorities/2)
  1796. continue;
  1797. if (ed_consensus > 0) {
  1798. if (ed_consensus <= total_authorities / 2) {
  1799. log_warn(LD_BUG, "Not enough entries had ed_consensus set; how "
  1800. "can we have a consensus of %d?", ed_consensus);
  1801. }
  1802. }
  1803. /* The clangalyzer can't figure out that this will never be NULL
  1804. * if n_listing is at least 1 */
  1805. tor_assert(current_rsa_id);
  1806. /* Figure out the most popular opinion of what the most recent
  1807. * routerinfo and its contents are. */
  1808. memset(microdesc_digest, 0, sizeof(microdesc_digest));
  1809. rs = compute_routerstatus_consensus(matching_descs, consensus_method,
  1810. microdesc_digest, &alt_orport);
  1811. /* Copy bits of that into rs_out. */
  1812. memset(&rs_out, 0, sizeof(rs_out));
  1813. tor_assert(fast_memeq(current_rsa_id,
  1814. rs->status.identity_digest,DIGEST_LEN));
  1815. memcpy(rs_out.identity_digest, current_rsa_id, DIGEST_LEN);
  1816. memcpy(rs_out.descriptor_digest, rs->status.descriptor_digest,
  1817. DIGEST_LEN);
  1818. rs_out.addr = rs->status.addr;
  1819. rs_out.published_on = rs->status.published_on;
  1820. rs_out.dir_port = rs->status.dir_port;
  1821. rs_out.or_port = rs->status.or_port;
  1822. tor_addr_copy(&rs_out.ipv6_addr, &alt_orport.addr);
  1823. rs_out.ipv6_orport = alt_orport.port;
  1824. rs_out.has_bandwidth = 0;
  1825. rs_out.has_exitsummary = 0;
  1826. if (chosen_name && !naming_conflict) {
  1827. strlcpy(rs_out.nickname, chosen_name, sizeof(rs_out.nickname));
  1828. } else {
  1829. strlcpy(rs_out.nickname, rs->status.nickname, sizeof(rs_out.nickname));
  1830. }
  1831. {
  1832. const char *d = strmap_get_lc(name_to_id_map, rs_out.nickname);
  1833. if (!d) {
  1834. is_named = is_unnamed = 0;
  1835. } else if (fast_memeq(d, current_rsa_id, DIGEST_LEN)) {
  1836. is_named = 1; is_unnamed = 0;
  1837. } else {
  1838. is_named = 0; is_unnamed = 1;
  1839. }
  1840. }
  1841. /* Set the flags. */
  1842. smartlist_add(chosen_flags, (char*)"s"); /* for the start of the line. */
  1843. SMARTLIST_FOREACH_BEGIN(flags, const char *, fl) {
  1844. if (!strcmp(fl, "Named")) {
  1845. if (is_named)
  1846. smartlist_add(chosen_flags, (char*)fl);
  1847. } else if (!strcmp(fl, "Unnamed")) {
  1848. if (is_unnamed)
  1849. smartlist_add(chosen_flags, (char*)fl);
  1850. } else if (!strcmp(fl, "NoEdConsensus")) {
  1851. if (ed_consensus <= total_authorities/2)
  1852. smartlist_add(chosen_flags, (char*)fl);
  1853. } else {
  1854. if (flag_counts[fl_sl_idx] > n_flag_voters[fl_sl_idx]/2) {
  1855. smartlist_add(chosen_flags, (char*)fl);
  1856. if (!strcmp(fl, "Exit"))
  1857. is_exit = 1;
  1858. else if (!strcmp(fl, "Guard"))
  1859. is_guard = 1;
  1860. else if (!strcmp(fl, "Running"))
  1861. is_running = 1;
  1862. else if (!strcmp(fl, "BadExit"))
  1863. is_bad_exit = 1;
  1864. else if (!strcmp(fl, "Valid"))
  1865. is_valid = 1;
  1866. }
  1867. }
  1868. } SMARTLIST_FOREACH_END(fl);
  1869. /* Starting with consensus method 4 we do not list servers
  1870. * that are not running in a consensus. See Proposal 138 */
  1871. if (!is_running)
  1872. continue;
  1873. /* Starting with consensus method 24, we don't list servers
  1874. * that are not valid in a consensus. See Proposal 272 */
  1875. if (!is_valid)
  1876. continue;
  1877. /* Pick the version. */
  1878. if (smartlist_len(versions)) {
  1879. sort_version_list(versions, 0);
  1880. chosen_version = get_most_frequent_member(versions);
  1881. } else {
  1882. chosen_version = NULL;
  1883. }
  1884. /* Pick the protocol list */
  1885. if (smartlist_len(protocols)) {
  1886. smartlist_sort_strings(protocols);
  1887. chosen_protocol_list = get_most_frequent_member(protocols);
  1888. } else {
  1889. chosen_protocol_list = NULL;
  1890. }
  1891. /* If it's a guard and we have enough guardfraction votes,
  1892. calculate its consensus guardfraction value. */
  1893. if (is_guard && num_guardfraction_inputs > 2) {
  1894. rs_out.has_guardfraction = 1;
  1895. rs_out.guardfraction_percentage = median_uint32(measured_guardfraction,
  1896. num_guardfraction_inputs);
  1897. /* final value should be an integer percentage! */
  1898. tor_assert(rs_out.guardfraction_percentage <= 100);
  1899. }
  1900. /* Pick a bandwidth */
  1901. if (num_mbws > 2) {
  1902. rs_out.has_bandwidth = 1;
  1903. rs_out.bw_is_unmeasured = 0;
  1904. rs_out.bandwidth_kb = median_uint32(measured_bws_kb, num_mbws);
  1905. } else if (num_bandwidths > 0) {
  1906. rs_out.has_bandwidth = 1;
  1907. rs_out.bw_is_unmeasured = 1;
  1908. rs_out.bandwidth_kb = median_uint32(bandwidths_kb, num_bandwidths);
  1909. if (n_authorities_measuring_bandwidth > 2) {
  1910. /* Cap non-measured bandwidths. */
  1911. if (rs_out.bandwidth_kb > max_unmeasured_bw_kb) {
  1912. rs_out.bandwidth_kb = max_unmeasured_bw_kb;
  1913. }
  1914. }
  1915. }
  1916. /* Fix bug 2203: Do not count BadExit nodes as Exits for bw weights */
  1917. is_exit = is_exit && !is_bad_exit;
  1918. /* Update total bandwidth weights with the bandwidths of this router. */
  1919. {
  1920. update_total_bandwidth_weights(&rs_out,
  1921. is_exit, is_guard,
  1922. &G, &M, &E, &D, &T);
  1923. }
  1924. /* Ok, we already picked a descriptor digest we want to list
  1925. * previously. Now we want to use the exit policy summary from
  1926. * that descriptor. If everybody plays nice all the voters who
  1927. * listed that descriptor will have the same summary. If not then
  1928. * something is fishy and we'll use the most common one (breaking
  1929. * ties in favor of lexicographically larger one (only because it
  1930. * lets me reuse more existing code)).
  1931. *
  1932. * The other case that can happen is that no authority that voted
  1933. * for that descriptor has an exit policy summary. That's
  1934. * probably quite unlikely but can happen. In that case we use
  1935. * the policy that was most often listed in votes, again breaking
  1936. * ties like in the previous case.
  1937. */
  1938. {
  1939. /* Okay, go through all the votes for this router. We prepared
  1940. * that list previously */
  1941. const char *chosen_exitsummary = NULL;
  1942. smartlist_clear(exitsummaries);
  1943. SMARTLIST_FOREACH_BEGIN(matching_descs, vote_routerstatus_t *, vsr) {
  1944. /* Check if the vote where this status comes from had the
  1945. * proper descriptor */
  1946. tor_assert(fast_memeq(rs_out.identity_digest,
  1947. vsr->status.identity_digest,
  1948. DIGEST_LEN));
  1949. if (vsr->status.has_exitsummary &&
  1950. fast_memeq(rs_out.descriptor_digest,
  1951. vsr->status.descriptor_digest,
  1952. DIGEST_LEN)) {
  1953. tor_assert(vsr->status.exitsummary);
  1954. smartlist_add(exitsummaries, vsr->status.exitsummary);
  1955. if (!chosen_exitsummary) {
  1956. chosen_exitsummary = vsr->status.exitsummary;
  1957. } else if (strcmp(chosen_exitsummary, vsr->status.exitsummary)) {
  1958. /* Great. There's disagreement among the voters. That
  1959. * really shouldn't be */
  1960. exitsummary_disagreement = 1;
  1961. }
  1962. }
  1963. } SMARTLIST_FOREACH_END(vsr);
  1964. if (exitsummary_disagreement) {
  1965. char id[HEX_DIGEST_LEN+1];
  1966. char dd[HEX_DIGEST_LEN+1];
  1967. base16_encode(id, sizeof(dd), rs_out.identity_digest, DIGEST_LEN);
  1968. base16_encode(dd, sizeof(dd), rs_out.descriptor_digest, DIGEST_LEN);
  1969. log_warn(LD_DIR, "The voters disagreed on the exit policy summary "
  1970. " for router %s with descriptor %s. This really shouldn't"
  1971. " have happened.", id, dd);
  1972. smartlist_sort_strings(exitsummaries);
  1973. chosen_exitsummary = get_most_frequent_member(exitsummaries);
  1974. } else if (!chosen_exitsummary) {
  1975. char id[HEX_DIGEST_LEN+1];
  1976. char dd[HEX_DIGEST_LEN+1];
  1977. base16_encode(id, sizeof(dd), rs_out.identity_digest, DIGEST_LEN);
  1978. base16_encode(dd, sizeof(dd), rs_out.descriptor_digest, DIGEST_LEN);
  1979. log_warn(LD_DIR, "Not one of the voters that made us select"
  1980. "descriptor %s for router %s had an exit policy"
  1981. "summary", dd, id);
  1982. /* Ok, none of those voting for the digest we chose had an
  1983. * exit policy for us. Well, that kinda sucks.
  1984. */
  1985. smartlist_clear(exitsummaries);
  1986. SMARTLIST_FOREACH(matching_descs, vote_routerstatus_t *, vsr, {
  1987. if (vsr->status.has_exitsummary)
  1988. smartlist_add(exitsummaries, vsr->status.exitsummary);
  1989. });
  1990. smartlist_sort_strings(exitsummaries);
  1991. chosen_exitsummary = get_most_frequent_member(exitsummaries);
  1992. if (!chosen_exitsummary)
  1993. log_warn(LD_DIR, "Wow, not one of the voters had an exit "
  1994. "policy summary for %s. Wow.", id);
  1995. }
  1996. if (chosen_exitsummary) {
  1997. rs_out.has_exitsummary = 1;
  1998. /* yea, discards the const */
  1999. rs_out.exitsummary = (char *)chosen_exitsummary;
  2000. }
  2001. }
  2002. if (flavor == FLAV_MICRODESC &&
  2003. tor_digest256_is_zero(microdesc_digest)) {
  2004. /* With no microdescriptor digest, we omit the entry entirely. */
  2005. continue;
  2006. }
  2007. {
  2008. char *buf;
  2009. /* Okay!! Now we can write the descriptor... */
  2010. /* First line goes into "buf". */
  2011. buf = routerstatus_format_entry(&rs_out, NULL, NULL,
  2012. rs_format, consensus_method, NULL);
  2013. if (buf)
  2014. smartlist_add(chunks, buf);
  2015. }
  2016. /* Now an m line, if applicable. */
  2017. if (flavor == FLAV_MICRODESC &&
  2018. !tor_digest256_is_zero(microdesc_digest)) {
  2019. char m[BASE64_DIGEST256_LEN+1];
  2020. digest256_to_base64(m, microdesc_digest);
  2021. smartlist_add_asprintf(chunks, "m %s\n", m);
  2022. }
  2023. /* Next line is all flags. The "\n" is missing. */
  2024. smartlist_add(chunks,
  2025. smartlist_join_strings(chosen_flags, " ", 0, NULL));
  2026. /* Now the version line. */
  2027. if (chosen_version) {
  2028. smartlist_add_strdup(chunks, "\nv ");
  2029. smartlist_add_strdup(chunks, chosen_version);
  2030. }
  2031. smartlist_add_strdup(chunks, "\n");
  2032. if (chosen_protocol_list &&
  2033. consensus_method >= MIN_METHOD_FOR_RS_PROTOCOLS) {
  2034. smartlist_add_asprintf(chunks, "pr %s\n", chosen_protocol_list);
  2035. }
  2036. /* Now the weight line. */
  2037. if (rs_out.has_bandwidth) {
  2038. char *guardfraction_str = NULL;
  2039. int unmeasured = rs_out.bw_is_unmeasured;
  2040. /* If we have guardfraction info, include it in the 'w' line. */
  2041. if (rs_out.has_guardfraction) {
  2042. tor_asprintf(&guardfraction_str,
  2043. " GuardFraction=%u", rs_out.guardfraction_percentage);
  2044. }
  2045. smartlist_add_asprintf(chunks, "w Bandwidth=%d%s%s\n",
  2046. rs_out.bandwidth_kb,
  2047. unmeasured?" Unmeasured=1":"",
  2048. guardfraction_str ? guardfraction_str : "");
  2049. tor_free(guardfraction_str);
  2050. }
  2051. /* Now the exitpolicy summary line. */
  2052. if (rs_out.has_exitsummary && flavor == FLAV_NS) {
  2053. smartlist_add_asprintf(chunks, "p %s\n", rs_out.exitsummary);
  2054. }
  2055. /* And the loop is over and we move on to the next router */
  2056. }
  2057. tor_free(size);
  2058. tor_free(n_voter_flags);
  2059. tor_free(n_flag_voters);
  2060. for (i = 0; i < smartlist_len(votes); ++i)
  2061. tor_free(flag_map[i]);
  2062. tor_free(flag_map);
  2063. tor_free(flag_counts);
  2064. tor_free(named_flag);
  2065. tor_free(unnamed_flag);
  2066. strmap_free(name_to_id_map, NULL);
  2067. smartlist_free(matching_descs);
  2068. smartlist_free(chosen_flags);
  2069. smartlist_free(versions);
  2070. smartlist_free(protocols);
  2071. smartlist_free(exitsummaries);
  2072. tor_free(bandwidths_kb);
  2073. tor_free(measured_bws_kb);
  2074. tor_free(measured_guardfraction);
  2075. }
  2076. /* Mark the directory footer region */
  2077. smartlist_add_strdup(chunks, "directory-footer\n");
  2078. {
  2079. int64_t weight_scale = BW_WEIGHT_SCALE;
  2080. char *bw_weight_param = NULL;
  2081. // Parse params, extract BW_WEIGHT_SCALE if present
  2082. // DO NOT use consensus_param_bw_weight_scale() in this code!
  2083. // The consensus is not formed yet!
  2084. /* XXXX Extract this code into a common function. Or not: #19011. */
  2085. if (params) {
  2086. if (strcmpstart(params, "bwweightscale=") == 0)
  2087. bw_weight_param = params;
  2088. else
  2089. bw_weight_param = strstr(params, " bwweightscale=");
  2090. }
  2091. if (bw_weight_param) {
  2092. int ok=0;
  2093. char *eq = strchr(bw_weight_param, '=');
  2094. if (eq) {
  2095. weight_scale = tor_parse_long(eq+1, 10, 1, INT32_MAX, &ok,
  2096. NULL);
  2097. if (!ok) {
  2098. log_warn(LD_DIR, "Bad element '%s' in bw weight param",
  2099. escaped(bw_weight_param));
  2100. weight_scale = BW_WEIGHT_SCALE;
  2101. }
  2102. } else {
  2103. log_warn(LD_DIR, "Bad element '%s' in bw weight param",
  2104. escaped(bw_weight_param));
  2105. weight_scale = BW_WEIGHT_SCALE;
  2106. }
  2107. }
  2108. added_weights = networkstatus_compute_bw_weights_v10(chunks, G, M, E, D,
  2109. T, weight_scale);
  2110. }
  2111. /* Add a signature. */
  2112. {
  2113. char digest[DIGEST256_LEN];
  2114. char fingerprint[HEX_DIGEST_LEN+1];
  2115. char signing_key_fingerprint[HEX_DIGEST_LEN+1];
  2116. digest_algorithm_t digest_alg =
  2117. flavor == FLAV_NS ? DIGEST_SHA1 : DIGEST_SHA256;
  2118. size_t digest_len =
  2119. flavor == FLAV_NS ? DIGEST_LEN : DIGEST256_LEN;
  2120. const char *algname = crypto_digest_algorithm_get_name(digest_alg);
  2121. char *signature;
  2122. smartlist_add_strdup(chunks, "directory-signature ");
  2123. /* Compute the hash of the chunks. */
  2124. crypto_digest_smartlist(digest, digest_len, chunks, "", digest_alg);
  2125. /* Get the fingerprints */
  2126. crypto_pk_get_fingerprint(identity_key, fingerprint, 0);
  2127. crypto_pk_get_fingerprint(signing_key, signing_key_fingerprint, 0);
  2128. /* add the junk that will go at the end of the line. */
  2129. if (flavor == FLAV_NS) {
  2130. smartlist_add_asprintf(chunks, "%s %s\n", fingerprint,
  2131. signing_key_fingerprint);
  2132. } else {
  2133. smartlist_add_asprintf(chunks, "%s %s %s\n",
  2134. algname, fingerprint,
  2135. signing_key_fingerprint);
  2136. }
  2137. /* And the signature. */
  2138. if (!(signature = router_get_dirobj_signature(digest, digest_len,
  2139. signing_key))) {
  2140. log_warn(LD_BUG, "Couldn't sign consensus networkstatus.");
  2141. goto done;
  2142. }
  2143. smartlist_add(chunks, signature);
  2144. if (legacy_id_key_digest && legacy_signing_key) {
  2145. smartlist_add_strdup(chunks, "directory-signature ");
  2146. base16_encode(fingerprint, sizeof(fingerprint),
  2147. legacy_id_key_digest, DIGEST_LEN);
  2148. crypto_pk_get_fingerprint(legacy_signing_key,
  2149. signing_key_fingerprint, 0);
  2150. if (flavor == FLAV_NS) {
  2151. smartlist_add_asprintf(chunks, "%s %s\n", fingerprint,
  2152. signing_key_fingerprint);
  2153. } else {
  2154. smartlist_add_asprintf(chunks, "%s %s %s\n",
  2155. algname, fingerprint,
  2156. signing_key_fingerprint);
  2157. }
  2158. if (!(signature = router_get_dirobj_signature(digest, digest_len,
  2159. legacy_signing_key))) {
  2160. log_warn(LD_BUG, "Couldn't sign consensus networkstatus.");
  2161. goto done;
  2162. }
  2163. smartlist_add(chunks, signature);
  2164. }
  2165. }
  2166. result = smartlist_join_strings(chunks, "", 0, NULL);
  2167. {
  2168. networkstatus_t *c;
  2169. if (!(c = networkstatus_parse_vote_from_string(result, NULL,
  2170. NS_TYPE_CONSENSUS))) {
  2171. log_err(LD_BUG, "Generated a networkstatus consensus we couldn't "
  2172. "parse.");
  2173. tor_free(result);
  2174. goto done;
  2175. }
  2176. // Verify balancing parameters
  2177. if (added_weights) {
  2178. networkstatus_verify_bw_weights(c, consensus_method);
  2179. }
  2180. networkstatus_vote_free(c);
  2181. }
  2182. done:
  2183. dircollator_free(collator);
  2184. tor_free(client_versions);
  2185. tor_free(server_versions);
  2186. tor_free(packages);
  2187. SMARTLIST_FOREACH(flags, char *, cp, tor_free(cp));
  2188. smartlist_free(flags);
  2189. SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
  2190. smartlist_free(chunks);
  2191. SMARTLIST_FOREACH(param_list, char *, cp, tor_free(cp));
  2192. smartlist_free(param_list);
  2193. return result;
  2194. }
  2195. /** Given a list of networkstatus_t for each vote, return a newly allocated
  2196. * string containing the "package" lines for the vote. */
  2197. STATIC char *
  2198. compute_consensus_package_lines(smartlist_t *votes)
  2199. {
  2200. const int n_votes = smartlist_len(votes);
  2201. /* This will be a map from "packagename version" strings to arrays
  2202. * of const char *, with the i'th member of the array corresponding to the
  2203. * package line from the i'th vote.
  2204. */
  2205. strmap_t *package_status = strmap_new();
  2206. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  2207. if (! v->package_lines)
  2208. continue;
  2209. SMARTLIST_FOREACH_BEGIN(v->package_lines, const char *, line) {
  2210. if (! validate_recommended_package_line(line))
  2211. continue;
  2212. /* Skip 'cp' to the second space in the line. */
  2213. const char *cp = strchr(line, ' ');
  2214. if (!cp) continue;
  2215. ++cp;
  2216. cp = strchr(cp, ' ');
  2217. if (!cp) continue;
  2218. char *key = tor_strndup(line, cp - line);
  2219. const char **status = strmap_get(package_status, key);
  2220. if (!status) {
  2221. status = tor_calloc(n_votes, sizeof(const char *));
  2222. strmap_set(package_status, key, status);
  2223. }
  2224. status[v_sl_idx] = line; /* overwrite old value */
  2225. tor_free(key);
  2226. } SMARTLIST_FOREACH_END(line);
  2227. } SMARTLIST_FOREACH_END(v);
  2228. smartlist_t *entries = smartlist_new(); /* temporary */
  2229. smartlist_t *result_list = smartlist_new(); /* output */
  2230. STRMAP_FOREACH(package_status, key, const char **, values) {
  2231. int i, count=-1;
  2232. for (i = 0; i < n_votes; ++i) {
  2233. if (values[i])
  2234. smartlist_add(entries, (void*) values[i]);
  2235. }
  2236. smartlist_sort_strings(entries);
  2237. int n_voting_for_entry = smartlist_len(entries);
  2238. const char *most_frequent =
  2239. smartlist_get_most_frequent_string_(entries, &count);
  2240. if (n_voting_for_entry >= 3 && count > n_voting_for_entry / 2) {
  2241. smartlist_add_asprintf(result_list, "package %s\n", most_frequent);
  2242. }
  2243. smartlist_clear(entries);
  2244. } STRMAP_FOREACH_END;
  2245. smartlist_sort_strings(result_list);
  2246. char *result = smartlist_join_strings(result_list, "", 0, NULL);
  2247. SMARTLIST_FOREACH(result_list, char *, cp, tor_free(cp));
  2248. smartlist_free(result_list);
  2249. smartlist_free(entries);
  2250. strmap_free(package_status, tor_free_);
  2251. return result;
  2252. }
  2253. /** Given a consensus vote <b>target</b> and a set of detached signatures in
  2254. * <b>sigs</b> that correspond to the same consensus, check whether there are
  2255. * any new signatures in <b>src_voter_list</b> that should be added to
  2256. * <b>target</b>. (A signature should be added if we have no signature for that
  2257. * voter in <b>target</b> yet, or if we have no verifiable signature and the
  2258. * new signature is verifiable.) Return the number of signatures added or
  2259. * changed, or -1 if the document signed by <b>sigs</b> isn't the same
  2260. * document as <b>target</b>. */
  2261. STATIC int
  2262. networkstatus_add_detached_signatures(networkstatus_t *target,
  2263. ns_detached_signatures_t *sigs,
  2264. const char *source,
  2265. int severity,
  2266. const char **msg_out)
  2267. {
  2268. int r = 0;
  2269. const char *flavor;
  2270. smartlist_t *siglist;
  2271. tor_assert(sigs);
  2272. tor_assert(target);
  2273. tor_assert(target->type == NS_TYPE_CONSENSUS);
  2274. flavor = networkstatus_get_flavor_name(target->flavor);
  2275. /* Do the times seem right? */
  2276. if (target->valid_after != sigs->valid_after) {
  2277. *msg_out = "Valid-After times do not match "
  2278. "when adding detached signatures to consensus";
  2279. return -1;
  2280. }
  2281. if (target->fresh_until != sigs->fresh_until) {
  2282. *msg_out = "Fresh-until times do not match "
  2283. "when adding detached signatures to consensus";
  2284. return -1;
  2285. }
  2286. if (target->valid_until != sigs->valid_until) {
  2287. *msg_out = "Valid-until times do not match "
  2288. "when adding detached signatures to consensus";
  2289. return -1;
  2290. }
  2291. siglist = strmap_get(sigs->signatures, flavor);
  2292. if (!siglist) {
  2293. *msg_out = "No signatures for given consensus flavor";
  2294. return -1;
  2295. }
  2296. /** Make sure all the digests we know match, and at least one matches. */
  2297. {
  2298. common_digests_t *digests = strmap_get(sigs->digests, flavor);
  2299. int n_matches = 0;
  2300. int alg;
  2301. if (!digests) {
  2302. *msg_out = "No digests for given consensus flavor";
  2303. return -1;
  2304. }
  2305. for (alg = DIGEST_SHA1; alg < N_COMMON_DIGEST_ALGORITHMS; ++alg) {
  2306. if (!tor_mem_is_zero(digests->d[alg], DIGEST256_LEN)) {
  2307. if (fast_memeq(target->digests.d[alg], digests->d[alg],
  2308. DIGEST256_LEN)) {
  2309. ++n_matches;
  2310. } else {
  2311. *msg_out = "Mismatched digest.";
  2312. return -1;
  2313. }
  2314. }
  2315. }
  2316. if (!n_matches) {
  2317. *msg_out = "No recognized digests for given consensus flavor";
  2318. }
  2319. }
  2320. /* For each voter in src... */
  2321. SMARTLIST_FOREACH_BEGIN(siglist, document_signature_t *, sig) {
  2322. char voter_identity[HEX_DIGEST_LEN+1];
  2323. networkstatus_voter_info_t *target_voter =
  2324. networkstatus_get_voter_by_id(target, sig->identity_digest);
  2325. authority_cert_t *cert = NULL;
  2326. const char *algorithm;
  2327. document_signature_t *old_sig = NULL;
  2328. algorithm = crypto_digest_algorithm_get_name(sig->alg);
  2329. base16_encode(voter_identity, sizeof(voter_identity),
  2330. sig->identity_digest, DIGEST_LEN);
  2331. log_info(LD_DIR, "Looking at signature from %s using %s", voter_identity,
  2332. algorithm);
  2333. /* If the target doesn't know about this voter, then forget it. */
  2334. if (!target_voter) {
  2335. log_info(LD_DIR, "We do not know any voter with ID %s", voter_identity);
  2336. continue;
  2337. }
  2338. old_sig = networkstatus_get_voter_sig_by_alg(target_voter, sig->alg);
  2339. /* If the target already has a good signature from this voter, then skip
  2340. * this one. */
  2341. if (old_sig && old_sig->good_signature) {
  2342. log_info(LD_DIR, "We already have a good signature from %s using %s",
  2343. voter_identity, algorithm);
  2344. continue;
  2345. }
  2346. /* Try checking the signature if we haven't already. */
  2347. if (!sig->good_signature && !sig->bad_signature) {
  2348. cert = authority_cert_get_by_digests(sig->identity_digest,
  2349. sig->signing_key_digest);
  2350. if (cert) {
  2351. /* Not checking the return value here, since we are going to look
  2352. * at the status of sig->good_signature in a moment. */
  2353. (void) networkstatus_check_document_signature(target, sig, cert);
  2354. }
  2355. }
  2356. /* If this signature is good, or we don't have any signature yet,
  2357. * then maybe add it. */
  2358. if (sig->good_signature || !old_sig || old_sig->bad_signature) {
  2359. log_info(LD_DIR, "Adding signature from %s with %s", voter_identity,
  2360. algorithm);
  2361. tor_log(severity, LD_DIR, "Added a signature for %s from %s.",
  2362. target_voter->nickname, source);
  2363. ++r;
  2364. if (old_sig) {
  2365. smartlist_remove(target_voter->sigs, old_sig);
  2366. document_signature_free(old_sig);
  2367. }
  2368. smartlist_add(target_voter->sigs, document_signature_dup(sig));
  2369. } else {
  2370. log_info(LD_DIR, "Not adding signature from %s", voter_identity);
  2371. }
  2372. } SMARTLIST_FOREACH_END(sig);
  2373. return r;
  2374. }
  2375. /** Return a newly allocated string containing all the signatures on
  2376. * <b>consensus</b> by all voters. If <b>for_detached_signatures</b> is true,
  2377. * then the signatures will be put in a detached signatures document, so
  2378. * prefix any non-NS-flavored signatures with "additional-signature" rather
  2379. * than "directory-signature". */
  2380. static char *
  2381. networkstatus_format_signatures(networkstatus_t *consensus,
  2382. int for_detached_signatures)
  2383. {
  2384. smartlist_t *elements;
  2385. char buf[4096];
  2386. char *result = NULL;
  2387. int n_sigs = 0;
  2388. const consensus_flavor_t flavor = consensus->flavor;
  2389. const char *flavor_name = networkstatus_get_flavor_name(flavor);
  2390. const char *keyword;
  2391. if (for_detached_signatures && flavor != FLAV_NS)
  2392. keyword = "additional-signature";
  2393. else
  2394. keyword = "directory-signature";
  2395. elements = smartlist_new();
  2396. SMARTLIST_FOREACH_BEGIN(consensus->voters, networkstatus_voter_info_t *, v) {
  2397. SMARTLIST_FOREACH_BEGIN(v->sigs, document_signature_t *, sig) {
  2398. char sk[HEX_DIGEST_LEN+1];
  2399. char id[HEX_DIGEST_LEN+1];
  2400. if (!sig->signature || sig->bad_signature)
  2401. continue;
  2402. ++n_sigs;
  2403. base16_encode(sk, sizeof(sk), sig->signing_key_digest, DIGEST_LEN);
  2404. base16_encode(id, sizeof(id), sig->identity_digest, DIGEST_LEN);
  2405. if (flavor == FLAV_NS) {
  2406. smartlist_add_asprintf(elements,
  2407. "%s %s %s\n-----BEGIN SIGNATURE-----\n",
  2408. keyword, id, sk);
  2409. } else {
  2410. const char *digest_name =
  2411. crypto_digest_algorithm_get_name(sig->alg);
  2412. smartlist_add_asprintf(elements,
  2413. "%s%s%s %s %s %s\n-----BEGIN SIGNATURE-----\n",
  2414. keyword,
  2415. for_detached_signatures ? " " : "",
  2416. for_detached_signatures ? flavor_name : "",
  2417. digest_name, id, sk);
  2418. }
  2419. base64_encode(buf, sizeof(buf), sig->signature, sig->signature_len,
  2420. BASE64_ENCODE_MULTILINE);
  2421. strlcat(buf, "-----END SIGNATURE-----\n", sizeof(buf));
  2422. smartlist_add_strdup(elements, buf);
  2423. } SMARTLIST_FOREACH_END(sig);
  2424. } SMARTLIST_FOREACH_END(v);
  2425. result = smartlist_join_strings(elements, "", 0, NULL);
  2426. SMARTLIST_FOREACH(elements, char *, cp, tor_free(cp));
  2427. smartlist_free(elements);
  2428. if (!n_sigs)
  2429. tor_free(result);
  2430. return result;
  2431. }
  2432. /** Return a newly allocated string holding the detached-signatures document
  2433. * corresponding to the signatures on <b>consensuses</b>, which must contain
  2434. * exactly one FLAV_NS consensus, and no more than one consensus for each
  2435. * other flavor. */
  2436. STATIC char *
  2437. networkstatus_get_detached_signatures(smartlist_t *consensuses)
  2438. {
  2439. smartlist_t *elements;
  2440. char *result = NULL, *sigs = NULL;
  2441. networkstatus_t *consensus_ns = NULL;
  2442. tor_assert(consensuses);
  2443. SMARTLIST_FOREACH(consensuses, networkstatus_t *, ns, {
  2444. tor_assert(ns);
  2445. tor_assert(ns->type == NS_TYPE_CONSENSUS);
  2446. if (ns && ns->flavor == FLAV_NS)
  2447. consensus_ns = ns;
  2448. });
  2449. if (!consensus_ns) {
  2450. log_warn(LD_BUG, "No NS consensus given.");
  2451. return NULL;
  2452. }
  2453. elements = smartlist_new();
  2454. {
  2455. char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
  2456. vu_buf[ISO_TIME_LEN+1];
  2457. char d[HEX_DIGEST_LEN+1];
  2458. base16_encode(d, sizeof(d),
  2459. consensus_ns->digests.d[DIGEST_SHA1], DIGEST_LEN);
  2460. format_iso_time(va_buf, consensus_ns->valid_after);
  2461. format_iso_time(fu_buf, consensus_ns->fresh_until);
  2462. format_iso_time(vu_buf, consensus_ns->valid_until);
  2463. smartlist_add_asprintf(elements,
  2464. "consensus-digest %s\n"
  2465. "valid-after %s\n"
  2466. "fresh-until %s\n"
  2467. "valid-until %s\n", d, va_buf, fu_buf, vu_buf);
  2468. }
  2469. /* Get all the digests for the non-FLAV_NS consensuses */
  2470. SMARTLIST_FOREACH_BEGIN(consensuses, networkstatus_t *, ns) {
  2471. const char *flavor_name = networkstatus_get_flavor_name(ns->flavor);
  2472. int alg;
  2473. if (ns->flavor == FLAV_NS)
  2474. continue;
  2475. /* start with SHA256; we don't include SHA1 for anything but the basic
  2476. * consensus. */
  2477. for (alg = DIGEST_SHA256; alg < N_COMMON_DIGEST_ALGORITHMS; ++alg) {
  2478. char d[HEX_DIGEST256_LEN+1];
  2479. const char *alg_name =
  2480. crypto_digest_algorithm_get_name(alg);
  2481. if (tor_mem_is_zero(ns->digests.d[alg], DIGEST256_LEN))
  2482. continue;
  2483. base16_encode(d, sizeof(d), ns->digests.d[alg], DIGEST256_LEN);
  2484. smartlist_add_asprintf(elements, "additional-digest %s %s %s\n",
  2485. flavor_name, alg_name, d);
  2486. }
  2487. } SMARTLIST_FOREACH_END(ns);
  2488. /* Now get all the sigs for non-FLAV_NS consensuses */
  2489. SMARTLIST_FOREACH_BEGIN(consensuses, networkstatus_t *, ns) {
  2490. char *sigs_on_this_consensus;
  2491. if (ns->flavor == FLAV_NS)
  2492. continue;
  2493. sigs_on_this_consensus = networkstatus_format_signatures(ns, 1);
  2494. if (!sigs_on_this_consensus) {
  2495. log_warn(LD_DIR, "Couldn't format signatures");
  2496. goto err;
  2497. }
  2498. smartlist_add(elements, sigs_on_this_consensus);
  2499. } SMARTLIST_FOREACH_END(ns);
  2500. /* Now add the FLAV_NS consensus signatrures. */
  2501. sigs = networkstatus_format_signatures(consensus_ns, 1);
  2502. if (!sigs)
  2503. goto err;
  2504. smartlist_add(elements, sigs);
  2505. result = smartlist_join_strings(elements, "", 0, NULL);
  2506. err:
  2507. SMARTLIST_FOREACH(elements, char *, cp, tor_free(cp));
  2508. smartlist_free(elements);
  2509. return result;
  2510. }
  2511. /** Return a newly allocated string holding a detached-signatures document for
  2512. * all of the in-progress consensuses in the <b>n_flavors</b>-element array at
  2513. * <b>pending</b>. */
  2514. static char *
  2515. get_detached_signatures_from_pending_consensuses(pending_consensus_t *pending,
  2516. int n_flavors)
  2517. {
  2518. int flav;
  2519. char *signatures;
  2520. smartlist_t *c = smartlist_new();
  2521. for (flav = 0; flav < n_flavors; ++flav) {
  2522. if (pending[flav].consensus)
  2523. smartlist_add(c, pending[flav].consensus);
  2524. }
  2525. signatures = networkstatus_get_detached_signatures(c);
  2526. smartlist_free(c);
  2527. return signatures;
  2528. }
  2529. /**
  2530. * Entry point: Take whatever voting actions are pending as of <b>now</b>.
  2531. *
  2532. * Return the time at which the next action should be taken.
  2533. */
  2534. time_t
  2535. dirvote_act(const or_options_t *options, time_t now)
  2536. {
  2537. if (!authdir_mode_v3(options))
  2538. return TIME_MAX;
  2539. tor_assert_nonfatal(voting_schedule.voting_starts);
  2540. /* If we haven't initialized this object through this codeflow, we need to
  2541. * recalculate the timings to match our vote. The reason to do that is if we
  2542. * have a voting schedule initialized 1 minute ago, the voting timings might
  2543. * not be aligned to what we should expect with "now". This is especially
  2544. * true for TestingTorNetwork using smaller timings. */
  2545. if (voting_schedule.created_on_demand) {
  2546. char *keys = list_v3_auth_ids();
  2547. authority_cert_t *c = get_my_v3_authority_cert();
  2548. log_notice(LD_DIR, "Scheduling voting. Known authority IDs are %s. "
  2549. "Mine is %s.",
  2550. keys, hex_str(c->cache_info.identity_digest, DIGEST_LEN));
  2551. tor_free(keys);
  2552. voting_schedule_recalculate_timing(options, now);
  2553. }
  2554. #define IF_TIME_FOR_NEXT_ACTION(when_field, done_field) \
  2555. if (! voting_schedule.done_field) { \
  2556. if (voting_schedule.when_field > now) { \
  2557. return voting_schedule.when_field; \
  2558. } else {
  2559. #define ENDIF \
  2560. } \
  2561. }
  2562. IF_TIME_FOR_NEXT_ACTION(voting_starts, have_voted) {
  2563. log_notice(LD_DIR, "Time to vote.");
  2564. dirvote_perform_vote();
  2565. voting_schedule.have_voted = 1;
  2566. } ENDIF
  2567. IF_TIME_FOR_NEXT_ACTION(fetch_missing_votes, have_fetched_missing_votes) {
  2568. log_notice(LD_DIR, "Time to fetch any votes that we're missing.");
  2569. dirvote_fetch_missing_votes();
  2570. voting_schedule.have_fetched_missing_votes = 1;
  2571. } ENDIF
  2572. IF_TIME_FOR_NEXT_ACTION(voting_ends, have_built_consensus) {
  2573. log_notice(LD_DIR, "Time to compute a consensus.");
  2574. dirvote_compute_consensuses();
  2575. /* XXXX We will want to try again later if we haven't got enough
  2576. * votes yet. Implement this if it turns out to ever happen. */
  2577. voting_schedule.have_built_consensus = 1;
  2578. } ENDIF
  2579. IF_TIME_FOR_NEXT_ACTION(fetch_missing_signatures,
  2580. have_fetched_missing_signatures) {
  2581. log_notice(LD_DIR, "Time to fetch any signatures that we're missing.");
  2582. dirvote_fetch_missing_signatures();
  2583. voting_schedule.have_fetched_missing_signatures = 1;
  2584. } ENDIF
  2585. IF_TIME_FOR_NEXT_ACTION(interval_starts,
  2586. have_published_consensus) {
  2587. log_notice(LD_DIR, "Time to publish the consensus and discard old votes");
  2588. dirvote_publish_consensus();
  2589. dirvote_clear_votes(0);
  2590. voting_schedule.have_published_consensus = 1;
  2591. /* Update our shared random state with the consensus just published. */
  2592. sr_act_post_consensus(
  2593. networkstatus_get_latest_consensus_by_flavor(FLAV_NS));
  2594. /* XXXX We will want to try again later if we haven't got enough
  2595. * signatures yet. Implement this if it turns out to ever happen. */
  2596. voting_schedule_recalculate_timing(options, now);
  2597. return voting_schedule.voting_starts;
  2598. } ENDIF
  2599. tor_assert_nonfatal_unreached();
  2600. return now + 1;
  2601. #undef ENDIF
  2602. #undef IF_TIME_FOR_NEXT_ACTION
  2603. }
  2604. /** A vote networkstatus_t and its unparsed body: held around so we can
  2605. * use it to generate a consensus (at voting_ends) and so we can serve it to
  2606. * other authorities that might want it. */
  2607. typedef struct pending_vote_t {
  2608. cached_dir_t *vote_body;
  2609. networkstatus_t *vote;
  2610. } pending_vote_t;
  2611. /** List of pending_vote_t for the current vote. Before we've used them to
  2612. * build a consensus, the votes go here. */
  2613. static smartlist_t *pending_vote_list = NULL;
  2614. /** List of pending_vote_t for the previous vote. After we've used them to
  2615. * build a consensus, the votes go here for the next period. */
  2616. static smartlist_t *previous_vote_list = NULL;
  2617. /* DOCDOC pending_consensuses */
  2618. static pending_consensus_t pending_consensuses[N_CONSENSUS_FLAVORS];
  2619. /** The detached signatures for the consensus that we're currently
  2620. * building. */
  2621. static char *pending_consensus_signatures = NULL;
  2622. /** List of ns_detached_signatures_t: hold signatures that get posted to us
  2623. * before we have generated the consensus on our own. */
  2624. static smartlist_t *pending_consensus_signature_list = NULL;
  2625. /** Generate a networkstatus vote and post it to all the v3 authorities.
  2626. * (V3 Authority only) */
  2627. static int
  2628. dirvote_perform_vote(void)
  2629. {
  2630. crypto_pk_t *key = get_my_v3_authority_signing_key();
  2631. authority_cert_t *cert = get_my_v3_authority_cert();
  2632. networkstatus_t *ns;
  2633. char *contents;
  2634. pending_vote_t *pending_vote;
  2635. time_t now = time(NULL);
  2636. int status;
  2637. const char *msg = "";
  2638. if (!cert || !key) {
  2639. log_warn(LD_NET, "Didn't find key/certificate to generate v3 vote");
  2640. return -1;
  2641. } else if (cert->expires < now) {
  2642. log_warn(LD_NET, "Can't generate v3 vote with expired certificate");
  2643. return -1;
  2644. }
  2645. if (!(ns = dirserv_generate_networkstatus_vote_obj(key, cert)))
  2646. return -1;
  2647. contents = format_networkstatus_vote(key, ns);
  2648. networkstatus_vote_free(ns);
  2649. if (!contents)
  2650. return -1;
  2651. pending_vote = dirvote_add_vote(contents, &msg, &status);
  2652. tor_free(contents);
  2653. if (!pending_vote) {
  2654. log_warn(LD_DIR, "Couldn't store my own vote! (I told myself, '%s'.)",
  2655. msg);
  2656. return -1;
  2657. }
  2658. directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_VOTE,
  2659. ROUTER_PURPOSE_GENERAL,
  2660. V3_DIRINFO,
  2661. pending_vote->vote_body->dir,
  2662. pending_vote->vote_body->dir_len, 0);
  2663. log_notice(LD_DIR, "Vote posted.");
  2664. return 0;
  2665. }
  2666. /** Send an HTTP request to every other v3 authority, for the votes of every
  2667. * authority for which we haven't received a vote yet in this period. (V3
  2668. * authority only) */
  2669. static void
  2670. dirvote_fetch_missing_votes(void)
  2671. {
  2672. smartlist_t *missing_fps = smartlist_new();
  2673. char *resource;
  2674. SMARTLIST_FOREACH_BEGIN(router_get_trusted_dir_servers(),
  2675. dir_server_t *, ds) {
  2676. if (!(ds->type & V3_DIRINFO))
  2677. continue;
  2678. if (!dirvote_get_vote(ds->v3_identity_digest,
  2679. DGV_BY_ID|DGV_INCLUDE_PENDING)) {
  2680. char *cp = tor_malloc(HEX_DIGEST_LEN+1);
  2681. base16_encode(cp, HEX_DIGEST_LEN+1, ds->v3_identity_digest,
  2682. DIGEST_LEN);
  2683. smartlist_add(missing_fps, cp);
  2684. }
  2685. } SMARTLIST_FOREACH_END(ds);
  2686. if (!smartlist_len(missing_fps)) {
  2687. smartlist_free(missing_fps);
  2688. return;
  2689. }
  2690. {
  2691. char *tmp = smartlist_join_strings(missing_fps, " ", 0, NULL);
  2692. log_notice(LOG_NOTICE, "We're missing votes from %d authorities (%s). "
  2693. "Asking every other authority for a copy.",
  2694. smartlist_len(missing_fps), tmp);
  2695. tor_free(tmp);
  2696. }
  2697. resource = smartlist_join_strings(missing_fps, "+", 0, NULL);
  2698. directory_get_from_all_authorities(DIR_PURPOSE_FETCH_STATUS_VOTE,
  2699. 0, resource);
  2700. tor_free(resource);
  2701. SMARTLIST_FOREACH(missing_fps, char *, cp, tor_free(cp));
  2702. smartlist_free(missing_fps);
  2703. }
  2704. /** Send a request to every other authority for its detached signatures,
  2705. * unless we have signatures from all other v3 authorities already. */
  2706. static void
  2707. dirvote_fetch_missing_signatures(void)
  2708. {
  2709. int need_any = 0;
  2710. int i;
  2711. for (i=0; i < N_CONSENSUS_FLAVORS; ++i) {
  2712. networkstatus_t *consensus = pending_consensuses[i].consensus;
  2713. if (!consensus ||
  2714. networkstatus_check_consensus_signature(consensus, -1) == 1) {
  2715. /* We have no consensus, or we have one that's signed by everybody. */
  2716. continue;
  2717. }
  2718. need_any = 1;
  2719. }
  2720. if (!need_any)
  2721. return;
  2722. directory_get_from_all_authorities(DIR_PURPOSE_FETCH_DETACHED_SIGNATURES,
  2723. 0, NULL);
  2724. }
  2725. /** Release all storage held by pending consensuses (those waiting for
  2726. * signatures). */
  2727. static void
  2728. dirvote_clear_pending_consensuses(void)
  2729. {
  2730. int i;
  2731. for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
  2732. pending_consensus_t *pc = &pending_consensuses[i];
  2733. tor_free(pc->body);
  2734. networkstatus_vote_free(pc->consensus);
  2735. pc->consensus = NULL;
  2736. }
  2737. }
  2738. /** Drop all currently pending votes, consensus, and detached signatures. */
  2739. static void
  2740. dirvote_clear_votes(int all_votes)
  2741. {
  2742. if (!previous_vote_list)
  2743. previous_vote_list = smartlist_new();
  2744. if (!pending_vote_list)
  2745. pending_vote_list = smartlist_new();
  2746. /* All "previous" votes are now junk. */
  2747. SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, v, {
  2748. cached_dir_decref(v->vote_body);
  2749. v->vote_body = NULL;
  2750. networkstatus_vote_free(v->vote);
  2751. tor_free(v);
  2752. });
  2753. smartlist_clear(previous_vote_list);
  2754. if (all_votes) {
  2755. /* If we're dumping all the votes, we delete the pending ones. */
  2756. SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, {
  2757. cached_dir_decref(v->vote_body);
  2758. v->vote_body = NULL;
  2759. networkstatus_vote_free(v->vote);
  2760. tor_free(v);
  2761. });
  2762. } else {
  2763. /* Otherwise, we move them into "previous". */
  2764. smartlist_add_all(previous_vote_list, pending_vote_list);
  2765. }
  2766. smartlist_clear(pending_vote_list);
  2767. if (pending_consensus_signature_list) {
  2768. SMARTLIST_FOREACH(pending_consensus_signature_list, char *, cp,
  2769. tor_free(cp));
  2770. smartlist_clear(pending_consensus_signature_list);
  2771. }
  2772. tor_free(pending_consensus_signatures);
  2773. dirvote_clear_pending_consensuses();
  2774. }
  2775. /** Return a newly allocated string containing the hex-encoded v3 authority
  2776. identity digest of every recognized v3 authority. */
  2777. static char *
  2778. list_v3_auth_ids(void)
  2779. {
  2780. smartlist_t *known_v3_keys = smartlist_new();
  2781. char *keys;
  2782. SMARTLIST_FOREACH(router_get_trusted_dir_servers(),
  2783. dir_server_t *, ds,
  2784. if ((ds->type & V3_DIRINFO) &&
  2785. !tor_digest_is_zero(ds->v3_identity_digest))
  2786. smartlist_add(known_v3_keys,
  2787. tor_strdup(hex_str(ds->v3_identity_digest, DIGEST_LEN))));
  2788. keys = smartlist_join_strings(known_v3_keys, ", ", 0, NULL);
  2789. SMARTLIST_FOREACH(known_v3_keys, char *, cp, tor_free(cp));
  2790. smartlist_free(known_v3_keys);
  2791. return keys;
  2792. }
  2793. /** Called when we have received a networkstatus vote in <b>vote_body</b>.
  2794. * Parse and validate it, and on success store it as a pending vote (which we
  2795. * then return). Return NULL on failure. Sets *<b>msg_out</b> and
  2796. * *<b>status_out</b> to an HTTP response and status code. (V3 authority
  2797. * only) */
  2798. pending_vote_t *
  2799. dirvote_add_vote(const char *vote_body, const char **msg_out, int *status_out)
  2800. {
  2801. networkstatus_t *vote;
  2802. networkstatus_voter_info_t *vi;
  2803. dir_server_t *ds;
  2804. pending_vote_t *pending_vote = NULL;
  2805. const char *end_of_vote = NULL;
  2806. int any_failed = 0;
  2807. tor_assert(vote_body);
  2808. tor_assert(msg_out);
  2809. tor_assert(status_out);
  2810. if (!pending_vote_list)
  2811. pending_vote_list = smartlist_new();
  2812. *status_out = 0;
  2813. *msg_out = NULL;
  2814. again:
  2815. vote = networkstatus_parse_vote_from_string(vote_body, &end_of_vote,
  2816. NS_TYPE_VOTE);
  2817. if (!end_of_vote)
  2818. end_of_vote = vote_body + strlen(vote_body);
  2819. if (!vote) {
  2820. log_warn(LD_DIR, "Couldn't parse vote: length was %d",
  2821. (int)strlen(vote_body));
  2822. *msg_out = "Unable to parse vote";
  2823. goto err;
  2824. }
  2825. tor_assert(smartlist_len(vote->voters) == 1);
  2826. vi = get_voter(vote);
  2827. {
  2828. int any_sig_good = 0;
  2829. SMARTLIST_FOREACH(vi->sigs, document_signature_t *, sig,
  2830. if (sig->good_signature)
  2831. any_sig_good = 1);
  2832. tor_assert(any_sig_good);
  2833. }
  2834. ds = trusteddirserver_get_by_v3_auth_digest(vi->identity_digest);
  2835. if (!ds) {
  2836. char *keys = list_v3_auth_ids();
  2837. log_warn(LD_DIR, "Got a vote from an authority (nickname %s, address %s) "
  2838. "with authority key ID %s. "
  2839. "This key ID is not recognized. Known v3 key IDs are: %s",
  2840. vi->nickname, vi->address,
  2841. hex_str(vi->identity_digest, DIGEST_LEN), keys);
  2842. tor_free(keys);
  2843. *msg_out = "Vote not from a recognized v3 authority";
  2844. goto err;
  2845. }
  2846. tor_assert(vote->cert);
  2847. if (!authority_cert_get_by_digests(vote->cert->cache_info.identity_digest,
  2848. vote->cert->signing_key_digest)) {
  2849. /* Hey, it's a new cert! */
  2850. trusted_dirs_load_certs_from_string(
  2851. vote->cert->cache_info.signed_descriptor_body,
  2852. TRUSTED_DIRS_CERTS_SRC_FROM_VOTE, 1 /*flush*/,
  2853. NULL);
  2854. if (!authority_cert_get_by_digests(vote->cert->cache_info.identity_digest,
  2855. vote->cert->signing_key_digest)) {
  2856. log_warn(LD_BUG, "We added a cert, but still couldn't find it.");
  2857. }
  2858. }
  2859. /* Is it for the right period? */
  2860. if (vote->valid_after != voting_schedule.interval_starts) {
  2861. char tbuf1[ISO_TIME_LEN+1], tbuf2[ISO_TIME_LEN+1];
  2862. format_iso_time(tbuf1, vote->valid_after);
  2863. format_iso_time(tbuf2, voting_schedule.interval_starts);
  2864. log_warn(LD_DIR, "Rejecting vote from %s with valid-after time of %s; "
  2865. "we were expecting %s", vi->address, tbuf1, tbuf2);
  2866. *msg_out = "Bad valid-after time";
  2867. goto err;
  2868. }
  2869. /* Fetch any new router descriptors we just learned about */
  2870. update_consensus_router_descriptor_downloads(time(NULL), 1, vote);
  2871. /* Now see whether we already have a vote from this authority. */
  2872. SMARTLIST_FOREACH_BEGIN(pending_vote_list, pending_vote_t *, v) {
  2873. if (fast_memeq(v->vote->cert->cache_info.identity_digest,
  2874. vote->cert->cache_info.identity_digest,
  2875. DIGEST_LEN)) {
  2876. networkstatus_voter_info_t *vi_old = get_voter(v->vote);
  2877. if (fast_memeq(vi_old->vote_digest, vi->vote_digest, DIGEST_LEN)) {
  2878. /* Ah, it's the same vote. Not a problem. */
  2879. log_info(LD_DIR, "Discarding a vote we already have (from %s).",
  2880. vi->address);
  2881. if (*status_out < 200)
  2882. *status_out = 200;
  2883. goto discard;
  2884. } else if (v->vote->published < vote->published) {
  2885. log_notice(LD_DIR, "Replacing an older pending vote from this "
  2886. "directory (%s)", vi->address);
  2887. cached_dir_decref(v->vote_body);
  2888. networkstatus_vote_free(v->vote);
  2889. v->vote_body = new_cached_dir(tor_strndup(vote_body,
  2890. end_of_vote-vote_body),
  2891. vote->published);
  2892. v->vote = vote;
  2893. if (end_of_vote &&
  2894. !strcmpstart(end_of_vote, "network-status-version"))
  2895. goto again;
  2896. if (*status_out < 200)
  2897. *status_out = 200;
  2898. if (!*msg_out)
  2899. *msg_out = "OK";
  2900. return v;
  2901. } else {
  2902. *msg_out = "Already have a newer pending vote";
  2903. goto err;
  2904. }
  2905. }
  2906. } SMARTLIST_FOREACH_END(v);
  2907. /* This a valid vote, update our shared random state. */
  2908. sr_handle_received_commits(vote->sr_info.commits,
  2909. vote->cert->identity_key);
  2910. pending_vote = tor_malloc_zero(sizeof(pending_vote_t));
  2911. pending_vote->vote_body = new_cached_dir(tor_strndup(vote_body,
  2912. end_of_vote-vote_body),
  2913. vote->published);
  2914. pending_vote->vote = vote;
  2915. smartlist_add(pending_vote_list, pending_vote);
  2916. if (!strcmpstart(end_of_vote, "network-status-version ")) {
  2917. vote_body = end_of_vote;
  2918. goto again;
  2919. }
  2920. goto done;
  2921. err:
  2922. any_failed = 1;
  2923. if (!*msg_out)
  2924. *msg_out = "Error adding vote";
  2925. if (*status_out < 400)
  2926. *status_out = 400;
  2927. discard:
  2928. networkstatus_vote_free(vote);
  2929. if (end_of_vote && !strcmpstart(end_of_vote, "network-status-version ")) {
  2930. vote_body = end_of_vote;
  2931. goto again;
  2932. }
  2933. done:
  2934. if (*status_out < 200)
  2935. *status_out = 200;
  2936. if (!*msg_out) {
  2937. if (!any_failed && !pending_vote) {
  2938. *msg_out = "Duplicate discarded";
  2939. } else {
  2940. *msg_out = "ok";
  2941. }
  2942. }
  2943. return any_failed ? NULL : pending_vote;
  2944. }
  2945. /* Write the votes in <b>pending_vote_list</b> to disk. */
  2946. static void
  2947. write_v3_votes_to_disk(const smartlist_t *pending_votes)
  2948. {
  2949. smartlist_t *votestrings = smartlist_new();
  2950. char *votefile = NULL;
  2951. SMARTLIST_FOREACH(pending_votes, pending_vote_t *, v,
  2952. {
  2953. sized_chunk_t *c = tor_malloc(sizeof(sized_chunk_t));
  2954. c->bytes = v->vote_body->dir;
  2955. c->len = v->vote_body->dir_len;
  2956. smartlist_add(votestrings, c); /* collect strings to write to disk */
  2957. });
  2958. votefile = get_datadir_fname("v3-status-votes");
  2959. write_chunks_to_file(votefile, votestrings, 0, 0);
  2960. log_debug(LD_DIR, "Wrote votes to disk (%s)!", votefile);
  2961. tor_free(votefile);
  2962. SMARTLIST_FOREACH(votestrings, sized_chunk_t *, c, tor_free(c));
  2963. smartlist_free(votestrings);
  2964. }
  2965. /** Try to compute a v3 networkstatus consensus from the currently pending
  2966. * votes. Return 0 on success, -1 on failure. Store the consensus in
  2967. * pending_consensus: it won't be ready to be published until we have
  2968. * everybody else's signatures collected too. (V3 Authority only) */
  2969. static int
  2970. dirvote_compute_consensuses(void)
  2971. {
  2972. /* Have we got enough votes to try? */
  2973. int n_votes, n_voters, n_vote_running = 0;
  2974. smartlist_t *votes = NULL;
  2975. char *consensus_body = NULL, *signatures = NULL;
  2976. networkstatus_t *consensus = NULL;
  2977. authority_cert_t *my_cert;
  2978. pending_consensus_t pending[N_CONSENSUS_FLAVORS];
  2979. int flav;
  2980. memset(pending, 0, sizeof(pending));
  2981. if (!pending_vote_list)
  2982. pending_vote_list = smartlist_new();
  2983. /* Write votes to disk */
  2984. write_v3_votes_to_disk(pending_vote_list);
  2985. /* Setup votes smartlist */
  2986. votes = smartlist_new();
  2987. SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v,
  2988. {
  2989. smartlist_add(votes, v->vote); /* collect votes to compute consensus */
  2990. });
  2991. /* See if consensus managed to achieve majority */
  2992. n_voters = get_n_authorities(V3_DIRINFO);
  2993. n_votes = smartlist_len(pending_vote_list);
  2994. if (n_votes <= n_voters/2) {
  2995. log_warn(LD_DIR, "We don't have enough votes to generate a consensus: "
  2996. "%d of %d", n_votes, n_voters/2+1);
  2997. goto err;
  2998. }
  2999. tor_assert(pending_vote_list);
  3000. SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, {
  3001. if (smartlist_contains_string(v->vote->known_flags, "Running"))
  3002. n_vote_running++;
  3003. });
  3004. if (!n_vote_running) {
  3005. /* See task 1066. */
  3006. log_warn(LD_DIR, "Nobody has voted on the Running flag. Generating "
  3007. "and publishing a consensus without Running nodes "
  3008. "would make many clients stop working. Not "
  3009. "generating a consensus!");
  3010. goto err;
  3011. }
  3012. if (!(my_cert = get_my_v3_authority_cert())) {
  3013. log_warn(LD_DIR, "Can't generate consensus without a certificate.");
  3014. goto err;
  3015. }
  3016. {
  3017. char legacy_dbuf[DIGEST_LEN];
  3018. crypto_pk_t *legacy_sign=NULL;
  3019. char *legacy_id_digest = NULL;
  3020. int n_generated = 0;
  3021. if (get_options()->V3AuthUseLegacyKey) {
  3022. authority_cert_t *cert = get_my_v3_legacy_cert();
  3023. legacy_sign = get_my_v3_legacy_signing_key();
  3024. if (cert) {
  3025. if (crypto_pk_get_digest(cert->identity_key, legacy_dbuf)) {
  3026. log_warn(LD_BUG,
  3027. "Unable to compute digest of legacy v3 identity key");
  3028. } else {
  3029. legacy_id_digest = legacy_dbuf;
  3030. }
  3031. }
  3032. }
  3033. for (flav = 0; flav < N_CONSENSUS_FLAVORS; ++flav) {
  3034. const char *flavor_name = networkstatus_get_flavor_name(flav);
  3035. consensus_body = networkstatus_compute_consensus(
  3036. votes, n_voters,
  3037. my_cert->identity_key,
  3038. get_my_v3_authority_signing_key(), legacy_id_digest, legacy_sign,
  3039. flav);
  3040. if (!consensus_body) {
  3041. log_warn(LD_DIR, "Couldn't generate a %s consensus at all!",
  3042. flavor_name);
  3043. continue;
  3044. }
  3045. consensus = networkstatus_parse_vote_from_string(consensus_body, NULL,
  3046. NS_TYPE_CONSENSUS);
  3047. if (!consensus) {
  3048. log_warn(LD_DIR, "Couldn't parse %s consensus we generated!",
  3049. flavor_name);
  3050. tor_free(consensus_body);
  3051. continue;
  3052. }
  3053. /* 'Check' our own signature, to mark it valid. */
  3054. networkstatus_check_consensus_signature(consensus, -1);
  3055. pending[flav].body = consensus_body;
  3056. pending[flav].consensus = consensus;
  3057. n_generated++;
  3058. consensus_body = NULL;
  3059. consensus = NULL;
  3060. }
  3061. if (!n_generated) {
  3062. log_warn(LD_DIR, "Couldn't generate any consensus flavors at all.");
  3063. goto err;
  3064. }
  3065. }
  3066. signatures = get_detached_signatures_from_pending_consensuses(
  3067. pending, N_CONSENSUS_FLAVORS);
  3068. if (!signatures) {
  3069. log_warn(LD_DIR, "Couldn't extract signatures.");
  3070. goto err;
  3071. }
  3072. dirvote_clear_pending_consensuses();
  3073. memcpy(pending_consensuses, pending, sizeof(pending));
  3074. tor_free(pending_consensus_signatures);
  3075. pending_consensus_signatures = signatures;
  3076. if (pending_consensus_signature_list) {
  3077. int n_sigs = 0;
  3078. /* we may have gotten signatures for this consensus before we built
  3079. * it ourself. Add them now. */
  3080. SMARTLIST_FOREACH_BEGIN(pending_consensus_signature_list, char *, sig) {
  3081. const char *msg = NULL;
  3082. int r = dirvote_add_signatures_to_all_pending_consensuses(sig,
  3083. "pending", &msg);
  3084. if (r >= 0)
  3085. n_sigs += r;
  3086. else
  3087. log_warn(LD_DIR,
  3088. "Could not add queued signature to new consensus: %s",
  3089. msg);
  3090. tor_free(sig);
  3091. } SMARTLIST_FOREACH_END(sig);
  3092. if (n_sigs)
  3093. log_notice(LD_DIR, "Added %d pending signatures while building "
  3094. "consensus.", n_sigs);
  3095. smartlist_clear(pending_consensus_signature_list);
  3096. }
  3097. log_notice(LD_DIR, "Consensus computed; uploading signature(s)");
  3098. directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_SIGNATURES,
  3099. ROUTER_PURPOSE_GENERAL,
  3100. V3_DIRINFO,
  3101. pending_consensus_signatures,
  3102. strlen(pending_consensus_signatures), 0);
  3103. log_notice(LD_DIR, "Signature(s) posted.");
  3104. smartlist_free(votes);
  3105. return 0;
  3106. err:
  3107. smartlist_free(votes);
  3108. tor_free(consensus_body);
  3109. tor_free(signatures);
  3110. networkstatus_vote_free(consensus);
  3111. return -1;
  3112. }
  3113. /** Helper: we just got the <b>detached_signatures_body</b> sent to us as
  3114. * signatures on the currently pending consensus. Add them to <b>pc</b>
  3115. * as appropriate. Return the number of signatures added. (?) */
  3116. static int
  3117. dirvote_add_signatures_to_pending_consensus(
  3118. pending_consensus_t *pc,
  3119. ns_detached_signatures_t *sigs,
  3120. const char *source,
  3121. int severity,
  3122. const char **msg_out)
  3123. {
  3124. const char *flavor_name;
  3125. int r = -1;
  3126. /* Only call if we have a pending consensus right now. */
  3127. tor_assert(pc->consensus);
  3128. tor_assert(pc->body);
  3129. tor_assert(pending_consensus_signatures);
  3130. flavor_name = networkstatus_get_flavor_name(pc->consensus->flavor);
  3131. *msg_out = NULL;
  3132. {
  3133. smartlist_t *sig_list = strmap_get(sigs->signatures, flavor_name);
  3134. log_info(LD_DIR, "Have %d signatures for adding to %s consensus.",
  3135. sig_list ? smartlist_len(sig_list) : 0, flavor_name);
  3136. }
  3137. r = networkstatus_add_detached_signatures(pc->consensus, sigs,
  3138. source, severity, msg_out);
  3139. if (r >= 0) {
  3140. log_info(LD_DIR,"Added %d signatures to consensus.", r);
  3141. } else {
  3142. log_fn(LOG_PROTOCOL_WARN, LD_DIR,
  3143. "Unable to add signatures to consensus: %s",
  3144. *msg_out ? *msg_out : "(unknown)");
  3145. }
  3146. if (r >= 1) {
  3147. char *new_signatures =
  3148. networkstatus_format_signatures(pc->consensus, 0);
  3149. char *dst, *dst_end;
  3150. size_t new_consensus_len;
  3151. if (!new_signatures) {
  3152. *msg_out = "No signatures to add";
  3153. goto err;
  3154. }
  3155. new_consensus_len =
  3156. strlen(pc->body) + strlen(new_signatures) + 1;
  3157. pc->body = tor_realloc(pc->body, new_consensus_len);
  3158. dst_end = pc->body + new_consensus_len;
  3159. dst = strstr(pc->body, "directory-signature ");
  3160. tor_assert(dst);
  3161. strlcpy(dst, new_signatures, dst_end-dst);
  3162. /* We remove this block once it has failed to crash for a while. But
  3163. * unless it shows up in profiles, we're probably better leaving it in,
  3164. * just in case we break detached signature processing at some point. */
  3165. {
  3166. networkstatus_t *v = networkstatus_parse_vote_from_string(
  3167. pc->body, NULL,
  3168. NS_TYPE_CONSENSUS);
  3169. tor_assert(v);
  3170. networkstatus_vote_free(v);
  3171. }
  3172. *msg_out = "Signatures added";
  3173. tor_free(new_signatures);
  3174. } else if (r == 0) {
  3175. *msg_out = "Signatures ignored";
  3176. } else {
  3177. goto err;
  3178. }
  3179. goto done;
  3180. err:
  3181. if (!*msg_out)
  3182. *msg_out = "Unrecognized error while adding detached signatures.";
  3183. done:
  3184. return r;
  3185. }
  3186. static int
  3187. dirvote_add_signatures_to_all_pending_consensuses(
  3188. const char *detached_signatures_body,
  3189. const char *source,
  3190. const char **msg_out)
  3191. {
  3192. int r=0, i, n_added = 0, errors = 0;
  3193. ns_detached_signatures_t *sigs;
  3194. tor_assert(detached_signatures_body);
  3195. tor_assert(msg_out);
  3196. tor_assert(pending_consensus_signatures);
  3197. if (!(sigs = networkstatus_parse_detached_signatures(
  3198. detached_signatures_body, NULL))) {
  3199. *msg_out = "Couldn't parse detached signatures.";
  3200. goto err;
  3201. }
  3202. for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
  3203. int res;
  3204. int severity = i == FLAV_NS ? LOG_NOTICE : LOG_INFO;
  3205. pending_consensus_t *pc = &pending_consensuses[i];
  3206. if (!pc->consensus)
  3207. continue;
  3208. res = dirvote_add_signatures_to_pending_consensus(pc, sigs, source,
  3209. severity, msg_out);
  3210. if (res < 0)
  3211. errors++;
  3212. else
  3213. n_added += res;
  3214. }
  3215. if (errors && !n_added) {
  3216. r = -1;
  3217. goto err;
  3218. }
  3219. if (n_added && pending_consensuses[FLAV_NS].consensus) {
  3220. char *new_detached =
  3221. get_detached_signatures_from_pending_consensuses(
  3222. pending_consensuses, N_CONSENSUS_FLAVORS);
  3223. if (new_detached) {
  3224. tor_free(pending_consensus_signatures);
  3225. pending_consensus_signatures = new_detached;
  3226. }
  3227. }
  3228. r = n_added;
  3229. goto done;
  3230. err:
  3231. if (!*msg_out)
  3232. *msg_out = "Unrecognized error while adding detached signatures.";
  3233. done:
  3234. ns_detached_signatures_free(sigs);
  3235. /* XXXX NM Check how return is used. We can now have an error *and*
  3236. signatures added. */
  3237. return r;
  3238. }
  3239. /** Helper: we just got the <b>detached_signatures_body</b> sent to us as
  3240. * signatures on the currently pending consensus. Add them to the pending
  3241. * consensus (if we have one); otherwise queue them until we have a
  3242. * consensus. Return negative on failure, nonnegative on success. */
  3243. int
  3244. dirvote_add_signatures(const char *detached_signatures_body,
  3245. const char *source,
  3246. const char **msg)
  3247. {
  3248. if (pending_consensuses[FLAV_NS].consensus) {
  3249. log_notice(LD_DIR, "Got a signature from %s. "
  3250. "Adding it to the pending consensus.", source);
  3251. return dirvote_add_signatures_to_all_pending_consensuses(
  3252. detached_signatures_body, source, msg);
  3253. } else {
  3254. log_notice(LD_DIR, "Got a signature from %s. "
  3255. "Queuing it for the next consensus.", source);
  3256. if (!pending_consensus_signature_list)
  3257. pending_consensus_signature_list = smartlist_new();
  3258. smartlist_add_strdup(pending_consensus_signature_list,
  3259. detached_signatures_body);
  3260. *msg = "Signature queued";
  3261. return 0;
  3262. }
  3263. }
  3264. /** Replace the consensus that we're currently serving with the one that we've
  3265. * been building. (V3 Authority only) */
  3266. static int
  3267. dirvote_publish_consensus(void)
  3268. {
  3269. int i;
  3270. /* Now remember all the other consensuses as if we were a directory cache. */
  3271. for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
  3272. pending_consensus_t *pending = &pending_consensuses[i];
  3273. const char *name;
  3274. name = networkstatus_get_flavor_name(i);
  3275. tor_assert(name);
  3276. if (!pending->consensus ||
  3277. networkstatus_check_consensus_signature(pending->consensus, 1)<0) {
  3278. log_warn(LD_DIR, "Not enough info to publish pending %s consensus",name);
  3279. continue;
  3280. }
  3281. if (networkstatus_set_current_consensus(pending->body, name, 0, NULL))
  3282. log_warn(LD_DIR, "Error publishing %s consensus", name);
  3283. else
  3284. log_notice(LD_DIR, "Published %s consensus", name);
  3285. }
  3286. return 0;
  3287. }
  3288. /** Release all static storage held in dirvote.c */
  3289. void
  3290. dirvote_free_all(void)
  3291. {
  3292. dirvote_clear_votes(1);
  3293. /* now empty as a result of dirvote_clear_votes(). */
  3294. smartlist_free(pending_vote_list);
  3295. pending_vote_list = NULL;
  3296. smartlist_free(previous_vote_list);
  3297. previous_vote_list = NULL;
  3298. dirvote_clear_pending_consensuses();
  3299. tor_free(pending_consensus_signatures);
  3300. if (pending_consensus_signature_list) {
  3301. /* now empty as a result of dirvote_clear_votes(). */
  3302. smartlist_free(pending_consensus_signature_list);
  3303. pending_consensus_signature_list = NULL;
  3304. }
  3305. }
  3306. /* ====
  3307. * Access to pending items.
  3308. * ==== */
  3309. /** Return the body of the consensus that we're currently trying to build. */
  3310. MOCK_IMPL(const char *,
  3311. dirvote_get_pending_consensus, (consensus_flavor_t flav))
  3312. {
  3313. tor_assert(((int)flav) >= 0 && (int)flav < N_CONSENSUS_FLAVORS);
  3314. return pending_consensuses[flav].body;
  3315. }
  3316. /** Return the signatures that we know for the consensus that we're currently
  3317. * trying to build. */
  3318. MOCK_IMPL(const char *,
  3319. dirvote_get_pending_detached_signatures, (void))
  3320. {
  3321. return pending_consensus_signatures;
  3322. }
  3323. /** Return a given vote specified by <b>fp</b>. If <b>by_id</b>, return the
  3324. * vote for the authority with the v3 authority identity key digest <b>fp</b>;
  3325. * if <b>by_id</b> is false, return the vote whose digest is <b>fp</b>. If
  3326. * <b>fp</b> is NULL, return our own vote. If <b>include_previous</b> is
  3327. * false, do not consider any votes for a consensus that's already been built.
  3328. * If <b>include_pending</b> is false, do not consider any votes for the
  3329. * consensus that's in progress. May return NULL if we have no vote for the
  3330. * authority in question. */
  3331. const cached_dir_t *
  3332. dirvote_get_vote(const char *fp, int flags)
  3333. {
  3334. int by_id = flags & DGV_BY_ID;
  3335. const int include_pending = flags & DGV_INCLUDE_PENDING;
  3336. const int include_previous = flags & DGV_INCLUDE_PREVIOUS;
  3337. if (!pending_vote_list && !previous_vote_list)
  3338. return NULL;
  3339. if (fp == NULL) {
  3340. authority_cert_t *c = get_my_v3_authority_cert();
  3341. if (c) {
  3342. fp = c->cache_info.identity_digest;
  3343. by_id = 1;
  3344. } else
  3345. return NULL;
  3346. }
  3347. if (by_id) {
  3348. if (pending_vote_list && include_pending) {
  3349. SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, pv,
  3350. if (fast_memeq(get_voter(pv->vote)->identity_digest, fp, DIGEST_LEN))
  3351. return pv->vote_body);
  3352. }
  3353. if (previous_vote_list && include_previous) {
  3354. SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, pv,
  3355. if (fast_memeq(get_voter(pv->vote)->identity_digest, fp, DIGEST_LEN))
  3356. return pv->vote_body);
  3357. }
  3358. } else {
  3359. if (pending_vote_list && include_pending) {
  3360. SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, pv,
  3361. if (fast_memeq(pv->vote->digests.d[DIGEST_SHA1], fp, DIGEST_LEN))
  3362. return pv->vote_body);
  3363. }
  3364. if (previous_vote_list && include_previous) {
  3365. SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, pv,
  3366. if (fast_memeq(pv->vote->digests.d[DIGEST_SHA1], fp, DIGEST_LEN))
  3367. return pv->vote_body);
  3368. }
  3369. }
  3370. return NULL;
  3371. }
  3372. /** Construct and return a new microdescriptor from a routerinfo <b>ri</b>
  3373. * according to <b>consensus_method</b>.
  3374. **/
  3375. STATIC microdesc_t *
  3376. dirvote_create_microdescriptor(const routerinfo_t *ri, int consensus_method)
  3377. {
  3378. microdesc_t *result = NULL;
  3379. char *key = NULL, *summary = NULL, *family = NULL;
  3380. size_t keylen;
  3381. smartlist_t *chunks = smartlist_new();
  3382. char *output = NULL;
  3383. crypto_pk_t *rsa_pubkey = router_get_rsa_onion_pkey(ri->onion_pkey,
  3384. ri->onion_pkey_len);
  3385. if (crypto_pk_write_public_key_to_string(rsa_pubkey, &key, &keylen)<0)
  3386. goto done;
  3387. summary = policy_summarize(ri->exit_policy, AF_INET);
  3388. if (ri->declared_family)
  3389. family = smartlist_join_strings(ri->declared_family, " ", 0, NULL);
  3390. smartlist_add_asprintf(chunks, "onion-key\n%s", key);
  3391. if (ri->onion_curve25519_pkey) {
  3392. char kbuf[128];
  3393. base64_encode(kbuf, sizeof(kbuf),
  3394. (const char*)ri->onion_curve25519_pkey->public_key,
  3395. CURVE25519_PUBKEY_LEN, BASE64_ENCODE_MULTILINE);
  3396. smartlist_add_asprintf(chunks, "ntor-onion-key %s", kbuf);
  3397. }
  3398. /* We originally put a lines in the micrdescriptors, but then we worked out
  3399. * that we needed them in the microdesc consensus. See #20916. */
  3400. if (consensus_method < MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC &&
  3401. !tor_addr_is_null(&ri->ipv6_addr) && ri->ipv6_orport)
  3402. smartlist_add_asprintf(chunks, "a %s\n",
  3403. fmt_addrport(&ri->ipv6_addr, ri->ipv6_orport));
  3404. if (family)
  3405. smartlist_add_asprintf(chunks, "family %s\n", family);
  3406. if (summary && strcmp(summary, "reject 1-65535"))
  3407. smartlist_add_asprintf(chunks, "p %s\n", summary);
  3408. if (ri->ipv6_exit_policy) {
  3409. /* XXXX+++ This doesn't match proposal 208, which says these should
  3410. * be taken unchanged from the routerinfo. That's bogosity, IMO:
  3411. * the proposal should have said to do this instead.*/
  3412. char *p6 = write_short_policy(ri->ipv6_exit_policy);
  3413. if (p6 && strcmp(p6, "reject 1-65535"))
  3414. smartlist_add_asprintf(chunks, "p6 %s\n", p6);
  3415. tor_free(p6);
  3416. }
  3417. {
  3418. char idbuf[ED25519_BASE64_LEN+1];
  3419. const char *keytype;
  3420. if (ri->cache_info.signing_key_cert &&
  3421. ri->cache_info.signing_key_cert->signing_key_included) {
  3422. keytype = "ed25519";
  3423. ed25519_public_to_base64(idbuf,
  3424. &ri->cache_info.signing_key_cert->signing_key);
  3425. } else {
  3426. keytype = "rsa1024";
  3427. digest_to_base64(idbuf, ri->cache_info.identity_digest);
  3428. }
  3429. smartlist_add_asprintf(chunks, "id %s %s\n", keytype, idbuf);
  3430. }
  3431. output = smartlist_join_strings(chunks, "", 0, NULL);
  3432. {
  3433. smartlist_t *lst = microdescs_parse_from_string(output,
  3434. output+strlen(output), 0,
  3435. SAVED_NOWHERE, NULL);
  3436. if (smartlist_len(lst) != 1) {
  3437. log_warn(LD_DIR, "We generated a microdescriptor we couldn't parse.");
  3438. SMARTLIST_FOREACH(lst, microdesc_t *, md, microdesc_free(md));
  3439. smartlist_free(lst);
  3440. goto done;
  3441. }
  3442. result = smartlist_get(lst, 0);
  3443. smartlist_free(lst);
  3444. }
  3445. done:
  3446. crypto_pk_free(rsa_pubkey);
  3447. tor_free(output);
  3448. tor_free(key);
  3449. tor_free(summary);
  3450. tor_free(family);
  3451. if (chunks) {
  3452. SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
  3453. smartlist_free(chunks);
  3454. }
  3455. return result;
  3456. }
  3457. /** Format the appropriate vote line to describe the microdescriptor <b>md</b>
  3458. * in a consensus vote document. Write it into the <b>out_len</b>-byte buffer
  3459. * in <b>out</b>. Return -1 on failure and the number of characters written
  3460. * on success. */
  3461. static ssize_t
  3462. dirvote_format_microdesc_vote_line(char *out_buf, size_t out_buf_len,
  3463. const microdesc_t *md,
  3464. int consensus_method_low,
  3465. int consensus_method_high)
  3466. {
  3467. ssize_t ret = -1;
  3468. char d64[BASE64_DIGEST256_LEN+1];
  3469. char *microdesc_consensus_methods =
  3470. make_consensus_method_list(consensus_method_low,
  3471. consensus_method_high,
  3472. ",");
  3473. tor_assert(microdesc_consensus_methods);
  3474. if (digest256_to_base64(d64, md->digest)<0)
  3475. goto out;
  3476. if (tor_snprintf(out_buf, out_buf_len, "m %s sha256=%s\n",
  3477. microdesc_consensus_methods, d64)<0)
  3478. goto out;
  3479. ret = strlen(out_buf);
  3480. out:
  3481. tor_free(microdesc_consensus_methods);
  3482. return ret;
  3483. }
  3484. /** Array of start and end of consensus methods used for supported
  3485. microdescriptor formats. */
  3486. static const struct consensus_method_range_t {
  3487. int low;
  3488. int high;
  3489. } microdesc_consensus_methods[] = {
  3490. {MIN_SUPPORTED_CONSENSUS_METHOD, MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC - 1},
  3491. {MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC, MAX_SUPPORTED_CONSENSUS_METHOD},
  3492. {-1, -1}
  3493. };
  3494. /** Helper type used when generating the microdescriptor lines in a directory
  3495. * vote. */
  3496. typedef struct microdesc_vote_line_t {
  3497. int low;
  3498. int high;
  3499. microdesc_t *md;
  3500. struct microdesc_vote_line_t *next;
  3501. } microdesc_vote_line_t;
  3502. /** Generate and return a linked list of all the lines that should appear to
  3503. * describe a router's microdescriptor versions in a directory vote.
  3504. * Add the generated microdescriptors to <b>microdescriptors_out</b>. */
  3505. vote_microdesc_hash_t *
  3506. dirvote_format_all_microdesc_vote_lines(const routerinfo_t *ri, time_t now,
  3507. smartlist_t *microdescriptors_out)
  3508. {
  3509. const struct consensus_method_range_t *cmr;
  3510. microdesc_vote_line_t *entries = NULL, *ep;
  3511. vote_microdesc_hash_t *result = NULL;
  3512. /* Generate the microdescriptors. */
  3513. for (cmr = microdesc_consensus_methods;
  3514. cmr->low != -1 && cmr->high != -1;
  3515. cmr++) {
  3516. microdesc_t *md = dirvote_create_microdescriptor(ri, cmr->low);
  3517. if (md) {
  3518. microdesc_vote_line_t *e =
  3519. tor_malloc_zero(sizeof(microdesc_vote_line_t));
  3520. e->md = md;
  3521. e->low = cmr->low;
  3522. e->high = cmr->high;
  3523. e->next = entries;
  3524. entries = e;
  3525. }
  3526. }
  3527. /* Compress adjacent identical ones */
  3528. for (ep = entries; ep; ep = ep->next) {
  3529. while (ep->next &&
  3530. fast_memeq(ep->md->digest, ep->next->md->digest, DIGEST256_LEN) &&
  3531. ep->low == ep->next->high + 1) {
  3532. microdesc_vote_line_t *next = ep->next;
  3533. ep->low = next->low;
  3534. microdesc_free(next->md);
  3535. ep->next = next->next;
  3536. tor_free(next);
  3537. }
  3538. }
  3539. /* Format them into vote_microdesc_hash_t, and add to microdescriptors_out.*/
  3540. while ((ep = entries)) {
  3541. char buf[128];
  3542. vote_microdesc_hash_t *h;
  3543. if (dirvote_format_microdesc_vote_line(buf, sizeof(buf), ep->md,
  3544. ep->low, ep->high) >= 0) {
  3545. h = tor_malloc_zero(sizeof(vote_microdesc_hash_t));
  3546. h->microdesc_hash_line = tor_strdup(buf);
  3547. h->next = result;
  3548. result = h;
  3549. ep->md->last_listed = now;
  3550. smartlist_add(microdescriptors_out, ep->md);
  3551. }
  3552. entries = ep->next;
  3553. tor_free(ep);
  3554. }
  3555. return result;
  3556. }
  3557. /** Parse and extract all SR commits from <b>tokens</b> and place them in
  3558. * <b>ns</b>. */
  3559. static void
  3560. extract_shared_random_commits(networkstatus_t *ns, const smartlist_t *tokens)
  3561. {
  3562. smartlist_t *chunks = NULL;
  3563. tor_assert(ns);
  3564. tor_assert(tokens);
  3565. /* Commits are only present in a vote. */
  3566. tor_assert(ns->type == NS_TYPE_VOTE);
  3567. ns->sr_info.commits = smartlist_new();
  3568. smartlist_t *commits = find_all_by_keyword(tokens, K_COMMIT);
  3569. /* It's normal that a vote might contain no commits even if it participates
  3570. * in the SR protocol. Don't treat it as an error. */
  3571. if (commits == NULL) {
  3572. goto end;
  3573. }
  3574. /* Parse the commit. We do NO validation of number of arguments or ordering
  3575. * for forward compatibility, it's the parse commit job to inform us if it's
  3576. * supported or not. */
  3577. chunks = smartlist_new();
  3578. SMARTLIST_FOREACH_BEGIN(commits, directory_token_t *, tok) {
  3579. /* Extract all arguments and put them in the chunks list. */
  3580. for (int i = 0; i < tok->n_args; i++) {
  3581. smartlist_add(chunks, tok->args[i]);
  3582. }
  3583. sr_commit_t *commit = sr_parse_commit(chunks);
  3584. smartlist_clear(chunks);
  3585. if (commit == NULL) {
  3586. /* Get voter identity so we can warn that this dirauth vote contains
  3587. * commit we can't parse. */
  3588. networkstatus_voter_info_t *voter = smartlist_get(ns->voters, 0);
  3589. tor_assert(voter);
  3590. log_warn(LD_DIR, "SR: Unable to parse commit %s from vote of voter %s.",
  3591. escaped(tok->object_body),
  3592. hex_str(voter->identity_digest,
  3593. sizeof(voter->identity_digest)));
  3594. /* Commitment couldn't be parsed. Continue onto the next commit because
  3595. * this one could be unsupported for instance. */
  3596. continue;
  3597. }
  3598. /* Add newly created commit object to the vote. */
  3599. smartlist_add(ns->sr_info.commits, commit);
  3600. } SMARTLIST_FOREACH_END(tok);
  3601. end:
  3602. smartlist_free(chunks);
  3603. smartlist_free(commits);
  3604. }
  3605. /* Using the given directory tokens in tokens, parse the shared random commits
  3606. * and put them in the given vote document ns.
  3607. *
  3608. * This also sets the SR participation flag if present in the vote. */
  3609. void
  3610. dirvote_parse_sr_commits(networkstatus_t *ns, const smartlist_t *tokens)
  3611. {
  3612. /* Does this authority participates in the SR protocol? */
  3613. directory_token_t *tok = find_opt_by_keyword(tokens, K_SR_FLAG);
  3614. if (tok) {
  3615. ns->sr_info.participate = 1;
  3616. /* Get the SR commitments and reveals from the vote. */
  3617. extract_shared_random_commits(ns, tokens);
  3618. }
  3619. }
  3620. /* For the given vote, free the shared random commits if any. */
  3621. void
  3622. dirvote_clear_commits(networkstatus_t *ns)
  3623. {
  3624. tor_assert(ns->type == NS_TYPE_VOTE);
  3625. if (ns->sr_info.commits) {
  3626. SMARTLIST_FOREACH(ns->sr_info.commits, sr_commit_t *, c,
  3627. sr_commit_free(c));
  3628. smartlist_free(ns->sr_info.commits);
  3629. }
  3630. }
  3631. /* The given url is the /tor/status-vote GET directory request. Populates the
  3632. * items list with strings that we can compress on the fly and dir_items with
  3633. * cached_dir_t objects that have a precompressed deflated version. */
  3634. void
  3635. dirvote_dirreq_get_status_vote(const char *url, smartlist_t *items,
  3636. smartlist_t *dir_items)
  3637. {
  3638. int current;
  3639. url += strlen("/tor/status-vote/");
  3640. current = !strcmpstart(url, "current/");
  3641. url = strchr(url, '/');
  3642. tor_assert(url);
  3643. ++url;
  3644. if (!strcmp(url, "consensus")) {
  3645. const char *item;
  3646. tor_assert(!current); /* we handle current consensus specially above,
  3647. * since it wants to be spooled. */
  3648. if ((item = dirvote_get_pending_consensus(FLAV_NS)))
  3649. smartlist_add(items, (char*)item);
  3650. } else if (!current && !strcmp(url, "consensus-signatures")) {
  3651. /* XXXX the spec says that we should implement
  3652. * current/consensus-signatures too. It doesn't seem to be needed,
  3653. * though. */
  3654. const char *item;
  3655. if ((item=dirvote_get_pending_detached_signatures()))
  3656. smartlist_add(items, (char*)item);
  3657. } else if (!strcmp(url, "authority")) {
  3658. const cached_dir_t *d;
  3659. int flags = DGV_BY_ID |
  3660. (current ? DGV_INCLUDE_PREVIOUS : DGV_INCLUDE_PENDING);
  3661. if ((d=dirvote_get_vote(NULL, flags)))
  3662. smartlist_add(dir_items, (cached_dir_t*)d);
  3663. } else {
  3664. const cached_dir_t *d;
  3665. smartlist_t *fps = smartlist_new();
  3666. int flags;
  3667. if (!strcmpstart(url, "d/")) {
  3668. url += 2;
  3669. flags = DGV_INCLUDE_PENDING | DGV_INCLUDE_PREVIOUS;
  3670. } else {
  3671. flags = DGV_BY_ID |
  3672. (current ? DGV_INCLUDE_PREVIOUS : DGV_INCLUDE_PENDING);
  3673. }
  3674. dir_split_resource_into_fingerprints(url, fps, NULL,
  3675. DSR_HEX|DSR_SORT_UNIQ);
  3676. SMARTLIST_FOREACH(fps, char *, fp, {
  3677. if ((d = dirvote_get_vote(fp, flags)))
  3678. smartlist_add(dir_items, (cached_dir_t*)d);
  3679. tor_free(fp);
  3680. });
  3681. smartlist_free(fps);
  3682. }
  3683. }
  3684. /** Get the best estimate of a router's bandwidth for dirauth purposes,
  3685. * preferring measured to advertised values if available. */
  3686. static uint32_t
  3687. dirserv_get_bandwidth_for_router_kb(const routerinfo_t *ri)
  3688. {
  3689. uint32_t bw_kb = 0;
  3690. /*
  3691. * Yeah, measured bandwidths in measured_bw_line_t are (implicitly
  3692. * signed) longs and the ones router_get_advertised_bandwidth() returns
  3693. * are uint32_t.
  3694. */
  3695. long mbw_kb = 0;
  3696. if (ri) {
  3697. /*
  3698. * * First try to see if we have a measured bandwidth; don't bother with
  3699. * as_of_out here, on the theory that a stale measured bandwidth is still
  3700. * better to trust than an advertised one.
  3701. */
  3702. if (dirserv_query_measured_bw_cache_kb(ri->cache_info.identity_digest,
  3703. &mbw_kb, NULL)) {
  3704. /* Got one! */
  3705. bw_kb = (uint32_t)mbw_kb;
  3706. } else {
  3707. /* If not, fall back to advertised */
  3708. bw_kb = router_get_advertised_bandwidth(ri) / 1000;
  3709. }
  3710. }
  3711. return bw_kb;
  3712. }
  3713. /** Helper for sorting: compares two routerinfos first by address, and then by
  3714. * descending order of "usefulness". (An authority is more useful than a
  3715. * non-authority; a running router is more useful than a non-running router;
  3716. * and a router with more bandwidth is more useful than one with less.)
  3717. **/
  3718. static int
  3719. compare_routerinfo_by_ip_and_bw_(const void **a, const void **b)
  3720. {
  3721. routerinfo_t *first = *(routerinfo_t **)a, *second = *(routerinfo_t **)b;
  3722. int first_is_auth, second_is_auth;
  3723. uint32_t bw_kb_first, bw_kb_second;
  3724. const node_t *node_first, *node_second;
  3725. int first_is_running, second_is_running;
  3726. /* we return -1 if first should appear before second... that is,
  3727. * if first is a better router. */
  3728. if (first->addr < second->addr)
  3729. return -1;
  3730. else if (first->addr > second->addr)
  3731. return 1;
  3732. /* Potentially, this next bit could cause k n lg n memeq calls. But in
  3733. * reality, we will almost never get here, since addresses will usually be
  3734. * different. */
  3735. first_is_auth =
  3736. router_digest_is_trusted_dir(first->cache_info.identity_digest);
  3737. second_is_auth =
  3738. router_digest_is_trusted_dir(second->cache_info.identity_digest);
  3739. if (first_is_auth && !second_is_auth)
  3740. return -1;
  3741. else if (!first_is_auth && second_is_auth)
  3742. return 1;
  3743. node_first = node_get_by_id(first->cache_info.identity_digest);
  3744. node_second = node_get_by_id(second->cache_info.identity_digest);
  3745. first_is_running = node_first && node_first->is_running;
  3746. second_is_running = node_second && node_second->is_running;
  3747. if (first_is_running && !second_is_running)
  3748. return -1;
  3749. else if (!first_is_running && second_is_running)
  3750. return 1;
  3751. bw_kb_first = dirserv_get_bandwidth_for_router_kb(first);
  3752. bw_kb_second = dirserv_get_bandwidth_for_router_kb(second);
  3753. if (bw_kb_first > bw_kb_second)
  3754. return -1;
  3755. else if (bw_kb_first < bw_kb_second)
  3756. return 1;
  3757. /* They're equal! Compare by identity digest, so there's a
  3758. * deterministic order and we avoid flapping. */
  3759. return fast_memcmp(first->cache_info.identity_digest,
  3760. second->cache_info.identity_digest,
  3761. DIGEST_LEN);
  3762. }
  3763. /** Given a list of routerinfo_t in <b>routers</b>, return a new digestmap_t
  3764. * whose keys are the identity digests of those routers that we're going to
  3765. * exclude for Sybil-like appearance. */
  3766. static digestmap_t *
  3767. get_possible_sybil_list(const smartlist_t *routers)
  3768. {
  3769. const or_options_t *options = get_options();
  3770. digestmap_t *omit_as_sybil;
  3771. smartlist_t *routers_by_ip = smartlist_new();
  3772. uint32_t last_addr;
  3773. int addr_count;
  3774. /* Allow at most this number of Tor servers on a single IP address, ... */
  3775. int max_with_same_addr = options->AuthDirMaxServersPerAddr;
  3776. if (max_with_same_addr <= 0)
  3777. max_with_same_addr = INT_MAX;
  3778. smartlist_add_all(routers_by_ip, routers);
  3779. smartlist_sort(routers_by_ip, compare_routerinfo_by_ip_and_bw_);
  3780. omit_as_sybil = digestmap_new();
  3781. last_addr = 0;
  3782. addr_count = 0;
  3783. SMARTLIST_FOREACH_BEGIN(routers_by_ip, routerinfo_t *, ri) {
  3784. if (last_addr != ri->addr) {
  3785. last_addr = ri->addr;
  3786. addr_count = 1;
  3787. } else if (++addr_count > max_with_same_addr) {
  3788. digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri);
  3789. }
  3790. } SMARTLIST_FOREACH_END(ri);
  3791. smartlist_free(routers_by_ip);
  3792. return omit_as_sybil;
  3793. }
  3794. /** Given a platform string as in a routerinfo_t (possibly null), return a
  3795. * newly allocated version string for a networkstatus document, or NULL if the
  3796. * platform doesn't give a Tor version. */
  3797. static char *
  3798. version_from_platform(const char *platform)
  3799. {
  3800. if (platform && !strcmpstart(platform, "Tor ")) {
  3801. const char *eos = find_whitespace(platform+4);
  3802. if (eos && !strcmpstart(eos, " (r")) {
  3803. /* XXXX Unify this logic with the other version extraction
  3804. * logic in routerparse.c. */
  3805. eos = find_whitespace(eos+1);
  3806. }
  3807. if (eos) {
  3808. return tor_strndup(platform, eos-platform);
  3809. }
  3810. }
  3811. return NULL;
  3812. }
  3813. /** Given a (possibly empty) list of config_line_t, each line of which contains
  3814. * a list of comma-separated version numbers surrounded by optional space,
  3815. * allocate and return a new string containing the version numbers, in order,
  3816. * separated by commas. Used to generate Recommended(Client|Server)?Versions
  3817. */
  3818. char *
  3819. format_recommended_version_list(const config_line_t *ln, int warn)
  3820. {
  3821. smartlist_t *versions;
  3822. char *result;
  3823. versions = smartlist_new();
  3824. for ( ; ln; ln = ln->next) {
  3825. smartlist_split_string(versions, ln->value, ",",
  3826. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  3827. }
  3828. /* Handle the case where a dirauth operator has accidentally made some
  3829. * versions space-separated instead of comma-separated. */
  3830. smartlist_t *more_versions = smartlist_new();
  3831. SMARTLIST_FOREACH_BEGIN(versions, char *, v) {
  3832. if (strchr(v, ' ')) {
  3833. if (warn)
  3834. log_warn(LD_DIRSERV, "Unexpected space in versions list member %s. "
  3835. "(These are supposed to be comma-separated; I'll pretend you "
  3836. "used commas instead.)", escaped(v));
  3837. SMARTLIST_DEL_CURRENT(versions, v);
  3838. smartlist_split_string(more_versions, v, NULL,
  3839. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  3840. tor_free(v);
  3841. }
  3842. } SMARTLIST_FOREACH_END(v);
  3843. smartlist_add_all(versions, more_versions);
  3844. smartlist_free(more_versions);
  3845. /* Check to make sure everything looks like a version. */
  3846. if (warn) {
  3847. SMARTLIST_FOREACH_BEGIN(versions, const char *, v) {
  3848. tor_version_t ver;
  3849. if (tor_version_parse(v, &ver) < 0) {
  3850. log_warn(LD_DIRSERV, "Recommended version %s does not look valid. "
  3851. " (I'll include it anyway, since you told me to.)",
  3852. escaped(v));
  3853. }
  3854. } SMARTLIST_FOREACH_END(v);
  3855. }
  3856. sort_version_list(versions, 1);
  3857. result = smartlist_join_strings(versions,",",0,NULL);
  3858. SMARTLIST_FOREACH(versions,char *,s,tor_free(s));
  3859. smartlist_free(versions);
  3860. return result;
  3861. }
  3862. /** If there are entries in <b>routers</b> with exactly the same ed25519 keys,
  3863. * remove the older one. If they are exactly the same age, remove the one
  3864. * with the greater descriptor digest. May alter the order of the list. */
  3865. static void
  3866. routers_make_ed_keys_unique(smartlist_t *routers)
  3867. {
  3868. routerinfo_t *ri2;
  3869. digest256map_t *by_ed_key = digest256map_new();
  3870. SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) {
  3871. ri->omit_from_vote = 0;
  3872. if (ri->cache_info.signing_key_cert == NULL)
  3873. continue; /* No ed key */
  3874. const uint8_t *pk = ri->cache_info.signing_key_cert->signing_key.pubkey;
  3875. if ((ri2 = digest256map_get(by_ed_key, pk))) {
  3876. /* Duplicate; must omit one. Set the omit_from_vote flag in whichever
  3877. * one has the earlier published_on. */
  3878. const time_t ri_pub = ri->cache_info.published_on;
  3879. const time_t ri2_pub = ri2->cache_info.published_on;
  3880. if (ri2_pub < ri_pub ||
  3881. (ri2_pub == ri_pub &&
  3882. fast_memcmp(ri->cache_info.signed_descriptor_digest,
  3883. ri2->cache_info.signed_descriptor_digest,DIGEST_LEN)<0)) {
  3884. digest256map_set(by_ed_key, pk, ri);
  3885. ri2->omit_from_vote = 1;
  3886. } else {
  3887. ri->omit_from_vote = 1;
  3888. }
  3889. } else {
  3890. /* Add to map */
  3891. digest256map_set(by_ed_key, pk, ri);
  3892. }
  3893. } SMARTLIST_FOREACH_END(ri);
  3894. digest256map_free(by_ed_key, NULL);
  3895. /* Now remove every router where the omit_from_vote flag got set. */
  3896. SMARTLIST_FOREACH_BEGIN(routers, const routerinfo_t *, ri) {
  3897. if (ri->omit_from_vote) {
  3898. SMARTLIST_DEL_CURRENT(routers, ri);
  3899. }
  3900. } SMARTLIST_FOREACH_END(ri);
  3901. }
  3902. /** Routerstatus <b>rs</b> is part of a group of routers that are on
  3903. * too narrow an IP-space. Clear out its flags since we don't want it be used
  3904. * because of its Sybil-like appearance.
  3905. *
  3906. * Leave its BadExit flag alone though, since if we think it's a bad exit,
  3907. * we want to vote that way in case all the other authorities are voting
  3908. * Running and Exit.
  3909. */
  3910. static void
  3911. clear_status_flags_on_sybil(routerstatus_t *rs)
  3912. {
  3913. rs->is_authority = rs->is_exit = rs->is_stable = rs->is_fast =
  3914. rs->is_flagged_running = rs->is_named = rs->is_valid =
  3915. rs->is_hs_dir = rs->is_v2_dir = rs->is_possible_guard = 0;
  3916. /* FFFF we might want some mechanism to check later on if we
  3917. * missed zeroing any flags: it's easy to add a new flag but
  3918. * forget to add it to this clause. */
  3919. }
  3920. /** Return a new networkstatus_t* containing our current opinion. (For v3
  3921. * authorities) */
  3922. networkstatus_t *
  3923. dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
  3924. authority_cert_t *cert)
  3925. {
  3926. const or_options_t *options = get_options();
  3927. networkstatus_t *v3_out = NULL;
  3928. uint32_t addr;
  3929. char *hostname = NULL, *client_versions = NULL, *server_versions = NULL;
  3930. const char *contact;
  3931. smartlist_t *routers, *routerstatuses;
  3932. char identity_digest[DIGEST_LEN];
  3933. char signing_key_digest[DIGEST_LEN];
  3934. int listbadexits = options->AuthDirListBadExits;
  3935. routerlist_t *rl = router_get_routerlist();
  3936. time_t now = time(NULL);
  3937. time_t cutoff = now - ROUTER_MAX_AGE_TO_PUBLISH;
  3938. networkstatus_voter_info_t *voter = NULL;
  3939. vote_timing_t timing;
  3940. digestmap_t *omit_as_sybil = NULL;
  3941. const int vote_on_reachability = running_long_enough_to_decide_unreachable();
  3942. smartlist_t *microdescriptors = NULL;
  3943. smartlist_t *bw_file_headers = NULL;
  3944. tor_assert(private_key);
  3945. tor_assert(cert);
  3946. if (crypto_pk_get_digest(private_key, signing_key_digest)<0) {
  3947. log_err(LD_BUG, "Error computing signing key digest");
  3948. return NULL;
  3949. }
  3950. if (crypto_pk_get_digest(cert->identity_key, identity_digest)<0) {
  3951. log_err(LD_BUG, "Error computing identity key digest");
  3952. return NULL;
  3953. }
  3954. if (resolve_my_address(LOG_WARN, options, &addr, NULL, &hostname)<0) {
  3955. log_warn(LD_NET, "Couldn't resolve my hostname");
  3956. return NULL;
  3957. }
  3958. if (!hostname || !strchr(hostname, '.')) {
  3959. tor_free(hostname);
  3960. hostname = tor_dup_ip(addr);
  3961. }
  3962. if (options->VersioningAuthoritativeDir) {
  3963. client_versions =
  3964. format_recommended_version_list(options->RecommendedClientVersions, 0);
  3965. server_versions =
  3966. format_recommended_version_list(options->RecommendedServerVersions, 0);
  3967. }
  3968. contact = get_options()->ContactInfo;
  3969. if (!contact)
  3970. contact = "(none)";
  3971. /*
  3972. * Do this so dirserv_compute_performance_thresholds() and
  3973. * set_routerstatus_from_routerinfo() see up-to-date bandwidth info.
  3974. */
  3975. if (options->V3BandwidthsFile) {
  3976. dirserv_read_measured_bandwidths(options->V3BandwidthsFile, NULL, NULL);
  3977. } else {
  3978. /*
  3979. * No bandwidths file; clear the measured bandwidth cache in case we had
  3980. * one last time around.
  3981. */
  3982. if (dirserv_get_measured_bw_cache_size() > 0) {
  3983. dirserv_clear_measured_bw_cache();
  3984. }
  3985. }
  3986. /* precompute this part, since we need it to decide what "stable"
  3987. * means. */
  3988. SMARTLIST_FOREACH(rl->routers, routerinfo_t *, ri, {
  3989. dirserv_set_router_is_running(ri, now);
  3990. });
  3991. routers = smartlist_new();
  3992. smartlist_add_all(routers, rl->routers);
  3993. routers_make_ed_keys_unique(routers);
  3994. /* After this point, don't use rl->routers; use 'routers' instead. */
  3995. routers_sort_by_identity(routers);
  3996. omit_as_sybil = get_possible_sybil_list(routers);
  3997. DIGESTMAP_FOREACH(omit_as_sybil, sybil_id, void *, ignore) {
  3998. (void) ignore;
  3999. rep_hist_make_router_pessimal(sybil_id, now);
  4000. } DIGESTMAP_FOREACH_END;
  4001. /* Count how many have measured bandwidths so we know how to assign flags;
  4002. * this must come before dirserv_compute_performance_thresholds() */
  4003. dirserv_count_measured_bws(routers);
  4004. dirserv_compute_performance_thresholds(omit_as_sybil);
  4005. routerstatuses = smartlist_new();
  4006. microdescriptors = smartlist_new();
  4007. SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) {
  4008. /* If it has a protover list and contains a protocol name greater than
  4009. * MAX_PROTOCOL_NAME_LENGTH, skip it. */
  4010. if (ri->protocol_list &&
  4011. protover_contains_long_protocol_names(ri->protocol_list)) {
  4012. continue;
  4013. }
  4014. if (ri->cache_info.published_on >= cutoff) {
  4015. routerstatus_t *rs;
  4016. vote_routerstatus_t *vrs;
  4017. node_t *node = node_get_mutable_by_id(ri->cache_info.identity_digest);
  4018. if (!node)
  4019. continue;
  4020. vrs = tor_malloc_zero(sizeof(vote_routerstatus_t));
  4021. rs = &vrs->status;
  4022. set_routerstatus_from_routerinfo(rs, node, ri, now,
  4023. listbadexits);
  4024. if (ri->cache_info.signing_key_cert) {
  4025. memcpy(vrs->ed25519_id,
  4026. ri->cache_info.signing_key_cert->signing_key.pubkey,
  4027. ED25519_PUBKEY_LEN);
  4028. }
  4029. if (digestmap_get(omit_as_sybil, ri->cache_info.identity_digest))
  4030. clear_status_flags_on_sybil(rs);
  4031. if (!vote_on_reachability)
  4032. rs->is_flagged_running = 0;
  4033. vrs->version = version_from_platform(ri->platform);
  4034. if (ri->protocol_list) {
  4035. vrs->protocols = tor_strdup(ri->protocol_list);
  4036. } else {
  4037. vrs->protocols = tor_strdup(
  4038. protover_compute_for_old_tor(vrs->version));
  4039. }
  4040. vrs->microdesc = dirvote_format_all_microdesc_vote_lines(ri, now,
  4041. microdescriptors);
  4042. smartlist_add(routerstatuses, vrs);
  4043. }
  4044. } SMARTLIST_FOREACH_END(ri);
  4045. {
  4046. smartlist_t *added =
  4047. microdescs_add_list_to_cache(get_microdesc_cache(),
  4048. microdescriptors, SAVED_NOWHERE, 0);
  4049. smartlist_free(added);
  4050. smartlist_free(microdescriptors);
  4051. }
  4052. smartlist_free(routers);
  4053. digestmap_free(omit_as_sybil, NULL);
  4054. /* Apply guardfraction information to routerstatuses. */
  4055. if (options->GuardfractionFile) {
  4056. dirserv_read_guardfraction_file(options->GuardfractionFile,
  4057. routerstatuses);
  4058. }
  4059. /* This pass through applies the measured bw lines to the routerstatuses */
  4060. if (options->V3BandwidthsFile) {
  4061. /* Only set bw_file_headers when V3BandwidthsFile is configured */
  4062. bw_file_headers = smartlist_new();
  4063. dirserv_read_measured_bandwidths(options->V3BandwidthsFile,
  4064. routerstatuses, bw_file_headers);
  4065. } else {
  4066. /*
  4067. * No bandwidths file; clear the measured bandwidth cache in case we had
  4068. * one last time around.
  4069. */
  4070. if (dirserv_get_measured_bw_cache_size() > 0) {
  4071. dirserv_clear_measured_bw_cache();
  4072. }
  4073. }
  4074. v3_out = tor_malloc_zero(sizeof(networkstatus_t));
  4075. v3_out->type = NS_TYPE_VOTE;
  4076. dirvote_get_preferred_voting_intervals(&timing);
  4077. v3_out->published = now;
  4078. {
  4079. char tbuf[ISO_TIME_LEN+1];
  4080. networkstatus_t *current_consensus =
  4081. networkstatus_get_live_consensus(now);
  4082. long last_consensus_interval; /* only used to pick a valid_after */
  4083. if (current_consensus)
  4084. last_consensus_interval = current_consensus->fresh_until -
  4085. current_consensus->valid_after;
  4086. else
  4087. last_consensus_interval = options->TestingV3AuthInitialVotingInterval;
  4088. v3_out->valid_after =
  4089. voting_schedule_get_start_of_next_interval(now,
  4090. (int)last_consensus_interval,
  4091. options->TestingV3AuthVotingStartOffset);
  4092. format_iso_time(tbuf, v3_out->valid_after);
  4093. log_notice(LD_DIR,"Choosing valid-after time in vote as %s: "
  4094. "consensus_set=%d, last_interval=%d",
  4095. tbuf, current_consensus?1:0, (int)last_consensus_interval);
  4096. }
  4097. v3_out->fresh_until = v3_out->valid_after + timing.vote_interval;
  4098. v3_out->valid_until = v3_out->valid_after +
  4099. (timing.vote_interval * timing.n_intervals_valid);
  4100. v3_out->vote_seconds = timing.vote_delay;
  4101. v3_out->dist_seconds = timing.dist_delay;
  4102. tor_assert(v3_out->vote_seconds > 0);
  4103. tor_assert(v3_out->dist_seconds > 0);
  4104. tor_assert(timing.n_intervals_valid > 0);
  4105. v3_out->client_versions = client_versions;
  4106. v3_out->server_versions = server_versions;
  4107. /* These are hardwired, to avoid disaster. */
  4108. v3_out->recommended_relay_protocols =
  4109. tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
  4110. "Link=4 Microdesc=1-2 Relay=2");
  4111. v3_out->recommended_client_protocols =
  4112. tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
  4113. "Link=4 Microdesc=1-2 Relay=2");
  4114. v3_out->required_client_protocols =
  4115. tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
  4116. "Link=4 Microdesc=1-2 Relay=2");
  4117. v3_out->required_relay_protocols =
  4118. tor_strdup("Cons=1 Desc=1 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
  4119. "Link=3-4 Microdesc=1 Relay=1-2");
  4120. /* We are not allowed to vote to require anything we don't have. */
  4121. tor_assert(protover_all_supported(v3_out->required_relay_protocols, NULL));
  4122. tor_assert(protover_all_supported(v3_out->required_client_protocols, NULL));
  4123. /* We should not recommend anything we don't have. */
  4124. tor_assert_nonfatal(protover_all_supported(
  4125. v3_out->recommended_relay_protocols, NULL));
  4126. tor_assert_nonfatal(protover_all_supported(
  4127. v3_out->recommended_client_protocols, NULL));
  4128. v3_out->package_lines = smartlist_new();
  4129. {
  4130. config_line_t *cl;
  4131. for (cl = get_options()->RecommendedPackages; cl; cl = cl->next) {
  4132. if (validate_recommended_package_line(cl->value))
  4133. smartlist_add_strdup(v3_out->package_lines, cl->value);
  4134. }
  4135. }
  4136. v3_out->known_flags = smartlist_new();
  4137. smartlist_split_string(v3_out->known_flags,
  4138. "Authority Exit Fast Guard Stable V2Dir Valid HSDir",
  4139. 0, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  4140. if (vote_on_reachability)
  4141. smartlist_add_strdup(v3_out->known_flags, "Running");
  4142. if (listbadexits)
  4143. smartlist_add_strdup(v3_out->known_flags, "BadExit");
  4144. smartlist_sort_strings(v3_out->known_flags);
  4145. if (options->ConsensusParams) {
  4146. v3_out->net_params = smartlist_new();
  4147. smartlist_split_string(v3_out->net_params,
  4148. options->ConsensusParams, NULL, 0, 0);
  4149. smartlist_sort_strings(v3_out->net_params);
  4150. }
  4151. v3_out->bw_file_headers = bw_file_headers;
  4152. voter = tor_malloc_zero(sizeof(networkstatus_voter_info_t));
  4153. voter->nickname = tor_strdup(options->Nickname);
  4154. memcpy(voter->identity_digest, identity_digest, DIGEST_LEN);
  4155. voter->sigs = smartlist_new();
  4156. voter->address = hostname;
  4157. voter->addr = addr;
  4158. voter->dir_port = router_get_advertised_dir_port(options, 0);
  4159. voter->or_port = router_get_advertised_or_port(options);
  4160. voter->contact = tor_strdup(contact);
  4161. if (options->V3AuthUseLegacyKey) {
  4162. authority_cert_t *c = get_my_v3_legacy_cert();
  4163. if (c) {
  4164. if (crypto_pk_get_digest(c->identity_key, voter->legacy_id_digest)) {
  4165. log_warn(LD_BUG, "Unable to compute digest of legacy v3 identity key");
  4166. memset(voter->legacy_id_digest, 0, DIGEST_LEN);
  4167. }
  4168. }
  4169. }
  4170. v3_out->voters = smartlist_new();
  4171. smartlist_add(v3_out->voters, voter);
  4172. v3_out->cert = authority_cert_dup(cert);
  4173. v3_out->routerstatus_list = routerstatuses;
  4174. /* Note: networkstatus_digest is unset; it won't get set until we actually
  4175. * format the vote. */
  4176. return v3_out;
  4177. }