Verifiable Data Structures

[Ben Laurie]

As promised ... sorry, not much notice before meeting, but it is brief.

Also, objecthash, as discussed last time: https://github.com/benlaurie/objecthash.

[Adam Eijdenberg]

And see also:

https://github.com/google/certificate-transparency/tree/master/python/demo/vdb

On Fri, Dec 4, 2015 at 1:59 AM 'Ben Laurie' via binary-transparency <binary-tr...@googlegroups.com> wrote:

As promised ... sorry, not much notice before meeting, but it is brief.

Also, objecthash, as discussed last time: https://github.com/benlaurie/objecthash.

--
You received this message because you are subscribed to the Google Groups "binary-transparency" group.
To unsubscribe from this group and stop receiving emails from it, send an email to binary-transpar...@googlegroups.com.
To post to this group, send email to binary-tr...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/binary-transparency/CABrd9SQaMhP4nAPy3jsSeQinG94yD0hNYBzyFVG1mhAhrfEf8g%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Philip Potter]

This paper says that "Clients of the map can... efficiently detect split-view attacks".  However, the revocation transparency paper [1] has the section "Consistency with Claimed Changes Is Not Enough" which seems to say that the given consistency proofs are not enough to defend against split-view attacks, and that you need some sort of CT-log-based structure to actually be safe.  This seems to say to me that verifiable maps do *not* allow a client to efficiently detect split-view attacks.  Have I misunderstood something?

Phil

[1]: http://sump2.links.org/files/RevocationTransparency.pdf

[Ben Laurie]

On 5 January 2016 at 03:58, Philip Potter <philip...@digital.cabinet-office.gov.uk> wrote:

This paper says that "Clients of the map can... efficiently detect split-view attacks".  However, the revocation transparency paper [1] has the section "Consistency with Claimed Changes Is Not Enough" which seems to say that the given consistency proofs are not enough to defend against split-view attacks, and that you need some sort of CT-log-based structure to actually be safe.  This seems to say to me that verifiable maps do *not* allow a client to efficiently detect split-view attacks.  Have I misunderstood something?

I am pleased to say the answer is: yes. :-)

The map _is_ accompanied by a log (essentially a log of all transactions that change the map). So long as someone is checking that the current map is the same as the accumulation of all the transactions in the current log, then everyone else gets efficient proofs of everything.

Phil

[1]: http://sump2.links.org/files/RevocationTransparency.pdf

On Friday, 4 December 2015 09:59:14 UTC, Ben Laurie wrote:

As promised ... sorry, not much notice before meeting, but it is brief.

Also, objecthash, as discussed last time: https://github.com/benlaurie/objecthash.

--
You received this message because you are subscribed to the Google Groups "binary-transparency" group.
To unsubscribe from this group and stop receiving emails from it, send an email to binary-transpar...@googlegroups.com.
To post to this group, send email to binary-tr...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/binary-transparency/d724b3c2-97a6-4571-9123-a892afc948c5%40googlegroups.com.

[Philip Potter]

For the avoidance of any doubt, I'm talking about the section of the
paper titled "Verifiable Maps", not the section titled "Verifiable
Log-Backed Map".

The "Verifiable Maps" section says that a verifiable map allows a
client to efficiently detect split-view attacks. It does not mention
any accompanying log. The accompanying log you describe seems to only
come in the "Verifiable Log-Backed Map" section?

[Ben Laurie]

On 5 January 2016 at 09:00, Philip Potter <philip...@digital.cabinet-office.gov.uk> wrote:

For the avoidance of any doubt, I'm talking about the section of the
paper titled "Verifiable Maps", not the section titled "Verifiable
Log-Backed Map".

The "Verifiable Maps" section says that a verifiable map allows a
client to efficiently detect split-view attacks.  It does not mention
any accompanying log.  The accompanying log you describe seems to only
come in the "Verifiable Log-Backed Map" section?

Ah, I see. Yes.

So, in the case of a map that is not log-backed, you can still detect split views in the trivial sense that if the root hash doesn't match its not the same tree.

But, of course, you can transform any map to any other, so I can show you map A and someone else map B and claim that they're both legit views at different times. Furthermore, I could never show anyone but you map A and no-one would be much wiser.

Once a log is added, then everyone can see both A and B.