[tahoe-dev] Weekly Dev Chat report, 2013-04-18

[Zooko Wilcox-OHearn]

2013-04-18

in attendance: Zooko, Oleg, Iraklis, CodesInChaos, Brian, Andrew, Daira, Amber

The topic was Andrew's mind-boggling PhD research project. It is a
type-driven compiler to generate authenticated data structures. So, if
I understand correctly, you write some code in a nice functional
language like Haskell that implements a data structure, and then you
apply these crazy type annotations to it that explain to Andrew's
compiler what it would mean for that thing to be an authenticated data
structure (i.e. "soundness" — the server can't forge the structure —
and "correctness" — whenever the server delivers an unforged answer,
the data structure produces the correct output). Then Andrew's
compiler generates a cryptographically-enforced version of the data
structure. This works for "Merklizing" arbitrary pointer-based data
structures (by using collision-resistant hashes as adjuncts to
pointers). Andrew has a demonstration of it which is an authenticated
Red-Black tree.

Watching this presentation melted my brain and I had to lie down
afterward. Daira bounced and clapped. She loved it. It all made
perfect sense to her.

Then, having got back up, I got on IRC and said a few things:

1. I'm interested in Red-Black trees as the basis of Large Distributed
Mutable Files.

2. I think relying on collision-resistance is iffy but relying on
2nd-pre-image-resistance is very safe. Here is an incomplete write-up
about that: https://zooko.com/uri/URI%3ADIR2-RO%3Ajztduk4og4p6meikidbxfkoeia%3Ayjx7niqa7czmtz6qn7calxpgr3nhjrdcnoxiz4t5pg7r4mwd5rvq/preimage-attacks.rst
 . The bottom line is that most of the real-world secure hash
functions ever created have turned out to be vulnerable to collisions,
but only one (Snefru, designed by Merkle in 1989) has ever turned out
to be vulnerable to 2nd-pre-images. So I actually care about the
difference between "If this protocol is unsound then here is a hash
collision." and the more complicated "If this protocol is unsound then
here is a second pre-image that hashes to the same image that the
pre-image you told me hashes to.".

3. Down with K=2! Binary trees suck. I'm a fan of fanout. Hopefully
this is the sort of thing that is trivially covered by Andrew's
generalized system.

next meeting: starting at 15:30Z (8:30 AM Pacific) instead of 16:00Z
(9:00 AM Pacific), like this one did.

Possible agenda items:

* Could Amiller's generalized authenticated data structures be useful
for Tahoe-LAFS?
* 1.10
* share placement for 1.11
* GSoC students ?

I think we'll have time for only about two of those agenda items...

Regards,

Zooko Wilcox-O'Hearn

Founder, CEO, and Customer Support Rep

https://LeastAuthority.com