Utreexo - advantages, state of development etc ...

[d5000]

In the recent discussions about OP_RETURN, Knots etc. I stumbled upon Utreexo, developed by the MIT Digital Currency Initiative. It is one of the possible solutions to a part of Bitcoin's scalability problem.

There's a short description here, and there you can also find the link to the whitepaper. There are some node implementations already, like Floresta, but to my knowledge none of the big node projects (Core, Knots, btcd ...) has currently Utreexo support.

I try an ELI5:

- Currently all full nodes must store all unspent output (UTXOs) in a database to be able to validate transactions correctly. This set can grow, above all if there are many small outputs (e.g. from Ordinals).
- In Utreexo, the nodes store only a hash of the UTXOs, which is re-calculated after each block.
- It's the "owners" of the UTXOs (=the Bitcoin owners who want to transact their coins) who have to provide the UTXO when they broadcast a transaction, and a proof that it matches with the UTXO set hash.
- The nodes who see a new transaction, can then compare the hash of the UTXO set they have stored for the current block, to the UTXO proofs provided by those who are transacting.

Please correct if this short summary is wrong.

I don't know the magic behind the last step, have still to investigate if this is something I'm able to understand without a cryptography background. But I can imagine that to work at least.

The advantage should be clear: The nodes would have to store much less data in a "hot" database which changes all the time. Above all small & dust UTXOs created by data protocols would not longer be harmful. And it opens the door also for methods where the nodes would not need to store any possible problematic UTXO anymore, reducing the risk to broadcast problematic data of all kinds.

One question I was wondering about: If the "coin owners" have to provide the UTXO, I think they have to rely on a solid group of nodes who archive the whole blockchain and do not prune it, so they can query the UTXOs. Or would this also work if all nodes prune the old blockchain data (e.g. because they're afraid to distribute certain parts of the blockchain)?

It would also be interesting how mature the Utreexo code is. Can we expect this in the next years already? Or is it something for the 2030s/40s?

Anyway, all thoughts are welcome

[stwenhao]

I don't know the magic behind the last step, have still to investigate if this is something I'm able to understand without a cryptography background.

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:

Code:

SHA-256("")=e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

And then, the owner of the first block is added: https://mempool.space/tx/0e3e2357e806b6cdb1f70b54c3a3a17b6714ee1f0e68bebb44a74b1efd512098

Code:

SHA-256(0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d4e0a604f8141781e62294721166bf621e73a82cbf2342c858ee)=6527751dd9b3c2e5a2ee74db57531ae419c786f5b54c165d21cdddf04735281f

Then, the second block can be attached, and form a basic tree: https://mempool.space/tx/9b0fc92260312ce44e74ef369f5c66bbb85848f2eddd5a7a1cde251e54ccfdd5

Code:

SHA-256(047211a824f55b505228e4c3d5194c1fcfaa15a456abdf37f9b9d97a4040afc073dee6c89064984f03385237d92167c13e236446b417ab79a0fcae412ae3316b77)=1be7e6b388892a76eb5119cd32d339cc0f64e3b7574cd4f1d00afaa844331e7c

And now, you can connect two leaves of the tree, to compute the merkle root:

Code:

SHA-256(utxo1)=6527751dd9b3c2e5a2ee74db57531ae419c786f5b54c165d21cdddf04735281f
SHA-256(utxo2)=1be7e6b388892a76eb5119cd32d339cc0f64e3b7574cd4f1d00afaa844331e7c
SHA-256(6527751dd9b3c2e5a2ee74db57531ae419c786f5b54c165d21cdddf04735281f1be7e6b388892a76eb5119cd32d339cc0f64e3b7574cd4f1d00afaa844331e7c)=7fb6e3044fa2b48ae2180b0f41ff88f3b7f48305538643993979e32cd14f1a6c

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.

The nodes would have to store much less data in a "hot" database which changes all the time.

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.

If the "coin owners" have to provide the UTXO, I think they have to rely on a solid group of nodes who archive the whole blockchain and do not prune it, so they can query the UTXOs.

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.

Or would this also work if all nodes prune the old blockchain data (e.g. because they're afraid to distribute certain parts of the blockchain)?

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.

Can we expect this in the next years already?

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.

Or is it something for the 2030s/40s?

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/

A. Intro

Imagine we need to put The Lord of the Rings trilogy “on the blockchain”.

Which blockchain, should we use? BTC or BSV?

Well, BTC has a 4 MB blocksize limit. LotR is 176 GB. So LotR won’t fit “on” BTC… right? We have to use BSV.

Wrong.

I could put 10,000 copies of LotR “on” the BTC blockchain, right now. Or even a million copies. Or a million unique movies. There’s no limit.

It would be different, if I wanted to put LotR “in” the BTC blockchain.

“On” and “in” make all the difference.

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.

[d5000]

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:

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.

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

[ertil]

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?

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.

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.

If a new valid block is produced, then all nodes would accept it.

but wouldn't it cause disruptions if major wallets like Electrum lag with that implementation

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.

and many people would have difficulties to send their transactions

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.

I imagine a new transaction version with the UTXO proof integrated, implemented via softfork, would be the way to go?

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.

BTW: is there currently an Utreexo implementation really ready for productive use?

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.

I haven't seen any announcement yet, or am I wrong?

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.

Because a Knots "victory" in the OP_RETURN drama is definitely not impossible, but the consequences could be devastating.

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.

So it's not a bad idea to have a plan ready to upgrade the network to it

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

[NotATether]

One question I was wondering about: If the "coin owners" have to provide the UTXO, I think they have to rely on a solid group of nodes who archive the whole blockchain and do not prune it, so they can query the UTXOs. Or would this also work if all nodes prune the old blockchain data (e.g. because they're afraid to distribute certain parts of the blockchain)?

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.

[Mia Chloe]

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.

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.

Segwit is not mandatory, you can run a node, which knows nothing about it, and you will stay on the same chain.

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.

[tromp]

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.

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

[ABCbits]

Utreexo is a novel hash based dynamic accumulator, which allows the millions of unspent outputs to be represented in under a kilobyte -- small enough to be written on a sheet of paper. There is no trusted setup or loss of security; instead the burden of keeping track of funds is shifted to the owner of those funds. 

Currently transactions specify inputs and outputs, and verifying an input requires you to know the whole state of the system.  With Utreexo, the holder of funds maintains a proof that the funds exist, and provides that proof at spending time to the other nodes.  These proofs are compact (under 1KB) but do represent the main downside in the utreexo model they present an additional data transmission overhead which allows much smaller state.

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.

It would also be interesting how mature the Utreexo code is. Can we expect this in the next years already? Or is it something for the 2030s/40s?

I'd say 2030 or later, since it require change on both wallet software and full node.

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.

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

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.

[ertil]

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

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.

it supposed to be very impractical

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.

[tromp]

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

By embedding it into private keys.

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.

And the same attack can be done on top of Monero as well

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.

[NotATether]

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.

[tromp]

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.

[ertil]

how do properly order all these bytes that you get from many 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:

Code:

SHA-224("first")=25dcea7702a33590fbc3b77fca5c7e4185bf695016c6aac206732f2f
SHA-224("second")=ec509df26f24b037062470e4a3067e5208734c7b0efcf37bca421d21
SHA-224("third")=f4d22c82a590c71cf552851ad0d4f548a52038874ba6f7612c4c59e5
SHA-224("fourth")=c156cf9dadc4c6e4a38edc1d31009a90a625f642d968b3c432f5f1fb
SHA-224("fifth")=b33815dadef1da3e97abd685ea7dbfd8ef130caa4fea163dddd30095

key1=0900000025dcea7702a33590fbc3b77fca5c7e4185bf695016c6aac206732f2f
key2=78000000ec509df26f24b037062470e4a3067e5208734c7b0efcf37bca421d21
key3=73000000f4d22c82a590c71cf552851ad0d4f548a52038874ba6f7612c4c59e5
key4=8c000000c156cf9dadc4c6e4a38edc1d31009a90a625f642d968b3c432f5f1fb
key5=e5000000b33815dadef1da3e97abd685ea7dbfd8ef130caa4fea163dddd30095

key1*G=0300BFF8E97F611BFDCB051F0A2199B49957399F9EAFF98C014B5C8ABC17314724
key2*G=0301A6E729CEFF00CA024AB780B1DB9E0FD4AEB4773A2BB609B6951EC80F9F128B
key3*G=03029D0D5D783751527DF65DB65ECEED331E909A6DA884D035049E86A1BD4A957A
key4*G=030328826847120697B23C5AE039234EF9B8E36D26DA6F704FCA192A1A127C9B7C
key5*G=02047C7EF396025C50B6DF3672B3D35799A6EF49EBE6184B83DE2BE5D740173593

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.

Recovering data from a pure MW chain is so painful that a spammer will vastly prefer any other chain to spam.

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.

[tromp]

how do properly order all these bytes that you get from many 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.

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.

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.

[ertil]

for a spamming efficiency of 1/3

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.

[d5000]

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.

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?

If a new valid block is produced, then all nodes would accept it.

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.

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.

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.

[ertil]

Wouldn't it then be "cleaner" to simply do a softfork with a new transaction format which already includes 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.

but I was referring to the phase before the acceptance into a block, when the transaction is trying to propagate via the mempools

If some transaction has enough information, that it is accepted in a block, then what else is needed, if it is flying in mempools?

Perhaps Core in v31 returns to the old standardness values too.

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

That would lead to an UTXO set explosion.

It is not a question, if UTXO set will explode. The only question is "when?".

that you will only be able to make transactions without friction if you already include the UTXO proof

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.

[pancelot]

One question I was wondering about: If the "coin owners" have to provide the UTXO, I think they have to rely on a solid group of nodes who archive the whole blockchain and do not prune it, so they can query the UTXOs. Or would this also work if all nodes prune the old blockchain data (e.g. because they're afraid to distribute certain parts of the blockchain)?

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.

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.

[d5000]

If some transaction has enough information, that it is accepted in a block, then what else is needed, if it is flying in mempools?

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.

[ertil]

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.

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.

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.

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's a scenario where even true full nodes are scarce and most nodes are pruned

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.