The problem of distributed counting, and how we avoided it (at significant mental cost to you)

In lingering continuation of an ancient discussion, we will be making some changes to the Eulora communication protocol (still specced here).

To summarize, Eulora communications rest on a layered encrypted protocol. The first layer's RSA, which is known to be secure, but it is also very intensive, both in time (exponentiation's not free) and in space (OAEP ensures sub-50% packet utilization, for instance). The second layer's [an in-house elaboration ofⁱ] Serpent, which is much more comfortable but also ambiguousⁱⁱ. The RSA key is fixed and intrinsically melded into the notion of identity (as it should be!) whereas serpent keys are just kept in a round buffer by the hundreds, intended for and destined to ephemereality.

The protocol as summarily described (and naively represented in the reader's mind on a first pass read) works well enough in most practical situations : the RSA secure layer handles identity and Serpent key seeding, the Serpent workhorse layer takes over from there. Problems arise at the interface with a somewhat marginal case which is practically a ftp implementation : large quantities of data are sent over this protocol, being the game's own resources (models, animations, etcetera). UDP packets are relatively small (thousand bytes sorta thing) ; such assets are relatively large (million byte sorta thing), but an elaborate (yet remarkably flexible and functional, I must say!) algorithm cuts the files into more manageable-sized chunks, produces manifests for the lists, ships the manifests over first... it's basically torrenting but fast, cheap and altogether lite not to mention actually encrypted, because that "https" bullshit you folk do... But let's not get distracted with discussions of the pustulence and all-around misery of barbarian lands. Instead, let's say our thing works splendidly well, except...

There's this naive concept of automatically burning serpent keys, see ? It seemed, at some point illo tempore, in continuation of and comunion with specified idiocies, that it'd be a good idea to have an implicit rule for burning Serpent keys every nth use (potentially, n=1ⁱⁱⁱ, why not, if the user's willing to pay for the mounting costs involved the server will work for pay, that's what a server is). This leads to an insolvable problem : decentralized counting. We have some mechanisms to deal with it in some favourable cases (which involve private algebras and other things I absolutely won't... "bother" you with, for you're unworthy), but in this particular case, where the count can increase by arbitrarily large chunks suddenly... well, nothing's doing, what can I say.

We've seen all sorts of lulz as part of ongoing, for the past five or six weeks, experimental constructions to better understand the problem in our own terms (which is what the lab ever was for). Such as for instance a client telling the server "hey, use THIS key from now on!" upwards of sixty times (in response to a large burst of data) only to exhaust the key's lifetime thusly and so cap the hot mess with a message to... use a different key. (Which of course doesn't even have to arrive in order, yes, it could come in next-to-last or something, why not, it's UDP after all.) Such as for instance all sorts and manner, the fact of the matter's that decentralized counting is dubious at best...

Hellow, an' welcome to Part Two!!! of our article. When we parted company in part one (which at the time was merely The Article) barely twenty minutes ago, I hadn't yet had breakfast, and we were discussing things and matters phylosophycal and of great depth, such as distributed counting -- this enhancedly insane situation where two people count the things they say to each other over a lossy channel and baș-never manage to arrive at any sort of reconciled count ; nor is there any hope to resolve the situation through authority, because whoever is promoted to head librarian is stuck issuing a concrete number, and the recipient can always find itself looking at a five written down next to a collection of six items all present.

In other words, before this Part Two!!! came along, we were fucked. But then it occured to me^iv there's no absolute need to manage it as a distributed counting exercise, if (and only if) one lets go of the "modern democracy" poison and reverts to more traditional values. Removing spurious "communication" and assorted "anyone-can-do-anything-isms" from the pie results in... less complexity, or more properly put : manageable complexity.

And so... work continues, on better footing. Always remember : #BelieveWomen kills IRL.

And don't forget to love Rochester like I do!

1. This because everyone out there sucks pustulent whore ass and call it macaronifoss. There existed no such thing as a Serpent implementation before I had my own engineer make it exist, fancy that wonder. [↩]
2. Any buffer can be used as "key" to "decrypt" via this algorithm any buffer used as "encrypted message", resulting in a "decrypted message" of the correct length obtained through the correct number of steps. If this makes you salivate while you've your crypto hat on, because "man, sounds just like OTP", it'll also make you weep because there's no good ways to reject messages intrinsically. You always gotta know the item's actually a message, and actually intended for so-and-so key, you can't really do the (very useful!) old RSA trick, for instance. [↩]
3. An important point to underscore here is that even n=1 (meaning, burn the key used after every packet) does not in fact equate single-usage of Serpent keys.

   The 1472-byte Serpent packet is really a concatenation of 92 16-byte chunks, all of which were obtained by encrypting respective 16-byte payload chunks to the same Serpent key, so even the (extremely expensive!) n=1 case still means 92 reuses per Serpent key. Such is the nature of the beast : there's no self-obvious way to stretch Serpent to larger sizes ; there's not much utility to smaller UDP packets ; a procedure whereby 92 different keys are used for composing each packet could theoretically be implemented on the current protocol, however it'd increase costs substantially. [↩]

4. Here, if you wish to see raw the workings of true life I'm not one to deny :

   mircea_popescu diana_coman, tuuuu!
   mircea_popescu pula mea noi suntem idioti complet.
   mircea_popescu de ce isi face fiecare management la ~cheile lui~ ?!
   mircea_popescu sa faca bine sa faca management la cheile celuilalt, ca NU IS ALE CELUILALT. pizda fetei ii a mea nu a ei, ea doar o poarta prin lume si-i da de mincare, PENTRU MINE.
   mircea_popescu si fix tot asa, cheia pe care primeste clientu' mesaje E A SERVERULUI nu a clientului. serverul SI DOAR SERVERUL zice cind nu mai e buna.
   mircea_popescu clientu' doar plateste chirie pe memoria ei, atit, in rest e a lui cum e si puta cuckoldului.
   mircea_popescu si-n felu' asta, nu mai e problema de distributed counting. e problema de local counting : cind ~tu~ stii ca ai trimis X mesaje pe cheia Y, te muti pe cheia Z.
   diana_coman mircea_popescu: ha!
   mircea_popescu tot verific aici dac-ai aparut din 5 in cinci minute
   mircea_popescu ha! salut!
   mircea_popescu deci ma-ntelegi ce zic ?
   diana_coman la brute force mai sus: varianta 2 din ce zici acolo adica da, eliminat treptat
   diana_coman aici pricep, numai ma mir ca abia acum a iesit in sensul ca ne-am mai invartit pe langa ea da' n-a fost clar cum ar veni mai logic
   mircea_popescu eu blamez indoctrinarea psiho-sexuala a modernitatii
   diana_coman lol
   mircea_popescu sa mor de nu
   diana_coman nu prea creditez faza, da' in fine, nu e "cauza" esentiala acu'
   mircea_popescu nici nu e, si pe urma de ce n-ai si tu dreptu' sa-ti explici propria experienta cum ti-o explici, exact ca si mine ? io asa mi-o explic, tu te descurci
   mircea_popescu da' revenind : deci fa o proba asa, ca fiecare isi numara cheia "lui" in sensul de, cheia tinuta de celalalt in care encrpteaza. nu cheia tinuta de el
   diana_coman revenind insa, zici ca fiecare si le gestioneaza pe ale lui si altminteri doar informeaza gen "vezi ca ma mut" + mutat?
   mircea_popescu nope.
   diana_coman fiecare numara ce trimite
   mircea_popescu el nu se mai muta. gata cu aia.
   mircea_popescu fiecare numara ce trimite el si ATIT
   diana_coman ah, zici ca sa nu ma mai chinui cu cele doua countere?
   mircea_popescu ba da, alea lasa-le. DOAR ca nu mai depind chei burn de ele.
   mircea_popescu ci stau acolo de curiozitate, cum erau
   mircea_popescu hai sa repet tatu clar si explicit ca te chinui degeaba. deci :
   diana_coman bun, deci sa fac proba cu key burn inca pe "nr de utilizari" da' omeneste in sensul ca adica de cate ori le foloseste ala de numara
   diana_coman ascult
   mircea_popescu se face rsa handshake. serveru' trimite niste chei, spre a fi folosite in a scrie mesaje catre server. clientu' le noteaza.
   diana_coman da
   diana_coman asa si este acum
   mircea_popescu clientu' trimite niste alte chei, spre a fi folosite de server, sa-i scrie mesaje clientului.
   diana_coman asa este.
   mircea_popescu serveru' trimite 5 mesaje pe o cheie, si i se pare ca 5 is destul, asa ca trimite al saselea : de acum, mesaje mai departe trimit pe cheia X
   diana_coman adica face burn la cheia 5 si selecteaza cheia x
   mircea_popescu clientu' trimite si el mesaje catre server. de la un moment dat, i se pare c-o folosit destul o cheie, da "de acum, trimit pe Y"
   mircea_popescu exact asa.
   diana_coman ori ma rog, la cheia y ce era
   mircea_popescu da.
   mircea_popescu asta e tot.
   diana_coman bun, si daca se pierde mesajul ala si deci de ex primeste clientul ceva la care se uita ca-n calendar?
   mircea_popescu ce era pina acum si nu va mai fi, e situatia in care unu' decide sa-i futa cheia celuilalt da' tre' cumva sa-i zica
   mircea_popescu ignora
   diana_coman pai ignora da' atunci raman deci desincronizati ori cum vezi
   diana_coman la urmatorul burn zici ca se resincronizeaza oricum?
   mircea_popescu in cel mai rau caz isi refac rsa
   diana_coman ce zic eu e ca nu *realizeaza* ca s-au desincronizat
   mircea_popescu nu au cum sa se mai resincronizeze neam, deoarece urmatoru' burn va fi si el pe noua cheie
   diana_coman drept
   diana_coman deci si mai rau: nici nu stiu si si daca stiu tot degeaba
   mircea_popescu au cum sa realizeze, pentru ca clientu' nu mai pricepe nic din ce zice asta
   diana_coman pai da, da' n-are cum sa-i spuna
   diana_coman lol
   mircea_popescu pai isi refac rsa. deci pierdut pachetul ala anumit == disconnect
   mircea_popescu == rsa handshake
   diana_coman ah, deci zici ca daca nu pricepe, tolereaza eventual da' altminteri n-are ce face decat sa trimita iar via rsa
   mircea_popescu yup
   mircea_popescu nici nu are nici nu cred ca trebuie sa aiba.
   diana_coman adica sa trimita iar un set de chei pt vorbit cu el gen, ca alta n-are ce
   mircea_popescu daca doresti poate duplica pachetul ala.
   diana_coman si alea reseteaza
   mircea_popescu dap
   mircea_popescu facem asa, ca pachetul de burn e trimis de doua ori ? ca nu s-or pierde ambele ?
   diana_coman macar e mai clar asa, cum sa zic, ca ma innebunea toata invarteala dincolo
   mircea_popescu dap! e MULT mai clar, si ce e mai important, e macar corect sa-l fut
   diana_coman apai aia ma gandesc ca tine de implementare adica fiecare poate decide de cate ori vrea sa-l trimita, nu?
   mircea_popescu pai cam da. da; la server zic
   diana_coman daca unul vrea sa-si faca implementare sa trimita de 100 de ori cine ce-are cu el
   mircea_popescu ce ne caca pe noi un pachet udp extra.
   diana_coman da, numai ca tb sa aiba ceva interval ca sa aiba orice potential efect
   mircea_popescu cam da.
   diana_coman ca daca le trimite asa foc scurt imediat cam degeaba
   diana_coman poate trimite daca e la urmatorul heartbeat ori ceva, cuget acolo, nu-i problema
   mircea_popescu daca doresti : se pot tine TOATE burn facute de la ultimul heartbeat, si retrimise daca nu apare urmatorul. da' asta e deja poate cam mult.
   diana_coman eu altminteri in cod abia ce-am facut un v-commit si pe client si pe server ca sa stiu ca nu pierd istoric nimic din ce am facut da' altminteri inca n-am intrat sa chiar modific ca na, intai sa am clar ce fac acolo exact
   mircea_popescu orisicit : fa-i asta, da-o-n teste sa videm, si io am sa termin articolu' de care ma apucasem, da' iese foarte diferit de ce aveam initial lol. ca asa mi-o si picat fisa, incercind sa scriu articol
   diana_coman ha, deci tb sa scrii mai demult!!!
   diana_coman lol
   mircea_popescu pai plm, 9 januar chiar asa tardiv e ?
   diana_coman totul e ...cine si de unde numara!
   mircea_popescu heh
   diana_coman da' cine ne alearga altminteri
   mircea_popescu i plea commonality. ca altu' cinci ani nu-i pica fisa.
   diana_coman ca oricum ei obosesc si doar sa se uite, ce sa mai
   mircea_popescu bietii
   diana_coman apai mi-a si zis unul ca l-am ...extenuat; in conversatie!
   mircea_popescu lmao
   mircea_popescu nu-ti zic ce fericit is lol
   diana_coman da' sa stii ca si eu, mai ales ca imi rezolva asa frumos si partea aia cu "cum dracu' sa decida cand ori daca e cazul de reset"
   mircea_popescu e un salt calitativ
   diana_coman este.

   And so it goes! [↩]