search

AljoschaMeyer / bamboo

Creative Commons Attribution Share Alike 4.0 International
141 stars 4 forks source link

Question about verification rule #8

Open snej opened 4 years ago

snej commented 4 years ago

There's an inconsistency between the verification rules, and the definition of the certificate pool. My guess is that the verification rule is a bit too strict:

  • authenticity has been checked via the signature (matching the claimed author)
  • the entry has sequence number one OR there is a link path from the entry to the first entry, where all but the newest entry (which is the one to be verified) are already verified
  • the entry has sequence number one OR the backlink and the lipmaalink point to the entry of the expected sequence number

I didn't realize this until I started implementing it, but to verify an entry N it's not sufficient to have the entries along the lipmaalink path from 1 to N. You also need the backlinks of those entries, because the 3rd rule above implies that an intermediate entry can't be verified without checking its backlink too. (I guess that makes it a "hairy" path, since many of the entries in the path have additional backlinks sticking out.)

For the figure showing the certificate pool of entry 23, this means several other numbers need to be colored blue: 3, 12, 16, 20. (I think some orange numbers would need to be added too...?)

Is this the correct rule for verification, meaning the figure is incorrect? Or is the verification rule being too strict about intermediate entries?

AljoschaMeyer commented 4 years ago

I am sorry about the state of this readme, I've been planning a reworked version for a long time that would among other things have addressed this.

For the most part, I have abandoned the idea of "a log" being "verified" or "correct". All one can really do is to check for any pair of entries whether there is a path along hashes from one to the other. If there is, the two of them are known to be compatible, i.e. not on different branches of a forked log. In addition to that state, a bamboo database can assigned two other states to a pair of entries: they might be known to lie on different branches for certain, or there might not be enough entries available yet to determine which of the other two states the pair belongs to.

The verification rules in this repository simply don't reflect that mindset yet and are not really workable (since applying them transitively would always require downloading all entries).

All I can do for now is leave this issue open and refer to future updates for which I will hopefully make the time at some point =/

snej commented 4 years ago

Good to know — thanks. I agree that verification seems pretty heavyweight and might be more trouble than it's worth.

But I disagree about the current rules being unworkable. As I understand them, verifying an entry doesn't require verifying the previous (backlinked) entry, it only requires checking that its digest matches. So along the verification chain the backlinked entries must be fetched, but not transitively.

AljoschaMeyer commented 4 years ago

So along the verification chain the backlinked entries must be fetched, but not transitively.

True, but then again, what do you actually gain from doing so? Slightly better coverage in detecting forks, but a malicious author could still work around that in most cases I think.