If you want to share your ideas …
The other ideas were mostly language related (C#) which is why I didn't mention them. For instance I've been experimenting with the new feature added in recent C# versions called ref structs. A ref readonly struct has been a successful optimization too. Another idea was playing around with underlying integer type (UInt32 versus UInt64) and to use 32-bit or half of a UInt64 which later I found an article explaining an optimization for Curve25519 which uses radix 2 51 representation instead. Basically I've started the optimization from the lowest part which is the integer type and all the basic arithmetic. If there is interest, I could start a topic and share my findings when I'm done optimizing ECC in near future.
|
|
|
One of the main reasons for your code being slow is that you are using BigInteger, or more precisely an arbitrary length integer. The implementation of BigInteger is also known to be not-optimized which contributed to it being slow. Optimization of BigInteger itself could help increase speed by a factor of 5 to 10. Replacing it with a fixed length integer increases the speed by a factor of 20. Replacing methods such as Add, Subtract, Multiply,... with their modular alternatives (AddMod, MultMod,...) increases the speed by a factor of 10. There are some more ideas I'm currently exploring that would optimize ECC further. I've actually started a topic about optimization here 4 month ago but didn't receive any reply so the ideas are kinda on pause right now.
|
|
|
Why are you looking for that if you don't mind?
I'm currently refactoring the Script part of Bitcoin.Net library and writing a BlockVerifier + TransactionVerifier classes and the SigOpCount method needs testing.
|
|
|
That is only testing the case where number of SigOps exceeds the maximum with a very simple mock script.
|
|
|
I'm trying to make sense of how sigops are supposed to be counted and although I think I've figured it out but since it makes little sense I'd like to see some test vectors. Hopefully something like SignatureScript:Foo SigOpCount:m; PubkeyScript:Bar SigOpCount:n.
PS. Is there any limit (consensus-wise not standard-wise) per transaction or is the limit only per block?
|
|
|
I've added address input type to The FinderOuter, will commit the code today (need to do some more tests). Edit: The code is now updated to let you find the correct base-58 encoded address with missing characters at known locations. With the following input I can not find any valid address. Other characters might also be wrong. 1****nN36wEjR279pvwMYyPaVi
|
|
|
You mean integers?
Yes, both math and English failed me at the same time
|
|
|
Did you compute efficient power ladders for each value? There is a factor of 100 difference in speed between e.g. a hamming weight 1 256-bit exponent and a hamming 128 256-bit exponent. It won't be that big a difference, but you can't assume the speed is similar just because the process is similar. Good to know. I'm just using .net core's arbitrary length integers and a quick benchmark didn't show any difference.
|
|
|
Nope, there are three solutions to the cuberoot. Which is also an answer to your question: there are more possibilities.
Shouldn't it be only one solution since we are only working with positive integers? (I haven't checked for this post but the cuberoot is also likely more expensive to calculate).
On secp256k1 thanks to P ≡ 7 (mod 9) we can compute cube root by computing one side to the power of [(p+2)/9] x = ModPow(y^2 - 7, (P+2)/9, P)
Considering the fact that we compute square root in a similar fashion thanks to P ≡ 3 (mod 4): y = ModPow(x^3 + 7, (P+1)/4, P)
And assuming there is no other faster method that I don't know about, they are pretty much of the same speed. Also ignoring the fact that finding y (square root) has a possible additional step of negating y. PS. ModPow above is modular power, in .net it is found under System.Numerics.BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus); and in python it is same pow method with 3 inputs with the same order (value, exponent, modulus).
|
|
|
I'm in the same boat. The basics of bitcoin script language are pretty easy, the problem I've faced is the special cases and undocumented exceptions. Unfortunately the only way to fully understand scripts your only option is to look at the bitcoin core source code (C++ code), start here. Suppose I create a timelocked script or multisig script, how do I execute that script live or on the testnet?
This answer by me may help you get started on pay to (witness) script hash script types: https://bitcoin.stackexchange.com/a/93733/87716
|
|
|
Hi! can you elaborate a bit more about the solution? why the OP_NOP is relevant?
I was hard coding test vectors and missed that particular one at the beginning so I was confused about how things should work, that is why it was relevant. Now I understand the process of executing OP_CheckSig better which goes like this: - Replace the SignatureScript of the transaction you are verifying with the same script1 that contains that OP_CheckSig. - Remove all signatures that are the same as the one this OP is verifying because a signature can not sign itself. So when we want to evaluate Sig1+pub1 in the following script OP_Foo OP_Bar <Push_Sig2> <Push_Sig1> <Push_Sig1> <Push_pub1> OP_CheckSig OP_FooBar
We replace the SignatureScript of the transaction with OP_Foo OP_Bar <Push_Sig2> <Push_pub1> OP_CheckSig OP_FooBar
Foo Bar ops are any OP code except OP_CodeSeparator. [1] A tiny little fact that makes a huge difference and is not found in any documentation or at least no clearly.
|
|
|
In particular I'm talking about this test vector in bitcoin core: https://github.com/bitcoin/bitcoin/blob/b53af72b8276e8a23915d38fe459889cccb56f50/src/test/data/tx_valid.json#L167-L169["CHECKSIG is legal in scriptSigs"], [[["ccf7f4053a02e653c36ac75c891b7496d0dc5ce5214f6c913d9cf8f1329ebee0", 0, "DUP HASH160 0x14 0xee5a6aa40facefb2655ac23c0c28c57c65c41f9b EQUALVERIFY CHECKSIG"]], "0100000001e0be9e32f1f89c3d916c4f21e55cdcd096741b895cc76ac353e6023a05f4f7cc00000000d86149304602210086e5f736a2c3622ebb62bd9d93d8e5d76508b98be922b97160edc3dcca6d8c47022100b23c312ac232a4473f19d2aeb95ab7bdf2b65518911a0d72d50e38b5dd31dc820121038479a0fa998cd35259a2ef0a7a5c68662c1474f88ccb6d08a7677bbec7f22041ac4730440220508fa761865c8abd81244a168392876ee1d94e8ed83897066b5e2df2400dad24022043f5ee7538e87e9c6aef7ef55133d3e51da7cc522830a9c4d736977a76ef755c0121038479a0fa998cd35259a2ef0a7a5c68662c1474f88ccb6d08a7677bbec7f22041ffffffff010000000000000000016a00000000", "P2SH"],
SignatureScript is OP_NOP <PushSig1> <PushPub> OP_CheckSig <PushSig2> <PushPub>PubkeyScript is OP_DUP OP_HASH160 <PushHash> OP_EqualVerify OP_CheckSigSig2 verifies as it should (hash digest for signing is the same as ever) but I can't figure out what is being signed for Sig1, using the same PubkeyScript doesn't work (it is also evident from signature being different assuming it was deterministic).
Edit: never mind, I figured it out. I was removing more than I should have and also was missing the first OP_NOP. If anyone is interested, this is what the first OP_CheckSig hashes: 0100000001e0be9e32f1f89c3d916c4f21e55cdcd096741b895cc76ac353e6023a05f4f7cc000000008e6121038479a0fa998cd35259a2ef0a7a5c68662c1474f88ccb6d08a7677bbec7f22041ac4730440220508fa761865c8abd81244a168392876ee1d94e8ed83897066b5e2df2400dad24022043f5ee7538e87e9c6aef7ef55133d3e51da7cc522830a9c4d736977a76ef755c0121038479a0fa998cd35259a2ef0a7a5c68662c1474f88ccb6d08a7677bbec7f22041ffffffff010000000000000000016a0000000001000000
|
|
|
Thanks Dave for the offer, I really appreciate it. @ETFbitcoin helped me find a mistake in my difficulty assessment which makes it a bit harder for me to find blocks in a competing way. I still haven't had time to fix that part. I will post an update here if I could successfully fix it in which case I may be able to broadcast it myself since the bug doesn't seem to be with my P2PNetwork implementation anymore.
|
|
|
~ 1500 keys/sec (cpu Intel Pentium b960)
Thanks for sharing the rate. Your speed seems a lot higher than mine considering your much weaker CPU compared to mine (core i3-6100). It would be great if you could share the code publicly though.
|
|
|
That's certainly wasteful of resource (especially if you have slow connection), i assume software you use can't connect to Bitcoin Core client?
P.S. i have fully synced testnet full node (originally used to learn more about Bitcoin, but eventually only used to test LN in past), PM me if you trust me to broadcast it.
Thanks for the offer. The problem is not trust though since it is TestNet and it is a block, the problem is that I'm already wasting a lot of time starting to mine the next block and by the time I copy the result and send it to you it could be already too late and you could end up in a "fork". I've already sent you a block (#1671095) I found in ~5 min in PM though. Edit: ... someone else found the same block after 20 minutes.
|
|
|
what HCP suggested might be your best option,
Did you mean "ETFbitcoin" or was one comment deleted? I think the testnet blockchain is similar to the size of the litecoin blockchain and on my dual core 2GHz laptop, it seemed to take only about 8 hours to download and store the entire thing. It's not the best but if you really need it it's not that bad - load it up before sleep and wake up with the full sync.
That is 22.5 GB blockchain, ignoring the chainstate. It's a bit high just to broadcast one block, not to mention eventually I am going to download it with my own code as soon as I can fix my P2PNetwork namespace which is why I don't want to do it twice.
|
|
|
and if you know Adress or Compressed Adress, then i can give you my Script (php language), instruction. its easy. Could you also share the speed you've reached in keys/second? I'm at a very low speed of ~1200 although there is no restriction on number of missing chars or position of them.
|
|
|
Doesn't submitblock command require the node to be fully synced? I remember reading that it first "verifies" the block before broadcasting it which would require being synced.
|
|
|
I have a transaction stuck in TestNet which is not being mined, so I decided to mine it myself. The problem is that Denovo's P2P network implementation is incomplete so I can't broadcast the block I find, which is why I'm looking for a workaround to broadcast that block. Mining... Finished elapsed time: 00:02:49.4430433 block height: 1670930 block header: 000000207afc873c6dd49c55a8ec591947e65ea8e3c993f67ba5e5f8b522e35e000000007fbb3f2100ca7f1af3dc16b448f3a94f0e0556a4c86fb6a1f6fa316ebc615df81dc0795effff001d1418859f block hash: 00000000eadf03548790f5aefd32f4c11b131b29229664a9a039fd1ad3466ea3
|
|
|
|