Pages:
Author

Topic: Ultimate blockchain compression w/ trust-free lite nodes (Read 87932 times)

legendary
Activity: 1358
Merit: 1003
Ron Gross
FYI - Back in 2012 there was a [bounty of 5.725 BTC](https://bitcointalksearch.org/topic/pledging-coins-for-ultimate-blockchain-compression-93606) (& eventually BCH) dedicated to this project, to which I'm the custodian of.
As nobody claimed the bounty, I plan to find a suitable project or projects that deal with Bitcoin Scalability and transfer the coins to them.

Check out the bounty thread for updates, I expect a decision to be made within a couple of weeks.
newbie
Activity: 10
Merit: 0
Is there a plan to deal with parties that want to store arbitrary data in the blockchain? Right now, OP_RETURN is used as a way to prevent non-financial data from bloating UTXO trees. However, if someone wants to store arbitrary data in the blockchain, ultimate blockchain c*mpression might encourage them to store this data by using fake addresses, because that way they would get much faster lookups and they could basically use this to build an efficient key-value store. Is this just accepted as something that will inevitably happen?
legendary
Activity: 905
Merit: 1012
No offense, but I'm not sure you understand "UTXO" well enough to explain it to others. For starters, UTXO is nothing new, this post is about "committed utxo". As maaku explained, miners need to know that they're mining on top of the valid chain, that's the only way they can know they have the accurate UTXO.

maaku confirmed that I understood UTXO's SPV+ mode.

Jorge is correct: miners have to know they are building on top of a valid chain, and to do that they need to validate the entire block chain history. The post you linked to endorsed a statement which included this caveat, which your most recent explanation does not.
legendary
Activity: 1372
Merit: 1002
maaku confirmed that I understood UTXO's SPV+ mode.

Maybe you understand it, I don't know, but some of the terms you were using are unusual and I thought some people could get confused, that's all.
newbie
Activity: 58
Merit: 0
No offense, but I'm not sure you understand "UTXO" well enough to explain it to others. For starters, UTXO is nothing new, this post is about "committed utxo". As maaku explained, miners need to know that they're mining on top of the valid chain, that's the only way they can know they have the accurate UTXO.

maaku confirmed that I understood UTXO's SPV+ mode.
legendary
Activity: 1372
Merit: 1002
I'm not sure who misunderstands. I'll try to rephrase.

Here's the core of my question - does the system (all nodes) forget a prefix of the chain at some point?

If a node reads the entire chain (from genesis), it can prune it locally, sure. But how does a new node bootstrap without the entire chain? It needs to trust a snapshot (rolling root, utxo block, whatever it's called). That's my issue.

Rolling root and UTXO are very different architecturally, so I'll just answer for UTXO here.

Nobody, whether it's new nodes or old nodes, needs to know the entire histories of coins. The only thing that matters is whether they have the accurate unspent transactions.

New nodes download the entire UTXO meta chain (step #2 in the summary I posted earlier). This chain is protected by PoW. That's it. By knowing the accurate UTXO tree fingerprint, they can safely build the UTXO tree.

No offense, but I'm not sure you understand "UTXO" well enough to explain it to others. For starters, UTXO is nothing new, this post is about "committed utxo".
As maaku explained, miners need to know that they're mining on top of the valid chain, that's the only way they can know they have the accurate UTXO.

I don't think validity of commitment touches validity of Bitcoin block. Bitcoin nodes are allowed to completely ignore this merge-mined chain.

There's two ways to implement this: as a merged mined chain or as a softfork. The soft fork would invalidate blocks with an invalid utxo root, with the merged mined chain their validity is independent. I prefer the second option, the mini-chain just seems like a mechanism to deploy it, but until you make the soft fork this is not that useful.

Then these Bitcoin nodes (aka Bitcoin) should not truncate the chain. When you truncate up to some point you trust that you have a valid snapshot up to this time. There is no way to verify the UTXO chain (in the sense that there can be missing transactions) once the prefix is gone. So if someone manages to slip an invalid utxo into the blockchain, and this error is discovered after the prefix is gone, it invalidates every node that forgets prefixes.

So it could work as a fast-bootstrapping probably-reliable mechanism for your home PC. Something between SPV and full wallet. But to be done in full nodes the snapshot mechanism has to be incorporated in the blockchain.

Not sure what you mean by "prefix" here, it seems you mean the past chain.
With committed utxo SPV nodes can be much more secure, but full nodes still need to fully validate the chain (otherwise they would have SPV security, not full node security).
newbie
Activity: 4
Merit: 0
I don't think validity of commitment touches validity of Bitcoin block. Bitcoin nodes are allowed to completely ignore this merge-mined chain.

Then these Bitcoin nodes (aka Bitcoin) should not truncate the chain. When you truncate up to some point you trust that you have a valid snapshot up to this time. There is no way to verify the UTXO chain (in the sense that there can be missing transactions) once the prefix is gone. So if someone manages to slip an invalid utxo into the blockchain, and this error is discovered after the prefix is gone, it invalidates every node that forgets prefixes.

So it could work as a fast-bootstrapping probably-reliable mechanism for your home PC. Something between SPV and full wallet. But to be done in full nodes the snapshot mechanism has to be incorporated in the blockchain.
member
Activity: 114
Merit: 12
Ok, I'm convinced. As long as the UTXO meta chain is verified by the system, that's fine. I thought initially that it's a separately maintained data structure. If it's integrated in the Blockchain, in the sense that an invalid utxo would cause the entire Blockchain block to be rejected, then it's fine. In this case you're not adding any principles to rely on, and security is essentially intact as far as I see.



I don't think validity of commitment touches validity of Bitcoin block. Bitcoin nodes are allowed to completely ignore this merge-mined chain.
newbie
Activity: 4
Merit: 0
New nodes download the entire UTXO meta chain (step #2 in the summary I posted earlier). This chain is protected by PoW. That's it. By knowing the accurate UTXO tree fingerprint, they can safely build the UTXO tree.

Ok, I'm convinced. As long as the UTXO meta chain is verified by the system, that's fine. I thought initially that it's a separately maintained data structure. If it's integrated in the Blockchain, in the sense that an invalid utxo would cause the entire Blockchain block to be rejected, then it's fine. In this case you're not adding any principles to rely on, and security is essentially intact as far as I see.

newbie
Activity: 58
Merit: 0
I'm not sure who misunderstands. I'll try to rephrase.

Here's the core of my question - does the system (all nodes) forget a prefix of the chain at some point?

If a node reads the entire chain (from genesis), it can prune it locally, sure. But how does a new node bootstrap without the entire chain? It needs to trust a snapshot (rolling root, utxo block, whatever it's called). That's my issue.

Rolling root and UTXO are very different architecturally, so I'll just answer for UTXO here.

Nobody, whether it's new nodes or old nodes, needs to know the entire histories of coins. The only thing that matters is whether they have the accurate unspent transactions.

New nodes download the entire UTXO meta chain (step #2 in the summary I posted earlier). This chain is protected by PoW. That's it. By knowing the accurate UTXO tree fingerprint, they can safely build the UTXO tree.
newbie
Activity: 4
Merit: 0
I'm not sure who misunderstands. I'll try to rephrase.

Here's the core of my question - does the system (all nodes) forget a prefix of the chain at some point?

If a node reads the entire chain (from genesis), it can prune it locally, sure. But how does a new node bootstrap without the entire chain? It needs to trust a snapshot (rolling root, utxo block, whatever it's called). That's my issue.
newbie
Activity: 58
Merit: 0
I guess I'm not sure what's the ultimate goal of this. Do you want to actually prune the Blockchain prefix at some point, or is this just a mechanism to speed up bootstrapping? My feeling is that this mechanism is secure enough for the latter cause, but not for the former.

What do you mean "not for the former"? This scheme would make the prefix irrelevant. If you don't care about the history of those coins there's no issue (that I can see).

Quote
To verify that a UTXO set i includes all utxo's, the verifier has to go back to the latest UTXO set it trusts j and make sure there are no missing outputs between j and i. There is no way to do that once the Blockchain get pruned at i.

Technically, it's possible to lose utxo's this way, if the network wrongfully accepts a partial UTXO set and prunes the prefix. That being said, it's quite difficult to take advantage of this vulnerability, so I think it is viable for fast bootstrapping.

Or perhaps I'm missing a part of the mechanism? Please correct me if I'm wrong.

I think either I've misunderstood what you're saying here, or you've misunderstood the how this would work. Please let me know either way.

Once a node has a complete UTXO tree that corresponds to the most recently accepted block, there should be no problems from that point on. It does not go to the UTXO to verify much of anything, but merely updates it based on newly minted blocks.

The blockchain can be pruned locally according to any lossless scheme the node desires. The only place I see a potential issue is if there's a reorganization (a different fork suddenly exceeds the current in length). If that happens, and the node pruned too closely to the current time, then it might not know how to safely deal with the reorg event. To mitigate against this, nodes can keep a blockchain prefix of sufficient length.
newbie
Activity: 4
Merit: 0
I guess I'm not sure what's the ultimate goal of this. Do you want to actually prune the Blockchain prefix at some point, or is this just a mechanism to speed up bootstrapping? My feeling is that this mechanism is secure enough for the latter cause, but not for the former.

To verify that a UTXO set i includes all utxo's, the verifier has to go back to the latest UTXO set it trusts j and make sure there are no missing outputs between j and i. There is no way to do that once the Blockchain get pruned at i.

Technically, it's possible to lose utxo's this way, if the network wrongfully accepts a partial UTXO set and prunes the prefix. That being said, it's quite difficult to take advantage of this vulnerability, so I think it is viable for fast bootstrapping.

Or perhaps I'm missing a part of the mechanism? Please correct me if I'm wrong.
newbie
Activity: 58
Merit: 0
I don't know of anyone besides me who is still working on UTXO commitments. It is developer time limited right now since for about six months I've been split between multiple projects trying to make ends meet. I posted a summary of the current state earlier in this thread, and any bitcoins or bitcoind developers would be appreciated in speeding the process along.

Mmmk, sent ya a PM.
legendary
Activity: 905
Merit: 1012
I don't know of anyone besides me who is still working on UTXO commitments. It is developer time limited right now since for about six months I've been split between multiple projects trying to make ends meet. I posted a summary of the current state earlier in this thread, and any bitcoins or bitcoind developers would be appreciated in speeding the process along.
newbie
Activity: 58
Merit: 0
That appears to be a correct description of SPV+ mode.

OK cool, thanks maaku for reviewing it! Smiley

Then it sounds like UTXO / SPV+ is a solution to the long running problem of safely and quickly bringing new bitcoin nodes online. That's really great news if true! Cheesy

So who's working on this? I haven't seen etotheipi post anything recently, is he still working on it? Does he still need donations?
legendary
Activity: 905
Merit: 1012
That appears to be a correct description of SPV+ mode.
newbie
Activity: 58
Merit: 0
Erm, just a note, I forgot to remove Step 7 when I copied that post:

Quote
7. Continue mining blocks as per above to secure the network and build new blocks, slowly transforming this light node into a full node.

I deleted that. Mining will commence only *after* our local UTXO merkle tree thing has be completed.
newbie
Activity: 58
Merit: 0
I think it would be helpful (in general) for me to paste here my updated understanding of how these "full-security new lite-nodes" would be booted up:

Quote
For a new node to boot up from scratch and begin securing the network, approximately the following needs to happen:

1. Download entire BTC blockchain headers.
2. Download the entire UTXO meta chain.
3. Begin merged mining on UTXO and BTC blockchains. begin mining *only* when we've built up the complete UTXO tree.
4. For each new transaction the "almost-full node" receives, query other nodes for the block in which the payer's bitcoins were previously located, along with the hashes to verify the merkle root in the BTC blockchain. Verify the root can be found. Edit: This part is just regular SPV!
5. Query other nodes for the transactions and merkle root hashes that result in the merkle root hash of the most recent block in the UTXO blockchain. Verify that previous txn the coins belong to exists in the current data comprising the most recent merkle root of the UTXO blockchain.
6. If the transaction passes the above verifications, store all received data so far in order to build the Merkle hash tree that represents all the UTXOs.

To build the complete UTXO tree, ask for any missing children of our current UTXO merkle tree and verify them according to the above.
member
Activity: 110
Merit: 10
If the client has a built-in feature that takes a checkpoint of the UTXO every so often based on the longest valid blockchain, and the code for that feature is well documented and understood, then I think there would be no problem with trusting the built-in UTXO checkpoints.
Pages:
Jump to: