Schemă de angajament pentru o posibilă colecție neordonată de elemente în creștere

Arborii Merkle pot fi utilizați pentru schema de angajament vectorial. În special, având în vedere două secvențe S, S' cu aceleași elemente în aceeași ordine, rădăcina merkle pentru S va fi aceeași cu cea pentru S'. Ce se întâmplă dacă trebuie să atașez la S și S’ aceleași elemente în timp, dar pot diferi în ordine? Există vreo schemă specifică de angajament cea mai potrivită pentru acest scenariu?

Ideea unei scheme de angajament este că angajamentul nu dezvăluie ceea ce s-a angajat până când probatorul eliberează unele informații secrete. Pentru shemes-uri pe bază de hash, în general, angajamentul este C=H(R+V) Unde R este un număr mare (128 de biți) aleatoriu. Un atacator nu poate verifica o estimare a valorii V fara sa stie R.

Pentru o schemă de angajare vectorială a arborelui Merkle, frunzele din arborele Merkle ar fi angajamente privind valorile. Fiecare frunză din copac este calculată ca frunză[i]=Ci=H(Ri+Vi). Un angajament pentru [A,B,C,D,A,B,C,D] ar folosi diferite aleatorii Ri valori pentru fiecare frunză. În ciuda faptului că valorile din subarborele din stânga și din dreapta sunt identice ([A,B,C,D]) valorile frunzelor și subarborele rezultate sunt diferite.

Există optimizări care pot fi făcute în implementare, Adăugarea de valori la listă necesită doar adăugarea unei noi frunze la arborele merkle, de exemplu. Mai puțin evident, cel Ri valorile pot fi construite folosind un arbore binar pentru a reduce dimensiunea datelor asociate cu Ri secvență atunci când dezvăluie o porțiune din tabloul de valori.