6 ms·

The Subjectivity / Exploitability Tradeoff

25 points by jrbedard 12y ago

kanzure 12y ago
> The key argument is this: proof of work, at the core, can be seen in two different ways Neither of those ways are how anyone describes proof of work. I can offer two explanations. First is the explanation of the Byzantine Generals' Problem from bitcoin.org: http://web.archive.org/web/20090309175840/http://www.bitcoin.org/byzantine.html http://web.archive.org/web/20090309175840/http://www.bitcoin... A number of Byzantine Generals each have a computer and want to attack the King's wi-fi by brute forcing the password, which they've learned is a certain number of characters in length. Once they stimulate the network to generate a packet, they must crack the password within a limited time to break in and erase the logs, lest they be discovered. They only have enough CPU power to crack it fast enough if a majority of them attack at the same time. They don't particularly care when the attack will be, just that they agree. It has been decided that anyone who feels like it will announce an attack time, which we'll call the "plan", and whatever plan is heard first will be the official plan. The problem is that the network is not instantaneous, and if two generals announce different plans at close to the same time, some may hear one first and others hear the other first. They use a proof-of-work chain to solve the problem. Once each general receives whatever plan he hears first, he sets his computer to solve a difficult hash-based proof-of-work problem that includes the plan in its hash. The proof-of-work is difficult enough that with all of them working at once, it's expected to take 10 minutes before one of them finds a solution and broadcasts it to the network. Once received, everyone adjusts the hash in their proof-of-work computation to include the first solution, so that when they find the next proof-of-work, it chains after the first one. If anyone was working on a different plan, they switch to this one, because its proof-of-work chain is now longer. After about two hours, the plan should be hashed by a chain of 12 proofs-of-work. Every general, just by verifying the difficulty of the proof-of-work chain, can estimate how much parallel CPU power per hour was expended on it and see that it must have required the majority of the computers to produce in the allotted time. At the least, most of them had to have seen the plan, since the proof-of-work is proof that they worked on it. If the CPU power exhibited by the proof-of-work is sufficient to crack the password, they can safely attack at the agreed time. Second is a more general understanding: Proof-of-Work (PoW) works because of the economic restriction provided by the second law of thermodynamics. Even though you can't know you're in the consensus set, you can put a raw economic cost on the probability of you being tricked. Bitcoin uses proof-of-work to tie Bitcoin consensus to a fundamentally scarce resource, namely negentropy. It is possible to use another physically scarce resource instead, but there is no alternative to the universal scarcity of negentropy. As maaku puts it, "I could be an AI trapped in a simulation with no knowledge of the outside world other than the foundational laws of physics, and from that be able to assert the validity of proof-of-work.". (Really it has nothing to do with currency. Sorry folks.)
- Adlai 12y ago
  This explanation doesn't cover how Bitcoin determines difficulty. I tried to come up with a rewrite that does, but the original example has the "password, which they've learned is a certain number of characters in length", and Bitcoin has no such fixed target; rather, it simply requires reaching consensus on transaction ordering, with the first-in-consensus transaction moving some funds being the only valid one (subsequent transactions are double-spends). This consensus is achieved through a game-theoretic setup, involving a PoW chain, which endeavors to: 1) make an attack as expensive as physically possible, and to 2) provide a rational actor with access to a given amount of computational power a stronger incentive to collaborate, than to attack Evidence in favor of Bitcoin's setup achieving the second goal is that the system is still alive despite individuals repeatedly having access to sufficient power to perform double spends; in fact, they already have, yet the system as a whole keeps running: https://bitcointalk.org/index.php?topic=321630.0 https://bitcointalk.org/index.php?topic=321630.0
- caymannava 12y ago
  > Neither of those ways are how anyone describes proof of work. Argument from silence. Your explanations are, of course, correct. You are just approaching this differently than he. Given a system with mechanisms that work according to your explanations, we can also describe the system in terms of economics and game theory (and possibly gain some extra insight). This is what Vitalik is doing. Specifically, in the first way, he's saying that PoW can be seen as a game that rewards participant votes toward a majority vote that hopes to align with a schelling point, ie, schellingcoin. Here, participants vote with their mining power, and those that vote with the majority are rewarded, while everyone else gets nothing. In the second way, he's saying the PoW is a market between tokens and resources, which can be measured in total computational power. > it has nothing to do with currency. PoW does to do with currency, in practice, because participating has a real cost; miners are trading some resources, electricity and computational power, for tokens as part of what could be described as a schellingcoin mechanism. If there was no currency involved, no reward for 'correctly' participating, no 'market' for trading computation for currency, I'd assume that no work would actually ever be done by rational actors. Looking at these incentives of the system, looking from an economic and game theoretic perspective, can help us gain insight about how these systems perform in the real world of limited resources and competing ideologies and actors. This field is being called "cryptoeconomics". https://www.youtube.com/watch?v=9lw3s7iGUXQ https://www.youtube.com/watch?v=9lw3s7iGUXQ
lappa 12y ago
Vitaliks games aren't amusing. A blockchain has fundamental limitations that prevent PoS from working, namely it must be costly to make a fork[1]. Complexity is the enemy of security. Bitcoin solved the consensus problem with it's relatively simple incentive scheme. This post starts off by proposing a flawed system, making slight changes to the flawed system (punish attackers, trust someone when downloading the chain, assume economic incentives will cause people to update their software after an attack, etc) and recursively point out ways to "fix" those problems while at the same time either introducing more subproblems or more centralization. This is similar to what is being done with Ethereum. Instead of one clear problem, there are many small unclear problems caused by trying to fix problems caused by a fix of a fix of a fix of the fundamental problem. In short, this is Vitaliks Fractal. [1] https://download.wpsoftware.net/bitcoin/pos.pdf https://download.wpsoftware.net/bitcoin/pos.pdf
- drcode 12y ago
  I see where your coming from, but I think you are wrong: The problem right now is that Bitcoin is a very hard system to upgrade or expand, and because of this cryptocurrency innovation is starting to stagnate (in a similar way that the traditional banking system has stifled innovation in the last 50 years.) The concerning part of Vitalik's posts is that right now they build unproven ideas on top of other unproven ideas, because we lack empirical evidence to test these kinds of things, because Bitcoin isn't a general-purpose infrastructure for trying out new cryptoeconomic models... it seems kind of unfair for knocking a guy though for trying to analyze them anyway. However, in 2015, with the launch of Ethereum 1.0 and other competing systems, we'll get a lot more hard data than ever to find out which of these kinds of ideas are good- Both because these systems themselves test these ideas, and because they allow ideas like this to be built on top of them. So you may be right that there are bad ideas here (As a fan of POS I disagree on that one with you, however) but they are not "fractal" and we will know in the near future with empirical data which ones need to be tossed away.
  - lappa 12y ago
    >The concerning part of Vitalik's posts is that right now they build unproven ideas on top of other unproven ideas Not only are they unproven, but there are mounds of evidence that it isn't possible. >it seems kind of unfair for knocking a guy though for trying to analyze them anyway. I'm knocking him because he is dangerously misinformed and is implementing and promoting broken cryptographic systems. >However, in 2015, with the launch of Ethereum 1.0 and other competing systems, we'll get a lot more hard data than ever to find out which of these kinds of ideas are good- Both because these systems themselves test these ideas, and because they allow ideas like this to be built on top of them. We already have seen that amateur cryptographers cannot make their unworkable ideas workable. You don't need another broken altcoin (Ethereum) to know this, you need to understand what the blockchain accomplishes to know this. I'm sure once Ethereum fails there will be a new next big thing and people will get sucked into another broken system, but you can actually understand what is a good idea if you try to understand the blockchain. You don't need to cross items from the near-infinite list of possible bad ideas to know what's a bad idea. I'm not sure what you mean by "Ideas like this to be built on top of them." If you already have Ethereums PoW consensus system, what the hell would having a PoS consensus system on top of that accomplish? >but they are not "fractal" and we will know in the near future with empirical data which ones need to be tossed away. They are certainly fractal. One could recursively say why each of those fixes have problems, and eventually you would end up with a fully centralized system that masquerades itself as being decentralized and PoS or a completely broken system that is attackable for near-free.

25 points by jrbedard 12y ago

> The key argument is this: proof of work, at the core, can be seen in two different ways Neither of those ways are how anyone describes proof of work. I can offer two explanations. First is the explanation of the Byzantine Generals' Problem from bitcoin.org: http://web.archive.org/web/20090309175840/http://www.bitcoin.org/byzantine.html http://web.archive.org/web/20090309175840/http://www.bitcoin... A number of Byzantine Generals each have a computer and want to attack the King's wi-fi by brute forcing the password, which they've learned is a certain number of characters in length. Once they stimulate the network to generate a packet, they must crack the password within a limited time to break in and erase the logs, lest they be discovered. They only have enough CPU power to crack it fast enough if a majority of them attack at the same time. They don't particularly care when the attack will be, just that they agree. It has been decided that anyone who feels like it will announce an attack time, which we'll call the "plan", and whatever plan is heard first will be the official plan. The problem is that the network is not instantaneous, and if two generals announce different plans at close to the same time, some may hear one first and others hear the other first. They use a proof-of-work chain to solve the problem. Once each general receives whatever plan he hears first, he sets his computer to solve a difficult hash-based proof-of-work problem that includes the plan in its hash. The proof-of-work is difficult enough that with all of them working at once, it's expected to take 10 minutes before one of them finds a solution and broadcasts it to the network. Once received, everyone adjusts the hash in their proof-of-work computation to include the first solution, so that when they find the next proof-of-work, it chains after the first one. If anyone was working on a different plan, they switch to this one, because its proof-of-work chain is now longer. After about two hours, the plan should be hashed by a chain of 12 proofs-of-work. Every general, just by verifying the difficulty of the proof-of-work chain, can estimate how much parallel CPU power per hour was expended on it and see that it must have required the majority of the computers to produce in the allotted time. At the least, most of them had to have seen the plan, since the proof-of-work is proof that they worked on it. If the CPU power exhibited by the proof-of-work is sufficient to crack the password, they can safely attack at the agreed time. Second is a more general understanding: Proof-of-Work (PoW) works because of the economic restriction provided by the second law of thermodynamics. Even though you can't know you're in the consensus set, you can put a raw economic cost on the probability of you being tricked. Bitcoin uses proof-of-work to tie Bitcoin consensus to a fundamentally scarce resource, namely negentropy. It is possible to use another physically scarce resource instead, but there is no alternative to the universal scarcity of negentropy. As maaku puts it, "I could be an AI trapped in a simulation with no knowledge of the outside world other than the foundational laws of physics, and from that be able to assert the validity of proof-of-work.". (Really it has nothing to do with currency. Sorry folks.)

Adlai 12y ago
This explanation doesn't cover how Bitcoin determines difficulty. I tried to come up with a rewrite that does, but the original example has the "password, which they've learned is a certain number of characters in length", and Bitcoin has no such fixed target; rather, it simply requires reaching consensus on transaction ordering, with the first-in-consensus transaction moving some funds being the only valid one (subsequent transactions are double-spends). This consensus is achieved through a game-theoretic setup, involving a PoW chain, which endeavors to: 1) make an attack as expensive as physically possible, and to 2) provide a rational actor with access to a given amount of computational power a stronger incentive to collaborate, than to attack Evidence in favor of Bitcoin's setup achieving the second goal is that the system is still alive despite individuals repeatedly having access to sufficient power to perform double spends; in fact, they already have, yet the system as a whole keeps running: https://bitcointalk.org/index.php?topic=321630.0 https://bitcointalk.org/index.php?topic=321630.0
caymannava 12y ago
> Neither of those ways are how anyone describes proof of work. Argument from silence. Your explanations are, of course, correct. You are just approaching this differently than he. Given a system with mechanisms that work according to your explanations, we can also describe the system in terms of economics and game theory (and possibly gain some extra insight). This is what Vitalik is doing. Specifically, in the first way, he's saying that PoW can be seen as a game that rewards participant votes toward a majority vote that hopes to align with a schelling point, ie, schellingcoin. Here, participants vote with their mining power, and those that vote with the majority are rewarded, while everyone else gets nothing. In the second way, he's saying the PoW is a market between tokens and resources, which can be measured in total computational power. > it has nothing to do with currency. PoW does to do with currency, in practice, because participating has a real cost; miners are trading some resources, electricity and computational power, for tokens as part of what could be described as a schellingcoin mechanism. If there was no currency involved, no reward for 'correctly' participating, no 'market' for trading computation for currency, I'd assume that no work would actually ever be done by rational actors. Looking at these incentives of the system, looking from an economic and game theoretic perspective, can help us gain insight about how these systems perform in the real world of limited resources and competing ideologies and actors. This field is being called "cryptoeconomics". https://www.youtube.com/watch?v=9lw3s7iGUXQ https://www.youtube.com/watch?v=9lw3s7iGUXQ

lappa 12y ago

Vitaliks games aren't amusing. A blockchain has fundamental limitations that prevent PoS from working, namely it must be costly to make a fork[1]. Complexity is the enemy of security. Bitcoin solved the consensus problem with it's relatively simple incentive scheme. This post starts off by proposing a flawed system, making slight changes to the flawed system (punish attackers, trust someone when downloading the chain, assume economic incentives will cause people to update their software after an attack, etc) and recursively point out ways to "fix" those problems while at the same time either introducing more subproblems or more centralization. This is similar to what is being done with Ethereum. Instead of one clear problem, there are many small unclear problems caused by trying to fix problems caused by a fix of a fix of a fix of the fundamental problem. In short, this is Vitaliks Fractal. [1] https://download.wpsoftware.net/bitcoin/pos.pdf https://download.wpsoftware.net/bitcoin/pos.pdf

drcode 12y ago
I see where your coming from, but I think you are wrong: The problem right now is that Bitcoin is a very hard system to upgrade or expand, and because of this cryptocurrency innovation is starting to stagnate (in a similar way that the traditional banking system has stifled innovation in the last 50 years.) The concerning part of Vitalik's posts is that right now they build unproven ideas on top of other unproven ideas, because we lack empirical evidence to test these kinds of things, because Bitcoin isn't a general-purpose infrastructure for trying out new cryptoeconomic models... it seems kind of unfair for knocking a guy though for trying to analyze them anyway. However, in 2015, with the launch of Ethereum 1.0 and other competing systems, we'll get a lot more hard data than ever to find out which of these kinds of ideas are good- Both because these systems themselves test these ideas, and because they allow ideas like this to be built on top of them. So you may be right that there are bad ideas here (As a fan of POS I disagree on that one with you, however) but they are not "fractal" and we will know in the near future with empirical data which ones need to be tossed away.
- lappa 12y ago
  >The concerning part of Vitalik's posts is that right now they build unproven ideas on top of other unproven ideas Not only are they unproven, but there are mounds of evidence that it isn't possible. >it seems kind of unfair for knocking a guy though for trying to analyze them anyway. I'm knocking him because he is dangerously misinformed and is implementing and promoting broken cryptographic systems. >However, in 2015, with the launch of Ethereum 1.0 and other competing systems, we'll get a lot more hard data than ever to find out which of these kinds of ideas are good- Both because these systems themselves test these ideas, and because they allow ideas like this to be built on top of them. We already have seen that amateur cryptographers cannot make their unworkable ideas workable. You don't need another broken altcoin (Ethereum) to know this, you need to understand what the blockchain accomplishes to know this. I'm sure once Ethereum fails there will be a new next big thing and people will get sucked into another broken system, but you can actually understand what is a good idea if you try to understand the blockchain. You don't need to cross items from the near-infinite list of possible bad ideas to know what's a bad idea. I'm not sure what you mean by "Ideas like this to be built on top of them." If you already have Ethereums PoW consensus system, what the hell would having a PoS consensus system on top of that accomplish? >but they are not "fractal" and we will know in the near future with empirical data which ones need to be tossed away. They are certainly fractal. One could recursively say why each of those fixes have problems, and eventually you would end up with a fully centralized system that masquerades itself as being decentralized and PoS or a completely broken system that is attackable for near-free.