Bitcoin Target Calculator - How Does Bitcoin Mining Work?

Great interview questions for bitcoin engineers

From here...
https://bitcointalk.org/index.php?topic=5006583.0
Questions. Chapter 1: Introduction 1. What are the main Bitcoin terms? 2. What is a Bitcoin address? 3. What is a Bitcoin transaction? 4. What is a Bitcoin block? 5. What is a Bitcoin blockchain? 6. What is a Bitcoin transaction ledger? 7. What is a Bitcoin system? What is a bitcoin (cryptocurrency)? How are they different? 8. What is a full Bitcoin stack? 9. What are two types of issues that digital money have to address? 10. What is a “double-spend” problem? 11. What is a distributed computing problem? What is the other name of this problem? 12. What is an election? 13. What is a consensus? 14. What is the name of the main algorithm that brings the bitcoin network to the consensus? 15. What are the different types of bitcoin clients? What is the difference between these clients? Which client offers the most flexibility? Which client offers the least flexibility? Which client is the most and least secure? 16. What is a bitcoin wallet? 17. What is a confirmed transaction and what is an unconfirmed transaction? Chapter 2: How Bitcoin works. 1. What is the best way to understand transactions in the Bitcoin network? 2. What is a transaction? What does it contain? What is the similarity of a transaction to a double entry ledger? What does input correspond to? What does output correspond to? 3. What are the typical transactions in the bitcoin network? Could you please name three of such transactions and give examples of each type of the transaction? 4. What is a QR and how it is used in the Bitcoin network? Are there different types of QRs? If so, what are the different types? Which type is more informational? What kind of information does it provide? 5. What is SPV? What does this procedure check and what type of clients of the Bitcoin network usually use this procedure? Chapter 3: The Bitcoin client. 1. How to download and install the Core Bitcoin client? 2. What is the best way to test the API available for the Core Bitcoin client without actually programming? What is the interface called? 3. What are the major areas of operations in the Bitcoin client? What can we do with the client? 4. What are the available operations for the Bitcoin addresses? 5. What are the available read operations for the Bitcoin transactions? How is a transaction encoded in the Bitcoin network? What is a raw transaction and what is a decoded transaction? 6. If I want to get information about a transaction that is not related to any address in my own wallet, do I need to change anything in the Bitcoin client configuration? If yes, which option do I need to modify? 7. What are the available read operation for the Bitcoin blocks? 8. What are the available operations for the creation of the transactions in the Bitcoin network? 9. How do you normally need to address the unspent output from the previous transaction in order to use it as an input for a new transaction? 10. What is the mandatory operation after creating a new transaction and before sending this new transaction to the network? What state does the wallet have to be in order to perform this operation? 11. Is the transaction ID immutable (TXID)? If not why, if yes, why and when? 12. What does signing a transaction mean? 13. What are the other options for Bitcoin clients? Are there any libraries that are written for some specific languages? What types of clients do these libraries implement? Chapter 4: Keys, Addresses and Wallets. 1. What is a PKC? When it was developed? What are the main mathematical foundations or functions that PKC is using? 2. What is ECC? Could you please provide the formula of the EC? What is the p and what is the Fp? What are the defined operations in ECC? What is a “point to infinity”? 3. What is a Bitcoin wallet? Does this wallet contain coins? If not, what does it contain then? 4. What is a BIP? What it is used for? 5. What is an encrypted private key? Why would we want to encrypt private keys? 6. What is a paper wallet? What kind of storage it is an example of? 7. What is a nondeterministic wallet? Is it a good wallet or a bad wallet? Could you justify? 8. What is a deterministic wallet? 9. What is an HD wallet? 10. How many keys are needed for one in and out transaction? What is a key pair? Which keys are in the key pair? 11. How many keys are stored in a wallet? 12. How does a public key gets created in Bitcoin? What is a “generator point”? 13. Could you please show on a picture how ECC multiplication is done? 14. How does a private key gets created in Bitcoin? What we should be aware of when creating a new private key? What is CSPRNG? What kind of input should this function be getting? 15. What is a WIF? What is WIF-Compressed? 16. What is Base58 encoding and what is Base58Check encoding? How it is different from Base64 encoding? Which characters are used in Base58? Why Base58Check was invented? What kind of problems does it solve? How is Base58Check encoding is created from Base58 encoding? 17. How can Bitcoin addresses be encoded? Which different encodings are used? Which key is used for the address creation? How is the address created? How this key is used and what is the used formula? 18. Can we visually distinguish between different keys in Base58Check format? If yes, how are they different from each other? What kind of prefixes are used? Could you please provide information about used prefixes for each type of the key? 19. What is an index in HD wallets? How many siblings can exist for a parent in an HD wallet? 20. What is the depth limitation for an HD wallet key hierarchy? 21. What are the main two advantages of an HD wallet comparing to the nondeterministic wallets? 22. What are the risks of non-hardened keys creation in an HD wallet? Could you please describe each of them? 23. What is a chain code in HD wallets? How many different chain code types there are? 24. What is the mnemonic code words? What are they used for? 25. What is a seed in an HD wallet? Is there any other name for it? 26. What is an extended key? How long is it and which parts does it consist of? 27. What is P2SH address? What function are P2SH addresses normally used for? Is that correct to call P2SH address a multi-sig address? Which BIP suggested using P2SH addresses? 28. What is a WIF-compressed private key? Is there such a thing as a compressed private key? Is there such a thing as a compressed public key? 29. What is a vanity address? 30. What is a vanity pool? 31. What is a P2PKH address? What is the prefix for the P2PKH address? 32. How does the owner prove that he is the real owner of some address? What does he have to represent to the network to prove the ownership? Why a perpetrator cannot copy this information and reuse it in the next transactions? 33. What is the rule for using funds that are secured by a cold storage wallet? How many times you can send to the address that is protected by the private key stored in a cold storage? How many times can you send funds from the address that is protected by the private key stored in a cold storage? Chapter 5: Transactions. 1. What is a transaction in Bitcoin? Why is it the most important operation in the Bitcoin ecosystem? 2. What is UTXO? What is one of the important rules of the UTXO? 3. Which language is used to write scripts in Bitcoin ecosystem? What are the features of this language? Which language does it look like? What are the limitations of this language? 4. What is the structure of a transaction? What does transaction consists of? 5. What are the standard transactions in Bitcoin? How many standard transactions there are (as of 2014)? 6. What is a “locking script” and what is an “unlocking script”? What is inside these scripts for a usual operation of P2PKH? What is a signature? Could you please describe in details how locking and unlocking scripts work and draw the necessary diagrams? 7. What is a transaction fee? What does the transaction fee depend on? 8. If you are manually creating transactions, what should you be very careful about? 9. Could you please provide a real life scenario when you might need a P2SH payment and operation? 10. What is the Script operation that is used to store in the blockchain some important data? Is it a good practice? Explain your answer. Chapter 6: The Bitcoin Network. 1. What is the network used in Bitcoin? What is it called? What is the abbreviation? What is the difference between this network architecture and the other network architectures? Could you please describe another network architecture and compare the Bitcoin network and the other network architectures? 2. What is a Bitcoin network? What is an extended Bitcoin network? What is the difference between those two networks? What are the other protocols used in the extended Bitcoin network? Why are these new protocols used? Can you give an example of one such protocol? What is it called? 3. What are the main functions of a bitcoin node? How many of them there are? Could you please name and describe each of them? Which functions are mandatory? 4. What is a full node in the Bitcoin network? What does it do and how does it differ from the other nodes? 5. What is a lightweight node in the Bitcoin network? What is another name of the lightweight node? How lightweight node checks transactions? 6. What are the main problems in the SPV process? What does SPV stand for? How does SPV work and what does it rely on? 7. What is a Sybil attack? 8. What is a transaction pool? Where are transaction pools stored in a Bitcoin network client? What are the two different transaction pools usually available in implementations? 9. What is the main Bitcoin client used in the network? What is the official name of the client and what is an unofficial name of this client? 10. What is UTXO pool? Do all clients keep this pool? Where is it stored? How does it differ from the transaction pools? 11. What is a Bloom filter? Why are Bloom filters used in the Bitcoin network? Were they originally used in the initial SW or were they introduced with a specific BIP? Chapter 7: The Blockchain. 1. What is a blockchain? 2. What is a block hash? Is it really a block hash or is it a hash of something else? 3. What is included in the block? What kind of information? 4. How many parents can one block have? 5. How many children can one block have? Is it a temporary or permanent state of the blockchain? What is the name of this state of the blockchain? 6. What is a Merkle tree? Why does Bitcoin network use Merkle trees? What is the advantage of using Merkle trees? What is the other name of the Merkle tree? What kind of form must this tree have? 7. How are blocks identified in the blockchain? What are the two commonly used identities? Are these identities stored in the blockchain? 8. What is the average size of one transaction? How many transactions are normally in one block? What is the size of a block header? 9. What kind of information do SPV nodes download? How much space do they save by that comparing to what they would need if they had to download the whole blockchain? 10. What is a usual representation of a blockchain? 11. What is a genesis block? Do clients download this block and if yes – where from? What is the number of the genesis block? 12. What is a Merkle root? What is a Merkle path? Chapter 8: Mining and Consensus. 1. What is the main purpose of mining? Is it to get the new coins for the miners? Alternatively, it is something else? Is mining the right or good term to describe the process? 2. What is PoW algorithm? 3. What are the two main incentives for miners to participate in the Bitcoin network? What is the current main incentive and will it be changed in the future? 4. Is the money supply in the Bitcoin network diminishing? If so, what is the diminishing rate? What was the original Bitcoin supply rate and how is it changed over time? Is the diminishing rate time related or rather block related? 5. What is the maximum number of Bitcoins available in the network after all the Bitcoins have been mined? When will all the Bitcoins be mined? 6. What is a decentralized consensus? What is a usual setup to clear transactions? What does a clearinghouse do? 7. What is deflationary money? Are they good or bad usually? What is the bad example of deflationary spiral? 8. What is an emergent consensus? What is the feature of emergent consensus? How does it differ from a usual consensus? What are the main processes out of which this emergent decentralized consensus becomes true? 9. Could you please describe the process of Independent Transaction Verification? What is the list of criteria that are checked against a newly received transaction? Where can these rules be checked? Can they be changed over time? If yes, why would they be changed? 10. Does mining node have to be a full node? If not, what are the other options for a node that is not full to be a mining node? 11. What is a candidate block? What types of nodes in the Bitcoin network create candidate blocks? What is a memory pool? Is there any other name of the memory pool? What are the transactions kept in this memory pool? 12. How are transactions added to the candidate block? How does a candidate block become a valid block? 13. What is the minimum value in the Bitcoin network? What is it called and what is the value? Are there any alternative names? 14. What is the age of the UTXO? 15. How is the priority of a transaction is calculated? What is the exact formula? What are the units of each contributing member? When is a transaction considered to be old? Can low priority transactions carry a zero fee? Will they be processed in this case? 16. How much size in each block is reserved for high priority transactions? How are transactions prioritized for the remaining space? 17. Do transactions expire in Bitcoin? Can transactions disappear in the Bitcoin network? If yes, could you please describe such scenario? 18. What is a generation transaction? Does it have another name? If it does, what is the other name of the transaction? What is the position of the generation transaction in the block? Does it have an input? Is the input usual UTXO? If not – what is the input called? How many outputs there are for the generation transaction? 19. What is the Coinbase data? What is it currently used for? 20. What is little-endian and big-endian formats? Could you please give an example of both? 21. How is the block header constructed? Which fields are calculated and added to the block header? Could you please describe the steps for calculation of the block header fields? 22. What is a mantissa-exponent encoding? How is this encoding used in the Bitcoin network? What is the difficulty target? What is the actual process of mining? What kind of mathematical calculation is executed to conduct mining? 23. Which hash function is used in the Bitcoin mining process? 24. Could you describe the PoW algorithm? What features of the hash function does it depend on? What is the other name of the hash function? What is a nonce? How can we increase the difficulty of the PoW calculation? What do we need to change and how do we need to change this parameter? 25. What is difficulty bits notation? Could you please describe in details how it works? What is the formula for the difficulty notation? 26. Why is difficulty adjustable? Who adjusts it and how exactly? Where is the adjustment made? On which node? How many blocks are taken into consideration to predict the next block issuance rate? What is the change limitation? Does the target difficulty depend on the number of transactions? 27. How is a new block propagated in the network? What kind of verification does each node do? What is the list of criteria for the new block? What kind of process ensures that the miners do not cheat? 28. How does a process of block assembly work? What are the sets of blocks each full node have? Could you please describe these sets of blocks? 29. What is a secondary chain? What does each node do to check this chain and perhaps to promote it to the primary chain? Could you please describe an example when a fork occurs and what happens? 30. How quickly forks are resolved most of the time? Within how many new block periods? 31. Why the next block is generated within 10 minutes from the previous? What is this compromise about? What do designers of the Bitcoin network thought about when implementing this rule? 32. What is a hashing race? How did Bitcoin hashing capacity has changed within years from inception? What kind of hardware devices were initially used and how did the HW utilization evolved? What kind of hardware is used now to do mining? How has the network difficulty improved? 33. What is the size of the field that stores nonce in the block header? What is the limitation and problem of the nonce? Why was an extra nonce created? Was there any intermediate solution? If yes, what was the solution? What are the limitations of the solution? 34. What is the exact solution for the extra nonce? Where does the new space come from? How much space is currently used and what is the range of the extra nonce now? 35. What is a mining pool? Why was it created? How are normally such pools operated? Do they pay regularly to the pool participants? Where are newly created Bitcoins distributed? To which address? How do mining pools make money? How do the mining pools calculate the participation? How are shares earned calculated? 36. What is a managed pool? How is the owner of the pool called? Do pool members need to run full nodes? Explain why or why not? 37. What are the most famous protocols used to coordinate pool activities? What is a block template? How is it used? 38. What is the limitation of a centralized pool? Is there any alternative? If yes, what is it? How is it called? How does it work? 39. What is a consensus attack? What is the main assumption of the Bitcoin network? What can be the targets of the consensus attacks? What can these attacks do and what they cannot do? How much overall capacity of the network do you have to control to exercise a consensus attack? Chapter 9: Alternative Chains, Currencies and Applications. 1. What is the name of alternative coins? Are they built on top of the Bitcoin network? What are examples of them? Is there any alternative approach? Could you please describe some alternatives? 2. Are there any alternatives to the PoW algorithm? If yes – what are the alternatives? Could you please name two or three? 3. What is the operation of the Script language that is used to store a metadata in Bitcoin blockchain? 4. What is a coloured coin? Could you please explain how it is created and how it works? Do you need any special SW to manage coloured coins? 5. What is the difference between alt coins and alt chains? What is a Litecoin? What are the major differences between the Bitcoin and Litecoin? Why so many alt coins have been created? What are they usually based on? 6. What is Scrypt? Where is it used and how is it different from the original algorithm from which it has been created? 7. What is a demurrage currency? Could you please give an example of one blockchain and crypto currency that is demurrage? 8. What is a good example of an alternative algorithm to PoW? What is it called and how is it different from the PoW? Why the alternatives to Bitcoin PoW have been created? What is the main reason for this? What is dual-purpose PoW algorithms? Why have they been created? 9. Is Bitcoin “anonymous” currency? Is it difficult to trace transactions and understand someone’s spending habits? 10. What is Ethereum? What kind of currency does it use? What is the difference from Bitcoin? Chapter 10: Bitcoin security. 1. What is the main approach of Bitcoin security? 2. What are two common mistakes made by newcomers to the world of Bitcoin? 3. What is a root of trust in traditional security settings? What is a root of trust in Bitcoin network? How should you assess security of your system? 4. What is a cold storage and paper wallet? 5. What is a hardware wallet? How is it better than storing private keys on your computer or your smart phone?
submitted by 5tu to BitcoinTechnology [link] [comments]

BlockTorrent: The famous algorithm which BitTorrent uses for SHARING BIG FILES. Which you probably thought Bitcoin *also* uses for SHARING NEW BLOCKS (which are also getting kinda BIG). But Bitcoin *doesn't* torrent *new* blocks (while relaying). It only torrents *old* blocks (while sync-ing). Why?

This post is being provided to further disseminate an existing proposal:
This proposal was originally presented by jtoomim back in September of 2015 - on the bitcoin_dev mailing list (full text at the end of this OP), and on reddit:
https://np.reddit.com/btc/comments/3zo72i/fyi_ujtoomim_is_working_on_a_scaling_proposal/cyomgj3
Here's a TL;DR, in his words:
BlockTorrenting
For initial block sync, [Bitcoin] sort of works [like BitTorrent] already.
You download a different block from each peer. That's fine.
However, a mechanism does not currently exist for downloading a portion of each [new] block from a different peer.
That's what I want to add.
~ jtoomim
The more detailed version of this "BlockTorrenting" proposal (as presented by jtoomim on the bitcoin_dev mailing list) is linked and copied / reformatted at the end of this OP.
Meanwhile here are some observations from me as a concerned member of the Bitcoin-using public.
Questions:
Whoa??
WTF???
Bitcoin doesn't do this kind of "blocktorrenting" already??
But.. But... I thought Bitcoin was "p2p" and "based on BitTorrent"...
... because (as we all know) Bitcoin has to download giant files.
Oh...
Bitcoin only "torrents" when sharing one certain kind of really big file: the existing blockchain, when a node is being initialized.
But Bitcoin doesn't "torrent" when sharing another certain kind of moderately big file (a file whose size, by the way, has been notoriously and steadily growing over the years to the point where the system running the legacy "Core"/Blockstream Bitcoin implementation is starting to become dangerously congested - no matter what some delusional clowns "Core" devs may say): ie, the world's most wildly popular, industrial-strength "p2p file sharing algorithm" is mysteriously not being used where the Bitcoin network needs it the most in order to get transactions confirmed on-chain: when a a newly found block needs to be shared among nodes, when a node is relaying new blocks.
https://np.reddit.com/Bitcoin+bitcoinxt+bitcoin_uncensored+btc+bitcoin_classic/search?q=blocktorrent&restrict_sr=on
How many of you (honestly) just simply assumed that this algorithm was already being used in Bitcoin - since we've all been told that "Bitcoin is p2p, like BitTorrent"?
As it turns out - the only part of Bitcoin which has been p2p up until now is the "sync-ing a new full-node" part.
The "running an existing full-node" part of Bitcoin has never been implemented as truly "p2p2" yet!!!1!!!
And this is precisely the part of the system that we've been wasting all of our time (and destroying the community) fighting over for the past few months - because the so-called "experts" from the legacy "Core"/Blockstream Bitcoin implementation ignored this proposal!
Why?
Why have all the so-called "experts" at "Core"/Blockstream ignored this obvious well-known effective & popular & tested & successful algorithm for doing "blocktorrenting" to torrent each new block being relayed?
Why have the "Core"/Blockstream devs failed to p2p-ize the most central, fundamental networking aspect of Bitcoin - the part where blocks get propagated, the part we've been fighting about for the past few years?
This algorithm for "torrenting" a big file in parallel from peers is the very definition of "p2p".
It "surgically" attacks the whole problem of sharing big files in the most elegant and efficient way possible: right at the lowest level of the bottleneck itself, cleverly chunking a file and uploading it in parallel to multiple peers.
Everyone knows torrenting works. Why isn't Bitcoin using it for its new blocks?
As millions of torrenters already know (but evidently all the so-called "experts" at Core/Blocsktream seem to have conveniently forgotten), "torrenting" a file (breaking a file into chunks and then offering a different chunk to each peer to "get it out to everyone fast" - before your particular node even has the entire file) is such a well-known / feasible / obvious / accepted / battle-tested / highly efficient algorithm for "parallelizing" (and thereby significantly accelerating) the sharing of big files among peers, that many people simply assumed that Bitcoin had already been doing this kind of "torrenting of new-blocks" these whole past 7 years.
But Bitcoin doesn't do this - yet!
None of the Core/Blockstream devs (and the Chinese miners who follow them) have prioritized p2p-izing the most central and most vital and most resource-consuming function of the Bitcoin network - the propagation of new blocks!
Maybe it took someone who's both a miner and a dev to "scratch" this particular "itch": Jonathan Toomim jtoomim.
  • A miner + dev who gets very little attention / respect from the Core/Blockstream devs (and from the Chinese miners who follow them) - perhaps because they feel threatened by a competing implementation?
  • A miner + dev who may have come up with the simplest and safest and most effective algorithmic (ie, software-based, not hardware-consuming) scaling proposal of anyone!
  • A dev who who is not paid by Blockstream, and who is therefore free from the secret, undisclosed corporate restraints / confidentiality agreements imposed by the shadowy fiat venture-capitalists and legacy power elite who appear to be attempting to cripple our code and muzzle our devs.
  • A miner who has the dignity not to let himself be forced into signing a loyalty oath to any corporate overlords after being locked in a room until 3 AM.
Precisely because jtoomim is both a indepdendent miner and an independent dev...
  • He knows what needs to be done.
  • He knows how to do it.
  • He is free to go ahead and do it - in a permissionless, decentralized fashion.
Possible bonus: The "blocktorrent" algorithm would help the most in the upload direction - which is precisely where Bitcoin scaling needs the most help!
Consider the "upload" direction for a relatively slow full-node - such as Luke-Jr, who reports that his internet is so slow, he has not been able to run a full-node since mid-2015.
The upload direction is the direction which everyone says has been the biggest problem with Bitcoin - because, in order for a full-node to be "useful" to the network:
  • it has to able to upload a new block to (at least) 8 peers,
  • which places (at least) 8x more "demand" on the full-node's upload bandwidth.
The brilliant, simple proposed "blocktorrent" algorithm from jtoomim (already proven to work with Bram Cohen's BitTorrent protocol, and also already proven to work for initial sync-ing of Bitcoin full-nodes - but still un-implemented for ongoing relaying among full-nodes) looks like it would provide a significant performance improvement precisely at this tightest "bottleneck" in the system, the crucial central nexus where most of the "traffic" (and the congestion) is happening: the relaying of new blocks from "slower" full-nodes.
The detailed explanation for how this helps "slower" nodes when uploading, is as follows.
Say you are a "slower" node.
You need to send a new block out to (at least) 8 peers - but your "upload" bandwidth is really slow.
If you were to split the file into (at least) 8 "chunks", and then upload a different one of these (at least) 8 "chunks" to each of your (at least) 8 peers - then (if you were using "blocktorrenting") it only would take you 1/8 (or less) of the "normal" time to do this (compared to the naïve legacy "Core" algorithm).
Now the new block which your "slower" node was attempting to upload is already "out there" - in 1/8 (or less) of the "normal" time compared to the naïve legacy "Core" algorithm.[ 1 ]
... [ 1 ] There will of course also be a tiny amount of extra overhead involved due to the "housekeeping" performed by the "blocktorrent" algorithm itself - involving some additional processing and communicating to decompose the block into chunks and to organize the relaying of different chunks to different peers and the recompose the chunks into a block again (all of which, depending on the size of the block and the latency of your node's connections to its peers, would in most cases be negligible compared to the much-greater speed-up provided by the "blocktorrent" algorithm itself).
Now that your block is "out there" at those 8 (or more) peer nodes to whom you just blocktorrented it in 1/8 (or less) of the time - it has now been liberated from the "bottleneck" of your "slower" node.
In fact, its further propagation across the net may now be able to leverage much faster upload speeds from some other node(s) which have "blocktorrent"-downloaded it in pieces from you (and other peers) - and which might be faster relaying it along, than your "slower" node.
For some mysterious reason, the legacy Bitcoin implementation from "Core"/Blockstream has not been doing this kind of "blocktorrenting" for new blocks.
It's only been doing this torrenting for old blocks. The blocks that have already been confirmed.
Which is fine.
But we also obviously need this sort of "torrenting" to be done for each new block is currently being confirmed.
And this is where the entire friggin' "scaling bottleneck" is occurring, which we just wasted the past few years "debating" about.
Just sit down and think about this for a minute.
We've had all these so-called "experts" (Core/Blockstream devs and other small-block proponents) telling us for years that guys like Hearn and Gavin and repos like Classic and XT and BU were "wrong" or at least "unserious" because they "merely" proposed "brute-force" scaling: ie, scaling which would simply place more demands on finite resources (specifically: on the upload bandwidth from full-nodes - who need to relay to at least 8 peer full-nodes in order to be considered "useful" to the network).
These "experts" have been beating us over the head this whole time, telling us that we have to figure out some (really complicated, unproven, inefficient and centralized) clever scaling algorithms to squeeze more efficiency out of existing infrastructure.
And here is the most well-known / feasible / obvious / accepted / battle-tested algorithm for "parallelizing" (and thereby massively accelerating) the sharing of big file among peers - the BitTorrent algorithm itself, the gold standard of p2p relaying par excellence, which has been a major success on the Internet for decades, at one point accounting for nearly 1/3 of all traffic on the Internet itself - and which is also already being used in one part of Bitcoin: during the phase of sync-ing a new node.
And apparently pretty much only jtoomim has been talking about using it for the actual relaying of new blocks - while Core/Blockstream devs have so far basically ignored this simple and safe and efficient proposal.
And then the small-block sycophants (reddit users or wannabe C/C++ programmers who have beaten into submission and/or by the FUD and "technological pessimism" of the Core/Blockstream devs, and by the censorhip on their legacy forum), they all "laugh" at Classic and proclaim "Bitcoin doesn't need another dev team - all the 'experts' are at Core / Blockstream"...
...when in fact it actually looks like jtoomim (an independent minedev, free from the propaganda and secret details of the corporate agenda of Core/Blockstream - who works on the Classic Bitcoin implementation) may have proposed the simplest and safest and most effective scaling algorithm in this whole debate.
By the way, his proposal estimates that we could get about 1 magnitude greater throughput, based on the typical latency and blocksize for blocks of around 20 MB and bandwidth of around 8 Mbps (which seems like a pretty normal scenario).
So why the fuck isn't this being done yet?
This is such a well-known / feasible / obvious / accepted / battle-tested algorithm for "parallelizing" (and thereby significantly accelerating) the sharing of big files among peers:
  • It's already being used for the (currently) 65 gigabytes of "blocks in the existing blockchain" itself - the phase where a new node has to sync with the blockchain.
  • It's already being used in BitTorrent - although the BitTorrent protocol has been optimized more to maximize throughput, whereas it would probably be a good idea to optimize the BlockTorrent protocol to minimize latency (since avoiding orphans is the big issue here) - which I'm fairly sure should be quite doable.
This algorithm is so trivial / obvious / straightforward / feasible / well-known / proven that I (and probably many others) simply assumed that Bitcoin had been doing this all along!
But it has never been implemented.
There is however finally a post about it today on the score-hidden forum /Bitcoin, from eragmus:
[bitcoin-dev] BlockTorrent: Torrent-style new-block propagation on Merkle trees
https://np.reddit.com/Bitcoin/comments/484nbx/bitcoindev_blocktorrent_torrentstyle_newblock/
And, predictably, the top-voted comment there is a comment telling us why it will never work.
And the comment after that comment is from the author of the proposal, jtoomim, explaining why it would work.
Score hidden on all those comments.
Because the immature tyrant theymos still doesn't understand the inherent advantages of people using reddit's upvoting & downvoting tools to hold decentralized, permissionless debates online.
Whatever.
Questions:
(1) Would this "BlockTorrenting" algorithm from jtoomim really work?
(2) If so, why hasn't it been implemented yet?
(3) Specifically: With all the "dev firepower" (and $76 million in venture capital) available at Core/Blockstream, why have they not prioritized implementing this simple and safe and highly effective solution?
(4) Even more specifically: Are there undisclosed strategies / agreements / restraints imposed by Blockstream financial investors on Bitcoin "Core" devs which have been preventing further discussion and eventual implementation of this possible simple & safe & efficient scaling solution?
Here is the more-detailed version of this proposal, presented by Jonathan Toomim jtoomim back in September of 2015 on the bitcoin-dev mailing list (and pretty much ignored for months by almost all the "experts" there):
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-Septembe011176.html
As I understand it, the current block propagation algorithm is this:
  1. A node mines a block.
  2. It notifies its peers that it has a new block with an inv. Typical nodes have 8 peers.
  3. The peers respond that they have not seen it, and request the block with getdata [hash].
  4. The node sends out the block in parallel to all 8 peers simultaneously. If the node's upstream bandwidth is limiting, then all peers will receive most of the block before any peer receives all of the block. The block is sent out as the small header followed by a list of transactions.
  5. Once a peer completes the download, it verifies the block, then enters step 2.
(If I'm missing anything, please let me know.)
The main problem with this algorithm is that it requires a peer to have the full block before it does any uploading to other peers in the p2p mesh. This slows down block propagation to:
O( p • log_p(n) ) 
where:
  • n is the number of peers in the mesh,
  • p is the number of peers transmitted to simultaneously.
It's like the Napster era of file-sharing. We can do much better than this.
Bittorrent can be an example for us.
Bittorrent splits the file to be shared into a bunch of chunks, and hashes each chunk.
Downloaders (leeches) grab the list of hashes, then start requesting their peers for the chunks out-of-order.
As each leech completes a chunk and verifies it against the hash, it begins to share those chunks with other leeches.
Total propagation time for large files can be approximately equal to the transmission time for an FTP upload.
Sometimes it's significantly slower, but often it's actually faster due to less bottlenecking on a single connection and better resistance to packet/connection loss.
(This could be relevant for crossing the Chinese border, since the Great Firewall tends to produce random packet loss, especially on encrypted connections.)
Bitcoin uses a data structure for transactions with hashes built-in. We can use that in lieu of Bittorrent's file chunks.
A Bittorrent-inspired algorithm might be something like this:
  1. (Optional steps to build a Merkle cache; described later)
  2. A seed node mines a block.
  3. It notifies its peers that it has a new block with an extended version of inv.
  4. The leech peers request the block header.
  5. The seed sends the block header. The leech code path splits into two.
  6. (a) The leeches verify the block header, including the PoW. If the header is valid,
  7. (a) They notify their peers that they have a header for an unverified new block with an extended version of inv, looping back to 2. above. If it is invalid, they abort thread (b).
  8. (b) The leeches request the Nth row (from the root) of the transaction Merkle tree, where N might typically be between 2 and 10. That corresponds to about 1/4th to 1/1024th of the transactions. The leeches also request a bitfield indicating which of the Merkle nodes the seed has leaves for. The seed supplies this (0xFFFF...).
  9. (b) The leeches calculate all parent node hashes in the Merkle tree, and verify that the root hash is as described in the header.
  10. The leeches search their Merkle hash cache to see if they have the leaves (transaction hashes and/or transactions) for that node already.
  11. The leeches send a bitfield request to the node indicating which Merkle nodes they want the leaves for.
  12. The seed responds by sending leaves (either txn hashes or full transactions, depending on benchmark results) to the leeches in whatever order it decides is optimal for the network.
  13. The leeches verify that the leaves hash into the ancestor node hashes that they already have.
  14. The leeches begin sharing leaves with each other.
  15. If the leaves are txn hashes, they check their cache for the actual transactions. If they are missing it, they request the txns with a getdata, or all of the txns they're missing (as a list) with a few batch getdatas.
Features and benefits
The main feature of this algorithm is that a leech will begin to upload chunks of data as soon as it gets them and confirms both PoW and hash/data integrity instead of waiting for a fully copy with full verification.
Inefficient cases, and mitigations
This algorithm is more complicated than the existing algorithm, and won't always be better in performance.
Because more round trip messages are required for negotiating the Merkle tree transfers, it will perform worse in situations where the bandwidth to ping latency ratio is high relative to the blocksize.
Specifically, the minimum per-hop latency will likely be higher.
This might be mitigated by reducing the number of round-trip messages needed to set up the BlockTorrent by using larger and more complex inv-like and getdata-like messages that preemptively send some data (e.g. block headers).
This would trade off latency for bandwidth overhead from larger duplicated inv messages.
Depending on implementation quality, the latency for the smallest block size might be the same between algorithms, or it might be 300% higher for the torrent algorithm.
For small blocks (perhaps < 100 kB), the BlockTorrent algorithm will likely be slightly slower.
Sidebar from the OP: So maybe this would discourage certain miners (cough Dow cough) from mining blocks that aren't full enough:
Why is [BTCC] limiting their block size to under 750 all of a sudden?
https://np.reddit.com/Bitcoin/comments/486o1u/why_is_bttc_limiting_their_block_size_to_unde

For large blocks (e.g. 8 MB over 20 Mbps), I expect the BlockTorrent algo will likely be around an order of magnitude faster in the worst case (adversarial) scenarios, in which none of the block's transactions are in the caches.

One of the big benefits of the BlockTorrent algorithm is that it provides several obvious and straightforward points for bandwidth saving and optimization by caching transactions and reconstructing the transaction order.

Future work: possible further optimizations
A cooperating miner [could] pre-announce Merkle subtrees with some of the transactions they are planning on including in the final block.
Other miners who see those subtrees [could] compare the transactions in those subtrees to the transaction sets they are mining with, and can rearrange their block prototypes to use the same subtrees as much as possible.
In the case of public pools supporting the getblocktemplate protocol, it might be possible to build Merkle subtree caches without the pool's help by having one or more nodes just scraping their getblocktemplate results.
Even if some transactions are inserted or deleted, it [might] be possible to guess a lot of the tree based on the previous ordering.
Once a block header and the first few rows of the Merkle tree [had] been published, they [would] propagate through the whole network, at which time full nodes might even be able to guess parts of the tree by searching through their txn and Merkle node/subtree caches.
That might be fun to think about, but probably not effective due to O( n2 ) or worse scaling with transaction count.
Might be able to make it work if the whole network cooperates on it, but there are probably more important things to do.
Leveraging other features from BitTorrent
There are also a few other features of Bittorrent that would be useful here, like:
  • prioritizing uploads to different peers based on their upload capacity,
  • banning peers that submit data that doesn't hash to the right value.
Sidebar from the OP: Hmm...maybe that would be one way to deal with the DDoS-ing we're experiencing right now? I know the DDoSer is using a rotating list of proxies, but still it could be a quick-and-dirty way to mitigate against his attack.
DDoS started again. Have a nice day, guys :)
https://np.reddit.com/Bitcoin_Classic/comments/47zglz/ddos_started_again_have_a_nice_day_guys/d0gj13y
(It might be good if we could get Bram Cohen to help with the implementation.)
Using the existing BitTorrent algorithm as-is - versus tailoring a new algorithm optimized for Bitcoin
Another possible option would be to just treat the block as a file and literally Bittorrent it.
But I think that there should be enough benefits to integrating it with the existing bitcoin p2p connections and also with using bitcoind's transaction caches and Merkle tree caches to make a native implementation worthwhile.
Also, BitTorrent itself was designed to optimize more for bandwidth than for latency, so we will have slightly different goals and tradeoffs during implementation.
Concerns, possible attacks, mitigations, related work
One of the concerns that I initially had about this idea was that it would involve nodes forwarding unverified block data to other nodes.
At first, I thought this might be useful for a rogue miner or node who wanted to quickly waste the whole network's bandwidth.
However, in order to perform this attack, the rogue needs to construct a valid header with a valid PoW, but use a set of transactions that renders the block as a whole invalid in a manner that is difficult to detect without full verification.
However, it will be difficult to design such an attack so that the damage in bandwidth used has a greater value than the 240 exahashes (and 25.1 BTC opportunity cost) associated with creating a valid header.
Related work: IBLT (Invertible Bloom Lookup Tables)
As I understand it, the O(1) IBLT approach requires that blocks follow strict rules (yet to be fully defined) about the transaction ordering.
If these are not followed, then it turns into sending a list of txn hashes, and separately ensuring that all of the txns in the new block are already in the recipient's mempool.
When mempools are very dissimilar, the IBLT approach performance degrades heavily and performance becomes worse than simply sending the raw block.
This could occur if a node just joined the network, during chain reorgs, or due to malicious selfish miners.
Also, if the mempool has a lot more transactions than are included in the block, the false positive rate for detecting whether a transaction already exists in another node's mempool might get high for otherwise reasonable bucket counts/sizes.
With the BlockTorrent approach, the focus is on transmitting the list of hashes in a manner that propagates as quickly as possible while still allowing methods for reducing the total bandwidth needed.
Remark
The BlockTorrent algorithm does not really address how the actual transaction data will be obtained because, once the leech has the list of txn hashes, the standard Bitcoin p2p protocol can supply them in a parallelized and decentralized manner.
Thoughts?
-jtoomim
submitted by ydtm to btc [link] [comments]

Why bitcoin is better than gold

About 3.5 years ago I submitted my first post to reddit https://www.reddit.com/Bitcoin/comments/18hidg/why_bitcoin_is_better_than_gold/
Since then I have revised some of my thoughts and decided to rewrite this in a more concise way hopefully.
Reason 1
With bitcoin it is possible to offer proof of reserves.
"I am attesting to [...] the root hash of a merkle tree containing all balances that were considered in the audit. If you are a customer of Kraken, you'll be able to verify using open-source tools that your balance at the time of the audit is part of this root hash. If it is and if you believe that I am trustworthy, then you can be confident that your balance was covered by 100% reserves at the time of the audit."
With gold there is more trust involved because such proofs are not possible in the same way. link
Reason 2
The supply of bitcoins is more predictable and known. While there are probably pretty accurate estimations for how much gold exists above and below ground... when it comes down to it, mining an asteroid could drastically alter the "rarity" property of gold.
Reason 3
The storage of bitcoin is far more versatile than gold. Bitcoin can be secured to be as safe as gold or even more safe (or less) . For instance you can't steal gold through a picture. But if you put up a photo of your private key it could be taken rather quickly if uploaded to the internet. On the flipside, you could break up your private key into n of M pieces. Lets say 4 out of 6. That means that there are 6 pieces and only 4 are required for reassembling the key. You could then store 1 in a safe in your house, 1 in a bank in one country, 1 in a bank in another country, 1 buried somewhere, 1 in your mind, 1 at a relatives house. As long as you could acquire 4 of them you could reassemble the key. The possibilities just expand from there. When speaking of storage it is also worth mentioning that costs associated with storing bitcoin should be much less than gold since gold is large, heavy and must always be physically guarded somehow. This should reduce storage costs which are also important considering that a lot of people invest long term.
Reason 4
Transfer. Bitcoin has a built in payment network and this makes its transfer easier, cheaper. If gold is meant as wealth protection and your particular country has capital controls in place it may not be so easy to transport it across the border. We can all agree capital controls are bad right? Here is a recent article about how someone was caught bringing 18 bars of gold across a border. With bitcoin this isn't really a problem since you can store it in your mind. Deterministic wallets allow you to create a seed that can restore multiple keys. For instance my mycelium wallet on my phone has a 12 word phrase that can restore my bitcoins. I could destroy my phone, leave the country, find another android phone in a different country, download mycelium, and restore all the bitcoin I had from the new phone just by typing in those 12 words. The fact that this "payment network" is built in also creates other beneficial scenarios where merchants and people in general are more likely to accept bitcoin as payment. I remember watching a video recently where someone actually tried to sell an ounce of gold for much cheaper than it was worth and normal people wouldn't even accept it.
Reason 5
There is one other big issue that I don't see mentioned often. If you combine some of the superior attributes of bitcoin... take reason 1, 2 , 3 and 4.. it results in a much more possibly honest value for bitoin than gold could achieve.
From The New Case For Gold by James Rickards :
"Investors should understand that there's a physical gold market and a paper gold market. The paper gold market consists of a number of contracts: COMEX futures, exchange traded funds (ETFs), gold swaps, gold leasing, forward contracts, and so-called unallocated gold issued by London Bullion Market Association banks. Those derivatives--futures, swaps, ETFs, leasing, forwards and unallocated gold--form the paper gold market.
The paper market could easily be one hundred times the size of the physical market. This means that for every hundred people who think they own gold, ninety-nine of them are wrong. Only one of them is going to get physical gold when the panic begins"
Because bitcoin is so easily transferred, because there is no large associated cost with the acquirement of it due to shipping and all the losses that involves, and because over time it gets easier to use and store in a secure way and how people are more likely to actually have it than simply have a piece of paper that says they have it... we probably won't see the same problem in the future where there will be a "fake bitcoin" market that dwarfs the actual bitcoins that exist. This means its value.... if it starts to etch into golds market could be far higher than some people calculate based on the simple rarity of gold in proportion to its value.
submitted by specialenmity to btc [link] [comments]

An approach to mining centralization induced by mining pools

This approach attempts to address the mining-pool-induced centralization issue by introducing mining pool features into Bitcoin protocol, therefore eliminating the need for mining pools.
To be more specific, miners work poollessly, broadcast shares to Bitcoin network, and get paid based on their shares directly by the Bitcoin protocol.
 
Challenges:
The instant problem/challenge with such an approach is obvious: there is no way that miners can work on the same block. This can be broken down into:
  1. There is no way miners can work on the same block because the regular transactions included and the order won't be the same.
  2. There is no way miners can work on the same block because the coinbase transaction won't be the same.
The first issue is to be addressed with a P2P communication process.
In order to address the second issue, two key ideas/theories are introduced:
  1. Proof-of-work on (only) the critical part of a given dataset provides a close level of security to the whole dataset, compared to when it is done on the whole dataset.
  2. Proof-of-work can be accumulated.
An example of the first theory is as follows: Assume the version field is less important. PoW on the block without it, e.g., with it always set to zero, results in a close level of security compared to PoW on the original block. The first theory enables the idea that you don't have to mine the exactly same block to mine the "same" block. The part that's deemed less important in this approach is the coinbase transaction.
An example of the second theory is as follows: Assume we want a PoW of 5 out of 100. The regular way to achieve it is to hash until a result of 5 or less occurs. There is another way. PoW of 5 out of 100 in average requires 20 attempts of hashing. As long as we can tell 20 or more attempts have been made, we have the required PoW. We know that 10 out of 100 requires 10 attempts in average. With 2x 10s, there are 20 attempts, meaning that the PoW requirement of 5 out of 100 is met. It's the same is for 4x 20s. The second theory basically means shares can be combined to meet the PoW requirement.
 
Solution (brief):
Based on the two theories and the assumption that the coinbase transaction is less important, the outline of the solution, which I call Aggregated Mining, is formed:
 
Solution (details):
Here are the detailed explanations:
The resulting block is of the same format as current ones except for the coinbase transaction, which contains not only the (finalizing) miner's data, but also the data of all shares.
For verification, when a block is received, besides the regular validation check of the full block, of which the block income used is the total income rather than the dividend of the minter, the block is verified the-number-of-the-shares times for each share, by rebuilding the share's original block, which is done by replacing all related fields in the current block with the miner-specific data of the share. (All shares share the same block data, excluding the miner-specific parts, as the minter's block.) The distribution of dividends is also verified. The block is valid only when all verifications succeed.
Data structure:
A share's P2P data:
prev_block:1a2b3c4d, // first 64 bits of hash of previous block { // barebone block id n_tx:2345, // number of transactions tx:[ { tx_id:1f3e5d7c // transaction id; 64-bit integer (first 64 bits of hash) }, { tx_id:2f4e6d8c // transaction id; 64-bit integer (first 64 bits of hash) }, ... ], } { // miner-specific data coinbase:"Miner001:...", // starting with miner ID, to avoid miners mining in the same space value:14.12345, // the block income scriptPubKey:..., // the harvester's address timestamp:1489634411, // the share's timestamp nonce:23456789, // the share's nonce } 
A share's (harvester's) coinbase data:
in:[ { prev_out:{ hash:00000...00000, n:-1 }, coinbase:"Miner001:..." // starting with miner ID, to avoid miners mining in the same space } ] out:[ { value:14.12345 scriptPubKey:... // the harvester's address } ] 
A share's (harvester's) coinbase data (space-saving version):
in:[ { coinbase:"Miner001:..." // starting with miner ID, to avoid miners mining in the same space } ] out:[ { scriptPubKey:... // the harvester's address } ] 
Minter's coinbase data:
in:[ { prev_out:{ hash:00000...00000, n:-1 }, coinbase:"......" } ] out:[ { total:14.12345 // total block income; applies to all shares, too value:2.34567 // the minter's dividend scriptPubKey:... // the minter's address } ] share_size:5678, shares:[ { { // share's coinbase data }, value:0.12345 // the share's dividend timestamp:1489634400 // the share's timestamp nonce:12345678 // the share's nonce }, { { // share's coinbase data }, value:0.98765 // the share's dividend timestamp:1489634411 // the share's timestamp nonce:23456789 // the share's nonce }, ... ] 
 
Securities:
The security of all share data and the security of the minter's own coinbase data, as well as the security of the whole block, are to be consolidated by the following blocks, just like the blocks in the current scheme.
 
Pros and cons:
Pros:
Cons:
If the verification process takes too much time, an optimization can be introduced by changing how the Merkle root is calculated. There will be a Merkle root for all the regular transactions. The final Merkel root will be calculated from the coinbase transaction and the Merkle root of regular transactions.
In order to lower the odds of the forks and stale blocks, the minimum PoW requirement for minting can be raised.
 
Discussions (basic):
Timeline (based on the minimum minting PoW requirement being 10%):
(Transactions, miner-signed transaction IDs, and shares are relayed in the network all the time.)
Analysis:
A share's P2P data:
early_share:1 // early share flag prev_block:1a2b3c4d, // first 64 bits of hash of previous block { // barebone block id n_tx:2345, // number of transactions tx:[ { tx_id:1f3e5d7c // transaction id; 64-bit integer (first 64 bits of hash) }, { tx_id:2f4e6d8c // transaction id; 64-bit integer (first 64 bits of hash) }, ... ], } { // miner-specific data coinbase:"Miner001:...", // starting with miner ID, to avoid miners mining in the same space value:14.12345, // the block income scriptPubKey:..., // the harvester's address timestamp:1489634411, // the share's timestamp nonce:23456789, // the share's nonce } 
Minter's coinbase data (with early shares added):
in:[ { prev_out:{ hash:00000...00000, n:-1 }, coinbase:"......" } ] out:[ { total:14.12345 // total block income; applies to all shares, too value:2.34567 // the minter's dividend scriptPubKey:... // the minter's address } ] early_share_size:654, early_shares:[ { { // share's coinbase data }, value:0.11111 // the share's dividend timestamp:1489634300 // the share's timestamp nonce:345678 // the share's nonce }, { { // share's coinbase data }, value:0.22222 // the share's dividend timestamp:1489634311 // the share's timestamp nonce:876543 // the share's nonce }, ... ] share_size:5678, shares:[ { { // share's coinbase data }, value:0.12345 // the share's dividend timestamp:1489634400 // the share's timestamp nonce:12345678 // the share's nonce }, { { // share's coinbase data }, value:0.98765 // the share's dividend timestamp:1489634411 // the share's timestamp nonce:23456789 // the share's nonce }, ... ] 
 
Discussions (advanced):
Timeline (adjusted for independent regular miners):
Further analysis:
 
Any genuine (non-trolling) comment is welcomed.
Any correction, improvement or education will be appreciated.
EDIT: The post will keep being updated for corrections, improvements, rewording and formatting, until this line is removed.
submitted by exab to Bitcoin [link] [comments]

Merkle trees and mountain ranges | Bram Cohen | Jun 15 2016

Bram Cohen on Jun 15 2016:
This is in response to Peter Todd's proposal for Merkle Mountain Range
commitments in blocks:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html
I'm in strong agreement that there's a compelling need to put UTXO
commitments in blocks, and that the big barrier to getting it done is
performance, particularly latency. But I have strong disagreements (or
perhaps the right word is skepticism) about the details.
Peter proposes that there should be both UTXO and STXO commitments, and
they should be based on Merkle Mountain Ranges based on Patricia Tries. My
first big disagreement is about the need for STXO commitments. I think
they're unnecessary and a performance problem. The STXO set is much larger
than the utxo set and requires much more memory and horespower to maintain.
Most if not all of its functionality can in practice be done using the utxo
set. Almost anything accepting proofs of inclusion and exclusion will have
a complete history of block headers, so to prove inclusion in the stxo set
you can use a utxo proof of inclusion in the past and a proof of exclusion
for the most recent block. In the case of a txo which has never been
included at all, it's generally possible to show that an ancestor of the
txo in question was at one point included but that an incompatible
descendant of it (or the ancestor itself) is part of the current utxo set.
Generating these sorts of proofs efficiently can for some applications
require a complete STXO set, but that can done with a non-merkle set,
getting the vastly better performance of an ordinary non-cryptographic
hashtable.
The fundamental approach to handling the latency problem is to have the
utxo commitments trail a bit. Computing utxo commitments takes a certain
amount of time, too much to hold up block propagation but still hopefully
vastly less than the average amount of time between blocks. Trailing by a
single block is probably a bad idea because you sometimes get blocks back
to back, but you never get blocks back to back to back to back. Having the
utxo set be trailing by a fixed amount - five blocks is probably excessive
issue. Smaller commitments for the utxos added and removed in each block
alone could be added without any significant performance penalty. That way
all blocks would have sufficient commitments for a completely up to date
proofs of inclusion and exclusion. This is not a controversial approach.
Now I'm going to go out on a limb. My thesis is that usage of a mountain
range is unnecessary, and that a merkle tree in the raw can be made
serviceable by sprinkling magic pixie dust on the performance problem.
There are two causes of performance problems for merkle trees: hashing
operations and memory cache misses. For hashing functions, the difference
between a mountain range and a straight merkle tree is roughly that in a
mountain range there's one operation for each new update times the number
of times that thing will get merged into larger hills. If there are fewer
levels of hills the number of operations is less but the expense of proof
of inclusion will be larger. For raw merkle trees the number of operations
per thing added is the log base 2 of the number of levels in the tree,
minus the log base 2 of the number of things added at once since you can do
lazy evaluation. For practical Bitcoin there are (very roughly) a million
things stored, or 20 levels, and there are (even more roughly) about a
thousand things stored per block, so each thing forces about 20 - 10 = 10
operations. If you follow the fairly reasonable guideline of mountain range
hills go up by factors of four, you instead have 20/2 = 10 operations per
thing added amortized. Depending on details this comparison can go either
way but it's roughly a wash and the complexity of a mountain range is
clearly not worth it at least from the point of view of CPU costs.
But CPU costs aren't the main performance problem in merkle trees. The
biggest issues is cache misses, specifically l1 and l2 cache misses. These
tend to take a long time to do, resulting in the CPU spending most of its
time sitting around doing nothing. A naive tree implementation is pretty
much the worst thing you can possibly build from a cache miss standpoint,
and its performance will be completely unacceptable. Mountain ranges do a
fabulous job of fixing this problem, because all their updates are merges
so the metrics are more like cache misses per block instead of cache misses
per transaction.
The magic pixie dust I mentioned earlier involves a bunch of subtle
implementation details to keep cache coherence down which should get the
number of cache misses per transaction down under one, at which point it
probably isn't a bottleneck any more. There is an implementation in the
works here:
https://github.com/bramcohen/MerkleSet
This implementation isn't finished yet! I'm almost there, and I'm
definitely feeling time pressure now. I've spent quite a lot of time on
this, mostly because of a bunch of technical reworkings which proved
necessary. This is the last time I ever write a database for kicks. But
this implementation is good on all important dimensions, including:
Lazy root calculation
Few l1 and l2 cache misses
Small proofs of inclusion/exclusion
Reasonably simple implementation
Reasonably efficient in memory
Reasonable defense against malicious insertion attacks
There is a bit of a false dichotomy with the mountain range approach.
Mountain ranges need underlying merkle trees, and mine are semantically
nearly identically to Peter's. This is not a coincidence - I adopted
patricia tries at his suggestion. There are a bunch of small changes which
allow a more efficient implementation. I believe that my underlying merkle
tree is unambiguously superior in every way, but the question of whether a
mountain range is worth it is one which can only be answered empirically,
and that requires a bunch of implementation work to be done, starting with
me finishing my merkle tree implementation and then somebody porting it to
C and optimizing it. The Python version has details which are ridiculous
and only make sense once it gets ported, and even under the best of
conditions Python performance is not strongly indicative of C performance.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160614/a1bc30c1/attachment.html
original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-June/012758.html
submitted by dev_list_bot to bitcoin_devlist [link] [comments]

Bitcoin Sidechains & SPV Proofs Bitcoin most regulated currency in the world! Bitcoin Mining Explained in Detail: Nonce, Merkle Root, SPV,...  Part 15 Cryptography Crashcourse Bitcoin Internals: Verifying Merkle Roots using Merkle Proofs in JavaScript Bitcoin Blockchain Bitcoin at the protocol level

21504 Total views Crypto newbie Bitcoin is gaining popularity and the numbers of BTC users are constantly increasing too.The Mystery Behind Block Time – FACILELOGIN Investieren In Auxmoney The lower the target value, the more repetitions of the hash function a miner must go through in order to get an bitcoin target calculator acceptable result – in other words, the higher bitcoin client ... 1:1 DAPP REVOLUTION ““BITCOIN”, “BLOCKCHAIN”, “MERKLE ROOT”, AHHHHHHH???!??! — Almost Everyone. Fear not, this is the experience 99% of people exposed to distributed ledger ... The root node of a merkle tree, a descendant of all the hashed pairs in the tree. Block headers must include a valid merkle root descended from all transactions in that block. Not to be confused with: Merkle tree (the tree of which the merkle root is the root node), Merkle block (a partial merkle branch connecting the root to one or more leaves ... Why are Merkle roots used in Bitcoin? There are a handful of use cases for Merkle trees, but here we will focus on their importance in blockchains.Merkle trees are essential in Bitcoin and many other cryptocurrencies. They’re an integral component of every block, where they can be found in the block headers.To get the leaves for our tree, we use the transaction hash (the TXID) of every ... The Bitcoin wiki Vocabulary article explains why the Merkle root exists: Every transaction has a hash associated with it. In a block, all of the transaction hashes in the block are themselves hashed (sometimes several times -- the exact process is complex), and the result is the Merkle root. In other words, the Merkle root is the hash of all ...

[index] [41489] [29560] [4271] [17622] [17640] [48765] [950] [39575] [13176] [26639]

Bitcoin Sidechains & SPV Proofs

# Blockstream Sidechain Proposal: https://blockstream.com/sidechains.pdf # RSK Bitcoin Mainnet Sidechain w/ Solidity EVM https://media.rsk.co/bamboo-mainnet-... Bitcoin Mining Explained in Detail: Nonce, Merkle Root, SPV,... Part 15 Cryptography Crashcourse Part 15 Cryptography Crashcourse Dr. Julian Hosp - Bitcoin, Aktien, Gold und Co. And while 6 percent of all bitcoins allegedly went missing via MtGox, every year 3 percent of China's GDP goes missing into property and bank accounts in the US, Canada and Australia. They also ... James Turner will be covering Hashing and how it relates to bitcoin mining. P2P networks and CAP theorem with Distributed Ledgers. The Zeros and Ones. Cryptographic Signatures and Merkle Trees and ... Using a concept called a Merkle tree - in this video I break it down in depth with a simple example and show how a SPV node (Simple Payment Verification) node that does not keep a full copy of the ...

#