Join GitHub today
GitHub is home to over 36 million developers working together to host and review code, manage projects, and build software together.Sign up
Improved Signature Hash Algorithm Proposal #950
I'm creating this issue to open community discussion and request feedback on an improved signature hash algorithm that I would like to propose. Obviously, a full blown DCP with a lot more details such as enumerating the affected opcodes, specifying the exact byte sizes of each field, deployment specifics, test vectors, etc will be required before any type of vote on this could happen. The intention here is to focus solely on the algorithm semantics as preliminary work toward that end.
For some background, the current signature hash algorithm works correctly by faithfully generating a hash of a portion of transactions according to the chosen signature hash type and verifying signatures against the hash with a given public key. However, unfortunately, the
That said, it would be even more useful if the signature committed to all input amounts since then it would be possible for the aforementioned devices to safely use the total amount being spent by the transaction for providing better user error messages and calculating transaction fees.
So, while it would be possible to change the consensus rule in question to include
The new signature hash algorithm should satisfy the following goals and requirements:
My proposal for an algorithm that satisfies all of these goals is as follows:
As an update to this, I've written some quick and dirty and completely unoptimized prototype code that calculates the signature hash using the proposal I laid out in the description and benchmarked it against a couple of transactions in order to compare. One of the transactions is a very typically encountered form and the other is a much larger and less frequent form. The code can surely be further improved and is not ready to be shared yet, but I did want to share some preliminary results thus far since they are extremely promising:
So, in the typical transaction case, this unoptimized code using the proposed algorithm is roughly 4,100% faster, and in the larger and less frequent transaction case, it is roughly 32,225% faster.
4,100% and 32,225% faster are a lot, great improvement! Is the existing code slow or is the prototype amazingly fast? I guess it's hard to compare to other coins' speed but it'd be even more interesting to see a benchmark with them, at least in terms of marketing Decred.
This was referenced
Jun 11, 2018
Possibly a dumb question, but I'm going to ask anyway. What about changing the signature hash calculation to:
That way, using a "streaming" hash calculator (ie, the raw github.com/dchest/blake256) we could store the internal hash state between inputs (the initial
Do you think there's not enough of a performance gain to justify the additional logic/memory required to keep track of the internal hash state at various stages or totally breaking the bitcoin standard (by moving the hash_type further down the list of hashed items) might be problematic or introduce a security issue?
It seems like a reasonable change worthy of consideration. The proposed algorithm is already a break from what Bitcoin does, so that's not a concern here. Also, I don't see any security issues the suggested permutation would introduce on the surface, though I'd certainly like to think through all of the possibilities to be sure.
We'd have to benchmark it to see the performance difference. I wouldn't expect there to be very much difference since we're only talking about a constant number of N bytes where N is very small (something like 77), but nevertheless there would likely be some gain since it should theoretically be possible to avoid 1 block of hashing. The real gain with the original proposal is moving from quadratic time to linear time though, so any potential gains here would definitely pale in comparison regardless.
That said, you can't actually store the intermediate internal state with the linked implementation because it's all done through an interface and the internal state is stored in an unexported struct, so you can't even type cast it to get at the internal state to clone it. It would, of course, be possible to expose it via a fork of the package which provides that functionality (I did something very similar for sha256 a long time ago in another context). I'm not sure going through the hassle of maintaining our own fork for just this purpose is worth the complexity here because where only talking about small value of N as previously mentioned, however, that doesn't necessarily mean the suggestion shouldn't be done as it would potentially allow other implementations to take advantage of it if they already have libs which support cloning the internal state at arbitrary points in the byte stream.