A problem here is that any "factoring in" is just a guess. It's been increasing lately as there has been a series of hardware makers successfully shipping. Maybe it continues like a rocket. Maybe it doesn't.  The current rate of growth cannot continue forever though, or otherwise we will soon need to start converting the mass of the sun into energy to power the miners.

See the thread. The transaction was already in his wallet (thats what the gettransaction checks for), which wouldn't have been possible if a duplicate address had just been generated.  We don't know what exactly happened but there are several other hypothesis which are more consistent with the facts than there being an actual duplicate address generated.

E.g. a unclean wallet shutdown made it miss flagging that address as used, thus resulting in it handing it out again, or a mouse mis-targeting resulted in the OP generating an address but then copying another.

Also, now that the newly received coin has been spent we can see that both the new instance and old instance used the same public key (03a97dfbd26061494c9369cd469f8422f7c5f16e4fd6b4da42e42138e711f7fd6f), which means that it's 256 bits involved, not just 160. (E.g. if your hypothesis was a chance collision the probability of that is now 79,228,162,514,264,337,593,543,950,336 times lower than before we knew for sure that he was using the same public keys).

A collision didn't happen here, I'd stake my life on it gladly.  With respect to a bad PRNG, things are possible, but the code in Bitcoin-qt has been audited by many people (including myself personally) and that seems unlikely (also, if it were to happen, considering the design I would expect consecutive duplicate addresses and not just one).

"Just needing to downgrade" would have meant erasing the blockchain database because their 0.8 installs were not compatible (different database formats), which would have meant being offline for a long time to sync back up. Instead, at least in the initial repair they fixed by directly hard coding a different block or by blacklistingthe one on the 0.8-only fork.

Thats not the right way to ask someone to do that, the right way would be to ask them to perform a signmessage (file->signmessage plug in the address, and "this is alikim on bitcointalk", and post the signature and the exact message used). But I don't see any reason to doubt that this address is the OPs. I suspect you have your local timezone set in the forum, his post appears to be >10 minutes after the transaction to me.

Why was this moved back out of the technical support area?  Is the purpose of this thread to spread (apparent misplaced, see my prior posts) concerns or is it actually to figure out whats up technically?

It's normal and necessary when its syncing up with the blockchain.  Are you fully synced up yet or not?

It wouldn't have. That isn't how the software works. This is why doing a gettransaction is a pretty useful: had it just generated an address that was used before the wallet wouldn't know about any of the transactions. But in this case it did.
What am I?  Chopped liver?

In any case, people need to relax. See my prior post. This looks like he managed to get an address out of key-pool twice, e.g. due to some error in losing the write that marked the key spent after an unclean shutdown. (Or pilot error of some kind, e.g. generate a new one, then mis-click on the copy and copy an old one instead)

No, it should return an address your own wallet previously generated that you've never used before. Unclean shutdowns, wallet corruption, salvagewallet, or restoring a backup could cause it to issue an address to you twice, however.  I've never heard of a local replay before outside of these circumstances.

Can you look back through your records and confirm that

78f929d6fd5461cea8a64b1867cbc45b39c3119495b18aff313e9024c025092c was really a transaction paying you and/or
5aed0ce301ecd17b237be9bd0dda7fa8fb7e2eb7f453c2ca1f27de160a23c791 was really a transaction with you paying some place?

E.g. if you were selling coins at mtgox at that time, go look at your mtgox deposit records on 2012-07-07?

Thats actually due to a bug which is fixed in git: it asks for the pass phrase totally unnecessarily when you request a new address.
It is _always_ a old one from the keypool.

Open up the debug console (help->debug window->console), type in:

gettransaction 5aed0ce301ecd17b237be9bd0dda7fa8fb7e2eb7f453c2ca1f27de160a23c791

If it returns that old transaction then that key was already in the wallet when that transaction hit your client.

There are ages on keys too, but off the top of my head the only way I think you can get them is if you dumpwallet and IIRC thats only in git.

Other questions: have you restored a wallet from a backup at any point, used salvagewallet, or pywallet?

It would enable a bandwidth/storage tradeoff. E.g. if you're willing to store all the data yourself, you could tell your peers not to send you all the proof data which you can simply construct on your own.

If all full nodes stored the data the bandwidth would be ~= to what we have now.

Bandwidth is more costly than storage, indeed, but it's "instant bandwidth" vs "integral storage" so the tradeoff isn't entirely clear.  Even without this idea the data must be sent to you, so the most additional bandwidth for storageless is the overhead of the proof vs actually sending the data.  This would be a small constant factor, I suppose.  Might be useful to actually reason out some of the details to get more concrete numbers.

It's utterly trivial to do that. Just ask that they tell you parts of the file from time to time. You can even do this without remembering the file yourself if you just compute a hashtree over it, and remember the root, and they give you the hash fragments.

But that wouldn't be very useful as a decentralized anti-dos mechanism: one copy of the file would allow you to prove to as many concurrent peers as you want.  If, instead, the peers ask you to store some unique file for them to address that issue— they have to undertake the cost of actually sending you that file which is contrary to the goal of using this as anti-dos (and also you have the risk that Sergio addressed of someone doing that in order to invisibly delegate their proof work to someone else).

What this adds to that idea is the ability to send a few bytes that the peer can use to make a file of arbitrary size, and then they can convince you that they have actually done so... without you having to do non-trivial communication, computation, or storage. The price is, indeed, that the information stored isn't terribly useful. (You could perhaps replace the hash with some other kind of abstractly useful function "folding proteins" or something— but in general double-use for proof-of-whatever subsidizes the cost of attacking, since now your attack can be paid for by the secondary benefit of the barrier function, and other useful functions have some risk of surprising optimizations that strong cryptographic hashes lack).

Are you asking about all bitcoins in the Bitcoin system?

The newly created aren't mined "from" anywhere, they are simply introduced to the system out of thin air. See https://en.bitcoin.it/wiki/Mining for more information.

The space is ~2^256 it will never search more than a very very tiny sliver of the space. Additionally there may, in fact, be _no_ solutions to your query (even a simple one like 1zzzzz*, though that is unlikely).  Moreover, the search is randomized. Even if there were a solution, and even if you did evaluate ~2^256 points you may still have not found it (and in fact could search forever without finding it).

It's not incorrect to show a longer expected time for a prefix of 12 than 4, of course. But what is incorrect is an indication that goes _down_.  If it tells you it will take 1 hour to find an 8 character prefix, it should tell you that it expects 58 hours for 9 indeed.  But if you've spent a half hour on your 8 character search and still not found one, it should still be reporting 1 hour. Not 30 minutes.  Your probability of finding a solution is not appreciably increased by all the times you've failed to find one because the probability is independent (given cryptographic assumptions).
 

An idea which has come up in the past is that various security model reductions in Bitcoin could be practically secure if we had compact fraud proofs.

Today, for example, SPV nodes validate nothing. So if there is a longer _invalid_ chain, SPV nodes will still follow it.  This is a existential risk for Bitcoin in the future if SPV nodes become very very popular and almost no one runs full nodes: At some point running a full node may even be foolish, because you'll reject a chain that the economic majority (running SPV nodes) accepts.

However, if instead it were possible to construct small messages that a SPV node could inspect and then be completely confident that a block broke the rules then security would be restored: An invalid chain would only be accepted so long as all SPV nodes could be partitioned from all honest nodes— there only really need to be one attentive honest node in the whole world to achieve security, so long as its truth cannot be censored.

Modifying Bitcoin to make compact fraud proofs possible is fairly straight-forward.  The big problem is that from a practical engineering perspective this idea is very risky:  Processing a fraud proof is at least as complicated as validating a block and we know that people get block validation wrong already. If these proofs exist then there would be no reason for a miner to ever try to create fraud. As a result they will never be used. If they are never used the implementations will be wrong... if not in the reference then in all of the alternative implementations.  Some implementations might be vulnerable to incorrect fraud proofs that break consensus even absent fraud, others might fail to reject some kinds of fraud.  Basically any inconsistency in this normally dead code is a point an attacker could use to break the network, or it could just cause failure by chance.

Obviously software testing and whatnot addresses this kind of concern in theory. But in practice we already see people writing alternative implementations which are forked by the pre-existing test code. Good testing is only a complete answer if you assume idealized spherical developers.  Completely eliminating the possibility of error in these systems via testing is infeasible in any case, because the input space is too large to exhaust.

So in spite of the potential benefits, I think many people have not been super excited about it as a practical idea.

I finally stumbled into a retrospectively obvious way to make this kind of design more safe:  You require that all block solutions commit to two distinct candidate blocks.  One of the candidate blocks is required to be fraudulent.  The fraudulent block is eliminated through a fraud proof. Nodes which do not process fraud proofs correctly will be unable to determine which of the two is the right one.

This wouldn't eliminate all risk, and it has considerable overhead if used completely seriously but it would at least address the concern that the proof code would be completely nonfunctional due to disuse.
 

The trick here is that the UTXO needs to be constructed here in such a way that the information provided with transactions is always enough to update the new committed UTXO hash.

This is trickier than it might seem at first glance for a couple reasons.

First, a proof of UTXO existence must also carry enough data to perform a proof for removal. Some tree structures make these proofs one and the same, but in others they are not.

Secondly, users construct their proofs independently of each other.  So a user constructs a proof for find and remove A, and another user constructs a proof for find and remove B.  This means the block must contain a proof for remove A+B.   This requirement generally eliminates any UTXO scheme based on a self-balancing tree and any scheme with content adaptive level compression,  since the A+B proof may need to access additional data than the A or B alone in order to rebalanced or recompress the tree.  (Note, most UTXO discussion on this forum has been about tree types invalidated by this requirement. It's easily fixed, but I guess it's good we didn't run headlong into implementing them). In #bitcoin-dev we've been calling this a "composable" or "commutative" property.

Insertion of new utxo, in particular, is somewhat tricky: For any kind of binary search tree insert may need to happen at arbitrary location. Users can not write proofs for the insertions of their new UTXO sets because they have no clue what the state of the tree would be in at the time their insertion actually happens.

Petertodd's suggestion is to store the utxo as an authenticated insertion ordered binary tree which supports efficient inserts, a merkle mountain range. This addresses the above issues nicely. Proofs are still invalidated by updates, but anyone who has the update can correct any proof (even a proof originally written by a third party).

Most important about Petertodd's suggestion is that it completely eliminates the necessity of storing third party data.  In a practical system nodes that store everything would still exist, of course, but they aren't required in Petertodd's idea: The system would work fine so long as each person keeps track of only his own coins (plus headers, of course).

There are some tradeoffs in this scheme however:  Anyone storing the proof required to spend a coin must observe every block so that they can update their proofs as the coins surrounding their coins in the UTXO set change.  Proof sizes would be log2() in the size of the complete history, rather than in the size of the spendable coins because unless we nodes to store the complete history there may be no single party that has the data required to re-balance the tree as coins are spent.

The latter point is not really a killer, since log2() grows slowly and the universe is finite. It's also somewhat offset by the fact that spends of recently created coins would have smaller proofs. The first point can be addressed by the existence of nodes who do store the complete data, and unlike in the Bitcoin of today, those nodes could actually get compensated for the service they provide.  (E.g. I write a txn spending my coin, but I can't produce the proof because I've been has been offline for a long time.  Your node tells me that it'll provide the proof, so long as the transaction pays it some fee).

The cost of observation could potentially be reduced if nodes were required to store the N top levels of the tree, by virtue of not including them with transactions. Then you would only need to observe the blocks (or, rather, the parts of blocks) which made updates to branches where you have txouts.

The potential to completely eliminate storing third party data removes some of the hazards of the Bitcoin design. E.g. no more incentive to abuse the blockchain as a backup service. No need to worry about people stuffing child pornography into it to try to get the data censored.  However, that full vision also requires that new nodes be able to bootstrap without auditing the old history. This would be a substantial change from the current zero trust model, and I'm not sure if such a change would be viable in Bitcoin. At a minimum it would probably require the robust existence of fruad proofs, in order to make a persuasive argument to newcomers that the history they can't review doesn't contain violations of the rules.

You'll still get paid— but as your correct payout falls too low you won't get paid every block. Instead, you'll get shares here and there and get paid way more while those are in the window than your hashrate would suggest, offsetting when you didn't get paid. On average your expected income is the same, just with somewhat higher variance.    This is how p2pool avoids creating potentially infinitely large coinbase transactions that pay out really tiny dust (not to mention keeping the sharechain datarate sane).

Assuming that the bitcoin hashrate is actually "free" to be turned around maliciously.  This is tricky, it's like some of the arguments that Bitcoin is only secure if half of all existent (or potentially existent!) computing power is currently working on it.  In any case, my comments were only in tepid complaint about "almost as strong as" in comparison to Bitcoin. There is more to consensus than just the blocks.

None of this applies to your central purpose of your message: Parasitic altcoins have the same problem with internally invalid data or the inability to make efficient access to their state or to have reduced security compressed representations of their state.  So quit letting me knock you off-topic with my pedantry.

Trivially fixed (you might recognize the idea by the more recent name of "Committed UTXO set").

In any case, yea, I'm not intending to say bad things about the idea generally. But there are limitations to be aware of. Perhaps some of them are fixable, I haven't given it much thought.   Thanks for following up.

I expected this to be dumb. Indeed, it was. But it was also a lot of fun. Nice singing.

The patent situation for ECC is highly over hyped. Mostly it's just optimizations which are patented (and mostly for characteristic 2 curves). In my prior review, it looked like what we were doing was fine.  There is also a lot of ecc patents expiring this year and next, further solidifying the situation.

I'm not sure what you mean by "actively scan".

Petertodd suggests that people should be nlocktiming some of their transactions for the future to reduce problems with this. E.g. once the current block has enough incentive, start making transactions that can only be mined in the one after it... Regardless, if transaction load isn't so high that blocks are mostly pretty full, I suspect we'll have much greater problems than miners running intermittently.