So I'm reviving an old thread here, but I'm interested in a slightly different application of deterministic key generation.  It seems like something that could integrated with pywallet very easily.  I'm sure I'm not the first person to suggest this, but I'm not finding other threads about it.

Rather than using passwords to deterministically generate your key, I'd like to use a random number generator to create a 256-bit Private-Key-Generator once.  This generator would be the first private key, GenKey, and then you get a semi-infinite sequence of new keys by simply following:


You wouldn't need the key stretching (at least that's what I'm assuming the iterations are for in the PBKDF2 module), because you're using full entropy in your original key.  Using this technique, you only need to backup your wallet once.  Sure, it links all your addresses together, but 99% of the time with the current wallet, if the attacker gets one key, he gets all of them, anyway.  And by using GenKey in each iteration, even if attacker gets PrivKey(i), he cannot determine any of the other keys.  My primary motivation is that I want to be able to put my GenKey into a QR code and store it in a safe-deposit box, and then I never have to worry about losing my private keys.  

With the current wallet, I only get a pool of 100 keys, and have to re-backup my wallet every time I run out.

Just for clarity of point, there's two separate events here:

(1) To create the transaction into the [(A and B) or C]-encumbered account, you need three addresses or public keys.
(2) To spend one of these encumbered transactions, you need to contact the third-party with a partially-signed transaction. (or use backup key, C)

These two situations have completely different use-cases.  Perhaps you make a weekly deposit to such account which is used as a savings account.  For years you might only use transaction (1), and only use (2) one time to move the money to a seller for a house.  There's no way around contacting the third-party to use (2)... this was actually the point of the entire exercise.  But unless you're using a pool of keys or one key for everything, you can't even give someone your own address without contacting the third party to get another B address.  If you use a single key for B, then all your transactions are linked.

I suppose the part about your own backup key is made easier if you use a Private-key-generator.  The actual secret is a 256-bit random number, A.  Then you can compute a semi-infinite sequence of private keys through:


or something to that effect.  You create the generator on the offline computer, and compute and copy 100,000 public keys to your online computer key pool.  Then you only need to store the single generator key A in the safety deposit box, which can be stored in a single QR code on one sheet of paper.  I'm sure I'm not the first person to think of this generator idea, but it seems like a feasible way for regular online wallets too.  That way you can backup the wallet once, ever.  

I guess this isn't so much about security, as it is more about privacy.  I really like the concept here, that you send yourself much, such that the only way to spend it is to get a second signature from a third-party who will do a two-factor authentication before offering their signature.

(A and B) or C

A:  Your normal, online wallet.
B:  Third-party verification website
C:  Backup key stored in safety deposit box

Casascius described this best:  it can be implemented such that when you tell your computer to spend some funds from one of these transactions, it will sign with private key A, and send the partial transaction to the third-party who will then, say, send you a text message asking "Did you authorize 23.7 BTC to be sent to address 1Ptk21Fjk38?".  When they receive confirmation, they sign it and broadcast it, making it final.  If the third-party goes out of business, you can always go to your safety deposit box to get key C, which is sufficient alone to spend the funds.

Here's my problem with this though.  There are numerous reasons it is good to use a different address for every transaction.  However, in this case, that different address amounts to changing A every time.  The problem is what about B and C?  No matter how you do it, the address of B and C must be visible to the blockchain at some point (either in the original transaction, or after getting spent in the case of Casascius' OP_CHECKSIG modification proposal).  If B or C is the same on every one of these transactions, then you have now created a verifiable link between every address A you ever used.  So how do you handle creating transactions that send money to this (AandB)orC-encumbered account and have different B and C addresses?

Let's look at Addr/PubKey B:
This is the easy one.  There are three options here:
(1) Third-party gives you a single key to use on every transaction.
(2) You periodically download a new batch of 1000 publickeys/addresses from B to be used until you run out and get more.
(3) The application queries the third-party and requests a new addr/key to be used before each transaction is constructed.

Option 1 is clearly the worst, but it's the easiest.  (If the service uses the same single addr/pubkey for every user, we don't have this problem, but that puts all users at risk if that private key is leaked...I wouldn't use that service)
Option 2 is probably the best, as it allows you to sync online or through an update packet every now and then, but mainly remain offline and sign transactions remotely.  (This is most relevant for systems that are entirely offline that want to sign these transaction types.
Option 3 is the best for always-online services, but puts a burden on you to have internet and for the 3rd party to be available, just to send money via this kind of transaction.

The problem here is that if you pick option 2 or 3, you have to develop extra infrastructure to handle the communication of keys/addr between parties.  Not terrible, but it's not trivial, either.

For Addr/PubKey C:
This is your key in your safety-deposit box.  This is the part that's a little more difficult.   The options are (1) and (2) above, because you can't query for a new address every time even if you wanted to.  My main concern is that if you use a batch of 10,000 keys, you probably won't be printing the QR codes of the private keys onto paper into your safety deposit box (it'd be a lot of pages).  But who knows what happens if you only store it on a USB key:  you might get the USB key out of storage to find out the memory is corrupted.  Sure, store the keys on multiple USB sticks and some ZIP disks.

This may not actually be a problem.  Perhaps Option 2 for both can just store 1,000,000 keys/addresses and you'll never run out.  But it is a concern/decision that will have to be addressed when this becomes a standard transaction type.  At the very least, software developers might consider including a feature allowing you to store pools of keys/addr to be used just for this purpose.  You would have a third-party pool, and a backup pool.  You "fill" both of them when you start this kind of account and the client will automatically pull addresses from each one into B and C fields every time you want to construct this kind of transaction.

So part of the discussion is about the length of acceptable keys, which would help drive the format for these multi-sig addresses.     Casascius... you mentioned in another thread that you actually type some addresses in by hand.  What is the reason for this?  So far, I have never needed to do it myself, and was wondering if you have special requirements, or if we anticipate a common scenario that people would be copying by hand (i.e. typing).  If so, then perhaps it's not ideal to push the multisig approach with long addresses.  It's okay if it's done occasionally, but if there's a common scenario that most users would run into semi-frequently, we probably should focus on keeping them short.

But difficulty is a floating point number, so I don't know how you can get there without doing floating point math.  The most straightforward way I know is simply what is in the client source code: 


Even I don't totally understand the calculation, but I think this is as simple as it gets, using some bit-math (shiftings, bit-and).  Be aware that the difficulty is typically a 32-bit number that looks like 1DAABBCC.  The first 8 bits (1D) are the "nShift" above, and the last 24 bits (AABBCC) contribute to the dDiff number.  It looks like to me that the "nShift" is the raw number of zero-bytes needed on the front of the hash (multiples of eight 0-bits), and the other 24 bits give you an adjustment factor.   Something like that...

The way I calculate the longest chain is to start with a pool of unorganized blocks, accessed by hash.  I go through all the blocks one-by-one, and follow them down to the genesis block (or the first block that I've already calculated) by following the "previous-hash" field, accumulating all the difficulty values as I go.  When I get to the "end", I walk back up the chain in the exact same order, and accumulate the difficulty-sums assigning them to each block as I go.  After that, I just find the block with the highest sum.   

The reason I can't just start at the genesis block and walk up is that "next-hash" is not initially defined.  And if the block chain forks anywhere, you would actually have two "next-hash" values, and you won't know which branch to follow without knowing the longest chain... but that's what we're trying to find!

But of course, you're going to need that difficulty calculation above to make it work.

I think we're promoting slightly different things here.  My only point is that this OP_CHECKSIG modification has some "different" behaviors than a "standard" multi-signature transaction, and thus, we should work for both to be supported as "standard" scripts.   I really like your idea, and fully support getting into the client design.  But I don't think it precludes us from having to answer Gavin's post about how to standardize multi-signature scripts that are currently possible without your modification.

I think it does help, in general, to consider how users could/would use these transactions, and then the message formats can be designed to accommodate.  But, upon rereading the original thread, I see that I slightly mis-understood the original intent of Gavin's proposal.  He's looking more for how these transactions will be encoded in the blockchain, not how people will use them.  So yes, my post was a little off-topic.   Feel free to ignore it then.  I'll recycle those mock-ups for a more-appropriate thread.

I see Casascius' point about changes to the OP_CHECKSIG improving the original request, but I don't think it precludes us from needing to have to come up with standard formats that don't use casascius' improvement.  Casascius' suggestion simplifies a lot of things, but does require all parties to be manually notified that they are part of a given transaction.  This may not always be preferable, and I think we have to accommodate more-explicit transaction types that are already possible, anyway (and to be used sooner than we can implement Casascius' suggestion).

In other words, I am siding with both, here:  I'd like to see casascius' change vetted and implemented if it seems secure (although nested scripts might open some very creative security problems, I don't know for sure).  But I think the original proposal Gavin presented still needs to be addressed.  In that regard, I'm not concerned about long strings.  Unless someone has a specific, common use-case that I'm not familiar with, addresses are almost always communicated via copy-and-paste into email/IM, or through QR code scans.  In this case, I don't see how it's really relevant how long it is, probably as long as it doesn't exceed half the length a QR code can handle (which is about 3 KB).

There's more uses to the multi-sig functionality than just what you're talking about.  I always think of a 2-of-3 transaction online, where the buyer puts 110%*purchase price into such a 2-of-3 transaction between seller, buyer and third-party.  When the goods arrive and the purchase is complete, both buyer and seller offer their signatures to give the 100% of purchase prices to the seller, and return 10% to the buyer.  If there is any dispute, no one gets the money until it is resolved.  If one of the parties is too stubborn or disappears, the other party can appeal to the third-party to get their signature, and give them the 10% for arbitrating.

In this case, the buyer created the 2-of-3 tx with two other parties, but the other two parties don't know about it until the buyer explicitly tells them.  I still like the idea, I was just commenting that it adds an extra step if you want all the other parties to know that they're involved.

-Eto

+1 for this idea. 

I have no comments about integration, release, and not forking the blockchain, in general.

The only concern is that other parties have no other way to know they are part of a particular transaction unless you send them the serialized string and the transaction hash.  They can see the string includes their address in the appropriate place and that it hashes to the "address" in the specified transaction.  This creates an extra step to "executing" a transaction, as it's not really complete until all parties are notified by the original sender about.

Of course, people don't have to use it. I do like this as an option.

-Eto

I think this is an arbitrary distinction.  Users themselves will need to communicate with their own clients to execute 1-of-2, 2-of-2, etc, transactions.  Providing a standard "code" for these will allow the users to know what they're doing.  If I'm telling my wife to put money in our 1-of-2 or 2-of-2 account, I give her the long code.  If I'm selling stuff on the internet, I use your suggestion (give buyer reg address, move it myself).  The key is to create the language.  People will use it as they feel is appropriate.

For these more complicated transactions, we'll need to come up with terminology and methodology for executing them.  We not only need to create the transactions, but also make an intuitive interface for spending them.   I suggest we make a "proposal" msg that users can import and choose to sign.  Each person can sign and pass the result to the next party.  Once the last party signs it, the client will tell them "This is a valid proposal!"  and be presented with a button for "Broadcast now!" or something like that


Click here for the full-sized image:  http://dl.dropbox.com/u/1139081/BitcoinImg/AdvTxDialogs.png

I left off the "save to file" button so it can be attached to emails instead of inline.  Of course, the Base58 there would be the exact serialization of the proposed Tx, with the single input and the proposed outputs.  Don't pry too deep into the details of the attached images:  they're just notional.  

I don't want to get too sidetracked debating the "average" MHash/s estimate, but I was conflicted about how to come up with a ballpark estimate.  I based it on the fact that present-day Intel chips get 2-8 MHash/s, and the AMDs get like 4-16 MHash/s.  However, most computers are Intel, so I sided with the average value there.  I considered that there would be a significant number of older computers, but also that there were going to be a significant number of AMDs offsetting them.  And even one computer with any decent graphics can add the value of 10 - 30 CPUs.

Guys, if someone has 55%+ of the network on their own and they have malicious intent, we're screwed.  Once a week they could do a huge double-spend or just start rewriting the blockchain for fun.   The value of BTC, and thus quantities of miners, would probably dissipate after the first or second week, making it even easier on subsequent weeks to throw in the KO punch.  The entire security of BTC is based on the assumption that no one has that much power.  I agree that there should be a plan in place for how to deal with such events, but I'm trying to focus on whether there's a way to avoid it to start. 

Right now, there's only a few entities in the world who can match the global hashrate, but I don't see how this is going to get any better.  I am looking for optimism about the future of BTC in this light.  There is not enough financial incentive for miners to invest in new hardware, and CPUs mine for net loss.  So, is the BTC network always going to be vulnerable to a botnet/gov't attack?  Or is there a reason to believe that things will pick up?  I know we'd like to believe value will jump up above $100/BTC which would certainly provide incentive, but if it doesn't happen before the generation rewards are cut in half, that could be the start of a downward spiral.

I originally decided not to go into byte-level detail on the TxOut scripts, but I have no idea why.  I've updated it to be a complete byte map now.  Also changed constants like "30" to "0x30" for clarification.  If it's not perfect, it's damned close! 

And now I've updated the Transaction bytemap with examples of each TxIn and TxOut type.  Once again, I've learned quite a bit about BTC since making the original illustrations, and so I thought it was a good idea to update it.



The full size image can be downloaded here:  http://dl.dropbox.com/u/1139081/BitcoinImg/TxBinaryMap.png

The only thing I'm not 100% sure about is the script field on a coinbase generation TxIn.  I'm pretty sure I read that mining pools use that field as an extra nonce, so that they can have all the connected workers hashing different things and avoid redundant computations (different script --> different Tx hash --> different merkle tree --> different merkle root).

Theymos, I think you are being way too optimistic about the consequences of such an attack.  Sure, the network may survive, but the value will drop dramatically, and a significant proportion of participants will flee.  You may not need high value for Bitcoin to work, but you do need users...

But I don't want to debate what the fallout would be of such an attack, I want to figure out if my calculations and concerns are justified, and brainstorm how this might be mitigated.  We can debate all day about why no one would/should want to attack the network like this, but people don't always have good reasons to do what they do, and we'd all be better off if it just weren't possible for anyone to do it.  How can we possibly incentivise people to contribute more compute power?  And do we need to? 

P.S. -- One very good reason for the attack could be that someone gets the opportunity to short-sell a couple million dollars worth of BTC.  By killing the network, he gets to keep the money.

In the case that there are two equal-difficulty-sum chains, the node processes whichever block it received first.  They won't discard the second block, but they won't be trying to extend it if they saw the other one first.   If MBC is behind Tor and the attacker studied the network latencies well, most miners will see the "legit" block first, and that "legit" chain will most definitely get extended first.  (I'm using "legit" here, because I don't know any other way to refer to the non-attacker chain... there is, of course, nothing wrong with the attacker's block except that that chain is unlikely to get extended)

If transactions carry over between from invalidated chains, then the attacker should send himself a small transaction using one of the outputs he used in the huge deposit transaction, to be included in the "legit" block while he waits for it.  By doing this, he guarantees that the large deposit is DOA on the new chain in case the nodes decide to carry it over.  Otherwise, it's possible that the deposit will be transferred to the new chain and the double-spend fails.

I really like vector76's hypothesis, and I recognize it's only speculation.  But it sounds like feasible, targeted attack.   It would also explain why there was no evidence on any others' systems of a forked blockchain.  MyBitcoin was one the only node that directly received this invalid block, and most other nodes probably had the soon-to-be-real block before MyBitcoin could forward it to peers.

Let's assume this is what happend.  My question is, how did the attacker receive his "goods" for the "fake coins" that he sent.  I presume it was a BTC withdrawal from MyBitcoin.  If so, then MyBitcoin had to construct the transaction while it was on the invalid blockchain.   I am assuming that other nodes receiving the transaction don't know what blockchain MyBitcoin thinks is the current one, they only care whether the TxOuts referenced are valid.  But there will be a problem if MBC uses outputs from the transaction it just received.

For instance:  If MBC only has 1000 BTC total in it's accounts.  The attacker deposits 5000 BTC using this attack, and then immediately withdraws it at 1 confirmation... there is no way for MyBitcoin to process the withdrawal request without using outputs of the transaction that will ultimately be invalid.  Then when the first transaction becomes invalid, so will the withdrawal.  The attacker gains nothing.

I presume that "standard logic" was being used to select TxOuts for withdrawals/transfers.  Probably used the oldest coins available, which most definitely wouldn't be the coins that MyBitcoin just received.  As long as the attack is for fewer bitcoins than MyBitcoin started with, the attack would be successful.  The defense against this (besides just making people wait for 6 confirmations), would be to "quarantine" TxOuts of new transactions until they are at X confirmations.  Any withdrawal requests made by the same user would be processed with only his own TxOuts.  Therefore, if his deposit was a invalidated, so will his withdrawal. 

Of course, this only passes on the problem to other members if they process transfers.  MyBitcoin would be safe from losing money, but the recipient of the money would ultimately get screwed by the double-spend.  The attacker deposits N btc, then MBC sends N btc to another member with the TxOuts from the first.  Of course, ethically speaking, MBC would still be "liable" for the missing coins, but they could just hypocritcally claim that the recipient should've waited for 6 confirmations before acting on the transaction.

First, have you seen how freakin' difficult it is to get users to upgrade their clients?  0.3.24 has been out forever, yet countless users are still using earlier versions, probably because they don't even know a new client is there, or don't feel like being inconvenienced by it when their current client already works.  It would take days to get everyone upgraded, and until then different users will be operating on different branches of the block chain. 

Second, if it happens once, what's to stop the same person from doing it again?  They still have 50%+ computing power, and wasting money may not be the primary concern of the attacker.  Perhaps they just want to disrupt the network...

Third, you can't possibly believe that such an event would not make headlines and cause catastrophic damage to the BTC network...?  The entire value of Bitcoin is based on people's confidence in the system, which is not well-correlated with the technical/security merit of the system.  MtGox and MyBitcoin had nothing to do with the merit of BTC, yet both did quite a bit of damage.  Let's see what happens when we throw a real security "breach" into the ring.

I agree that it's quite profitable for botnet owners to use the BTC network as it was designed to mine coins.  But it's feasible that someone, some time, might find it appealing execute a massive double-spend attack and make off with the cash/goods/whatever before the network crashes.  We are all familiar with how motivated some people are by short-term rewards... It only takes one time for this to crush the network, and I think we should all be concerned if there is any one person/organization that is capable of it.  That's a lot of power they're wielding, even if they have no ill-intentions towards the network.

But let's not focus on botnets, and focus on entities with a ton of resources:  perhaps governments that would feel more comfortable without the BTC network.  It's probably feasible for an existing US government agency to pull the trigger on this primarily with existing resources, they'd only need a little bit of preparation to distribute the software to all their computers.   

My point is, I think a one-million-computer threshold for breaking the network is too low.  If you consider the number of GPUs and/or FPGAs needed, it starts to look even easier.  And without a massive spike in BTC value, I only see this getting worse over time.

I was doing some back-of-the-envelope math and realized that the current global hashrate makes me uneasy.  Current hashrate is about 13 THash/s.  Consider an "average" computer can do 5 MHash/s without a GPU.  A simple calculation reveals that it would take 2.6 million "average" computers to start rewriting the blockchain, double-spending and overall complete loss of confidence in BTC.   Now take into account that many of these computers have GPUs so that number is probably more like 1 million computers.    I'm concerned because, not only is this within scope of government agencies, but...

     'Indestructible' botnet snares 4.5 million computers
     'Gang of Six' Controls Botnet of 1.9 Million Computers   (actually, I believe this botnet was deactivated by the US government)
     Data-stealing botnet infects 2.3 million computers

All of these botnets could probably crush the BTC network.  There was already reports of botnets being used to mine BTC, but I'm not sure about any plans to attack it.  Obviously, I'd simply feel a lot more comfortable if it just wasn't feasible.   Three things we have going for us is: 

• (1) The security of Bitcoin should definitely receive credit for the fact that the botnet operators are mining coins like the rest of us, even if it's stolen hardware.  Obviously these botnets have a $#!+load of computing power, yet they can't/aren't using it to try to break the security of the network.
• (2) Bitcoin actually represents a possible benefit to the criminals running them, and they may not want to risk killing the network.  It may be more profitable to mine millions of dollars (and stealing wallets) and then use the same BTC network to move the millions of dollars around without trace.
• (3) The botnets that are mining to make BTC are actually increasing the difficulty.  When botnets compete, everyone else wins.

I'm concerned that, without any significant increases in BTC value, and thus incentives for miners to expand their mining hardware, the global hashrate is going to continue to wane at this vulnerable level.  It's great that only a very select few people/organizations in the world have this capability... but it only takes one to end it for all of us.  And it's only going to get worse over time:  once the rewards are halved, we'll probably see the exit of tons of miners from the network.   The only thing I can see truly making a difference here would be transaction fees.  But at the current tx/day quantities, there is no transaction fee scheme that could incentivise miners that would also be acceptable to the users. 

The more I think about it, the more it makes sense to have designed the network to have a constant generation rate at the beginning, and then switch to constant inflation rate.  This would guarantee that miners will have "economically constant" reward, forever.  Not to mention that many economists (whom I agree with) consider small, consistent inflation to be good for a currency/economy. 

Is there a reason to be more optimistic about this?