Delivery-date: Wed, 31 Jul 2024 11:02:39 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as permitted sender) client-ip=172.104.61.193;
Date: Thu, 1 Aug 2024 04:00:07 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Luke Dashjr <luke@dashjr.org>
Cc: bitcoindev@googlegroups.com
Subject: Re: [bitcoindev] Mining pools, stratumv2 and oblivious shares
Message-ID: <Zqp7p/j25tJI4zn9@erisian.com.au>
References: <Zp/GADXa8J146Qqn@erisian.com.au>
 <6f7feb2b-2e24-4081-b555-db69f34d308e@dashjr.org>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline
In-Reply-To: <6f7feb2b-2e24-4081-b555-db69f34d308e@dashjr.org>
X-Spam_score: -0.0
X-Spam_bar: /
X-Original-Sender: aj@erisian.com.au
X-Original-Authentication-Results: gmr-mx.google.com;       spf=pass
 (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as
 permitted sender) smtp.mailfrom=aj@erisian.com.au
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.8 (/)

I think "decentralised" isn't quite a specific enough term here;
this scheme requires that the pool has a "trusted coordinator", who
can be relied upon to (a) construct sensible templates for people to
mine against, (b) reveal the secret they included in the template when
a share has enough work to be a valid block, (c) not reveal the secret
prior to work being submitted, ie, don't collaborate with people attacking
the pool.

But pools generally require trusted coordinators anyway:

 a) to hold custody over funds until miner income reaches the on-chain
    payment threshold
 b) to hold the funds prior to paying shares rewards over lightning
 c) to act as a validating proxy so that each participant in the pool doesn't
    have to check that every other share submitted to the pool had valid work

If we want hashpower to be very widely distributed, those coordinators
seem pretty important/essential; it makes for generally low payouts (ie,
rarely reaching the onchain threshold), many payouts (ie, if you don't
want to spam the chain, better pay them via lightning etc), and a lot
of shares to check.

I can see it making sense to have a coordinator-free pool if you have
a high minimum hashrate requirement to be a member, perhaps 0.1%; at
that point some of the members might themselves be pools with a central
coordinator, etc. With at most ~1000 members, though, it's not clear to
me that a pool like that wouldn't be better off doing identity-based
membership and some form of federated governance and just banning
attackers, rather than complex crypto protocols and game theory things.

I think if you wanted to fix the problem for a pool-of-pools that
does have a trusted coordinator, you'd need to do three PoW tests
instead of two: work X from the miner demonstrates a valid pool share,
additional work Y when you add in the pool's secret demonstrates
a valid pool-of-pools share, and additional work Z when you add in
the pool-of-pool's secret demonstrates a valid block. But nodes also
need to calculate each of X, Y and Z and check X+Y+Z matches the chain
difficulty. If you skip out Y, the miners can withhold from the pool;
if you skip out Z, the pool can withhold from the pool-of-pools. Not
really convinced that would be worthwhile.

So I think making things better for pools with coordinators is worthwhile,
anyway, even in an ideal world where there's a successful decentralised
pool. I think this is the case even if the pool does some light KYC: if
you're accepting shares from a mass of "lottery miners" it's probably
easy for an attacker to bypass your KYC via identity theft etc, and
still hurt you.

Conversely, even in the absence of a decentralised pool, I don't think
making it easier for pools that do have a coordinator to prevent block
withholding is a bad thing: we're already in a situation where most
hashpower goes to a few heavily-KYC pools that control the templates
being worked on.  Making it easier to setup a small non-KYC pools that
can compete with these seems a step forward; and even if one of those
pools sees huge success and becomes the new dominant pool, despite it
being easier to compete with that pool, and uses that weight to dictate
what transactions are included in the majority of block templates,
that's not even any worse than what we have now...


Anyway, I spent some time thinking about the problem for decentralised
pools, where you don't have a coordinator and can't/don't keep secrets
from miners/attackers. I did get a bit confused because [0] (expanding
on "Luke-Jr's two-stage target mechanism" from [1]) seems to describe
a very different proposal to the June 2012 description in [2].

[0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-December/012069.html
[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-December/012046.html
[2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2012-June/001506.html

Unfortunately, I don't think approaches like that described in [2]
actually do what we want. My understanding of that proposal is that it
would go something like this:

 * a block header is changed to include:
    - version, nbits, timestamp, prevhash, merkleroot, nonce (as currently)
    - next_version, next_timestamp, next_merkleroot, next_nonce (additional)
   which is the combination of a share of the current block and a share for
   the following block

 * share work is based on (version, nbits, timestamp, prevprevhash,
   merkleroot, nonce) ie, when you're working on a share, you're only
   committing to the grandparent block, not the parent block

 * given a block header, you can check the share work for the current block, and
   the "next" block. both must have sufficient work

 * **additionally**, the hash of the entire block header must have work X

 * the total difficulty of a block is then the share work plus X, which
   must satisfy nbits.

 * (the next block's transaction tree is not expanded as part of consensus
   unless it happens to actually be the next block, though the pool
   members might still verify the details)

In that scenario, miners who want to find a block at height N+1 probably
take three steps:

  a) mine a bunch of shares at height N+1
  b) mine a bunch of shares at height N+2
  c) pair each N+1 share with each N+2 share until they find a pair that
     has work X, where the share work plus X matches the target difficulty

For simplicity, imagine that every block with an odd height is empty
-- otherwise it gets complicated to ensure there aren't double spends
between some blocks at height N+1 and some blocks at height N+2.

Note that once you've found block N+1, you'll have already done most of the
work for step (a) at height N+2.

The problem is that for miners/pools that don't publish their shares
to the world prior to finding a block, larger miners get an advantage:
having found K shares in each of steps (a) and (b), they have K^2 chances
of having a pair that has work X in step (c), and thus a valid block. So
a miner with twice the hashrate has four times the chances of finding
a block in any given time period.

I'd thought of a similar approach, where instead of taking a share for
the current block and a share for the next block, you simply pair two
shares for the current block. That seems a bit simpler, in that you don't
have to worry about conflicting transaction sets, because once a block is
found you simply discard all the existing shares, and you also don't need
to worry about balancing the shares you have in step (a) and (b). But it
still has the same K^2 problem benefiting large miners.

I think in that scenario, the optimal pool size (in one sense, anyway)
is about 70% (sqrt(0.5)?) -- you have h^2/(h^2 + (1-h)^2) odds of getting
the next block, which amounts to about 85%, while the remaining 30%
of hashrate only gets the remaining 15% of blocks. If you both have the
same expenses, and they're running just break-even, then your expenses
are paid by the first 35% of blocks, and the remaining 50% of blocks
that you mine are pure profit. (If you instead accepted everyone into
your pool, everyone would be getting the same profits, encouraging more
people to buy mining hardware, driving up the difficulty; in this case,
anyone who bought hardware would have to join the competing pool, and
given they had the same expenses, would not end up making a profit,
so you're effectively making excess profits by keeping Bitcoin's total
hashrate lower than what it would be with today's system)

But the main issue is that if the dominant pool is "evil" (it's
centralised, censors txs, and charges high fees eg), a small competing
pool starts out with a huge disadvantage -- if the 30% of competing
hashrate was split into two pools of 15% instead, they'd get 4% of blocks
each, eg. That's a much worse situation than today, and I don't think
it's salvageable.

For a decentralised pool, you also have the problem that this only fixes
half the withholding attack -- in the decentralised case, the attacker
can be assumed to know all the shares that have been found so far,
so for all the possible blocks that would include a share found by the
attacker, if the later of the two shares in that block was found by the
attacker, they can simply withhold that share. Depending on how much of
the pool's hashrate belongs to the attacker, that's somewhere above 50%
of the blocks that would include a share from the attacker.

I'd guess you could extend the approach further, so that rather than
a block being made up of 2 shares, you have it be made up of n shares,
so that effectively the additional O(H**N) benefit of getting additional
hashrate outweighs the cost of the last share getting withheld. That's
even worse at hurting small pools, but I think at that point you're
effectively switching from Nakomoto consensus to more of a DAG-chain
design anyway, so perhaps it's fair to design for your "pool" being 100%
of miners.

In some sense I think this is in conflict with the "progress-free" [3]
nature of bitcoin mining. If you want the chance of finding a block to
be proportional to hashrate, you want it to be independent of how much
previous work has been done, but in that case you can't make one share's
chance at being a valid block depend on other shares...

[3] eg https://bitcoin.stackexchange.com/a/107401/30971

So pretty disappointed to conclude that I'm not seeing anywhere here
where progress could usefully be made.


The issue with the "invalid blocks" approach is that if you're not
checking template validity but still rewarding payouts for submitted
shares, then there is a trivial approach to the block withholding attack:
just mine invalid blocks, and don't withhold any of them. At that point
it doesn't matter how clever a scheme you have to make it difficult
to tell which shares will be a valid block; they just submit all of
them, knowing none of them will be a valid block. If you're associating
hashrate with identities, you can still ban them when you find they've
sent an invalid block, but if that's good enough, you can already ban
identities that are fall below some threshold of unlucky-ness.


As far as zero-knowledge proofs making template validation easy goes;
I think that makes sense, but we're a long way off. First, I think you'd
need to have utreexo hashes widely available to get a handle on the utxo
set at all; and second, I think the state of the art is zerosync which
is still in the "parity with `-assumevalid=TIP`" phase, and beyond that
generating proofs is fairly compute intensive, so not something that
you'd want to have as a blocking step in announcing a share to your pool.

Cheers,
aj

On Tue, Jul 23, 2024 at 02:44:46PM -0400, Luke Dashjr wrote:
> Block withholding is already trivial, and annoying to detect. Decentralised
> mining / invalid blocks doesn't increase the risk at all - it only makes it
> easier to detect if done that way.
>
> While it isn't made any worse, fixing it is still a good idea.
> Unfortunately, I think your proposal still requires checking every template,
> and only fixes block withholding for centralised mining. It would risk
> *creating* the very "centralised advantage over decentralised" problem
> you're trying to mitigate.
>
> Given that block withholding is trivial regardless of approach, and there's
> no advantage to taking the invalid-block approach, the risk of invalid
> blocks would stem from buggy nodes or softfork disagreements/lagging
> upgrades. That risk can be largely addressed by spot-checking random
> templates.
>
> Another possibility would be to use zero-knowledge proofs of block validity,
> but I don't know if we're there yet. At that point, I think the hardfork to
> solve the last remaining avenue would be a good idea. (Bonus points if
> someone can think up a way to do it without a centrally-held
> secret/server...)

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/Zqp7p/j25tJI4zn9%40erisian.com.au.