Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Proof-Of-Work is a Decentralized Clock

grisha.org

Post reply on HN
Print view View original

121–130 of 130 posts

Re: Proof-Of-Work is a Decentralized Clock

#121

Post by gtrubetskoy »

danbruc wrote: post #120
gtrubetskoy wrote: post #118

Earlier quoted context omitted.

OK, at the time the solution was found, and the miner went "hooray I solved a block!". That's exactly when the the blockchain clock ticked and on that tick the block was mined. 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 ex…

Okay, now I understand what we are talking about but I still don't find it remarkable in any way. I can come up with an endless number of similar processes. For example the FTP clock. I have a public FTP server and at some point in time I create a directory named 1. Then I open that directory and create a subdirectory named 2. Then 3 another level deeper. And 4. And... I don't see what is special about such a process…

> What is the point in time you mined block 12345 exactly?

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 :)

Re: Proof-Of-Work is a Decentralized Clock

#123

Post by db48x »

mac01021 wrote: post #115
db48x wrote: post #54

Earlier quoted context omitted.

In Neptune's Brood there were "slow" currencies where transactions had to be settled by communication with other star systems. It was created as a deliberate way to drive colonization of new star systems, since the only way to create more of it was to colonize more systems. The founders of a colony could end up quite wealthy, if they survived the attempt. Of course, for every-day transactions there were also "fast" c…

Since I won't have time to read this book for at least several months - what are those colonists able to spend their newfound wealth on? Goods that will have to travel from lightyears away?

There is some physical trade between systems in the book (it's cheaper once you know you won't have to build a civilization on the other end), but there's no real enumeration of the possibilities in the book.

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.

Re: Proof-Of-Work is a Decentralized Clock

#124

Post by IncRnd »

danbruc wrote: post #84
IncRnd wrote: post #81

Earlier quoted context omitted.

That makes no sense, or the meaning is at least not obvious. What does it mean to make creation of information one-way? 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.

I know what a one-way function is but what does making the creation of information one-way mean? What information are we creating and what is this one-way that we can not go back? Do you mean to ensure that the information can not be destroyed after it was created? Or do you mean to order things temporally? And how does proof of work do that?

I just answered your question. I even quoted your question first, so you could readily see.

> 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.

Re: Proof-Of-Work is a Decentralized Clock

#125

Post by rocqua »

ema wrote: post #105
rocqua wrote: post #44

Earlier quoted context omitted.

Hi, I hope my tone wasn't too grating. 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 th…

If there is no double spend between the later arriving block from mars and the block earth already mined the next block could acknowledge both. Basically making the blockchain a blocklatice. If I haven't missed anything the only reason it wasn't done like this from the beginning is that when the orphan rate is low it' not worth the additional code complexity.

Interesting! A block lattice seems like a nice thing.

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?

Re: Proof-Of-Work is a Decentralized Clock

#126

Post by rocqua »

gtrubetskoy wrote: post #72
rocqua wrote: post #30

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…

>> 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. You may be right about my use of "memoryless", though it won't matter at any hashrate :) "...brute-force attacks against 256-bit keys w…

I totally agree, in practice sha-256 is just memoryless.

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.

Re: Proof-Of-Work is a Decentralized Clock

#127

Post by rocqua »

discussedbefore wrote: post #48
rocqua wrote: post #22

Earlier quoted context omitted.

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 un…

> 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 >> Since this created a series of unconfirmed transactions, we had to do something drastic: use Child-Pays-For-Parent with a very significant fee…

> 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.

Re: Proof-Of-Work is a Decentralized Clock

#128

Post by drdrey »

rpearl wrote: post #45
drdrey wrote: post #21

Earlier quoted context omitted.

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.

> 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 burn…

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?

Re: Proof-Of-Work is a Decentralized Clock

#129

Post by danbruc »

zodiac wrote: post #116
danbruc wrote: post #112

Earlier quoted context omitted.

I think you have to be more precise when making claims of this sort; in this case "establishing a global clock" is not very precisely defined. 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 som…

Yes, a user can sign multiple blobs. One construction is this: we agree on some genesis state (no block rewards are issued in this protocol). Call a transaction pre-valid if the transaction is signed by the oracle. A transaction is valid iff it is pre-valid, it is a valid state transaction (valid signature, enough balance etc) and if the originating account made no other pre-valid transactions during the same hour. T…

I see. Actually you can get rid of the one hour interval and the signing. And you can also implement everything or at least many things on top of it. The oracle just records all incoming requests in order. Then, if you want to know the current state of the system, you just request all the requests ever made and apply them in order starting from some initial state. And of course ignoring all invalid requests.

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.

Re: Proof-Of-Work is a Decentralized Clock

#130

Post by mrb »

rocqua wrote: post #114
mrb wrote: post #91

Earlier quoted context omitted.

« for sha-256 using brute force, this probability is totally 0 » 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.

But sha-256 is actually memory-full. Or rather, lets model sha-256 as a random oracle. 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…

«lets assume there is an input that leads sha-256 »

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.

Post reply on HN