Protocol Extension: Share Accounting + Accountability

[plebhash]

Double Geometric Method

The in-depth description can be found at Meni Rosenfeld, 2011, Analysis of Bitcoin Pooled Mining Reward
Systems (chapter 5.1, page 18)

cc @marathon-gary @Fi3 @lorbax @GitGab19 @pavlenex

[xraid]

T.I.D.E.S.
Transparent Index of Distinct Extended Shares
A Fair Bitcoin Mining Pool Reward System

https://ocean.xyz/docs/tides

[Fi3]

Below a first sketch of what such extension is and how it could work:

Pool accountability system

Intro

Provide a way for a miner to verify that the pool is calculating the payouts correctly. This
is an SV2 extension (it reuse data format, framing encryption and authentication). For sake of
simplicity, only centralized pool are supported (for now). Payouts method considered are:

1. PPLNS
   This seem to be the best choice ...

2. FPPS
   A miner mining with FPPS do not need such a system to verify that the pool is not cheating. A
   miner only need to keep track of the accepted shares, since each share already have a value she can
   calculate how much is her reward. Btw, just adding a single message to this extension, will enable
   monitoring the miner reward. This message, sent by the pool and received by the miner, will
   contain the value of a share for the next period. It could make sense to support FPPS monitoring in
   this extension.

3. RPPLNS
   Have been discarded cause, not in order of importance: (1) no one is using it (2) at a first look it
   seems to be susceptible to attacks (3) it make the implementation of the extension more difficult
   since we also need a way to negotiate a random value between all the miners and the pool. Maybe we can
   just use the block hash but since (1) and (2) we didn't explore it further.

4. DOUBLE GEOMETRIC
   @lorbax is looking into it.

How it could work

1. The pool broadcast each valid share received to every miner.
2. A miner verifies that the share that she provided are broadcasted by the pool.
3. A share is composed by nonce, extranonce, timestamp, version, reference to the job,
   share weight (see point 6) and target.
4. The pool keep all the declared jobs (jobs contain txs id).
5. The pool keep all the transactions for the aforementioned declared job.
6. It exist a function that weights a share based on the associated job, (so share with the same
   target do not have the same reward if the associated job pays different txs fees).
7. Given all the above a miner can verify how much should be paid for the provided shares with
   the following algorithm:

Verification

1. The miner take n shares at random positions (from the shares broadcasted by the pool - the miner's
   shares) (with n derived by a trust threshold).
2. For each share the miner:
   • If the miner do not have the declared job for that share, she require it from the pool.
   • Request the tx data for all the missing txs.
   • Verifies that the target of the share is correct.
   • Verifies that the share weight is correct (this point must be expanded since a function
     that calculates the weight will likely need to know the MAX and MIN fees for the declared
     jobs within the PPLNS window, and we don't want to trust the pool for that; there
     are several possible solution).

Share ordering

To calculate the payout, the order in which shares are arranged (share1, share2, etc.) is important.

The pool cannot mess up the order because it is broadcasting every valid share. If a miner goes
offline for some time and needs to fetch shares produced when she was offline, she don’t need to
worry about the order since she did not produce any shares while offline.

[mcelrath]

1. All miners won't have all info about all shares (because it's bandwidth-prohibitive)
2. Verifying a random sample doesn't allow you to verify the sum. It only takes one bad share to modify the sum. I guess you're just verifying the block template there but not auditing the total number of shares? That's still valuable but let's be clear about what's being validated. Spot-checking templates vs. auditing the share sums.
3. How do miners fetch shares/templates from other miners? Presumably the pool would have to coordinate this, which would allow them to verify only non-cheating shares. (So it must be P2P instead)

(1) is solved by using sub-pools where a subset of miners validate each other's shares and have complete knowledge of all shares within their sub-pool. It does imply that miners have direct P2P connections to other miners in their sub-pool to transmit block templates and shares.

(This approach is asymptotically approaching the Braidpool design...)

[Fi3]

1. it is? for sure do not scale well but with last system proposed we have ~8 bytes shares
2. is true that it only take a bad share to modify the sum, but is a non sense for the pool to add few bad share. It will earn nothing, and can have a big reputational impact
3. I dont' get the point. In particular can you explain better this part:

which would allow them to verify only non-cheating shares.

[mcelrath]

1. A "share" is a weak block, meaning at a minimum it's the 80 byte block header + coinbase, but technically should include validation of an entire weak-bitcoin block. Sure you can encode it in 8 bytes but this is a trusted operation. When we're talking about auditing you shouldn't trust anyone.
2. The pool adds a bad share with a negative value to make the hashrate look lower than it is, allowing them to pay out less and keep more revenue.
3. Does the pool tell miners which shares to verify? Do they determine it on their own? How do they get the data? I don't know how to make the question more clear...

[Fi3]

1. we don't trust this is the reason why you randomly verify shares
2. you as a miner know how many share you have, so if the pool do that you spot it immediately, you don't even need to verify shares
3. (a) no the miner select a random sample from all the shares and verify them; (b) yes; (c) the data is provided by the pool

• pool publish every produced share
• miner see that pool is publishing shares that the miner itself is mining
• miner select a random sample from the shares published by the pool and verify it

That's it. I don't understand what is not clear? Or what are the downside of it other then scale linearly with number of shares (if there is another way to do it without this issue I'm the first one that want to use it)

[TheBlueMatt]

If we use a proof of reserve style merkle tree, where the pool just update the root every time it
receive a share and publish it, a miner can see that produced shares are in the tree but this is
useless, since he can not verify total hash rate of the pool.

Right, so this is not what I was proposing. I was proposing, instead, when the pool does payouts (which they do in batches, eg once an hour for PPS or once every block for PPLNS), they build a full merkle tree of all shares received during that batch which they use for payouts. Users who submitted shares (which the pool signed off on at submit-time) can validate that their shares are all present in the merkle tree and then they can pick a random subset of the rest of the shares in the merkle tree and fetch those, validating them.

The pool cannot cheat materially here because each leaf of the merkle tree is one share, with some fixed or maximum value (ie the pool cannot inflate the total share value by adding a lot of value to a single share because each share either has some fixed value for PPS or the pool places some maximum value on each PPLNS share, which is generally important for PPLNS in custom-work-selection pools because not all work is going to be fully validated to ensure the miner isnt trying to inflate the claimed fees on a share).

Of course this scheme is totally equivalent to "publish al shares" if the miner decides to fetch and validate everything, but the merkle tree means a miner does not to have to fetch very much to have a very high level of confidence that they'd catch cheating if any were to occur.

Indeed, however, to validate a share, a miner needs to not only fetch the full block header and coinbase transaction the share was mined for (to ensure its paying out to the pool) but also may need to fetch the full transaction set and ensure they're valid bitcoin transactions mined on the right block hash to ensure no fee inflation occurs (you may be able to get away with just checking that your own block templates were pretty close to the mean share value the pool publishes, but if they differ you'll need to validate the block templates themselves).

[plebhash]

I have a dumb question from a theoretical perspective. I've been reading the 2011 Rosenfeld paper linked on the top of this Discussion.

The paper seems to set the definition of a share around a fixed difficulty target, which is the minimum possible value (1).

To determine the amount of work done for the pool, users find and submit shares, hashes of a block header which are low enough to have made a block if the difficulty was 1.

The paper goes on to explain multiple payout schemes based on this definition, including the most popular ones used in the industry nowadays (PPS, PPLNS). All those explanations seem to be based on this definition of share that's actually based on a minimum difficulty.

However, that doesn't seem sustainable. Maybe at the time when the paper was written (2011), it was ok for multiple miners to be sending shares of difficulty 1 from their CPUs and GPUs to a pool. But nowadays, with ASIC farms, this would basically be a DDoS attack against the pool, because each miner would be submitting an astronomically high number of shares per second.

Also, the SRI Proxy implementations perform a difficulty adjustment algorithm for each miner, so that they only submit shares above an optimal difficulty threshold.

So my question is: how do payout schemes like PPLNS take this per-miner difficulty variability into account?
E.g.: A share submitted under a higher difficulty must be valued more than a share submitted under a lower difficulty.

[average-gary]

Share Acceptance
Proofs that are valid and accepted by the pool software are added to the top of the share log in the order they are received. Each proof counts as a number of shares in the share log equal to the proof’s target difficulty. This means the share log is effectively a measure of the number of hashes the miner has done for the pool.

https://ocean.xyz/docs/tides
as an example.

[plebhash]

thanks @marathon-gary , but I guess my question is more on the context of the Rosenfeld paper (and the fact that @Fi3 and @lorban mentioned this paper as a reference for the Double Geometric Method)

what confused me is the fact that Rosenfeld fixed the difficulty at 1 on his definition of share, and then goes on to derive concepts like PPLNS and Double Geometric Method on top of that definition.

I guess I just want to make sure we are not overlooking this detail while we use the Rosenfeld paper as a reference, because SRI definitely doesn't treat every share as if their difficulty was 1

---

am I making sense here? @TheBlueMatt @Fi3 @lorban

[GitGab19]

I think that the rights answer to this is explained at chapter 7.5 of Rosenfeld paper called Variable difficulty shares.

"So far we have assumed that participants submit shares which match the hash target of difficulty 1. This choice is completely arbitrary – for any value d, hash targets corresponding to difficulty d can be used as shares. Using shares of higher difficulty reduce server load, but increase share-based variance.
Every method discussed can be trivially adapted to using a different share difficulty. The only requirement is that wherever p = 1/D is used, the value p′ = d/D is used instead, representing the probability that a share will be a valid block. Also, in some of the analysis the value D′ = D/d = 1/p′ takes the role of D."

[Fi3]

yep you can generalize it, I guess he took 1 cause it make everything nicer

[plebhash]

aaah ok, I guess I should have read the entire paper all the way through chapter 7 🙈

thanks!

[mcelrath]

This proposal is kind-of halfway between SV2 and Braidpool. It can't enforce payouts but could detect bad pools. As such here are a few thoughts from my learnings about Braidpool:

You need a consensus system on the database of shares. If one miner misses one share submission, it looks to him like the pool is cheating, and without consensus you can't prove fraud. There are many ways to do this but you'll have to select one to ensure that all miners auditing the shares receive all shares. The DAG of Braidpool isn't the only way to do this, you could use another BFT replicated database, but it's a complicated topic, and bandwidth requirements are considerable as the share target difficulty gets smaller.

I proposed "sub-pools" in part to address this bandwidth problem. The speed (block rate) at which we can run the DAG is fundamentally given by the latency of the network (as measured by diamond graphs and other higher order DAG structures) but ultimately we have no control over that. The "natural fastest speed" we can run the DAG is around 1000x faster than bitcoin. (Sub-second share blocks) Many networks achieve this in practice including Kaspa, Avalanche, and some asynchronous BFT databases. But a 1000x more shares than blocks isn't really fast enough for a centralized pool, especially with individual device monitoring. Estimates are that there are around 6,000,000 individual mining devices on the network, so we need at least another factor of 1000 in order to get one share from each device per bitcoin block, and you probably want even more than that.

The idea of sub-pools is to have two levels of accounting, one at the 1000 shares/block rate, and miners for whom that isn't fast enough join a sub-pool, that rolls up into a single share in the parent pool. In the case of SV2 you might call this sub-accounting since there would only be one centralized pool here, you wouldn't actually be creating new pools but just dividing up the accounting responsibility. There can be several sub-pools, and sub-sub pools. Thus the smallest miners using a sub-sub pool would need to audit 3 levels of share accounting (and 3x bandwidth), instead of everyone needing to audit all shares of the smallest miners (which is multiplicatively more bandwidth). Bandwidth is saved by not auditing sub-pools you're not a part of.

Of course this factor of 1000 is decided by considerations that SV2 may not care about, and fundamentally this is a logarithmic tree of sub-pools. You could choose a smaller branching factor based on your considerations, with more depth in sub-sub-sub pools instead. For instance, optimize to minimize bandwidth while having "enough" miners in each sub-pools to ensure effective auditing.

This could be a pretty interesting way to collaborate too. :-D

[Fi3]

I like the idea of sub-accounting. About the consensus system I want to start with something simpler that we can implement in a reasonable time. I think that having the pool (or the accounting server) send every share is a good point of start, as what we care most is pool not creating "fake" shares inflating the real hash rate of the pool. I didn't think too much at miners missing share submission as I assume miner are well connected while mining, not sure how we can model share submission miss for miners do you have any insight here?

I still have to thing about what proposed @TheBlueMatt regarding the merkle tree of shares, if we really can remove the need for miner of downloading every share produced, we can have fatter share and maybe put in there a reference to the last share, and have a block chain of shares?

[mcelrath]

You can't do accounting if you don't have all the data. You can't have all the data if you don't have a consensus system. There is no "simpler" shortcut here, there's only a broken one.

[average-gary]

How does the consensus system know if a miner is missing a share? Is the miner required to be an active participant in the consensus, aside from creating PoW and submitting a valid share to the pool?

[mcelrath]

@marathon-gary that's kind of the definition of "consensus". It ensures that all miners receive all shares. In the case of a DAG, each share commits to parent shares. For any given "share tip" you can walk up the DAG through the parents to see that you have them all.

Other algorithms achieve the same, usually by some kind of leader election.

[mcelrath]

I think there's a simpler way to do this. In the above Merkle Tree proposal, the pool can simply omit some shares from its Merkle tree, possibly through private agreement with a miner. HOWEVER it would still be an improvement to prove to the miner that his shares were included. This can be done automatically by the StratumV2 software, which substantially improves the auditing over historical pools (I think Slush used to do this) which required the miner to spot-check. Herein a miner is only verifying his own shares.

What the pool needs to do is create a cryptographic accumulator of shares, along with a sum rule that adds up the shares and ensures that there are no negative entries, and publish the root of this accumulator. This is basically a Merkle Sum Tree, but since you don't really want to send the shares of all miners to all other miners, you can make a ZKP instead. I've proposed using CurveTrees for such things, which can use the Bulletproof ZK system to make (and accumulate) arbitrary proofs about the data in the accumulator.

The difficulty for this particular application will be proving that the shares in the accumulator are valid. You need to validate a bitcoin header in ZK, extract the coinbase payout to the pool, and then apply the sum rule to the coinbase payouts. It can be done with CurveTrees and bulletproofs. It might be interesting to see if the Starkware guys have any interest in this... if the level of ZK-fu among StratumV2 devs is low...

Done correctly, this provides a lower bound on the hashrate of the pool. (Assuming the bitcoin header can be validated properly, and it's impossible to put "fake" hashrate into the accumulator). It can't provide an upper bound because as mentioned the pool can just omit some hashrate and you'll never know.

[Fi3]

Not sure why we want a lower bound, maybe I'm missing something obvious.

[mcelrath]

A lower bound is all you can get. Because you can't know or prove that the pool excluded data.

[Fi3]

yep I was tired I mixed upper and lower bound in my head

[Fi3]

@mcelrath
My main concern with it are the resource needed in order to create and verify proofs for such a system.

Is important to note that each share pay respectively on how much fees there are in the jobs that the share is solving. That means that if we do not verify that the job + share lead to a valid block, we give a big incentive to miner to mine invalid jobs that pay more fees.

So, if we don't want to have an system that scale linearly with number of shares in the register O(n) , like the one that I proposed above, we must verify the validity of each job inside our ZKP circuit.

Now let's say that we have a register that contains 3M shares, 100 jobs, 10K transactions, and that we want to know something like that:

in the register I have (1M shares with target T and fees F, 1M shares with target T and fees G, 1M shares with target Z and fees F)

I need a prover that as input take the register and an UTXO set (let's say 10GB). The prover must at least:

1. verify that each txs in the register spend an output that is in the UTXO set
2. apply script to each txs in register and verify that is valid
3. for each job in the register verify that is a valid job (with the right share can be transformed in a block that is accepted by the bitcoin network). If I don't do that I give an incentive to miner to create jobs that have more transaction and pay more fee than possible.
4. for each job extract the fee payed
5. hash each share

Can you give a rough estimation of cpu time + ram needed to create such a proof?

[mcelrath]

There are benchmarks of the CurveTrees algorithm in their paper and they can be reproduced using their github code. It's quite fast.

As to the additional proofs necessary it depends on the implementation.

The Starkware guys have done this already for bitcoin headers, and have a demo that is fast enough to verify the entire blockchain in a couple seconds. Here's the code. However they use a different ZKP system. Their system could be adapted instead of CurveTrees/Bulletproofs (and has the advantage that more of the work is already done...)

I wasn't able to find anyone who has implemented verifying a bitcoin block header using Bulletproofs.

[EthnTuttle]

https://delvingbitcoin.org/t/ecash-tides-using-cashu-and-stratum-v2/870

[lorbax]

I spent the weekend investigating the Double Geometric Method. With a score-based payout method, every time that a share S is sent to the pool, then score of the miner that produced the share has his score increased by (r^n)pB, where
r is the ratio of the score
n is the number of shares received by the pool before S
p is the probability that a share is a block
B is the block reward.
If some powers of r are missing, these will be added to the variable fee of the pool. So even with DGM it is important that the miners can recognizes if the pool is producing fake shares.

DGM seems very interesting, because there is no need to set a time-window for memorizing shares as with PPLNS. Also, there are some variables that can be adjusted in order to reduce pool-based variance and share-based variance. On the other hand, I couldn't see that with DGM is not possible to perform some pool-hopping based on difficulty adjustments (this is basically because I had issue figuring out why the expected payout per share does not depend on difficulty, I also opened
this question on stack exhange).

[mcelrath]

Can you clarify:

1. How you you calculate r ratio of the score: a ratio with respect to what?
2. n is the number of shares received: within what time window? Since the last block received by the pool, or within some PPLNS-like epoch? Is this the number of shares received from the same miner, or all shares from all miners?
3. p probability that S is a block: how do you calculate this probability? All shares should be valid blocks so this should be 100%? I don't see any way to assign probability, unless this is some kind of latency measurement? In Braidpool we could calculate a latency-based probability by looking at the structure of the DAG, but in a centralized pool this is a trusted operation ("trust me, this is when the pool received the share"). This is why the Braidpool spec commits to high resolution timestamps in shares - the block time is not high enough resolution and is rolled by some mining hardware, in addition to being falsifiable within +/- 2 hours.

Latency games are pretty serious and a centralizing force, it's a main reason for the downfall of P2Pool. As such I've proposed that all shares not receive a latency-based score within Braidpool, up to some maximum latency. (e.g. if a share is delayed by 10 minutes, it can't be a Bitcoin block). In practice we will have to discard shares with a latency more than about 5-10s. This window will be dynamic and based on the concept of a cohort that I've previously described. We will still include them in the DAG and use the DAG structure to measure overall network latency, but they can't be counted as paying shares.

[AlejandroDeLaTorre]

stack exchange link brings up a 404

[lorbax]

@mcelrath, @AlejandroDeLaTorre I have to rewrite the question, but I didn't have time lately, hope to do it soon

[average-gary]

Outline a new role to enable auditing of shares.
stratum-mining/stratum#1052