cypherdoc (OP)
Legendary
Offline
Activity: 1764
Merit: 1002
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 04:32:54 PM |
|
the question is, where is that point? This is not a question we can answer. The right approach is to build a machine for constantly discovering the answer to that question in real time a.k.a a market. the other thing i don't understand is doesn't the miner who has received a valid header from another miner still have to wait for the tx's themselves to show up so he can remove them from the UTXO set before constructing the next block? Presumably you assume the miners have already seen the transactions before they see the Merkle tree, and they've seen the Merkle tree before they see the header. People who want their transactions processed, and miners who want their headers to propagate, have an incentive to make sure it is so. i think the UTXO set will have to have a pre-agreed order that will need to be synced amongst all miners in real-time. then, the successful miner can publish the header hash along with some signal as to how far down in that list he went before he stopped adding tx's. then, all other miners will know how to verify the published header hash and remove those tx's from the utxo set before moving on to the next block.
|
|
|
|
justusranvier
Legendary
Offline
Activity: 1400
Merit: 1013
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 04:39:40 PM |
|
i think the UTXO set will have to have a pre-agreed order that will need to be synced amongst all miners in real-time. What if the UTXO set itself is a structure that gets merge-mined with the blocks themselves?
|
|
|
|
flipperfish
Sr. Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 350
Merit: 251
Dolphie Selfie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 04:41:09 PM |
|
i think the UTXO set will have to have a pre-agreed order that will need to be synced amongst all miners in real-time. then, the successful miner can publish the header hash along with some signal as to how far down in that list he went before he stopped adding tx's. then, all other miners will know how to verify the published header hash and remove those tx's from the utxo set before moving on to the next block.
Yes, as I understand it, the trick is the deterministic order. The "signal as to how far down in that list" is the thing gavin tweeted about.
|
|
|
|
cypherdoc (OP)
Legendary
Offline
Activity: 1764
Merit: 1002
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 04:43:35 PM |
|
i think the UTXO set will have to have a pre-agreed order that will need to be synced amongst all miners in real-time. What if the UTXO set itself is a structure that gets merge-mined with the blocks themselves? iirc, the utxo set takes up about 75% of RAM required to run a node. as i run 4 nodes myself, it takes a minimum of 1GB RAM to run smoothly meaning 750MB could be estimated for the utxo set itself. that's pretty big to be including in a block...
|
|
|
|
justusranvier
Legendary
Offline
Activity: 1400
Merit: 1013
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 04:44:49 PM |
|
iirc, the utxo set takes up about 75% of RAM required to run a node. as i run 4 nodes myself, it takes a minimum of 1GB RAM to run smoothly meaning 750MB could be estimated for the utxo set itself. that's pretty big to be including in a block... Not in the block, alongside the block. Just like when people merge mine Namecoin the nmc blocks aren't included in the btc blocks.
|
|
|
|
|
cypherdoc (OP)
Legendary
Offline
Activity: 1764
Merit: 1002
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 04:45:12 PM |
|
i think the UTXO set will have to have a pre-agreed order that will need to be synced amongst all miners in real-time. then, the successful miner can publish the header hash along with some signal as to how far down in that list he went before he stopped adding tx's. then, all other miners will know how to verify the published header hash and remove those tx's from the utxo set before moving on to the next block.
Yes, as I understand it, the trick is the deterministic order. The "signal as to how far down in that list" is the thing gavin tweeted about. how reliable is a synced utxo set across all miners?
|
|
|
|
cypherdoc (OP)
Legendary
Offline
Activity: 1764
Merit: 1002
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 04:46:36 PM |
|
nah, miners who aren't paying attention, maybe. but not the protocol itself.
|
|
|
|
cypherdoc (OP)
Legendary
Offline
Activity: 1764
Merit: 1002
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 04:47:11 PM |
|
iirc, the utxo set takes up about 75% of RAM required to run a node. as i run 4 nodes myself, it takes a minimum of 1GB RAM to run smoothly meaning 750MB could be estimated for the utxo set itself. that's pretty big to be including in a block... Not in the block, alongside the block. Just like when people merge mine Namecoin the nmc blocks aren't included in the btc blocks. why would you do that?
|
|
|
|
domob
Legendary
Offline
Activity: 1135
Merit: 1170
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 05:29:13 PM |
|
iirc, the utxo set takes up about 75% of RAM required to run a node. as i run 4 nodes myself, it takes a minimum of 1GB RAM to run smoothly meaning 750MB could be estimated for the utxo set itself. that's pretty big to be including in a block... Not in the block, alongside the block. Just like when people merge mine Namecoin the nmc blocks aren't included in the btc blocks. why would you do that? I may be mistaken, but isn't this basically what the "ultimate UTXO pruning" thing is about? As far as I have heard, it allows new clients to be synced almost immediately (at least a lot faster than when downloading the full chain) with less required trust than SPV clients and the like (or even almost the same trustless-ness as a full node?). I've never really dived into the details, though.
|
Use your Namecoin identity as OpenID: https://nameid.org/Donations: 1 domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NC domobcmcmVdxC5yxMitojQ4tvAtv99pY BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS | GPG 0xA7330737
|
|
|
flipperfish
Sr. Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 350
Merit: 251
Dolphie Selfie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 05:41:33 PM |
|
i think the UTXO set will have to have a pre-agreed order that will need to be synced amongst all miners in real-time. then, the successful miner can publish the header hash along with some signal as to how far down in that list he went before he stopped adding tx's. then, all other miners will know how to verify the published header hash and remove those tx's from the utxo set before moving on to the next block.
Yes, as I understand it, the trick is the deterministic order. The "signal as to how far down in that list" is the thing gavin tweeted about. how reliable is a synced utxo set across all miners? I don't think it is the utxo set, that has to be in an deterministic order, but the txs in the mempool. The utxo set is a result of the valid blockchain, so it should be synchronized already (except a node regards a block as valid, which later will become orphaned). Gavin proposed to use "Invertible Bloom Lookup Tables". The lookup table tells the miner which transactions from its mempool should be considered for the verification of the published blockheader. Because now the miner knows which txs are used to form the block and in which order, he can reconstruct the merkle root and compare that against the published blockheader. However the proposed "Invertible Bloom Lookup Tables" are not 100% reliable. From a quick glance at the paper I found, that about <1% of keys are lost during an experiment with 10000 keys. Keys can be seen as txs in this case. Now I ask myself what happens in case of the remaining 1%? Maybe the failure rate can be reduced by publishing multiple lookup tables of the same set?
|
|
|
|
sidhujag
Legendary
Offline
Activity: 2044
Merit: 1005
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 06:01:16 PM |
|
iirc, the utxo set takes up about 75% of RAM required to run a node. as i run 4 nodes myself, it takes a minimum of 1GB RAM to run smoothly meaning 750MB could be estimated for the utxo set itself. that's pretty big to be including in a block... Not in the block, alongside the block. Just like when people merge mine Namecoin the nmc blocks aren't included in the btc blocks. The merged-mine implementations that don't include the memory fix: (mutable vs imutable storage) and no auxpow data in cblockindex (blocks stored in memory) will eat up alot of RAM... so far only Devcoin and I0coin are the ones that have this fix and only Devcoin is running on 0.9.2 (currently in testing) with all the other fixes that bitcoin rolled up along the way included. So for most of these incompatible alt-coins who now wish to merge-mine (because I called that they would, and the ones that dont will die) are now suffering from either memory bloat issues or incorrect implementions/bugs and its next to impossible for a general programmer to port it over because its increasingly convoluted code to keep track of.
|
|
|
|
cypherdoc (OP)
Legendary
Offline
Activity: 1764
Merit: 1002
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 06:04:19 PM |
|
iirc, the utxo set takes up about 75% of RAM required to run a node. as i run 4 nodes myself, it takes a minimum of 1GB RAM to run smoothly meaning 750MB could be estimated for the utxo set itself. that's pretty big to be including in a block... Not in the block, alongside the block. Just like when people merge mine Namecoin the nmc blocks aren't included in the btc blocks. The merged-mine implementations that don't include the memory fix: (mutable vs imutable storage) and no auxpow data in cblockindex (blocks stored in memory) will eat up alot of RAM... so far only Devcoin and I0coin are the ones that have this fix and only Devcoin is running on 0.9.2 (currently in testing) with all the other fixes that bitcoin rolled up along the way included. So for most of these incompatible alt-coins who now wish to merge-mine (because I called that they would, and the ones that dont will die) are now suffering from either memory bloat issues or incorrect implementions/bugs and its next to impossible for a general programmer to port it over because its increasingly convoluted code to keep track of. which is exactly why i've been warning everyone about these leech coins or sidechains that wish to piggyback themselves onto the Bitcoin mining network to secure themselves.
|
|
|
|
sidhujag
Legendary
Offline
Activity: 2044
Merit: 1005
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 06:36:11 PM |
|
iirc, the utxo set takes up about 75% of RAM required to run a node. as i run 4 nodes myself, it takes a minimum of 1GB RAM to run smoothly meaning 750MB could be estimated for the utxo set itself. that's pretty big to be including in a block... Not in the block, alongside the block. Just like when people merge mine Namecoin the nmc blocks aren't included in the btc blocks. The merged-mine implementations that don't include the memory fix: (mutable vs imutable storage) and no auxpow data in cblockindex (blocks stored in memory) will eat up alot of RAM... so far only Devcoin and I0coin are the ones that have this fix and only Devcoin is running on 0.9.2 (currently in testing) with all the other fixes that bitcoin rolled up along the way included. So for most of these incompatible alt-coins who now wish to merge-mine (because I called that they would, and the ones that dont will die) are now suffering from either memory bloat issues or incorrect implementions/bugs and its next to impossible for a general programmer to port it over because its increasingly convoluted code to keep track of. which is exactly why i've been warning everyone about these leech coins or sidechains that wish to piggyback themselves onto the Bitcoin mining network to secure themselves. Well merged-mining is still better than POS, and now with LTC asics you have scrypt merged-miners aswell... I think its a great thing. But those that have strong dev communites will survive. With Devcoin since its address compatible with bitcoin its more of a trivial task to keep the port and then the thin clients and external tools all just work... it was a smart decision to do so... so it really is a viable alternative but others may not be so lucky a few years down the road with some major structural changes to the codebase. I would much rather support merged-mine coins over some random pos coin because of the inability of those pos coins to keep up with the development power of bitcoin. If you think about it conceptually from a bigger picture.. none of these alts can exist without bitcoin anyway, so it makes sense that without bitcoin hash power they would simply be not secure... but they are flexible to find another high hash parent if that ever happens.
|
|
|
|
domob
Legendary
Offline
Activity: 1135
Merit: 1170
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 06:59:28 PM |
|
iirc, the utxo set takes up about 75% of RAM required to run a node. as i run 4 nodes myself, it takes a minimum of 1GB RAM to run smoothly meaning 750MB could be estimated for the utxo set itself. that's pretty big to be including in a block... Not in the block, alongside the block. Just like when people merge mine Namecoin the nmc blocks aren't included in the btc blocks. The merged-mine implementations that don't include the memory fix: (mutable vs imutable storage) and no auxpow data in cblockindex (blocks stored in memory) will eat up alot of RAM... so far only Devcoin and I0coin are the ones that have this fix and only Devcoin is running on 0.9.2 (currently in testing) with all the other fixes that bitcoin rolled up along the way included. So for most of these incompatible alt-coins who now wish to merge-mine (because I called that they would, and the ones that dont will die) are now suffering from either memory bloat issues or incorrect implementions/bugs and its next to impossible for a general programmer to port it over because its increasingly convoluted code to keep track of. Note that Namecoin also doesn't keep the auxpow in memory (CBlockIndex) or in the blkindex.dat file any longer. I have removed this artefact (from times before I hacked on the code) recently.
|
Use your Namecoin identity as OpenID: https://nameid.org/Donations: 1 domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NC domobcmcmVdxC5yxMitojQ4tvAtv99pY BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS | GPG 0xA7330737
|
|
|
sidhujag
Legendary
Offline
Activity: 2044
Merit: 1005
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 07:07:13 PM |
|
iirc, the utxo set takes up about 75% of RAM required to run a node. as i run 4 nodes myself, it takes a minimum of 1GB RAM to run smoothly meaning 750MB could be estimated for the utxo set itself. that's pretty big to be including in a block... Not in the block, alongside the block. Just like when people merge mine Namecoin the nmc blocks aren't included in the btc blocks. The merged-mine implementations that don't include the memory fix: (mutable vs imutable storage) and no auxpow data in cblockindex (blocks stored in memory) will eat up alot of RAM... so far only Devcoin and I0coin are the ones that have this fix and only Devcoin is running on 0.9.2 (currently in testing) with all the other fixes that bitcoin rolled up along the way included. So for most of these incompatible alt-coins who now wish to merge-mine (because I called that they would, and the ones that dont will die) are now suffering from either memory bloat issues or incorrect implementions/bugs and its next to impossible for a general programmer to port it over because its increasingly convoluted code to keep track of. Note that Namecoin also doesn't keep the auxpow in memory (CBlockIndex) or in the blkindex.dat file any longer. I have removed this artefact (from times before I hacked on the code) recently. You still need it in blnkindex.dat unless you dont care about not having any thin clients or external clients using "getheaders"
|
|
|
|
justusranvier
Legendary
Offline
Activity: 1400
Merit: 1013
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 07:13:37 PM |
|
why would you do that? https://bitcointalk.org/index.php?topic=88208.0If it ever becomes possible to do so without risking the integrity of the ledger, I would like Bitcoin to be able to discard transaction history. Right now storing 100% of history is the easiest way to safeguard the ledger, but it also means we're subsidizing surveillance. In a perfect world we'd only need to keep a P2P-validated UTXO set and enough history to detect tampering, and let the people who want to store everything forever so they can perform graph analysis pay for that themselves.
|
|
|
|
molecular
Donator
Legendary
Offline
Activity: 2772
Merit: 1019
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 07:16:23 PM |
|
i think the UTXO set will have to have a pre-agreed order that will need to be synced amongst all miners in real-time. then, the successful miner can publish the header hash along with some signal as to how far down in that list he went before he stopped adding tx's. then, all other miners will know how to verify the published header hash and remove those tx's from the utxo set before moving on to the next block.
Yes, as I understand it, the trick is the deterministic order. The "signal as to how far down in that list" is the thing gavin tweeted about. how reliable is a synced utxo set across all miners? I don't think it is the utxo set, that has to be in an deterministic order, but the txs in the mempool. The utxo set is a result of the valid blockchain, so it should be synchronized already (except a node regards a block as valid, which later will become orphaned). Gavin proposed to use "Invertible Bloom Lookup Tables". The lookup table tells the miner which transactions from its mempool should be considered for the verification of the published blockheader. Because now the miner knows which txs are used to form the block and in which order, he can reconstruct the merkle root and compare that against the published blockheader. However the proposed "Invertible Bloom Lookup Tables" are not 100% reliable. From a quick glance at the paper I found, that about <1% of keys are lost during an experiment with 10000 keys. Keys can be seen as txs in this case. I just read the relevant parts of a paper explaining ITLB (Invertible Bloom Lookup Tables)... quite an interesting data structure. It has a constant size (pre-chosen) and allows storing (key, value) pairs. "insert" and "delete" operations are efficient. "get" may fail and "list" may return partial results. I can see how an ITLB of some constant size might be used for block announcements by miners. Some things I don't quite get, though: - why does this require deterministic ordering of txs in mempool?
- does this require that all txs a miner includes in a block are properly broadcast beforehand?
- would this require a hardfork or can it be used off-chain (so to say) by a subgroup of willing miners?
Now I ask myself what happens in case of the remaining 1%? Maybe the failure rate can be reduced by publishing multiple lookup tables of the same set?
maybe the publishing miner can include the 1% explicitly (he can determine which ones are affected himself and include the remainder). This would destroy the "constant size" property, but it would lessen the propagation cost of block size by ~99%, right?
|
PGP key molecular F9B70769 fingerprint 9CDD C0D3 20F8 279F 6BE0 3F39 FC49 2362 F9B7 0769
|
|
|
flipperfish
Sr. Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 350
Merit: 251
Dolphie Selfie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 09:56:30 PM |
|
Some things I don't quite get, though: - why does this require deterministic ordering of txs in mempool?
- does this require that all txs a miner includes in a block are properly broadcast beforehand?
- would this require a hardfork or can it be used off-chain (so to say) by a subgroup of willing miners?
1) This is needed to construct the merkle tree. Txs are grouped pairwise to build the nodes of the next level in the tree. The pairs are concatenated for the hashing, so the order is relevant. Currently the order is defined by the list of txs in the published block. 2) Yes, although I think the receiving miner could request missing tx(s). 3) To my understanding this does not need a hardfork, because the blocks are still built by the same rules. Now I ask myself what happens in case of the remaining 1%? Maybe the failure rate can be reduced by publishing multiple lookup tables of the same set?
maybe the publishing miner can include the 1% explicitly (he can determine which ones are affected himself and include the remainder). This would destroy the "constant size" property, but it would lessen the propagation cost of block size by ~99%, right? Ah, of course, this makes sense!
|
|
|
|
cypherdoc (OP)
Legendary
Offline
Activity: 1764
Merit: 1002
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2014, 10:55:21 PM |
|
Hey look!
Dow goes up, Dow goes down, gold goes up, gold goes down. Meanwhile;
Bitcoin goes UP!
|
|
|
|
|