[Questions] Public key cost comparison

ABCbits

legendary

Activity: 2870

Merit: 7490

Crypto Swap Exchange

Quote from: PrimeNumber7 on January 26, 2022, 01:20:53 AM

There may be an argument to move the public key of the inputs to a new part of a transaction that does not need to be retained (similar to how the 'witness' part of a transaction does not need to be retained).

BIP125/Replace-by-fee(RBF) flag might be better comparison.

PrimeNumber7

copper member

Activity: 1666

Merit: 1901

Amazon Prime Member #7

Quote from: pooya87 on January 26, 2022, 04:19:13 AM

Quote from: PrimeNumber7 on January 26, 2022, 01:36:48 AM

Quote from: pooya87 on January 26, 2022, 01:27:19 AM

Quote from: PrimeNumber7 on January 26, 2022, 01:20:53 AM

(similar to how the 'witness' part of a transaction does not need to be retained).

Witness part of the transactions must be retained, there is no way around that! If you discard them, then you can no longer validate that transaction and you stop being a full node.

I have to disagree with you on that. Once you validate a transaction, there is no need to validate it again in the future. Even if for some reason you need to reindex the blockchain if you have already validated previous transactions, all you need is the transaction history of inputs/outputs of each transaction in each block.

When you first receive a transaction (or a block), you need to validate it because it may not be valid, and you may need to reject the transaction. However, once you accept a transaction, nothing is going to change that will cause you to later reject the transaction. There is no circumstance in which you will reject a transaction that you had previously accepted.

In that case why stop at public keys or witnesses, if you don't want to be a full [archival] node you can get rid of everything (your entire blockchain up to a handful of recent blocks) and only keep the UTXO set. After all UTXOs are the only data you need to keep in order to validate the new blocks.

You are referring to pruned nodes, and yes, you are correct, that is all that is needed to validate if any future transaction is valid, and will provide sufficient information to tell the user the current "balance" of any arbitrary address.

If someone has the available resources, they may wish to retain some additional data so they can provide said data to new nodes who are in the process of validating the blockchain.

There may also be non-validation reasons why someone may want to retain additional information. For example, if someone is hosting a block explorer, they would want to retain as much additional information as they want to be able to provide to their users.

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: PrimeNumber7 on January 26, 2022, 01:36:48 AM

Quote from: pooya87 on January 26, 2022, 01:27:19 AM

Quote from: PrimeNumber7 on January 26, 2022, 01:20:53 AM

(similar to how the 'witness' part of a transaction does not need to be retained).

Witness part of the transactions must be retained, there is no way around that! If you discard them, then you can no longer validate that transaction and you stop being a full node.

I have to disagree with you on that. Once you validate a transaction, there is no need to validate it again in the future. Even if for some reason you need to reindex the blockchain if you have already validated previous transactions, all you need is the transaction history of inputs/outputs of each transaction in each block.

When you first receive a transaction (or a block), you need to validate it because it may not be valid, and you may need to reject the transaction. However, once you accept a transaction, nothing is going to change that will cause you to later reject the transaction. There is no circumstance in which you will reject a transaction that you had previously accepted.

In that case why stop at public keys or witnesses, if you don't want to be a full [archival] node you can get rid of everything (your entire blockchain up to a handful of recent blocks) and only keep the UTXO set. After all UTXOs are the only data you need to keep in order to validate the new blocks.

PrimeNumber7

copper member

Activity: 1666

Merit: 1901

Amazon Prime Member #7

Quote from: NotATether on January 26, 2022, 02:18:35 AM

Quote from: PrimeNumber7 on January 26, 2022, 01:36:48 AM

When you first receive a transaction (or a block), you need to validate it because it may not be valid, and you may need to reject the transaction. However, once you accept a transaction, nothing is going to change that will cause you to later reject the transaction. There is no circumstance in which you will reject a transaction that you had previously accepted.

I could modify the block data on the disk while Bitcoin Core isn't running; that would necessitate a re-validation of the block.

But since it doesn't know which block I modified, it has to check all of them and it can't assume a specific block is the dirty block.

I don't think core verifies previous block data when it starts, so it would not re-validate previous blocks unless instructed to by the user.

More importantly, if someone can arbitrarily modify block data, they can also arbitrarily install malware, which would make any output from your computer untrustworthy, which makes running core pointless because the malware could potentially cause core to produce output that is not accurate.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: PrimeNumber7 on January 26, 2022, 01:36:48 AM

When you first receive a transaction (or a block), you need to validate it because it may not be valid, and you may need to reject the transaction. However, once you accept a transaction, nothing is going to change that will cause you to later reject the transaction. There is no circumstance in which you will reject a transaction that you had previously accepted.

I could modify the block data on the disk while Bitcoin Core isn't running; that would necessitate a re-validation of the block.

But since it doesn't know which block I modified, it has to check all of them and it can't assume a specific block is the dirty block.

PrimeNumber7

copper member

Activity: 1666

Merit: 1901

Amazon Prime Member #7

Quote from: pooya87 on January 26, 2022, 01:27:19 AM

Quote from: PrimeNumber7 on January 26, 2022, 01:20:53 AM

(similar to how the 'witness' part of a transaction does not need to be retained).

Witness part of the transactions must be retained, there is no way around that! If you discard them, then you can no longer validate that transaction and you stop being a full node.

I have to disagree with you on that. Once you validate a transaction, there is no need to validate it again in the future. Even if for some reason you need to reindex the blockchain if you have already validated previous transactions, all you need is the transaction history of inputs/outputs of each transaction in each block.

When you first receive a transaction (or a block), you need to validate it because it may not be valid, and you may need to reject the transaction. However, once you accept a transaction, nothing is going to change that will cause you to later reject the transaction. There is no circumstance in which you will reject a transaction that you had previously accepted.

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: PrimeNumber7 on January 26, 2022, 01:20:53 AM

(similar to how the 'witness' part of a transaction does not need to be retained).

Witness part of the transactions must be retained, there is no way around that! If you discard them, then you can no longer validate that transaction and you stop being a full node.
You may be confusing the case when full nodes strip the witness part for the old clients (that are no longer full verifying nodes) so that they can still be used and do a half-ass sync.

PrimeNumber7

copper member

Activity: 1666

Merit: 1901

Amazon Prime Member #7

Forcing nodes to calculate the public key would increase the cost of rejecting an invalid transaction. So there would be an increased threat of a DDoS type attack in which attacker nodes broadcast invalid transactions that spend UTXOs but are signed by incorrect private keys.

If there is a high cost to validate transactions, there is the risk that some nodes will assume received transactions are valid and will accept them (which includes both relaying the invalid transactions and relaying blocks that include invalid transactions).

There may be an argument to move the public key of the inputs to a new part of a transaction that does not need to be retained (similar to how the 'witness' part of a transaction does not need to be retained).

In general, time is much more valuable than space, and as a general rule, using additional space is acceptable if it means to save on the time cost.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: pooya87 on January 25, 2022, 11:20:13 PM

Why -40 bytes?

The daily averages Bitcoinvisuals varied significantly so I didn't feel it would be worthwhile to chase an accurate result out of an estimated guess Tongue

Quote from: pooya87 on January 25, 2022, 11:20:13 PM

A pubkey is 33 bytes and it is pushed to the stack with 1 byte (compact size length) so a total of 34 bytes is removed.
Also a 600-byte transaction that most of the times has more than one input also has more than one public key. For example with 5 P2WPKH inputs (roughly 600 bytes) we have 5 public keys so 170 bytes could be removed.

I believe the multi-pubkey transactions are reflected on the days with a higher average tx size since that would mean more of those transactions were created on that day. It doesn't necessarily mean that we're removing all those bytes from an average 600-byte transaction for example.

Actually, even the average tx size is skewed because of all of those exchange dumping their inputs and outputs. That's why the average seems really large but according to Bitcoin SE a 220 (specifically, 223)-byte transactions are the common transaction type assuming an input and two outputs.

The proportion of large exchange transactions is small enough that a 170-byte reduction in size wouldn't make much of a difference to blockchain size, despite that being a larger percent reduction.

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: NotATether on January 25, 2022, 10:53:26 PM

The average transaction size is about 600 bytes, so subtracting the 33 bytes from the signature script to make transaction sizes smaller would bring it down to about 560 bytes or so,

Why -40 bytes? A pubkey is 33 bytes and it is pushed to the stack with 1 byte (compact size length) so a total of 34 bytes is removed.
Also a 600-byte transaction that most of the times has more than one input also has more than one public key. For example with 5 P2WPKH inputs (roughly 600 bytes) we have 5 public keys so 170 bytes could be removed.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

The average transaction size is about 600 bytes, so subtracting the 33 bytes from the signature script to make transaction sizes smaller would bring it down to about 560 bytes or so, but this is only a 6% reduction in storage size which will hardly make a dent in blockchain size forecasts. Not to mention that it is impossible to remove the public key from the tx since that would break existing address types, and this is already obsoleted by taproot as garlonicon mentioned anyway.

pooya87

legendary

Activity: 3472

Merit: 10611

It is not just that recovering public key from signature is expensive but also that you can recover multiple possible public keys so you can end up verifying one signature multiple times whereas right now with the public key already available you only perform the verification once.

Otherwise if you want to know the cost of public key recovery you have to do some serious benchmarking with the available optimized library (libsecp256k1). Take random blocks that are full and try to rewrite the OP_CHECK(MULTI)SIG(VERIFY) in interpreter.cpp to recover public key instead of using the top stack item and see how different the time is going to be to verify that particular block. (I don't know C++ to do it myself).

garlonicon

copper member

Activity: 821

Merit: 1992

Quote

Each public key takes 33 bytes of space as it consists of the x-coordinate which is 32 bytes (256 bits) and a prefix which is 1 byte.

This information is a bit outdated, because in taproot your public key is your address (and it always has 02 prefix, so you have two matching private keys for any taproot address). So, the compression is done in another place: instead of keeping only hashes and recovering public keys, you get rid of hashes and store public keys directly.

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

I really couldn't find a more suitable title. Send me a PM if you've thought of something better.

Currently, we use public keys in compressed format. Each public key takes 33 bytes of space as it consists of the x-coordinate which is 32 bytes (256 bits) and a prefix which is 1 byte. They're included into scriptSig so the validator can check if the signature of a transaction is valid.

However, a validator can also check if the signature of a transaction is valid without having the public key in the first place, simply by deriving it, using the r, s, z values[1]. The problem is that this (extra) operation is computationally expensive and when we're talking about millions of signatures, it may make validation more tough for an ordinary computer.

My questions are these:

Is the expense of keeping all the public keys (storage-wise) greater than if you just derived all those keys using this operation?
If no, how do you measure the expenses of these two methodologies in such large scale?

[1] https://crypto.stackexchange.com/questions/18105/how-does-recovering-the-public-key-from-an-ecdsa-signature-work

Topic: [Questions] Public key cost comparison (Read 200 times)