8 ms·

Tamper-Evident Logs

106 points by philips 6y ago

philips 6y ago
We built a tamper evident log system for https content. The beta is over here: https://www.transparencylog.com/ https://www.transparencylog.com/ Or try out the CLI tool https://github.com/transparencylog/tl#installation https://github.com/transparencylog/tl#installation
- arianvanp 6y ago
  Heh; seems very similar to a project I've been working on :) github.com/arianvp/kpop.sh I'm happy to see my idea is not novel. That means I was on the right track :P
- kevin_nisbet 6y ago
  I've scanned through the work you've been doing on this a couple times, going back to trying to use letsencrypt / existing transparency logs. While its great stuff and really interesting, I wanted to point out the last time I looked at the current iteration I really struggled trying to understand how it worked, and as such how the security properties worked. Not meant to be criticism, just feedback, as it would be ideal to have some sort of transparency mechanism in common use.
cs702 6y ago
Couldn't we use, you know, git for the many applications that require a verifiable history of commits but don't need to be super fast or real-time?
- dang 6y ago
  "Don't be snarky." "Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html You may have a good point, but for it to be a good comment you would need to drop the snark and engage more specifically with the details of the article. The odds, for example, that the authors don't know about or have thought about git are basically zero.
  - cs702 6y ago
    dang: I did not mean for my comment to be snarky! I also did not mean it to be dismissive! I meant it as an honest, obvious question one should ask. But in hindsight, in the light of morning, my comment sure looks snarky, you're right. I wrote it quickly last night. Argh. Sorry. And thank you for taking the time to point it out. philips: please accept my apologies too. The last thing I want to be is snarky.
    - dang 6y ago
      It happens! Objects in the mirror are closer than they appear, etc. :) Thanks for the kind reply!
- justincormack 6y ago
  Git has an issue that branch heads are mutable, and unsigned, so two repos can disagree about what is head with the same commits in them. Using a transparency log to record changes in heads is like forcing no fast forwards and signing each change in heads.
  - cs702 6y ago
    Thanks for the clear explanation. That makes sense.
throw0101a 6y ago
RFC 5848, "Signed Syslog Messages": > This document describes a mechanism to add origin authentication, message integrity, replay resistance, message sequencing, and detection of missing messages to the transmitted syslog messages. This specification is intended to be used in conjunction with the work defined in RFC 5424, "The Syslog Protocol". * https://tools.ietf.org/html/rfc5848 https://tools.ietf.org/html/rfc5848
- deathanatos 6y ago
  Every time I've seen syslog in the wild, it's been the old "BSD" version (RFC 3164), not the newer RFC 5424 version. And pretty much any newer format, even something basic like JSON-lines over TCP, is going to be nicer to work with, IMO. (Though I admit, I have no idea how I'd even begin to start signing messages with JSON-lines.)
  - peteretep 6y ago
    Got to believe most JSON parsers can be set to permissive mode to allow comments, and then you could just append `//signature` on to the end of each JSON line?
    - throw0101a 6y ago
      Or you can simply STRUCTURED-DATA of RFC 5424 (§6.3) and put the signature into JSON proper as outlined in RFC 5428 § 4.2.9 (example): 2009-05-03T14:00:39.529966+02:00 host.example.org syslogd 2138 - [ssign VER="0111" RSID="1" SG="0" SPRI="0" GBC="2" FMN="1" CNT="7" HB="K6wzcombEvKJ+UTMcn9bPryAeaU= zrkDcIeaDluypaPCY8WWzwHpPok= zgrWOdpx16ADc7UmckyIFY53icE= XfopJ+S8/hODapiBBCgVQaLqBKg= J67gKMFl/OauTC20ibbydwIlJC8= M5GziVgB6KPY3ERU1HXdSi2vtdw= Wxd/lU7uG/ipEYT9xeqnsfohyH0=" SIGN="AKBbX4J7QkrwuwdbV7Taujk2lvOf8gCgC62We1QYfnrNHz7FzAvdySuMyfM="] You're trying to re-invent the wheel. Look at the prior art.
  - throw0101a 6y ago
    The STRUCTURED-DATA of RFC 5424 is basically JSON: > [exampleSDID@32473 iut="3" eventSource="Application" eventID="1011"][examplePriority@32473 class="high"] * https://tools.ietf.org/html/rfc5424#section-6.3 https://tools.ietf.org/html/rfc5424#section-6.3
keyle 6y ago
Sorry I read the page and I found it very vague. Pretty graphics and lot of white space for not much meat. Basically, looks like the command pattern implemented with signed token for every time you read, you must mutate the 'chain' or array of information. Am I close?
- owenmarshall 6y ago
  C-f Merkle It took quite a bit of time to get there. https://en.m.wikipedia.org/wiki/Merkle_tree https://en.m.wikipedia.org/wiki/Merkle_tree
- droptical 6y ago
  Many thanks for the feedback on the site, perhaps we need to get some more dense technical details either on there directly or adding to the existing docs on the github repo. Command pattern is definitely one pattern we've seen these tamper-evident logs applied to; you can easily imagine a system where, say, config update "commands" are packaged off and written to a TE log, and then workers apply those commands to a system if and only if they are convinced that the commands were properly logged. If the admins/command-workers/auditors etc. can all prove they're looking at the same set of logged commands (which is the property that these tamper-evident logs are intended to provide), then you have a reliable and tamper-evident audit trail of all changes to your system. There are a bunch of other scenarios we think these things might be useful for too, and we're trying to explore (and help others explore) these and provide mechanisms for reasoning about the properties of such systems. [Disclaimer: I work on CT, Trillian, and other related projects]
  - jacques_chester 6y ago
    > Command pattern is definitely one pattern we've seen these tamper-evident logs applied to; you can easily imagine a system where, say, config update "commands" are packaged off and written to a TE log, and then workers apply those commands to a system if and only if they are convinced that the commands were properly logged. Tip: call it LogOps and engage in an exercise-yard shiv-fight with GitOps folks. I prefer to think of both as examples of WAL or intent logs. It's a useful pattern and it's nice to have a narrowly-focused tool for it.
pram 6y ago
I’m sorry, but Trillian? That seems like a pretty major name collision with a well known piece of software that has been around for decades and has zero chance of getting displaced in search rankings lol
- tylerchilds 6y ago
  > has zero chance of getting displaced in search rankings unless this new product happens to be run by a company that controls a prominent search ranking algorithm
- qwantim1 6y ago
  In addition to an IM client, it was a character in HGTTG by Douglas Adams.
cocktailpeanuts 6y ago
Maybe I'm missing something, but there is already the term "append only logs" which we use everywhere. How is this different from append only logs? Append only logs rely on cryptography to make the history transparent too. I skimmed through the website but couldn't find a distinction. Also, the website format is kinda weird. As I reach the bottom of the page, it looks like this is a promotional site for Trillian. Maybe the confusion comes from here. What is this site really about?
- tleb_ 6y ago
  What cryptography are you referring to when talking about append-only logs? To me, an AOL is just a list of records that has a single operation, append. It could be implemented as a file that is only opened in append mode, multiple files (eg logrotate), a lib that works in memory, a process that exposes an API, etc. I don't see any cryptography here.
  - MertsA 6y ago
    In general, yes, an append only log might be weakly "append only". If you want a cryptographic approach look at how forward secure sealing works with systemd. Basically you make a cryptographic ratchet on the system doing the logging such that given some arbitrary key you can find out what the next key is but not the previous one. You generate a verification key that you take off of the system in question at the start and the verification key can be used to efficiently check any part of that series. During operation you sign the log segment you just wrote out on some regular interval and then ratchet the key forward and delete the old key in memory to where even if the system was completely compromised it no longer holds a key that could rewrite the previous log segment.
  - drdeca 6y ago
    There is something called an authenticated append only skip list, which I think is kinda neat. It is basically what it sounds like. Iirc it allows certificates showing that something has a particular place in the list, given the assumption of the latest thing added to it, in length at most logarithmic in the length of the list.
f-word 6y ago
How long until this is strategically murdered? I refuse to use Google products for critical infrastructure until they prove they won't kill the product as soon as they lose interest to chase the next shiny trinket or maybe build their 78th chat app
- jacques_chester 6y ago
  From my reading it's not a product or service.
skybrian 6y ago
This isn't obviously anything new. From the github repo, it looks like Google open-sourced the underlying implementation for certificate transparency a while back. [1] Any DNS registry will need something similar to this to participate. While in theory, anyone publishing public information might find something like this useful, it's not clear there's much demand for it outside DNS. Something like Dolt [2] seems like it would better for publishing public datasets in a way that changes can be tracked? [1] https://en.wikipedia.org/wiki/Certificate_Transparency https://en.wikipedia.org/wiki/Certificate_Transparency [2] https://www.dolthub.com/ https://www.dolthub.com/
- henryfjordan 6y ago
  Amazon offers QLDB which exists in a similar space (https://aws.amazon.com/qldb/ https://aws.amazon.com/qldb/). The target audience seems to be organizations with strict regulatory requirements who want to prove that data hasn't been tampered with since write. Useful for payment records, storing a log immutable events (patient 23 had an appointment today), stuff like that. The applications aren't endless, but they extend further than just DNS.
- jacques_chester 6y ago
  > This isn't obviously anything new. Conceptually, maybe not, given the history of Merkle trees and hash chains. But examples of production code using these ideas are few and far between. That's still valuable.
  - skybrian 6y ago
    Sorry, speaking loosely. I meant that this doesn't seem to be an announcement of a new open source repo. Certificate transparency itself has been in production for a while. Apparently since 2013 and required for all certificates since 2018, according to Wikipedia. Depending on how you define it, everyone who publishes source code using git is already using these ideas. It seems they are all Merkle trees? I would guess this code would be most useful when the logs are pretty big. If you can download the whole dataset (like with git) and you are making manual edits and sending pull requests, then Dolt's approach sounds more user-friendly? You get a change history, and if upstream rebases then you will see it. (I haven't used them; I just read their blog.)
nemo1618 6y ago
Russ Cox has a good blog post on this data structure: https://research.swtch.com/tlog https://research.swtch.com/tlog A similar data structure has been proposed as a cryptographic accumulator for the Bitcoin UTXO set: https://eprint.iacr.org/2019/611 https://eprint.iacr.org/2019/611 (Although in this case, the "log" is not append-only; elements can be deleted.)
deleted 6y ago
[deleted]
hardwaresofton 6y ago
If anyone wants to see how someone built this in production without any of the "we're building a movement, we have a fancy landing page" hype: Secure logging with syslog-ng Forward integrity and confidentiality of system logs @ FOSDEM 2020[0]. I'm starting to become really suspicious of things being pushed as standards/new approaches/things-that-should-be-rfcs-but-have-a-marketing-budget. As other posts have pointed out, an RFC for this already exists, and all I can see is Google trying to make another gRPC where new engineers hear the term "gRPC" before they hear and/or take the time to understand HTTP/2. [0]: https://www.youtube.com/watch?v=8uN4s_m7sno https://www.youtube.com/watch?v=8uN4s_m7sno
- deleted 6y ago
  [deleted]
krrrh 6y ago
I’ve said it for years, but straightforward approaches to signing logs and database dumps takes care of most problems blockchains are supposed to solve.
- strstr 6y ago
  I'm not totally sure those solve the problem this aims to solve. That's like saying that certificates solve the problem that certificate transparency solves. They are related, but not quite the same.
nexthash 6y ago
A cursory skim of the comments reveals that the problem being pushed by Google here seems to already have many existing solutions being discussed for adoption as a possible comprehensive standard. Out of curiosity, can somebody explain to me why Google would feel the need to push its own standard and throw up a sleek website/showcase instead of contributing to what is already out there?
- hackmiester 6y ago
  My best guess would be NIH. I try not to be pessimistic about Google but that's the best I've got.
cube2222 6y ago
Looks neat. I don’t understand one part though. Because checking for log integrity is fairly obvious and easy to understand (merkle trees). However, I don’t see how this creates a log that can’t be tampered with. If you change a record in a log, you have to change all records following it, in order to preserve integrity of hashes, but if that record has been stored recently, that wouldn’t be terribly hard. So where’s the magic that make this impossible? With bitcoin the magic is that mining hashes for a transaction block takes a lot of resources and the longest chain always wins. Here I don’t see anything of this kind. I'm definitely a layman as far as crypto is concerned, so take the above with a grain of salt. Looking for somebody more knowledgable about the topic to clear my confusion. EDIT: Looking at https://transparency.dev/verifiable-data-structures/ https://transparency.dev/verifiable-data-structures/ there's the part `Clients must store a copy of tree head hashes`, so that partly solves the problem I suppose. But aren't the clients (who I understand have to consume all produced records in order to continuously recalculate the root hash) then ripe for tampering?
- strstr 6y ago
  My impression is that this is more about publishing tree head hashes as a way of promising that you have nothing up your sleeve. You can't remove something after someone has depended on that value being there without someone noticing. The certificate transparency comparison is helpful. If it's append only, you should be able to find the old head in the log. Not sure if that is what it's going for though. I'm still a bit confused by this myself.
- droptical 6y ago
  I prefer to use the term "tamper-evident" when describing these things - you can totally fiddle with logs, but the property you likely want is that this can be detected. As you say, Merkle trees are fairly straight-forward, but beyond integrity checking a file they have some other nice properties - as the "operator" of a Merkle tree based log, you can efficiently [O(log N)] convince an observer that: - you've only grown the log by appending new entries since the last time they looked ("consistency proof") - a given entry they hold is indeed included in the log ("inclusion proof") if you change an entry in the log (or claim something is in the log when it's not) it becomes impossible for you to prove both of those properties (unless you're powerful enough to also break what's called the "second pre-image resistance" of the cryptographic hash you're using). Note that for these two properties, an observer doesn't need to download or inspect the full contents of the log, just a handful of hashes in the Merkle tree which they can then use to recreate the "tree head hash" you mentioned. These "tree heads" are the state they store and are just a few hundred bytes. There are generally a few types of log client: - one type is putting things into the log - one type are wanting to use what's stored in the log to make a decision of some kind ("should I trust this site", "should I install this binary", "am I seeing the true history of events", etc.) and they won't trust that data unless they are convinced it is in the log - another can verify the accuracy/validity/goodness of things in the log (e.g. in CT it's the domain owner who is in the unique position of saying "yes, I asked for this cert to be created", for binaries it might be "I'm the authorised creator of these binaries and, yup, that was me" or "I'm a respectable malware scanning company, and this binary doesn't match any known signatures", "I'm an auditor and these transactions are complete and correct", etc. - you can probably think of many more examples!) In this light, you can think of a tamper-evident log as being a sort of "reliable transport" to connect these different types of clients together, and importantly, where they all can prove to each other (using those light weight tree heads + consistency/inclusion proofs) that they're seeing the same set of data in the log - or, if they can't prove it - they have the cryptographic evidence of operator of the log operator having done something unexpected. If you have a spare few mins, have a look at the Claimant Model docs here: https://github.com/google/trillian/tree/master/docs/claimantmodel https://github.com/google/trillian/tree/master/docs/claimant... which talks in a bit more detail about this "transport" idea and the concept of discoverability which it brings. Hope that's helpful/interesting! [Disclaimer: I work on CT, Trillian, and a bunch of other related projects.]
supermatt 6y ago
This seems to be the same as guardtimes (patented) hash-calendar? https://patents.google.com/patent/US8312528 https://patents.google.com/patent/US8312528 I dont particularly agree with an obvious use of a merkle tree being patented in this way - but it is. Probably worthy of further research if you plan to use this.
- jacques_chester 6y ago
  IANA patent lawyer, but I am not sure this patent's claims would apply. It creates a sequence of the natural numbers and certificates for each number in the sequence. But the approach being outlined here doesn't rely on trustworthy sequential numbers at all. Put another way: this patent may cover some specific applications of Merkle trees to natural numbers, but doesn't cover all sequential data structures. For most purposes "happened-at" or "happens-before" relations are plenty useful and don't require sequence numbers to establish the relation.

106 points by philips 6y ago

We built a tamper evident log system for https content. The beta is over here: https://www.transparencylog.com/ https://www.transparencylog.com/ Or try out the CLI tool https://github.com/transparencylog/tl#installation https://github.com/transparencylog/tl#installation

arianvanp 6y ago
Heh; seems very similar to a project I've been working on :) github.com/arianvp/kpop.sh I'm happy to see my idea is not novel. That means I was on the right track :P
kevin_nisbet 6y ago
I've scanned through the work you've been doing on this a couple times, going back to trying to use letsencrypt / existing transparency logs. While its great stuff and really interesting, I wanted to point out the last time I looked at the current iteration I really struggled trying to understand how it worked, and as such how the security properties worked. Not meant to be criticism, just feedback, as it would be ideal to have some sort of transparency mechanism in common use.

cs702 6y ago

Couldn't we use, you know, git for the many applications that require a verifiable history of commits but don't need to be super fast or real-time?

dang 6y ago
"Don't be snarky." "Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html You may have a good point, but for it to be a good comment you would need to drop the snark and engage more specifically with the details of the article. The odds, for example, that the authors don't know about or have thought about git are basically zero.
- cs702 6y ago
  dang: I did not mean for my comment to be snarky! I also did not mean it to be dismissive! I meant it as an honest, obvious question one should ask. But in hindsight, in the light of morning, my comment sure looks snarky, you're right. I wrote it quickly last night. Argh. Sorry. And thank you for taking the time to point it out. philips: please accept my apologies too. The last thing I want to be is snarky.
  - dang 6y ago
    It happens! Objects in the mirror are closer than they appear, etc. :) Thanks for the kind reply!
justincormack 6y ago
Git has an issue that branch heads are mutable, and unsigned, so two repos can disagree about what is head with the same commits in them. Using a transparency log to record changes in heads is like forcing no fast forwards and signing each change in heads.
- cs702 6y ago
  Thanks for the clear explanation. That makes sense.

throw0101a 6y ago

RFC 5848, "Signed Syslog Messages": > This document describes a mechanism to add origin authentication, message integrity, replay resistance, message sequencing, and detection of missing messages to the transmitted syslog messages. This specification is intended to be used in conjunction with the work defined in RFC 5424, "The Syslog Protocol". * https://tools.ietf.org/html/rfc5848 https://tools.ietf.org/html/rfc5848

deathanatos 6y ago
Every time I've seen syslog in the wild, it's been the old "BSD" version (RFC 3164), not the newer RFC 5424 version. And pretty much any newer format, even something basic like JSON-lines over TCP, is going to be nicer to work with, IMO. (Though I admit, I have no idea how I'd even begin to start signing messages with JSON-lines.)
- peteretep 6y ago
  Got to believe most JSON parsers can be set to permissive mode to allow comments, and then you could just append `//signature` on to the end of each JSON line?
  - throw0101a 6y ago
    Or you can simply STRUCTURED-DATA of RFC 5424 (§6.3) and put the signature into JSON proper as outlined in RFC 5428 § 4.2.9 (example): 2009-05-03T14:00:39.529966+02:00 host.example.org syslogd 2138 - [ssign VER="0111" RSID="1" SG="0" SPRI="0" GBC="2" FMN="1" CNT="7" HB="K6wzcombEvKJ+UTMcn9bPryAeaU= zrkDcIeaDluypaPCY8WWzwHpPok= zgrWOdpx16ADc7UmckyIFY53icE= XfopJ+S8/hODapiBBCgVQaLqBKg= J67gKMFl/OauTC20ibbydwIlJC8= M5GziVgB6KPY3ERU1HXdSi2vtdw= Wxd/lU7uG/ipEYT9xeqnsfohyH0=" SIGN="AKBbX4J7QkrwuwdbV7Taujk2lvOf8gCgC62We1QYfnrNHz7FzAvdySuMyfM="] You're trying to re-invent the wheel. Look at the prior art.
- throw0101a 6y ago
  The STRUCTURED-DATA of RFC 5424 is basically JSON: > [exampleSDID@32473 iut="3" eventSource="Application" eventID="1011"][examplePriority@32473 class="high"] * https://tools.ietf.org/html/rfc5424#section-6.3 https://tools.ietf.org/html/rfc5424#section-6.3

keyle 6y ago

Sorry I read the page and I found it very vague. Pretty graphics and lot of white space for not much meat. Basically, looks like the command pattern implemented with signed token for every time you read, you must mutate the 'chain' or array of information. Am I close?

owenmarshall 6y ago
C-f Merkle It took quite a bit of time to get there. https://en.m.wikipedia.org/wiki/Merkle_tree https://en.m.wikipedia.org/wiki/Merkle_tree
droptical 6y ago
Many thanks for the feedback on the site, perhaps we need to get some more dense technical details either on there directly or adding to the existing docs on the github repo. Command pattern is definitely one pattern we've seen these tamper-evident logs applied to; you can easily imagine a system where, say, config update "commands" are packaged off and written to a TE log, and then workers apply those commands to a system if and only if they are convinced that the commands were properly logged. If the admins/command-workers/auditors etc. can all prove they're looking at the same set of logged commands (which is the property that these tamper-evident logs are intended to provide), then you have a reliable and tamper-evident audit trail of all changes to your system. There are a bunch of other scenarios we think these things might be useful for too, and we're trying to explore (and help others explore) these and provide mechanisms for reasoning about the properties of such systems. [Disclaimer: I work on CT, Trillian, and other related projects]
- jacques_chester 6y ago
  > Command pattern is definitely one pattern we've seen these tamper-evident logs applied to; you can easily imagine a system where, say, config update "commands" are packaged off and written to a TE log, and then workers apply those commands to a system if and only if they are convinced that the commands were properly logged. Tip: call it LogOps and engage in an exercise-yard shiv-fight with GitOps folks. I prefer to think of both as examples of WAL or intent logs. It's a useful pattern and it's nice to have a narrowly-focused tool for it.

pram 6y ago

I’m sorry, but Trillian? That seems like a pretty major name collision with a well known piece of software that has been around for decades and has zero chance of getting displaced in search rankings lol

tylerchilds 6y ago
> has zero chance of getting displaced in search rankings unless this new product happens to be run by a company that controls a prominent search ranking algorithm
qwantim1 6y ago
In addition to an IM client, it was a character in HGTTG by Douglas Adams.

cocktailpeanuts 6y ago

Maybe I'm missing something, but there is already the term "append only logs" which we use everywhere. How is this different from append only logs? Append only logs rely on cryptography to make the history transparent too. I skimmed through the website but couldn't find a distinction. Also, the website format is kinda weird. As I reach the bottom of the page, it looks like this is a promotional site for Trillian. Maybe the confusion comes from here. What is this site really about?

tleb_ 6y ago
What cryptography are you referring to when talking about append-only logs? To me, an AOL is just a list of records that has a single operation, append. It could be implemented as a file that is only opened in append mode, multiple files (eg logrotate), a lib that works in memory, a process that exposes an API, etc. I don't see any cryptography here.
- MertsA 6y ago
  In general, yes, an append only log might be weakly "append only". If you want a cryptographic approach look at how forward secure sealing works with systemd. Basically you make a cryptographic ratchet on the system doing the logging such that given some arbitrary key you can find out what the next key is but not the previous one. You generate a verification key that you take off of the system in question at the start and the verification key can be used to efficiently check any part of that series. During operation you sign the log segment you just wrote out on some regular interval and then ratchet the key forward and delete the old key in memory to where even if the system was completely compromised it no longer holds a key that could rewrite the previous log segment.
- drdeca 6y ago
  There is something called an authenticated append only skip list, which I think is kinda neat. It is basically what it sounds like. Iirc it allows certificates showing that something has a particular place in the list, given the assumption of the latest thing added to it, in length at most logarithmic in the length of the list.

f-word 6y ago

How long until this is strategically murdered? I refuse to use Google products for critical infrastructure until they prove they won't kill the product as soon as they lose interest to chase the next shiny trinket or maybe build their 78th chat app

jacques_chester 6y ago
From my reading it's not a product or service.

skybrian 6y ago

This isn't obviously anything new. From the github repo, it looks like Google open-sourced the underlying implementation for certificate transparency a while back. [1] Any DNS registry will need something similar to this to participate. While in theory, anyone publishing public information might find something like this useful, it's not clear there's much demand for it outside DNS. Something like Dolt [2] seems like it would better for publishing public datasets in a way that changes can be tracked? [1] https://en.wikipedia.org/wiki/Certificate_Transparency https://en.wikipedia.org/wiki/Certificate_Transparency [2] https://www.dolthub.com/ https://www.dolthub.com/

henryfjordan 6y ago
Amazon offers QLDB which exists in a similar space (https://aws.amazon.com/qldb/ https://aws.amazon.com/qldb/). The target audience seems to be organizations with strict regulatory requirements who want to prove that data hasn't been tampered with since write. Useful for payment records, storing a log immutable events (patient 23 had an appointment today), stuff like that. The applications aren't endless, but they extend further than just DNS.
jacques_chester 6y ago
> This isn't obviously anything new. Conceptually, maybe not, given the history of Merkle trees and hash chains. But examples of production code using these ideas are few and far between. That's still valuable.
- skybrian 6y ago
  Sorry, speaking loosely. I meant that this doesn't seem to be an announcement of a new open source repo. Certificate transparency itself has been in production for a while. Apparently since 2013 and required for all certificates since 2018, according to Wikipedia. Depending on how you define it, everyone who publishes source code using git is already using these ideas. It seems they are all Merkle trees? I would guess this code would be most useful when the logs are pretty big. If you can download the whole dataset (like with git) and you are making manual edits and sending pull requests, then Dolt's approach sounds more user-friendly? You get a change history, and if upstream rebases then you will see it. (I haven't used them; I just read their blog.)

nemo1618 6y ago

Russ Cox has a good blog post on this data structure: https://research.swtch.com/tlog https://research.swtch.com/tlog A similar data structure has been proposed as a cryptographic accumulator for the Bitcoin UTXO set: https://eprint.iacr.org/2019/611 https://eprint.iacr.org/2019/611 (Although in this case, the "log" is not append-only; elements can be deleted.)

deleted 6y ago

[deleted]

hardwaresofton 6y ago

If anyone wants to see how someone built this in production without any of the "we're building a movement, we have a fancy landing page" hype: Secure logging with syslog-ng Forward integrity and confidentiality of system logs @ FOSDEM 2020[0]. I'm starting to become really suspicious of things being pushed as standards/new approaches/things-that-should-be-rfcs-but-have-a-marketing-budget. As other posts have pointed out, an RFC for this already exists, and all I can see is Google trying to make another gRPC where new engineers hear the term "gRPC" before they hear and/or take the time to understand HTTP/2. [0]: https://www.youtube.com/watch?v=8uN4s_m7sno https://www.youtube.com/watch?v=8uN4s_m7sno

deleted 6y ago
[deleted]

krrrh 6y ago

I’ve said it for years, but straightforward approaches to signing logs and database dumps takes care of most problems blockchains are supposed to solve.

strstr 6y ago
I'm not totally sure those solve the problem this aims to solve. That's like saying that certificates solve the problem that certificate transparency solves. They are related, but not quite the same.

nexthash 6y ago

A cursory skim of the comments reveals that the problem being pushed by Google here seems to already have many existing solutions being discussed for adoption as a possible comprehensive standard. Out of curiosity, can somebody explain to me why Google would feel the need to push its own standard and throw up a sleek website/showcase instead of contributing to what is already out there?

hackmiester 6y ago
My best guess would be NIH. I try not to be pessimistic about Google but that's the best I've got.

cube2222 6y ago

Looks neat. I don’t understand one part though. Because checking for log integrity is fairly obvious and easy to understand (merkle trees). However, I don’t see how this creates a log that can’t be tampered with. If you change a record in a log, you have to change all records following it, in order to preserve integrity of hashes, but if that record has been stored recently, that wouldn’t be terribly hard. So where’s the magic that make this impossible? With bitcoin the magic is that mining hashes for a transaction block takes a lot of resources and the longest chain always wins. Here I don’t see anything of this kind. I'm definitely a layman as far as crypto is concerned, so take the above with a grain of salt. Looking for somebody more knowledgable about the topic to clear my confusion. EDIT: Looking at https://transparency.dev/verifiable-data-structures/ https://transparency.dev/verifiable-data-structures/ there's the part `Clients must store a copy of tree head hashes`, so that partly solves the problem I suppose. But aren't the clients (who I understand have to consume all produced records in order to continuously recalculate the root hash) then ripe for tampering?

strstr 6y ago
My impression is that this is more about publishing tree head hashes as a way of promising that you have nothing up your sleeve. You can't remove something after someone has depended on that value being there without someone noticing. The certificate transparency comparison is helpful. If it's append only, you should be able to find the old head in the log. Not sure if that is what it's going for though. I'm still a bit confused by this myself.
droptical 6y ago
I prefer to use the term "tamper-evident" when describing these things - you can totally fiddle with logs, but the property you likely want is that this can be detected. As you say, Merkle trees are fairly straight-forward, but beyond integrity checking a file they have some other nice properties - as the "operator" of a Merkle tree based log, you can efficiently [O(log N)] convince an observer that: - you've only grown the log by appending new entries since the last time they looked ("consistency proof") - a given entry they hold is indeed included in the log ("inclusion proof") if you change an entry in the log (or claim something is in the log when it's not) it becomes impossible for you to prove both of those properties (unless you're powerful enough to also break what's called the "second pre-image resistance" of the cryptographic hash you're using). Note that for these two properties, an observer doesn't need to download or inspect the full contents of the log, just a handful of hashes in the Merkle tree which they can then use to recreate the "tree head hash" you mentioned. These "tree heads" are the state they store and are just a few hundred bytes. There are generally a few types of log client: - one type is putting things into the log - one type are wanting to use what's stored in the log to make a decision of some kind ("should I trust this site", "should I install this binary", "am I seeing the true history of events", etc.) and they won't trust that data unless they are convinced it is in the log - another can verify the accuracy/validity/goodness of things in the log (e.g. in CT it's the domain owner who is in the unique position of saying "yes, I asked for this cert to be created", for binaries it might be "I'm the authorised creator of these binaries and, yup, that was me" or "I'm a respectable malware scanning company, and this binary doesn't match any known signatures", "I'm an auditor and these transactions are complete and correct", etc. - you can probably think of many more examples!) In this light, you can think of a tamper-evident log as being a sort of "reliable transport" to connect these different types of clients together, and importantly, where they all can prove to each other (using those light weight tree heads + consistency/inclusion proofs) that they're seeing the same set of data in the log - or, if they can't prove it - they have the cryptographic evidence of operator of the log operator having done something unexpected. If you have a spare few mins, have a look at the Claimant Model docs here: https://github.com/google/trillian/tree/master/docs/claimantmodel https://github.com/google/trillian/tree/master/docs/claimant... which talks in a bit more detail about this "transport" idea and the concept of discoverability which it brings. Hope that's helpful/interesting! [Disclaimer: I work on CT, Trillian, and a bunch of other related projects.]

supermatt 6y ago

This seems to be the same as guardtimes (patented) hash-calendar? https://patents.google.com/patent/US8312528 https://patents.google.com/patent/US8312528 I dont particularly agree with an obvious use of a merkle tree being patented in this way - but it is. Probably worthy of further research if you plan to use this.

jacques_chester 6y ago
IANA patent lawyer, but I am not sure this patent's claims would apply. It creates a sequence of the natural numbers and certificates for each number in the sequence. But the approach being outlined here doesn't rely on trustworthy sequential numbers at all. Put another way: this patent may cover some specific applications of Merkle trees to natural numbers, but doesn't cover all sequential data structures. For most purposes "happened-at" or "happens-before" relations are plenty useful and don't require sequence numbers to establish the relation.