Proof-of-Work designed for lower power consumption

[alkan]

Hi folks,

I’ve have an idea about how to make proof-of-works more energy-friendly by lowering power consumption. At first sight, this might seem impossible since proof-of-work schemes are explicitly designed to reward the (wasteful) computation that is used to build new blocks. The incentive is clearly to process as many hashes as you can, which is true for everybody and every time.

What if it was possible to temporarily limit mining to alternating subsets of the participants? In other words, only a fraction of the total computation power would be eligible for creating new blocks (and coins) at any time. Of course, we need a mechanism to ensure that the miners are selected in a fair way, i.e. according to their relative computation power. To that end, we have to pre-select those who can lawfully create new blocks in the actual mining phase. Here’s a brief outline of my concept:

1) Pre-selection phase

No actual mining and block-building is taking place at this stage. The sole aim is to determine who can get into the mining phase. Every node can take part and compete to be selected.

Let’s start with an existing block X1. The task consists in finding a hash value h(h(X1) || pubkey_address || nonce) < threshold. Every node who finds a suitable hash, will broadcast it to his peers. The nodes collect all the hashes they receive.

Once a node has collected n hashes, he will start working on the next block X2. In addition to the regular transactions, X2 must also contain a list of n pubkey_addresses along with the hash puzzles they solved. The successful miner of X2 earns a reward for this block, i.e. some number of bitcoins. With the creation of block X2, the pre-selection phase comes to an end.

2) Mining phase

The actual mining happens in this phase. Although participation is not strictly limited to nodes that succeeded in the pre-selection phase, rewards can only go to the pubkey_addresses listed in block X2. Therefore, no one except the owners of the listed addresses will have an incentive to take part in mining.

Every node can easily check if the block reward goes to a pubkey_address contained in X2. If this is not the case, the block will be regarded as invalid. As a result, only nodes who got into the list will eventually mine the blocks X3, X4, ... This phase ends after the successful mining of the m’th block, which will serve as the basis for the next pre-selection phase.

While changing the value of m alters the length of mining phase, n determines the number of nodes (or: amount of computation power) who will probably take part in mining. As the pre-selected nodes are a random subset of the total computation power, on average, the share of honest nodes will be the same as overall. However, each subset will be a Gaussian distribution between honest and malicious nodes, so in some groups there will be more malicious nodes than in others. Luckily, this effect becomes negligible for high n’s.

As a result, most of the nodes will only mine at short intervals of time (pre-selection phases), which should lower power consumption considerably.

What do you think of all this?

Please bear with me as I’m pretty new to the concept of Bitcoin and my reasoning might be completely wrong. Thanks a lot.

Cheers!
alkan

[alkan]

As participation in mining is not limited to the pre-selected nodes, it's possible that malicious nodes nevertheless take part in mining by indicating the listed pubkey_addresses in the blocks they create. While they couldn't make a direct reward out of this (as the block reward would go to other users), they could still try to take over 51 % of the hashing power. As only a subset of the total hasing power is incentivized to mine actual blocks, such an attack would be much easier to achieve than in standard Bitcoin.

It's quite easy to remedy this issue though since the pubkey_adresses allow for identification of the owners by the means of digital signature. Therefore, we should strictly limit participation in mining to nodes who can prove that they have solved the hash puzzles in the pre-selection phase. All we have to do is to require them to sign the blocks with their private keys, so that everyone could verify if they belong to the list of pubkey_adresses.


Even with this limitation imposed, the problem remains that n should be kept low in order to save energy, while it should be as high as possible to prevent any single entity (i.e. a large mining pool) from dominating the mining phase with 51 % of the hashing power.

There's a solution to remedy this tradeoff. Let's determine a specific set of eligible nodes for every single block in the mining phase rather than a general set of nodes that can together work on all of the 1...m blocks. To that end, the pre-selection phase would be used to get m random subsets, one for every block:

1) Collect n hash puzzles like before and order them according to their value.
2) Make m subsets of size n/m from the corresponding pubkey_addresses: [addr_1...addr_n/m], [addr_n/m+1...addr_2n/m], [addr_2n/m+1...addr3n/m], ...
3) Nodes contained in [addr_1...addr_n/m] are allowed to mine block 1, nodes in [addr_n/m+1...addr_2n/m] could mine block 2, and so on.

In this scenario, n can be chosen sufficiently large to include most of the hashing power in subsequent mining. On the other hand, the nodes in a specific subset would only represent a small portion of the total hashing power. Even though attacks would still be possible, it's nothing to worry about since the varying composition of the subsets guarantees that invalid blocks can be quickly discarded by honest nodes who come after them. In contrast to my original proposal where successful attackers might affect a whole chain segment of m blocks, attacks would thus be limited to single blocks of the chain.

[cr1776]

How do you limit it one pubkey_address per "node"?  

e.g. I don't see anything preventing node X from creating Y million pubkeys for their node and treating their node as 1 million individual nodes for this purpose, assuming they are a large pool this seems doable.  And with IPv6, tor, dhcp etc, tying it to a single IP address doesn't seem like a solution.  A single pool hashes these puzzles during the mining phase and treats themselves as a large cluster of nodes vs one single pool?

And how do you stop hash power "hopping" from one node to another depending on who is allowed to mine a block?

:-)

[alkan]

How do you limit it one pubkey_address per "node"?  

e.g. I don't see anything preventing node X from creating Y million pubkeys for their node and treating their node as 1 million individual nodes for this purpose, assuming they are a large pool this seems doable.  And with IPv6, tor, dhcp etc, tying it to a single IP address doesn't seem like a solution.  A single pool hashes these puzzles during the mining phase and treats themselves as a large cluster of nodes vs one single pool?

And how do you stop hash power "hopping" from one node to another depending on who is allowed to mine a block?

:-)

You're right, there's no possibility to limit a pubkey_address to a specific node. But that shouldn't be a problem since computation power remains the limiting factor. The success of a node (or a pool of nodes) won't depend on the number of pubkeys or IP addresses it owns. To get into the mining phase, it still needs to successfully solve at least one hash puzzle. The fact that you have a lot of pubkey_addresses to choose from doesn't make it easier to find a suitable hash. Of course, a mining pool that owns 10 % of the total computation power will be able to solve 10 % of the hash puzzles on average and, as a consequence, build 10 % of the blocks later on.

There's no difference to the existing mining algorithm in that regard. However, the distribution of the nodes in smaller subsets will show a greater variance, which can constitute a risk if we let the selected nodes mine a lot of blocks in series. That's why I finally suggested to allow each subset (or sub-subset of n/m nodes) to mine only one single block. This makes it unlikely that the attacker will make it into several consecutive subsets.

[spartacusrex]

You could limit the set of allowed miners per block by using POS. This is sybil attack proof.

Then if you are allowed - you use your POW.

[alkan]

You could limit the set of allowed miners per block by using POS. This is sybil attack proof.

Then if you are allowed - you use your POW.

That's an interesting idea and it's certainly sybil attack proof. Using POS to limit the set of POW miners would also solve an issue that I initially overlooked in my proposal. In the pre-selection phase, nodes who are interested in mining have a disincentive to not broadcast any hash puzzle they receive since that would lessen their chance of being among the first n puzzle solvers who can make it into the actual mining phase.  

The problem with POS is the fact that there are no guarantees that someone with a high stake is also interested in mining coins by POW. So, you would probably have to admit a (very) large set of nodes to ensure that there will be enough active miners, which adversely affects the goal of having small mining sets to reduce power consumption.


Maybe we could use a completely different approach to enforce nodes to only mine periodically, thus saving energy. The approach is based on the idea of having two separate blockchains instead of one. The first block chain serves as a meta-chain with the purpose of selecting the allowed miners of the second chain and is empty otherwise. The second chain is the block chain that includes all the transactions. Let's call it transaction chain.

1) Meta-chain. It is built like the regular Bitcoin blockchain by POW. However, in order to create new blocks (that are accepted by your peers), a condition must be met which is not given most of the time (this is to ensure low power consumption). The condition is that the number of eligible miners of the transaction chain is within a certain range [min,max]. Miners of the meta-chain would thus only create blocks to extend the chain to its new length once the number of eligible miners falls below the threshold. So, mining would only take place every now and then. When creating a new block of the meta-chain, the node has to include his address (public key) for later identification while there's no immediate block reward for this block.

2) Transaction chain. The transaction chain is built without any POW/POS mechanism whatsoever. Instead, the mining nodes (and thus the order of the blocks) are determined by a deterministic pseudo-random selector function (with a public seed) that is applied to the meta-chain. For example, the PRNG outputs a random value in the node address range. The node whose address has the lowest hamming distance to the value is selected as the next block creator and is then allowed to build the next transaction block to get a reward. For proper identification, each node has to sign the block with his private key so that the others can check it against his address (public key).

Block creation is performed according to a fixed time schedule with regular intervals. If a node fails to deliver his block in the allotted time, the other nodes would only accept a block built by the node who comes next according the the PRNG function. This ensures a well-arranged sequence of blocks. As the order of the miners is known in advance and blocks are created at a regular pace, the block time could be set much lower than in standard Bitcoin.

As it's not desirable to allow miners of the meta-chain to build transaction blocks forever, we have to set an upper limit for each participating node. Once a node (or more exactly: an instance of his address enshrined in the meta-chain) has built k blocks, it will be disabled from creating more blocks. That is, his address won't take part in the PRNG raffle any longer. As a result, more and more nodes will be barred over time, so that eventually the number of remaining eligible nodes will fall below the min threshold. In that case, step 1) will be reactivated and the meta-chain will be extended until the number of eligible nodes reaches the max threshold again.

I think that this approach is sybil-proof. Although you can create as many addresses as you like, your computing power limits your ability to build the meta-chain and to become a node who is allowed to build the transaction chain.

[cryptopunk]

The scheme strongly favors the largest pool since it will win most preselections. The next to largest pool will win less, therefore it's clients will have less profits per invested mining capital. Yes, there would be some savings with the energy costs, but not proportional to the revenue drop since capital costs are paramount in mining. The miners will therefore switch to the largest pool where they are able to compete on an equal footing with other miners; this pool will quickly control 100% of the hashing power and employ it 100% of the time. We have achieved centralization without any energy savings.

[joey.rich]

I've been working on a project where POW secures the network, but money is also given out by POS in proportion to coin days destroyed.  This effectively lowers the power consumption of the network since POW rewards are only a fraction of the coin's market cap.  For example 25% could be given out to miners and 75% to coin holders by gamified proof of stake.

I'm not sure if this could ever be bitcoin compatible since it relies on exponential inflation.

The whitepaper is here for anyone who's interested.
http://empirecoin.org/EmpirecoinWhitepaper.pdf

[funkenstein]

Proof-of-work is already incredibly energy-friendly.  The network has no energy minimum requirement, it simply runs on whatever excess power the miners are willing to spend on mining.  Thus energy use is self regulating. 

[alkan]

Proof-of-work is already incredibly energy-friendly.  The network has no energy minimum requirement, it simply runs on whatever excess power the miners are willing to spend on mining.  Thus energy use is self regulating.  

This is true if you measure energy efficiency against the mining rewards. A miner usually seeks to reduce his power consumption in order to increase his net profit. However, if you look at how much security you can get out of the total mining power, Bitcoin's PoW model is far from optimal.

Let me explain why. Bitcoin mining is a continuous process whose security is determined by the hash rate available at any given time. Therefore, an attacker only needs to accumulate 51 % of the current hashing power for a short time (i.e. by renting the hardware) to launch a successful short-range attack, i.e. to replace the most recent blocks of the chain by his own arbitrary blocks (with a double-spend).

On the other hand, to change the whole history of the network, potentially as far back as the genesis block, the attacker would have to generate an alternate chain faster than the existing chain. Such a long-range attack is extremely difficult to achieve because one would have to outpace the hashing power of all the honest nodes for a very long time. Hence, the Bitcoin network provides a much higher level of security against long-range attacks than with regard to short-range attacks. In other words, the mining power “materialized” in the existing blockchain (i.e. the total mining energy used thus far) only backs the existing chain but not the creation of new blocks. The mining energy is wasted in that regard, which is sub-optimal.

To overcome this issue, we could use a separate blockchain (meta chain) to determine the block creation order of the actual transaction chain. This could be done by selecting a random block of the meta chain whose creator is elected as the miner of the next block of the transaction chain (Of course, this requires a selection process that is truly random and manipulation-proof). In contrast to mining the meta chain, building a block of the transaction chain will come with a reward for the creator.

The security of the transaction chain does not rely on the network's current hash rate but on the cumulative hash power stored in the meta chain. With such a model, short-range attacks would become equally hard as long-range attacks.

Contrary to what one might think at first, this system does not facilitate centralization any more than Bitcoin's PoW already does. As mining is a dynamic process with miners coming and going, one would have to exhibit the same relative mining power during the whole lifetime of the currency in order to preserve the same share of the mining rewards.

[funkenstein]

Hmm, interesting  

Somebody else was doing this with an altcoin, I can't remember which one now sorry.  The motivation stated was to make the arrival of blocks more regular.  One potential issue is that if such a coin existed and was popular, if one could mine the "rights" to a future block - one would have a cryptographic key which enabled the creation of block N and the collection of reward R for so doing.  In this instance we could imagine that a market would arise for such keys.  A miner would be willing to part with his key for R + epsilon, which is after all more than he would get for mining the thing himself.   Thus we return to our original model, shared by PoW and PoS, in which ability to create a block can be rented or purchased on the open market - and short term security of untrusted transaction is again proportional to this price. 

 

[alkan]

Thanks for your quick response!

That's an interesting objection. It's questionable though if a market for creation rights would arise in practice since that would require the transfer of the private key to the new miner. As private keys cannot be changed, the seller could still use his key to steal the reward from the buyer.

[alkan]

Besides, the metachain I described offers the advantage that its block creation rate can be chosen flexibly since it has no direct influence on the transaction ledger. In particular, it's not necessary to have a constant block rate. This makes it possible to adapt the hash difficulty in order to save energy in the long run. In extremis you could foresee a difficulty function that will eventually, e.g. after several years of operation, put an end to mining.

[alkan]

Instead of relying on metachains, we could use hash puzzles that must be added to regular blocks in order to leverage the cumulative hash power of the whole chain.

A hash puzzle is regarded as valid if it satisfies the following condition: h(prev_block|account_id|nonce) < puzzle_difficulty
Blocks must satisfy a different condition: h(account_id) < acc_score * no_of_included_puzzles * block_difficulty

Hash puzzles are derived from the previous block, are tied to the creator's account and can only be included in the next block.

For every hash puzzle that makes it into a block, the creator's account gets a reward and its score is increased:
acct_score := acc_score + 1
reward := 1

For every created block, the minter also gets a small reward in proportion to the number of hash puzzles that he included in the block:
reward := c*no_of_included_puzzles (c is a small constant so that block reward is small compared to the puzzle rewards)

Minting of blocks doesn't require PoW but is random lottery like in PoS. The increasing no_of_included_puzzles ensures that a minter can be found within a reasonable time since the users will keep creating (and broadcasting) more an more puzzles, thereby increasing the chances that somebody will eventually satisfy the condition. The higher the alltime score of an account, the more likely it will become the next minter.

As the reward is based on no_of_included_puzzles, the minter has a strong incentive to include as many puzzles as possible. On the other hand, it is risky for him to withhold a valid block for too long since another minter might supervene and win the race. So, minters have an incentive to release their blocks as soon as possible. In case of multiple concurring valid blocks, the nodes select the block with the lowest number of puzzles.

This scheme offers the following advantages over traditional PoW:
1) The creation of new blocks is secured by the cumulative hash power stored in the existing chain since the probability of becoming the next minter depends on the total number of hash puzzles that one has solved thus far.
2) Decentralization is facilitated because hash puzzles can be created with much less hash power and at much faster intervals than blocks.