Utreexo benefits, current development status and more

So, I've been diving into the talks around OP_RETURN, Knots, and I came across Utreexo, which is being worked on by the MIT Digital Currency Initiative. It could be a key player in tackling some of Bitcoin's scalability challenges. There’s a brief overview available here, and you can find the link to the whitepaper too. There are some implementations for nodes like Floresta, but as far as I know, none of the major node projects like Core, Knots, or btcd have integrated Utreexo support yet. Let me break it down in simple terms: - Right now, full nodes need to keep all unspent outputs (UTXOs) in a database to validate transactions correctly. This can really pile up, especially with a ton of small outputs (like those from Ordinals). - With Utreexo, nodes only save a hash of the UTXOs and update it after each block. - It’s the UTXO owners (Bitcoin holders wanting to make transactions) who provide the actual UTXO when they send a transaction, along with proof that it lines up with the UTXO set hash. - Nodes that see a new transaction can check the UTXO set hash they have for the current block against the UTXO proofs sent by those making transactions. Feel free to correct me if I got any of this wrong. I’m still figuring out the technical magic behind that last part. Not sure if I can grasp it without a cryptography background, but it seems like it should work at least. The upside seems pretty obvious: nodes would need to handle way less data in a constantly changing "hot" database. Especially when it comes to small and dust UTXOs generated by data protocols.

It is quite simple. If you know, how SPV wallets work, then you should understand it. Just imagine that instead of the merkle root of all transactions, you have a merkle root of UTXOs, and instead of transactions as leaves of the tree, you have transaction outputs, which can be used as inputs in the future. Which means, that initially, you can start from the empty UTXO set: And then, the owner of the first block is added: https://mempool.space/tx/0e3e2357e806b6cdb1f70b54c3a3a17b6714ee1f0e68bebb44a74b1efd512098 Then, the second block can be attached, and form a basic tree: https://mempool.space/tx/9b0fc92260312ce44e74ef369f5c66bbb85848f2eddd5a7a1cde251e54ccfdd5 And now, you can connect two leaves of the tree, to compute the merkle root: Then, the root of the tree is set to 7fb6e3044fa2b48ae2180b0f41ff88f3b7f48305538643993979e32cd14f1a6c. And you can prove, that your UTXO is inside, by revealing, that the left branch is set to 6527751dd9b3c2e5a2ee74db57531ae419c786f5b54c165d21cdddf04735281f, the right branch to 1be7e6b388892a76eb5119cd32d339cc0f64e3b7574cd4f1d00afaa844331e7c, and you can reveal the UTXO behind the branch you own, by travelling down the binary tree, just like you can do the same inside merkle root for transactions. Not only that. All updates can be logarithmic. If many parts of the tree are never changed, and coins are just staying, where they were, then once hashed data can be just copy-pasted, without being re-hashed again. Yes. If they know only their private keys, but nothing behind that, then they have a problem, if no node can give them any proof, that their transaction exists at all. Then, funds are still there, but if nobody knows, where they are located, then it is the same, as if someone would throw away the private key. Then, having keys is as important, as knowing the content of your transaction, and its location in the UTXO set. If some user would backup the UTXO location, and a proof, that coins are located in a certain place, then that user should be safe. It is not a soft-fork. It is just a different client, that can be used by those, who want to consume less resources. As long as it is not mandatory, to provide UTXO proofs, to spend coins, it is fully optional. It can be mandatory, if there will be too much spam, so that nodes will be kicked out of the network. But it is not the case yet, as long as hashrate majority didn't turn BTC into BSV yet. You can use it now, without asking for anyone's permission. Nodes can run any source code they want, as long as they stay compatible with the network. You can here and now, require UTXO proofs from people, to relay their transactions. Or you can accept no transactions at all, and just listen for new blocks. As long as there is no proposal, to make it mandatory, it is fully optional. It is in the same category, as transaction compression: you don't have to process over 600 GB. You can accept ZK proof during Initial Blockchain Download, if you want to. And you can compress any transaction data in any way you want, as long as you can decompress it, and share with the rest of the network in the old format, when needed. So, it is fully up to users, what they want to use. The official protocol dictates, what you need, to stay compatible. But behind it, you can use everything. A good example is "LOTR node": https://www.truthcoin.info/blog/bsv-data-avail/ Which means, that even if someone will want to change the block size, then old nodes can stay unupgraded. Segwit is not mandatory, you can run a node, which knows nothing about it, and you will stay on the same chain. So, some kind of UTXO proof can be included, just like this: 7fb6e3044fa2b48ae2180b0f41ff88f3b7f48305538643993979e32cd14f1a6c. But it is all about nodes, to really validate it, make sure, that it is computed correctly, and that all coins are valid. And behind a single 256-bit number, you can store up to 2^64 bits of data, as long as SHA-256 is not broken.

Thanks @stwenhao a lot for your explanation! Indeed, SPV seems to be a very good model to compare. Now to the last part there's still one thing I don't understand: But once these proofs become mandatory, when nobody is anymore storing the "classic" UTXO set and Utreexo nodes are considered "full nodes", then I guess some consensus change would become necessary, right? Let's speculate the whole OP_RETURN drama leads to a "victory" of Knots, and all NFT protocols switch to fake public keys (Bitcoin Stamps ...), causing the UTXO set to explode. That makes node owners aware of Utreexo and they switch massively to some utreexo-supporting client. But if the UTXO proof for transactions was still not mandatory, I guess there would be a conflict between transaction senders who omit the proof (and maybe don't know how to obtain it) and nodes not providing the classic UTXO set anymore. Of course the wallet client maintainers would have eventually to implement that, but wouldn't it cause disruptions if major wallets like Electrum lag with that implementation and many people would have difficulties to send their transactions. I imagine a new transaction version with the UTXO proof integrated, implemented via softfork, would be the way to go? BTW: is there currently an Utreexo implementation really ready for productive use? There seem to be indeed projects like utreexod and Floresta (Electrum server). But these seem to be small hobbyist projects and for Core (and other major clients like Knots) I haven't seen any announcement yet, or am I wrong? That whole bunch of questions was what I meant when I asked if Utreexo is already "ready" or "something for the 2030s". Because a Knots "victory" in the OP_RETURN drama is definitely not impossible, but the consequences could be devastating. So it's not a bad idea to have a plan ready to upgrade the network to it ...

I think it is not a good idea, to make it mandatory. A lot of people would protest, a lot of spammers would complain, and we would have yet another "OP_RETURN drama", which nobody needs. It is much better to make it optional, and have it as a "de-facto standard". Stratum is not obligatory, but most of the miners use it. Fee rate of 1 sat/vB is also optional, but it was set to this value for years. And the same can be done here: node operators that care about resources, could just upgrade to the new model, and stay compatible with the rest of the network. There is no need to force it on everyone. When running old nodes will consume too much resources, then people will upgrade anyway, rushing it will only cause more drama, than we need. If a new valid block is produced, then all nodes would accept it. Electrum doesn't have sighashes fully implemented yet, even though they are present since 2009. So, if 16 years of delay is not that bad, then they can delay some features a bit more, because there is no rush. Nodes can relay what they want. Or even not relay anything at all, and accept only new blocks. As long as all new blocks are accepted correctly, the network will follow the same chain. There is no need for a new transaction version, but yes, it can be done in that way. It can be simply added as a new P2P message, because the client doesn't have to be limited to the current protocol. It can handle Bitcoin and anything more, if you want to. When you connect to port 8333, then you can serve Bitcoin requests for Bitcoin nodes, and also HTTPS requests for the browser, and stay compatible with the network. Which means, that if your client will do more things, then it can still be compatible. It is like stratum: you can use it, you can use getblocktemplate instead, or you can build blocks in a completely different way. It is up to you. The only case, where it matters, is when you want to standardize things, to make your life easier, and connect to other nodes, send them some traffic, and expect it to be interpreted in a particular way. But just for yourself, you can make any optimizations or extensions you want, and nobody would stop you. Bitcoin itself is "experimental software", so everything built on top of that is "double experimental". Don't expect some group, which would tell you, what you should use. Just try it, and make your own decision. Because no announcement is needed. Sidechains were also poorly announced, but they are now deployed. People would move, where they would want. Nothing is enforced, you can be only encouraged to try something. Soft-forks cause too much drama, so new upgrades will be built in a no-fork way, and then, nobody will be asked for permission; you will just see new things deployed, without any BIPs, any activation, any signalling, and anything like that. So, welcome to the no-fork world, where you can do with your client, what you want, where developers are responsible for absolutely nothing, and where you have to make your own decisions, because nobody cares. The only "victory" could happen, if the blockchain would be reorged, and all spammy transactions would be removed. Otherwise, it is very far from "victory". It is just a single win in a single battle, but the war is still ongoing. Also, I don't think they will ever "win". Data could be wrapped into regular public keys and signatures. You can have a chain with P2PK-only, without any Script, just like the whitepaper described, and still have Ordinals. Even if you upgrade to a model like Grin, and reorg the whole chain, to enforce it from the first block, then the chain will still be spammed. The spam will always be there, it is only a matter of writing the code. More than that: the "grin-like" spam will be harder to detect, easier to be compressed by spammers, and more difficult to handle by non-spamming nodes. The current situation is far from perfect, but it could be much worse. So, just use the current chain, while you still can, and while the level of spam is still quite low, compared to what it could be in the future. The upgrade plan is optional. Nothing will be enforced, because as I told you, developers will be responsible for nothing. Users will start seeking solutions, when running a node will be too difficult. And then, many people will stop running any node, and others will run just a better implementation. And now, there is no need to rush, because it is better to let spammers think, that they won, so they won't focus on worse solutions, and existing nodes can handle the current level of spam much easier, than they would after a "no-ordinals-softfork".

It's more like having a large bitwise array (without needing to store any of the UTXOs somehow), where each bit represents a UTXO that has ever been created, as to whether it exists or not. Just so that you understand how the storage savings is supposed to work. This is the simple explanation but the data structure is actually much more complex than that because you not really going to save a lot of space by using an array that does not contain the metadata.

Actually i was of the opinion Implementing a UTXO set commitment as a verifiable part of the protocol which means blocks are invalid without a correct commitment is actually a fundamental change to Bitcoin's consensus rules. More like a new rule that all nodes must follow to stay on the same chain. It is in a way not fully optional for the network since the entire network would need to adopt the new rule to actually validate blocks containing the commitment. Also, I think a legacy node that actually knows nothing about SegWit can't fully validate SegWit transactions. It can't verify the new witness data and go ahead to trust that upgraded nodes are doing the work correctly. Regardless of the fact it's still the same chain it has actually affected its ability to independently verify all transactions which is one of the purpose of a full node.

And how exactly would you embed spam into a pure Mimblewimble blockchain like Grin?

This makes me wonder size of TX (in bytes and virtual btytes) between regular one and one that include this Utreexo proof. I unable to find such information on both their website and their PDF. I'd say 2030 or later, since it require change on both wallet software and full node. I don't know much about technical side of Grin. But looking at https://forum.grin.mw/t/ordinals-on-grin/10336, it supposed to be very impractical.

By embedding it into private keys. Mimblewimble can make your blocks smaller, if everything is compressed in a scope of a single block. But if you have "Alice -> Bob" transaction in one block, and "Bob -> Charlie" transaction in another block, then Bob will never be thrown away. Also note that spammers don't care about efficiency. If uploading 1 MB of data into Grin would take them 1 GB, then they will still do that, given enough incentive. Because the purpose is not to even have an efficient cloud storage: the purpose is to turn every chain into BSV, so that centralization pressure starts throwing nodes out of the network, and then, it becomes ruled by miners in practice. Another important thing is if you are a Grin miner, and you send transactions between yourself, then your keys doesn't have to be "random". If you transact between independent parties, then they usually are. But if you are transacting only between yourself, then you can pick all values in a way, where even all private keys could be trivially broken, when you apply weak encryption, or no encryption at all, and where the real transaction flow, before batching, would be trivial to decode. And the same attack can be done on top of Monero as well: things are hidden, if you transact between different parties. But putting a large amount of data into Monero, if you use a private key equal to one, is valid, when it comes to consensus rules. And if you make the whole block of transactions with only weak keys, then it would be trivial to decode. Because a lot of people have no technical knowledge, or it is limited. However, if simple ways of spamming will be blocked, then spammers will switch to different models, which will be harder to stop. Now, when it comes to OP_RETURN, witness data, or Ordinals envelope, it is trivial to detect and prune. So it should stay that way, as long as it could be, because then, throwing away all of that data will be easier, when ZK proofs, or other improvements will be ready.

You can only embed a few bytes into private keys, since the data must be efficiently recoverable from the corresponding public keys that appear on chain. But the bigger problem you have is: how do properly order all these bytes that you get from many keys? Recovering data from a pure MW chain is so painful that a spammer will vastly prefer any other chain to spam. Spamming any non-MW chain, like Bitcoin or Monero, is orders of magnitude easier since you can simply use fake public keys that store the full 32 byte of arbitrary data.

This also includes optional-MW chains like Litecoin, but I'm sure you already knew that.

Yes, I mentioned that *pure* Mimblewimble is spam-resistent. Litecoin implements a much more complicated hybrid that allows for fake public keys.

Just by a little bit of grinding. Imagine that you are a miner, and you want to put things in order. Then, you sacrifice some bytes from your private key, to grind it, until you reach a proper value. For example: if some private key has 256 bits, then you can use 224 bits for data storage, and 32 bits for nonce grinding, to put things in order. And then, putting data is costly, because you have to literally mine them. However, reading data is easy, because you read a public key prefix, and you know, where it should be placed. For example: And then, by reading "0300", "0301", "0302", "0303", and finally "0204", you know, what is the order of the public keys. If signatures are weak, then public keys can be easily turned to the private keys, and then you can read the data. Of course. But it is possible. And if all chains will start putting protections, then at some point, spamming the MW chain will be profitable, if other ways of spamming will be even more difficult to launch. Or, spammers could always give up, if the barrier of knowledge, to make a spamming client, would be too high. But I think there is enough determination, that some people will always spam. Because if some altcoiners still cannot make a great chain, then at least they would try to harm others, because of their egos.

You make a good point about weak signatures. The spammer can make a transaction with N signatures, with the i'th one using nonce i, public nonce Ri = i*G, arbitrary data for the public key xi, and public key Pi = xi*G. Then the signature si = i + e * xi where e = Hash(Ri|Pi|mi), from which xi can be recovered as xi = (si - i) * e^-1. The easily recognized public nonces Ri can be used to recover the correct order of all xi. Message mi encodes kernel features, which in Grin can include a lock height in the past, that can store an additional 3 bytes of arbitrary data. Altogether, this encodes 35N bytes in a transaction of at most 105N bytes, for a spamming efficiency of 1/3, although the extraction is computationally somewhat expensive.

It can be turned into 2/3, or something around 1/2 in practice, if signatures would be weak, but if they would also carry some data. For example: 128-bit signatures are weak. You can have the first half of the signature, which would just make it weak, and inform about the order, and the second half can carry some data. Then, by using lattice attacks, private keys can be easily recovered, so you can read everything. If a given elliptic curve would be fully broken, you would reach 2/3 spamming efficiency, where for every 96 bytes of consensus data, 64 bytes would be taken by the payload, and 32 bytes would just make things tick under ECDSA. But in practice, under lattice attacks, I expect the spamming factor to be closer to something like 1/2, because you have to leak some bits somehow, to make going from public to private key easy enough, so your data could be read by anyone. And then, spamming efficiency of 2/3 is just the same as in Bitcoin with P2PK, and nothing else. But 1/2 spamming efficiency, or even 1/3, is something practical. I guess some spammers would happily waste 3 MB of MW blockchain space, just to publish 1 MB of data in it. Edit: Also note, that 3 MB is something, that would be seen by non-spammers. Spammers could easily use deterministic algorithms, and derive the whole content from their 1 MB. And if a spammer is a miner, then through self-transfers, the whole block can be fully controlled, so that nothing is randomly set, but every byte is placed in a desired order, as long as it meets consensus rules.

The problem is that it could become mandatory "by accident", if too many nodes use utreexo. The transaction senders would not be able anymore to send transactions without the UTXO proof. It's for example possible (although perhaps not too likely) that so few nodes which still provide a classic UTXO set are left, that they would start to take fees. All this is a quite worst case scenario, but it could become realistic when we get a massive UTXO spam wave. Wouldn't it then be "cleaner" to simply do a softfork with a new transaction format which already includes the UTXO proof? That's clear, but I was referring to the phase before the acceptance into a block, when the transaction is trying to propagate via the mempools. Of course miners would probably have an incentive to run the old-style UTXO set to be able to accept high-fee transactions without the UTXO proof directly. But the network then would become more segregated. It would be a similar effect to that happening today with non-standard transactions being accepted directly by miners. I meant a different thing here. The scenario I have in mind goes as follows: A lot of nodes (50%+) switch to Knots. Knots has the Ordinals filters and the low OP_RETURN standardness value as defaults. This would make it more difficult for Ordinals and OP_RETURN based NFTs to propagate. While they could still pay miners directly, it would not be as straightforward as before. Perhaps Core in v31 returns to the old standardness values too. NFT creators then could massively switch to Stampchain and other fake public keys methods which Knots is unable to filter (Stampchain isn't a small protocol, there are more than a million transactions already). That would lead to an UTXO set explosion. The consequence would be more nodes experimenting with utreexod or Floresta or any other utreexo-supporting client. Eventually they could become the majority, and then we would begin perhaps to see the problems I mentioned: that you will only be able to make transactions without friction if you already include the UTXO proof.

Of course it would be. But the default option is to "do nothing", so expect that option to be deployed, unless someone will propose something else. If some transaction has enough information, that it is accepted in a block, then what else is needed, if it is flying in mempools? It is hard to put limits back, when they are lifted. Nobody would accept that, for the same reason, why nobody would rise minimal fees from 0.1 sat/vB into 1 sat/vB or 10 sat/vB. Introducing standardness rules was easy during early days, because there were not so many nodes. But now, if non-standard transactions will be widely included, then in practice, we would need a new way of upgrading things (fortunately, there are some, but they are unused, because it is easier to increase Segwit version, at least for now). It is not a question, if UTXO set will explode. The only question is "when?". Yes, so aware users should be prepared for that now, by saving more things than just their private keys in their backups. And unaware users will of course suffer. And then, only spammers can be blamed, because they are pushing us to the world, where accepting UTXO proofs is inevitable, when there is too much spam. Being your own bank comes with some responsibility. Users should watch quantum progress, users should keep their transaction data somewhere, users should not use too far in the future locktimes, to not risk their funds being burned forever, and so on. That is a price you have to pay for P2P transactions: that you have to care about consensus rules, and the current state of the network.

I agree with the contention that Utreexo does not simply "rehash the UTXO set," but instead uses a Merkle forest–based accumulator. Namely, nodes only need to store the root hashes, and membership proofs are logarithmic in length relative to the UTXO set. That is, it's not simply an array of binary values, but a data structure which ensures integrity and efficient updates upon adding or removing UTXOs. This makes storage more lightweight and allows for efficient verification without nodes needing to keep full UTXO metadata.

The problem isn't that much with wallets which are synced regularly, where normally the UTXOs are saved in the wallet database too, even if it's a SPV wallet, so the information needed for the UTXO proof indeed should be always available. Instead it could appear if we have an old HODLer, who has not touched his coins nor synced any wallet in years, and then wants to transfer them. If he isn't able to connect to an archival node who has stored the whole blockchain, or alternatively the UTXO set, he wouldn't be able to move the coins. Of course this is a step further away than the "Knots wins and triggers Utreexo adoption" scenario, it's a scenario where even true full nodes are scarce and most nodes are pruned. This could however happen after some massive injection of illegal material in the blockchain via the "fake public keys" model. It's true that it is unlikely that the number of full nodes able to provide the UTXO is so low that there are really problems to connect to one. However, if it comes close to that scenario, it could be used for FUD and maybe some economical attacks. I agree with your conclusion that users should be made aware to save UTXOs when they receive a transaction. I hope however that once Utreexo adoption begins to increase, Core implements it "officially", preferrably with a transaction format update. BTW there are three draft BIPs which came out relatively recently and have just 2 weeks ago been asigned the BIP numbers 181 to 183 (but are still not official): - Utreexo accumulator specification (BIP 181) - Transaction validation (BIP 182) - P2P networking changes (BIP 183) The second and third BIP are just what I was referring to - the additional information which has to circulate about UTXOs.

1. If someone has some old wallet, then that person usually also can see some old transactions, even if it is SPV wallet. 2. If new coins were sent in the meantime, then without syncing the node, the owner does not know, if he received anything at all. Because online sites like block explorers can lie. And if the owner would sync even some SPV wallet, then he would get transactions in plaintext. That would happen only in case of "walletless" people, who just trust, that block explorers, and other online sites, are telling the truth. But in that case, they could be easily robbed anyway, because if a given block explorer would display some fake SHA-256 hash, and that would be signed with the real keys, then coins could be easily stolen in many cases, because a valid signature for a fake transaction, could be used in other contexts, to trigger some unexpected conditions. It is inevitable. If you count, how many pruned nodes are there, and compare it with the number of "nodeless" users, then I think the majority is not running any node at all. A lot of users are using SPV wallets, many users use exchanges, and never touch any on-chain coins, and now, more and more users are trading things like CFDs, where they don't have to touch any crypto, and where everything can be fake. Also, if you think about it, and count, how many UTXOs can be created and consumed per block, then you will notice, that if Bitcoin would be adopted globally, then one UTXO per user is not a realistic scenario. It is very likely, that if people would want to globally use Bitcoin, then there would be thousands, millions, or more users, committed to a single UTXO. Which also means, that regular users would need many SPV-like merkle trees, to locate their coins on-chain. Now, LN assumes two users per UTXO, but this number is quite low, and it is not enough to onboard everyone.