You should read the paper's Appendix when you get to the point where Section III.B talks about ADSs.
The paper positions Verena as applying to a single web site, with its own database, its own web server, a specific application, and a hash server. Would it make sense to use Verena as the integrity mechanism for (for example) a big shared global DHT built from untrusted servers?
How do authenticated data structures (ADSs) work? What happens during a write? During a read? What does the storage server's proof look like?
At a high level, the point of Verena is to prevent bad people (or a corrupt server) from modifying data that they aren't supposed to modify. Suppose the server does modify data that it shouldn't. What happens then? If a client detects that the server is returning incorrect data, what should the client do to recover?
What happens if a new IQP (corresponding to a new query) is added to an existing database? Does a new ADS need to be created? Who does that, and who signs the content?
What happens if a user is added to an existing trust context? Delete?
Where does the DB store the data? Is it basically stored in the ADS trees, or are the ADS trees just for checking the content of some non-ADS tables that the DB maintains?
Verena supports fairly complex queries -- range scans over multiple rows, filtering, and aggregation (e.g. sums). What aspects of the design are there in order to support such queries? If Verena only supported a single-record put/get interface, could it be simpler? What kinds of applications require verified complex queries?
What is the purpose of the hash server? What would go wrong if Verena's design didn't include the hash server?
How does Verena relate to the fork-consistent systems we've seen? Is the idea that Verena has better consistency semantics? Better security? Or that Verena is faster?
Verena assumes the application developer is trusted, but the server is not trusted. Why does that make sense for the paper's use scenarios?
Verena requires that at least one of the Hash Server and the Verena Server be trustworthy, but it's only worthwhile if one of them is potentially malicious. If either could be malicious, why does it make sense to assume that the other must be good?
Is there one ADS per table? One ADS per trust context? One ADS per query?
Why does it make sense to group users into trust contexts? For the medical example, why not set up the policy so that each physician is only allowed to modify that physician's patients?
Why does Verena include trust contexts that include multiple users? Wouldn't it be more secure to specify precisely who is allowed to modify each record, or who is allowed to influence each query?
Why does Verena set policies on queries, rather than having write permissions on the data records?
What happens if one policy allows a user to write a record, but a different policy forbids a user from writing that record?
Could a malicious user create an IQP that prevents other people's data from being updated? For example, an IPQ for a query on a table with the empty set for a trust context?
Do read-only queries update the version number(s) in the hash server? If yes, why?