New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

low-variance reward PoW #137

Open
nathan-at-least opened this Issue Mar 8, 2015 · 7 comments

Comments

Projects
None yet
3 participants
@nathan-at-least
Contributor

nathan-at-least commented Mar 8, 2015

Low-variance rewards for mining could make the difference between small-time solo miner viability or not.

Suppose the difficulty is such that a given miner expects to win a block within 1 year, and the block reward is R. If they can instead receive R/365 units per day for the same work, this might affect the barrier to entry.

I haven't yet searched for low-variance PoW but @amiller's talk at MITBTC15 alluded to "many high speed low reward blocks", so I guess I should ask him first.

@zookoatleastauthoritycom

This comment has been minimized.

Show comment
Hide comment
@zookoatleastauthoritycom

zookoatleastauthoritycom May 9, 2015

As far as I know, the only way to achieve very low block-times is to use the "GHOST protocol", or descendants thereof, including the Ethereum descendant: #15

We've already closed #15 as "rejected from Zcoin 1.0", and I'm now closing this ticket with the same status.

zookoatleastauthoritycom commented May 9, 2015

As far as I know, the only way to achieve very low block-times is to use the "GHOST protocol", or descendants thereof, including the Ethereum descendant: #15

We've already closed #15 as "rejected from Zcoin 1.0", and I'm now closing this ticket with the same status.

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira May 9, 2015

Contributor

Wait, isn't that conflating low block times with variance in block difficulty? They are not at all the same.

Contributor

daira commented May 9, 2015

Wait, isn't that conflating low block times with variance in block difficulty? They are not at all the same.

@zookoatleastauthoritycom

This comment has been minimized.

Show comment
Hide comment
@zookoatleastauthoritycom

zookoatleastauthoritycom May 9, 2015

I have been thinking of the former -- low block times -- as the main determinant of variance in a miner's expected revenue. What were you thinking of?

zookoatleastauthoritycom commented May 9, 2015

I have been thinking of the former -- low block times -- as the main determinant of variance in a miner's expected revenue. What were you thinking of?

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira May 9, 2015

Contributor

A conventional hashcash-style PoW requires one hash meeting a criterion that has probability 1/m for each trial. Suppose we generalize that to requiring r hashes meeting a criterion that has probability r/m for each trial.

Multiplying the probability by r (i.e. making it r times easier to find a hash) balances out the requirement to have r hashes in terms of the expected amount of work. But how does the distribution of work needed change? Well, the number of unsuccessful trials needed follows a Pascal distribution NB(r; p) where p = 1 - r/m.

(See https://en.wikipedia.org/wiki/Negative_binomial_distribution#Waiting_time_in_a_Bernoulli_process ; note that a "failure" as described there corresponds to a successful trial in our case, which is why we have p = 1 - r/m.)

As a sanity check, the expected total number of trials needed should be independent of r. The mean of the Pascal distribution is

p*r / (1-p) = (1 - r/m)*r / (r/m)
            = (1 - r/m)*m
            = m - r,

and so the expected total number of trials is m (since there are always r successful trials), which is indeed independent of r.

However, the variance of the Pascal distribution is

p*r / (1-p)^2 = (m - r) * m/r
              = m^2/r - m

and so by increasing r, we reduce the variance (which is also in accord with intuition).

Contributor

daira commented May 9, 2015

A conventional hashcash-style PoW requires one hash meeting a criterion that has probability 1/m for each trial. Suppose we generalize that to requiring r hashes meeting a criterion that has probability r/m for each trial.

Multiplying the probability by r (i.e. making it r times easier to find a hash) balances out the requirement to have r hashes in terms of the expected amount of work. But how does the distribution of work needed change? Well, the number of unsuccessful trials needed follows a Pascal distribution NB(r; p) where p = 1 - r/m.

(See https://en.wikipedia.org/wiki/Negative_binomial_distribution#Waiting_time_in_a_Bernoulli_process ; note that a "failure" as described there corresponds to a successful trial in our case, which is why we have p = 1 - r/m.)

As a sanity check, the expected total number of trials needed should be independent of r. The mean of the Pascal distribution is

p*r / (1-p) = (1 - r/m)*r / (r/m)
            = (1 - r/m)*m
            = m - r,

and so the expected total number of trials is m (since there are always r successful trials), which is indeed independent of r.

However, the variance of the Pascal distribution is

p*r / (1-p)^2 = (m - r) * m/r
              = m^2/r - m

and so by increasing r, we reduce the variance (which is also in accord with intuition).

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira May 9, 2015

Contributor

Note that the protocol above lends itself very easily to outsourcing, which is not what we want. I'm putting it forward as a thought experiment proving that it is possible to change the variance of required work for a block, independently of the expected work for a block.

Contributor

daira commented May 9, 2015

Note that the protocol above lends itself very easily to outsourcing, which is not what we want. I'm putting it forward as a thought experiment proving that it is possible to change the variance of required work for a block, independently of the expected work for a block.

@daira daira reopened this May 9, 2015

@nathan-at-least

This comment has been minimized.

Show comment
Hide comment
@nathan-at-least

nathan-at-least May 20, 2015

Contributor

I'm very intrigued by this. It's still over the line for my gut reaction of feature conservatism, but it's certainly in my giant pool of intriguing potential features for "NextGen Coin". ;-)

So I advocate closing this at least as post-1.0 feature.

What about protocol upgrade path? I suppose we could think of this as a distinct PoW and then we use any PoW upgrade path, but is there any trick or shortcut? I ask because if we can launch with as few changes as possible, but then upgrade later to a low-variance system, that may be valuable. Actually, if that's possible for sha256d then the same upgrade could occur for Bitcoin.

Contributor

nathan-at-least commented May 20, 2015

I'm very intrigued by this. It's still over the line for my gut reaction of feature conservatism, but it's certainly in my giant pool of intriguing potential features for "NextGen Coin". ;-)

So I advocate closing this at least as post-1.0 feature.

What about protocol upgrade path? I suppose we could think of this as a distinct PoW and then we use any PoW upgrade path, but is there any trick or shortcut? I ask because if we can launch with as few changes as possible, but then upgrade later to a low-variance system, that may be valuable. Actually, if that's possible for sha256d then the same upgrade could occur for Bitcoin.

@zookoatleastauthoritycom

This comment has been minimized.

Show comment
Hide comment
@zookoatleastauthoritycom

zookoatleastauthoritycom May 20, 2015

Agreed. Let's leave this tagged with "rejected from Zcoin 1.0" and with "potential post-1.0 features".

zookoatleastauthoritycom commented May 20, 2015

Agreed. Let's leave this tagged with "rejected from Zcoin 1.0" and with "potential post-1.0 features".

@daira daira added this to the Rejected from 1.0 milestone Aug 20, 2015

@daira daira changed the title from Is low-variance reward PoW possible? to low-variance reward PoW Aug 20, 2015

@daira daira added research and removed question labels Aug 20, 2015

ebfull pushed a commit that referenced this issue Nov 4, 2015

Squashed 'src/secp256k1/' changes from b0210a9..bccaf86
bccaf86 Merge pull request #150
2a53a47 Merge pull request #151
5f5a31f Merge pull request #149
3907277 Merge pull request #142
a3e0611 Enable tests in x86 travis builds
45da235 x86 builder
8bb0e93 Merge pull request #155
971fe81 build: fix openssl detection for cross builds
f22d73e Explicitly access %0..%2 as 64-bit so we use the right registers for x32 ABI
e66d4d6 Avoid the stack in assembly and use explicit registers
cf7b2b4 Fix ECDSA message hashes to 32 bytes
056ad31 Really compile with -O3 by default
74ad63a Merge pull request #146
9000458 Merge pull request #145
1f46b00 build: fix __builtin_expect detection for clang
aaba2e0 Merge pull request #136
8a0775c Merge pull request #144
ee1eaa7 Merge pull request #141
c88e2b8 Compile with -O3 by default
6558a26 Make the benchmarks print out stats
000bdf6 Rename bench_verify to bench_recovery
7c6fed2 Add a few more additional tests.
992e03b travis: add clang to the test matrix
b43b79a Merge pull request #143
e06a924 Include time.h header for time().
8d11164 Add some additional tests.
3545627 Merge pull request #118
6a9901e Merge pull request #137
376b28b Merge pull request #128
1728806 Merge pull request #138
a5759c5 Check return value of malloc
39bd94d Variable time normalize
ad86bdf Merge pull request #140
54b768c Another redundant secp256k1_fe_normalize
69dcaab Merge pull request #139
1c29f2e Remove redundant secp256k1_fe_normalize from secp256k1_gej_add_ge_var.
2b9388b Remove unused secp256k1_fe_inv_all
f461b76 Allocate precomputation arrays on the heap
b2c9681 Make {mul,sqr}_inner use the same argument order as {mul,sqr}
6793505 Convert YASM code into inline assembly
f048615 Rewrite field assembly to match the C version
3ce74b1 Tweak precomputed table size for G

git-subtree-dir: src/secp256k1
git-subtree-split: bccaf86caa9c44166e5a66600b742c516e03c3f0

@daira daira removed the mining label Apr 8, 2016

@daira daira removed this from the DEPRECATED - Rejected from 1.0 milestone Sep 30, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment