* [Bitcoin-development] Enforcing inflation rules for SPV clients
@ 2012-06-24 12:45 Mike Hearn
2012-06-24 16:51 ` Stefan Thomas
2012-06-24 18:03 ` Gregory Maxwell
0 siblings, 2 replies; 6+ messages in thread
From: Mike Hearn @ 2012-06-24 12:45 UTC (permalink / raw)
To: Bitcoin Dev
I've been having a discussion with d'aniel from the forums about how
to handle the possibility of a majority-miner conspiracy to raise
inflation, if most economic actors use SPV clients.
Because of how blocks are formatted you cannot check the coinbase of a
transaction without knowing the fees in the block, and the fees can
only be calculated if you have all the input transactions for every
transaction in that block. Because the attack scenario is an attempted
takeover of the economy by miners, attempting to put hints into the
blocks won't work - we have to assume the hardest chain is in fact
wrong according to the rules signed up to by the Bitcoin user.
The most obvious goal for a cartel of miners is to change the
inflation formula, either for purely selfish reasons (they want more
money than can be obtained by fees) or due to coercion by
governments/central banks who still subscribe to the "inflation is
good" idea.
Whilst "good" nodes (still on the old ruleset) won't relay blocks that
violate the rules no matter how hard they are, in a situation where an
SPV client DOES hear about the bad best chain, it would switch to it
automatically. And who knows how the network might look in future -
perhaps most nodes would end up run by miners, or other entities that
upgrade to the new ruleset for other reasons.
d'aniel made a good proposal - having good nodes broadcast
announcements when they detect a rule that breaks the rules, along
with a proof that it did so. Checking the proof might be very
expensive, but it would only have to be done for split points,
limiting the potential for DoS. If a node announces that it has a
weaker chain and that the split point is a rule-breaker, the SPV
client would download the headers for the side chain to verify the
split, then download all the transactions in the split block along
with all their inputs, and the merkle branches linking the inputs to
the associated block headers. In this way the fee can be calculated,
the inflation formula applied and the coinbase value checked.
If the block is indeed found to be a rule-breaker, it'd be blacklisted
and chains from that point forward ignored.
Miners may decide to allow themselves to create money with
non-index-zero transactions to work around this. In that case the good
node can announce that a given tx in the rule-breaker block is
invalid. The SPV node would then challenge nodes announcing the longer
chain to provide the inputs for the bad tx all the way back to a
pre-split coinbase.
Doing these checks would be rather time consuming with huge blocks,
but it's a last resort only. In the absence of bugs, the mere presence
of the mechanism should ensure it never has to be used.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Bitcoin-development] Enforcing inflation rules for SPV clients
2012-06-24 12:45 [Bitcoin-development] Enforcing inflation rules for SPV clients Mike Hearn
@ 2012-06-24 16:51 ` Stefan Thomas
2012-06-25 8:44 ` Mike Hearn
2012-06-24 18:03 ` Gregory Maxwell
1 sibling, 1 reply; 6+ messages in thread
From: Stefan Thomas @ 2012-06-24 16:51 UTC (permalink / raw)
To: bitcoin-development
Very interesting for you to bring this up. I had a similar idea for a
totally different use case. Greg recently pointed out an interesting
dilemma saying that (significantly) larger blocks would lead to
centralization. So I've been working on a design for a decentralized
pool that can handle gigabyte sized blocks by splitting up the work
among its members.
At the moment P2Pool nodes all verify all transactions in all blocks.
But it seems feasible to create a system where miners who have over the
last 10000 blocks contributed to the pool's proof-of-work are allocated
a proportional piece of verification work with redundancy and
deterministic randomness that makes manipulation of the allocation
extremely difficult. Such a pool would be very unlikely to accept an
invalid block or transaction in practice.
However, with these block sizes obviously non miners are going to have
to be SPV, so even just a 0.0001% chance of an invalid block being
accepted has profound implications for the network. If a decentralized
pool like that had more than 50% of the hashing power and it accepted a
single invalid block, that tainted chain would be forever regarded as
valid by SPV clients. There needs to be some way to recover once an
invalid block has been accidentally accepted by an imperfect miner.
Based on that I also started to think about proofs of invalidity that
would circulate. Basically you would add a new network message that
would contain the proof that a specific signature and therefore the
whole block is invalid.
As long as the block's proof-of-work is valid and the block's parent is
one of the last n = 50000 blocks, the message is relayed (subject to a
cooldown, warnings would be less frequently relayed the older the
offending block is.)
The mechanism works in exactly the way Mike mentions: It allows even SPV
clients to punish any miner who is dishonest or negligent with their
verification work. That gives miners a good reason not to be dishonest
or negligent in the first place.
(Motivation:
Processing more transactions means that hashing is a smaller part of the
overall cost for miners. For example, paying for 50 BTC worth of hashing
per block costs 0.05 BTC per tx at 1000 tx/block, but only 0.0005 BTC at
100000 tx/block.
Number of transactions is a lever that lets us have lower fees and more
network security at the same time. Like Greg correctly pointed out, this
is not worth having if we have to sacrifice decentralization. But if we
don't, it becomes a no-brainer.
My IMTUO proposal [1] showed a way where miners don't need a copy of the
set of unspent outputs at all. This means the minimum storage
requirements per node no longer grow with the number of transactions.
However, the price for this was about five times greater bandwidth usage
per verified transaction. Since every miner still had to verify every
transaction it looked like bandwidth would become an even bigger problem
with IMTUO than storage would have been without. However, if a small
miner can do less than 100% verifications and still contribute, suddenly
IMTUO may become viable. That would accomplish the holy grail of Bitcoin
scalability where the network successfully runs on trust-atomic entities
all of which can choose to store only a small fraction of the block
chain, verify a small fraction of transactions and perform a small
fraction of the hashing.)
[1] https://en.bitcoin.it/wiki/User:Justmoon/IMTUO
On 6/24/2012 2:45 PM, Mike Hearn wrote:
> I've been having a discussion with d'aniel from the forums about how
> to handle the possibility of a majority-miner conspiracy to raise
> inflation, if most economic actors use SPV clients.
>
> Because of how blocks are formatted you cannot check the coinbase of a
> transaction without knowing the fees in the block, and the fees can
> only be calculated if you have all the input transactions for every
> transaction in that block. Because the attack scenario is an attempted
> takeover of the economy by miners, attempting to put hints into the
> blocks won't work - we have to assume the hardest chain is in fact
> wrong according to the rules signed up to by the Bitcoin user.
>
> The most obvious goal for a cartel of miners is to change the
> inflation formula, either for purely selfish reasons (they want more
> money than can be obtained by fees) or due to coercion by
> governments/central banks who still subscribe to the "inflation is
> good" idea.
>
> Whilst "good" nodes (still on the old ruleset) won't relay blocks that
> violate the rules no matter how hard they are, in a situation where an
> SPV client DOES hear about the bad best chain, it would switch to it
> automatically. And who knows how the network might look in future -
> perhaps most nodes would end up run by miners, or other entities that
> upgrade to the new ruleset for other reasons.
>
> d'aniel made a good proposal - having good nodes broadcast
> announcements when they detect a rule that breaks the rules, along
> with a proof that it did so. Checking the proof might be very
> expensive, but it would only have to be done for split points,
> limiting the potential for DoS. If a node announces that it has a
> weaker chain and that the split point is a rule-breaker, the SPV
> client would download the headers for the side chain to verify the
> split, then download all the transactions in the split block along
> with all their inputs, and the merkle branches linking the inputs to
> the associated block headers. In this way the fee can be calculated,
> the inflation formula applied and the coinbase value checked.
>
> If the block is indeed found to be a rule-breaker, it'd be blacklisted
> and chains from that point forward ignored.
>
> Miners may decide to allow themselves to create money with
> non-index-zero transactions to work around this. In that case the good
> node can announce that a given tx in the rule-breaker block is
> invalid. The SPV node would then challenge nodes announcing the longer
> chain to provide the inputs for the bad tx all the way back to a
> pre-split coinbase.
>
> Doing these checks would be rather time consuming with huge blocks,
> but it's a last resort only. In the absence of bugs, the mere presence
> of the mechanism should ensure it never has to be used.
>
> ------------------------------------------------------------------------------
> 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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Bitcoin-development] Enforcing inflation rules for SPV clients
2012-06-24 12:45 [Bitcoin-development] Enforcing inflation rules for SPV clients Mike Hearn
2012-06-24 16:51 ` Stefan Thomas
@ 2012-06-24 18:03 ` Gregory Maxwell
2012-06-25 8:42 ` Mike Hearn
1 sibling, 1 reply; 6+ messages in thread
From: Gregory Maxwell @ 2012-06-24 18:03 UTC (permalink / raw)
To: Mike Hearn; +Cc: Bitcoin Dev
On Sun, Jun 24, 2012 at 8:45 AM, Mike Hearn <mike@plan99•net> wrote:
> d'aniel made a good proposal - having good nodes broadcast
> announcements when they detect a rule that breaks the rules, along
> with a proof that it did so. Checking the proof might be very
Link?
I also proposed this on this list (see the response in the tree
datastructures thread) along with more elaboration on IRC. If multiple
people are coming up with it thats a good sign that it it might
actually be viable. :)
I was going for a slightly different angle and pointing out that the
proofs would mean that a node doing validation with TxOUT tree which
hasn't personally wittnessed the complete history of Bitcoin actually
has basically the same security— including resistance to miners
creating fake coin in the past— as a full node today because in order
to get away with a lie every single node must conspire: It's adequate
that only one honest node wittness the lie because once it has the
proof information is hard to suppress.
To save people from having to dig through the public IRC logs for what
I wrote there:
--- Day changed Thu Jun 21 2012
15:10 < gmaxwell> etotheipi_: amiller: an interesting point with all
this txout tree stuff is that if you join the network late and just
trust that the history is correct based on the headers, any other node
who has witnessed a rule violation in the past can prepare a small
message which you would take to be conclusive proof of a rule
violation and then ignore that chain.
15:11 < gmaxwell> e.g. if someone doublespends I just take the
conflicting transactions out and the segments connecting them to the
chain... and show them to you. And without trusting me you can now
ignore the entire child chain past that point.
15:13 < gmaxwell> This fits nicely with the Satoshi comment "It takes
advantage of the nature of information being easy to spread but hard
to stifle" ... it would be safe to late-join a txout tree chain,
because if there is only a single other honest node in the world who
was around long enough to wittness the cheating, he could still tell
you and it would be as good as if you saw it yourself.
15:17 < gmaxwell> (this is akin to the provable doublespend alert
stuff we talked about before, but applied to blocks)
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Bitcoin-development] Enforcing inflation rules for SPV clients
2012-06-24 18:03 ` Gregory Maxwell
@ 2012-06-25 8:42 ` Mike Hearn
0 siblings, 0 replies; 6+ messages in thread
From: Mike Hearn @ 2012-06-25 8:42 UTC (permalink / raw)
To: Gregory Maxwell; +Cc: Bitcoin Dev
> Link?
It was a private conversation for some reason.
> I also proposed this on this list (see the response in the tree
> datastructures thread) along with more elaboration on IRC.
Ah OK. I wasn't paying much attention to those threads.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Bitcoin-development] Enforcing inflation rules for SPV clients
2012-06-24 16:51 ` Stefan Thomas
@ 2012-06-25 8:44 ` Mike Hearn
0 siblings, 0 replies; 6+ messages in thread
From: Mike Hearn @ 2012-06-25 8:44 UTC (permalink / raw)
To: Stefan Thomas; +Cc: bitcoin-development
> Very interesting for you to bring this up. I had a similar idea for a
> totally different use case. Greg recently pointed out an interesting
> dilemma saying that (significantly) larger blocks would lead to
> centralization.
Yeah. I am still unsure that this really holds. Bitcoin moves fast,
but even so, unless there are a few more SatoshiDice-like events and
the way people use transactions changes dramatically we're a long way
from gigabyte sized blocks. And once we get there, technology will
probably have improved to the point where it doesn't seem like a big
deal anymore.
Of course we have debated this many times already. Maybe again at the
next meetup :-)
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Bitcoin-development] Enforcing inflation rules for SPV clients
@ 2012-06-25 23:21 Daniel Lidstrom
0 siblings, 0 replies; 6+ messages in thread
From: Daniel Lidstrom @ 2012-06-25 23:21 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 10629 bytes --]
Here's the conversation I had with Mike that Gregory requested a link to:
Thanks!
Bad or hacked client devs is indeed a huge, worrying problem. The
official client is addressing this with a system called gitian, where
multiple developers all compile the same source to the same binary and
then sign the results. Multi-signatures raise the bar for releasing
hacked clients a lot. We're starting to investigate this with bitcoinj
too, but it's a lot of work.
Generally, the more people you have to involve in a conspiracy, the less
likely it is to succeed. If a few miners started to dominate the system
they have strong financial incentives to cheat, alternatively, they may
be subjected to government pressure. Having to get the client developers
involved too makes it much harder, especially as users have to actually
upgrade.
I started a thread on the development mailing list with your suggestion,
by the way.
On Mon, Jun 25, 2012 at 1:00 AM, Daniel Lidstrom <lidstrom83@gmail•com
<mailto:lidstrom83@gmail•com>> wrote:
Hey Mike,
I put our conversation in the email for easy reference.
In the unlikely event of a miner conspiracy to print money, is it
really so much of a further stretch to think the developers of a
widely used client could also be involved? (Well, maybe, since
miners are unaccountable and developers are not. OTOH if most users
are apathetic...) Also, isn't the advantage for lightweight clients
of SPV over the server-client model that you don't have to trust any
operator? Maybe I'm being too much of a purist here...
Regarding errors being cheap to send and expensive to verify,
compartmentalizing them the way I suggested before would make them
individually cheaper to verify. Just throwing around ideas:
requiring the error message be received by a quorum of peers before
checking, and dropping misbehaving or unreliable peers could help.
Also, not verifying error messages unless the peers relaying them
are willing to send all the data necessary to do so would help.
Hashcash could also be used to balance the costs to send and to
verify a given type of error message. I like your idea to only
check errors in blocks that are split points, and the length of the
split could also be a consideration.
> Can we move further conversations to email please? SMF kind of
> sucks as an inbox.
>
> Anyway, yes, your proposal makes a lot of sense, although I think
> in practice this is unlikely to be an issue. If a majority of
> miners did start mining on a chain with new rules, even if SPV
> clients couldn't detect the switch automatically it's very likely
> the developers of those clients would notify the users out of band
> in some way. For example, by pushing an update to users that
> explains the new rules to them and tells them how they can cash
> out of the Bitcoin economy if they disagree with the new consensus.
>
> If users are on the losing side of a rule change and want to stay
> there (eg, maybe most non-miners want to stay on the slower
> chain), then the client can just checkpoint the first block after
> the rule change occurred. Now even though there's a harder chain
> with the new rules, the client will stay with the old rules
> despite being blind to them. There's nothing that says checkpoints
> have to be hard coded - clients could poll the client developers
> every day to get new ones. So as long as the SPV devs are on the
> ball, most users would stay on the old rules even if the software
> can't do it by itself.
>
> All that said, broadcasting messages proving a block broke the
> rules is a nice backstop if it can be done without excessive
> complexity. There are some details to think about. These messages
> would be cheap to create and expensive to verify. There has to be
> something that stops me claiming to SPV clients that every single
> block is invalid and forcing them to do tons of useless work.
> Perhaps only blocks that are split points would be eligible. Also,
> currently, SPV clients do not form their own P2P network. They are
> always leaves of full nodes. So propagation of the messages might
> prove difficult unless that was changed.
> Hi Mike,
>
> Thanks for your reply. It was actually an old post of yours on
> the forum that made me understand the importance of lightweight
> clients being able to audit the coinbase tx.
>
> Re: input tx download, I think that splitting the "invalid
> coinbase" error notification into separate "input n in tx m is
> invalid" and "invalid fee arithmetic" errors would mean mobile
> clients would only ever have to download at most one input tx to
> verify an invalid coinbase.
>
> The "invalid fee arithmetic" error could also be compartmentalized
> into "invalid fee arithmetic in tx batch n", where the fee
> subtotals are recorded in the block, so as to be separately
> verifiable. Then the necessary tx downloads would be completely
> capped.
>
> Anyway, I think most of my fears about lifting the block size
> limit are put to rest by these lines of thinking Smiley
> Hey Daniel,
>
> I think you're thinking along the right lines here. We should be
> looking at cheap and backwards compatible ways to upgrade the SPV
> trust model to more than just going along with the majority consensus.
>
> For the coinbase issue, it's actually really important because if
> you can't calculate fees, you can't check the size of the coinbase
> value and therefore a conspiracy of miners could try and change
> the inflation schedule. The worst that can happen today if miners
> decide to try and fork the ruleset against the best interests of
> other users, is that they produce chains that are not accepted by
> regular merchant/exchange/end-user nodes and tx confirmation slows
> down. But if most users are on SPV nodes they will happily accept
> the new blocks and the miner conspiracy will have successfully
> seized control of the money supply for the majority of end users.
>
> The problem with calculating fees is you actually need not only
> every tx in a block, but all the input txns too! You can't know
> the fee of a transaction without the input transactions being
> available too.
>
> So there's good news and bad news. The good news is you don't have
> to actually store every transaction on disk or check signatures,
> which is the expensive part, if you're an SPV node - you can still
> check the coinbase value asynchronously after receiving a block by
> requesting the entire contents and all the input transactions
> (+branches, of course). If you are in an environment that is
> always-on and not bandwidth constrained this can make a lot of
> sense. For example, if you're running an SPV client on a regular
> PC that is sitting in a shop somewhere, just downloading a lot of
> data is still very cheap compared to indexing it all and verifying
> all the signatures. I'm implementing support for this kind of
> async verification in bitcoinj at the moment.
>
> Where it doesn't really make sense is mobile clients, and your
> ideas of notification can help a lot there. The first type of
> error broadcast I'd add is actually for detected double spends
> because there's a paper from researchers at ETH which show this is
> needed to address a feasible attack on todays infrastructure. But
> adding more later to detect invalid blocks is not a bad idea.
> Hi Mike,
>
> I wanted to post this on the forum and figured that since, based
> on the subject, you'd probably end up reading it anyway, I thought
> I'd run it by you first to see if there's any merit to it.
>
> Quote
> I think similar ideas are currently being tossed around.
>
> The motivation here is to keep rule enforcement maximally
> decentralized while scaling Bitcoin. Basically, SPV clients could
> subscribe to peers' announcements of /invalid/ blocks + their
> specific failure mode. AFAICT, most of the possible failure modes
> are easily verifiable by smart phone SPV clients, even at scale.
> For example, inclusion of double spends or otherwise invalid txs
> are easy to verify /given the necessary data/, and Merkle tree
> nodes can be deemed invalid /if no peer can produce the data that
> hashes to it/ (gotta be careful to detect and deal with false
> positives here). The only failure mode I can think of that isn't
> easily verifiable at scale is an invalid quantity of fees spent in
> the coinbase tx, since that currently requires the download of the
> whole block. (I think I have an idea to fix this below.)
>
> This trust model relies upon having a single fully validating peer
> that will reliably announce invalid blocks. To help this, one or
> more peers could be periodically cycled, and new ones asked if the
> main chain contains any invalid blocks. Worst case scenario, an
> SPV client reverts to the current trust model, so this idea can
> only improve the situation. Best case, it takes advantage of the
> fact that public information is hard to suppress.
>
> *Verifying coinbase tx invalidity at scale with SPV clients*
>
> While this is currently not prohibitive for a smart phone if done
> only occasionally, this will not be the case if the block size
> limit is lifted. The idea is to split up the summing of the
> spendable fees into verifiable pieces. A new merkle tree is
> calculated where the i'th leaf's data is the total fees in the
> i'th chunk of 1024 txs, along with these txs' Merkle root (to
> prevent collisions). The Merkle root of this new tree is then
> included somewhere in the block.
>
> To verify a claim of invalidity of one of these leaves requires
> the download of ~1MB of tx data (along with a small amount of
> Merkle tree data to verify inclusion). If no claims are made
> against it, the leaf data is assumed to be valid. If this is the
> case, but shenanigans are called on the coinbase tx, downloading
> all of the leaf data, verifying inclusion, and calculating the
> total spendable fees is easily doable for a smart phone, even at
> very large tx volumes.
>
> Thanks for any thoughts/suggestions!
>
> Cheers,
> Daniel
[-- Attachment #2.1: Type: text/html, Size: 14721 bytes --]
[-- Attachment #2.2: Type: image/gif, Size: 382 bytes --]
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2012-06-25 23:21 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-06-24 12:45 [Bitcoin-development] Enforcing inflation rules for SPV clients Mike Hearn
2012-06-24 16:51 ` Stefan Thomas
2012-06-25 8:44 ` Mike Hearn
2012-06-24 18:03 ` Gregory Maxwell
2012-06-25 8:42 ` Mike Hearn
2012-06-25 23:21 Daniel Lidstrom
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox