random transaction checking

[Cryddit]

Change the software so that not all clients have to check all signatures. This was raised in http://bitcointalk.org/index.php?topic=6373.msg94314#msg94314 in the context of speeding transaction propagation.

This one.  If each client checks a randomly-selected one-third of all transactions, each transaction would still get checked thousands of times and we'd be running considerably faster.  Miners would want to check everything so they don't get orphan blocks, but other full nodes could, without practical loss of security, trust each other for a substantial fraction of their checking - a "randomly-selected third of all bitcoin nodes" is for practical purposes just as uncontrollable to an attacker as "all the bitcoin nodes."

[TierNolan]

This one.  If each client checks a randomly-selected one-third of all transactions, each transaction would still get checked thousands of times and we'd be running considerably faster.

This would have to be combined with fraud proofs.  If you find a badly signed transaction, you have to be able to tell all the other nodes about it.

[jl2012]

Thanks for bringing this up. I didn't know this. I think eventually we will need this as we have more transactions. This could be done as soft-fork, anyway.

Revisting this topic.   While changing the protocol to allow transactions with implicit public key recovery is worthwhile it would be a breaking change so I understand not moving on this.  However there is absolutely no reason for the Bitcoin-Core client to require an address when verifying the signature.  The PubKey can be recovered from the signature the PubKeyHash produced from that and then the address generated from that.  

Can anyone think of any reason why the Bitcoin client requires the user provide the address (something it can and already does compute)?
I would add the UI in the core client for this section is not user friendly.  A user verifying signature has to copy and paste three separate components into three different boxes (one of which is pointless).  How about a unified copy and paste of a single signed message block?
Why not have the user supply the message & signature (preferably in a unified encoded form (i.e. similar to PGP signed message) and then the client verifies the signature and computes and displays the results?

An example which puts it all together.

Input

Code:

-----BEGIN BITCOIN SIGNED MESSAGE-----
This is an example of a signed message.
-----BEGIN BITCOIN SIGNATURE-----
HHfUi9n72BxXottUu+AbU4iS0QQLxPtAtuydgRcjc+XoY9Hzw8u6Z+wbzDV+owVLiQR85OwioPcUVJcT+LHjqCE=
-----END BITCOIN SIGNATURE-----

and the client responds with either
Message verified to be signed by 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T

or

Message not verified.  Please double check signed message is copied in it entirety including the BEGIN and END lines.


Brainwallet.org has something similar and is more intuitive than the Bitcoin Core client.  Still even the brainwallet website adds a "warning" that is pointless and vague.

Message verified to be from 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T (but address was not found in the signature!)

Code:

-----BEGIN BITCOIN SIGNED MESSAGE-----
This is an example of a signed message.
-----BEGIN BITCOIN SIGNATURE-----
HHfUi9n72BxXottUu+AbU4iS0QQLxPtAtuydgRcjc+XoY9Hzw8u6Z+wbzDV+owVLiQR85OwioPcUVJcT+LHjqCE=
-----END BITCOIN SIGNATURE-----

The address is not found in the signature?  Is that bad?  Should I be worried?  Am I being scammed?  To most users, yellow is a color of caution.   The expected outcome would be a definitive "SUCCESS" (and green) but instead there is this ambiguous partial success.  The "yellow" response is pointless as anyone can add the address in after the signature is created to remove the warning.  So what is is warning about.  Adding the address 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T just above the signature looks like this and provides the expected "good" response.

Message verified to be from 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T

Code:

-----BEGIN BITCOIN SIGNED MESSAGE-----
This is an example of a signed message.
-----BEGIN BITCOIN SIGNATURE-----
1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T
HHfUi9n72BxXottUu+AbU4iS0QQLxPtAtuydgRcjc+XoY9Hzw8u6Z+wbzDV+owVLiQR85OwioPcUVJcT+LHjqCE=
-----END BITCOIN SIGNATURE-----

The "caution" response only undermines the point of even allowing signatures that don't include the (unnecessary) address.  Imagine you are a company which sends out signed messages to customers.   Lets use the 80/20 rule.  If you exclude the address 80% of your users will understand the "warning" is pointless however that means you are going to confuse 20% of your customers and that means extra cost and work.  So why not just include the (pointless) address so it shows up as green.

Still the behavior isn't as bad as the core client which refuses to validate the signatures and throws an error.

[DeathAndTaxes]

This one.  If each client checks a randomly-selected one-third of all transactions, each transaction would still get checked thousands of times and we'd be running considerably faster.

This would have to be combined with fraud proofs.  If you find a badly signed transaction, you have to be able to tell all the other nodes about it.

The overhead of that would significantly reduce any efficiency gains.  I wonder if we are heading towards a future where we see ECDSA Accelerator cards.  SSL Accelerator (and TCP/IP offload) cards were pretty common until a combination of improved hardware instructions and the brute force power of Moore's law made the CPU load for most servers a minimal concern.

[gmaxwell]

The overhead of that would significantly reduce any efficiency gains.

libsecp256k1 does over 40,000 ecdsa verifies per second on a desktop class quad-core cpu. I suspect any need for accelerators may be over-blown.

[DeathAndTaxes]

The overhead of that would significantly reduce any efficiency gains.

libsecp256k1 does over 40,000 ecdsa verifies per second on a desktop class quad-core cpu. I suspect any need for accelerators may be over-blown.

Is that a real world test of some static verify the same signature with a key in memory?  The reason I ask is because throughput on block verification seems to be more than three orders of magnitude slower than that.  Yes block verification has some other overhead be we aren't talking about rounding errors.  Or is it that bitcoind implementation is just very inefficient?

[gmaxwell]

Is that a real world test of some static verify the same signature with a key in memory?

It's a test with randomly generated keys and signatures.

The reason I ask is because throughput on block verification seems to be more than three orders of magnitude slower than that.  Yes block verification has some other overhead be we aren't talking about rounding errors.  Or is it that bitcoind implementation is just very inefficient?

I'm not clear on what _precisely_ you're talking about there: During normal operation bitcoind isn't doing much if any ECDSA validation when it verifies a block, because it does validation when transactions are circulated on the network. If you're talking about initial syncup then the performance there is entirely bound by things completely unrelated to ECDSA (mostly due to poor fetching logic that does redundant work).  OpenSSL is also about 6x slower than libsecp256k1.  There is a benchmark flag in bitcoin core to make it log how much time is spend on each part of the validation.

[TierNolan]

This would have to be combined with fraud proofs.  If you find a badly signed transaction, you have to be able to tell all the other nodes about it.

The overhead of that would significantly reduce any efficiency gains.

Huh?  The overhead is tiny.  

The proof is the path form the merkle root of the header to the transaction and the input transaction.

Your peer then checks if the signature is wrong.

If it is correct, then your node is assumed to be launching a DOS attack and the connection is broken.

Otherwise, your peer forwards the proof to all peers connected to it.

Since the proof is checked on each hop, the only time a fraud broadcast happens is if an invalid block is mined.

The cost is two transactions plus two merkle paths.  Unless the transactions are massive, this isn't a big deal.  It could be fixed with a hard fork to have the merkle path go the whole way to the transaction outputs.

[gmaxwell]

It's not two transactions, it's one transaction plus the number of inputs transactions and their merkel paths. However, if you're asserting that an input simply doesn't exist there is no compact proof for that currently (though one could be added with an additional commitment). Proving things like "coinbase takes too much subsidy" also requires additional data. I enumerated many (most?) of the things that need additional data to be proved a long time back: https://en.bitcoin.it/wiki/User:Gmaxwell/features#Proofs

[TierNolan]

It's not two transactions, it's one transaction plus the number of inputs transactions and their merkel paths. However, if you're asserting that an input simply doesn't exist there is no compact proof for that currently (though one could be added with an additional commitment). Proving things like "coinbase takes too much subsidy" also requires additional data. I enumerated many (most?) of the things that need additional data to be proved a long time back: https://en.bitcoin.it/wiki/User:Gmaxwell/features#Proofs

The big one is missing data.

SPV header checks

Header size is unaffected by number of transactions per second, so I think SPV nodes could be assumed to check headers.

Making the header chain the root for all the other proofs is reasonable.

Even if some SPV nodes only keep the 10-20k newest blocks, it would likely be safe.

Proof of invalid script

If P2SH was made mandatory, then this is made easier.  The entire script and release script is included in the spending transaction.

It is still necessary to prove that the output actually exists.  That can be handled by the UTXO commit system.

If merkle tree changes are allowed, the merkle tree could also have paths to the hash for all outputs.  That keeps the proof of existence easier.

Failing that, there could be a rule that transactions can't have more than 4 outputs.  That (somewhat) limits the size of transactions.

Proof of double spend

The UTXO commit system would also cover this.  

Proof of false inflation
Proof of block too large

Right, needs a new merkle tree.

Proof of spending a non-existing input

This is the hard one.  If there was a commit system, then blocks should include the extra data needed to verify each of the commits.

If all UTXOs are in a tree, then only the hash of the root is needed.

To verify each transaction, it is necessary to know the root before and after the transaction to prove that the transaction tree has been correctly updated.

This means that there is a need for a merkle tree containing the root of the tree after each update.

To verify that the UTXO tree has been updated correctly, then you need

merkle root of UTXO merkle tree for the block

path to the node before and after the transaction
- This proves the tree's root before and after the transaction was inserted

path through the UTXO tree for each input and output in the transaction
- This allows the TXO's to be inserted and removed

This allows a SPV node to check a particular transaction.

The final issue is proving that proof data is missing.  If an illegal transaction is included, nodes have to be able to obtain the extra data.  If they can't, then they can't create the proof.