Let's try this "engagement farming" thing. I was invited to a big YT channel to discuss the quantum threat. Inspired by the comments to the previous video (pinned), if this post gets 1k likes I'll wear a $kas Kaspa shirt.

UTXO set commitments are $kas Kaspa's quantum achilles hill In light of the recent truly astounding advances in building quantum computers, I think it's time to explain the most significant threat to Kaspa's consensus mechanism that such machines pose. It's not an immediate threat, but arguably something that requires more attention given the shift in the landscape. Before I start, I want to mention that @mcpauld invited me to a recorded session where we will talk about the new quantum advances, their meaning, and their consequences to blockchains. Stay tuned to know when it is published. Incremental Hash commitments and MuHash When a new Kaspa node syncs from an existing one, it gets a copy (actually, two copies, but never mind) of the UTXO set, along with a commitment. The commitment is a small hash that cryptographically assures that the supplied UTXO set matches the expected one. Hashing the entire UTXO set is an ever-daunting task, whose computational cost grows with the number of UTXOs. It's reasonable to do once during sync for verification, but for a miner, recomputing the entire hash for every new block would gradually make mining less and less accessible. To address this, Kaspa headers use an incremental hash. It's a special kind of hash that is used to commit to a set of strings (each representing a UTXO). What makes it special is that given the current commitment, as well as a list of elements to add and remove, one can compute the hash of the resulting set without recomputing the entire hash. So when creating a new block, the miner just uses the existing hash and updates it according to the UTXOs consumed and created in its block. As long as the block wasn't pruned, all nodes can repeat this check and verify that the miner is honest. Generally speaking, hashes are not incremental. Incremental hashes are specially designed to provide this functionality. In particular, Kaspa uses MuHash, a very lightweight incremental hash. Quantum Shor Attacks I will not go into the details of what quantum computers can or cannot break. But what's important to remember is that they can break what we call "discrete log assumptions". Stock hash families like Keccak, SHA, Blake, and so on do not rely on any such assumption, so they are considered quantum secure (in the sense that it is impossible to quantum-optimize them beyond the obligatory Grover quadratic speedup). However, MuHash relies on elliptic discrete log assumptions, very similar to ECDSA. This means that a quantum adversary can invert the hash commitment. In other words: they can find a completely different UTXO set with the same MuHash commitment. Consequences The UTXO set can only be verified independently of the UTXO commitment until the block is pruned. After that, Kaspa clients will accept any UTXO set that matches the commitment. This, for example, allows the following 51% attack: 1. Locate the UTXO commitment of the latest pruning block 2. Use your quantum computer to find another UTXO set with the same commitment 3. Build a competing heavier chain that assumes the UTXO set at pruning is the one you manufactured and not the original one Voila! A 51% the length of a single pruning window that can rewrite Kaspa's enitre history. Comparison to the current state Currently, Kaspa relies on social consensus in the short term, followed by cryptographic security in the long term. Social consensus prevents committing to UTXO sets that weren't a consequence of legitimate transactions. Cryptography uses state commitment to cement the UTXO set agreed upon by consensus. This is a very mild relaxation of Bitcoin's trust model, which does not require social consensus in the short term for chain consistency. Breaking MuHash means that the cryptographic backbone of this model no longer holds. UTXO commitments become unreliable, compromising Kaspa's trust model. I want to stress two things: 1. The attack only requires one application of Shor's algorithm to find a preimage. It might require some clever mix-and-match to find a preimage you actually like, but factors like BPS or difficulty do not make the attack any harder. 2. The attack cost is directly proportional to the length of a pruning window (in RW time, not blocks). So shorter pruning windows = less quantum secure network. Partial Solutions 1. Relying on archival nodes. If archival nodes are always available, then the problem "goes away". The issue is that archival nodes become a trusted source of truth. Currently, we don't have to trust archival nodes, because the UTXO commitment ensures that the UTXO set they describe is genuine. With this assumption quantum-broken, we need to either trust archival nodes or have enough archival nodes to trust decentralization. One of Kaspa's strong points over Bitcoin's antiquated model is a trust model that does not require trusted archives. Removing this will make Kaspa de-facto centralized. Worse yet, the reliance on archival nodes is fragile, as if, for some reason, there is a period of time longer than a pruning window that was not archived by anyone, the chain becomes indefinitely unverifiable. 2. Changing Hash There are post-quantum hashes like LtHash. The first issue (but not the key one) is that such a commitment is much larger (2KB versus a few dozen bytes). Recall that the UTXO commitment is a part of the header, so using such large commitments will make headers 9-10 times larger, drastically increasing storage costs for pruned nodes. (One can argue that pruned non-mining nodes can run in a mode that chucks away the commitments after verifying them. This will reduce storage, but it is impossible to sync from such nodes trustlessly, recreating the few sources of truth problem.) But even if we do magically find a tiny post-quantum hash, that will only provide a partial solution. A quantum adversary could not forge the UTXO set from the latest pruning point, but would have to go back far enough to split from a block that still uses MuHsah. Possible solution I haven't spent any time trying to come up with a better solution. It is very possible that a better approach exists. Below is a strating point for a discussion, not a concrete proposal: 1. Converge on a post-quantum incremental hash, lets call it QuHash 2. Decide on a block from which commitments must be in QuHash 3. Decide on a period of time (say, a year) after which reorgs below the QuHash depth are considered invalid. This is a very problematic solution, for several reasons: 1. (After qday) any archival information from before the QuHash days cannot be trusted. This includes any form of cryptographic receipt. All could be easily forged without tampering with the commitment. 2. (After qday) there will no longer be a reliable way to verify a UTXO set "all the way to genesis", just "all the way to when we started using QuHash". What happened before qday is delegated to social consensus. 3. Headers will become larger by an order of magnitude. Conclusion MuHash is a considerable quantum weak point that is unique to Kaspa. Arguably, it's time to start brewing up solutions.