Topic: Securing the network against miner fraud (Read 911 times)

They are proof that something is wrong with the block.

You need to go through every check that is performed on a block and then have a proof to show that it is wrong.

You can show that a transaction exists in a block by giving the path along the merkle tree.

You could prove that an output was double spent by showing a path to the previous transaction that spent the block and also a path to the transaction in the current block that spent it.

By including the spending transaction, you can show that the scripts are all correct.

Some of the fraud proofs require new merkle trees to be added and then committed to in the block.

You can commit to "sums" using sum-trees.  For example, each transaction has a size.  If the total size of the block exceeds the limit, you have to be able to prove it.

Sum trees include the sum of all the leaves below the node in the merkle tree.  In order to get it to add up to the wrong value, you need at least one path through the tree to be wrong.  This false path is the fraud proof.

This is also required for protecting against inflation (miners paying themselves to much) and checking the number of sigops in the block.


SPV clients inherently trust the miners not to produce bad blocks.

I'm not the OP, but I could imagine example:
lets assume that block A invalid because contains wrong tx (which spend already spent txout, or wrong by itself). Every spv-node has blockheader which contain merklehash, so fraud-proof should contain:

[proof that tx is wrong] + [proof that tx is in block A].

[proof that tx is in block A] merkle hash - is pyramid structure, so you can easily prove that tx is in the block by providing N intermediate hashes where N=log_2(number of txs in the block)

[proof that tx is wrong] it could be tx by itself if its obviously wrong, or you could provide another tx2 in previous block B which spend the same tx out with [proof that tx2 is in block B]

Please elaborate more on fraud proof. How it works etc.

SPV mining without full block verification is vulnerable and them losing the money is a lessen well deserved.
I think malicious (or dumb) miners can still generate invalid blocks even now which would be accepted as valid by a lot of clients.

Well it's good proposal.
Now function of "Fraud Proofs" is executed by pool operator. Bitcoin-core doesn't mine new block on the top of block for which it has header but not body, so pools which use spv-mining and pools which use bitcoin-core will have different forks of blockchain. I believe that many people automatically check network for such forks and proof of my point of view is speed of solving problem July, 4.
But you are right, we need more dependable mechanisms for spv-mining.

Encouraging more people to run full nodes is often suggested as a good way to improve the security of the network and people are encouraged to do so.

This is intended to protect the network from miners creating invalid blocks and violating the network rules (keeping miners honest).

In the extreme case, if all merchants and their customers used SPV clients, then a majority of miners could set any rules that they wish for the network.

Everyone would just find the longest chain and not care about validity of the blocks.

Full Nodes

Running a full node means that you fully check all transactions and blocks before forwarding them.

Adding another full node doesn't actually help that much in protecting against miners.

Your node will just fall behind the rest of the network, since it won't track the longest chain.  None of the SPV clients will bother with your node, since you can't give them info on the latest blocks.

On the other hand, if merchants refuse to accept transactions on the longest (but invalid) chain, then that creates the incentive for miners to properly follow the protocol rules.

For full nodes, the encouragement should be for merchants to run their own full nodes.

Full nodes also help SPV clients for transaction lookup, so they aren't worthless, but it doesn't add to security against miners.

SPV Clients

SPV clients are users of the network, so there is an incentive to make sure that blocks are acceptable to them.  But, by their nature, they don't do miner verification.

Fraud Proofs

Fraud proofs are a short (hopefully less than 100kB) proof that a block is invalid.  Even for 1GB blocks, the fraud proof would be about the same size.  They generally scale with the log of the maximum block size  O(log(block_size)).

Arguably, they scale with the square of the maximum transaction size.  This assumes a maximum size transaction with all the inputs being maximum size.  In practice, the fraud proofs would likely scale with the maximum transaction size.

The advantage of fraud proofs is that you can prove to SPV clients that a block is invalid.

If 75% of the miners want to violate the protocol rules, anyone running a full node can broadcast a fraud proof.

When the miner cartel broadcasts their invalid block, full nodes broadcast the block header and fraud proof.  SPV-nodes can quickly check the header and fraud proof.  This means the fraud proof could propagate faster than the bad block.  Full nodes which receive the fraud proof before the block wouldn't have to validate the block, since they have proof that it is invalid.

Block Withholding Attack

If the miners' cartel just broadcasts the block headers, then it isn't possible to generate a fraud proof. 

Since the full nodes haven't received the full blocks, they can't check them.  This means that they can't produce fraud proofs.

The mining cartel must send the merkle path for any transactions it wants to show to SPV clients.  This means that slowly the block would be broadcast.  A fraud proof broadcast 3 months later would do damage to trust in the network, since all SPV clients would reverse all transactions since then.

Publication Verification Nodes

These are nodes which verify that blocks have actually been published.

They do minimal verification.  They just check the POW and the merkle tree.  They don't even need to check if the transactions are properly formatted transactions.

If they don't delete old blocks, then they would be (non-validating) archive nodes.

In practice, they need to store some of the blocks so that they can forward them.  This is necessary to prove that they have actually been published.

DOS protection is provided due to block POW.  They would only download blocks that are on the longest chain and they haven't seem before.

The relay system in use for bitcoin works this way. With fast relaying, it decreases the need for miners to build empty blocks on block headers.  SPV-mining timeouts can be set lower.

Full System

Merchants running publication verification nodes would create an incentive for miners to actually publish their blocks.

These nodes are pretty cheap for a merchant to run.  Even only storing the 10 most recent blocks would give pretty good proof that the block was actually published, in full, to the world.

Ideally, some merchants would run full nodes too.

Once block publication is proven, fraud proofs can be used to keep all the miners honest.

With fraud proofs, SPV clients are almost as secure as full nodes.  You only need a small number of honest peers to keep the whole system honest.  There could be a delay before the fraud proof is broadcast, so low confirms should be considered less safe.

Risks

Fraud proofs are potentially risky for the network.  They are, in effect, a re-implementation of the network rules.

If there was a bug in the fraud proof system, someone might be able to produce a proof of fraud for a valid block.  This would allow an attack on the network where months of transactions could be reversed by waiting and then submitting the proof of fraud. 

The opposite problem is also true.  The miner's cartel could create an invalid block without it being possible to notify SPV clients.

Ideally, all invalid blocks should have a fraud proof and there should be no fraud proofs possible for valid blocks.  Achieving that and proving it is achieved are the hard part.

SPV clients should probably go into emergency mode if they receive a block revert for a block that is more than 10-20 blocks deep and be directed to find out what has actually happened.  This covers fraud proofs for valid blocks.

Invalid blocks without fraud proofs could be handled by an alert.

Summary

• Running full nodes alone doesn't protect again miners collusion
• Full nodes run by merchants does help
• SPV Clients inherently trust miners
• Fraud proofs allow SPV clients to reject invalid chains
• Fraud proofs are vulnerable to miners withholding full block data
• Publication verification nodes protect against withholding attacks