Hacker News Reader

Comment by nullc | Hacker News Reader

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.

View on HN

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.

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.

That would not be a recurring cost unlike electricity.

To be precise, the point of PoW is not having a recurring cost, but just organizing a "decentralized lottery" where it is very unlikely that you get to verify your own (fake) transactions.

As someone commented above, there are studies on "proof of idle", but other systems have bigger drawbacks than PoW.

I'm not sure what you mean by fake transactions, but transactions are verified with public key cryptography, and a block with invalid transactions will be rejected out of hand by blockchain nodes.

There are two* major classes of attack which someone could do with the power to mint blocks at will (i.e. a 51% attack):

    - discriminatory filtering, where valid transactions are 
      never validated
    - double spends, where a transaction appears like it's 
      been validated for a time but is then rolled back and 
      becomes invalid

But no one can mint transactions without private keys.

* They can also monopolize the rewards of mining, but that's not nearly as bad as the other issues.

Burstcoin has a design like this, except for hard drive space instead of RAM.

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.

How could it not be gamed by introducing artificial latency?

High frequency trading?

You can always introduce more latency artificially. So the only thing you could prove is a "no farther than" property, because you can't be farther than the speed of light, but you could be arbitrarily closer.

I was thinking of an activity called "mapping the stars". Essentially users with telescopes all around the world map as much stars coordinates as they can, and create a block with such info. Next blocks does the same and so on.

Users verify the validity of the chain by making sure those stars exist at those coordinates.

It's hard for any single entity to create a copy of this chain as they would have to map all the stars themselves.

Of course the whole endeavor ends when all the stars have been mapped - but maybe there are so many that this can be viable, and more importantly, cheaper than energy consumption.

EDIT: another idea would be using supernovas, which may actually be infinite since they're constantly exploding. Similar to mapping the stars, users signal the coordinates of the found supernova. Users validate the block based on whether or not it's a supernova - I think there are specific traits which remain in the sky for a long period of time that proves whether there was a supernova there.

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.

My maths isn't good enough for this yet, but I did wonder why there wasn't a popular SETIcoin

Hashing needs to be asymmetric-- expensive to produce a hash that fits the criteria but very cheap to validate that the hash fits the criteria.

This is why attempts to make scientific computation into a proof of work have been difficult-- often the validation cost is equal to the work itself.

eg: BOINC, https://boinc.berkeley.edu/

Hashing is wasteful, but its redeeming quality is that it takes negligible work to validate, despite taking significant work to find values whose hashes have certain characteristics. Just hash the value produced by the worker node and make sure it conforms to the parameters. Should take microseconds.

With proof of useful work, it's probably significantly harder to find similar problem domains where the validation is fast but the useful work is laborious.

Maybe I'm wrong but wasn't a property of NP-hard problems that you can verify them in P time but find a solution only in >P time? (As far as we know)

NP can only verify positive solutions in P time.

Useful cryptographic problems are usually in the intersection of NP and co-NP.

Current best guess is that NP and co-NP are different.

Thus NP complete problems can't be in co-NP, and thus are probably not cryptographically useful. There's a way to make this argument a bit less vague, but it basically explains why cryptographers have stopped looking at NP complete problems.

There was a cryptosystem based on solving knapsack problems. But they had to patch problems until people stopped paying attention.

Well,

Think of the traveling salesman problem for example.

The only way to verify someone's answer is to do all of it yourself too.

You can do it by checking that the solution provided is a valid traversal of the graph, and does not touch two vertices twice. If there are N vertices, you can check in O(N) time.

It's about validating the proposed solution on being the fastest path, not if the proposed solution is a valid path.

I would dispute the assertion that hashing is wasteful. That implies it's inefficient or you're not getting something of equal value in return for what you're paying. But in PoW you spend energy and get in return the security of a global public accounting ledger, which has considerable potential social value, easily comparable to the cost of it. It should not even be surprising that such a thing has great cost, given that economics is certain of only two things - incentives matter and there's no free lunch. There's no free lunch in blockchain. (well, maybe there is, but it would take a considerable CS breakthrough).

And if you're concerned about the environment, don't worry, most of Bitcoin is secured by hydropower right now anyway, and in the foreseeable future will probably migrate to solar power (https://finance.yahoo.com/news/why-california-giving-away-el...).

I agree, but I want to break it down a little more:

Effort ->

You do a lot of hashing to try and win the 10 minute lottery by finding the magic hash that lets you make the next block.

Rewards ->

You win a block reward (or portion of one if you're pooling work with others) that has economic value.

You win transaction fees for the transaction included in the winning block.

Profitability ->

If you are generating enough hash power per your operational expenses, these rewards are profitable, even though you don't win every block.

Some may mine unprofitably because they are speculating on the future value of those rewards rather than the immediate value.

Side Effects ->

This scheme increases the security of the global ledger. Making it more viable and bolstering the value of the rewards you're getting above.

If the overall system is valuable to society, that also bolsters the value of the rewards, but also has a value to society approximately equivalent to the value of the system.

Thus, bitcoin, which does consume energy, is currently, in my opinion providing a better monetary solution at lower cost than the system it is disrupting (banks use power, employ people, etc. etc.)

The perception that it is wasteful could only come, to my mind, if one thought bitcoin was not providing value to society, or that bitcoins were going to zero in economic value.

It may have a lot of potential, but currently cryptocurrencies have at most as much social value as traditional currencies - which cost considerably less energy. (That's assuming they are actually used as currecies and not just as a hype and speculation vehicle)

As for energy consumption, I see no fundamental reason why mining has to stay green. If the valuation should climb high enough that renting a nuclear plant becomes profitable then someone will probably do that.

Even with hydro, the mining spends energy that could have been used for other things.

Finally, what I find most worrysome is the combination of PoW and self-adjusting difficulty. The practical effect seems to be that not just is constant energy required to maintain the system but that energy demand is also steadily growing.

which has considerable potential social value, easily comparable to the cost of it.

The value is 'potential,' the cost is real.

What evidence or milestones are there to indicate this considerable potential social value panning out is increasingly more or less likely? What exactly is the social value that the average HNer could perceive firsthand, rather than some mythical "unbanked" or whatever?

How long has bitcoin been around, a decade? Has anyone putting it to use in a sustainable, self-perpetuating use case that isn't a dark market or ransomware?

It's been around less than a decade and jury is still out whether it will even succeed or not yet, hence why I wrote "potential". But assuming it does prove sound and reliable over the long term, then its best value is as a hedge against governments screwing up their currency, like Venezuela and other distressed economies. There are already US dollar black markets in those places, and new cryptocurrency black markets are starting to form now too.

As for "unbanked", I don't even know why you mention it unless you're setting up a strawman to knock down. But here, let me do that for you - people who are unbanked don't have access to financial services b/c they don't have money, b/c they live somewhere that economic norms, institutions, and growth all have problems that make it hard to create wealth. Solve those problems and the banks and finserve folks will come running and those people won't be unbanked anymore. But I have yet to see a good case for how cryptocurrency in its current incarnation will solve those problems.

Currently it's difficult to verify useful work, especially when there's incentive to spam the system with useless work disguised as useful work.

https://www.cs.umd.edu/~elaine/docs/permacoin.pdf

>Bitcoin is widely regarded as the first broadly successful ecash system. An oft-cited concern, though, is that mining Bitcoins wastes computational resources. Indeed, Bitcoin’s underlying mining mechanism, which we call a scratch-off puzzle (SOP), involves continuously attempting to solve computational puzzles that have no intrinsic utility. We propose a modification to Bitcoin that repurposes its mining resources to achieve a more broadly useful goal: distributed storage of archival data. We call our new scheme Permacoin. Unlike Bitcoin and its proposed alternatives, Permacoin requires clients to invest not just computational resources, but also storage. Our scheme involves an alternative scratch-off puzzle for Bitcoin based on Proofs-ofRetrievability (PORs). Successfully minting money with this SOP requires local, random access to a copy of a file. Given the competition among mining clients in Bitcoin, this modi- fied SOP gives rise to highly decentralized file storage, thus reducing the overall waste of Bitcoin. Using a model of rational economic agents we show that our modified SOP preserves the essential properties of the original Bitcoin puzzle. We also provide parameterizations and calculations based on realistic hardware constraints to demonstrate the practicality of Permacoin as a whole.

Would this (posted earlier today on HN) be a possible candidate? https://news.ycombinator.com/item?id=14947768

> Proof of useful work?

In the Bitcoin industrial space most of us are of the belief that only the marginal value of the work matters for security.

For example, if you can combine mining the Bitcoin chain and calculating ads for google, and the Bitcoin mining pays $1 and the ad crunching pays $5, then this process is really only providing $1 in security. The reason for this is that the for the security of the chain we care about your lost opportunity to mine one chain vs another, which keeps you working to say on the eventual winning chain so that you get paid that $1.

It's also inaccurate to describe mining as not useful. It makes Bitcoin secure. This is very useful, at least to those of us who use Bitcoin!

From a practical perspective the general constraints on what makes a proof of work good for a system like Bitcoin (e.g. that it must be largely optimization and approximation free and that you can randomly generate instances all with roughly equal hardness and that it be cheap to verify) broadly exclude most classes of work you'd likely call otherwise useful.

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

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?

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.

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

This is a poor analogy because colluding Bitcoin miners can never steal funds; they just stamp a chain with proof of work, while the Bitcoin P2P network verifies the stamped blocks, and rejects them if they’re invalid. In the case of Byteball, colluding witnesses can steal funds, which becomes increasingly problematic as the value of the currency increases.

With Ripple, no one can steal money. Just like with bitcoin, all transactions have to be signed by the payer at least. However, instead of POW being what selects the next miner, there's a different consensus algorithm that doesn't waste electricity. And Ripple moves more money than bitcoin per day.

I don’t dispute that. Ripple is centralized, there are dozens of centralized payment systems out there, but that’s not what Bitcoin is competing against. Creating performant, centralized payment systems are a solved problem. The question is what Ripple brings to the table that the other payment systems don’t.

Bitcoin is just as centralized now in practice. There are just a few mining pools that have the most electricity to spend. In Ripple they will eventually expand the number of main nodes way beyond what bitcoin has.

Once a transaction has been made you just need SOMEONE to confirm it for the blockchain. In bitcoin, that's the miner that happened to solve the POW. If they don't take your transaction, the next miner will. In Ripple it's effectively the same thing.

Even with Byteball the witnesses cant steal funds or generate new ones without the other full nodes noticing and rejecting the same way as other bitcoin full nodes can reject if a miner generates a 10000 coinbase reward to itself.

I don’t understand. If nodes do not accept whatever the witnesses say is the true transaction history, why are the witnesses needed in the first place?

I know that it’s not possible for a witness to fake some users signature, and send these funds to themselves, but that’s not the attack we need to worry about. The attack we need to worry about is witnesses colluding to present a false history of transactions, such that the user’s funds (that the miners want) were never sent to that user in the first place, thus remaining the property of the coinbase owner. Since all coins originate as a coinbase, if witnesses go far enough back in time, all coins are theirs.

Reply on news.ycombinator.com