55 ms·

Implementing a Merkle Tree for an Immutable Verifiable Log

147 points by eatonphil 5y ago

skybrian 5y ago
I knew that Go had a checksum database but not that it had a tamper-proof log. This seems like something that other package management systems should do as well.
- gumby 5y ago
  What do you think your git repo is?
  - colburnmh 5y ago
    True to an extent--meaning mostly true in practice. You can mutate the Git data if you chose to using commands like "filter-branch". "filter-branch" isn't used frequently, since it causes issues with every up/down-stream replica if the data has been pushed/pulled, but it is possible. But, even some commonly used commands like "amend", "rebase", and "squash" cause limited data mutations which are broadly considered appropriate and useful.
    - tylorr 5y ago
      Those all generate new commits, they don't modify existing ones. Though the only way of easily detecting that is comparing it to a clone of the repo.
    - kjeetgill 5y ago
      This is kind of the brilliance of git forcing users to refer to commits by hashes, all the things you're referring to don't modify commits, they make new ones. Braches are the the only mutable place where you have it point to different commits in a sequence. I could imagine in some horrific alternate universe someone deciding to hide hashes as not user friendly. Like, I think we got incredibly lucky how that played out.
      - GauntletWizard 5y ago
        You can experience this alternate universe right now in Github Actions, which allows you to refer to other "Actions" by their tag, and encourages you to pin yourself to a "v3" which the team will then destroy and replace to update you. If this sounds terrible, insecure, and begging to be exploited, it's because every idiot on the Github Actions Team should be censured for their poor understanding of Git, Github, and yet proceeding to ship anyway.
        hermanb 5y ago
        I’ve been wondering about this too and always used full sha’s until now. But recently I’ve made an action myself: You actually need to publish the action to the marketplace with each tag manually. It feels like there might be more going on. Is GitHub storing those published tags and avoiding tampering by only letting you use those tags once? Are they warning or blocking runs if you tamper? … I’m really curious because it seems like SUCH a giant risk otherwise.
        GauntletWizard 5y ago
        Nope, they even suggest (and companies have built tooling around) deleting versions of the tags.
        WorldMaker 5y ago
        Deleting a tag is a force push operation like any other and repo policies that block force pushes will block tag updates. Tags themselves aren't necessarily the worst idea, but yes policies encouraging force pushes are likely to experience exploitation. Also, annotated tags have their own "commit" hashes, and can be code signed like any other commit. There are more precautions that could be taken.
        Arnavion 5y ago
        When the threat is an action repo becoming malicious and force-pushing its existing tags to malicious code, the policies of the action repo preventing force-pushes is not a safeguard.
    - tylersmith 5y ago
      You can always create new trees by commiting or rebasing but absent being able to find a proper hash collision you can't change content within a given commit hash.
    - cryptonector 5y ago
      Uhm, you can mutate any Merkle hash tree / log you want, provided you can replace the copies of the past that others store. Correspondingly, the security of a Merkle hash tree / blockchain depends on having others store copies of it and check that additions chain from their past heads. Git, of course, lets you "mutate" the Merkle hash tree[0], but -to the extent that the hash function used allows- your rewriting of published branch history will be detected by others. (Those others can recover by reviewing the deltas and using `git rebase --onto`.) There's no Merkle-hash-tree-defeating code in Git as such because this is a generic issue for Merkle hash trees, not a Git-specific one. And to be clear: there is nothing wrong with `git rebase` and "rEwRiTiNg HiStOry" as long as you're not rewriting published history. And for those times when you must rewrite published history (for whatever reason), you can recover forks with `git rebase --onto`. The idea that "oh no!!1! Git lets you rewrite history, that's baaad and you shouldn't ever ever do that!!" is a terrible canard that must be called out as such every time it comes up. Mercurial does too. It's not really a problem unless you rewrite published history, but the vast majority of the time any user rewrites Git (or Mercurial, or...) history, they're doing so locally, on dev branches, not on published trunks. I think the history-rewrite-is-always-bad meme must have been started by people who hated Git or who just didn't understand. But it's a very destructive meme that causes people to be happy pushing and accepting ugly and useless history because "you don't want to ever fix it". That meme must be defeated. [0] Well, Git doesn't let you mutate the objects in the tree itself, it only lets you add or remove objects, and it lets you change the commits pointed to by branches, tags, and other symbolic refs.
  - skybrian 5y ago
    How often do packages refer to their dependencies using git hashes? Very seldom in my experience, and for good reason. (Unless you're using git submodules, which is not the usual way.) Go's checksum server does something different by making sure that the names used in module files refer to the same things for different people. Also, it works even if some packages don't come from git repos.
- jacques_chester 5y ago
  I know that at least RubyGems, NPM, PyPI and Maven Central are in various stages of using Sigstore for signing and transparent logging.
TedDoesntTalk 5y ago
How is this different from a blockchain (serious question)?
- greiskul 5y ago
  A blockchain is a merkle tree with a distributed consensus algorithm.
  - deleted 5y ago
    [deleted]
  - charcircuit 5y ago
    A blockchain is just a data structure. A consensus algorithm can agree what the current state / last block of a block chain is, but they are separate. Similarly if one says B tree or LSM tree that doesn't mean they are also talking about a consensus algorithm.
    - WorldMaker 5y ago
      The only thing that keeps a blockchain appearing to be a rebase-only straight line and not an otherwise ordinary merkle tree is the consensus algorithm on what the "current state / last block of the chain" is. The difference between a blockchain and a merkle tree in no way resembles that between a B tree or LSM tree. It's closer to the difference between a Binary Search Tree and a Red/Black Tree. They are both Binary Search trees and most operations are the exact same, but Red/Black Trees have an extra "color" attribute and rely on that for a better balancing algorithm than the "default" BST algorithm.
      - charcircuit 5y ago
        I think you are over complicating things. A blockchain is just a linked list with content addressed next pointers. You don't need a distributed system to use it. When on a single machine you don't need a consensus algorithm to agree on what the head of the list is. Even if you have multiple different heads none of them will be a tree. A node can only ever point to 1 other node.
jaboutboul 5y ago
“Recently I'd been reading on the application of immutable databases for tracking changes in sensitive data, and for auditing purposes.” Pretty sure he is referring to https://immudb.io https://immudb.io.
- SemanticStrengh 5y ago
  there is also https://aws.amazon.com/qldb/ https://aws.amazon.com/qldb/ Thoses tech make blockchain obscolete for many uses.
  - losteric 5y ago
    Isn't QLDB a blockchain tech? Albeit a real-world practical one.
    - SemanticStrengh 5y ago
      It is not it seems https://aws.amazon.com/qldb/faqs/#:~:text=Amazon%20QLDB%20can,multi%2Dparty%20consensus https://aws.amazon.com/qldb/faqs/#:~:text=Amazon%20QLDB%20ca....
    - jaboutboul 5y ago
      It’s not a blockchain. It’s meant to be a ledger database so it works in a similar way to a Blockchain, same internal data structure, but without the distributed consensus concept.
      - dspillett 5y ago
        So it is a blockchain, just not a distributed blockchain. The idea of a blockchain for tamper detection, with external validation by regularly sending off a current state hash for signing, existed long before crypto currencies arrived with the distributed verification process.
        SemanticStrengh 5y ago
lichtenberger 5y ago
We're also storing a similar hash tree (a hash is stored in each node -- an insert/update/delete triggers a recomputation of the hash in all ancestor nodes) to verify if a subtree has changed in SirixDB[1]. However, only pointers to neighbour nodes as well as the content is used for recomputation of the ancestor hashes instead of all children during updates. Furthermore checksums of child page-fragments are stored in parent references. The hashes are used for fast diff calculations along with an optional DeweyID node scheme to quickly get diffs in a resource in preorder or to check if a subtree has changed without fetching all ancestor nodes (due to the stored DeweyIDs). For instance you can simply check for updates of a node in a JSON structure with the following query: let $node := jn:doc('mycol.jn','mydoc.jn')=>fieldName[[1]] let $result := for $node-in-rev in jn:all-times($node) return if ((not(exists(jn:previous($node-in-rev)))) or (sdb:hash($node-in-rev) ne sdb:hash(jn:previous($node-in-rev)))) then $node-in-rev else () return [ for $jsonItem in $result return { "node": $jsonItem, "revision": sdb:revision($jsonItem) } ] It iterates through all revisions of a node and returns the node and the revision (and we could also add the author) when it has been updated. To make this even easier I could write a native Java function for use in the query. [1] https://sirix.io https://sirix.io
- j-pb 5y ago
  We do something similar to accelerate set operations over the indices of our in-memory immutable binary triple store. Since our indices are sets, we only have to compute the hashes for the leaves and can then combine them via XOR in our inner nodes. Due to the self inverse nature of XOR we can then efficiently maintain them over the operations. Normally this would be a big no no, but since we are using sets, we have the invariant that hashes will never be the same for two different leaves. (Under the assumption of no hash collisions, which is justified for the 128bit SipHash that we use.)
  - lichtenberger 5y ago
    I'm using a rolling hash with SHA265 but only take 128 bits, as it should be enough to avoid collisions. Leaf node hashes are computed on demand, only inner node hashes are stored persistently. Can you elaborate a bit more? You mean bitset indexes?
londons_explore 5y ago
> By using a tamper-evident to store compliance records, you can keep them in one place and simplify presenting them to an auditor. You can cryptographically prove they haven't been tampered with. Is this realistically the case? Won't most auditors instead say "Microsoft Access with a password is fine. But your homegrown cryptographic black box we can't trust."?

147 points by eatonphil 5y ago

I knew that Go had a checksum database but not that it had a tamper-proof log. This seems like something that other package management systems should do as well.

gumby 5y ago
What do you think your git repo is?
- colburnmh 5y ago
  True to an extent--meaning mostly true in practice. You can mutate the Git data if you chose to using commands like "filter-branch". "filter-branch" isn't used frequently, since it causes issues with every up/down-stream replica if the data has been pushed/pulled, but it is possible. But, even some commonly used commands like "amend", "rebase", and "squash" cause limited data mutations which are broadly considered appropriate and useful.
  - tylorr 5y ago
    Those all generate new commits, they don't modify existing ones. Though the only way of easily detecting that is comparing it to a clone of the repo.
  - kjeetgill 5y ago
    This is kind of the brilliance of git forcing users to refer to commits by hashes, all the things you're referring to don't modify commits, they make new ones. Braches are the the only mutable place where you have it point to different commits in a sequence. I could imagine in some horrific alternate universe someone deciding to hide hashes as not user friendly. Like, I think we got incredibly lucky how that played out.
    - GauntletWizard 5y ago
      You can experience this alternate universe right now in Github Actions, which allows you to refer to other "Actions" by their tag, and encourages you to pin yourself to a "v3" which the team will then destroy and replace to update you. If this sounds terrible, insecure, and begging to be exploited, it's because every idiot on the Github Actions Team should be censured for their poor understanding of Git, Github, and yet proceeding to ship anyway.
      - hermanb 5y ago
        I’ve been wondering about this too and always used full sha’s until now. But recently I’ve made an action myself: You actually need to publish the action to the marketplace with each tag manually. It feels like there might be more going on. Is GitHub storing those published tags and avoiding tampering by only letting you use those tags once? Are they warning or blocking runs if you tamper? … I’m really curious because it seems like SUCH a giant risk otherwise.
        GauntletWizard 5y ago
        Nope, they even suggest (and companies have built tooling around) deleting versions of the tags.
        WorldMaker 5y ago
        Deleting a tag is a force push operation like any other and repo policies that block force pushes will block tag updates. Tags themselves aren't necessarily the worst idea, but yes policies encouraging force pushes are likely to experience exploitation. Also, annotated tags have their own "commit" hashes, and can be code signed like any other commit. There are more precautions that could be taken.
        Arnavion 5y ago
        When the threat is an action repo becoming malicious and force-pushing its existing tags to malicious code, the policies of the action repo preventing force-pushes is not a safeguard.
  - tylersmith 5y ago
    You can always create new trees by commiting or rebasing but absent being able to find a proper hash collision you can't change content within a given commit hash.
  - cryptonector 5y ago
    Uhm, you can mutate any Merkle hash tree / log you want, provided you can replace the copies of the past that others store. Correspondingly, the security of a Merkle hash tree / blockchain depends on having others store copies of it and check that additions chain from their past heads. Git, of course, lets you "mutate" the Merkle hash tree[0], but -to the extent that the hash function used allows- your rewriting of published branch history will be detected by others. (Those others can recover by reviewing the deltas and using `git rebase --onto`.) There's no Merkle-hash-tree-defeating code in Git as such because this is a generic issue for Merkle hash trees, not a Git-specific one. And to be clear: there is nothing wrong with `git rebase` and "rEwRiTiNg HiStOry" as long as you're not rewriting published history. And for those times when you must rewrite published history (for whatever reason), you can recover forks with `git rebase --onto`. The idea that "oh no!!1! Git lets you rewrite history, that's baaad and you shouldn't ever ever do that!!" is a terrible canard that must be called out as such every time it comes up. Mercurial does too. It's not really a problem unless you rewrite published history, but the vast majority of the time any user rewrites Git (or Mercurial, or...) history, they're doing so locally, on dev branches, not on published trunks. I think the history-rewrite-is-always-bad meme must have been started by people who hated Git or who just didn't understand. But it's a very destructive meme that causes people to be happy pushing and accepting ugly and useless history because "you don't want to ever fix it". That meme must be defeated. [0] Well, Git doesn't let you mutate the objects in the tree itself, it only lets you add or remove objects, and it lets you change the commits pointed to by branches, tags, and other symbolic refs.
- skybrian 5y ago
  How often do packages refer to their dependencies using git hashes? Very seldom in my experience, and for good reason. (Unless you're using git submodules, which is not the usual way.) Go's checksum server does something different by making sure that the names used in module files refer to the same things for different people. Also, it works even if some packages don't come from git repos.
jacques_chester 5y ago
I know that at least RubyGems, NPM, PyPI and Maven Central are in various stages of using Sigstore for signing and transparent logging.

TedDoesntTalk 5y ago

How is this different from a blockchain (serious question)?

greiskul 5y ago
A blockchain is a merkle tree with a distributed consensus algorithm.
- deleted 5y ago
  [deleted]
- charcircuit 5y ago
  A blockchain is just a data structure. A consensus algorithm can agree what the current state / last block of a block chain is, but they are separate. Similarly if one says B tree or LSM tree that doesn't mean they are also talking about a consensus algorithm.
  - WorldMaker 5y ago
    The only thing that keeps a blockchain appearing to be a rebase-only straight line and not an otherwise ordinary merkle tree is the consensus algorithm on what the "current state / last block of the chain" is. The difference between a blockchain and a merkle tree in no way resembles that between a B tree or LSM tree. It's closer to the difference between a Binary Search Tree and a Red/Black Tree. They are both Binary Search trees and most operations are the exact same, but Red/Black Trees have an extra "color" attribute and rely on that for a better balancing algorithm than the "default" BST algorithm.
    - charcircuit 5y ago
      I think you are over complicating things. A blockchain is just a linked list with content addressed next pointers. You don't need a distributed system to use it. When on a single machine you don't need a consensus algorithm to agree on what the head of the list is. Even if you have multiple different heads none of them will be a tree. A node can only ever point to 1 other node.

jaboutboul 5y ago

“Recently I'd been reading on the application of immutable databases for tracking changes in sensitive data, and for auditing purposes.” Pretty sure he is referring to https://immudb.io https://immudb.io.

SemanticStrengh 5y ago
there is also https://aws.amazon.com/qldb/ https://aws.amazon.com/qldb/ Thoses tech make blockchain obscolete for many uses.
- losteric 5y ago
  Isn't QLDB a blockchain tech? Albeit a real-world practical one.
  - SemanticStrengh 5y ago
    It is not it seems https://aws.amazon.com/qldb/faqs/#:~:text=Amazon%20QLDB%20can,multi%2Dparty%20consensus https://aws.amazon.com/qldb/faqs/#:~:text=Amazon%20QLDB%20ca....
  - jaboutboul 5y ago
    It’s not a blockchain. It’s meant to be a ledger database so it works in a similar way to a Blockchain, same internal data structure, but without the distributed consensus concept.
    - dspillett 5y ago
      So it is a blockchain, just not a distributed blockchain. The idea of a blockchain for tamper detection, with external validation by regularly sending off a current state hash for signing, existed long before crypto currencies arrived with the distributed verification process.
      - SemanticStrengh 5y ago

lichtenberger 5y ago

We're also storing a similar hash tree (a hash is stored in each node -- an insert/update/delete triggers a recomputation of the hash in all ancestor nodes) to verify if a subtree has changed in SirixDB[1]. However, only pointers to neighbour nodes as well as the content is used for recomputation of the ancestor hashes instead of all children during updates. Furthermore checksums of child page-fragments are stored in parent references. The hashes are used for fast diff calculations along with an optional DeweyID node scheme to quickly get diffs in a resource in preorder or to check if a subtree has changed without fetching all ancestor nodes (due to the stored DeweyIDs). For instance you can simply check for updates of a node in a JSON structure with the following query: let $node := jn:doc('mycol.jn','mydoc.jn')=>fieldName[[1]] let $result := for $node-in-rev in jn:all-times($node) return if ((not(exists(jn:previous($node-in-rev)))) or (sdb:hash($node-in-rev) ne sdb:hash(jn:previous($node-in-rev)))) then $node-in-rev else () return [ for $jsonItem in $result return { "node": $jsonItem, "revision": sdb:revision($jsonItem) } ] It iterates through all revisions of a node and returns the node and the revision (and we could also add the author) when it has been updated. To make this even easier I could write a native Java function for use in the query. [1] https://sirix.io https://sirix.io

j-pb 5y ago
We do something similar to accelerate set operations over the indices of our in-memory immutable binary triple store. Since our indices are sets, we only have to compute the hashes for the leaves and can then combine them via XOR in our inner nodes. Due to the self inverse nature of XOR we can then efficiently maintain them over the operations. Normally this would be a big no no, but since we are using sets, we have the invariant that hashes will never be the same for two different leaves. (Under the assumption of no hash collisions, which is justified for the 128bit SipHash that we use.)
- lichtenberger 5y ago
  I'm using a rolling hash with SHA265 but only take 128 bits, as it should be enough to avoid collisions. Leaf node hashes are computed on demand, only inner node hashes are stored persistently. Can you elaborate a bit more? You mean bitset indexes?

londons_explore 5y ago

> By using a tamper-evident to store compliance records, you can keep them in one place and simplify presenting them to an auditor. You can cryptographically prove they haven't been tampered with. Is this realistically the case? Won't most auditors instead say "Microsoft Access with a password is fine. But your homegrown cryptographic black box we can't trust."?