Cu alte cuvinte, care este probabilitatea ca Bob să fi mințit despre rădăcina Merkle după N interogări?
Ei bine, iată o modalitate prin care Bob ar putea înșela; ar putea lua lista de $M$ valorile $$V_1, V_2, ..., V_M$$ și în loc să formați un arbore Merkle pe baza acestuia, selectați o valoare $c$ indice și o valoare $V'_c \ne V_c$, și în schimb formați lista $$V_1, V_2, ..., V_{c-1}, V'_c, V_{c+1}, ..., V_M$$ și formați arborele Merkle pe baza acelei liste (și dați lui Alice rădăcina calculată, care este cu o probabilitate destul de mare diferită de rădăcina din lista originală).
Apoi, când Alice îi dă $K$ indici pentru a baza $K$ dovezi, el le formează pe baza listei modificate și a arborelui pe care l-a calculat. El va fi detectat ca înșelă doar dacă unul dintre indicii pe care i-a cerut ea se întâmplă să fie indicele $c$; dacă niciunul dintre indicii pe care i-a cerut nu s-a întâmplat să fie pentru index $c$, atunci dovezile pe care le-ar primi sunt toate valide și consecvente între ele (deoarece corespund unui arbore Merkle auto-consecvent, frunzele revelate fiind valorile pe care le așteaptă)
Probabilitatea ca Bob să fie prins trișând, adică probabilitatea ca unul dintre indicii alesi de Alice este $c$, este $K/M$. Prin urmare, probabilitatea de detectare împotriva oricărei strategii nu este mai mare de atât (ar putea fi mai mică dacă există o strategie și mai bună pe care Bob ar putea-o folosi).
Deci, pentru a detecta Bob trișând cu probabilitatea 0,99, avem K$ > 0,99 M$; în acel moment, va fi de fapt mai puțin calcul pentru Alice dacă ar fi doar să recalculeze ea însăși arborele.
Ni s-a părut interesant pentru că ar putea fi o formă de dovadă a spațiului-timp dacă lista este costisitoare de construit
Acum, a privi problema ca pe o dovadă de lucru este puțin mai interesantă (dovada de spațiu nu funcționează, deoarece arborele și căile de autentificare pot fi calculate fără a crește semnificativ cantitatea de calcul necesară); evident, strategia de înșelăciune pe care am dat-o mai sus nu înlătură această problemă, deoarece Bob face toată munca. Dacă aș avea mai mult timp, aș încerca să investighez mai mult...
