Bitcoin Forum
December 05, 2016, 02:39:34 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: « 1 [2]  All
  Print  
Author Topic: Speeding up signature verification  (Read 20712 times)
MatthewLM
Legendary
*
Offline Offline

Activity: 1092



View Profile WWW
January 13, 2013, 06:28:23 PM
 #21

If you are to use a GPU, why not also use the CPU along side it? If time is important, then surely using as much processing power as is available is recommended. Understandably the are other considerations such as power usage and the operation of other programs on the same system.

At least you can take advantage of multiple CPU cores with multiple threads.

Bitcoin Extra Wallet | Peercoin Android Wallet
BTC: 1D5A1q5d192j5gYuWiP3CSE5fcaaZxe6E9  PPC: PH7fVn1Xs7nkUFmdwCX2ZRYfLPCSwGxAq9
There are several different types of Bitcoin clients. Server-assisted clients like blockchain.info rely on centralized servers to do their network verification for them. Although the server can't steal the client's bitcoins directly, it can easily execute double-spending-style attacks against the client.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
smtp
Member
**
Offline Offline

Activity: 70


View Profile
January 13, 2013, 06:48:35 PM
 #22

If you are to use a GPU, why not also use the CPU along side it? If time is important, then surely using as much processing power as is available is recommended. Understandably the are other considerations such as power usage and the operation of other programs on the same system.

At least you can take advantage of multiple CPU cores with multiple threads.
Of course, but two important points must/should be decided (as usual):

1) Effort: Who should write all this coding (for which GPUs?) and merge it with bitcoin-0.?. (how much real time spend of a (few) developper(s)?
2) Benefit: How big is the average profit of this new code (by all bitcoin-client users)?

smtp
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
January 13, 2013, 06:53:55 PM
 #23

I simply should concatenate my current block chain (3 files) into 1 huge file (almost 4.9 GB), name this "bootstrap.dat" and 0.7.* will load this without signature-checking into the bitcoin-client if I start it (and of course build a new blkindex.dat)?

It will load it, but only the first 193000 blocks will be done without signature checking.

Also, I think 0.7.x has a bug where no more than 2G of bootstrap.dat is loaded anyway. You can use -loadblock=file1 -loadblock=file2, ... though.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
smtp
Member
**
Offline Offline

Activity: 70


View Profile
January 13, 2013, 07:13:43 PM
 #24

I simply should concatenate my current block chain (3 files) into 1 huge file (almost 4.9 GB), name this "bootstrap.dat" and 0.7.* will load this without signature-checking into the bitcoin-client if I start it (and of course build a new blkindex.dat)?

It will load it, but only the first 193000 blocks will be done without signature checking.

Also, I think 0.7.x has a bug where no more than 2G of bootstrap.dat is loaded anyway. You can use -loadblock=file1 -loadblock=file2, ... though.

All this I knew -- I thought that I had misunderstood that this 193000 blocks limit was hardcoded into the client. :-/

I did it with -loadblock... already, thus my personal annoying real-time expierence.
Thx, anyway, then I can stop my try now -- I just have started 0.7.1 with this 4.9 GB bootstrap.dat and looked forward whether all will succeed.
193000 blocks looks about as 216000 blocks, but the sad truth is: only about 50 % of the transactions and this is what matters. :-/

smtp
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
January 13, 2013, 08:24:49 PM
 #25

All this I knew -- I thought that I had misunderstood that this 193000 blocks limit was hardcoded into the client. :-/

Yes, it is hardcoded. 0.7.x have a latest checkpoint at 193000. The current development code has an extra one at 210000.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Diapolo
Hero Member
*****
Offline Offline

Activity: 769



View Profile WWW
January 14, 2013, 08:04:31 AM
 #26

But before the last checkpoint (=exactly what is stored in bootstrap.dat), signature checking is disabled anyway (and this hasn't changed in 0.Cool.
Huh Do I feel victim to a misunderstanding or do you just have told me a trick? Smiley

I simply should concatenate my current block chain (3 files) into 1 huge file (almost 4.9 GB), name this "bootstrap.dat" and 0.7.* will load this without signature-checking into the bitcoin-client if I start it (and of course build a new blkindex.dat)?

smtp

You perhaps won't succeed with a file > 4GB. There were some limits with fseek or such as far as I remember.

Dia

Liked my former work for Bitcoin Core? Drop me a donation via:
1PwnvixzVAKnAqp8LCV8iuv7ohzX2pbn5x
bitcoin:1PwnvixzVAKnAqp8LCV8iuv7ohzX2pbn5x?label=Diapolo
smtp
Member
**
Offline Offline

Activity: 70


View Profile
January 14, 2013, 09:06:58 AM
 #27

You perhaps won't succeed with a file > 4GB. There were some limits with fseek or such as far as I remember.
On 64-bit Linux the limit is 2^63 as filepos and I guess on 32-bit Linux 2^31 (at least, but depending on size of data_type long), but already the (official) 193000-bootstrap file has > 2GB size.

Appendum: I should add: Really it depends on the filesystem you are using. I talked about Ext-2, Ext-3 and Ext-4 FS - (the default Linux filesystems).

smtp
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
January 14, 2013, 08:34:40 PM
 #28

0.7.x has indeed a bug that it needs the ability to seek to positions in block files being imported. This limits it to 2 GB on some systems.

The current git head code doesn't need this, and can import blocks from arbitrary-sized files.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
deuteragenie
Newbie
*
Offline Offline

Activity: 23


View Profile
January 29, 2014, 10:00:48 PM
 #29


The book tells (well, hints) how to compute lambda and beta, and here are the values I found:
lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee


Isn't lambda a solution of l*l+l=-1 mod n ?

If that's the case, there are actually two possible lambdas:

5363AD4CC05C30E0A5261C028812645A122E22EA20816678DF02967C1B23BD72
and
AC9C52B33FA3CF1F5AD9E3FD77ED9BA4A880B9FC8EC739C2E0CFC810B51283CE

What made you choose the smaller one ?
ysangkok
Newbie
*
Offline Offline

Activity: 3


View Profile
January 04, 2015, 11:59:50 PM
 #30

Risk vs reward. No offense to Hal, but 25% isn't a very big improvement, and signature verification is something that absolutely must work correctly. Get it wrong and people can lose a lot of money very quickly. Why risk it?

The secp256k1-specific optimization has been implemented, and there's a pull request to integrate it in the reference client. It does indeed achieve some 20% improvement.

What smtp asked was about the parallel batch verification, with potentially much higher speedsup (Hal mentioned x4). The problem is that this is a much more invasive change, and the risk of getting crypto stuff wrong is extremely high. It's also not certain which degree of speedup is possible, as we need to do recovery of R before batch verification is possible (and changing this requires a hard fork basically, as the signatures are part of the scripting rules).

That said, if someone is interested in investigating, and potentially supplying a patch that is well testable... by all means, do so.

It looks as if this code is slated for inclusion in 0.10, but the given reasons are not performance, but security:

https://github.com/bitcoin/bitcoin/blob/0.10/doc/release-notes.md#improved-signing-security

Is the new code doing the batch verification previously mentioned or is it doing the "some 20%" optimization? Or maybe the optimizations vanished to mitigate timing attacks?

Thanks in advance.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2016



View Profile
January 05, 2015, 01:53:35 AM
 #31

5363AD4CC05C30E0A5261C028812645A122E22EA20816678DF02967C1B23BD72
and
AC9C52B33FA3CF1F5AD9E3FD77ED9BA4A880B9FC8EC739C2E0CFC810B51283CE
What made you choose the smaller one ?
Lambda (mod N) has multiplicative order three, the other value is just lambda applied twice. Unfortunately, it appears is no way to use that for additional speedups because the is no small orthogonal basis that cam be formed from a reduction on [n, lambda, lambda^2].

It looks as if this code is slated for inclusion in 0.10, but the given reasons are not performance, but security:
Absolutely not. The changes in 0.10 you're referring to are exclusively related to signing, as the release notes say, and do not change verification.

Quote
Is the new code doing the batch verification previously mentioned or is it doing the "some 20%" optimization? Or maybe the optimizations vanished to mitigate timing attacks?
Verification in libsecp256k1 on x86_64 is now probably closer to ten times faster than OpenSSL's implementation, but the software is very much still under development. This is without batch validation. True batch validation requires additional side information to have any hope of being faster, and even with it the speed increase is not that enormous due to the additional blinding required to preserve security.
AlexGR
Legendary
*
Offline Offline

Activity: 1064



View Profile
April 26, 2016, 03:25:31 AM
 #32

Is there any downside in using SIMD instructions (loading multiple values in different segments of the same registers and performing "packed" SSE/AVX instructions for the math operations) to batch-process multiple signatures per thread?

It would theoretically get the cpu cycles per round much lower than doing it in a serial manner.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2016



View Profile
April 26, 2016, 04:45:49 AM
 #33

Is there any downside in using SIMD instructions (loading multiple values in different segments of the same registers and performing "packed" SSE/AVX instructions for the math operations) to batch-process multiple signatures per thread?

It would theoretically get the cpu cycles per round much lower than doing it in a serial manner.
You lose the 64,64->128 widening multiplies. The net result appears to be a loss of performance.

If someone was able to get the field arithmetic to operate usefully in parallel there wouldn't be a need to perform multiple verification at once to get performance gains; fwiw.

But actually getting it to be faster while losing the wide multiplies appears to be elusive. Even in the AVX-512 integer stuff I do not see a quadword multiply.



AlexGR
Legendary
*
Offline Offline

Activity: 1064



View Profile
April 26, 2016, 11:02:52 PM
 #34

Does this help at all?

https://en.wikipedia.org/wiki/CLMUL_instruction_set

http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/carry-less-multiplication-instruction-in-gcm-mode-paper.pdf

http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/polynomial-multiplication-instructions-paper.pdf

"Using the PCLMULQDQ instruction, the performance of ECC can be
boosted significantly on a range of IA processor cores, making it an
attractive option over other public key algorithms."

There are also some newer "regular" instructions that might be useful for speedups (mulx, adcx, adox): http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf

Quote

MULX Instruction
The mulx instruction is an extension of the existing mul instruction, with the
difference being in the effect on flags:
mulx dest_hi, dest_lo, src1
The instruction also uses an implicit src2 register, edx or rdx depending on
whether the 32-bit or 64-bit version is being used.
The operation is:
 dest_hi:dest_lo = src1 * r/edx
The reg/mem source operand src1 is multiplied by rdx/edx, and the result is
stored in the two destination registers dest_hi:dest_lo. No flags are
modified.
This provides two key advantages over the existing mul instruction:
- Greater flexibility in register usage, as current mul destination
registers are implicitly defined. With mulx, the destination registers
may be distinct from the source operands, so that the source
operands are not over-written.
- Since no flags are modified, mulx instructions can be mixed with
add-carry instructions without corrupting the carry chain.

ADCX/ADOX Instructions

The adcx and adox instructions are extensions of the adc instruction,
designed to support two separate carry chains. They are defined as:
adcx dest/src1, src2
adox dest/src1, src2
Both instructions compute the sum of src1 and src2 plus a carry-in and
generate an output sum dest and a carry-out. The difference between these
two instructions is that adcx uses the CF flag for the carry in and carry out
(leaving the OF flag unchanged), whereas the adox instruction uses the OF
flag for the carry in and carry out (leaving the CF flag unchanged).

The primary advantage of these instructions over adc is that they support two
independent carry chains. Note that the two carry chains can be initialized by
an instruction that clears both the CF and OF flags, for example “xor reg,reg”

As for AVX512, I think AVX512-DQ (Q=quadword) might do (some of) the job, but it will be too limited in use (xeons).
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2016



View Profile
April 27, 2016, 08:30:18 AM
 #35

"Using the PCLMULQDQ instruction, the performance of ECC can be
boosted significantly on a range of IA processor cores, making it an
attractive option over other public key algorithms."
Not irrelevant, the 'carryless multiply' is useful for characteristic-2 ECC, which only crazy people would use.

There are also some newer "regular" instructions that might be useful for speedups (mulcx, adcx, adox): http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf

Quote
MULX Instruction
ADCX/ADOX Instructions
Yes, these are somewhat useful... but are only in very new processors. E.g. I just got broadwell-ep chips that support ADCX a couple weeks ago (release april 1st). But they don't let us do things efficiently with SIMD, they just would likely make the existing approach somewhat faster if we use them.

Pages: « 1 [2]  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!