What causes quadratic hash problem?

What causes quadratic hash problem?

I read ScriptSig content during signature (quadratic hashing) discussing quadratic hash problem.

Quadratic hash problem is the issue that signing (or verifying) transaction time grows with the square of the number of inputs (O(n^2) where n is the number of inputs).

Why is that so? I reason the following:

  1. For each input you construct different template. O(n)
  2. This template must be double-SHA-hashed. - Double-SHA-hash duration is dependent linearly on the size of the template.
  3. Double hashed template (of fixed length) is then signed. - as the leght is fixed this step is of fixed duration

As step 2 is dependent linearly on the size of the template, thus it is linearly dependent on the number of inputs, giving final time dependency relation O(n^2)?

More precisely O(n^2+m) where m is the number of outputs (as this contributes in step 2)?

http://ift.tt/2BtRtgN

Comments

Post a Comment

Popular posts from this blog

sendrawtransaction and txn-mempool-conflict

sendrawtransaction and txn-mempool-conflict When i sendrawtransaction to bitcoind, i get error (exceptions) 18: txn-mempool-conflict (use Bitcoin JSON-RPC denpamusic/php-bitcoinrpc ) But the transaction is sent to the network and is subsequently confirmed. Example one decoded transaction : https://jsfiddle.net/rn58a4j6/ then i send this transaction: 94ec12fc463230b4285a29b047608627c05572a4c6eabe6688a201ce49ae72f7 https://ift.tt/2MY2KP0
Read more

couldn't connect to server: EOF reached (code 1)

couldn't connect to server: EOF reached (code 1) I'm running a full node on my raspberry pi3. I try to do a simple command such as bitcoin-cli getblockchaininfo but I always get this error: error: couldn't connect to server: EOF reached (code 1) (make sure server is running and you are connecting to the correct RPC port) My bitcoin.conf file looks like this: Bitcoind options server=1 daemon=1 reindex-chainstate=1 reindex=1 txindex=1 disablewallet=1 listenonion=0 Connection settings rpcuser= * rpcpassword=* rpcport=8332 rpcallowip=127.0.0.1 rpcthreads=10 I also tried to get a command with "bitcoin-cli -rpcuser: * - rpcpassword=* -rpcportt8332 getblockchaininfo". But this also didn't work. Does someone has some advice or experience with this error? https://ift.tt/2D82TLW
Read more