* [Bitcoin-development] Defeating the block withholding attack
@ 2012-06-03 0:52 Luke-Jr
[not found] ` <CACsn0c=+xrVvGMAkPZffpVhRcAc09RuOW7LeOwi0TOD88VbuqQ@mail.gmail.com>
2012-06-04 1:43 ` [Bitcoin-development] " Peter Vessenes
0 siblings, 2 replies; 8+ messages in thread
From: Luke-Jr @ 2012-06-03 0:52 UTC (permalink / raw)
To: Bitcoin Dev
Analysis, comments, constructive criticism, etc welcome for the following:
==Background==
At present, an attacker can harm a pool by intentionally NOT submitting shares
that are also valid blocks. All pools are vulnerable to this attack, whether
centralized or decentralized and regardless of reward system used. The
attack's effectiveness is proportional to ratio of the attacker's hashrate to
the rest of the pool.
There are obvious solutions that can be used to defeat this attack on
centralized pools. For example, including a secret in the coinbase transaction
that is accepted by the network as a partial preimage proof-of-work. All these
solutions require changes to Bitcoin's proof-of-work acceptance terms, and
since centralized pools can be harmful to the network's security, these rule
changes are not likely to gain enough acceptance among the greater Bitcoin
community.
==Proposed Solution==
Please comment on the viability of this new proof-of-work algorithm, which I
think should be viable for even decentralized pools:
Blocks are accepted at a lower difficulty N (choosable by the pool; eg, the
share difficulty) iff they are submitted with a candidate for the next block
and SHA256(SHA256(NewBlockHash + NextBlockCandidateHash)) meets difficulty M.
The relationship between M and N must be comparable to the normal network
difficulty; details on the specifics of this can be figured out later, ideally
by someone more qualified than me. M and N must be chosen prior to searching
for the block: it should be safe to steal some always-zero bytes from the
prevblock header for this.
This algorithm should guarantee that every share has an equal chance of being
a valid block at the time it is found, and that which ones are actually blocks
cannot be known until the subsequent block is found. Thus, attackers have no
way to identify which shares to withhold even while they have full knowledge
of the shares/blocks themselves.
==Backward Compatibility==
Obviously, this change creates a hard-fork in the blockchain. I propose that
if it solves the block withholding risk, the gain is sufficient that the
community may approve a hard-fork to take place 1-2 years from consensus.
Since mining continues to use a double-SHA256 on a fixed 80 byte header,
existing miners, FPGAs, etc should work unmodified. Poolservers will need to
adapt significantly.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bitcoin-development] Fwd: Defeating the block withholding attack
[not found] ` <CACsn0c=+xrVvGMAkPZffpVhRcAc09RuOW7LeOwi0TOD88VbuqQ@mail.gmail.com>
@ 2012-06-03 3:40 ` Watson Ladd
0 siblings, 0 replies; 8+ messages in thread
From: Watson Ladd @ 2012-06-03 3:40 UTC (permalink / raw)
To: Bitcoin Dev
On Sat, Jun 2, 2012 at 7:52 PM, Luke-Jr <luke@dashjr•org> wrote:
> Analysis, comments, constructive criticism, etc welcome for the following:
>
> ==Background==
> At present, an attacker can harm a pool by intentionally NOT submitting shares
> that are also valid blocks. All pools are vulnerable to this attack, whether
> centralized or decentralized and regardless of reward system used. The
> attack's effectiveness is proportional to ratio of the attacker's hashrate to
> the rest of the pool.
This attack has an obvious signature: getting outworked on the same
block as the pool was trying to verify, and always by the same person.
>
> There are obvious solutions that can be used to defeat this attack on
> centralized pools. For example, including a secret in the coinbase transaction
> that is accepted by the network as a partial preimage proof-of-work. All these
> solutions require changes to Bitcoin's proof-of-work acceptance terms, and
> since centralized pools can be harmful to the network's security, these rule
> changes are not likely to gain enough acceptance among the greater Bitcoin
> community.
>
> ==Proposed Solution==
> Please comment on the viability of this new proof-of-work algorithm, which I
> think should be viable for even decentralized pools:
>
> Blocks are accepted at a lower difficulty N (choosable by the pool; eg, the
> share difficulty) iff they are submitted with a candidate for the next block
> and SHA256(SHA256(NewBlockHash + NextBlockCandidateHash)) meets difficulty M.
> The relationship between M and N must be comparable to the normal network
> difficulty; details on the specifics of this can be figured out later, ideally
> by someone more qualified than me. M and N must be chosen prior to searching
> for the block: it should be safe to steal some always-zero bytes from the
> prevblock header for this.
So the goal is to prevent the attacker double-dipping by submitting
cycles to the pool, which if he
found a correct answer he could submit himself. I don't see how this
does that: if he finds a valid
block he finds a valid block. Only if the operator has a secret is
this prevented.
>
> This algorithm should guarantee that every share has an equal chance of being
> a valid block at the time it is found, and that which ones are actually blocks
> cannot be known until the subsequent block is found. Thus, attackers have no
> way to identify which shares to withhold even while they have full knowledge
> of the shares/blocks themselves.
This further delays the finalization of a transaction. That's not a good thing.
>
> ==Backward Compatibility==
> Obviously, this change creates a hard-fork in the blockchain. I propose that
> if it solves the block withholding risk, the gain is sufficient that the
> community may approve a hard-fork to take place 1-2 years from consensus.
>
> Since mining continues to use a double-SHA256 on a fixed 80 byte header,
> existing miners, FPGAs, etc should work unmodified. Poolservers will need to
> adapt significantly.
>
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
--
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither Liberty nor Safety."
-- Benjamin Franklin
--
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither Liberty nor Safety."
-- Benjamin Franklin
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Defeating the block withholding attack
2012-06-03 0:52 [Bitcoin-development] Defeating the block withholding attack Luke-Jr
[not found] ` <CACsn0c=+xrVvGMAkPZffpVhRcAc09RuOW7LeOwi0TOD88VbuqQ@mail.gmail.com>
@ 2012-06-04 1:43 ` Peter Vessenes
2012-06-04 2:04 ` Luke-Jr
1 sibling, 1 reply; 8+ messages in thread
From: Peter Vessenes @ 2012-06-04 1:43 UTC (permalink / raw)
To: Luke-Jr; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1547 bytes --]
On Sat, Jun 2, 2012 at 8:52 PM, Luke-Jr <luke@dashjr•org> wrote:
> Analysis, comments, constructive criticism, etc welcome for the following:
>
> ==Background==
> At present, an attacker can harm a pool by intentionally NOT submitting
> shares
> that are also valid blocks. All pools are vulnerable to this attack,
> whether
> centralized or decentralized and regardless of reward system used. The
> attack's effectiveness is proportional to ratio of the attacker's hashrate
> to
> the rest of the pool.
>
>
I'm unclear on the economics of this attack; we spent a bit of time talking
about it a few months ago at CoinLab and decided not to worry about it for
right now.
Does it have asymmetric payoff for an attacker, that is, over time does it
pay them more to spend their hashes attacking than just mining?
My gut is that it pays less well than mining, meaning I think this is
likely a small problem in the aggregate, and certainly not something we
should try and fork the blockchain for until there's real pain.
Consider, for instance, whether it pays better than just mining bitcoins
and spending those on 'bonuses' for getting users to switch from a pool you
hate.
Watson, I don't believe the attack signature you mention is a factor here,
since the pool controls the merkle, only that pool will benefit from block
submission. The nonce / coinbase combo is worthless otherwise, and so this
attack is just in brief "get lucky, but don't submit."
So, can anyone enlighten me as to some actual estimates of badness for this
attack?
Peter
[-- Attachment #2: Type: text/html, Size: 2029 bytes --]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Defeating the block withholding attack
2012-06-04 1:43 ` [Bitcoin-development] " Peter Vessenes
@ 2012-06-04 2:04 ` Luke-Jr
2012-06-04 20:49 ` Mike Koss
0 siblings, 1 reply; 8+ messages in thread
From: Luke-Jr @ 2012-06-04 2:04 UTC (permalink / raw)
To: Peter Vessenes; +Cc: Bitcoin Dev
On Monday, June 04, 2012 1:43:42 AM Peter Vessenes wrote:
> Does it have asymmetric payoff for an attacker, that is, over time does it
> pay them more to spend their hashes attacking than just mining?
That depends on the pool's reward scheme. Some complicated forms are capable
of getting "bonus" earnings out of the pool. Under all systems, the attacker
at least gains the "hurt the pool" benefit. Given the frequency of DDoS
attacks on pools, it is clear there are people who will even pay for attacks
that provide no other benefit than harming pools. Under all systems, the
attacker doesn't lose out in any significant way.
> My gut is that it pays less well than mining, meaning I think this is
> likely a small problem in the aggregate, and certainly not something we
> should try and fork the blockchain for until there's real pain.
If we wait until there's real pain, it will be a painful fork. If we plan it
1-2 years out, people have time to upgrade on their own before it breaks.
> Consider, for instance, whether it pays better than just mining bitcoins
> and spending those on 'bonuses' for getting users to switch from a pool you
> hate.
With this attack, attackers can hurt the pool's "luck factor" *and* spend the
bitcoins they earn to bribe users away.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Defeating the block withholding attack
2012-06-04 2:04 ` Luke-Jr
@ 2012-06-04 20:49 ` Mike Koss
2012-06-04 21:05 ` Luke-Jr
0 siblings, 1 reply; 8+ messages in thread
From: Mike Koss @ 2012-06-04 20:49 UTC (permalink / raw)
To: Luke-Jr; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 3770 bytes --]
As I understand the attack, the attacker gets compensated for the shares
they earn, but the pool will be denied any valid blocks found. The
attacker DOES NOT have access to the Bitcoins earned in the unreported
block (only the mining pool has access to the Coinbase address and
transactions in the block).
So it's a zero-net-cost attack for the attacker (but no chance of making a
profit) to hurt the pool operator. The only way to detect such an attack
now is to look for "unlucky" miners; at the current difficulty, you can't
detect this cheat until many millions of shares have been earned w/o a
qualifying block. Since an attacker can also create many fake identities,
they can avoid detection indefinitely by abandoning each account after a
million earned shares.
I don't understand your proposal for fixing this. You would have to come
up with a scheme where:
- The miner can detect a qualifying hash to earn a share.
- Not be able to tell if the hash is for a valid block.
The way I would do this is to have a secret part (not shared with the
miners) of a block that is part of the merkle hash, which is also used in a
secondary hash. Difficulty is then divide into two parts: the first,
solved by the miner (earning a "share" - e.g., 1 in 4 Billion hashes). And
a second, solved by the pool (1 in Difficulty shares). A valid block would
have to exhibit a valid Share Hash AND a valid Pool Hash in order to be
accepted.
This would be a very major change to the Block structure. Given that
attackers do not have direct monetary gain from this attack, I'm not sure
we can justify it at this point.
On Sun, Jun 3, 2012 at 7:04 PM, Luke-Jr <luke@dashjr•org> wrote:
> On Monday, June 04, 2012 1:43:42 AM Peter Vessenes wrote:
> > Does it have asymmetric payoff for an attacker, that is, over time does
> it
> > pay them more to spend their hashes attacking than just mining?
>
> That depends on the pool's reward scheme. Some complicated forms are
> capable
> of getting "bonus" earnings out of the pool. Under all systems, the
> attacker
> at least gains the "hurt the pool" benefit. Given the frequency of DDoS
> attacks on pools, it is clear there are people who will even pay for
> attacks
> that provide no other benefit than harming pools. Under all systems, the
> attacker doesn't lose out in any significant way.
>
> > My gut is that it pays less well than mining, meaning I think this is
> > likely a small problem in the aggregate, and certainly not something we
> > should try and fork the blockchain for until there's real pain.
>
> If we wait until there's real pain, it will be a painful fork. If we plan
> it
> 1-2 years out, people have time to upgrade on their own before it breaks.
>
> > Consider, for instance, whether it pays better than just mining bitcoins
> > and spending those on 'bonuses' for getting users to switch from a pool
> you
> > hate.
>
> With this attack, attackers can hurt the pool's "luck factor" *and* spend
> the
> bitcoins they earn to bribe users away.
>
>
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
--
Mike Koss
CTO, CoinLab
(425) 246-7701 (m)
A Bitcoin Primer <http://coinlab.com/a-bitcoin-primer.pdf> - What you need
to know about Bitcoins.
[-- Attachment #2: Type: text/html, Size: 4846 bytes --]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Defeating the block withholding attack
2012-06-04 20:49 ` Mike Koss
@ 2012-06-04 21:05 ` Luke-Jr
2012-06-05 0:00 ` Mike Koss
0 siblings, 1 reply; 8+ messages in thread
From: Luke-Jr @ 2012-06-04 21:05 UTC (permalink / raw)
To: Mike Koss; +Cc: Bitcoin Dev
On Monday, June 04, 2012 8:49:48 PM Mike Koss wrote:
> As I understand the attack, the attacker gets compensated for the shares
> they earn, but the pool will be denied any valid blocks found. The
> attacker DOES NOT have access to the Bitcoins earned in the unreported
> block (only the mining pool has access to the Coinbase address and
> transactions in the block).
With decentralized pools, the attacker does have access to the block, and can
potentially submit it to the Bitcoin network directly bypassing the pool if it
benefits them to do so.
> So it's a zero-net-cost attack for the attacker (but no chance of making a
> profit) to hurt the pool operator.
Because of the above, there is a possibility an attacker can make a profit.
> The only way to detect such an attack now is to look for "unlucky" miners;
> at the current difficulty, you can't detect this cheat until many millions
> of shares have been earned w/o a qualifying block. Since an attacker can
> also create many fake identities, they can avoid detection indefinitely by
> abandoning each account after a million earned shares.
There are other modes of detection, but nobody has bothered to implement them
since attackers can easily do a simple workaround in an arms race.
> I don't understand your proposal for fixing this. You would have to come
> up with a scheme where:
>
> - The miner can detect a qualifying hash to earn a share.
> - Not be able to tell if the hash is for a valid block.
With my proposal, miners can find shares, but won't know if it's a valid block
until the subsequent block is also found (that subsequent block might not end
up being a real block in the big picture).
> The way I would do this is to have a secret part (not shared with the
> miners) of a block that is part of the merkle hash, which is also used in a
> secondary hash. Difficulty is then divide into two parts: the first,
> solved by the miner (earning a "share" - e.g., 1 in 4 Billion hashes). And
> a second, solved by the pool (1 in Difficulty shares). A valid block would
> have to exhibit a valid Share Hash AND a valid Pool Hash in order to be
> accepted.
This only works for centralized pools, which are contrary to the health of the
Bitcoin network. Decentralized pools cannot have a secret.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Defeating the block withholding attack
2012-06-04 21:05 ` Luke-Jr
@ 2012-06-05 0:00 ` Mike Koss
2012-06-05 1:05 ` Luke-Jr
0 siblings, 1 reply; 8+ messages in thread
From: Mike Koss @ 2012-06-05 0:00 UTC (permalink / raw)
To: Luke-Jr; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 3018 bytes --]
I don't understand how your proposal will work for decentralized pools -
can you explain it more concretely?
What would the new block header look like?
What is required for a share to to be earned?
What is required for a block to be valid (added to Block Chain)?
I don't think I understand what you mean by NextBlockCandidate. Perhaps a
concrete example using difficulty 1.7 million would be instructive.
On Mon, Jun 4, 2012 at 2:05 PM, Luke-Jr <luke@dashjr•org> wrote:
> On Monday, June 04, 2012 8:49:48 PM Mike Koss wrote:
> > As I understand the attack, the attacker gets compensated for the shares
> > they earn, but the pool will be denied any valid blocks found. The
> > attacker DOES NOT have access to the Bitcoins earned in the unreported
> > block (only the mining pool has access to the Coinbase address and
> > transactions in the block).
>
> With decentralized pools, the attacker does have access to the block, and
> can
> potentially submit it to the Bitcoin network directly bypassing the pool
> if it
> benefits them to do so.
>
> > So it's a zero-net-cost attack for the attacker (but no chance of making
> a
> > profit) to hurt the pool operator.
>
> Because of the above, there is a possibility an attacker can make a profit.
>
> > The only way to detect such an attack now is to look for "unlucky"
> miners;
> > at the current difficulty, you can't detect this cheat until many
> millions
> > of shares have been earned w/o a qualifying block. Since an attacker can
> > also create many fake identities, they can avoid detection indefinitely
> by
> > abandoning each account after a million earned shares.
>
> There are other modes of detection, but nobody has bothered to implement
> them
> since attackers can easily do a simple workaround in an arms race.
>
> > I don't understand your proposal for fixing this. You would have to come
> > up with a scheme where:
> >
> > - The miner can detect a qualifying hash to earn a share.
> > - Not be able to tell if the hash is for a valid block.
>
> With my proposal, miners can find shares, but won't know if it's a valid
> block
> until the subsequent block is also found (that subsequent block might not
> end
> up being a real block in the big picture).
>
> > The way I would do this is to have a secret part (not shared with the
> > miners) of a block that is part of the merkle hash, which is also used
> in a
> > secondary hash. Difficulty is then divide into two parts: the first,
> > solved by the miner (earning a "share" - e.g., 1 in 4 Billion hashes).
> And
> > a second, solved by the pool (1 in Difficulty shares). A valid block
> would
> > have to exhibit a valid Share Hash AND a valid Pool Hash in order to be
> > accepted.
>
> This only works for centralized pools, which are contrary to the health of
> the
> Bitcoin network. Decentralized pools cannot have a secret.
>
--
Mike Koss
CTO, CoinLab
(425) 246-7701 (m)
A Bitcoin Primer <http://coinlab.com/a-bitcoin-primer.pdf> - What you need
to know about Bitcoins.
[-- Attachment #2: Type: text/html, Size: 3825 bytes --]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Defeating the block withholding attack
2012-06-05 0:00 ` Mike Koss
@ 2012-06-05 1:05 ` Luke-Jr
0 siblings, 0 replies; 8+ messages in thread
From: Luke-Jr @ 2012-06-05 1:05 UTC (permalink / raw)
To: Mike Koss; +Cc: Bitcoin Dev
On Tuesday, June 05, 2012 12:00:25 AM Mike Koss wrote:
> I don't understand how your proposal will work for decentralized pools -
> can you explain it more concretely?
>
> What would the new block header look like?
For example (just a draft; in reality, merged mining would probably be
integrated in a hardfork)
4 bytes: Block version number = 2
31 bytes: Hash of the block 2 back, except for the minimum last 8 bits of zero
1 byte : Share difficulty (measured in "zero" bits)
4 bytes: Timestamp
4 bytes: "Bits" (current target in compact format)
4 bytes: Nonce
> What is required for a share to to be earned?
The final <share difficulty> bits (minimum 32) of the block header are zero.
> What is required for a block to be valid (added to Block Chain)?
The hash of this block header, concatenated with a valid share candidate for
the next block header, must hash to a value less than the current target
offset against the share difficulty (this algorithm may need adjustment).
> I don't think I understand what you mean by NextBlockCandidate. Perhaps a
> concrete example using difficulty 1.7 million would be instructive.
The first share becomes a block only after a second share is found that
combined hashes to meet the real difficulty. That second share becomes a block
when a third is found. Etc.
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2012-06-05 1:05 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-06-03 0:52 [Bitcoin-development] Defeating the block withholding attack Luke-Jr
[not found] ` <CACsn0c=+xrVvGMAkPZffpVhRcAc09RuOW7LeOwi0TOD88VbuqQ@mail.gmail.com>
2012-06-03 3:40 ` [Bitcoin-development] Fwd: " Watson Ladd
2012-06-04 1:43 ` [Bitcoin-development] " Peter Vessenes
2012-06-04 2:04 ` Luke-Jr
2012-06-04 20:49 ` Mike Koss
2012-06-04 21:05 ` Luke-Jr
2012-06-05 0:00 ` Mike Koss
2012-06-05 1:05 ` Luke-Jr
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox