Bitcoin utxo set size

MODERATORS

4 stars based on 76 reviews

I'll admit the last one was probably the most fun other than. TXO commitments were a bold idea but bitcoin utxo set size there were some observations that make it more interesting. I thought I would start by going through what problem they are actually solving. Like David was saying in the last presentationrunning a full node is kind of a pain. How big is the archival blockchain data?

Earlier this morning on blockchain. They don't have a good track record, who knows, but it's roughly the right number. History doesn't disappear, it keeps growing. In this case, in David's talk, we were able to mitigate that problem with pruning if you want to run a pruned node you don't have to go keep all that gigs on disk all the time. Currently there are some issues with pruned nodes where we don't have the infrastructure to do initial synchronization from each other.

But long story short, it's pretty easy to see how the archival history problem we can solve it by essentially splitting up the problem and letting people contribute bitcoin utxo set size space. However, pruned nodes still have the problem of the UTXO set which is that if your node wants to go verify someone spending a coin, you must have a copy of that data. Otherwise, how do you know that the coin is real? Even a pruned node is carrying around 50 million UTXOs right now.

That number while it can go up and down a bit, fundamentally it will always go up in the long run, because people will lose private keys.

That's enough to guarantee that UTXO set size will continue to grow up. That can grow by 50 GB per year. If we want to go scale up block size, and segwit does that, the amount that the Bitcoin utxo set size grows can go up too. So it's not necessarily a big problem right now, but even in the future having the UTXOs around can be a problem. If you have a block with inputs, you need to do queries to wherhever you're storing the UTXO set You can run this on a hard drive with all the UTXO data, and the node will run a lot slower, and that's not good for consensus either.

In the future we're going to have to fix this problem. How is the UTXO data stored anyway? With this crowd, you're all thinking about a merkle tree. The reality is that it's oversimplified of leveldb architecture.

Basically everything in existence that stores data, there's some kind of tree, you start at the top, you go access your data. You can always go take something that uses pointers and hash it and convert it into what bitcoin utxo set size usually call a merkle tree. The other thing to remembe rwith UTXO sets is that not all the coins are going to be spent. In this bitcoin utxo set size, suppose the red coins are the ones that people are likely to go spend in the future and they have the private keys.

And the grey ones maybe bitcoin utxo set size lost the private keys. If we're going to scale up the system, we have some problems there. First of all, if we're going to scale it, not everyone wants to have that all that data. So if I go and hash that data, you know, I can go and extract proofs, so I can go and outsource who has a copy of this.

For instance, go back a bitcoin utxo set size, if you imagine all this data being on my hard drive and I want to not have it, I could hash it all up, throw away most of it, and if someone wants to spend bitcoin utxo set size coin, we can give the person hey here's all the stuff you didn't have, you know it's correct because the hashing matches, now you can update your state and continue block processing.

With lost coins, the issue is that, who has this UTXO set data? How are we going to go and split that up to get a scalability benefit out of this? And, where was I I mean, so the technique that I came up with a while ago was why don't we go and make this insertion-ordered? And what's interesting about insertion-ordered Because obviously people are going to go spend their coins on a regular basis. And the freshly created coins are most likely to correspond to coins that someone is about to actually spend.

The grey ones are dead. But sometimes maybe someone spends an old coin from way back when. But first and bitcoin utxo set size, if you're insertion-ordering, what happens whne you add a new coin to the set? What data do you need to do bitcoin utxo set size If we go back to UTXO set commitments, if we're storing that by the hash of the transaction and the output number, that's essentially a randomly distributed key space because txids are random.

So I oculd end up having bitcoin utxo set size insert data into that data structure almost anywhree. Whereas if you do insertion-ordering, you only need basically the nodes on the right. Because I always know what part of the big data set I'm going to change and add something new to it. Which also means that in addition bitcoin utxo set size this, we have a cache Just like in the UTXO commitment example, someone could still provide you that extra data on demand.

You threw away the data, but you still had verified it. Just like bittorrent lets you download a bitcoin utxo set size from people you don't trust. So we can still get spend data when needed. Oops, where is it, there we go. When that guy finally spends his txo created a year ago, he could provide you with a proof that it is real, and you temporarily go and fill in that and you wind up being able to go record that. Now, here's an interesting observation bitcoin utxo set size.

If we're going to implement all this, which sounds good, we can run nodes with less than the full UTXO set, does this actually need to be a consensus protocol change? Do miners have to do this? I recently realized the answer is no.

We've often been talking about this technique in the wrong way. We think of this as TXO proofs. Proofs that things exist. In reality, when you look at the details of this, if we're basing this on standard data structures that you otherwise build with pointers, we're always tlaking about something where data you pruned away and discarded, that's not really a proof. You're just filling in some details that are missing from someone's database. I'm not proving that something is true. I'm simply helping you to go prove for yourself.

Which then also means, why do we care that miners do any of this? Why can't I just have a full node, that computes what the TXO set commitment would be, computes the hashes of all these states in the database, and hten among my peers, follow a similar protocol and give each other the data that we threw away.

If I want to convince your node that an output from 2 years ago was valid; I am going to give you data that you probably processed at some point but long since discarded. I don't need a miner to do that. I can go do that just between you and me. If miners do this, it's irrelevant to the argument. We could deploy this without a big political fight with guys scattered around the world that might not have our best interests in their hearts. This makes it all the more interesting.

The other interesting thing is that if this is not a consensus protocol change, they can be a lot faster. Mark Friedenbach implemented a UTXO set commitment schemewhere he took the set and hashed it and did state changes, he found that the performance was kind of bad because you're updating this big cryptographic data structure every time a new block came in and you have to do it quickly. Well, if we're not putting this into consensus itself, and we're just doing this locally, then my node can compute the intermediate hashes lazily.

So for instance we're looking at our reently created UTXOs cache example I could keep track bitcoin utxo set size the tree, but I don't have to re-hash anything. I could go treat it like any other pointer-based data structure and then at some point deep in the tree, on the left side, maybe I can keep some of the hashes and then someone else can fill me in on the details later. A peer would give me a small bit of data, bitcoin utxo set size enough to lead to something that in my local copy of the set has a hash attached to it I have implemented htis and I'm going to have to go see if this has any performance improvements.

And finally, the last thing I'd point out with this is that setting up new nodes takes a long time. David talked about how many hours spent re-hashing and re-validating and checking old blockchain data and so on. If you have a commitment to the state of the transaction output set, well, you could go and get the state of that from someone you trust. We recently did this in Bitcoin Core version 0.

My big contribution to that bitcoin utxo set size that I came up with the name. That command line option is also-- we assume a particular blockhash is valid. Rather than rechecking all the signatures leading up to that, which is a big chunk of time of the initial synchronization, we assume that a blockchain you're synchronizing in ends in that particular blockhash, then it skips all the signature validation.

You might think this is a terrible security model-- but remember the default value is part of the Bitcoin Core source code. And if you don't know that the source code isn't being malicious, well it could do anything.

Some 32 byte hash in the middle of the source code which is really easy to audit by just re-running bitcoin utxo set size process of block validation. That's one of your least concerns of potential attacks; if that value is wrong, that's a very obvious thing that people are going to point out. It's much more likely that someone distributing the code would go and make your node do something bad in a more underhanded way. I would argue that assumedvalid is a fair bit bitcoin utxo set size dodgy than assuming miners are honest.

If we implement TXO commitment schemes on the client-side without changing the consensus protocol, and you take advantage of it by having a trusted mechanism to assume that the UTXO state is correct based on state, that's actually a better security bitcoin utxo set size than having miners involved.

In BU, you could assume that miners say something is true then bitcoin utxo set size is bitcoin utxo set size true But I would much rather know who Bitcoin utxo set size am trusting.

Liquid in bottle cinema 4d r16

Buy and sell bitcoin in philippines filipino
Why are plasmids effective vectors in recombinant dna technology quizlet

5 best bitcoin wallet apps for androidthe droid review

Forex trading robot machines

Bitinstant cash deposit to bitcoin address wallet
Recombination repair and direct reversal
Building your own cryptocurrency trading bot using python and the poloniex api

Mip robot black target icon

18 comments

Bitcoin cash on the move again

Also posted to the bitcoin-dev mailing list. Mining is a zero-sum game, so the extra latency of not doing so if they do directly impacts your profit margin. Secondly, having possession of the UTXO set is one of the minimum requirements to run a full node; the larger the set the harder it is to run a full node. Currently the maximum size of the UTXO set is unbounded as there is no consensus rule that limits growth, other than the block-size limit itself; as of writing the UTXO set is 1.

However, making any coins unspendable, regardless of age or value, is a politically untenable economic change. A merkle tree committing to the state of all transaction outputs, both spent and unspent, can provide a method of compactly proving the current state of an output. Both the state of a specific item in the MMR, as well the validity of changes to items in the MMR, can be proven with sized proofs consisting of a merkle path to the tip of the tree.

However, the bandwidth overhead per txin is substantial, so a more realistic implementation is be to have a UTXO cache for recent transactions, with TXO commitments acting as a alternate for the rare event that an old txout needs to be spent. We can take advantage of this by delaying the commitment, allowing it to be calculated well in advance of it actually being used, thus changing a latency-critical task into a much easier average throughput problem.

Concretely each block commits to the TXO set state as of block , in other words what the TXO commitment would have been blocks ago, if not for the block delay. Since that commitment only depends on the contents of the blockchain up until block , the contents of any block after are irrelevant to the calculation. V map of txouts definitely known to be unspent.

Appends must be low-latency; removals can be high-latency. In both cases recording an output as spent requires no more than two key: The existing UTXO set requires one key: This impacts bulk verification, e.

That said, TXO commitments provides other possible tradeoffs that can mitigate impact of slower validation throughput, such as skipping validation of old history, as well as fraud proof approaches.

Each TXO MMR state is a modification of the previous one with most information shared, so we an space-efficiently store a large number of TXO commitments states, where each state is a small delta of the previous state, by sharing unchanged data between each state; cycles are impossible in merkelized data structures, so simple reference counting is sufficient for garbage collection.

Data no longer needed can be pruned by dropping it from the database, and unpruned by adding it again. Now suppose state 2 is committed into the blockchain by the most recent block. Suppose recently created txout f is spent. We have all the data required to update the MMR, giving us state 4. It modifies two inner nodes and one leaf node:. If an archived txout is spent requires the transaction to provide the merkle path to the most recently committed TXO, in our case state 2.

If txout b is spent that means the transaction must provide the following data from state When we mark txout b as spent we get state Secondly by now state 3 has been committed into the chain, and transactions that want to spend txouts created as of state 3 must provide a TXO proof consisting of state 3 data. The leaf nodes for outputs g and h, and the inner node above them, are part of state 3, so we prune them:.

Finally, lets put this all together, by spending txouts a, c, and g, and creating three new txouts i, j, and k. State 3 was the most recently committed state, so the transactions spending a and g are providing merkle paths up to it.

This includes part of the state 2 data:. Again, state 4 related data can be pruned. In addition, depending on how the STXO set is implemented may also be able to prune data related to spent txouts after that state, including inner nodes where all txouts under them have been spent more on pruning spent inner nodes later.

A reasonable approach for the low-level cryptography may be to actually treat the two cases differently, with the TXO commitments committing too what data does and does not need to be kept on hand by the UTXO expiration rules. On the other hand, leaving that uncommitted allows for certain types of soft-forks where the protocol is changed to require more data than it previously did. Inner nodes in the TXO MMR can also be pruned if all leafs under them are fully spent; detecting this is easy if the TXO MMR is a merkle-sum tree 4 , with each inner node committing to the sum of the unspent txouts under it.

When a archived txout is spent the transaction is required to provide a merkle path to the most recent TXO commitment. The first challenge can be handled by specialized archival nodes, not unlike how some nodes make transaction data available to wallets via bloom filters or the Electrum protocol. For a miner though not having the data necessary to update the proofs as blocks are found means potentially losing out on transactions fees. So how much extra data is necessary to make this a non-issue?

The maximum number of relevant inner nodes changed is per block, so if there are non-archival blocks between the most recent TXO commitment and the pending TXO MMR tip, we have to store inner nodes - on the order of a few dozen MB even when n is a seemingly ridiculously high year worth of blocks.

Archived txout spends on the other hand can invalidate TXO MMR proofs at any level - consider the case of two adjacent txouts being spent. To guarantee success requires storing full proofs. Of course, a TXO commitment delay of a year sounds ridiculous. Full nodes would be forced to compute the commitment from scratch, in the same way they are forced to compute the UTXO state, or total work.

A more pragmatic approach is to accept that people will do that anyway, and instead assume that sufficiently old blocks are valid.

That leaves public attempts to falsify TXO commitments, done out in the open by the majority of hashing power. With this in mind, a longer-than-technically-necessary TXO commitment delay 7 may help ensure that full node software actually validates some minimum number of blocks out-of-the-box, without taking shortcuts.

Can a TXO commitment scheme be optimized sufficiently to be used directly without a commitment delay? Is it possible to use a metric other than age, e. For instance it might be reasonable for the TXO commitment proof size to be discounted, or ignored entirely, if a proof-of-propagation scheme e.

How does this interact with fraud proofs? Pettycoin Revisted Part I: Do we really need a mempool? Checkpoints that reject any chain without a specific block are a more common, if uglier, way of achieving this protection. A good homework problem is to figure out how the TXO commitment could be designed such that the delay could be reduced in a soft-fork.

tfc-salamander.com