Stolechain

Sursa pentru această problemă poate fi accesată aici sau în secțiunea „Atașamente” din lateral.

Cerință

Mai mulți studenți la UNSTPB s-au adunat plini de idei și entuziasm pentru a crea AcadCoin, moneda lor digitală. În timp ce lucrau împreună la aceasta, au observat că unul dintre ei, pe nume Andrei, părea să lucreze la ceva în plus pe la spatele lor. Sebi, fiind mereu atent la detalii, a descoperit că Andrei, folosindu-se de propria sa gândire de geniu, a găsit o metodă greu de detectat prin care fură monede. Înainte de a fi exclus din echipă, Andrei a reușit să fure ultima felie de pizza și să schimbe codul sursă pentru a-i oferi control asupra monedei. Acum, echipa se confruntă cu o provocare dificilă, și anume să neutralizeze efectele rele ale codului lui Andrei.

Blockchain-ul poate fi imaginat ca un fel de caiet special folosit pentru a ține evidența tranzacțiilor unei monede (cine a plătit cui, cât și când), în care oricine poate propune tranzacții. Totuși, ca acestea să fie acceptate, trebuie inițiate de către cel care dorește să transfere suma de monede, nu de cel care le primește sau altcineva. De aceea, tranzacțiile includ și un număr de verificare (numit semnătură), care prin diverse metode de hashing, criptare si decriptare pot confirma identitatea inițiatorului. Astfel, fiecare utilizator va avea la bază o pereche de chei, una publică și una privată. La cheia privată are acces doar utilizatorul, iar aceasta este folosită pentru semnare. Cheia publică este cunoscută de întreaga rețea. Oricine o poate folosi pentru a verifica dacă o operație a fost semnată de userul corect.

În realitate, blockchainul fiind o rețea distribuită, "caietul" este stocat de toate entitățile din rețea.
Un utilizator poate încerca să falsifice o intrare. De aceea, trebuie să existe un algoritm de consens prin care utilizatorii trebuie să comunice între ei pentru a stabili un adevăr unic. Cel mai simplu algoritm de consens este decizia prin votul majorității. Un utilizator rău intenționat nu va putea introduce o tranzacție invalidă în blockchain, pentru că nu va fi acceptată de restul.

În cazul nostru, dacă o tranzacție primește peste $50\%$ de confirmări din rețea, tranzacția se aprobă. De asemenea, fiecare calculator din rețea este considerat o entitate (adică, dacă un utilizator are $5$ calculatoare, el are $5$ voturi). Vrem să evităm ca un utilizator să monopolizeze rețeaua, așa că nu permitem nimănui să aibă mai mult de $50\%$ din numărul de calculatoare din rețea. Deci când cineva încearcă să își adauge stația în rețea, cererea poate fi refuzată dacă pune în pericol securitatea. Dacă utilizatorul ar avea prea multe voturi în rețea, și-ar putea valida propriile tranzacții frauduloase de la altcineva către el însuși.

De asemenea, rețeaua noastră permite schimbarea cheilor private și publice, lucru pentru care este din nou necesară semnătura.

Problema noastră privește acest concept din perspectiva unui server care primește cereri din partea utilizatorilor. Semnătura este deja calculată de către utilizator (motiv pentru care, funcția encrypt nu este folosită în cadrul programului nostru, ci doar este prezentă în clasa User).

Mai jos, vom simula o cerere de transfer de monede trimisă de un utilizator (toate tipurile de cereri pe care un utilizator le poate face urmează același traseu, de aceea nu le vom trata separat). Vom observa că la server ajunge aceasta împreună cu semnatura creată de utilizator:

Date de intrare

Se citește $n$, reprezentând numărul de utilizatori din blockchain, iar apoi $n$ utilizatori cu formatul Nume Balanta Numar_PCuri Exponent Public_key Private_key.

Urmează un număr $m$, reprezentând numărul de solicitări ale utilizatorilor, iar apoi $m$ solicitări de forma:

• SEND Nume_Trimitator Nume_Destinatar Suma Semnatura — transferă de la Nume_Trimitator în contul lui Nume_Destinatar un număr de Suma monede AcadCoin;
• CHANGE_PASSWORD Nume Exponent_Nou Cheie_Publica_Noua Cheie_Privata_Noua Semnatura — schimbă detaliile pentru criptare și decriptare ale lui Nume;
• ADD_PC Nume — adaugă un calculator lui Nume (aici nu mai este necesară semnătura, deci, aceasta nu va mai fi verificată de către ceilalți utilizatori).

Date de ieșire

Pentru fiecare comandă din cele de mai sus, se vor afișa:

• SEND:
  • Invalid signature dacă tranzacția nu a fost inițiată/semnată de către trimițător;
  • Nume_trimitator has insufficient balance dacă trimițătorul nu are suma necesară pentru transfer;
  • Nume_trimitator sent Suma to Nume_primitor dacă tranzacția a avut loc cu succes;
• CHANGE_PASSWORD:
  • Invalid signature dacă cererea nu a fost inițiată/semnată de către cel asupra căruia se petrece schimbarea;
  • Password changed for Nume dacă perechea de chei a utilizatorului a fost schimbată;
• ADD_PC:
  • PC added to Nume dacă calculatorul a fost adăugat în rețea;
  • PC not added to Nume dacă calculatorul nu a fost adăugat în rețea.

Apoi, se va afișa balanța fiecărui utilizator sub forma `Nume Balanta'.

Restricții și precizări

• Solicitările de la intrare vor conține nume valide de useri.
• Semnătura pentru SEND provine din concatenarea următoarelor valori într-un string, separate printr-un spațiu: Nume_Trimitator Nume_Destinatar Suma.
• Semnătura pentru CHANGE_PASSWORD provine din concatenarea următoarelor valori într-un string, separate printr-un spațiu: Nume Exponent_Nou Cheie_Publica_Noua Cheie_Privata_Noua.
• Codul din clasa Hasher nu are buguri.

Exemplul 1

stdin

2
Alice 1900 4 7 3262089553 2329982343
Bob 2000 4 7 3566775067 2547610983
10
SEND Alice Bob 200 2346129895
SEND Alice Bob 300 3112513739
SEND Alice Bob 200 2346129895
SEND Alice Bob 200 1234567890
CHANGE_PASSWORD Alice 7 3484061857 2488530883 1230990308
CHANGE_PASSWORD Alice 7 3484061857 2488530883 18090708
CHANGE_PASSWORD Alice 7 3484061857 2488530883 18090708
CHANGE_PASSWORD Alice 7 3484061857 2488530883 3298412722
SEND Alice Bob 200 775141743
SEND Alice Bob 1001 1428497737

stdout

Alice sent 200 to Bob
Alice sent 300 to Bob
Alice sent 200 to Bob
Invalid signature
Password changed for Alice
Password changed for Alice
Password changed for Alice
Invalid signature
Alice sent 200 to Bob
Alice has insufficient balance
Alice 1000
Bob 2900

Exemplul 2

stdin

4
Bjarne 7800 1 7 1490867669 425940127
Ada 6400 1 7 3524241173 2013783943
Carmack 3600 9 7 1659516809 948247783
Guido 0 10 7 2939108723 419857087
7
ADD_PC Guido
ADD_PC Guido
ADD_PC Carmack
ADD_PC Ada
ADD_PC Guido
ADD_PC Guido
ADD_PC Guido

stdout

PC added to Guido
PC not added to Guido
PC added to Carmack
PC added to Ada
PC added to Guido
PC added to Guido
PC not added to Guido
Bjarne 7800
Ada 6400
Carmack 3600
Guido 0

Explicație

Pentru al doilea exemplu, în a doua și a șaptea comandă, calculatoarele lui Guido ar depăși jumătate din total, așa că serverul nu permite adăugarea calculatorului.