Review of the ASERT DAA proposal

35 722
Avatar for micropresident
4 years ago

Recently, Jonathan Toomim has written a detailed proposal for addressing a significant issue on Bitcoin Cash. That issue has been that "benevolent" miners are losing money relative to profit seeking miners. This is undesirable because Bitcoin is supposed to run on profit motives. If miners who drive the chain forward are not profiting properly, the system is effectively broken.

This problem is also why the current Difficulty Adjustment Algorithm (DAA; the system responsible for ensuring that coin issuance is stable and fair) was put in place relative to the previous Emergency Difficulty Adjustments. Much of the analysis that Toomim presents was done at that time. Toomim’s proposal is that we switch to an algorithm called ASERT.

The proposal’s problem statement correctly points out that the DAA is responsible for this. It also points out that no Difficulty Adjustment Algorithm as currently proposed can entirely fix this problem. This is fundamentally due to a lack of instantaneous price information. This information is only able to be inferred by the behavior of miners, and based on noisy data. The calculation of the DAA must only rely on internal blockchain information, or consensus cannot be reached, and there would also be the problem of trusted oracles. 

Fundamentally, the DAA has two pieces of information about what the current hashrate is: Block times, and Chainwork. Both of these are noisy data sources:

  1. Block time has two sources of error: Miners, for whatever reason, may not update the time of their blocks to be accurate to when they were mined -- this is shown in practice. There is also a potential to manipulate these timestamps in order to affect difficulty and game the algorithm.

  2. Chainwork for a particular block is the sum of the estimated number of hashes required to have produced said block if the entire chain was recreated from scratch. It may be thought of as the blockchain's enthalpy. However, because Chainwork is based on these block hashes, they are necessarily probabilistic. As such, each block's chainwork has some divergence from the actual number of hashes required to produce the block.

As such, the noise in the data introduces a fundamental minimum error. The error in these parameters are independent of any choice in DAA. These errors limit the ability of a DAA to respond to hash that is changing over a period of time that is bounded by a minimum of ten minutes, and increases the more switch miners there are.

However, I believe the simulation that is being used is also fundamentally flawed. As one of the original authors of the simulation that Jonathan used, I believe there are several important flaws that impact the validity of its output.

First, the simulation makes fundamental assumptions about the behavior of greedy miners. These assumptions are likely not valid.  We are currently observing strategic greedy miners that exhibit second order thinking. They can, and are currently, strategically applying their hashrate, and manipulating timestamps, in order to create future changes in the difficulty adjustments.

Additionally, the lead author of the simulation made relative profitability of mining Bitcoin Cash an independent random variable. This assumption makes the calculation of revenue ratio based on current hashrate seem independent of miner behavior. It is not.

Finally, there is no error introduced into the timestamps. There is significant variability in the actual timestamps, and time it takes to produce a block. 

In reality, the greedy miners have a significant impact on the future exchange rate based on their behavior. Because of limitations of 10 minute block times, and a larger response to variations in hashrate, switch mining actually becomes more of a problem, not less. 

Greedy miners, with significant hashrate available, have a large incentive to switch large pools to BCH for brief periods of time, and mine a block and leave. The result will be that the next block will have a significantly increased difficulty, and the block after it having a much reduced difficulty. As a result, selfish mining becomes a natural response to protect profits. If you are a miner taking the much reduced profitability of the next block, it makes rational sense to withhold it and mine an easy block on top.

These scenarios are explicitly not discussed in Jonathan’s proposal, but deferred to the following issues: EMA for BCH (part 2) and Hash Attack Examples github issue threads. However, the fundamental problem here is that the DAA cannot adjust until a block is found. If a block is found quickly, the difficulty will rise substantially, and it cannot be reduced until a new block is found - even if that difficulty increase was due to hash which has left the chain, or by timestamp manipulation.

Interestingly, from the analysis one proposal from ABC (cw-16-sha) for fixing the issue of resonances. It does so by modifying the current DAA (cw-144) to use a randomized window based on the current block hash. This also prevents any resonances from forming within the difficulty targets. From testing in 2017, it also outperforms other algorithms on all attacks at the expense of creating larger block solvetime variability. However, this still does not solve problems associated with switch miners. ABC has not chosen to implement this due to a variety of other factors not considered in Jonathan’s proposal.

One of those factors is that changing the DAA is a significant undertaking, because it does not just require updating the node software, but it also requires updating every SPV wallet in the ecosystem. This is no longer simply a problem for exchanges, and miners, but for every user. It is nearly impossible to ensure that every user gets a notification that they need to update their wallets - and will necessarily involve interrupted service. In 2017, the user base was smaller, and more engaged; this made such a change easier. Also, the magnitude of the profitability issues for benevolent miners were significantly larger than they are now.

As such, changing the DAA should be considered carefully before a change is made. I applaud Jonathan’s effort and thorough analysis of the DAA’s choice. However, I would like to see:

  1. Simulations performed under constant price ratio, so that miner behavior can be better seen.

  2. Add select timestamps based on the probability distribution, so that short term profitability variations show up more often due to random chance.

  3. Faster switching of rational miners. Pools can change chains very quickly, the cost to do so is miniscule. Very small price fluctuations due to solvetimes can dramatically impact profitability.

  4. Better tests for various rational miner behavior.

Finally, and most importantly is there a way to make better data available to the difficulty adjustment algorithm by fundamentally changing the way we think about the problem? The proposal does not consider any alternatives which would fix issues with difficulty adjustment algorithms entirely.

Some of these other options are:

  1. Bobtail

  2. Bounded mining

  3. Real-time targeting (RTT). Where wall clock time impacts what the difficulty accepted will be, and can be soft-forked into the protocol.

  4. Avalanche consensus to determine which block is chosen every 10 minutes.

All of these options have tradeoffs, but they all allow block times to be significantly less variable, and prevent selfish mining, and greedy mining, by ensuring that real-time price data is trustlessly provided to a DAA in a way it can react to quickly.

58
$ 11.99
$ 2.00 from @Cain
$ 2.00 from @Nicknameul
$ 2.00 from @Kyoo
+ 9
Avatar for micropresident
4 years ago

Comments

We are currently observing strategic greedy miners that exhibit second order thinking. They can, and are currently, strategically applying their hashrate, and manipulating timestamps, in order to create future changes in the difficulty adjustments.

I have not seen any evidence of this, and you do not cite any evidence to back up this claim. I believe your claim is false.

You may be thinking of Zander's finding of occasional negative block solvetimes on the blockchain. This does not mean that those timestamps were intentionally manipulated; it could just be that node operators don't have very precisely set system clocks. If this were intentional and malicious behavior, we would expect that these negative solvetimes would be clustered near the legal limit for timestamp manipulation. If this were accidental and non-malicious behavior, we would see these negative solvetimes clustered close to 0, with larger offsets being much rarer than smaller offsets. What we actually see is the latter: almost all negative solvetimes are smaller in magnitude than -20 seconds.

What the simulations show is that second-order thinking is unnecessary to explain the current oscillations. That is, first-order thinking is sufficient to explain the oscillations. You have not shown otherwise, nor have you shown second-order thinking to be present.

$ 1.02
4 years ago

First, the simulation makes fundamental assumptions about the behavior of greedy miners. These assumptions are likely not valid. We are currently observing strategic greedy miners that exhibit second order thinking. They can, and are currently, strategically applying their hashrate, and manipulating timestamps, in order to create future changes in the difficulty adjustments.

As I mentioned elsewhere, there is no evidence showing that miners are exhibiting second-order thinking, and are doing anything other than mining whichever chain is more profitable at the moment.

But even if they were showing second-order thinking, your criticism would be invalid, because the simulation includes scenarios to test the strategic application of hashrate or timestamp manipulation. You just overlooked them.

strategically applying their hashrate

The "pump-osc" scenario will simulate miners adding a large amount of hashrate in bursts every 144 blocks. This scenario also includes a forex price ramp, which (for idiosyncratic technical reasons) limits the simulation to about 5,000 blocks. As in all other scenarios that we've tested, EMA algorithms like asert perform well in this test, and only asert, wtema, lwma, and wt are competitive.

pump-osc (only 5000 blocks)

Algorithm Avg block interval (sec) Avg conf time (sec) Greedy Variable Steady Advantage
aserti1-144 581.03 653.20 0.346% -0.003% -1.321% 1.666%
aserti3-416 548.67 614.24 0.483% 0.013% -1.459% 1.942%
cw-144 597.61 2703.16 1.334% -0.061% -12.116% 13.449%
cw-sha-16 595.84 1128.63 0.421% -0.295% -4.425% 4.846%
d-1 869.02 5598.53 2.084% -0.624% -41.773% 43.858%
dgw3-144 599.68 2879.56 0.838% -0.270% -10.339% 11.176%
k-1 586.42 866.84 0.357% 0.034% -2.538% 2.895%
k-2 616.71 886.14 0.491% 0.018% -2.451% 2.942%
lwma-144 589.16 676.25 0.392% -0.004% -1.405% 1.796%
lwma-576 558.27 646.59 0.573% 0.023% -1.684% 2.257%
meng-1 600.93 2302.79 1.257% -0.002% -11.214% 12.471%
meng-2 619.83 1912.57 1.028% -0.346% -13.465% 14.493%
wt-144 591.08 677.94 0.387% -0.004% -1.402% 1.789%
wtema-144 584.59 668.99 0.386% -0.003% -1.361% 1.746%

manipulating timestamps

As I mentioned in another comment, the dr* and ft100 scenarios test some timestamp manipulation strategies.

$ 1.02
4 years ago

A very informative post indeed

$ 0.00
4 years ago

I did not once use the term "benevolent", but you put the term in quotes while paraphrasing my article. Please don't put things in quotes like that unless it is actually a quote.

$ 0.11
4 years ago

Nowhere did I say you did. Stop assuming bad faith. It's an in-use term for what is going on.

$ 0.00
4 years ago

I do not see substantial evidence from his request about quoting him that he was assuming bad faith on your part. It seemed like a reasonable personal request even if your interpretation of what you intended to say was accurate and a well accepted way of using quotes.

$ 0.20
4 years ago

In this case I think Jonathan is correct. The average person would assume something in quotes is actually a quote. And given your article is primarily a response to Jonathan's post, I feel it comes across as a quote from Jonathan.

$ 0.00
4 years ago

There's no wrong with a quote. I think micropresident evaluate and analyze the final output of your proposal. and think for the possible happenings.

$ 0.00
4 years ago

Additionally, the lead author of the simulation made relative profitability of mining Bitcoin Cash an independent random variable.

No, that is not true. Profitability is based on two things:

  1. The revenue ratio per block
  2. The difficulty of finding a block

The purpose of the DAA is to adjust (2) to follow (1).

The revenue ratio per block is an independent variable.

The relative profitability per hash is a dependent variable.

$ 1.22
4 years ago

The relative profitability is dependent on a random variable, and thus, INDEPENDENT. There is zero indication that the FX is at all reasonably generated.

You should know very well that if you want to measure something in an experiment you hold all variables constant except the one you are wanting to examine. This simulation varies a number of things independently making it nearly worthless.

I gave this same feedback to kyuupichan when this thing was being used, and he refused to change it.

$ 0.00
4 years ago

The relative profitability is dependent on a random variable, and thus, INDEPENDENT.

That is not what the word independent means in statistical and scientific contexts. A dependent variable is something that depends on something else. If variable B is dependent on random variable A, then B is a dependent variable.

https://en.wikipedia.org/wiki/Dependent_and_independent_variables

There is zero indication that the FX is at all reasonably generated.

The FX (foreign exchange rate) is generated exactly the same for all algorithms tested in the simulation. It uses the same random seed value, and gives exactly the same output every single time for a given random seed and parameter set. The only thing that varies is how each DAA responds to that input.

The simulation has a field in the web form for the randomness seed. Every algorithm in a sim run uses the same forex data, generated from the same random seed. If you want different forex data, you just need to change that randomness seed. My published sim results all use the randomness seed "100," which is the default nothing-up-my-sleeves value for the simulation.

You should know very well that if you want to measure something in an experiment you hold all variables constant except the one you are wanting to examine.

Yes, I know that. And that's exactly what I did.

$ 2.00
4 years ago

As such, the noise in the data introduces a fundamental minimum error.

Yes, there is a fundamental minimum error that any DAA will face. But cw-144's error is at least 20x larger than that fundamental minimum error. aserti3-415 gets rid of about 95% of the error present in cw-144.

Because we can't make something perfect, we shouldn't bother with something that's 20x better? I disagree.

$ 1.02
4 years ago

I didn't understand because I'm the newbie of cryptocurrency because of this article I read 2-3 times repeating and that's it I already understand it. Thank you for this😇

$ 0.00
4 years ago

I have no idea if this article is on point, but, I am really happy to see detailed discussions taking place as a means of moving forward (I hope) on fixing the DAA.

$ 1.00
4 years ago

Some of these other options are:

  1. Bobtail

Bobtail is an interesting proposal. However, it's about 10x as much code as a simple DAA change, and completely restructures the header -- that's a very large impact on the BCH ecosystem. And the code hasn't yet been written, and might never be written. Furthermore, Bobtail will work much better with asert than with cw-144. If we're going to do Bobtail, it should be in addition to replacing cw-144.

$ 2.02
4 years ago

Real-time targeting (RTT). Where wall clock time impacts what the difficulty accepted will be, and can be soft-forked into the protocol.

RTTs are not a soft fork. They are a hard fork, just like any other DAA change.

$ 0.01
4 years ago

It looks like you've linked to this paper bounded-time algorithms on cyber-physical systems in e.g. aerospace instead of this UMass paper on bonded mining in cryptocurrency systems. You might want to fix that.

$ 0.01
4 years ago

Article full of information.

$ 0.00
4 years ago

$ 0.00
4 years ago

Some of these other options are:

(4) Avalanche consensus to determine which block is chosen every 10 minutes.

If we get rid of PoW entirely, then we don't need a DAA any longer. But how likely is that to actually happen?

Given that we don't have a formal spec of Avalanche, and that most of the people who were working on Avalanche have moved over to their own coin (AVA), and that most of the concepts of Avalanche that I've seen have still used PoW and still needed a DAA, I would say that this is not very likely to actually happen.

$ 0.02
4 years ago

Great news 👍👍

$ 0.00
4 years ago

This is an interesting article. Nice work

$ 0.00
4 years ago

Finally, there is no error introduced into the timestamps. There is significant variability in the actual timestamps, and time it takes to produce a block.

There are artificial timestamp errors if you check the "ft100" or "dr*" boxes in the simulation. Doing so doesn't change the basic findings, and (at least for the ft100 scenario) increases the advantage of ASERT over cw-144.

FT100

Algorithm Avg block interval (sec) Avg conf time (sec) Greedy Variable Steady Advantage
aserti1-144 600.07 727.26 -0.263% -0.043% -1.030% 0.987%
aserti3-416 600.37 648.21 -0.121% -0.011% -0.426% 0.415%
cw-144 604.82 2223.86 0.462% 0.020% -10.463% 10.925%
cw-sha-16 606.10 1709.81 -0.510% -0.496% -6.883% 6.386%
d-1 691.15 4568.62 1.276% -0.555% -41.743% 43.019%
dgw3-144 604.04 1772.92 -0.053% -0.157% -6.697% 6.644%
k-1 593.52 782.54 0.056% 0.012% -1.426% 1.482%
k-2 633.60 954.31 0.092% 0.014% -1.688% 1.780%
meng-1 606.56 2149.91 0.149% -0.259% -10.480% 10.629%
meng-2 641.44 2802.37 -2.444% -3.526% -23.246% 20.801%

dr50

Algorithm Avg block interval (sec) Avg conf time (sec) Greedy Variable Steady Advantage
aserti1-144 600.08 707.86 -0.001% -0.003% -0.875% 0.874%
aserti3-416 600.40 641.17 -0.014% -0.002% -0.408% 0.406%
cw-144 604.07 1209.65 0.806% 0.152% -6.179% 6.984%
cw-sha-16 602.05 933.66 -0.045% -0.068% -2.895% 2.850%
d-1 652.02 2593.34 1.241% 0.259% -37.113% 38.354%
dgw3-144 604.72 1134.88 0.659% 0.086% -4.810% 5.469%
k-1 592.63 761.10 0.072% 0.036% -1.600% 1.672%
k-2 640.39 920.25 0.196% 0.049% -1.918% 2.115%
meng-1 604.93 1267.50 0.682% 0.115% -6.913% 7.594%
meng-2 621.68 1514.53 0.118% -0.111% -13.592% 13.710%

Default (no timestamp manipulation)

Algorithm Avg block interval (sec) Avg conf time (sec) Greedy Variable Steady Advantage
aserti1-144 600.08 674.97 -0.069% -0.001% -0.659% 0.658%
aserti3-416 600.39 639.02 -0.065% -0.003% -0.387% 0.384%
cw-144 604.09 1381.15 0.812% 0.153% -6.860% 7.672%
cw-sha-16 602.54 1013.36 -0.091% -0.105% -3.208% 3.117%
d-1 670.67 2941.89 1.152% 0.096% -36.555% 37.708%
dgw3-144 604.57 1136.91 0.476% 0.064% -3.810% 4.286%
k-1 593.88 750.61 0.021% 0.024% -1.394% 1.419%
k-2 635.47 912.92 0.172% 0.038% -1.854% 2.027%
meng-1 602.87 1244.91 0.527% 0.095% -5.482% 6.010%
meng-2 616.56 1632.72 0.122% -0.220% -13.133% 13.255%

The above simulations were run at 40k blocks, but otherwise used the default options in the simulation.

$ 1.02
4 years ago

Some of these other options are:

(2) Bounded [sic] mining

Bonded mining is a bad idea. At a fundamental level, bonded mining is a workaround for a broken DAA. It's much better to fix the bug than to add a workaround on top of the bug while leaving the bug still in place.

Bonded mining is a bad idea for many reasons. Here's a few:

  1. It's very complicated. It's about at least 10x as much code and as much work as simply fixing the DAA would be. Nobody has written that code yet. Nobody knows what it would look like. But it's a reasonable guess that it will be ugly.

  2. it simply does not work with low-hashrate miners. The algorithm proposed in the bonded mining paper requires each miner to comprise at least 1% of the hashrate in order to have a decent success rate. This would centralize hashrate. The Bonded Mining paper excuses this by saying: "Smaller miners do not need to be excluded from the system as they can join a larger pool." That's not a good excuse. Pool centralization is itself a problem.

  3. It compromises the ability of miners to remain anonymous. By tying miners to their bonds, miners need to have all of their blocks be linked together. Basically, it forces address reuse. This compromises the censorship-resistance properties of Bitcoin, and makes miners more vulnerable to reprisal, such as in the event of World War 3.

$ 1.02
4 years ago

It's very complicated. It's about 10x as much code

I would estimate it at much higher given the complex protocol and statistical test it foresees.

One should not only count the application code, but also the test code that needs to be developed for such a complex protocol.

$ 1.01
User's avatar freetrader
This user is who they claim to be.
We have manually verified this user via some other channel.
Proof
4 years ago

Just FYI, One of you may have a typo or be discussing a different type of mining: His #2 was "Bounded mining"

Your reply mentioned "Bonded" mining.

$ 0.10
4 years ago

Yes, it's an error on his part. The concept he was looking for (which is one of Amaury's favorites) is bonded mining, as described in this paper. However, Shammah mis-remembered that as "bounded mining." When Shammah tried to find the paper for "bounded mining" (which does not exist), he instead found this automotive/aerospace/medical engineering paper instead, which was using the term "mining" in the sense of "data-mining" not in the sense of "Bitcoin mining."

$ 1.06
4 years ago

Some of these other options are:

(3) Real-time targeting (RTT). Where wall clock time impacts what the difficulty accepted will be, and can be soft-forked into the protocol.

If you want RTT, there's an obvious RTT version of ASERT that can be used. Instead of using the previous block's timestamp for determining difficulty, use the current block template's timestamp.

I'm generally not a fan of RTTs, as they add a lot of potential attack scenarios. As you mentioned elsewhere in your article, it's hard to enumerate all of the attack scenarios.

I'm surprised, therefore, that you propose RTT, which dramatically increases the attack surface in the same article. It's like you're criticizing ASERT for being too conservative and for not being conservative enough in the same article. Make up your mind, which one is it?

There's a second problem with RTTs in addition to the attack surface issue. RTTs will narrow the distribution of block times, which makes it more likely that two sibling blocks will be found within a short time interval. This increases orphan rates, and will reduce the ability of a blockchain like BCH to scale.

$ 0.12
4 years ago

Interestingly, from the analysis one proposal from ABC (cw-16-sha) for fixing the issue of resonances. It does so by modifying the current DAA (cw-144) to use a randomized window based on the current block hash.

I tried it months ago. It gets rid of the resonance, and replaces it with random noise. It's not a very good algorithm. Consequently, I didn't bother to mention it in the article because its performance is so obviously bad. There were a half-dozen other algorithms with poor performance that I also chose not to mention.

Block and confirmation times, and profitability of different mining strategies

Algorithm Avg block interval (sec) Avg conf time (sec) Greedy Variable Steady Advantage
aserti1-144 600.08 674.97 -0.069% -0.001% -0.659% 0.658%
aserti3-416 600.39 639.02 -0.065% -0.003% -0.387% 0.384%
cw-144 604.09 1381.15 0.812% 0.153% -6.860% 7.672%
cw-sha-16 602.54 1013.36 -0.091% -0.105% -3.208% 3.117%
d-1 670.67 2941.89 1.152% 0.096% -36.555% 37.708%
dgw3-144 604.57 1136.91 0.476% 0.064% -3.810% 4.286%
k-1 593.88 750.61 0.021% 0.024% -1.394% 1.419%
k-2 635.47 912.92 0.172% 0.038% -1.854% 2.027%
meng-1 602.87 1244.91 0.527% 0.095% -5.482% 6.010%
meng-2 616.56 1632.72 0.122% -0.220% -13.133% 13.255%
$ 1.02
4 years ago

The random noise is intentional to dissuade calculated behavior. There are always trade offs given the lack of information. And it performs much better than CW-144, and it does perform better in a number of important scenarios. And, it wasn't implemented.

According to your data set k-1 and k-2 perform better. These algorithms are absolutely terrible. That simulator is basically nearly garbage -- and I helped write it. For those wondering, here's the code for those: https://github.com/jtoomim/difficulty/blob/comparator/mining.py#L140-L164

These are the same two algorithms that kyuupichan kept insisting be used.

$ 0.10
4 years ago

The random noise is intentional to dissuade calculated behavior.

Random noise is nearly as exploitable for profit as the oscillations are. It only takes about a second for miners to switch chains between BTC and BCH. They can do that after a block is found and the difficulty has been randomly jittered by cw-sha-16 just fine.

$ 0.11
4 years ago

Yes, k-1 and k-2 perform better than cw-144. But they're not as good as wtema, asert, wt, or lwma in any of the scenarios I tested, so I dropped them from consideration.

These algorithms are absolutely terrible.

But they're better than cw-144 and cw-sha-16 by a large margin; what does that tell you about the status quo?

That simulator is basically nearly garbage -- and I helped write it

Please make your criticisms specific and substantial, and cite evidence for your claims. It's impossible to refute vague claims like "[it's] garbage," and such claims do not belong in scientific or technical discourse.

In any case, if you don't like this simulator, you're welcome to go take a look at zawy12's simulator results instead. It's very different, but it still shows asert to be far superior to cw-144. Or you could look at his results from Nov, 2019, which showed the same thing. Or you could look at the Imperial College results, which showed the same thing.

$ 4.50
4 years ago

Assuming quote marks are best used for quotes as you suggested elsewhere, you imply here that he claims "it's garbage" when that is not exactly what he said. Not a big deal and you do provide the actual quote as well. I hope you guys keep figuring this stuff out, so, I probably should not have mentioned it and risked annoying you guys. I must have been a grammar-nazi in a previous life. Is grammar-nazi P.C. to say these days?

$ 0.00
4 years ago

Thanks for the information

$ 0.00
4 years ago