Implementing a Merkle Tree for an Immutable Verifiable Log | Hacker News Reader

Implementing a Merkle Tree for an Immutable Verifiable Log

aly.arriqaaq.com

147 pointseatonphil53 comments

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

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.)

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?

Ha sorry false friend during translation. Indexes. The covering indexes we use to store our triples (think RDF) are a (novel) form of adaptive radix trie. We handle hashes the same, recomputed for leaves, stored in inner nodes.

Have you looked at SIP or Highway hash? If you only use the hash as an implementation detail (as we do) without exposing it via an API you might not need the cryptographic strength of SHA. Both accept a key parameter which prevents attackers from crafting malicious datasets with bad worst-case performance characteristics or hash collisions, while having huge speedups over true cryptographic hash functions.

Funnily enough we do use bitsets heavily inside the trie to speed up set operations and joins between indexes.

The join algorithm is actually very similar to how ECS engines like Legion compute the components relevant to their entities.

There's a new variant called the HOT (height optimized trie) to improve over ART :) but really nice, didn't know of SIP or highway hash, but I wanted to prevent collisions as There's also a diff algorithm, which compares revisions (that said we now also store the type of change, plus the context nodes and the root of the change in a simple JSON file -- so changes are tracked, too).

The data in SirixDB is always indexed by a 64bit int whereas the upper 10 bits denote the position of the node in the page. I've also used different node sizes as in an ART and I'm using a bitset, too in a new node type.

Don't you have to join the data stored in the ART itself? Trying to understand why and how you join index pages :-)

Yeah we actually are much closer to the "old" ART than using the disciminating bit aproach of HOT.

Hot is a more complex data structure with a less deterministic structure which makes it less suited for set operations defined over it and makes it difficult to store the hashes of subtrees in the nodes, also it is not really suited for covering indices from what I can see.

The original ART is not a covering either because of their optimistic infix compression, but it's really easy to make it covering.

We also have the goal of being really "simple" in terms of moving parts, and "easy" in terms of implementation.

Our adaptiveness is not based on different node types but based on a single node type that comes in different sizes and uses perfect-consistent-locality-sensitive-cuckoo-hashing (yeah it's a mouthfull ^^'). We call the thing Persistent Adaptive Cuckoo Trie, or PACT (as in pact with the devil) for short.

The idea is that because of the 256-fanout, we can fine tune our hash functions, to be perfect and collision free, to preserve locality so that two adjacent byte keys will go into the same bucket, and to be consistent on resize, so that doubling the node size only requires a memcpy of the lower half of the new bucket array into the upper half (memory which needs to be initialised anyways, so we get the grow for free modulo reallocation overhead).

This not only saves us costly rehasing but also makes the implementation much simpler.

We figured if we want to build a competitor to RDF it better be implementable by anybody during a hackathon.

The binary triples (Tribles, get it?) that we store are 16byte unique entity id, 16byte unique attribute id, and 32byte value.

We don't do surrogate keys, to not only simplify the implementation and reduce latency, but to also be able to do range and limit queries from the primary indexes directly.

Because we store triples materializing all pssible indexes over our tables (3! + 3) is actually feasible. This allows us to create a worst case optimal join algorithm that is completely skew resistant.

We're currently working on adding minhash heuristics into the PACT to always pic the optimal variable order for constraint propagation which should make things instance optimal (a first to our knowledge).

So yeah basically the idea is to have a immutable in-memory knowledge base that is amortized O(1) for everything. I.e. you pay per inserted element but not by how much was already inserted, you pay proportional to the size of the intersection of the operands for set ops and not propertional to sum of the operands, you pay proportional to your result size for a query and not propertional to the size of the data queried.

We also have a (still very stealthy) discord channel if you'd like to chat some more about this stuff at discord.gg/tribles :D

Oh that's what you described in your first reply.

Just out of curiosity, what language is this? I don’t recognise it at all.

Basically JSONiq, with a few minor syntax differences.

Our query engine/compiler is and can be used by other data stores as well:

http://brackit.io

Interesting, thanks! I hadn’t heard of that one.

Give it a try ;)

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.

What do you think your git repo is?

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.

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.

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.

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.

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.

Nope, they even suggest (and companies have built tooling around) deleting versions of the tags.

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.

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.

I agree; there should be more protections and I'm pointing out that they could be offered. Github could certainly enforce at the platform level that the only tags allowed for use in Actions must be annotated, maybe even signed, and must never be force-pushed.

The use of tags isn't necessarily the wrong strategy: I'm mostly just pointing out it is treating tags as mutably as branches that is the problem. I don't think you should ever force push a tag, personally, and I always find it problematic when people treat tags like branches and confuse the two.

Indeed, all the actions tell you to use them via tags.

And then GitHub comes and recommends you (in a doc that you're unlikely to find unless you know to look for it) to use SHAs to protect yourself from the attack that they themselves enabled.

https://docs.github.com/en/actions/security-guides/security-...

Yeah this is all kind of lazy glue code. The same thing happens with Docker; people refer to foobar:latest, and that changes over time and is annoying/a good attack vector. (All the tags are mutable, of course, not just "latest".) What should happen in both cases is that "v3" or "latest" should be read at the time you submit the configuration and stored as the unique id (commit id for git, sha256 for container images). This does have the downside that you have to check that "v3" and "latest" are still what you want every time you apply an edit to the action, but at least you were tangentially involved rather than pure action at a distance.

There are vendors that I would be fine pinning to a vendors signature instead, but yeah. There is, thankfully, a lot of kubernetes tooling around this workflow

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.

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.

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.

I know that at least RubyGems, NPM, PyPI and Maven Central are in various stages of using Sigstore for signing and transparent logging.

> 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."?

“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.

there is also https://aws.amazon.com/qldb/ Thoses tech make blockchain obscolete for many uses.

Isn't QLDB a blockchain tech? Albeit a real-world practical one.

It is not it seems https://aws.amazon.com/qldb/faqs/#:~:text=Amazon%20QLDB%20ca....

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.

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.

It could be a blockchain, we don't know for sure

It is by the original definition. Though not by some of the recent redefinitions but as they are often due to marketing getting good of the dictionary...

Yes could be. We should point out that QLDB isn’t open source and only runs as an AWS service.

Or Git. Or...

This is a common pattern now.

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

A blockchain is a merkle tree with a distributed consensus algorithm.

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.

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.

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.

Most Git commits (almost all non-merge commits) only point to one other commit (node, whatever) and that still forms a tree of branches naturally. Rebase is a "consensus algorithm" that some need in git to keep their commits a straight line. On a single machine a blockchain consensus algorithm is nearly indistinguishable from "rebase" and yeah doesn't "feel like you need a consensus algorithm". That doesn't mean there isn't a consensus algorithm.

Multiple different heads is a tree. Multiple forks is very much a tree. I think it is Blockchain proponents that are overcomplicating things and bending over backwards to describe their Merkle trees as non-tree as possible.

Think the main confusion going on here is that people do not think of tree as lists, even if they could be 100% represented as such.

It's early so could you help me out by showing how to represent say this[1] tree as a list?

Or did you just mean you can store the nodes in an array and index them by level? In that case I wouldn't call it a list.

[1]: https://en.wikipedia.org/wiki/B-tree#/media/File:B-tree.svg

There is no token/currency associated to it, and it's made for a single specific purpose only, compared to most blockchains which try to run programs, manage wallets, etc. It also doesn't have a decentralized consensus algorithm, nor is there a gossip network to inform about new transactions that are to be added to the log. It's centralized per design.

Which of these differences you see as important to the blockchain / non-blockchain distinction, depends on the precise definition for blockchain that you want to use.

That being said, even the CT website uses the term "ledger" to explain what the logs are: https://certificate.transparency.dev/howctworks/

The term "ledger" pre-dates crypto. An append-only log is a ledger if the writers are trusted.

A blockchain provides a guarantee of (statisical eventual) write availability, since anyone can mine new blocks (eventually). A verifiable log only accepts new entries from a limited, generally closed set of writers (usually just one), and you can only add new entries by going through one of those writers. (Blockchains also tend to have better read availability due to being more widely distributed, but there's no reason why you couldn't destribute a verifiable log that widely, it just tends not to happen in practice.)

This makes a verifiable log unsuitable for financial purposes since a adversary with lead pipe capabilities (or corrupt judge capabilities as the case may be) can block undesirable transactions at a single (or few) point of failure, whereas against a blockchain they'd have to target anyone with significant compute capacity.

On the other hand, verifiable logs don't need proof of work/stake/etc to limit hostile forking, so if the log is describing things rather than acting a ground source of truth (so you can just ignore it if it starts refusing writes), it's much more efficient than a blockchain.

None of those things are features of blockchains, they are all features of cryptocurrencies.

Blockchains refer to any time you use a chain of hashes to prove a block of data and any data that came before it, has not been mutated.

The time keeper service that takes out classified ads in the new york times with hash blocks for the documents they timestamped to prove they were timestamped before a certain date, is a blockchain, because they include the previous day's hash.

Git, is a blockchain.

It's just hashes all the way down.

The random entropy driver in linux, is technically a blockchain, with how it works.

As others have pointed out: very little is different. Depending on if you include consensus in your use of "blockchain", there may be no difference whatsoever.

Currently it's a massively popular buzzword that frequently means very little in reality. It's just being tacked onto everything whether or not it makes sense because e.g. the Long Island Iced Tea company switched their name to "Long Blockchain" and immediately had massive stock gains: https://arstechnica.com/tech-policy/2017/12/iced-tea-company... . Even in the cases where it is technically accurate, it's rarely a good or useful idea... but it helps get funding.

So in practice, "blockchain" currently means "you will magically get rich". Technically it's almost always a Merkle tree, or a less efficient structure (e.g. Bitcoin's core "chain" is basically a linear version, which is dramatically less efficient to verify to the root for any given block... because it doesn't need that quality. Though it also uses Merkle trees within each block).

Reply on news.ycombinator.com