En autentiserad datastruktur (ADS) är en datastruktur vars verksamhet kan utföras av en opålitlig testare, vars resultat en kontrollör effektivt kan kontrollera som autentiska. Detta görs genom att provkroppen ger ett kompakt bevis på att kontrollören kan kontrollera tillsammans med varje verksamhets resultat. ADS stöder därmed outsourcing data underhåll och behandling av uppgifter till opålitliga servrar utan förlust av integritet. Tidigare arbete med ADS har fokuserat på särskilda datastrukturer (eller begränsade kategorier av datastrukturer), en i taget, ofta med stöd endast för särskilda verksamheter. Detta dokument presenterar en generisk metod, med hjälp av en enkel utvidgning till ett ML-liknande funktionellt programmeringsspråk som vi kallar λ• (lambda-auth), med vilken man kan programmera autentiserade operationer över någon datastruktur som definieras av standard typ konstruktörer, inklusive rekursiva typer, summor, och produkter. Programmeraren skriver datastrukturen till stor del som vanligt och den sammanställs för att kodas för att köras av testare och kontrollör. Med hjälp av en formalisering av λ• visar vi att alla välskrivna λ• program resulterar i kod som är säker under standard kryptografiskt antagande om kollisionsresistenta hashfunktioner. Vi har implementerat λ• som en förlängning till OCaml kompilatorn, och har använt den för att producera autentiserade versioner av många intressanta datastrukturer inklusive binära sökträd, röd-svart + träd, skip lists, med mera. Prestandaexperiment visar att vårt tillvägagångssätt är effektivt och ger upp lite jämfört med de handoptimerade datastrukturer som utvecklats tidigare.
Miller och Al. REF presenterar en generisk metod för autentisering av transaktioner på alla datastrukturer som kan definieras av standardtypkonstruktörer.
Authenticated data structures, generically
{'venue': "POPL '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}