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

Tor proxy on Electrum, what does Port: 9150 and 9050 mean?

Tor proxy on Electrum, what does Port: 9150 and 9050 mean? The first time that i installed Electrum i navigated to Tools->Network->Proxy i saw there a checkbox "Use Tor proxy on port 9050", i had a problem with my OS so i had to reinstall my OS, Electrum and Tor, and now instead of "port 9050" it's "port 9150". I think that it's because i'm using the Tor Bundle, as said on this electrum docs , downloaded from here: https://www.torproject.org/projects/torbrowser.html.en#linux i want to know what is the difference between the port "9050" and "9150". And if i'm fine using the "9150". https://ift.tt/2T0EvmY
Read more

Can we see Blockchain decentralized data like a mathematical duality or morphisms between representations?

Can we see Blockchain decentralized data like a mathematical duality or morphisms between representations? I prefer to think BLOCKChain in mathematic spaces formulation because we need to understand what is in mathematic terms this 'de-centralization' before. I find this what is decentralization and Wiki-decentralized blockchain My idea is that 'de-centralization' it is not as it appears so I start to use Category Theory to un-lock this 'blocks concept' because there is something that does not come back to me in all this 'inviolability' because we talk about just a simply P2P way (nodes, data,transactions..) 1 propagation 2 over a network 3 but the underlying layer is to the extend that this propagation is represented like a math object and now is useful also to talk about Feynman Propagator of a Scalar Field 1 : like algebraic varieties or manifolds 2 : in this case we talk or Action Functional or about Group Action 3 : This remember in math s...
Read more

How to discover startup flags or command-line options for bitcoind?

How to discover startup flags or command-line options for bitcoind? I'd like to query the Bitcoin daemon (bitcoind) to find out what startup flags (command-line options) were sent to it on startup (or the current state if it has changed, e.g. -server=0/1 changing). For example, I may want to know if -addresstype, -disablewallet, -rescan, or -uacomment=<cmt> or some other flag has been set. Or for Namecoin, it would be very useful to know if -namehistory has been set. Is there an RPC or any other method to find out? Or, to ask the question a different way... src/bitcoind.cpp's bool AppInit(int argc, char* argv[]) method calls ParseParameters(argc, argv);, which is in src/util.cpp. In src/util.cpp we have: map<string, string> mapArgs; static map<string, vector<string> > _mapMultiArgs; const map<string, vector<string> >& mapMultiArgs = _mapMultiArgs; To store flags/options/args. I'd basically just like to get whatever is in tho...
Read more