Fastest-possible PoW via Simple DAG

[zawy]

@ajtowns

I think it would be interesting to analyse this both as a difficulty adjustment for a standalone consensus system [and for Braidpool]

This is what I’m doing. Braidpool’s specifics aren’t on my mind yet.

@ajtowns

With the same latency applying to a global braidpool, but an expected block rate of 100 blocks per ten minutes (10% hashrate at 1/1000th of the difficulty), then the expected “orphan” rate is about 4%. Conversely, if you target an expected “orphan” rate of 44%, with 10% hashrate, that means beads are 14,500 times easier than blocks, rather than 1000 times easier?

Nb/Nc = 2.42 (approx parents = 1.44) results in solvetimes 2.9x mean latency if latency varies randomly from 0 to 2x the mean. It’s independent of hashrate. It targets a solvetime in units of latency, but affected by latency distribution. So if mean latency in a Braidpool = 0.5 seconds, block time is 1.45 s, 417 blocks in 600 s. At 10% hashrate, that’s 4,000x easier.

Using 1-e^(-0.5/1.45), I get a 29.2% orphan rate for Nb/Nc = 2.42 and a uniformly random latency variation around that mean. This equation for orphan rate is approximate. There’s a paper from way back that derives something precise. Looking at it another way, 1/2.42 is the fraction of blocks without any sibling according to any parents or children. If half the remaining 1.42 blocks would have been orphaned then 0.71/2.42 = 29.3% orphan rate.

@mcelrath

The above idea is contrary to Zawy’s suggestion to orphan high latency beads, I want to include them but not pay them.

To me, “not paying them” = orphaning, whether or not they’re included in the DAA calculation.

@ajtowns

I think/conjecture the look-back/latency constraints are probably critical for this approach’s ability to come to consensus between subsets of hashrate with very different latency properties – the 200:1 latency ratio I suggested would (I think) make it difficult for the latest beads from the two groups to have sufficiently common ancestry that they get merged; whereas I’d expect a 2:1 latency ratio to be more-or-less fine.

The Nb/Nc DAA doesn’t seem to have any problem with widely-varying latency. For example, if 5% have 200x longer latency, the solvetime per latency is still in the 2 to 3 range. The Nb/Nc DAA is pretty incredible at how well it handles topology and random variations in latency.

@mcelrath

I’m fairly skeptical of using graph structure alone and the DAA here to handle high latency. High latency is already observed and accounted for using the Nc/Nb method (because high latency generates large cohorts). I don’t want to create incentives for miners to do anything other than naming all known tips. So, I think we need to pull in another timing measurement to decide whether beads have abnormally high latency or not. Remember that just due to the statistics of the Poisson distribution, large cohorts and excessive grandparents will naturally be generated some calculable fraction of the time, and doesn’t represent a problem for the system or evidence of an attack. Adjusting the difficulty due to these infrequent large naturally-occurring cohorts biases the difficulty algorithm relative to the naive Nb/Nc=2.42 algorithm.

I was adjusting the difficulty based on “parents who were supposed to be grandparents” only because the Parent DAA needed it.

The statistical problem of accidentally not rewarding also applies if you use a hard 5 s limit: there could be a natural network delay and you don’t want to enforce a 5 second limit if half the miners are having that kind of delay, or if they’re unlucky and it’s taking 5 s to find a solution. The only way to determine that you’re not having either problem is to confirm there was a sufficient number of other blocks in that time. This is just a great grandparent check that might be able to be used instead. (The “great grandparent method” is not rewarding a block if he sees a parent that all his siblings see as a great grandparent.) Are the timestamps needed or are both be useful? The time limit check has false positives on slow blocks while the great grandparent method has false positives if they’re too fast.

Using a >= great^4 grandparent rule never has a false positive if latency is a uniform distribution. This is at the 5 s level when median latency = 0.25 s. If 10% of the hashrate has 4x the median, there’s a false positive on 2% of their mined blocks. At 10% with 10x latency, it’s 15%. 10x latency is at 2.5 seconds so they aren’t far from not meeting the 5 s limit. But 0.1% hashrate with 40x latency (10 s) has only 35% of it’s blocks rejected. So a combination of the two methods might be good.