BIP 52: Durable, Low Energy Bitcoin PoW

pkvk commented at 6:00 pm on May 26, 2021: none

Bitcoin’s energy consumption is growing with its value. Although scaling PoW is necessary to maintain the security of the network, reliance on massive energy consumption has scaling drawbacks and leads to mining centralization. A major consequence of the central role of local electricity cost in mining is that today, most existing and potential participants in the Bitcoin network cannot profitably mine Bitcoin even if they have the capital to invest in mining hardware. From a practical perspective, Bitcoin adoption by companies like Tesla (which recently rescinded its acceptance of Bitcoin as payment) has been hampered by its massive energy consumption and perceived environmental impact.

We propose a novel proof-of-work paradigm for Bitcoin–Optical proof-of-work. It is designed to decouple Bitcoin mining from energy and make it feasible outside of regions with low electricity costs. The proposal has been discussed on Bitcoin Dev mailing list https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-May/018951.html.

[DRAFT] Durable, Low Energy Bitcoin PoW 250cf54409

zawy12 commented at 7:36 pm on June 8, 2021: none

Isn’t all of your CAPEX/electricity improvement due to the delay caused by the non-photonic A2D and D2A converters? Without that delay, it looks like you could build a large number of ASICs operating in parallel around a single photonic unit. Your requirement for a random oracle (from past blocks) seems necessary in your system and Chia’s to provide a salt for the delay function. It feels like old blocks giving future miners a permission key to mine, forcing them to go through the delay function instead of being able to mine the whole time.

Our skepticism is about the shortest section in the paper, section 4.1. The evidence either way on the issue is weak. We skeptics assume that as the technology improves, photonics will split the CAPEX and lifetime electrical costs roughly 50-50 like ASICs. There seems to be a basic economic principle at work. Even cars seem to have a 50-50 split between CAPEX and lifetime fuel. If it were possible to scale the other way (away from photonics) and use marbles and gravity for digital computing instead of electrons and voltage, I would expect eventually reaching a 50-50 split, not 10x more lifetime_energy per CAPEX as might be expected if photons are going to enable 1/10th lifetime_energy per CAPEX. The competition for rewards in combination with economics seems to negate any increase or decrease in efficiency.

100% electricity for mining does not work because electricity is plentiful over the short term to any attacker. But 100% CAPEX is barely distinguishable from PoS. 0% energy means you can’t change a single nonce even in photonics due to Landauer’s limit, so you have to find another source of randomness to select the block leader in PoS and the CAPEX-heavy Chia. Your proposal (like Chia) requires prior randomness which makes me wonder if that alone is proof it’s leaning away from PoW. It’s interesting you also have a necessary time delay like Chia (your A2D and D2A convertors). But there’s no proof (as in Chia’s) that the delay can be maintained. If the delay is mostly removed, you’re back to square one with an ASIC burning through nonces to interact in parallel with a single photonics chip. As miners push for cheaper CAPEX and faster use of the photonics, the A2D and D2A convertors might be a target. If a 50-50 split is what miners want, I imagine they will find ways to support cheaper photonics with wasteful ASICs.

For those interested in how & why the extra randomness is needed, see this video.

sp-mdubrovsky commented at 7:09 pm on July 2, 2021: none

Hey, thanks for your comments :)

Some inline comments below

Isn’t all of your CAPEX/electricity improvement due to the delay caused by the non-photonic A2D and D2A converters? Without that delay, it looks like you could build a large number of ASICs operating in parallel around a single photonic unit.

The clock speed of normal Bitcoin ASICs can also be seen as a measure of the delay. It’s true that the speed of an oPoW miner will be limited by the electronics and A2D D2A, not the optics.

Your requirement for a random oracle (from past blocks) seems necessary in your system and Chia’s to provide a salt for the delay function. It feels like old blocks giving future miners a permission key to mine, forcing them to go through the delay function instead of being able to mine the whole time.

It’s really a stretch to compare the two cases. Maybe you can be more specific (though we already discussed this a bit on the Twitter thread)

Our skepticism is about the shortest section in the paper, section 4.1. The evidence either way on the issue is weak. We skeptics assume that as the technology improves, photonics will split the CAPEX and lifetime electrical costs roughly 50-50 like ASICs. There seems to be a basic economic principle at work. Even cars seem to have a 50-50 split between CAPEX and lifetime fuel. If it were possible to scale the other way (away from photonics) and use marbles and gravity for digital computing instead of electrons and voltage, I would expect eventually reaching a 50-50 split, not 10x more lifetime_energy per CAPEX as might be expected if photons are going to enable 1/10th lifetime_energy per CAPEX. The competition for rewards in combination with economics seems to negate any increase or decrease in efficiency.

**We kept 4.1 intentionally short. It’s just something that will be shown empirically. There’s no evidence that 50/50 OPEX/CAPEX is somehow inevitable. Lot’s of examples of technology that uses very little energy relative to capex (think fiber optics). **

100% electricity for mining does not work because electricity is plentiful over the short term to any attacker. But 100% CAPEX is barely distinguishable from PoS. 0% energy means you can’t change a single nonce even in photonics due to Landauer’s limit, so you have to find another source of randomness to select the block leader in PoS and the CAPEX-heavy Chia. Your proposal (like Chia) requires prior randomness which makes me wonder if that alone is proof it’s leaning away from PoW.

It doesn’t 100% require hashing the previous blocks… that’s just one way to choose a random matrix. There are other options and the matrix can even be static.

It’s interesting you also have a necessary time delay like Chia (your A2D and D2A convertors). But there’s no proof (as in >Chia’s) that the delay can be maintained. If the delay is mostly removed, you’re back to square one with an ASIC burning >through nonces to interact in parallel with a single photonics chip. As miners push for cheaper CAPEX and faster use of the >photonics, the A2D and D2A convertors might be a target. If a 50-50 split is what miners want, I imagine they will find ways >to support cheaper photonics with wasteful ASICs.

Let’s explore what you mean by “what miners want.” Currently, the split is not really dictated by what miners want, there are tons of people and corporations who would mine if they could do it profitably. Even if there is some way to rig up a miner for oPoW that would be both competitive and 50/50 CAPEX/OPEX, that would not prevent people in regions with expensive electricity from buying miners with 90/10 or 99/1 CAPEX/OPEX splits if they can be produced. We can empirically see that no one is producing low-opex ASICs for SHA256, although there would definitely be demand. As long as oPoW opens this possibility, it will enable competition and that’s enough.

Having said that I don’t really see why the ratio would settle to whatever is the case for electronics. Photonics is generally low power relative to electronics in its current use case (telecom) and that is just carrying over to computation.

For those interested in how & why the extra randomness is needed, see this video.

Thanks for digging into the details btw

luke-jr commented at 8:00 pm on July 2, 2021: member

This needs a section addressing backward compatibility.

Eventually (though not strictly required to merge) it will need a more complete specification as well.

luke-jr added the label New BIP on Jul 2, 2021

zawy12 commented at 2:35 am on July 3, 2021: none

Here’s a link to the optical POW paper we’re discussing.

I would say “forward compatibility” when referring to old software being able to work on new data and “backwards compatibility” when referring to new software working on old data. It might be changed to be “mostly” forward compatible (but not very secure for old clients) at a cost in electrical waste by requiring the winning nonce that solves oPoW to also solve the regular PoW at 1/10th the oPoW cost. New nodes would validate both solutions while old nodes just validate the old POW. The nBits and block hash apply to the old POW. New nodes require the oPoW cost to be 10x the POW cost via a hard-coded conversion factor to tell new nodes what the oPoW target is. It’s an estimate that will change with time as the efficiencies of the two POWs diverge. It can’t be corrected without a hard fork. If oPoW efficiency gets 4x better while POW efficiency gets 2x better, the waste is 20% instead of 10%. A miner would work on both POWs at the same time. If either finds a solution, the nonce is fed to the other. The probability of a nonce winning both POWs in either order like this is 2 * (target/2^256)^2 / 10. The inverse of this is proportional to the cost to finding a winning solution that rewards & fees finance. The “2” can be beneficially removed by making the POW the 1st stage of the current oPoW. The cost to attack old nodes with just POW is the regular 2^256/target, so they’re much less secure. A fork is assured. There would be a wasteful “classic” BTC and the new efficient BTC.

The only way to be really forward compatible is if the heaviest work in sha256 can be efficiently turned over to photonics. If that happens, there’s no need for a BIP. This is probably more likely in the medium term than quantum solving.

By “what miner’s want” I mean they will sacrifice efficiency to replace CAPEX with OPEX due to the opportunity cost of tying up capital. A 90/10 machine with an equal lifetime sum of direct expenditures on computation (90+10=50+50 if expenses are defined as net “on computation”) is economically more expensive than a 50/50 machine due to higher opportunity cost (or interest payments) on the CAPEX. (Amortizing CAPEX costs as in your paper shifts value from computation to interest on debt payments or ignores opportunity loss aka baseline interest rates). If computes per joule (efficiency) were a constant for a given computing paradigm, the opportunity cost of capital being tied up might affect the ratio only a little (especially with current low interest rates). But the physics of computation causes efficiency to go down as we compute faster for a given CAPEX in a given generation, or as the paradigm improves to lower CAPEX/computation_rate faster than efficiency improves as a result of the economic incentive. In other words, increasing inefficiency costs from pushing Hz higher are offset by increasing computation_rate/CAPEX, so we can choose a lower CAPEX at the expense of electrical OPEX to lower debt interest costs (or opportunity costs if there’s no debt). Economics wants and physics enables the ratio to be lowered. I agree photonics’ incredibly low energy use makes it hard to see how this effect applies in oPoW, but the physics of computation seem to enable it if the tech is sufficiently advanced. This might highlight the importance of the A2D delay (it prevents pushing the photonics Hz enough to become less efficient). Advancing the tech under economics pressure should enable the delay/MAC_compute_eff ratio to be lowered in the future (& thereby CAPEX/OPEX decreased).

Pro-photonics comment: the CAPEX/compute_rate in photonics should rapidly go down but since that causes CAPEX depreciation, it keeps security per miner expense at the current low level (as your paper reiterates, prior solid research shows security in BTC is strictly a function of non-repurposeable non-depreciating CAPEX) instead of hurting the electrical savings argument. That OPEX is not waste because it motivates important advancements in an important computation technology like alt POWs have done for GPU technology.

Communication is physically the same as computation, so I have to look at your counterexample. The installation cost per equipment cost is a lot higher in telecom so a long lifetime is paramount, biasing it towards CAPEX. But the shift from copper/silicon to glass/photonics might have kept the same CAPEX/OPEX ratio if my principle applies. The comparison has to include entire systems, not just silicon and photonics. Similarly, home computers historically had a much higher CAPEX/OPEX, like 20:1. But the entire system includes the user’s time as part of the OPEX. That may make it look like 1:20, but there’s a limit to what the CAPEX can do for a user which is not the case in POW.

It’s really a stretch to compare the two cases.

I can only say it’s interesting Chia and oPoW both have more CAPEX to save energy, requires an extra piece of prior randomness that POW does not, and they both use a delay to save energy. The opposite of these 3 things exposes the physics of why they’re correlated: more energy enables more low-entropy generation in less time. POW requires prior randomness (the previous block hash) as a proof of delay up until the prior block, not a delay during the hashing. Each hash, as you say, is a delay, but the 2nd randomness POW uses is a nonce, not another prior randomness. It’s the result of a very wide and expensive energy-intensive search. I can’t say there’s a problem with oPoW because it also uses a nonce, but this kind of reasoning makes me wonder if someone smart could see a problem in the combination of using prior randomness on 2 different inputs, and the delay being inside a MAC as opposed to being strictly encased in a PRF like hashing.

luke-jr commented at 9:12 pm on August 29, 2021: member

It’s not required to be backward compatible, only required to document what the status of compatibility is.

jaysonmald35 approved

JeremyRubin commented at 4:39 pm on September 12, 2021: contributor

I think the particular algorithm has a security hole that is similar to ASICBoost in that batch processing appears to be faster.

Here’s a simple sketch of the idea:

Generate M
Generate 64 candidates x1_0…x1_63
assemble x1 matrix properly (each x1_i should be a row if I understand correctly)
multiply x1 * M
process each row

Without the matrix form, the algorithm is O(n^2) work per interation (multiply 64 entries x 64 columns), and 64 iterations yields an O(n^3) or concretely 262,144 multiplys. However, we can (at least theoretically!) apply Alma-Williams and obtain O(n^ 2.3728596) or 19,311.2991086. This is about a 14x speedup.

If you can modify these algorithms to use rectangular inputs against M you could probably create an even larger speedup.

zawy12 commented at 12:43 pm on September 20, 2021: none

It’s not required to be backward compatible, …

For newcomers who know Wikipedia’s definition of “backwards compatible” and have seen newer articles saying “forward compatible”, an expert saying “backward compatible” causes confusion, making people wonder if they know what’s being discussed. Soft forks enable old software to be forward compatible (can read new data). all forks are backwards compatible (can read old data). Not having a precise name for the new software that makes the old software forward compatible seems to be the problem

From 2017:

 0jonasschnelli    The sad thing is, it will be another feature that is not downward compatible.
 1sipa             breaking backward compatibility in major releases is fine
 2wumpus           don't you mean forwards compatible? backwards compatible means that it 
 3                can use old wallets, which should always be possible
 4jonasschnelli    wumpus: right. My fault.
 5sipa             backward compatible means that old software can use new wallets
 6wumpus           huh? I thought the other way around.
 7sipa             forward compatible is what you normally always have
 8wumpus           I don't understand it anymore then
 9sipa             oopz
10sipa             maybe i am wrong too
11sipa             i will shut up
12jtimon           all these backwards and forwards compatibility is confusing, ...

sp-mdubrovsky commented at 1:41 pm on September 29, 2021: none

Hi all, thanks for contributing to the discussion about oPoW!

We’ll edit the BIP to better address reverse compatibility
@JeremyRubin I don’t think you can really consider this an ASICBoost-type speed up. There are standard ways to speed up matrix multiplications, it’s an established area of research in complexity theory and 100s of hardware companies are working on it as well for AI, graphics, and so on. The limits are very well established and there is no low hanging fruit like there was for SHA256 when it first became a target for high performance computing due to Bitcoin.

The whole argument for optics/analog matrix multiplication is that it’s O(n) not O(n^2 or n^3).

Add reverse-compatibility statement e8363a11bf

Update reverse-compatibility statement ff47e7ef14

in bip-powx-low-energy-pow.mediawiki:277 in e8363a11bf outdated

270@@ -239,6 +271,11 @@ Although it is out of the scope of this proposal, the authors strongly recommend
271 
272 A hard fork is not necessarily required for the Bitcoin network to test and eventually implement oPoW. It’s possible to add oPoW as a dual PoW to Bitcoin as a soft fork. Tuning the parameters to ensure that, for example, 99.9% of the security budget would be earned by miners via the SHA256 Hashcash PoW and 0.1% via oPoW would create sufficient incentive for oPoW to be stress-tested and to incentivize the manufacture of dedicated oPoW miners. If this test is successful, the parameters can be tuned continuously over time, e.g. oPoW share doubling at every halving, such that oPoW accounts for some target percentage (up to 100% in a complete SHA256 phase-out).
273 
274+
275+==== Reverse compatibility ====
276+
277+In general, we do not claim reverse compatibility, meaning it may not be possible to fully implement oPoW and maintain compatibility with older versions of the codebase that only perform SHA256 mining.

luke-jr commented at 11:14 pm on November 4, 2021:

“do not claim” “may not” is not clear. This section shouldn’t be about claims, but facts - how is it compatible? how is it not?

It’s probably fine to be uncertain on miner implementations, but absolutes should be known and stated explicitly insofar as the consensus protocol is concerned.

pkvk commented at 5:24 pm on November 25, 2021:

oPoW will not be reverse compatible

luke-jr commented at 5:37 pm on November 25, 2021:

Ok, please say so explicitly in the BIP :)

pkvk commented at 6:50 pm on November 25, 2021:

Sure https://github.com/bitcoin/bips/pull/1126/commits/ff47e7ef144224dbd94c6c045f7ca1bffa04e98a ;)

JeremyRubin commented at 6:26 pm on November 25, 2021: contributor

i don’t think you’re really hearing my concern. your hardware algorithm is O(n) time for vector times matrix, which should be O(n^2) for n tests. I’m noting that the problem might have a batched form of matrix times matrix which could be sub O(n^2) and you should prove that there is no such speedup.

s4turn commented at 6:05 pm on December 1, 2021: none

Hi Jeremy,

This is a valid concern. In fact, one can do better if one batches using rectangular matrices instead of square matrices. This way as k gets large the exponent of such perform n^k matrix vector multiplications approaches k+1. In particular, for every eps>0, there is a k such that n^k matrix vector products can be performed in time O(n^{(1+eps)*(k+1)}). (One can derive the best known constants from the table on p.2 here: https://arxiv.org/pdf/1708.05622.pdf)

But all of this is a bit immaterial, because almost all fast matrix multiplication algorithms are completely impractical. The big-Oh is hiding constants so huge that they only give speedups on incredibly large inputs. To my knowledge Strassen’s algorithm is the only one of practical import. However, I think dimension 64 will still be too small to give advantage over the naive cubic algorithm. (Also, I’m not sure if Strassen’s method has any bearing on rectangular matrix multiplication.)

I believe that proving a lower bound on the complexity of amortized matrix vector multiplication is well beyond our current techniques. The best lower bounds on the complexity of determining if a formula of length n is satisfiable are something like 4n (and the best upper bound is essentially 2^n, try all inputs). One could potentially hope to prove a lower bound on restricted class of algorithms, but its not clear what this would mean here.

.marshall

luke-jr renamed this:
~~[DRAFT] Durable, Low Energy Bitcoin PoW~~
[DRAFT] BIP 52: Durable, Low Energy Bitcoin PoW
on Dec 15, 2021

luke-jr commented at 9:33 pm on December 15, 2021: member

Assigned BIP number 52. Please rename and check CI for any syntax issues.

BIP 52 assigned 67a6c4dabb

Update README da4eb2fb20

Fix Malformed Author line cc636e6f83

BIP 52: Update Comments-URI 9292e959d0

BIP 52: Trying to fix CI errors abd62086df

BIP 52: Trying to fix CI errors 3a287681a4

pkvk commented at 10:41 pm on December 15, 2021: none

CI issues seemingly resolved

in bip-0052.mediawiki:6 in 3a287681a4 outdated

0@@ -0,0 +1,302 @@
1+<pre>
2+  BIP: 52
3+  Title: Durable, Low Energy Bitcoin PoW
4+  Author: Michael Dubrovsky <mike+bip@powx.org>
5+          Bogdan Penkovsky <bogdan+bip@powx.org>
6+  Discussions-To: <mike+bip@powx.org>

luke-jr commented at 10:47 pm on December 15, 2021:

Is this a mailing list?

“While a BIP is in private discussions (usually during the initial Draft phase), a Discussions-To header will indicate the mailing list or URL where the BIP is being discussed. No Discussions-To header is necessary if the BIP is being discussed privately with the author, or on the bitcoin email mailing lists.”

pkvk commented at 8:53 am on December 16, 2021:

No, it is not.

pkvk commented at 9:01 am on December 16, 2021:

Removed the email from Discussions-To in c689a92

in bip-0052.mediawiki:2 in 3a287681a4 outdated

0@@ -0,0 +1,302 @@
1+<pre>
2+  BIP: 52

luke-jr commented at 10:47 pm on December 15, 2021:

Missing Layer header

0  Layer: Consensus (hard fork)

Note this will affect the first line in the README entry

pkvk commented at 8:53 am on December 16, 2021:

Thank you for clarifications: c689a92e353447ce81e6c50b6243adec0a4f4522

luke-jr changes_requested

BIP 52: Add misssing layer information; remove private email from Discussions-To c689a92e35

pkvk force-pushed on Dec 16, 2021

BIP 52: Fix syntax fecbe1f8a8

luke-jr commented at 6:20 pm on December 17, 2021: member

Looks good - but you still have [DRAFT] in the title of the PR; do you want me to merge it or hold off a bit?

pkvk commented at 7:45 pm on December 17, 2021: none

Yes, merging would be fine. Thank you.

pkvk renamed this:
~~[DRAFT] BIP 52: Durable, Low Energy Bitcoin PoW~~
BIP 52: Durable, Low Energy Bitcoin PoW
on Dec 17, 2021

luke-jr merged this on Dec 17, 2021

luke-jr closed this on Dec 17, 2021

BIP 52: Durable, Low Energy Bitcoin PoW #1126