-MarkM-
Topic: UTXO set size does not increase storage costs, you just suck at computer science - page 2. (Read 3164 times)
March 16, 2013, 09:15:01 AM
Y'know what, don't apologise, those guys really do suck at computer science!
-MarkM-
-MarkM-
March 16, 2013, 09:10:03 AM
We have to share? Darn, I was gonna say I want me one of those 2^51 record databases!
Well, that's just 2^19 records per one of 2^32 humans using Bitcoin... I mean, we are talking about future, right?
Basically, if you own some coins (UTXOs), it is in your interest to keep index records which point to them in your wallet. Then you aren't at mercy of a DHT, you can always prove that you own coins without any external help.
This way all storage costs can be shifted onto users... It's their money, after all.
March 16, 2013, 09:05:48 AM
You know, miners are friendly guys, how about they all use same DHT, and then include confirmation information together with the block they have just mined?
We have to share? Darn, I was gonna say I want me one of those 2^51 record databases!
-MarkM-
March 16, 2013, 08:29:12 AM
Haha, sorry, I didn't mean to offend anyone, I'm just somewhat disappointed that people consider only the simplest solutions and do not want to see a bigger picture.
Let's start with an example... Suppose I am a miner who is in kinda exotic situation: I have unlimited computational and networking resources, and enough temporary storage (RAM) to verify blockchain, but local permanent storage is incredibly scarce. But if I want to store something, I can store it externally over network. Say, in a DHT like Freenet, Tahoe-LAFS or something like that.
So I want to download and scan blockchain up to block N just once, then I need to be able to verify validity of any transaction. Is it possible?
Of course. As I go through blockchain I will build an index and will store it in an external DHT. I only need to keep hash of the latest block locally, 32 bytes that is.
Having this hash, I can retrieve things from DHT until I find transaction outputs I need to verify in index I've built. (I do not care whether DHT is secure: if something was tampered with, hashes won't match.)
This is kinda obvious: if secure distributed file systems can exist, then I can simply store data in such file systems instead of a local file system.
But... how much would it cost me to verify a transaction? Well, tree-like datastructures generally have look-up costs on scale of log2 N where N is a number of elements. In the worst case each individual satoshi is an individual UTXO, so we have 21000000*100000000 = 2100000000000000 ~= 2^51 UTXOs. Thus I need something like 51 lookups to find an UTXO in a binary search tree. Or just 9 lookups if I have a 64-ary tree.
But people can argue that 9 lookups per UTXO is a lot... Network latency yada yada. How about zero?
That's possible. Suppose that person which sends transaction knows how I store index in DHT, it isn't secret. To make sure that I'll include his transaction into block, he will fetch all the data I need from DHT himself, and will send me a message with his transaction and all information I need.
I don't need to look up anything in a DHT myself, I only need data which was stored in the message. And this is secure: if data was tampered with, hash won't match.
So, basically, number of transactions I can include into a block is limited by my computational and network abilities, but storage capability/cost is irrelephant.
But what's about blocks mined by others? Oh...
Well, it is possible to do 9 DHT lookups per UTXO mentioned in block. Number of outputs is limited, I can do lookups in parallel, so it isn't such a big problem. But still...
You know, miners are friendly guys, how about they all use same DHT, and then include confirmation information together with the block they have just mined?
So I receive a new block and supplementary information which is all what is needed to confirm that block is valid.
In the end, it is possible to do all mining having only 32 bytes of permanent secure storage. It requires somewhat more bandwidth, though. But extra bandwidth costs are approximately proportional to block size. So maybe not a big problem...
E.g. I either need 128 GB of RAM, array of hard drives and 100 MBit/sec pipe. Or I need 1 GB of RAM, no hard drives at all and 1 GBit/sec pipe. Which is cheaper?
So what I'm talking about storage/bandwidth trade-off. Using less storage might increase latency, but possible in such a way that it won't be critical.
Next time I will teach you how to implement a blockchain-based cryptocurrency in such a way that new miners can start mining right away without downloading whole blockchain, stay tuned...
Let's start with an example... Suppose I am a miner who is in kinda exotic situation: I have unlimited computational and networking resources, and enough temporary storage (RAM) to verify blockchain, but local permanent storage is incredibly scarce. But if I want to store something, I can store it externally over network. Say, in a DHT like Freenet, Tahoe-LAFS or something like that.
So I want to download and scan blockchain up to block N just once, then I need to be able to verify validity of any transaction. Is it possible?
Of course. As I go through blockchain I will build an index and will store it in an external DHT. I only need to keep hash of the latest block locally, 32 bytes that is.
Having this hash, I can retrieve things from DHT until I find transaction outputs I need to verify in index I've built. (I do not care whether DHT is secure: if something was tampered with, hashes won't match.)
This is kinda obvious: if secure distributed file systems can exist, then I can simply store data in such file systems instead of a local file system.
But... how much would it cost me to verify a transaction? Well, tree-like datastructures generally have look-up costs on scale of log2 N where N is a number of elements. In the worst case each individual satoshi is an individual UTXO, so we have 21000000*100000000 = 2100000000000000 ~= 2^51 UTXOs. Thus I need something like 51 lookups to find an UTXO in a binary search tree. Or just 9 lookups if I have a 64-ary tree.
But people can argue that 9 lookups per UTXO is a lot... Network latency yada yada. How about zero?
That's possible. Suppose that person which sends transaction knows how I store index in DHT, it isn't secret. To make sure that I'll include his transaction into block, he will fetch all the data I need from DHT himself, and will send me a message with his transaction and all information I need.
I don't need to look up anything in a DHT myself, I only need data which was stored in the message. And this is secure: if data was tampered with, hash won't match.
So, basically, number of transactions I can include into a block is limited by my computational and network abilities, but storage capability/cost is irrelephant.
But what's about blocks mined by others? Oh...
Well, it is possible to do 9 DHT lookups per UTXO mentioned in block. Number of outputs is limited, I can do lookups in parallel, so it isn't such a big problem. But still...
You know, miners are friendly guys, how about they all use same DHT, and then include confirmation information together with the block they have just mined?
So I receive a new block and supplementary information which is all what is needed to confirm that block is valid.
In the end, it is possible to do all mining having only 32 bytes of permanent secure storage. It requires somewhat more bandwidth, though. But extra bandwidth costs are approximately proportional to block size. So maybe not a big problem...
E.g. I either need 128 GB of RAM, array of hard drives and 100 MBit/sec pipe. Or I need 1 GB of RAM, no hard drives at all and 1 GBit/sec pipe. Which is cheaper?
So what I'm talking about storage/bandwidth trade-off. Using less storage might increase latency, but possible in such a way that it won't be critical.
Next time I will teach you how to implement a blockchain-based cryptocurrency in such a way that new miners can start mining right away without downloading whole blockchain, stay tuned...
Jump to: