# Can we do better than git's Merkle DAG?

- Channel: [ETHBerlin](https://streameth.org/ethberlin)
- Date: 2025-06-16
- Duration: 26:02
- Watch: https://streameth.org/watch/6854837f90bd41297bf7dac5

## Description

Git is 20 years old and git's Merkle DAG model is an established standard for decentralized systems. BitCoin and blockchains more or less follow in the footsteps. Same applies to the most of decentralized technology. The Replicated Data eXchange format aimed to overcome a number of pain points in that model, such as: accumulation of cryptographic sediment, coarse-grained-ness of data units, various inherent impedance mismatches and so on.
So, how is the progress?

## Transcript

So, basically, my name is Viktor Grishenko, this title has no affiliation, but I have a ton of formal affiliations. So I'm like chronologically ex-Bank of Russia, ex-Yandex, ex-I don't remember, a couple of years ago, but I remember, ah, crypto company, so basically, yes, basically I'm ex-many things. But mainly I'm a researcher, so this is about 10-15 years old, architecture of Merkle-Zach, which is basically used everywhere these days. Oh, another entertaining nonsense about me is that my birthday is 6th of April, which is according to Wikipedia, is birthday of Satoshi Nakamoto. And for that reason I'm having a difficult life. Because some people believe I have money to spare. And some people, I mean, like, some really bad people. So, why do I think... One second. It only affects the small screen. Ah, ok, ok, ok. So, what else should I say? I just returned from Japan. It was quite a nice trip. I planned it, like, south to north to follow the wave of Sakura Blossom. Because it depends on the, how to say it, geography. It was quite nice. Yeah. Let's start. Hello. As you already heard, Victor is a long-time veteran CRDT researcher, and he's here to talk about, should we be improving upon a 20-year-old... Well, I'll let him explain. He's already up to speed. Go ahead. Thank you, thank you. There's also the QR code. So, we all know this diagram. This is a diagram of, I don't know, maybe blocks in a blockchain or maybe commits in  The reference back using hashes. Actually, this cannot be a blockchain because obviously it is a DAG and not a chain. Yeah, so this must be Git. Yeah. So, we all know this architecture. It is everywhere, but the idea is, like, what is the problem? I mean, we can, everybody can go into their .git folder and subfolder objects to look how it looks, like, how to say, technically. There is a block explorer site to see those blockchain blocks of different blockchains. So, we all know this architecture. What are the upsides of this architecture? Obviously, all the data is covered by one hash, so we have, like, bit-precise fidelity that all the data is the right data. That is the breakthrough. Because revision control systems before Git, they didn't have that feature. So, in theory, you can hack the servers and adjust some source code and introduce some vulnerabilities, for example. And second, you can reliably sync it incrementally. You can download new blocks which you don't have, check their hashes, check their point to the right history, and that way it's synchronized to the rest of the system. Bit-precise. That is a good part. What are the not-good parts? I mean, we have, like, 15 years to understand what kind of problems can we have with this architecture. First of all, it is accumulation of no longer relevant history. For example, Git rep is humongous, it has, like, history back to the first commit, which most of the users, 99.99%, probably never need, actually. Same applies to all the big blockchains. It has history to the beginning of time. Well, in many cases. Some managed to trim it. Then the other problem, accumulation of suits or cryptographic sediments. These are hashes and signatures which are no longer meaningful, but still we keep them because they affect the resulting hash and the resulting signature. For example, if the same party is signing the blockchain, like, 100 times, only the last signature is significant because all the previous signatures, they sign, basically, the subset of the data with the same key. So, the value is basically zero, but we keep them around because they affect the resulting hash. So, these are the problems. And finally, blockchain is a lock of changes. The basic model for all distributed databases, data systems, data synchronization is a replicated state machine. We have some deterministic state machine. We apply same ops in exactly the same order, and we have the same state of the machine on all the replicas. That is the basic idea from the 80s, actually, until the 70s. Well, in the case of blockchain, we take essentially a database, make it decentralized by splitting it into a state and a lock, and the lock we make into an actual blockchain. We hash and sign it, the lock. And the state we derive from the lock, same as in the original model from the 70s. But we don't actually, in most of the cases, we don't actually verify the state. We think the lock, not the state. That is my point. So, we are talking here about databases in a very broad scope. I'm not talking about consensus because it is a different and humongous topic. I'm talking about databases. The trick I'm going to explain now, it is not entirely original. It was already used in some projects, but it was used to apply to B3 databases. I will use it to apply to LSM databases because I believe it is much, much nicer in this case. Databases are split roughly in half. Half of them are B3, half of them are LSM. So, for example, on your iPhone, for example, SQLite is B3, and LevelDB typically is LSM. And then you upload your iPhone data to the cloud, it typically goes to Cassandra, which is LSM. Or it may go to some B3 database. Basically, it is a commodity. And what I'm trying to do here, I'm trying to take not the very basic abstract model, lock of changes in state, but go a little bit deeper into the structure of the database and apply cryptography in much finer detail and produce a useful result out of it. Actually, I'm describing an ongoing project. So, LSM inner workings are pretty basic. You have MIM table, which is like a MIM pool with recent changes. And then once you have enough of them, you dump them into a SST file, which is just a sorted file, key value, key value, key value, key value. And this is the key building block of most databases, key value store. To ensure that you don't forget your MIM table, you also duplicate it to write a headlock. They contain the same data, typically. And once you plant these SST files, periodically you compact them, because once you have too many, you have to fetch all of them when you need something. So, you want to be like, I want to have like four, like five of them, maybe seven, but not ten or a hundred, because I will have to check everyone. So, periodically these files are compacted. We take a bunch of small files, basically parallel pass them, and merge them into one big sorted file. And this way database compacts. Also, all the data that was deleted gets torched and compacted. The project I'm talking about, it is also based on CRDT. It is using RDX, CRDT data format. It is like JSON, but it always merges. You can always make a patch. You can always merge a patch to the state, or merge to states, and so on and so forth. And the good part about this particular variation in CRDT, it fits into constraints of LSM merge operators. Basically, in the very heart of LSM database, there is a merge operator, and it can be CRDT. And we made one project already where we installed CRDT into an LSM database. It is a database named Chodki. Basically, it turns any commodity LSM database into a CRDT database. So, you can branch it. You can merge it. You can do all the things. So, this local state separation, it is part of the very, very basic model in the very, very basics of computer science. So, you can see it everywhere. Everything Git has it. All of them have it. So, basically, the key trick that is needed here to have all the good consequences, which I want to achieve, is to compact these SST files deterministically the same way on every node. Because normal LSM databases, they compact based on how many three cores they have, how many space on the disk they have, whether the load is higher right now. So, basically, it is highly non-deterministic. And the idea to make it highly deterministic is to make all the nodes compact the same. So, once applied to the same changes, they will compact the same. They will produce a bit precise, identical state of the database. Not the blockchain, not the log, but the state that users actually read it will be identical. That is the idea. I mean, there is one intermediary step. In case of blockchain, we have verified the blockchain, and then we have some trusted code base, which produces the state identical on all the nodes. So, we have trusted code base. In this case, no. We have identical state. Like, one step less. One step closer to the victory. Then, once we apply this trick, actually, the trick is very simple. Basically, we have a chain of these blocks, and that will be a chain of commits, a chain of everything. So, some blocks will be happy. Their hash will start with some zeros. They'll say, this block is happy. We'll start compaction on this block. So, that way, all the peers synchronize in the way they do compaction. It is a very simple, basic trick. It reminds Proof-of-Work a little, the idea. It is not a new idea. So, then, once we apply this trick, the syncing protocol becomes very easy. First of all, we synchronize not on the lock of changes, we synchronize immediately on the state. And the lock of changes, we may synchronize it, but that is optional. May do it, may not do it. Absolutely optional. All the history, all the cryptographic code, everything stays there in the lock, which some peers may want to download, others don't. Others may just... So, the other interesting part that we apply cryptography deeper inside the database. So, actually, we hash chunks of the data separately. We hash SST files. We don't hash the entire state of the database, just one root hash. We hash chunks. So, we'll have one huge chunk, which wasn't updated for a month. We'll have a smaller chunk, which wasn't updated for a week. And then, if you spend a couple of days offline, then we'll have to update some smaller chunks, which are fresh. And the rest will stay untouched. That is the good part. So, that makes it easy to branch, for example. If you know NEON, the database, which was recently sold for a billion, they're using this particular feature or some databases to introduce branching to Postgres. So, Postgres is branches. The idea is worth a billion, apparently, with all the execution. So, that is the idea. And then, once we have states, we synchronize the states. So, we ask which hash is the current. We synchronize the states. We hash the states at the beginning of everything. We don't rely on some trusted code base. And downloading the log is completely optional. But once we download the state, if you want to stay updated in real time, we keep downloading the log. The actual blocks or the actual commits. Why not? Because we can verify the log, we can verify the state. Absolutely. But the log is optional. Actually, the state is also optional. We may choose. We have, like, four options. Verify nothing, verify one, or verify both. So, that is the architecture. And as long as we aggregate and compact this chunk deterministically, everything is nice, everything is cool. Then, what is good about this architecture? That original Norcal DAG or blockchain is actually highly optional. Like, in a regular commodity database, we have write-ahead log basically in every database. Only the smallest embedded databases don't have the log, write-ahead log. Often, even those databases have it as an option. So, like, in every commodity database, we can discard the old log. So, like, this Merkleized database, it becomes very much like a regular commodity database. Some sort of convergence, right? All the features like a regular LSM database have, but we have all the integrity checking, Merkle hashing signatures, and so on. Then, a good part is that old suit is completely optional. We don't even look into it. Then, catching up is very efficient because we may download the log, we may download the old block, or we may download aggregated changes. We can download the delta, which is already aggregated. That is meaningful in the context of one project, which we actually implemented, and it runs in production in one crypto company, actually counting the money. And the good part about counting the money is they increment counters all the time. They increment money counters, limit counters, quota counters, tons of counters. So, the good thing, they can increment one counter like 100 times a second, then we can compact it and send it out. So, your data changes, they're suddenly 100 times more compact. That's because you aggregate the counters. That is the good feature. And there are many good features like that in this architecture. So, this way, like, Merkle-ized database becomes very much like a commodity database, and from the standpoint of, I don't know, of the IT department, their features are not really different. But no consensus. Consensus is a separate thing. That's it. LSN database is easily syncable, Merkle-verified, forkable, mergeable because using CRT keys, not because of this trick. What not to like? This is an ongoing project. There are two links here. One is very low-level C library, which implements the thing, but it's very low-level C. It doesn't do even any memory management. So, basically, it receives a chunk of memory from the caller and then does the thing very fast in those chunks of memory. Very low-level. And the other one is that experimental database in Go, but it has no Merkle-ization, unfortunately, yet. But it has CRT running as a merge operator inside TableDB. So, thank you. So, the status of the project, it is unfolding. But my key idea here is that the original Bitcoin was very much like MySQL with Merkle-Hashem. And the idea, why don't we look deeper into the database and Merkle-ize the inner workings of the database, not like the most high-level interface and parts. Questions? Time for questions. So, if you scan this QR code on the top right side of the screen. Please, because I cannot see the faces from here, so I'm very interested in questions. I have no idea what the reaction was. It's like all black to me. There's one question there already. And they were asking about, is there a blockchain that's already adopting something similar to a data structure that you presented or getting inspired from it or something like that? I know there was a project, NOMS, which was acquired. And then there was a derived project named DOLT. But they made it with strict B3 database. It was basically MySQL married to Git, and they had babies. That was their slogan. But LSM database has that advantage, basically a better fit for this approach, I believe. But I'm working on a database and a revision control system, which I believe will be like proof-of-work, but it will show that it can work. So you may have like Linux kernel repo, which is like not gigabytes, but maybe like hundreds of megabytes, something like that. But that part of the project is ongoing. There's another question here now. Is the data structure provable, specifically on EVM on-chain? I don't understand this question. It is Merkle data structure. So basically all the data is covered by three flashes in this sense. What do you mean by provable? Maybe if someone is in the audience and has that question. You may do Merkle proofs like proof some local piece of it by making a chain of hashes, uncle hashes, right? If you mean that. You can even shout from the audience, too. You may, for example, have like that big SSD file, which has all your data, which is maybe a terabyte, but you only download from, you know, three. You only download several pages, which have all the data you need. And then you may actually construct Merkle proof to prove these pages are correct and they match the root cache, but that is a trivial exercise. If I understand the question correctly, most likely I don't. Would someone like to add some refinement to that question? I understand, but I'm from an entirely different world, so I don't care about such things. In my world, like everything branches and merges all the time. So that is like the main trick of Seredity is you can merge everything. So for us, fork is not some, you know, like world-ending tragedy, but fork is like, you know, like branches in Git are actually much, much cheaper than branching in Git. Because Seredity branches merge deterministically Git, branches merge non-deterministically. If you merge the same two branches twice, you'll produce different results. Hashes will be different in Git. In Seredity, if you merge the same thing any number of times, it will merge deterministically to the same hash. So in my universe, everything branches and merges all the time, and like we believe that we can live without linear sequences, or at least pretend we can. And in case of blockchain, everything is about linear sequencing. So there is a bit of cultural difference here. There's one new question. What data is used specifically for the CRDT? How are conflicts resolved? What data is what? What data is used for the CRDT, and how are conflicts resolved? Ah, conflicts. You mentioned a PN counter. PN counter. These counters, I don't remember the terminology from 2011. Like, I read it in 2011. I forgot. I don't remember which one counters PN, but the counters are using their vectorized. Basically, the value is split into the contribution of every source. Like for everyone who introduced this counter, you keep a separate entry, how much it will contribute total. This kind of vectorized counters. Maybe they're PN. Maybe I don't remember that terminology. So yes or no? What was the question? It was a question about the CRDTs, how conflicts are resolved there, specifically in this structure. Conflicts are resolved in every CRDT. Basically, you can only keep financial transactions in this kind of a database if you can go into red. Like in a classical bank, most of the time you can go into the red, and then they sort of sue you, some police, or maybe they have some, how to say it, collateral. So basically, banking transactions are sort of here and here. As long as you can go into the red, in classical banking you can go. Because, like, yeah. So it is a separate field which I probably shouldn't discuss here. And you also mentioned something. I think it was the replicated data exchange format, the JSON that merges. Could you talk more about that? It is like a superset of JSON, so it is generalized in many ways. So, for example, in JSON you have maps, and here you have sets, but the sets can host tuples. So tuple is like key and value, for example, or key value and another value, or key value and another value. So it is generalized. It is more algebraic, so you can combine everything and everything, and everything will merge. Because JSON is very limited because it is a subset of JavaScript, and JavaScript in itself was also a 10-day hack, right? So here if we generalize everything and make everything orthogonal and mergeable and mathematically nice, then JSON becomes very good. They also ask if there's any libraries or tools, especially Rust bindings that you would suggest for this. Libraries or tools doing what? Especially for this JSON that merges. Ah, there are many such projects. I don't know, JSONJoy and so on. But the one I'm working on is not JSON, but supersets of JSON. I think if you need just exactly JSON, you have to Google CRDT JSON. That will be like AutoMerge, Yjs, JSONJoy. There is a bunch of them. But this one is superset of JSON because it must be algebraic and very nice. Basically, it is lesser engineer everything from the scratch, and everything will be nice, and everything will work perfectly. One final question. Going to use cases of CRDTs in general, what use cases do you see currently, and where are they usually best at? They're obviously very good at various collaborative applications, various charts. I don't know what is the proper term for linear application, for example. There is groupware, task management, collaborative document editing. Actually, as I said, classical banking is CRDT, assuming that everybody can go into it and with problems, there is also power differently. I don't know. But shooting the depth, it doesn't work. Nothing like that. Then it is a CRDT. In case you need debit cards and spending limits, then it is not a CRDT. Okay. Thank you for your time. If you have any specific questions,