Also, there's nothing keeping me from running thousands of nodes. Or generating my own blockchain that purports to be longer than yours.
I agree. Too bad.
Topic: conjecture about proof-of-work and cryptocurrencies (Read 8271 times)
I agree. Too bad.
Also, there's nothing keeping me from running thousands of nodes. Or generating my own blockchain that purports to be longer than yours.
Good luck with that.
Also, there's nothing keeping me from running thousands of nodes. Or generating my own blockchain that purports to be longer than yours.
As you know many people don't like the idea of using CPU power in order to make so-called "useless" computations.
I suspect it is possible to rigorously prove that any cryptocurrencies, providing it fulfills a few conditions, has to be based on proof-of-work, and thus on CPU.
So far I can't prove it seriously, so it is just a conjecture. I'd be glad if someone with a solid maths and IT background could bring a demonstration.
So it would look like:
Obviously this relies on a theoretical, more general definition of "cryptocurrency". I won't give such a definition here but I guess you get the idea.
I suspect it is possible to rigorously prove that any cryptocurrencies, providing it fulfills a few conditions, has to be based on proof-of-work, and thus on CPU.
So far I can't prove it seriously, so it is just a conjecture. I'd be glad if someone with a solid maths and IT background could bring a demonstration.
So it would look like:
Quote from: grondilu
If a cryptocurrency respects the folowing criteria:
* it doesn't discriminate any node of the network ;
* the initial monetary amount available in the network is zero (apart from the genesis block) ;
Then at any time, the probability of generation of a new monetary unit for any node is proportionnal to the CPU of this node.
* it doesn't discriminate any node of the network ;
* the initial monetary amount available in the network is zero (apart from the genesis block) ;
Then at any time, the probability of generation of a new monetary unit for any node is proportionnal to the CPU of this node.
Obviously this relies on a theoretical, more general definition of "cryptocurrency". I won't give such a definition here but I guess you get the idea.
Every node that wishes to mine proposes a new block-candidate (chained into previous blocks but with no difficulty so that you're not burning CPU power). Say n nodes participate.
They run a protocol to choose a definitive block-candidate. This is not competitive since no one is declared the winner yet. Simple majority vote for a well formed block-candidate is sufficient. All n participants share a hash of the blessed block-candidate.
Then the step I don't know how to do
: Run a cooperative cryptographic protocol that that simulates a fair dice toss, somehow involves the hash of the blessed block-candidate, and ends up randomly selecting 1 of n. This is the next BLOCK and the selected number indicated the owner of the reward for mining the BLOCK.Rinse and repeat every 10 minutes.
------------------
Now I don't have such a protocol but here's an example of n nodes randomly selecting one of their numbers.
Each secretly chooses a number between 0 and n-1. Each hashes that with a public key he wishes to use to receive the reward. This is his commitment. When he reveals his chosen number later anyone can check that he didn't cheat and change the number.
After all are committed, all reveal their chosen number and check the others for honesty. The sum of the honest revealed numbers modulo the number of honest participants is a random number. Call it the selector.
Sort all the honest keys that were revealed. The selector tells us which key in the sorted list gets the reward.
n nodes cooperated and a new block is generated and one of the nodes randomly received the reward. Low CPU nodes have an equal chance. They just have to have enough power to keep up with the protocol.
-------------------
Useless of course, now that I review this. A newly started node would not know who to trust if the block chain had split recently. Oh well.
(I have to read-read what the protocol does for competing block-chains).
Largest proof-of-work wins. In case of ties, miners start working on the first one they saw.
A block with a higher difficulty is considered "larger" for this purpose, so creating your own chain from block 1 at difficulty 1 won't work.
The job of the time-stamping server would be to assign order to transactions that is final and immutable. Instead of the current block-chain there will be a chain of transactions signed by the time-stamping server. A copy of the chain of transactions will be stored on every node. If the time-stamping server attempts to double-spend, then it will have to modify the immutable chain of transactions, and that attempt will be rejected by the network of nodes, since each node will be able to see that the server is trying to assign a different order number to a transaction it has previously signed. Once that happens, the community has to choose a new time-stamping server that is trustworthy. Since the job of the time-stamping server is easy, it would be trivial to set one up.
Anything based on the Network Time Protocol or astronomical observation won't work. What is the recourse if the "time" server says you didn't make any transactions? Elect a new server? The beauty of the the Bitcoin protocol is that a new server is chosen by lottery every time a new block chain is made. The "time stamp" is a time stamp in terms of entropy and proof of work. To falsify a past transaction takes an increasing amount of resources as time goes on. To falsify the newest block chain you have to prove your version is "better" (I have to read-read what the protocol does for competing block-chains).
Keep in mind that transactions don't have to be synchronous. For smaller transactions, people may be trusted not to double-spend even in the absence of a constant network connection.
... anyway they put these lab rat students into a confined room for several weeks and started twiddling temperature and light on-offs and tricked the subjects body's into a 48 hour sleep-wake cycle ... they would be awake for 24 hours and sleep for 24 hours ....
Another way to get a similar result is to have the lab rat student spend some time on this forum
I'm not sure if this applies, but in nature, timestamping is distributed. That's how your heart works, for instance -- no one cell sets the pulse. Crickets do the same thing.
Nice observation, circadian rhythms, beat frequencies for clocks.
Thanks! I started reading Strogatz's book again. I wouldn't be surprised if his work on this stuff could be used in a really cool way:
http://epubs.siam.org/siap/resource/1/smjmap/v50/i6/p1645_s1?isAuthorized=no
Quote
The main result is that for almost all initial conditions, the population evolves to a state in which all the oscillators are firing synchronously. The relationship between the model and real communities of biological oscillators is discussed; examples include populations of synchronously flashing fireflies, crickets that chirp in unison, electrically synchronous pacemaker cells, and groups of women whose menstrual cycles become mutually synchronized.
Yeah, I think one of the craziest demonstrations from this was the experiments where the sleep-wake cycle was identified to result from two harmonic oscillators (24.XX hour core body temperature oscillation and another 24.XX oscillator that I can't remember ... melatonin level due to light exposure?) ... anyway they put these lab rat students into a confined room for several weeks and started twiddling temperature and light on-offs and tricked the subjects body's into a 48 hour sleep-wake cycle ... they would be awake for 24 hours and sleep for 24 hours ....
I'm not sure if this applies, but in nature, timestamping is distributed. That's how your heart works, for instance -- no one cell sets the pulse. Crickets do the same thing.
Nice observation, circadian rhythms, beat frequencies for clocks.
Thanks! I started reading Strogatz's book again. I wouldn't be surprised if his work on this stuff could be used in a really cool way:
http://epubs.siam.org/siap/resource/1/smjmap/v50/i6/p1645_s1?isAuthorized=no
Quote
The main result is that for almost all initial conditions, the population evolves to a state in which all the oscillators are firing synchronously. The relationship between the model and real communities of biological oscillators is discussed; examples include populations of synchronously flashing fireflies, crickets that chirp in unison, electrically synchronous pacemaker cells, and groups of women whose menstrual cycles become mutually synchronized.
I'm not sure if this applies, but in nature, timestamping is distributed. That's how your heart works, for instance -- no one cell sets the pulse. Crickets do the same thing.
Nice observation, circadian rhythms, beat frequencies for clocks.
That's how your heart works, for instance -- no one cell sets the pulse. Crickets do the same thing.
Hum... sounds interesting. Any source/documentation about that?
grondilu, I remember reading all about that stuff in this book:
http://www.amazon.com/Sync-Order-Emerges-Universe-Nature/dp/0786887214/ref=sr_1_1?ie=UTF8&qid=1306525959&sr=8-1
Well, I don't know. Maybe it's possible. But it is surely trickier than what you seem to think. For instance, say indeed some node sees an inconsistent entry in the table. It has to tell every one. They all have to check the accusation is true and then they all have to decide to ban the bad timestamp server, revoke its previous transactions (how many??), chose a new one and so on. An ugly mess for sure.
You are right it's messy. But the only messy part is how to choose a new time-stamp server. Revoking transactions will be easy. Only transactions that were placed after the invalid transaction will be revoked - but they should never have been placed in the chain by honest nodes anyway. Once a new time-stamp server is chosen - valid transaction will be placed back into the chain by that server. Even the originally invalid transaction may be placed into the chain eventually if the balance of the account to which it refers becomes sufficiently large.
No. A double-spending would not work this way. The timestamp server would sign two transactions but will just wait a bit to publish the oldest one. It will do as if there had been some network latency. There is no way the other nodes can prove it was not honest.
I think I didn't make myself clear. The chain of transactions must always be in a consistent state, i.e. no address can have a negative balance. Every node can verify the chain is in a consistent state. If the time-stamping server signs a transaction that puts the chain in an inconsistent state, then the server is rejected by the network. So a double-spend isn't really possible without invalidating the chain a copy of which is stored on every node.
Well, I don't know. Maybe it's possible. But it is surely trickier than what you seem to think. For instance, say indeed some node sees an inconsistent entry in the table. It has to tell every one. They all have to check the accusation is true and then they all have to decide to ban the bad timestamp server, revoke its previous transactions (how many??), chose a new one and so on. An ugly mess for sure.
That's how your heart works, for instance -- no one cell sets the pulse. Crickets do the same thing.
Hum... sounds interesting. Any source/documentation about that?
No. A double-spending would not work this way. The timestamp server would sign two transactions but will just wait a bit to publish the oldest one. It will do as if there had been some network latency. There is no way the other nodes can prove it was not honest.
I think I didn't make myself clear. The chain of transactions must always be in a consistent state, i.e. no address can have a negative balance. Every node can verify the chain is in a consistent state. If the time-stamping server signs a transaction that puts the chain in an inconsistent state, then the server is rejected by the network. So a double-spend isn't really possible without invalidating the chain a copy of which is stored on every node.
Quote
setting one up is easy, sure. But the tricky part is to chose one and to convince everyone to use the same.
Sure, that's a valid criticism. Maybe one could build a hierarchical structure where one could easily reach a consensus of a new time-stamping server across the network once the old one behaves badly.
I'm not sure if this applies, but in nature, timestamping is distributed. That's how your heart works, for instance -- no one cell sets the pulse. Crickets do the same thing.
A copy of the chain of transactions will be stored on every node. If the time-stamping server attempts to double-spend, then it will have to modify the immutable chain of transactions, and that attempt will be rejected by the network of nodes, since each node will be able to see that the server is trying to assign a different order number to a transaction it has previously signed.
No. A double-spending would not work this way. The timestamp server would sign two transactions but will just wait a bit to publish the oldest one. It will do as if there had been some network latency. There is no way the other nodes can prove it was not honnest.
Since the job of the time-stamping server is easy, it would be trivial to set one up.
setting one up is easy, sure. But the tricky part is to chose one and to convince everyone to use the same.
Quote
And the solution again would be to chose a new server if the current one starts behaving badly.
Bitcoin choses a new server every ten minutes or so, without having to wait for it to behave badly. This is much better.
It's not a totally bad idea. Whom would new money be given to, though?
The system could be bootstrapped from Bitcoin by assigning balances to each address in accordance with the current wealth distribution of Bitcoin users. The new system will use the same private/public key architecture as Bitcoin, and since users control their private keys, they will be able to spend their coins on both systems. The first (genesis) transaction in the new system will be one that assigns to all current Bitcoin public addresses in existence their respective Bitcoin balance.Quote
Also, even if the time-stamping server could not steal money or create new one, it would still have the power to double spend. So it would be difficult to obtain a consensus about who is trustworthy enough to get this power.
The job of the time-stamping server would be to assign order to transactions that is final and immutable. Instead of the current block-chain there will be a chain of transactions signed by the time-stamping server. A copy of the chain of transactions will be stored on every node. If the time-stamping server attempts to double-spend, then it will have to modify the immutable chain of transactions, and that attempt will be rejected by the network of nodes, since each node will be able to see that the server is trying to assign a different order number to a transaction it has previously signed. Once that happens, the community has to choose a new time-stamping server that is trustworthy. Since the job of the time-stamping server is easy, it would be trivial to set one up.Another problem with a central time-stamping server would be that it will have the power to selectively not include transactions into the chain based on their addresses. But the same problem exists in the current bitcoin implementation. And the solution again would be to chose a new server if the current one starts behaving badly.
Besides, a system based on a centralized time-stamping server would not be yet another centralized system. All centralized monetary systems are currently able to inflate their currency, whereas with the centralized time-stamping system the central entity will not be able to create new money. That will be it's only advantage.
It's not a totally bad idea. Whom would new money be given to, though?
Also, even if the time-stamping server could not steal money or create new one, it would still have the power to double spend. So it would be difficult to obtain a consensus about who is trustworthy enough to get this power.
So to speak bitcoin IS a system with centralized time server. But the server changes every ten minutes or so. So somehow, bitcoin is already an extreme version of what you are suggesting.
Alkor, I think you missed the point of Bitcoin. Its biggest advantage is that it is decentralized. Having expensive proof-of-works is simply a side-effect of having a distributed system. No one's interested in yet another centralized system; there are already hundreds of those, many of which have much larger backing and more trust than your idea ever will.
CydeWeys, I haven't missed the point of Bitcoin. Even though it may appear that bitcoin is a decentralized system, in the long term it will converge to the centralized system I described as miners become more specialized and control most of the computational power. With the recent case of one of the mining pools surpassing the 50% hashing power, we are already close to having a centralized proof of work system anyway. So eventually there is little doubt that select few highly-efficient miners will control what transactions get verified and what don't.
Besides, a system based on a centralized time-stamping server would not be yet another centralized system. All centralized monetary systems are currently able to inflate their currency, whereas with the centralized time-stamping system the central entity will not be able to create new money. That will be it's only advantage.
Jump to: