7 ms·

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 comp

by nullc 9y 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-of-idle.html 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.

SkyMarshal 9y 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://youtu.be/aYG0NxoG7yw; https://cyber.stanford.edu/sites/default/files/bramcohen.pdf https://cyber.stanford.edu/sites/default/files/bramcohen.pdf 2. DFINITY VRF-based Threshold Relay: https://youtu.be/o8HHM18PedU https://youtu.be/o8HHM18PedU (https://en.wikipedia.org/wiki/Verifiable_random_function https://en.wikipedia.org/wiki/Verifiable_random_function) 3. Algorand: https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf https://people.csail.mit.edu/nickolai/papers/gilad-algorand-... These are some of the more interesting ones, but plenty of others.
- empath75 9y 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.
  - colordrops 9y ago
    That would not be a recurring cost unlike electricity.
    - dullgiulio 9y ago
      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.
      - rictic 9y ago
        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.
  - AlexCoventry 9y ago
    Burstcoin has a design like this, except for hard drive space instead of RAM.
- jon_richards 9y 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.
  - colordrops 9y ago
    How could it not be gamed by introducing artificial latency?
  - sbanach 9y ago
    High frequency trading?
  - infogulch 9y ago
    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.
  - sktrdie 9y ago
    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.
- thruflo22 9y 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.
  - triplesec 9y ago
    My maths isn't good enough for this yet, but I did wonder why there wasn't a popular SETIcoin
    - rothbardrand 9y ago
      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.
  - burrows 9y ago
    eg: BOINC, https://boinc.berkeley.edu/ https://boinc.berkeley.edu/
  - andrewstuart2 9y ago
    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.
    - xg15 9y ago
      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)
- Shorel 9y ago
  Great, so far I had only read about proof of Stake and proof of Activity
EGreg 9y 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?
- antocv 9y ago
  You would be interested in Byteball. See https://byteball.org/ 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.
  - runeks 9y ago
    > 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.
deleted 9y ago
[deleted]

by nullc 9y ago

SkyMarshal 9y 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://youtu.be/aYG0NxoG7yw; https://cyber.stanford.edu/sites/default/files/bramcohen.pdf https://cyber.stanford.edu/sites/default/files/bramcohen.pdf 2. DFINITY VRF-based Threshold Relay: https://youtu.be/o8HHM18PedU https://youtu.be/o8HHM18PedU (https://en.wikipedia.org/wiki/Verifiable_random_function https://en.wikipedia.org/wiki/Verifiable_random_function) 3. Algorand: https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf https://people.csail.mit.edu/nickolai/papers/gilad-algorand-... These are some of the more interesting ones, but plenty of others.

empath75 9y 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.
- colordrops 9y ago
  That would not be a recurring cost unlike electricity.
  - dullgiulio 9y ago
    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.
    - rictic 9y ago
      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.
- AlexCoventry 9y ago
  Burstcoin has a design like this, except for hard drive space instead of RAM.
jon_richards 9y 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.
- colordrops 9y ago
  How could it not be gamed by introducing artificial latency?
- sbanach 9y ago
  High frequency trading?
- infogulch 9y ago
  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.
- sktrdie 9y ago
  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.
thruflo22 9y 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.
- triplesec 9y ago
  My maths isn't good enough for this yet, but I did wonder why there wasn't a popular SETIcoin
  - rothbardrand 9y ago
    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.
- burrows 9y ago
  eg: BOINC, https://boinc.berkeley.edu/ https://boinc.berkeley.edu/
- andrewstuart2 9y ago
  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.
  - xg15 9y ago
    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)
Shorel 9y ago
Great, so far I had only read about proof of Stake and proof of Activity

EGreg 9y 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?

antocv 9y ago
You would be interested in Byteball. See https://byteball.org/ 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.
- runeks 9y ago
  > 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.

deleted 9y ago

[deleted]