Mostly the claim that "The Difficulty is Intergalactic" is just flat wrong. Consider a miner on mars with 10% of the hash-rate on earth. Lets say the light delay from earth to mars is 10 minutes (it is 14 on average).
Now, suppose mars has last seen block B_0 and it was mined on earth (as would happen most often due to 90% of the hash rate being there). We will call E_1 the next block found if only earth were to mine, and M_1 the block for mars. Now, mars has two really big dis-advantages. First of all, earth gets to see B_0 ten minutes before mars does. So, earth can start mining a lot earlier. Second of all, when mars does find a block, but earth finds a block 10 minutes later, earth is going to orphan the martian block.
So, if mars has fewer than 20 minutes of advantage over earth, there is a very good chance any block they find won't matter.
Now, I suppose if the hash-rate is more spread-out over multiple planets, and one planet isn't dominating things might work out. But we might also see consensus break down. I might sit down and do the rigorous math on that tommorow, just to see what happens.
(Other minor nitpicks)
> SHA is Memoryless and Progress-Free
Technically false, because memory-less processes have positive probabilty of yielding no block after 2^256 tries, whereas for sha-256 using brute force, this probability is totally 0. I don't think this matters at the current hash-rate though. (our current hashrate covers about (2.5 * 10^-53)% of the entire output space every 10 minutes.)
> Trying a SHA Makes You a Participant
Only if you would actually submit your hash if you found a match. The same holds for the prime-factorization example. If I happen to factor a huge number and tell no-one I haven't contributed.
(I wrote the article) - I see your point, but I think the article is still correct. Now communicating the winning block is a problem, as you pointed out, so as a miner on Mars you're at a disadvantage, but that statistically the probability of solving the puzzle remains same regardless of your location in the universe is still true.
As someone else pointed out - for the intergalactic version we'd need an interval much longer than 10 minutes.
This is why 10 minutes was chosen by Satoshi probably - it's plenty of time for everyone to communicate the solved block, yet not too terribly long in "human time".
To put it another way: if there is a group of participants with spotty Internet that, after succeeding in calculating a hash, have only 10% chance of actually reporting it, then working backwards, we need to divide by .1 (multiply by 10) to calculate the number of participants. But if they have a 0% chance of reporting success, then we'd have to divide by zero. This is because they aren't actually participants. It's attempting to count non-participants.
I stand by my point though, for the purpose of totally ordering blocks, the difficulty is not intergalactic because a solution on mars is much less useful than a solution on earth. The problem here is time-delay preventing simultaneity. This is the same problem that block chain time-stamping hopes to solve. Thus it seems unfair to me to ignore this problem.
I wonder how tight the 10 minute mark is at the moment. I imagine there might be nodes that are 5 seconds apart on the network. Maybe even more when we have backhoe outages. How much lower could the 10 minutes be before we start seeing to many orphans even on earth?
It seems to me that different solar systems wouldn't be able to maintain a single blockchain, they'd each need their own.
> Technically false, because memory-less processes have positive probabilty of yielding no block after 2^256 tries, whereas for sha-256 using brute force, this probability is totally 0. I don't think this matters at the current hash-rate though.
You may be right about my use of "memoryless", though it won't matter at any hashrate :) "...brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space" (B. Schneier "Applied Cryptography").
Based on the current hash rate it would be about 10^40 life-times-of-the-universe to cover all possible hashes presuming no collisions.
It's not zero. It's very small, but not zero. The difference between being "theoretically exactly zero" and "very small" (yet practically zero) is why we can say SHA-256 is memoryless.
Moreover, lets assume there is an input that leads sha-256 to be our target (so the probability of finding a solution isn't 0 at all). Take the shortest input that meets our target, and call it L. Now, brute-force try all inputs up to length L. You know have P(find solution after 2^L tries) = 1. This cannot happen for a memoryless process.
If you pick your inputs randomly, it remains a memoryless process.
I'm no expert, but wouldn't it just be a matter of increasing the target time to solve each block? An solar-system-wide blockchain might need to take a few hours rather than ten minutes between each block, but it should still work.
Does a 10 minute delay require something like a 10 or 20 minute target time to keep consensus or is it more like 2 hours or even a day? How does is this effected by the ratio of hash-rates over the planets? What happens when you have clusters (say earth - moon and mars - phobos)?
In any case, if the target times need to increase by too much, things become infeasible. And I'd guess that at any given target time, there is distance from earth where computations no longer contribute to the hash-rate on earth. Thus, the claim that 'the hash-rate is universal' would be false.
You can use this to increase the fee of a transaction after the fact. So, suppose A has a fee of 0.001 in the first transaction, and the current fee needs to be 0.01 . Then, B has this transaction, but no-one will put it into a block, so B hasn't really received his money yet. A could sign another transaction with a higher fee that would send the money back to A. This could happen until the original transaction was actually deep enough in the chain.
But using your situation, B can do the same thing as A. B can create a transaction sending his own 0.999 BTC to another address of his, and include a fee here of 0.019 . In this fee, there is 0.01 to fund this transaction, and another 0.009 to fund the fee A forgot to include. Miners will see this, and include both transactions, and B is guaranteed he has his money.
Someone should have volunteered to help the Pineapple Fund do this instead of switching to Bitcoin Cash (or maybe this is what "Child-Pays-For-Parent" is, and it cost too much). https://news.ycombinator.com/item?id=15995391
>> Since this created a series of unconfirmed transactions, we had to do something drastic: use Child-Pays-For-Parent with a very significant fee.
Edit: You are always spending a specific input, so to broadcast B->C, B would have to wait for A->B and specifically name that transaction. The miner _could_ receive these transactions out of order, but that should not be an issue.
https://blockchain.info/tx/cffa18e3d519c31c8624fc2c3e498c0d9...
https://blockchain.info/tx/f24eaa493071e96f5bdf931204b893098...
Both transactions are in the same block (203732), the f24eaa tx is spending an output of cffa18.
[0] https://blog.keep.network/miners-arent-your-friends-cde9b6e0...
However, B can broadcast txB after receiving txA (txB essentially needs to know txA in order to "use" it).
The way this works is txA essentially says "send 1BTC I received from some tx to B". txB says "send 1BTC I received from txA to C". So, when creating the txB, B needs txA in order to use it.
Keep in mind this has nothing to do with txA or txB being included in blocks. txB can use txA if txA is not yet confirmed (so not in a block), however txB can only be included in a block (so confirmed) if txA is already confirmed in a previous block, or if both transactions are in the same block (this is where the part of a miner "ordering" the transactions from some other replies comes in play).
Part of being a valid block is "only spend BTC you have". B-to-A-first violates that.
Other miners would reject such a block as invalid and refuse to propagate it. Even if some did, the vast majority would not consider it valid, and the next published block (new transactions + proof of work) would extend from a block that didn't have that transaction in it.
There is no unspent transaction that B owns, so any transaction B creates to send money to C is invalid.
This is just not true at all?
for B to refer to A, it needs to know the transaction id.
Transaction ids are sha256(sha256(raw_transaction)) and a raw transaction consists of inputs and outputs. All this is known before the transaction gets put in a block--and has nothing to do with blocks.
Blocks and mining mitigate against double spending (...by burning an insanely huge amount of energy to do so, inefficiently. But that's a separate issue, at least right here)
I guess this has been said countless times before, but the role of proof of work is to establish a somewhat strange kind of identity among anonymous participants. If you had a trusted list of all participants, you could simply grant everyone one vote per block and decide by majority whether to accept or reject a block and get rid of the proof of work altogether. Of course using some cryptography to establish authenticity of votes and such.
But because Bitcoin is anonymous - or pseudonymous if you insist - there is no such list of participants and you need a mechanism to prevent participants from casting an arbitrary number of votes by essentially inventing identities. And this is what proof of work does, it limits your ability to invent identities and cast as many votes as you would like by making casting a vote really hard respectively expensive. The capital costs and the energy consumption of your warehouse full of ASIC miners become a proxy for your identity via their hashing power.
And that's it, nothing more, nothing less. The rest follows from here, for example a 51 % attack is just someone using a lot of money to buy more than half of all the available identities in the Bitcoin system granting him the majority of the available votes.
Is it so obviously wrong? From the first paragraph of the introduction to Satoshi's Bitcoin Paper: "In this paper, we propose a solution to the double-spending problem using a peer-to-peer distributed timestamp server to generate computational proof of the chronological order of transactions".
GPS is a trusted system, whereas bitcoin is designed to be completely trust-less. The reason why timestamping is a difficult problem is that if I publish two transactions spending the same money, the network must agree on the order of events (which is to say: must assign different timestamps to the two transactions) so that one is considered valid, and the other invalid. Doing this without proof-of-work leaves you vulnerable to Sybil attacks, where I can pretend to have an overwhelming amount of nodes in the consensus, and vote for the more favourable (to me) transaction to be considered the canonical one.
No, the system must not decide on the temporal order of your two transactions and in the extreme case, if you make them at the exact same time, it can not because neither one precedes the other one. In this specific case of an attempted double spending the system must only decide to accept at most one of your transactions and it must agree on which one gets accepted, if any. If one of the transactions gets accepted this will establish an ordering of the two transactions but this ordering is a result not an prerequisite.
A miner may randomly include any one of your two transactions, if individually valid, without regard to the time it was made. The inclusion in an accepted block then renders the other transaction invalid but this is still not really judgment about the time those transaction were made at, it is just a statement that one is valid and one is invalid.
Ordering is really only important insofar that you can only spend coins that you have received before, i.e. a spending transaction must not precede a receiving transaction. And even then the order in which the transactions are made does not matter. Nothing stops you from creating a spending transaction before the receiving transaction, the spending transaction will just be invalid and not get included in a block until the receiving transaction is made and included in a block.
Whenever I want to spend money, I just commit a changelog to my repo, I want to transfer some credit to identity X, signed with my identity (private key). I sign the ledger with my private key and commit the entry to the distributed store. Push out the changes to anyone who will listen. If you want to forget my identity and transactions, you may, but if I'm credit worthy, my identity will probably be remembered and followed.
Github could remember a repo for each of us, but users of the network would want to mirror the repos, index the repos, and keep an eye out for modified histories.
I imagine there are likely problem(s) with the idea, can someone explain the problem?
Chapter 3 - Timestamp Server
A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper or Usenet post [2-5]. The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.
Chapter 4 - Proof-of-Work
The proof-of-work also solves the problem of determining representation in majority decision making. If the majority were based on one-IP-address-one-vote, it could be subverted by anyone able to allocate many IPs. Proof-of-work is essentially one-CPU-one-vote. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it. If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains.
It is well-known that pure cryptography is strictly weaker than cryptography + economic assumptions or cryptography + subjectivity assumptions, due to some inherent information-theoretic asymmetries. For instance, pure cryptography allows us to prove that the owner of the secret key of a given public key has signed a message, but it cannot let us prove that the owner of a secret key has NOT publicly signed a message. A way to do this by relying on economic and non-coordination assumptions is to offer a public bounty (ie I will pay some USD) to anyone who can provide the signature and then to wait some time to see if anyone turns up. Another example: with pure cryptography it is easy to produce "private randomness" (say between 2 people) by using a commit-guess-reveal scheme, but a third party later who cannot trust that the two were not colluding cannot be convinced that the output was random. But once again this is possible with economic assumptions.
As for the distinctions between different kinds of non-cryptographic assumptions, I don't think it's clear-cut. Timestamping is strictly weaker than proof of publication (https://petertodd.org/2014/setting-the-record-proof-of-publi...), which is equivalent in strength to a distributed ledger. I'm not sure the anti-sybil assumptions have been modeled as such, but it is well-known that anti-coordination assumptions are needed even if we assume no double-spends are possible (e.g., a pool of 70% of btc hashpower can profitably censor the other 30% by orphaning their blocks; no double-spend needed!)
I meant this in the straight forward sense and what GPS essentially provides, a means to globally agree on the current time with a reasonable high resolution.
Suppose we have an oracle that implements this protocol: it publishes a new public key every hour, and at any time someone can present it a blob of data which it will sign with the private key corresponding to the current hour's public key. Furthermore, you can query it for the set of all blobs it has signed with a given public key.
You don't state it explicitly but from »[...] the set of all blobs it has signed with a given public key [...]« I assume more than one blob can be signed with any key pair and I would then also assume every user can get an arbitrary number of blobs signed with each key pair, right? Or did you imagine a limit per user or key pair?
It is obvious that one can implement a distributed ledger with the only security assumption (for each user) being "I trust this oracle" and "I can determine the current time".
This is, at least to me, not obvious and I tend somewhat towards thinking is it not possible or at least not easy. If my interpretation from above is correct and there is no limit on the number of blobs that can be signed with each key pair then it seems to be at least non-obvious how one could reimplement Bitcoin on top of the oracle. Everyone could just fork and create arbitrary long chains of blocks because there is no proof of work slowing the participants down which I turn means that the longest chain is not necessarily the one that the majority considers valid.
Only if the oracle had a limited capacity and all participants flooded the oracle with request as fast as possible one could hope that the majority would be able to create the longest chain assuming the oracle processes all requests fairly. Maybe there is a way [substantially different from Bitcoin] to build a distributed ledger on top of this oracle but, as already said, it is at least to me not so obvious that I could quickly figure out how to do so.
> the role of proof of work is to establish a somewhat strange kind of identity among anonymous participants.
The role of proof of work is to make the creation of information one-way based upon a pre-specified amount of work. Therefore, in a properly constructed system, a participant cannot steal the results created by another party.
Identification is generally accepted in the security community to come from something you are (biometrics), something you have (bank card), and something you know (pin for your bank card, password, etc). For safety, two separate classes are normally and simultaneously required for identification, hence the term two-factor id.
An identity is something entirely different from work. Proof of work, since it is one-way, proves that work was performed. This has nothing to do with identity, which cannot be proved by work.
Something You Can Do is not a new category of identification but a statement about processing power. This can be seen by simply sharing the private key of a wallet. In two factor identification, you could make a copy of someone's eye or face to try to get into a system, but two factor identification would stop you.
> And this is what proof of work does, it limits your ability to invent identities and cast as many votes as you would like by making casting a vote really hard respectively expensive.
Proof of work doesn't have anything to do with the ability to invent identities. It ties the result of processing power to keys. Digital keys are not identities any more than physical keys are houses. To construct a house, you need to perform the work. To get into a house, you need a key. To take possession of a key you need to identify yourself.
> a 51 % attack is just someone using a lot of money to buy more than half of all the available identities in the Bitcoin system granting him the majority of the available votes.
A 51% attack is when someone who may or may not use a lot of money forces an alternate version of a blockchain data structure by having 51% or more of the processing power. This has nothing to do with purchasing identities. You can test this for yourself. If you create two bitcoin wallets, you clearly didn't create two digital identities. You are the identity in possession of two keys for two separate wallets.
Besides, a 51% attack isn't 51% of the nodes but 51% of the processing power, which could be only 1 powerful node. Those are entirely different.
That makes no sense, or the meaning is at least not obvious. What does it mean to make creation of information one-way? Proof of work is just a vote allocation scheme. We want to reach consensus about what the transaction history is and do so by a majority vote and therefore we have to decide who gets how many votes.
This alone has no single obviously correct solution, for example, if I have a company with a company account, do I get one vote for the company or do I get a thousand votes because the company has a thousand employees? Or maybe votes proportional to the amount of money in the account? And if the system is anonymous it gets even harder because there is no easy way to know who cast a vote or if someone cast a million votes.
And that is the way in which I used identity, the identity of an entity allowed to cast a specific amount of votes. And that is what proof of work does, a collection of mining hardware establishes an entity with a voting power proportional to its hashing power.
Identification is generally accepted in the security community to come from something you are (biometrics), something you have (bank card), and [...] An identity is something entirely different from work. Proof of work, since it is one-way, proves that work was performed. This has nothing to do with identity, which cannot be proved by work.
As explained above, I was not using identity in the computer security sense but in the sense of the identity of entities with a certain amount of voting power. And all your other remarks essentially also hinge on a misunderstanding of my use of identity, if you read it as entities with voting power it will certainly make more sense.
Perhaps the idea is more clear if it's framed in terms of votes rather than identities. Mining on top of a particular fork can be viewed as voting for that fork. Each participant's number of votes is proportional to their hash power. Double voting is impossible since the same hardware can't mine on more than one fork without splitting its hash power.
So here, the bitcoin network needs to defer to the actual time. The difficulty is adjusted every 2016 blocks. Then, the time it took to create those blocks is determined by looking at actual time stamps of the blocks. That is, time stamps that purport to be the time in UTC when the block was created.
I never understood how these time stamps are trusted and reliable. If I recall correctly, a block with a creation time that is 'too far of' is supposed to be rejected by well behaving nodes. Yet, getting accurate time-stamps is the problem bitcoin is trying to solve.
I suppose that for almost anyone, it is feasible to get time accurate down to 60s and that might be enough that the difficulty calculations aren't affect as much. Especially due to the averaging over 2016 blocks.
edit:
I found this link en.bitcoin.it/wiki/Block_timestamp it states that:
> A timestamp is accepted as valid if it is greater than the median timestamp of previous 11 blocks, and less than the network-adjusted time + 2 hours. "Network-adjusted time" is the median of the timestamps returned by all nodes connected to you.
So the limits are quite loose.
(An interesting footnote from memory)
The difficulty calculation contains a bug where it calculates the average block time ignoring either the first or last block. Thus, the block time is slightly wrong. However, changing this would be a hard-fork because 'the running concensus code is the spec'. That is, if you fix this bug everyone has to fix it at the same time.
If you choose a time obscenely short (say, 1 second after the last block), presumably the difficulty is an average of many created blocks, and it would take a lot of malicious actors to make this valid.
Plus, if Block A is found at 10:00, and I find Block B at 10:10 but say it was 10:01... and then Block C is found at 10:20, the average of these three is ~10 minutes still.
What is required however it that a timestamp be at least the median of the last 11 blocks.
I guess for difficulty adjustment purposes, that's not a hard requirement, it'd be closer to "plausible and consensus agreed timestamps". It doesn't matter much if a bad actor can try to slightly influence the raising or lowering of difficulty, so long as the long-term once every ten minutes "clock tick" holds and can be used to define transaction ordering.
When orphan blocks are identified and dropped, any unique transactions in those blocks are added to the pool of transactions that have the opportunity to be added to the next block
Well behaved Miners will always mine on the longest chain, and get to pick if there are two chains of equal length. Most probably pick the first they saw, because it gives them more time to work on that block.
So if an orphan comes along, people ignore it. Like other have said, all nodes know about almost all transactions, so the next miner will just see those transactions as still being 'up for grabs' and might include them in the next block they are attempting.
Not necessarily: https://en.wikipedia.org/wiki/Logical_clock
Proof of work is the leader election phase of consensus. It is followed by the accept phase, where the leader broadcasts the decision to be accepted. The commit comes eventually and as probabilistic.
This is a common misconception stemming from looking at PoW through the Paxos/RAFT prism. In Paxos a leader is elected, then the leader decides the order of events. But that's not a valid comparison, because in PoW the supposed "leader" does not get to decide anything at all - the block has to be put together prior to "winning the election" (because the block is the input to the SHA).
PoW is a radically different approach - there is no leader, but there exist indisputable points in "blockchain time", and the order of blocks is determined by the longest chain, which is essentially a matter of chance.
Another related misconception is that PoW is good, but proof-of-stake is better. In fact, PoW is the evolution of PoS, not the other way around. A PoS based digital money was described 1998 by Wei Dai [1], but that approach had flaws that would only be overcome by a system described Nakomoto's Bitcoin paper.
1. http://www.weidai.com/bmoney.txt (B-Money, Wei Dai, 1998)
"Each server is required to deposit a certain amount of
money in a special account to be used as potential fines
or rewards for proof of misconduct."You speak authoritatively, saying "this is a common misconception", but blockchain is a distributed consensus protocol and I don't think you are familiar with multileader and leaderless flavors of distributed consensus.
Who picks the transactions from the mempool that will be serialized into history?
It being a "matter of chance" may be false and thus the thesis that this clock is "decentralized" should be questioned. There are situations where there will be conflicting blocks and no block gets orphaned unless a central authority commands it to be so. This was seen in the 2013 Bitcoin fork, when Pieter and Luke ordered the miners to move away from the majority chain (0.8) onto the minority chain (0.7) and this was also seen in 2016 when Vitalik ordered that a permanent chain divergence (ie. fork) happen. In both cases, the blockchain split and a central authority was necessary to resolve the conflict. It was not a matter of chance. The fact that this clock can have permanently divergent chains and that a central authority is required to say which chain should be chosen as the right one means that this clock is not decentralized.
https://bitcoinmagazine.com/articles/bitcoin-network-shaken-...
You can see how the developers behaved like a central authority in the IRC logs of the bitcoin-dev channel. More info here: https://freedom-to-tinker.com/2015/07/28/analyzing-the-2013-...
In [0], the authors argue that Bitcoin, in particular, is a partially-synchronized global clock, and they take advantage of it in [2] to make a hybrid blockchain-DB system that provides more traditional eventual consistency guarantees.
NOTE: I'm not an author of any of these papers, just a casual observer
[0] https://eprint.iacr.org/2016/454.pdf
While this is a cute way of looking at the issue it also isn't true. The bitcoin blockchain gets updated on average every 10 minutes with the data produced by proof of work.
The author is saying that the cart pulls the horse, because they are both moving.
[0] https://en.wikipedia.org/wiki/Logical_clockActually, this is only partially true. With Lightning, things can most certainly "happen" in between blocks. Granted, some things that "happen" may never make it to the main chain, but many things will get rolled up and committed for all to "see".
This is, ironically, how reality works.