Bitcoin Forum
June 17, 2024, 12:08:37 AM *
News: Voting for pizza day contest
 
  Home Help Search Login Register More  
  Show Posts
Pages: « 1 2 3 4 5 6 7 8 [9] 10 11 12 13 14 15 16 »
161  Bitcoin / Development & Technical Discussion / Re: Send bitcoins to an unknown recipient on: February 13, 2011, 08:01:25 PM
I think this is a great idea Joe. There have been many, many, many requests for this functionality. The recent addition of the rescan feature will help. When you import the key, do a rescan to pick up the transaction that funds it. Then pay yourself. People want this for backups too.

I don't think you need to remove the key from the sender's wallet, it will still notice when it's spent. OTOH might be a good idea to remove it, otherwise you might accidentally spend it before the recipient inputs it.
162  Bitcoin / Development & Technical Discussion / Re: How will the merkel hash tree be stored? on: February 13, 2011, 07:33:12 PM
I agree that Satoshi's "200 bytes for backward compatibility" is something of a mystery. The 200 is probably a clue. It is quite a bit bigger than a Bitcoin block header. Might be about the size of a block header plus a dummy transaction.

There are still some ways to embed arbitrary data in Bitcoin transactions. AFAIK scriptSig data is not checked, and you could put anything at the front without invalidating any signatures. So a BitDNS hash could be stuck into the current Bitcoin block.
163  Bitcoin / Development & Technical Discussion / Re: How will the merkel hash tree be stored? on: February 13, 2011, 04:33:31 AM
The idea of a Merkle tree is you just store the root, and then when someone wants to convince you that something's in the tree, they produce the Merkle branch. The Merkle roots are in the block headers. Merkle branches are stored with transactions in wallets. So when you do a spend, in principle you can prove that your "in" transactions are legit, by providing the Merkle branches for all of them. However there are no data structures defined at this time for sending such information in the network.

Now this is not a matter of removing spent transactions; rather, it's a mode of operation that would allow nodes to forget all transactions, spent and unspent, and just keep block headers.

164  Bitcoin / Bitcoin Technical Support / Re: Cannot seem to toggle bit coins server switch. Help! on: February 12, 2011, 09:21:22 PM
Did you create the bitcoin.conf file? Should be in the same directory as wallet.dat. Also make sure you spell rpcpassword correctly.
165  Bitcoin / Development & Technical Discussion / Re: More divisibility required - move the decimal point on: February 12, 2011, 09:15:11 PM
The problem is this code in main.h:GetMinFee(), called from main.cpp:AcceptToMemoryPool()

601           // To limit dust spam, require a 0.01 fee if any output is less than 0.01
602           if (nMinFee < CENT)
603               foreach(const CTxOut& txout, vout)
604                   if (txout.nValue < CENT)
605                       nMinFee = CENT;


This will prevent clients from forwarding transactions with outputs < 0.01 btc. We can change this rule but not everyone upgrades so lower value transactions will propagate unreliably for months.

I suggest we figure out how to fix this once and for all, put in the new rule but set it to trigger only as of some block number in the future, and meanwhile do something cool in the client so people will want to upgrade before the rule change.
166  Bitcoin / Bitcoin Discussion / Re: Peer Review on: February 12, 2011, 04:35:37 AM
There was some discussion on the cryptography mailing list two years ago (much of it poor quality unfortunately IMO):

http://www.mail-archive.com/cryptography@metzdowd.com/msg09959.html

The thread links are screwed up after the first two messages; skip to:

http://www.mail-archive.com/cryptography@metzdowd.com/msg09966.html

and from there you can follow the Thread right-arrow at the top left.

There was another flurry of messages when the client was released:

http://www.mail-archive.com/cryptography@metzdowd.com/msg10142.html



167  Bitcoin / Bitcoin Discussion / Re: Core ideas of Bitcoin on: February 11, 2011, 12:46:28 AM
I would focus on two ideas:

How are bitcoins created?

Everyone on the network competes to be the first solve a computationally hard puzzle. The winner is rewarded with 50 new bitcoins. Puzzle difficulty is automatically adjusted so it takes about ten minutes to get a solution, creating a slow, manageable increase in the supply of bitcoins. The 50 bitcoin reward gets halved every four years, so the total number of bitcoins that will ever be created stays under 21 million.

How are bitcoins transferred?

Bitcoins are associated with cryptographic public keys controlled by the person who owns them. To transfer them to someone else (i.e. to make a payment) he broadcasts on the Bitcoin network a digital signature identifying the bitcoins he is transferring, along with the public key of the new owner. This information is stored in a distributed database maintained by the Bitcoin network that records the public keys that own every bitcoin. Bitcoin software validates the digital signature and updates the database to record the new owner of the bitcoins. He will then be able to transfer them to someone else in the future.


Note that I am not trying to explain how these two ideas are connected, via the block chain. That's just too hard to get across quickly.
168  Bitcoin / Development & Technical Discussion / Re: Network-wide cost of a transaction on: February 10, 2011, 11:31:02 PM
Verifying an ECDSA signature takes about 3 ms. Let's say the typical transaction has 2 inputs. Each transaction is verified twice, once alone and once in a block. That's 12 ms per node, times 10000 nodes for 120 cpu-seconds, aka 2 cpu-minutes or 1/30 cpu-hour. I'm going to say a computer draws 300W @ $0.10/kWh for electricity, for $0.03 per cpu-hour. YMMV. That makes $0.001 for cpu costs, a tenth of a cent, which appears to dominate.
169  Bitcoin / Development & Technical Discussion / Re: More divisibility required - move the decimal point on: February 10, 2011, 06:53:14 PM
Lots of good ideas here!

I like Gavin's idea to display full precision in the UI and allow it on payments.

I like ribuck's terminology: 100 bitcents in a bitcoin, 1000 millicents in a bitcent, 1000 microcents in a Millicent.

I like [mike]'s suggestion to allow miners to store information relating to costs and policies, and to adapt network behavior from that information. I'd suggest using it specifically to normalize the "anti-spam" limits: the 0.01 minimums for large-transaction fees and for free transactions. Clearly Bitcoin needs a way to adjust these values, and Mike's proposal seems like a good candidate.

I also wonder if the anti-spam rule shouldn't be changed, to trigger if the largest output is tiny, rather than for any output. In Gavin's example, outputs of 1.5 and 0.000001 change seem ok to me.
170  Economy / Marketplace / Re: Wanted: How I Found Freedom in an Unfree World on: February 10, 2011, 06:28:54 AM
I used to have a copy, but I think maybe I gave it away. I'll have to check my shelves.
171  Economy / Economics / Re: Bitcoin value on: February 10, 2011, 05:10:30 AM
IMO one way to get a handle on a reasonable value for 1 bitcoin is via this formula:

probability Bitcoin ultimately succeeds * value of 1 bitcoin if it succeeds

Bitcoin has the potential to become the dominant currency for large-scale electronic transactions worldwide. If this happens, bitcoins could be worth millions of dollars each.

So what is the probability of such a grandiose outcome? One in a million? Maybe so.

I see the recent increase in value as a rise in the consensus probability that Bitcoin will succeed.
172  Economy / Economics / Re: Bitcoin 10x parity. When will 1BTC=10USD? Vote! on: February 10, 2011, 04:38:43 AM
You're missing Oct-Dec
173  Bitcoin / Development & Technical Discussion / Displaying bitcoins in wallet on: February 10, 2011, 12:43:33 AM
I have enhanced the bc_key program to print interesting information about transactions found in the wallet file.

https://github.com/halfinney/bc_key

Run it as:

Code:
./bc_key EVERYTHING ~/.bitcoin/wallet.dat

(substitute your own wallet.dat location on mac and windows)

This dumps everything in the wallet, including keys and address book, but let's just look at transactions:

Code:
./bc_key EVERYTHING ~/.bitcoin/wallet.dat | grep ^tx

I'll go ahead and violate my own privacy because I want to make a point. Here's my output:

Code:
tx 011104eddf3afd4e1133996e3e2a9c7f16ed1f9dfa922493612bab9b8be19f0e    1.50000000 12gHtU8z4HNymJUBetcyY2MU8CYYfszq5X 2011/01/22 spent
tx 5fa35fa2e753c8997aaca3b1cb434f218884d95ae8803a0ee7ff8eee298ba00f    3.00000000 1BPE6sLdYn8zoRH2ovEWiqQH4NRbyAAHNK 2011/01/22 change spent
tx cff5962c80af06506d6583710fdbde01b95e0bf4a37df27af82ee5038b241016    9.00000000 1NiihskVid2GTWEJjKDaft67aFkeCJTTaE 2011/02/06 change
tx 31989da39c18a351fb393b05d7d66efd69cf1cc64958d67a5c49189e28402b1f    0.50000000 157a7eFdnTg89gPZ5wWPjX1TMVL3ffeDSh 2011/01/28 change
tx a5a88c6af09b9bcd21a7ee0e0c25ce912a0ccabd90a5a6d8a5644c7b6c519321    6.00000000 payment                            2011/01/30 spent
tx b6f4b9239544d864d5fbbfce5bc6d6333227e2b6db8aa0d35beba3bcf12b212d   12.00000000 1513Z4iDpW1K3qyknHUhwxhXy6H5aYd6q6 2011/01/30 spent
tx 061ef85f7936b138675e5c6b01c67ddbb8710aa9c00dffdd1859e2e0b231ce47    3.00000000 payment                            2011/02/01 spent
tx 835d37f77fc980efa21771e3fefbd79d9a20f2f69d3d0517d99f86aeecae464a  997.00000000 1F4YL3tYS1Y4dEvCUppwMjggi2imgJogVW 2011/01/20 change spent
tx 3ed3602d07e3f16f90f4966c502e5fcccb7e13faacc0053e9558e91a93a9a24f    3.00000000 1J6ToHCuN6jeniL7wD2zJwxhRUv2V6TLXW 2011/01/30 change spent
tx 78537330713ec5c92befd3e1a91c754198ee14877c02d8888c899280d0a49c58  994.00000000 1K8THF4Qkr5mMKjQRJe1xW33ZYoUrgtUHL 2011/01/20 change
tx 82621223fccb83122edda411f941c729929507a21bed320d1a9af6caa12dc159 1000.00000000 1KeWUnmZZUNDSeWKf9pqZmMdtkeJ5jENnX 2011/01/02 spent
tx 5fd3fed9bef47df2c95255b863bf989b027121bfcedd692d08888ba704130c7a    5.00000000 19MvB9acQ4wx4GtGxBwTamMkfHPVSBWY3Z 2011/01/22 change spent
tx 9555b4b8e84e6e5b045847fe86d6bb82df67e4360a897b485dbd8a76e0b46b83   10.00000000 1NC55QPMZqtpRNiRvkBatNvZLrXT5XqnRR 2011/02/03 change spent
tx 3a3b74721cc6af482bcc8b6722f80a87a9de103ee26a67975a2eee69328a3b92    6.00000000 1513Z4iDpW1K3qyknHUhwxhXy6H5aYd6q6 2011/01/20 spent
tx 4c9bb949f106cfe6bed53415e7dcb86f5c93603434c65ca6423d5de1eabafa92    1.25000000 12gHtU8z4HNymJUBetcyY2MU8CYYfszq5X 2011/01/22 spent
tx 03f87b3c1ed4231e64a781ce2f8c10c03e7a3f6439389c97af640e1e63eb29b0    0.25000000 1LKRbsyxiSi3zfHKyumEH8W7fSQapapnnw 2011/01/28 change
tx a97511426aac9be884236578060293a1b6783d4c7467288bf89436bfc38feec9    3.00000000 payment                            2011/01/30 spent
tx 230fec2b39bc56ef359a5c078505b8aac0d8221c5109dd0fa8f98ddd667ab8d3   18.87000000 12BxP2C6aj2KT5fsnNdiyVMKfhm9tu1MK4 2011/02/01
tx 7b8cb378bc8f15e98a8f94c2c20a8e552b6dd785f3863c1baac314e8b8d56ada    6.00000000 1513Z4iDpW1K3qyknHUhwxhXy6H5aYd6q6 2011/01/30 spent
tx ca43a17aa52c670e96c77a752552d502016355e2c7018ed4c930215e8366a9da    6.00000000 1513Z4iDpW1K3qyknHUhwxhXy6H5aYd6q6 2011/01/20 spent

The big number is the transaction ID, suitable for plugging into blockexplorer.com. Next is the bitcoin amount, your address that received the bitcoins, and the date of the transaction. Finally come the optional words change and spent. Change means this transaction produced change as a side effect of a payment you made to others, and the address shown is the change address, which is largely hidden in the client UI. Spent means that the bitcoin(s) associated with this transaction have been spent and are no longer available.

There are basically three types of wallet transactions. First are payments from someone else to a wallet key. Next are payments to others which happen to exactly use up one or more available transactions, with nothing left over. These are shown as "payment" in the address field and are always marked as spent. Last are payments where there were bitcoins left over, which get returned to a new address. These are the ones which are shown as change.

To see the transactions which are available for spending, filter out the spent ones with grep -v:

Code:
./bc_key EVERYTHING ~/.bitcoin/wallet.dat | grep ^tx | grep -v spent\$


Code:
tx cff5962c80af06506d6583710fdbde01b95e0bf4a37df27af82ee5038b241016    9.00000000 1NiihskVid2GTWEJjKDaft67aFkeCJTTaE 2011/02/06 change
tx 31989da39c18a351fb393b05d7d66efd69cf1cc64958d67a5c49189e28402b1f    0.50000000 157a7eFdnTg89gPZ5wWPjX1TMVL3ffeDSh 2011/01/28 change
tx 78537330713ec5c92befd3e1a91c754198ee14877c02d8888c899280d0a49c58  994.00000000 1K8THF4Qkr5mMKjQRJe1xW33ZYoUrgtUHL 2011/01/20 change
tx 03f87b3c1ed4231e64a781ce2f8c10c03e7a3f6439389c97af640e1e63eb29b0    0.25000000 1LKRbsyxiSi3zfHKyumEH8W7fSQapapnnw 2011/01/28 change
tx 230fec2b39bc56ef359a5c078505b8aac0d8221c5109dd0fa8f98ddd667ab8d3   18.87000000 12BxP2C6aj2KT5fsnNdiyVMKfhm9tu1MK4 2011/02/01

These are really my "bitcoins". They are what I have available to spend. The sum of the bitcoin amounts should equal my wallet balance. Any spend I make will come from one or more of these transactions. Generally, the Bitcoin client will try to combine one or more small transactions to make a payment, otherwise it will use the smallest single transaction capable of funding the payment.

Although my wallet doesn't show it too clearly, it's not unusual for a single Bitcoin address to be funded by multiple transactions. But for making payments, this is basically irrelevant. Individual transactions are picked to fund payments without regard to whether some of them happen to use the same address.
174  Bitcoin / Development & Technical Discussion / Re: Sppliting/merging wallets on: February 09, 2011, 06:16:50 PM
People talk about moving keys/addresses, but also it is important to move the transactions. Bitcoin is a transaction based system. Your keys authorize (sign) payments, but the payments actually come from the transactions you have received and which are in your wallet. If you're splitting off some keys into another wallet, you need to move the transactions that fund those keys, or they won't be able to do anything. (Should move address book and account entries too.)

175  Bitcoin / Development & Technical Discussion / Re: Speeding up signature verification on: February 08, 2011, 09:08:58 PM
I've put the code up at github. I'm a C programmer more than C++; it shows.

https://github.com/halfinney/bitcoin/tree/secp256k1

Here's a self contained test program that compares the speeds. Build with -lcrypto.

Code:
#include <stdio.h>
#include <sys/time.h>
#include <openssl/ec.h>
#include <openssl/ecdsa.h>
#include <openssl/evp.h>

#define REPS 1000


// Split a secp256k1 exponent k into two smaller ones k1 and k2 such that for any point Y,
// k*Y = k1*Y + k2*Y', where Y' = lambda*Y is very fast
static int
splitk (BIGNUM *bnk1, BIGNUM *bnk2, const BIGNUM *bnk, const BIGNUM *bnn, BN_CTX *ctx)
{
    BIGNUM *bnc1 = BN_new();
    BIGNUM *bnc2 = BN_new();
    BIGNUM *bnt1 = BN_new();
    BIGNUM *bnt2 = BN_new();
    BIGNUM *bnn2 = BN_new();
    static unsigned char a1b2[] = {
        0x30, 0x86, 0xd2, 0x21, 0xa7, 0xd4, 0x6b, 0xcd,
        0xe8, 0x6c, 0x90, 0xe4, 0x92, 0x84, 0xeb, 0x15,
    };
    static unsigned char b1m[] = {
        0xe4, 0x43, 0x7e, 0xd6, 0x01, 0x0e, 0x88, 0x28,
        0x6f, 0x54, 0x7f, 0xa9, 0x0a, 0xbf, 0xe4, 0xc3,
    };
    static unsigned char a2[] = {
        0x01, 0x14, 0xca, 0x50, 0xf7, 0xa8, 0xe2, 0xf3,
        0xf6, 0x57, 0xc1, 0x10, 0x8d, 0x9d, 0x44, 0xcf,
        0xd8,
    };
    BIGNUM *bna1b2 = BN_bin2bn(a1b2, sizeof(a1b2), NULL);
    BIGNUM *bnb1m = BN_bin2bn(b1m, sizeof(b1m), NULL);
    BIGNUM *bna2 = BN_bin2bn(a2, sizeof(a2), NULL);

    BN_rshift1(bnn2, bnn);
    BN_mul(bnc1, bnk, bna1b2, ctx);
    BN_add(bnc1, bnc1, bnn2);
    BN_div(bnc1, NULL, bnc1, bnn, ctx);
    BN_mul(bnc2, bnk, bnb1m, ctx);
    BN_add(bnc2, bnc2, bnn2);
    BN_div(bnc2, NULL, bnc2, bnn, ctx);

    BN_mul(bnt1, bnc1, bna1b2, ctx);
    BN_mul(bnt2, bnc2, bna2, ctx);
    BN_add(bnt1, bnt1, bnt2);
    BN_sub(bnk1, bnk, bnt1);
    BN_mul(bnt1, bnc1, bnb1m, ctx);
    BN_mul(bnt2, bnc2, bna1b2, ctx);
    BN_sub(bnk2, bnt1, bnt2);

    BN_free(bnc1);
    BN_free(bnc2);
    BN_free(bnt1);
    BN_free(bnt2);
    BN_free(bnn2);
    BN_free(bna1b2);
    BN_free(bnb1m);
    BN_free(bna2);
    return 0;
}

static int
secp256k1Verify(const unsigned char hash[32], const unsigned char *dersig, size_t sigsize, const EC_KEY *pkey)
{
    int rslt = 0;;
    const EC_GROUP *group = EC_KEY_get0_group(pkey);
    const EC_POINT *Y = EC_KEY_get0_public_key(pkey);
    const EC_POINT *G = EC_GROUP_get0_generator(group);
    EC_POINT *Glam = EC_POINT_new(group);
    EC_POINT *Ylam = EC_POINT_new(group);
    EC_POINT *R = EC_POINT_new(group);
    const EC_POINT *Points[3];
    const BIGNUM *bnexps[3];
    BIGNUM *bnp = BN_new();
    BIGNUM *bnn = BN_new();
    BIGNUM *bnx = BN_new();
    BIGNUM *bny = BN_new();
    BIGNUM *bnk = BN_new();
    BIGNUM *bnk1 = BN_new();
    BIGNUM *bnk2 = BN_new();
    BIGNUM *bnk1a = BN_new();
    BIGNUM *bnk2a = BN_new();
    BIGNUM *bnsinv = BN_new();
    BIGNUM *bnh = BN_bin2bn(hash, 32, NULL);
    static unsigned char beta[] = {
        0x7a, 0xe9, 0x6a, 0x2b, 0x65, 0x7c, 0x07, 0x10,
        0x6e, 0x64, 0x47, 0x9e, 0xac, 0x34, 0x34, 0xe9,
        0x9c, 0xf0, 0x49, 0x75, 0x12, 0xf5, 0x89, 0x95,
        0xc1, 0x39, 0x6c, 0x28, 0x71, 0x95, 0x01, 0xee,
    };
    BIGNUM *bnbeta = BN_bin2bn(beta, 32, NULL);
    BN_CTX *ctx = BN_CTX_new();
    ECDSA_SIG *sig = d2i_ECDSA_SIG(NULL, &dersig, sigsize);

    if (sig == NULL)
        goto done;

    EC_GROUP_get_curve_GFp(group, bnp, NULL, NULL, ctx);
    EC_GROUP_get_order(group, bnn, ctx);

    if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || BN_ucmp(sig->r, bnn) >= 0
        || BN_is_zero(sig->s) || BN_is_negative(sig->s) || BN_ucmp(sig->s, bnn) >= 0)
        goto done;

    EC_POINT_get_affine_coordinates_GFp(group, G, bnx, bny, ctx);
    BN_mod_mul(bnx, bnx, bnbeta, bnp, ctx);
    EC_POINT_set_affine_coordinates_GFp(group, Glam, bnx, bny, ctx);
    EC_POINT_get_affine_coordinates_GFp(group, Y, bnx, bny, ctx);
    BN_mod_mul(bnx, bnx, bnbeta, bnp, ctx);
    EC_POINT_set_affine_coordinates_GFp(group, Ylam, bnx, bny, ctx);

    Points[0] = Glam;
    Points[1] = Y;
    Points[2] = Ylam;

    BN_mod_inverse(bnsinv, sig->s, bnn, ctx);
    BN_mod_mul(bnk, bnh, bnsinv, bnn, ctx);
    splitk(bnk1, bnk2, bnk, bnn, ctx);
    bnexps[0] = bnk2;
    BN_mod_mul(bnk, sig->r, bnsinv, bnn, ctx);
    splitk(bnk1a, bnk2a, bnk, bnn, ctx);
    bnexps[1] = bnk1a;
    bnexps[2] = bnk2a;

    EC_POINTs_mul(group, R, bnk1, 3, Points, bnexps, ctx);
    EC_POINT_get_affine_coordinates_GFp(group, R, bnx, NULL, ctx);
    BN_mod(bnx, bnx, bnn, ctx);
    rslt = (BN_cmp(bnx, sig->r) == 0);

    ECDSA_SIG_free(sig);
done:
    EC_POINT_free(Glam);
    EC_POINT_free(Ylam);
    EC_POINT_free(R);
    BN_free(bnp);
    BN_free(bnn);
    BN_free(bnx);
    BN_free(bny);
    BN_free(bnk);
    BN_free(bnk1);
    BN_free(bnk2);
    BN_free(bnk1a);
    BN_free(bnk2a);
    BN_free(bnsinv);
    BN_free(bnh);
    BN_free(bnbeta);
    BN_CTX_free(ctx);
   
    return rslt;
}



main()
{
    EC_KEY *pkey;
    EC_GROUP *group;
    const EC_POINT *ecpub;
    unsigned char sig[100];
    unsigned siglen = sizeof(sig);
    unsigned char hash[32];
    struct timeval tv1, tv2;
    double time1, time2;
    int i;
    int rslt;

    ENGINE_load_builtin_engines();
    CRYPTO_malloc_init();

    group = EC_GROUP_new_by_curve_name(NID_secp256k1);
    pkey=EC_KEY_new();
    EC_KEY_set_group(pkey,group);
    EC_KEY_generate_key(pkey);
    ecpub = EC_KEY_get0_public_key(pkey);
    ECDSA_sign(0, hash, 32, sig, &siglen, pkey);

    rslt = ECDSA_verify(0, hash, 32, sig, siglen, pkey);
    printf("rslt = %d\n", rslt);

    rslt = secp256k1Verify(hash, sig, siglen, pkey);
    printf("rslt = %d\n", rslt);

    hash[0]++;

    rslt = ECDSA_verify(0, hash, 32, sig, siglen, pkey);
    printf("rslt = %d\n", rslt);

    rslt = secp256k1Verify(hash, sig, siglen, pkey);
    printf("rslt = %d\n", rslt);

    hash[0]--;

    gettimeofday(&tv1, NULL);
    for(i=0; i<REPS; i++) {
        rslt = ECDSA_verify(0, hash, 32, sig, siglen, pkey);
    }
    gettimeofday(&tv2, NULL);
    printf("rslt = %d\n", rslt);
    time1 = (tv2.tv_sec - tv1.tv_sec + (tv2.tv_usec - tv1.tv_usec)/1000000.) / REPS;
    printf("time: %g\n", time1);

    gettimeofday(&tv1, NULL);
    for(i=0; i<REPS; i++) {
        rslt = secp256k1Verify(hash, sig, siglen, pkey);
    }
    gettimeofday(&tv2, NULL);
    printf("rslt = %d\n", rslt);
    time2 = (tv2.tv_sec - tv1.tv_sec + (tv2.tv_usec - tv1.tv_usec)/1000000.) / REPS;
    printf("time: %g\n", time2);
    printf("%f%% speedup\n", (time1-time2)/time1);

    exit(0);
}
176  Bitcoin / Development & Technical Discussion / Re: Speeding up signature verification on: February 08, 2011, 07:11:52 AM
I implemented an optimized ECDSA verify for the secp256k1 curve used by Bitcoin, based on pages 125-129 of the Guide to Elliptic Curve Cryptography, by Hankerson, Menezes and Vanstone. I own the book but I also found a PDF on a Russian site which is more convenient.

secp256k1 uses the following prime for its x and y coordinates:

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

and the curve order is:

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

The first step is to compute values beta, lambda such that for any curve point Q = (x,y):

lambda * Q = (beta*x mod p, y)

This is the so-called efficiently computable endomorphism, and what it means is, you can multiply any curve point by this special value lambda very quickly, by doing a single mod-p multiply.

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

lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee


Given that we can multiply by lambda quickly, here is the trick to compute k*Q. First use the shortcut to compute Q' = lambda*Q. Next, k must be decomposed into two parts k1 and k2, each about half the width of n, such that:

k = k1 + k2*lambda mod n

Then

k*Q = (k1 + k2*lambda)*Q = k1*Q + k2*lambda*Q = k1*Q + k2*Q'

That last expression can be evaluated efficiently via a double multiply algorithm, and since k1 and k2 are half length, we get the speedup.

The missing piece is splitting k into k1 and k2. This uses the following 4 values:

a1 = 0x3086d221a7d46bcde86c90e49284eb15
b1 = -0xe4437ed6010e88286f547fa90abfe4c3
a2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8
b2 = 0x3086d221a7d46bcde86c90e49284eb15

(it's ok that a1 = b2)

Use these as follows to split k:

c1 = RoundToNearestInteger(b2*k/n)
c2 = RoundToNearestInteger(-b1*k/n)

k1 = k - c1*a1 - c2*a2
k2 = -c1*b1 - c2*b2


With all this, I measure about a 25% speedup on raw signature verifications. For Bitcoin, initial block load from a wifi-connected local node is reduced from:

real   36m21.537s
user   24m43.277s
sys   0m27.950s

to:

real   32m59.777s
user   18m21.145s
sys   0m28.262s

Not a big difference, and it would probably be even less significant when fetching over the net.
177  Bitcoin / Development & Technical Discussion / Speeding up signature verification on: February 07, 2011, 10:31:27 PM
In another thread, [mike] wrote:

I don't know of any algorithms that will make ECDSA much faster using GPUs. The best bet for speeding this up (assuming we care) is to exploit the special properties of the secp256k1 curve:

http://portal.acm.org/citation.cfm?id=1514739

http://www.hyperelliptic.org/tanja/KoblitzC.html

I'm trying to inplement the secp256k1 shortcut. Should have results shortly. Unfortunately I only expect about 20% speedup. We'll see.

I'm also looking at batch signature verification:

http://cseweb.ucsd.edu/~mihir/papers/batch.pdf

http://www.math.snu.ac.kr/~jhcheon/publications/2007/BatchVer_PKC2007_CL.pdf

This can theoretically speed up verification by almost a factor of 4 (table 6 in 2nd paper) if you have a lot of signatures in a batch. It requires a slight change in the ECDSA signature format: (r, s) is replaced by (R, s), where R is the EC point of which r is the x coordinate. This change could be applied retroactively, as R is calculated and discarded every time the sig is verified.

We do tend to have sigs in batches, namely blocks; sometimes several dozen or even hundreds, and this will grow. Batch verification returns true iff all sigs are valid. A good block should never have invalid signatures so it makes sense to batch the verify.

I need to research some security aspects, namely: does R need to be checked to see if it's on the curve (ie y^2 = x^3 + 7)? And what is an appropriate security parameter for the probability the batch verify test could be fooled? The papers talk about 2^80 but that seems too conservative.
178  Economy / Economics / Re: Dept Fiat Money Questions. on: February 07, 2011, 05:55:06 PM
So what does that mean for Bitcoin loans? Where would the money come from to pay interest?
179  Bitcoin / Project Development / Re: Bitcoin Monitor: web-based live ticker for activity on the Bitcoin network on: February 07, 2011, 03:28:06 AM
I really like this, sent a tip. Be nice to be able to see a larger window of time. FYI the cluster of transactions on the hour is the mining pool paying out.
180  Other / Meta / Re: Improving the Bitcoin Forum on: February 06, 2011, 06:31:54 PM
I'd like to see a separate forum for mining. Lately mining posts are filling the Development and Technical Discussion forum.
Pages: « 1 2 3 4 5 6 7 8 [9] 10 11 12 13 14 15 16 »
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!