22 ms·

Proof-Of-Work is a Decentralized Clock

232 points by gtrubetskoy 9y ago

xamuel 9y ago
Can someone who knows the technical details of bitcoin answer the following questions? Suppose initially A owns 1BTC and B owns 0BTC. Suppose A publishes a signed transaction that would give 1BTC to B, and simultaneously B publishes a signed transaction that would give 1BTC to C. If a miner includes both transactions in a block, is the block valid? Does it depend on the order of the transactions within the block (A's transfer to B preceding B's transfer to C)?
- sly010 9y ago
  The block is valid only if the transactions are in the correct order, but the miner is incentivized to figure out the right order (specifically incentivized to include as many transactions as possible). 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.
- SilasX 9y ago
  The protocol says to only accept valid blocks. 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.
- Terr_ 9y ago
  A side topic you might find interesting, "Miners are not your friends" [0] which focuses on ways that miners have a mechanism and incentive to subtly exploit some badly-made interactions. [0] https://blog.keep.network/miners-arent-your-friends-cde9b6e0e9ac https://blog.keep.network/miners-arent-your-friends-cde9b6e0...
- nordsieck 9y ago
  No. In bitcoin, you don't spend from an account. You spend "unspent transaction output" or UTXO. There is no unspent transaction that B owns, so any transaction B creates to send money to C is invalid.
  - tylersmith 9y ago
    They can't actually do it simultaneously but after A sends to B, B can create a transaction spending that output to C and both transactions can occur in the same block.
- gtrubetskoy 9y ago
  Yes (as sly010 pointed out), here is an example: https://blockchain.info/tx/cffa18e3d519c31c8624fc2c3e498c0d9bfc64d009b23c3b076a50faa0048240 https://blockchain.info/tx/cffa18e3d519c31c8624fc2c3e498c0d9... https://blockchain.info/tx/f24eaa493071e96f5bdf931204b8930989f1563505ac28f7237d74bab7ee143f https://blockchain.info/tx/f24eaa493071e96f5bdf931204b893098... Both transactions are in the same block (203732), the f24eaa tx is spending an output of cffa18.
  - joeblau 9y ago
    None of the addresses in your examples are the same.
    - gtrubetskoy 9y ago
      >None of the addresses in your examples are the same. Check again: the first TX pays to 12Pws7qasVjt7uKfT6woQptx1MLNj2mo44, the second spends from it.
- deleted 9y ago
  [deleted]
- deleted 9y ago
  [deleted]
- drdrey 9y ago
  B would need to refer to a transaction output that has at least 1 BTC to be able to sign a transaction sending 1 BTC to B. Until A's transaction is included in a block, B can not do that.
  - rpearl 9y ago
    > Until A's transaction is included in a block, B can not do that. 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)
    - drdrey 9y ago
      But is it valid to refer to a transaction hash that only exists in the mempool? The transaction you refer to has to exist in history, which means it has to live on the longest chain, no?
- rocqua 9y ago
  Yes, and this actually has a use. 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.
  - discussedbefore 9y ago
    > increase the fee of a transaction after the fact 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 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.
    - rocqua 9y ago
      > maybe this is what "Child-Pays-For-Parent" is 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.
- xilis 9y ago
  I believe the exact scenario you propose is not possible. It cannot happen simultaneously (so A broadcasting his tx - txA and B broadcasting his tx - txB at the same time). 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).
lainga 9y ago
On the last section, is a better name for it "Proof-of-Time" or "Proof-of-Tick" (not that we can likely change the popular name, the cat's out of the bag)?
- gtrubetskoy 9y ago
  I like Proof-of-Tick :)
throwawaysecops 9y ago
> Nothing Happens Between Blocks 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.
ptest1 9y ago
But it isn’t a clock because it doesn’t tell us how much time has passed. PoW allows for the creation of an ordering. I’m not sure these metaphors are helpful.
- Terr_ 9y ago
  > But it isn’t a clock because it doesn’t tell us how much time has passed. Not necessarily: https://en.wikipedia.org/wiki/Logical_clock https://en.wikipedia.org/wiki/Logical_clock
- ghayes 9y ago
  I believe the reference is to a vector clock [0] [0] https://en.wikipedia.org/wiki/Vector_clock https://en.wikipedia.org/wiki/Vector_clock
  - ptest1 9y ago
    That makes a lot more sense, thanks.
- tylersmith 9y ago
  It tells you the time in number of blocks. Block height is the unix timestamp of blockchain-based timestamp servers.
panic 9y ago
Wouldn't a proof-of-time scheme have a bootstrapping problem? You need some way to unforgeably (and fairly) generate your Bitcoins before anyone will care to trade them with you.
rocqua 9y ago
> The Bitcoin Difficulty adjusts dynamically so that a proper hash is found on average once every ten minutes. 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.
- johnmaguire2013 9y ago
  If you choose a time in the future, other nodes could reject you. 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.
  - tromp 9y ago
    There is no requirement that timestamps be nondecreasing. A block at 10:00 can be followed by one at 9:59. What is required however it that a timestamp be at least the median of the last 11 blocks.
andrew1000 9y ago
The article references "orphans" in blockchain, what becomes of those orphans? My understanding is that nodes compete to solve the hash - then the "winning" node has its transactions from the preceding 10 minutes added to the blockchain. What about all the other (thousands?) of nodes that didn't win - their transactions must not vanish into the ether, but what becomes of them? They must get added to the blockchain at some point otherwise something like bitcoin would collapse on itself, but i've never been able to wrap my head around how that happens.
- deleted 9y ago
  [deleted]
- oillio 9y ago
  All the nodes have all the transactions (roughly). When you say the winning node puts "its" transactions in the block, that is really the transactions that it is currently aware of, and that fit in the block. All the losing nodes have the same transactions as well. 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
  - icebraining 9y ago
    Well, most of the transactions will be the same, but they can have some transactions the other doesn't, depending on what transactions they received and then chose from their own mempool. It's just that those transactions who got inserted into the "losing" block - but not in the "winning" one - will be kept around to be added in a new block in the future.
- rocqua 9y ago
  Those orphans are treated like someone trying to 'fork' the blockchain by working on an older block, and trying to get a longer chain. 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.
nikisweeting 9y ago
Looks like this article describes a system that's very similar to http://solana.io http://solana.io
aey 9y ago
We are building a ledger based on Verifiable Delay Functions. It's like a high resolution decentralized clock. https://github.com/solana-labs/solana https://github.com/solana-labs/solana
rocqua 9y ago
I think some of this is kind of wrong. 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.
- icebraining 9y ago
  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'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.
  - rocqua 9y ago
    Yeah, but it is quite interesting what the relevant target times are. 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.
bitxbitxbitcoin 9y ago
Well put, sir!
mad44 9y ago
https://muratbuffalo.blogspot.com/2018/03/anatomical-similarities-and-differences.html https://muratbuffalo.blogspot.com/2018/03/anatomical-similar... 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.
- gtrubetskoy 9y ago
  > Proof of work is the leader election phase of consensus. 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 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."
  - mad44 9y ago
    Leaders don't decide. They propose values (such as a block of transactions). There may be multiple leaders with different proposals and participants get to a consensus about which proposal gets accepted for a given slot. 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.
  - relyio 9y ago
    > 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). Who picks the transactions from the mempool that will be serialized into history?
danbruc 9y ago
This analysis is obviously wrong, if the important thing was establishing a global clock, you could just use GPS receivers. Ordering transactions works also without proof of work, just including a hash of an existing transaction or block in a new transaction or block and this proofs the order of those transactions or blocks relative to each other. No clock required at all. And also exactly what Bitcoin does but which is totally unrelated to the proof of work. 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.
- pdpi 9y ago
  > This analysis is obviously wrong, if the important thing was establishing a global clock, you could just use GPS receivers 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.
IncRnd 9y ago
> The Bitcoin blockchain Proof-of-Work is simply a distributed, decentralized clock. 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.
xmly 9y ago
Decentralized TimeStamp Server... This is clearly wrote in the bitcoin white paper. Why is this becoming a news?
- ajkjk 9y ago
  It's just a blog post; not necessarily 'news'.
hudon 9y ago
> There is a separate consensus in a rare but common case of two consecutive ticks being associated with conflicting blocks. The conflict is resolved by what block will be associated with the next tick, rendering one of the disputed blocks “orphan”. How the chain will continue is a matter of chance 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.
- sethgecko 9y ago
  Fascinating, I found this article by Vitalik that explains what happened. In v0.8 they swapped from BerkleyDB to LevelDB but due to a bug the two chains started diverting. https://bitcoinmagazine.com/articles/bitcoin-network-shaken-by-blockchain-fork-1363144448/ https://bitcoinmagazine.com/articles/bitcoin-network-shaken-...
  - hudon 9y ago
    Yup, we'll never know if the bug was intentional or not, and that's why the fix being centrally coordinated is scary. Maybe it was a legitimate mistake, but maybe one of the developers planned this and executed large double-spends on the 0.8 branch because he knew 0.7 would be ultimately chosen. The fact that nothing prevents this type of attack is worrisome. 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-bitcoin-fork-centralized-decision-making-saved-the-day/ https://freedom-to-tinker.com/2015/07/28/analyzing-the-2013-...
tchitra 9y ago
While the analysis contained in this article is rather arbitrary, blustery and imprecise, there is a mechanism by which blockchains can serve as 'partially synchronized clocks.' One interesting facet about Bitcoin is that the model under which you analyze the effect of network delays can give you different results about how unsynchronized local copies of the blockchain can become. In the paper, "Analysis of Blockchains in Asynchronous Networks" [0], a certain (and more realistic) model is used in which adversarial miners are allowed to delay forwarding of blocks that they receive. The goal of this model is to describe how networking can account for changes to the probability of selfish mining [1]. The authors of [0] prove that for Bitcoin, under some assumptions about the maximum delay an adversary can use and the block production rate, is consistent because it has both a lower bound on how much chains between different participants can differ as well as an upper bound about how far ahead a single participant can grow their chain. Note that all of these statements have to be interpreted as statements "with high probability" relative to security parameters. 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 https://eprint.iacr.org/2016/454.pdf [1] https://arxiv.org/abs/1311.0243 https://arxiv.org/abs/1311.0243 [2] https://eprint.iacr.org/2016/917.pdf https://eprint.iacr.org/2016/917.pdf
lowbloodsugar 9y ago
To be clear, we're talking about Logical Clocks [0], not what humans usually think of as a clock or its purpose. [0] https://en.wikipedia.org/wiki/Logical_clock

232 points by gtrubetskoy 9y ago

Can someone who knows the technical details of bitcoin answer the following questions? Suppose initially A owns 1BTC and B owns 0BTC. Suppose A publishes a signed transaction that would give 1BTC to B, and simultaneously B publishes a signed transaction that would give 1BTC to C. If a miner includes both transactions in a block, is the block valid? Does it depend on the order of the transactions within the block (A's transfer to B preceding B's transfer to C)?

sly010 9y ago
The block is valid only if the transactions are in the correct order, but the miner is incentivized to figure out the right order (specifically incentivized to include as many transactions as possible). 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.
SilasX 9y ago
The protocol says to only accept valid blocks. 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.
Terr_ 9y ago
A side topic you might find interesting, "Miners are not your friends" [0] which focuses on ways that miners have a mechanism and incentive to subtly exploit some badly-made interactions. [0] https://blog.keep.network/miners-arent-your-friends-cde9b6e0e9ac https://blog.keep.network/miners-arent-your-friends-cde9b6e0...
nordsieck 9y ago
No. In bitcoin, you don't spend from an account. You spend "unspent transaction output" or UTXO. There is no unspent transaction that B owns, so any transaction B creates to send money to C is invalid.
- tylersmith 9y ago
  They can't actually do it simultaneously but after A sends to B, B can create a transaction spending that output to C and both transactions can occur in the same block.
gtrubetskoy 9y ago
Yes (as sly010 pointed out), here is an example: https://blockchain.info/tx/cffa18e3d519c31c8624fc2c3e498c0d9bfc64d009b23c3b076a50faa0048240 https://blockchain.info/tx/cffa18e3d519c31c8624fc2c3e498c0d9... https://blockchain.info/tx/f24eaa493071e96f5bdf931204b8930989f1563505ac28f7237d74bab7ee143f https://blockchain.info/tx/f24eaa493071e96f5bdf931204b893098... Both transactions are in the same block (203732), the f24eaa tx is spending an output of cffa18.
- joeblau 9y ago
  None of the addresses in your examples are the same.
  - gtrubetskoy 9y ago
    >None of the addresses in your examples are the same. Check again: the first TX pays to 12Pws7qasVjt7uKfT6woQptx1MLNj2mo44, the second spends from it.
deleted 9y ago
[deleted]
deleted 9y ago
[deleted]
drdrey 9y ago
B would need to refer to a transaction output that has at least 1 BTC to be able to sign a transaction sending 1 BTC to B. Until A's transaction is included in a block, B can not do that.
- rpearl 9y ago
  > Until A's transaction is included in a block, B can not do that. 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)
  - drdrey 9y ago
    But is it valid to refer to a transaction hash that only exists in the mempool? The transaction you refer to has to exist in history, which means it has to live on the longest chain, no?
rocqua 9y ago
Yes, and this actually has a use. 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.
- discussedbefore 9y ago
  > increase the fee of a transaction after the fact 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 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.
  - rocqua 9y ago
    > maybe this is what "Child-Pays-For-Parent" is 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.
xilis 9y ago
I believe the exact scenario you propose is not possible. It cannot happen simultaneously (so A broadcasting his tx - txA and B broadcasting his tx - txB at the same time). 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).

lainga 9y ago

On the last section, is a better name for it "Proof-of-Time" or "Proof-of-Tick" (not that we can likely change the popular name, the cat's out of the bag)?

gtrubetskoy 9y ago
I like Proof-of-Tick :)

throwawaysecops 9y ago

> Nothing Happens Between Blocks 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.

ptest1 9y ago

But it isn’t a clock because it doesn’t tell us how much time has passed. PoW allows for the creation of an ordering. I’m not sure these metaphors are helpful.

Terr_ 9y ago
> But it isn’t a clock because it doesn’t tell us how much time has passed. Not necessarily: https://en.wikipedia.org/wiki/Logical_clock https://en.wikipedia.org/wiki/Logical_clock
ghayes 9y ago
I believe the reference is to a vector clock [0] [0] https://en.wikipedia.org/wiki/Vector_clock https://en.wikipedia.org/wiki/Vector_clock
- ptest1 9y ago
  That makes a lot more sense, thanks.
tylersmith 9y ago
It tells you the time in number of blocks. Block height is the unix timestamp of blockchain-based timestamp servers.

panic 9y ago

Wouldn't a proof-of-time scheme have a bootstrapping problem? You need some way to unforgeably (and fairly) generate your Bitcoins before anyone will care to trade them with you.

rocqua 9y ago

> The Bitcoin Difficulty adjusts dynamically so that a proper hash is found on average once every ten minutes. 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.

johnmaguire2013 9y ago
If you choose a time in the future, other nodes could reject you. 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.
- tromp 9y ago
  There is no requirement that timestamps be nondecreasing. A block at 10:00 can be followed by one at 9:59. What is required however it that a timestamp be at least the median of the last 11 blocks.

andrew1000 9y ago

The article references "orphans" in blockchain, what becomes of those orphans? My understanding is that nodes compete to solve the hash - then the "winning" node has its transactions from the preceding 10 minutes added to the blockchain. What about all the other (thousands?) of nodes that didn't win - their transactions must not vanish into the ether, but what becomes of them? They must get added to the blockchain at some point otherwise something like bitcoin would collapse on itself, but i've never been able to wrap my head around how that happens.

deleted 9y ago
[deleted]
oillio 9y ago
All the nodes have all the transactions (roughly). When you say the winning node puts "its" transactions in the block, that is really the transactions that it is currently aware of, and that fit in the block. All the losing nodes have the same transactions as well. 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
- icebraining 9y ago
  Well, most of the transactions will be the same, but they can have some transactions the other doesn't, depending on what transactions they received and then chose from their own mempool. It's just that those transactions who got inserted into the "losing" block - but not in the "winning" one - will be kept around to be added in a new block in the future.
rocqua 9y ago
Those orphans are treated like someone trying to 'fork' the blockchain by working on an older block, and trying to get a longer chain. 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.

nikisweeting 9y ago

Looks like this article describes a system that's very similar to http://solana.io http://solana.io

aey 9y ago

We are building a ledger based on Verifiable Delay Functions. It's like a high resolution decentralized clock. https://github.com/solana-labs/solana https://github.com/solana-labs/solana

rocqua 9y ago

I think some of this is kind of wrong. 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.

icebraining 9y ago
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'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.
- rocqua 9y ago
  Yeah, but it is quite interesting what the relevant target times are. 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.

bitxbitxbitcoin 9y ago

Well put, sir!

mad44 9y ago

https://muratbuffalo.blogspot.com/2018/03/anatomical-similarities-and-differences.html https://muratbuffalo.blogspot.com/2018/03/anatomical-similar... 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.

gtrubetskoy 9y ago
> Proof of work is the leader election phase of consensus. 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 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."
- mad44 9y ago
  Leaders don't decide. They propose values (such as a block of transactions). There may be multiple leaders with different proposals and participants get to a consensus about which proposal gets accepted for a given slot. 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.
- relyio 9y ago
  > 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). Who picks the transactions from the mempool that will be serialized into history?

danbruc 9y ago

This analysis is obviously wrong, if the important thing was establishing a global clock, you could just use GPS receivers. Ordering transactions works also without proof of work, just including a hash of an existing transaction or block in a new transaction or block and this proofs the order of those transactions or blocks relative to each other. No clock required at all. And also exactly what Bitcoin does but which is totally unrelated to the proof of work. 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.

pdpi 9y ago
> This analysis is obviously wrong, if the important thing was establishing a global clock, you could just use GPS receivers 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.

IncRnd 9y ago

> The Bitcoin blockchain Proof-of-Work is simply a distributed, decentralized clock. 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.

xmly 9y ago

Decentralized TimeStamp Server... This is clearly wrote in the bitcoin white paper. Why is this becoming a news?

ajkjk 9y ago
It's just a blog post; not necessarily 'news'.

hudon 9y ago

> There is a separate consensus in a rare but common case of two consecutive ticks being associated with conflicting blocks. The conflict is resolved by what block will be associated with the next tick, rendering one of the disputed blocks “orphan”. How the chain will continue is a matter of chance 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.

sethgecko 9y ago
Fascinating, I found this article by Vitalik that explains what happened. In v0.8 they swapped from BerkleyDB to LevelDB but due to a bug the two chains started diverting. https://bitcoinmagazine.com/articles/bitcoin-network-shaken-by-blockchain-fork-1363144448/ https://bitcoinmagazine.com/articles/bitcoin-network-shaken-...
- hudon 9y ago
  Yup, we'll never know if the bug was intentional or not, and that's why the fix being centrally coordinated is scary. Maybe it was a legitimate mistake, but maybe one of the developers planned this and executed large double-spends on the 0.8 branch because he knew 0.7 would be ultimately chosen. The fact that nothing prevents this type of attack is worrisome. 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-bitcoin-fork-centralized-decision-making-saved-the-day/ https://freedom-to-tinker.com/2015/07/28/analyzing-the-2013-...

tchitra 9y ago

While the analysis contained in this article is rather arbitrary, blustery and imprecise, there is a mechanism by which blockchains can serve as 'partially synchronized clocks.' One interesting facet about Bitcoin is that the model under which you analyze the effect of network delays can give you different results about how unsynchronized local copies of the blockchain can become. In the paper, "Analysis of Blockchains in Asynchronous Networks" [0], a certain (and more realistic) model is used in which adversarial miners are allowed to delay forwarding of blocks that they receive. The goal of this model is to describe how networking can account for changes to the probability of selfish mining [1]. The authors of [0] prove that for Bitcoin, under some assumptions about the maximum delay an adversary can use and the block production rate, is consistent because it has both a lower bound on how much chains between different participants can differ as well as an upper bound about how far ahead a single participant can grow their chain. Note that all of these statements have to be interpreted as statements "with high probability" relative to security parameters. 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 https://eprint.iacr.org/2016/454.pdf [1] https://arxiv.org/abs/1311.0243 https://arxiv.org/abs/1311.0243 [2] https://eprint.iacr.org/2016/917.pdf https://eprint.iacr.org/2016/917.pdf

lowbloodsugar 9y ago

To be clear, we're talking about Logical Clocks [0], not what humans usually think of as a clock or its purpose. [0] https://en.wikipedia.org/wiki/Logical_clock