Proof-Of-Work is a Decentralized Clock
grisha.org
grisha.org
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.
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'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.
So if a block takes X minutes with a 20% variation at, say, 95th percentile, and the inter-planet latency is 10 minutes, then I think the target time (X) must be more than 100 minutes, so that if Earth mined the last block, Mars can receive it 10 minutes late and still have a chance of mining it first and reporting it back before Earth finds it.
But I'm probably totally wrong :)
My idea is just that if you increase the target time quite a bit, Mars would get lucky more often.
In fact, this already happens: if an European miner wins a block, then why don't other European miners always win the subsequent blocks, since their latency to the winner is lower than American or Chinese miners? It's because the few miliseconds extra are not relevant when a block takes 10m on average to find.
My idea is just to increase the target time so that the 20mins latency are also not relevant.
(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".
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?
We're talking apples and oranges, I don't think there is a disagreement - I was only saying that the statistical problem is "intergalactic", not that how it's used in Bitcoin is useful across galaxies. The fact that the probability of the outcome is same across the whole universe is what I found particularly remarkable.
It would be problematic with regards to money creation though. As we get more blocks per 10 minutes, we get more block-rewards (new bitcoin) per minute.
It also seems weird to 'amend' history by saying some other stuff also happened.
Thinking of this, could you maybe use this to somehow block a payment by adding a 'past block' that already spends the bitcoins in your payment?
It seems to me that different solar systems wouldn't be able to maintain a single blockchain, they'd each need their own.
Of course, for every-day transactions there were also "fast" currencies where transactions were settled more or less instantaneously, and "medium" currencies where it would take longer but still be reasonably quick (probably for transactions between parties on different planets in the same system, but I don't recall that it was specified exactly).
Given the characters seen in the book, I think founders mainly try to set themselves up as president for life of some planet or moon in the new system. Another example shown in the book is emigration; once you're sufficiently wealthy you emigrate back to some place nice where you can enjoy it. Of course that requires building a starship, which pretty much requires setting up a successful civilization that can support a starship industry.
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.
> 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.
Your assumption is wrong. Theoretically, there might be no inputs that are solutions to the PoW. Of course in practice there are almost always a large number of solutions, but again the theoretical possibility of it is why it is correct to say the PoW is memoryless.
Even if theoretically there was always a solution, there is no way to iterate sequentially over all inputs because after iterating over 2^32 nonces, miners have to change the 256-bit merkel root, which is effectively random. This aspect alone makes mining memoryless.
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.
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.
Note that the paper says "_also_ solves", implying that the "representation in majority decision" part is secondary. If you think about it, the winning miner does not really get to decide anything at all, since the block has to exist before the winning SHA is found since it is the input to the SHA.
The only way you'd get this level of accuracy with a traditional clock is if you could measure/record Planck Time, which isn't possible and might never be. And if we could have Planck Time accuracy clocks, such a timestamp wouldn't come with a cryptographic proof like the PoW timestamp.
Everything else is secondary, an add on. The ordering is determined be the longest chain, recorded as a Merkle tree, transactions are tied by the strength of Elliptic Curve crytpography, miners motivated by rewards, etc.
But without that timestamp, none of it would work.
But that is all without consequences, nobody will know about this event until you broadcast and they receive your block. And the message about the new block will arrive at different nodes at different times. End if you are really inclined to pull physics into this - which in my opinion hardly makes any sense - you have to face the fact that simultaneity is relative.
So you are really not tying the discovery of the new block to any specific point in time. Everything anybody can really say is that it happened before they received the block and after the block that is referenced by the previous block hash was mined which itself may have happened any time before they first received that block.
The previous block hash establishes a happened before relation between the events of creating the blocks in the chain and including a transaction in a block establishes a happened before relation between the creation of the transaction and the creation of the block. But nothing ties anything to any specific point in time. And proof of work plays no role here at all, you can simply calculate a single hash of a block and send it to me and that proofs that the block existed before I received that hash, no need to work hard to find a fancy hash with many leading zeros.
The fact that the block time (i.e. height) is when the conforming SHA was found is indisputable. Also that no other block happened at this same point in time.
It does not, it just sets a lower bound on the time. I can totally mine a block linking directly to the genesis block today. All it proofs is that it happened after the previous block was created. And so does SHA(<GenesisBlock>) without any mining.
Also that no other block happened at this same point in time.
Also not true, I can totally mine several blocks all linking back to the same block. And with some luck that might also happen at the exact same point in time.
At the risk of sounding like a broken record: when the SHA puzzle is solved is the exact point at which the block which is the input to the SHA is mined. I sounds almost "duh - what other time could it be?", but upon some reflection, this is quite remarkable, because a point in time is tied to a block of data.
The rest of it, e.g. what block that block points to as a parent, is secondary and not that interesting.
I don't get it, so let's try once again. You mine a block, say this [1] one. How is it tied to any particular point in time? It includes a time stamp but that is not the time the block was mined, the block may have been mined before or after that point in time, no way I can tell just from looking at the block.
There is also the hash of the previous block [2] in there but that does not tell my at which point in time the block was mined either. The only thing I can conclude is that the block was mined after the block referenced by the previous block hash but there is no indication of how much time passed in between. And looking at the previous block does not help either because there is nothing in there indicating any point in time.
Or even better, let's do a thought experiment. With a fast enough computer I could have performed all the calculations of the last ten years that led to the Bitcoin block chain as of today within the first hour after the genesis block was mined on January 3rd 2009. Identical to the very last bit. But none of the blocks would have been mined at the same point in time as they were in the actual Bitcoin block chain. I obviously would not have known any of the transactions that would occur over the next ten years but I could of course have guessed them.
Or let's not be that wild and mine the entire Bitcoin block chain within one hour, let's just imagine all the blocks were mined one second earlier than they actually were. This hypothetical Bitcoin block chain could also be identical to the very last bit to the actual one but again none of the corresponding blocks would have been mined at the same point in time. And the fact that two bit-identical block chains could exist but where no two corresponding blocks were mined at the exact same point in time proves that nothing in there ties any block to a specific point in time.
[1] https://blockchain.info/block/0000000000000000001f6d740116db...
[2] https://blockchain.info/block/0000000000000000001a1c88ce0b57...
You can't know precisely what "human" time it was in hh:mm:ss, nor does it matter (because the blockchain operates in its own clock). But you do know the "blockchain time" (which is the parent height + 1).
Your first example block was mined exactly at blockchain time known as "height 518807" the second at 518806.
Note that the (first) block happened exactly, not a femtosecond before or after, but exactly at "height 518807". Such precision is not possible with our "human time".
Also note that this is not precise in any meaningful sense, neither in the case of Bitcoin nor in the case of my FTP clock, we are just labeling random points in time with names like »the point in time I found block 12345.« or »the point in time I created the subdirectory 42«. I could throw a plate against a wall at label that as »the point in time that plate hit the wall«.
This labeling does not establish any regular interval, it does not help identifying what this point in time was or what else happened at this point in time. It's a trivial tautology, every event happens at exactly the point in time it happens. And every clock is as precise - in your sense - as Bitcoin, the exact point in time this clocked switched from 11:59:59 to 12:00:00 is not different at all from the exact point in time you minded block 12345.
Maybe that clock was actually 5 minutes fast and it was really only 11:55:00 but that is inconsequential for the way you use »price«, every tick of that clock still labels a precise point in time. But an actual good clock is useful because it assigns labels like »2018-04-18 19:49:17« at regular intervals with some precision depending on the nature of the clock. Bitcoin, the FTP clock, and the plate hitting the wall are useless in that sense because the relation between points in time and the assigned label are to a large extend random. You could use Bitcoin as a crude clock with an time resolution of about ten minutes but that is not a good clock.
Finally note that the Bitcoin clock does not even really tick at the point in time you mined a block because that block might get orphaned or simply rejected for whatever reasons. Only in hindsight can you say that it ticked when this or that block was mined, once there are enough blocks on top of it that it becomes reasonably unlikely that another chain might become the longest one.
Wait, finally finally. What is the point in time you mined block 12345 exactly? There are zillions of subatomic particles moving around in you mining hardware, how would you ever be able to pin down precisely when you mined a block? Did you mine it now or do you have to wait until this electron over there also passes through that transistor here and increase the charge on the capacitor to the left another tiny bit? When you really think about it, the point in time you mined block 12345 becomes quite a fuzzy concept at the microscale. And so even before you start thinking about the uncertainty principle or relativity.
It is precisely this problem that Proof-of-Work (they way it's used in Bitcoin) solves.
OK, I think I'm beat trying to explain this :)
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?
If you're my friend or a business, and you see my balance is deeply negative, maybe you don't give some service.
If your my friend or a business, and my credit is not too bad, you follow my repo and give me some service. You commit a change that says, (pubkey:ae32...) paid (pubkey:af41...) 10 US dollars and reference my repo and commit.
I don't think there could be double spending because the receiver of the money acknowledges the credit offer on record (the git repo that paid).
If there are identities and entries in my ledger that are questionable, maybe you don't count them. For example, you might say credit only counts from those identities that are willing to answer a two-factor sms challenge. Or, if my git repo is credited by a google account, that's something worthwhile that could count toward my balance.
"USD is one option"
And now you have no restriction on the money supply.. USD is coins.
If I say I owe bitcoin, that's a transaction where I cash into bitcoin and then resolve my debt via bitcoin, but do I want my debt in bitcoin, maybe, but the value does vary more than USD.
A credit agency might not care if you improve your credit (by paying or resolving debts) in bitcoin, or may also give the option of cash or some other cheaper transaction form.
Maybe I am missing something but I have no idea how that could ever work unless this is essentially just the current banking system were I know that A is a trustworthy bank and I will be able to redeem your $500 check. Augmented with the anti-feature that we are now all broadcasting our balances and all our transactions to everyone.
If A, B and C are all the same person and there wasn't an identity attached to any account, outsiders wouldn't value the record much, especially if they were transactions of significant value.
C could redeem the value with Western Union (or similar agent). They might say you have to agree to sign the closure of the account to no longer modify the balance of the account. They'd basically be like a collections agency, buying debt.
You'd be able to have similar plausible deniability as Bitcoin. Coinbase sees the transaction flows and the ledger is public. You could do business as a pseudo identity ( Do business as C, if you're B )
Combining this, you essentially get GNU Taler: https://taler.net/
No proof-of-work, just a way for people to get digital money (representing USD, gold, or anything else) issued by A (Exchanges). And rather than regular signatories they use blind ones, so that A doesn't even know that B spent its coins on C.
Right. The only way B "really" has a balance of $1000 is if A is some established, trustworthy entity - e.g. an actual bank. And trustworthy entities that offer service to anonymous people don't stay trustworthy for long.
Modified histories are not that simple to deal with, because network propagation times mean that I can broadcast two different transactions to different parts of the network and base the attack on the ensuing race to reach consensus.
> 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.
A one-way function is a function that cannot easily be reversed but can be easily computed. One example of such a function is a hash function, such as what is used in bitcoin's proof of work.
> What information are we creating and what is this one-way that we can not go back?
Hash functions are one-way functions that create hashes.
> Do you mean to ensure that the information can not be destroyed after it was created?
You seem to be commenting on the wrong subject or replying to the wrong comment. "I" do not mean to ensure anything with Bitcoin's PoW function, since I am not Satoshi and did not design Bitcoin. However, Satoshi designed Bitcoin's PoW using a one-way function. If it were not a one-way function, then Bitcoin's PoW system would be broken.
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.
I was pointing out the anomalous use of "identity".
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.
You can modify the rules of the protocol to be slightly more complicated to relax the "no more than 1 tx/account/hr" rule optimistically.
Having such a trusted anchor of truth about all the requests ever made and their order is a pretty powerful primitive. At first look there is really only one problem beyond this that needs attention, making sure that not everyone can change everything, i.e. there will certainly be parts of the system state that should not be alterable be everyone, for example transferring money from your account to someone else.
But that seems reasonably easy to solve just the way it is done with Bitcoin and many other system. When you initially create an object that requires authorization ,you associate one or more public keys with it and requests to alter this object are only valid if the request passes a publicly verifiable challenge, for example being signed with an associated private key.
But this system seems not really interesting, it simply places the burden of serializing all request and guaranteeing their immutability in a trusted system and burdens all participants with the computational load to determine the current state of the system. At the expense of keeping the entire state of the system around, participants could just apply the set of new requests to their copy of the system state to lower their computational load and not have to request and process all requests every time they need the current state. This also lowers the network load.
But if we are already trusting the oracle to not mess with the requests received, it does not require much additional trust to let the oracle maintain the current state by applying all requests as they are received. Then participants could simply ask for the current state or parts of it and would not have to deal with all the requests or the entire system state. At which point we have an ordinary client server application with a database.
Initially we only had to trust that the oracle does not reorder request, delete requests, or insert new unsigned requests. If we do not compute the current state ourselves and just request it from the oracle, the oracle could additionally invent new signed requests without having the private key, for example it could just report changed account balances without there being any signed transaction that authorized that transfer. As long as the oracle still provides the set of all transactions, we could at least double check that.
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?
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.
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
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.
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.
[0] https://blog.keep.network/miners-arent-your-friends-cde9b6e0...
There is no unspent transaction that B owns, so any transaction B creates to send money to C is invalid.
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.
Check again: the first TX pays to 12Pws7qasVjt7uKfT6woQptx1MLNj2mo44, the second spends from it.
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)
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.
Yep, this is what that means. The downside is that the 'child' transaction doesn't just pay for the 'parent' transaction, but also for the 'child' transaction itself. If you make the child transaction a really complex one that draws from many parents, that transaction becomes larger (in terms of bytes) and thus becomes more expensive.
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).
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-...
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_clockNot necessarily: https://en.wikipedia.org/wiki/Logical_clock
Actually, 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.