Proof of Work Without All the Work

https://arxiv.org/abs/1708.01285

by federicoponzi • 9 years ago

208 115 9 years ago

arxiv.org

ForHackernews• 9 years ago

Would this make it possible to implement a cryptocurrency that wasn't an ecological disaster?

kronos29296• 9 years ago

probably not.

kristofferR• 9 years ago

Ethereum is planning to switch to Proof of Stake in the coming years: https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ

jacobush2• 9 years ago

Mmmm... good luck

icey• 9 years ago

There are some coins (NEO/AntShares for example) that are opting for DBFT-style governance -- https://themerkle.com/what-is-delegated-byzantine-fault-tole...

tomfitz• 9 years ago

https://en.wikipedia.org/wiki/Stellar_(payment_network) is a decentralized currency that already isn't the "ecological disaster" that Bitcoin is.

vanderZwan4• 9 years ago

I know this place is crawling with cryptocurrency fanboys, but this is a serious issue for many sceptics.

Regardless of whether you think that criticism is valid, downvoting anyone who asks questions about how to address this does not help make their scepticism go away.

jack_pp• 9 years ago

There's ecological disaster regardless of mining, I haven't done any math on the issue but I believe mining waste is a very small part of the overall polution in the world.

We must develop technology to clean our planet regardless of mining waste. Given this and the fact that energy is becoming cleaner by the year I think worrying about mining waste is not rational

vanderZwan4• 9 years ago

I haven't done any math on the issue but I believe

This is not the kind of discussion where assertion by belief has any place, on either side of the discussion.

What we need solid estimates of how this technology currently scales, how it might improve, and how it compares to existing electronic currency, and physical cash (taking into account things like embodied energy of coins).

bmcusick5• 9 years ago

Bitcoin mines are in western China and Oregon precisely for the abundant and cheap hydro power. That's not so bad, ecologically speaking.

Bitcoin is only as ecologically harmful as the source of the electricity used to run the miners, and it's no more harmful than any other use of electricity. If the world switches over to solar and wind as baseload power, problem solved. If the world doesn't switch away from using coal, that's not Bitcoin's fault. It's not a problem Bitcoin can solve.

the8472• 9 years ago

If the world's economies ran on bitcoin we would need a stupendous amount of energy to keep the miners running. That energy not being spent on something else is a huge opportunity cost since many problems could be solved if there were just enough spare energy..

SamBam• 9 years ago

and it's no more harmful than any other use of electricity

That's a tautological statement. My 50,000 watt bulb that I shine inside a closed box is also "no more harmful than any other use of electricity," but the question is whether I should be using that electricity in the first place.

You can argue whether the "wealth" generated is worth carbon dioxide released into the atmosphere, but you can't deny that more carbon dioxide has been released because of BitCoin.

Back to my lightbulb in a box: "If the world switches over to solar and wind my 50,000 watt useless bulb's problem is solved. If the world doesn't switch away from using coal, that's not my fault. It's not a problem I can solve."

mtrycz• 9 years ago

There's more than one Proof of Stake cryptocurrency, and Ethereum does want to go PoS sometime.

PoS have been around for 3 (maybe 4?) years by now.

Proof of Stake is quite genius in the politics of it, and the power needed to run is minimal (you still need to keep your hardware powered on)

GordonS2• 9 years ago

Can you give a short summary of how PoS works?

clarkmoody• 9 years ago

First, please show that cryptocurrency is an ecological "disaster" is the first place.

Next, please explain how crypto is more of a disaster than the existing monetary system. Does the cryptocurrency mining economy pose more of an ecological threat than the system put in place to secure government fiat money: buildings, employees, vaults, mints, printing presses, armored vehicles, police, (some part of) the military, etc?

antocv3• 9 years ago

Byteball is such a cryptocurrency. There is no Proof-of-Work, or Proof-of-Stake.

chj• 9 years ago

“Consequently, if the network is attacked, our scheme guarantees security, with algorithmic costs that are commensurate with the cost of the attacker. Conversely, in the absence of attack, algorithmic costs are small.”

Hope it works.

empath752• 9 years ago

The network will be under attack constantly.

KirinDave• 9 years ago

Blockchain tech has a lot of potential uses outside of currency. In those fields, the likelihood of a constant foreverwar amongst the contributors is way lower.

Also, providing a sliding cost on the network might make the miners agree it's more cost effective to step back from this breakneck energy-use-maximization game they're playing.

falcolas• 9 years ago

Well, in theory, you could simply alter the number of 0's required for any particular proof. Under attack? More 0's required in the hash. Not under attack? No 0's required.

Determining if you're under attack would seem to be the harder part.

ubaltaci• 9 years ago

For those who interested in the topic. Nem uses something called proof of importance https://www.nem.io/NEM_techRef.pdf

tromp• 9 years ago

If new coins are distributed as block rewards, then collectively, miners will spend (nearly) the monetary value of those coins in competition to solve as many blocks as possible. In other words, any gains in marketcap will translate to increased mining efforts. Paul Sztorc has written a lot more about this in http://www.truthcoin.info/blog/pow-cheapest/

qznc2• 9 years ago

If a cryptocurrency becomes too big to fail, then it seems inevitable that nation-states and large corporations will mine it at a loss.

russdpale4• 9 years ago

If it is solar powered, I don't see how it will be mined at a loss? Power is the number one cost, and we have a free unlimited supply of it.

canoebuilder3• 9 years ago

What interest does a government or large corporation have in cryptocurrency?

This is why cryptos as currently implemented will always be fringe and used for the most part illicitly, because as soon they gain a wide enough currency the participants in the system will switch to a more efficient, i.e. centralized system.

If enough people use them that a government or large corp would care, those "enough people" would form a new government or become the customers a new corp, that facilitates their transactions in a more efficient way.

...and a touch ironic that you seem to be pining for TBTF cryptos when Satoshi himself railed against the TBTF system.

runeks4• 9 years ago

Thank you for sharing this.

For a while I’ve had a sense that “useful PoW” simply doesn’t make sense, but I was unable to explain why. This article perfectly explains why it doesn’t make sense, albeit using very econ-specific terms. I think it may be possible to explain it in simpler terms, without needing to introduce marginal revenue and cost, but I’m not sure exactly how just yet.

kanzure• 9 years ago

Here's some "lore" around proof-of-work and why it must burn external resources:

https://download.wpsoftware.net/bitcoin/asic-faq.pdf

https://download.wpsoftware.net/bitcoin/pos.pdf

https://download.wpsoftware.net/bitcoin/alts.pdf

csomar• 9 years ago

So now we have click-baity academic papers? Can someone summarizes to me the genius behind the idea? Because as far as my math goes, it is not theoretically possible.

geofft2• 9 years ago

So now we have click-baity academic papers?

As academic paper titles go this is pretty normal.

Can someone summarizes to me the genius behind the idea?

I'm reading quickly, but I think the idea is that the reason we need proof-of-work is to prevent Sybil attacks, that is, a single entity pretending to be 50% of the network via spoofed identities. So you have a concept of persistent identity for each (apparent) member of the network, and you require nodes to solve a computational problem when they join the network and also periodically while they're in the network. This puts relatively little computational load on each participant, but puts a lot of load on a long-term attacker, and even more work on a short-term attacker who's trying to claim a bunch of identities in a hurry.

I'm not sure how much this actually helps Bitcoin, since my impression is that the computational load is what's needed to match the abilities of the legitimate members of the network. I guess the trick is that maybe you can make the block-mining difficulty scale up less aggressively over time, but I'm not following that logic yet.

geofft2• 9 years ago

Thinking harder I guess the only reason that mining difficulty is so competitive is that there's a reward for mining, given to just the miner, so the arms race is profitable (much as, say, the arms race for microsecond-level tech improvements is profitable to HFT because even if two algorithms make the same decision only one gets the purchase in first).

So if you get rid of that, and maybe add a nominal "reward" for solving the puzzles to remain in the network and give it to all participants, the incentive to build giant mining farms goes away: the only reason to have additional computational power is either to keep up with the network as a whole (not the fastest person in the network) or to actually gain 50% of computational power.

russdpale4• 9 years ago

When I read this: "This shortcoming is highlighted by recent studies showing that PoW is highly inefficient with respect to operating cost and ecological footprint." The moment we try and do away with this inefficiency we are going against the entire solution of what bitcoin was going for: how to use all of the inefficient computer parts laying around the globe for something useful?

It makes me think people just don't get it. High inefficiency is the _ENTIRE_ point! It gives rarity to the coin. That 10 minute block time is the same as compressing millions of years of geology into 600 seconds. It is fundamentally sound mathematics, and ultimately, that is why it holds its value. It is not meaningless mathematics, people who say that don't understand fully as to what they are talking about, imho.

ricardobeat• 9 years ago

how to use all of the inefficient computer parts laying around the globe for something useful?

How do you reconcile this statement with the fact that mining is done by a few thousand entities in the whole world, using custom-built hardware?

wlesieutre• 9 years ago

You're misinterpreting what people mean by "inefficient" in this context.

The bitcoin mining ASICs are extremely efficient at mining bitcoins. You can't mine them with an old GPU and expect to make back more money than you spent on electricity.

But the choice to mine bitcoins at all is (arguably) an inefficient use of resources that could have been used for pretty much anything else. There's no shortage of useful problems to be worked on by supercomputers and the world would be better off if we did that instead of mining cryptocurrencies. But the economic incentives aren't there.

EDIT: Reading your comment again, I think I was a bit quick on the "you're wrong" here. ISo to clarify, I do agree that inefficiency is at the core of the bitcoin mining ecosystem, but it's all about the "we have to spend a bunch of energy that could've done a lot of other things" inefficiency, not an individual "we can use old hardware for this" sort.

Nursie6• 9 years ago

When you look at it from that angle, Bitcoin becomes a very interesting hack on economic incentives (and how they don't always map to useful real-world activity)

nullc2• 9 years ago

I think the title and abstract of this are not very clear.

I gave it a fast skim to figure out what general class of thing it actually is.

This should be compared with "proof of idle" (https://www.cs.virginia.edu/~shelat/14s-pet/2014/02/11/proof...).

It is an online scheme for resisting sybil attacks in a P2P network where nodes have cryptographic identities which works by periodically forcing all users to do proof of work within a limited time window. Peers that don't respond fast enough are banned from the system (have to create a new identity to join, which is computationally expensive).

The idea is that this get some of the benefits of POW for sybil resistance without spending as much energy.

It doesn't, however, produce a large amount of cumulative work building up over a history. So it's not the sort of thing you'd want to use to protect the history of a ledger directly.

SkyMarshal3• 9 years ago

One of the holy grails in cryptocurrency research is figuring out a PoW alternative the provides similar security at reduced energy cost. A few other examples:

1. Bram Cohen's Proof of Space & Time: https://youtu.be/aYG0NxoG7yw; https://cyber.stanford.edu/sites/default/files/bramcohen.pdf

2. DFINITY VRF-based Threshold Relay: https://youtu.be/o8HHM18PedU (https://en.wikipedia.org/wiki/Verifiable_random_function)

3. Algorand: https://people.csail.mit.edu/nickolai/papers/gilad-algorand-...

These are some of the more interesting ones, but plenty of others.

empath752• 9 years ago

So let's say you replace hashing with some algo that just requires a lot of memory. Wouldn't the cost just be sunk into buying a lot of ram and 'wasting' it? Ram isn't free to produce and has its own externalities.

jon_richards• 9 years ago

I wonder if there's some way to do proof of location based on the latency of light.

Edit: It would clearly require some pretty complex network interactions. You can't be able to precompute a proof and send it to another place.

I'm thinking something like every node broadcasting a public key, which every other node then uses to sign an identifier and sends back. From this, you can generate local maps of the network. While nodes could collude to seem close to each other or lie and claim other nodes are far away, there's presumably some density of truth at which you can construct a reliable global map.

thruflo22• 9 years ago

Proof of useful work?

I.e. the problem is that hashing is wasteful. But we have demand for distributed computing.

Could the work that's being evidenced actually be performing useful computations? Perhaps by structuring a distributed computation platform that accepted standard units of compute work. Like perhaps an Erlang reduction.

Shorel3• 9 years ago

Great, so far I had only read about proof of Stake and proof of Activity

EGreg3• 9 years ago

Forget using POW to secure a ledger. It's comically bad because of the wasteful arms race which now makes each transaction take as much energy as a household does in a day(!)

The reason bitcoin is so far ahead is because it was the first. Proof of work to secure the blockchain AND also elect a dictator to mine the next block is cute, but I wish they had decoupled it, as they did for example for bitcoin-ng.

What I am far, far more interested in is proof of work for avoiding sybil attacks, or used COLLABORATIVELY by nodes to secure a history, as done in Ripple for example.

So, back to sybil attacks: proof of work, can we trust it?

What are the best ways to make it expensive for an attacker to create multiple identities, yet cheap for everyone else to make one identity?

One is the cumulative time and activity invested by you and those who invited you.

For example, reputation. Maybe making accounts is cheap but reputation comes from random nodes with reputation upvoting you. But then you can spam all those nodes since they're operated by humans.

It seems we have yet to design a system that's truly impervious to sybil attacks. The best we have is tying things to a human real world transaction, eg buying a smart phone, and hoping that whoever made the smart phone also has a service to sign data (they don't) that wasn't compromised.

Any other ideas? Paying for accounts with bitcoins? That at its root is just back to the proof of work arms race and reputation of bitcoin.

Question: is there some sort of service by the Secure Enclave that can sign a piece of data with an HMAC or something to prove that it was signed on a legitimate, non-jailbroken smart device?

antocv3• 9 years ago

You would be interested in Byteball. See https://byteball.org/

Secure distributed ledger, without PoW, without PoS.

The bad side? Not 100% trust-less like blockchains, instead (number chosen by no real reason) only has to trust that majority of 12 witnesses does not collude. The witnesses should have real world identities.

Basically transforming what bitcoin has become, with few mining pools/operators deciding its fate and whom users anyway have to trust - into witnesses which can be replaced.

chairmanwow• 9 years ago

There is something thoroughly logical about this approach to the unfortunate waste implicit in Proof of Work (PoW) schemes.

In summary of the motivations of the paper: PoW is currently limited to cryptocurrencies as a security system because of the implicit financial incentive in mining coins. This approach could allow PoW schemes to be widely adopted to secure systems as the overhead is lowered dramatically. Additionally, battery powered devices (ie phones) could make use of PoW without incurring large battery drains. This last bit is particularly interesting and could allow some interesting, distributed P2P systems on cellphones to arise.

The general principle of the paper revolves around asking network members to prove computational power only as much as necessary as the network scales. Because an attacker could easily spoof their MAC / IP address when joining the network, computational tests are periodically distributed to network members. If the test is unsolved in an allotted time period, their network membership is revoked (and the node is blacklisted). The attack referred to in the paper is an attacker adding bad (fake or otherwise) nodes to a system rapidly.

alistproducer2• 9 years ago

I'm in the process of auditing new low-power Po* algos for a crypto system I'm researching. This paper needs a way better abstract. The math is incomprehensible without knowing what it's end goal is. The paper uses acronyms (ex "Good ID") before explaining what they are. Overall a poorly written paper. The work maybe revolutionary, but what good is that if it's so difficult to understand. People forget that the purpose of a paper is to communicate your idea to other people. If it doesn't do that effectively then no matter how awesome the work is, you've failed.

Proof of Work Without All the Work

Related Stories