Today's call
43 views
Skip to first unread message
Ben Laurie
Feb 12, 2016, 11:46:09 AM2/12/16
to binary-tr...@googlegroups.com
Once more, can I ask everyone who said anything to summarise, since we still don't have a note-taker...
For my part, I was interested in who in the Debian community we might be able to pay to work on moving forward with BT...
Eric Myhre
Feb 18, 2016, 3:04:29 PM2/18/16
to binary-tr...@googlegroups.com
Belated as all sin, but I guess I had some (likely incomplete) cliff notes if no one else has... I'll try to provide attribution but mea cupla if I munge words or mistranslate!
### Efficient traversal:
We talked about ways to enable verifying "X-vn.m is the latest version of X" cheaply e.g. without downloading vasty/unbounded amounts of history.
BenL shares a story for that: a function for reducing the BT log to a map. This sounds like an effective way to put a cinch on things once and a while: assuming a client can trust the map, and getting their item of interest out of the map is cheaper than downloading additional ranges of history, they only need download and check history until they reach a map checkpoint.
dkg raises that this kind of delegation re-introduces a weakening trust centralization. But perhaps we can account for it by logging an objecthash of the map itself periodically? And then ensuring the func(stream)->map itself is publicly specified, deterministic, and verifiable. (Do we then log the community attestations, signed, back to the log?)
I'd love to describe a way to chunk up sub-maps in a reasonably deterministic way so we could do sharded verification. (This kind of resonates to me like using rabin fingerprinting to deterministically split large files into chunks...?) But this is an optimization problem, and maybe better served simply by human choices (e.g. here's the map for debian-latests, here's the map for freebsd-latests, etc).
### Object/tree hashing as the primitive in distribution:
dkg shared some thoughts about using merkle trees as the basis of distro packaging -- make sigs on roots of hash trees instead of per package. (I think there were a lot of noddings visible...)
### Splitting / Dovetailing of logs?
dkg has some ideas about the possible utility of having more than one log (topic logs?) and dovetailing them into another -- not sure I took good notes on this topic, I'll leave it to others to expand on.
I had some concerns about topic-limited logs meaning rarer updates, which may in some ways weaken the property of the log for pinning things at older dates. Others responded that periodically doing sigs on tip with short TTLs addresses this. (I still kind of have concerns about that but don't really know how to articulate them clearly so I'll punt until further notice... I think I'm interested in a "at least as old as X" property whereas our more common worry is up-to-dateness (which is the opposite direction and is indeed addressed by tip sigs), maybe?)
End-of-Notes.
Meta: ISTM we had a lot of ponderings about how to split things (easy) and how to merge them again (probably more tricky, because link/dovetail patterns would need to be well defined if we wanted automatic verification to traverse them). Not sure we have a list of folk's various concerns fuelling this e.g. manageability vs scalability etc, might be a useful list to gather in the future?
Cheers
E
### Efficient traversal:
We talked about ways to enable verifying "X-vn.m is the latest version of X" cheaply e.g. without downloading vasty/unbounded amounts of history.
BenL shares a story for that: a function for reducing the BT log to a map. This sounds like an effective way to put a cinch on things once and a while: assuming a client can trust the map, and getting their item of interest out of the map is cheaper than downloading additional ranges of history, they only need download and check history until they reach a map checkpoint.
dkg raises that this kind of delegation re-introduces a weakening trust centralization. But perhaps we can account for it by logging an objecthash of the map itself periodically? And then ensuring the func(stream)->map itself is publicly specified, deterministic, and verifiable. (Do we then log the community attestations, signed, back to the log?)
I'd love to describe a way to chunk up sub-maps in a reasonably deterministic way so we could do sharded verification. (This kind of resonates to me like using rabin fingerprinting to deterministically split large files into chunks...?) But this is an optimization problem, and maybe better served simply by human choices (e.g. here's the map for debian-latests, here's the map for freebsd-latests, etc).
### Object/tree hashing as the primitive in distribution:
dkg shared some thoughts about using merkle trees as the basis of distro packaging -- make sigs on roots of hash trees instead of per package. (I think there were a lot of noddings visible...)
### Splitting / Dovetailing of logs?
dkg has some ideas about the possible utility of having more than one log (topic logs?) and dovetailing them into another -- not sure I took good notes on this topic, I'll leave it to others to expand on.
I had some concerns about topic-limited logs meaning rarer updates, which may in some ways weaken the property of the log for pinning things at older dates. Others responded that periodically doing sigs on tip with short TTLs addresses this. (I still kind of have concerns about that but don't really know how to articulate them clearly so I'll punt until further notice... I think I'm interested in a "at least as old as X" property whereas our more common worry is up-to-dateness (which is the opposite direction and is indeed addressed by tip sigs), maybe?)
End-of-Notes.
Meta: ISTM we had a lot of ponderings about how to split things (easy) and how to merge them again (probably more tricky, because link/dovetail patterns would need to be well defined if we wanted automatic verification to traverse them). Not sure we have a list of folk's various concerns fuelling this e.g. manageability vs scalability etc, might be a useful list to gather in the future?
Cheers
E
Ben Laurie
Feb 19, 2016, 8:52:49 AM2/19/16
to Eric Myhre, binary-tr...@googlegroups.com
I updated our doc on verifiable data structures to be a bit clearer about the relationship between maps and logs, and also to talk about ordering. The new sections are "mapping functions" and "ordering".
--
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 an email to binary-tr...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/binary-transparency/56C623C4.3060803%40exultant.us.
For more options, visit https://groups.google.com/d/optout.
Martin Kleppmann
Feb 19, 2016, 10:14:44 AM2/19/16
to Ben Laurie, Eric Myhre, binary-tr...@googlegroups.com
I really like this idea of a verifiable (or perhaps better, "auditable") mapping function. It's close to some ideas I have been playing with recently, and I'm hoping to implement soon in order to explore further.
I believe the verifiable log-backed map data structure is equivalent to something described in Mark Ryan's NDSS 2014 paper “Enhanced certificate transparency and end-to-end encrypted mail”:
Might be worth adding a reference to it.
By the way, this paper is also very interesting:
It uses a verifiable map to bind user identifiers (e.g. email addresses, phone numbers) to public keys, but without making the full set of email addresses and phone numbers public. It achieves this using a verifiable unpredictable function (a kind of deterministic signature algorithm). It's perhaps unnecessary for binary transparency (where it is probably ok for all data to be public), but useful in other areas where you don't want to make everything public, but still want auditability.
Martin
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/CABrd9SSH8SNj7d8KP05weC%2BkOnRGq-Y%3D6piVN%3DAnQ2xDpFMyYg%40mail.gmail.com.
<VerifiableDataStructures (3).pdf>
Ben Laurie
Feb 19, 2016, 10:40:04 AM2/19/16
to Martin Kleppmann, Eric Myhre, binary-tr...@googlegroups.com
On 19 February 2016 at 15:14, Martin Kleppmann <mar...@kleppmann.com> wrote:
I really like this idea of a verifiable (or perhaps better, "auditable") mapping function. It's close to some ideas I have been playing with recently, and I'm hoping to implement soon in order to explore further.I believe the verifiable log-backed map data structure is equivalent to something described in Mark Ryan's NDSS 2014 paper “Enhanced certificate transparency and end-to-end encrypted mail”:Might be worth adding a reference to it.
That is actually building on our own previous work, Revocation Transparency, with alleged efficiency improvements that I don't actually agree with. Our paper is really just taking the original RT idea and adding the last 4 years of our thinking on that original idea, which is more in the nature of clarification than enhancement.
By the way, this paper is also very interesting:It uses a verifiable map to bind user identifiers (e.g. email addresses, phone numbers) to public keys, but without making the full set of email addresses and phone numbers public. It achieves this using a verifiable unpredictable function (a kind of deterministic signature algorithm). It's perhaps unnecessary for binary transparency (where it is probably ok for all data to be public), but useful in other areas where you don't want to make everything public, but still want auditability.
Right - we are very aware of CONIKS. We believe an essentially equivalent system can easily be built with a VDS (Verifiable Data Structure).
Reply all
Reply to author
Forward
0 new messages