Absolutely, but this doesn't eliminate the value in having the system support higher confidence absent trusted parties.  They'll still be business there in a system where clients can cheaply do more validation alone, but it will just be business for the value you can offer over and above the fully distributed system (faster, immune to some attacks, SLAs, etc).  The suggestion I'm making is still vulnerable to DOS attack, and feeding (mildly) stale data, and it requires more data (the tree fragment).

E.g. a system where you ask trusted parties for a signed statement about the transaction and then after getting it randomly also query for the tree to _prove_ it with reasonable confidence, then automatically announce loudly to the network when you detect lying, along with the cryptographic proof of the the inaccurate response— is a much more robust and secure system than "manually add a bunch of trusted parties; only find some were compromised and screwing you weeks later"... and also more costly since there would be no low cost alternative to trusted services (only run your own full node).

I'm quite concerned that during the last week while mtgox has been down people have been very actively stealing wallets. We've seen many trojans and other wallet collection scams.  Perhaps people took less care to make sure wallets that had little/nothing in them were not stolen.

If someone made a copy of your wallet this week they may be sitting on it hoping that when mtgox comes up you'll withdraw all your BTC and as soon as they see that transaction they'll launch a matching transaction to give all that coin to them. Even if your wallet had nothing in it before, if someone copies your wallet they will also gain access to future payments to the addresses in it as well as 100 future addresses (which are pregenerated and hidden).

If there is _any_ chance that your wallet has been compromised, do not deposit a bunch of coin in it. Instead make a new wallet or cycle out your old keys by hitting getaddress 101 times before using the next address. Make sure to update your backups too.

Stay safe!

Hm?  I'm not asking for proof related to unconfirmed transactions, I'm asking for proof related to previously mined transactions with outputs which have not been redeemed as of the completion of a particular block.  This should be a deterministic product of the block-chain and identically available to every full node.

I think your solution for namecoin is a non-solution because it makes it not a distributed system. You have to trust that the data has not been manipulated in some impossible to validate way.  The is also practically true of the software as whole, but only because everyone isn't actually going to review the whole thing, not because they couldn't review it.   With the tree solution I described you could randomly spot-check such summaries automatically, making them much less risky.

For namecoin, It's also not a solution because knowing the complete state of the system going to be too much work for most namecoin users and it's also pointless.


I want to know for sure what foo.bit resolves to. I don't have the full history (because I don't need it and can't afford the enormous required storage) so I can't tell on my own.  I ask my peers about foo.bit.

They tell me that foo.bit is 1.2.3.4 and that the last update to it was mined in block 100,000. We're currently at block 120,000 (or so say my peers).  With the current pruned tree stuff I can tell for sure that it really was mined in block 100,000,  but I _can't_ tell if it was updated after that since my peers could trivially by sibyl attackers. (If they lied about the chain height and just claimed we were at 100,000 I'd know because I'd notice if my clock was six months off)

If there is a commitment to the open transactions I can ask single peer for the merkle tree fragments from block 120000-199994 for the relevant open transaction (hopefully most of the tree would be the same in those blocks, reducing the data sent) and then be sure that either I got the correct result, that I got a slightly stale result (e.g. it was updated within whatever amount of lying about the height I'd fail to detect), or that my attacker has a serious amount of computing power being employed to give me a stale result about a name.



If you have the block headers (which are quite small), then your trust is limited to that your peers aren't lying to you about the block height and aren't telling you only about some fork.  But you can trust that such a fork would not be very long due to the extreme computational cost, and that the block height could not be too outrageously wrong because you know the current time. 

The fact that peers can DOS attack you by denying you information can't be avoided but it's also detectable and once detected you can try to seek more peers or at least refuse to do anything stupid.


Asking multiple peers is a good and fine thing, but it has _serious_ limitations.  Attackers can often control your network connectivity, so they can simply make themselves all your peers an you have no way to detect this.  Even without network control a sibyl attack can be quite effective: by running thousands of fake peers on a few hundred networks (e.g. just by having simple proxies on those networks) you will very likely end up as all the peers of quite a few nodes.  Querying many also results in N-fold increases in network load.

If a client can use the blockchain proof of work to prove most of their required data, then it only needs to consult multiple peers to obtain confidence about the true identity of the highest block, and attacks performed against this clients are limited to attacks about the content of very recent blocks.

I think this is a beautiful system, but I have a suggested improvement.

If the block is found in the first 599 shares, it should be payed to a multisig escrow. Like this: https://github.com/bitcoin/bitcoin/pull/319

The keys in use could be held by either a collection of parties (reduced trust centralized) or, better,  by a large deterministic random subset of the P2P nodes.  E.g. Take all of the nodes who were paid in the last round and use the block hash of the last block to pick 21 of them (or all of them if there are fewer), and require >50% to sign the transaction releasing the escrow to the appropriate receivers.

I believe this would completely decentralize it while preserving the other properties of your system.

As I understand it,  in lite mode you can validate that a transaction is in a particular block, but you can't validate that it hasn't been redeemed by a subsequent block.

This has a couple nontrivial consequences.  For example, a lite mode client can't tell if a transaction its been told about is even _possibly_ valid or if it is completely jibberish until someone mines it.   

This also means that you can't make a zero trust lite mode namecoin resolver because the only way to be sure that a later transaction didn't transfer the ownership of a name to someone else is to have reviewed the entire blockchain and made your own summary of the open transactions. You can't ask a peer to do this for you unless you trust them not to lie.    I think this is not just a namecoin issue, I think it also impacts various distributed contract proposals that require you to be able to see that a transaction is mined but not yet redeemed.

What if the coinbase TXN included the merkle root for a tree over all open transactions, and this was required by the network to be accurate if it is provided.

Then if you wanted to validate that a transaction was really open, you would obtain the block headers, then obtain the N most recent blocks, then ask an untrusted peer for the pruned open-transaction merkle trees leading to that the transaction in question.  You are now sufficiently confident that the open transaction is still open as of the height of the blockchain you have access to.

Since full nodes must already keep track of all open transactions for validation, maintaining such a tree would be relatively cheap (log2(n) for single updates, fewer per update if more than one txn changes at a time).

Beyond the namecoin/funky distributed contract case/ this would also permit semi-lite clients which track only the headers and open transactions and are allowed to forget about very old open transactions because they can be reminded of them by untrusted peers but can still do full validation.   This might be helpful for network health in the future (e.g. keep track of only recent, likely to be quickly redeemed transactions, and give them forwarding priority. If you can't validate a txn give it low priority, if its children show up again and keep bothering you, then ask a full peer to prove to you that they are are valid and then add them to your cache)


So, can someone please correct my understanding of the system if I'm wrong?

It's still segfaulting for me deep in the ati opencl code during the setup of the second card in a three card system.

It's also quite possible for a pool to never mine a block (or to mine far under the expectation), it's just less like just as it is less likely for the pool to do superbly well.  Worse, because of downtime, fees, cheating, etc. the pool is expected to average less overall. The the reduced variance is a real and useful result, but don't exaggerate the contrast.

Yep. That is the compromise.  The current wallets unsteal themselves.

My arguments:
(0) In spite of recent concerns, I think that loss is a greater risk for most users than theft.
(1) People frequently reuse addresses today, this eliminates the unstealing advantage.
[And, in fact, someone on IRC was just asking about changing the client to send change back to the original address in order to make backups more effective]
(2) Encryption makes theft less likely than it has been
(3) Thieves know about the unstealing property and will already act fast enough if coin is available.  If you're about to receive a lot of new coin you could start a new deterministic wallet. Also after compromising your machine once the thieves will likely leave backdoors in any-case.

If the interface allowed you to have multiple deterministic wallets at once (or just multiple key-heads in a single wallet) you could periodically trigger the creation of a new one in order to get the forward privacy, and you could do this in time with your backup schedule so you're not left surprised by a backup that failed to grab all your addresses.

diff --git a/ocl.c b/ocl.c
index 4173026..a8240eb 100644
--- a/ocl.c
+++ b/ocl.c
@@ -425,7 +425,7 @@ _clState *initCl(int gpu, char *name, size_t nameSize)
                        return NULL;
                }
 
-               clState->program = clCreateProgramWithBinary(clState->context, numDevices, &devices[gpu], binary_sizes, (const unsigned char **)binaries, &status, NULL);
+               clState->program = clCreateProgramWithBinary(clState->context, 1, &devices[gpu], binary_sizes, (const unsigned char **)binaries, &status, NULL);


Meh. Makes it not crash, but it's not sufficient for it to work right. I should look at this after sleeping.

Testing on a silly nvidia machine:

Selected 0: GeForce GTX 275
[2011-06-23 06:00:58] Preferred vector width reported 1
[2011-06-23 06:00:58] Max work group size reported 512
[2011-06-23 06:00:58] cl_amd_media_ops not found, will not BFI_INT patch
initCl() finished. Found GeForce GTX 275
[...]
[2011-06-23 06:04:18] GPU 0 found something?
[2011-06-23 06:04:18] No best_g found! Error in OpenCL code?

Looks like it never accepts results from the GPU. CPU mines fine.


on a system with 3 5850s:

(gdb) run -t 6 -a 4way --url http://pool.bitcoin.dashjr.org:8337/ --userpass 15xWuDHSyKzpvp6FacGKXijBeaaaYhKWSi:x --retry-pause 1 -r -1 --intensity 16
Starting program: /root/gm/cpuminer/minerd -t 6 -a 4way --url http://pool.bitcoin.dashjr.org:8337/ --userpass 15xWuDHSyKzpvp6FacGKXijBeaaaYhKWSi:x --retry-pause 1 -r -1 --intensity 16
[Thread debugging using libthread_db enabled]
[New Thread 0x7ffff4141700 (LWP 17510)]
[New Thread 0x7ffff3940700 (LWP 17511)]
Init GPU 0
List of devices:
        0       Cypress
        1       Cypress
        2       Cypress
Selected 0: Cypress
[2011-06-23 06:17:35] Preferred vector width reported 4
[2011-06-23 06:17:35] Max work group size reported 256
[2011-06-23 06:17:35] Preferred vector width reported 4
[2011-06-23 06:17:35] Max work group size reported 256
[2011-06-23 06:17:35] Preferred vector width reported 4
[2011-06-23 06:17:35] Max work group size reported 256
[2011-06-23 06:17:35] Patched source to suit 4 vectors
[2011-06-23 06:17:35] cl_amd_media_ops found, patched source with BFI_INT
[New Thread 0x7ffff313f700 (LWP 17512)]
initCl() finished. Found Cypress
[New Thread 0x7ffff307e700 (LWP 17513)]
[New Thread 0x7ffff287d700 (LWP 17514)]
[Thread 0x7ffff287d700 (LWP 17514) exited]
Init GPU 1
List of devices:
        0       Cypress
        1       Cypress
        2       Cypress
Selected 1: Cypress
[2011-06-23 06:17:37] Preferred vector width reported 4
[2011-06-23 06:17:37] Max work group size reported 256
[2011-06-23 06:17:37] Preferred vector width reported 4
[2011-06-23 06:17:37] Max work group size reported 256
[2011-06-23 06:17:37] Preferred vector width reported 4
[2011-06-23 06:17:37] Max work group size reported 256
[2011-06-23 06:17:37] Patched source to suit 4 vectors
[2011-06-23 06:17:37] cl_amd_media_ops found, patched source with BFI_INT

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff6a2b4b0 in ?? ()
   from /root/AMD-APP-SDK-v2.4-lnx64/lib/x86_64/libamdocl64.so
(gdb) bt
#0  0x00007ffff6a2b4b0 in ?? ()
   from /root/AMD-APP-SDK-v2.4-lnx64/lib/x86_64/libamdocl64.so
#1  0x00007ffff6a7a31b in ?? ()
   from /root/AMD-APP-SDK-v2.4-lnx64/lib/x86_64/libamdocl64.so
#2  0x00007ffff6a225a0 in clCreateProgramWithBinary ()
   from /root/AMD-APP-SDK-v2.4-lnx64/lib/x86_64/libamdocl64.so
#3  0x000000000040793b in initCl ()


Stupid binary libraries.  :-/

Update: Still crashing on the system with 5850s with 181070d129259d088219a0dcd0ef41d9a45439d3

Wtf. Black helicopters much?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I was there.

First the .4242 amount was named by non-mtgox parties (I didn't witness this myself, but talked to the people after who did).  Second the exact value of the txn and destination address were announced by mtgox a long time (probably 45 minutes?) before my node saw the flooded transaction. Apparently MagicalTux had issues getting connections up to a pre .23 wallet.

I consider this sufficient evidence that mtgox still controls that bitcoin.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iEYEARECAAYFAk4DBmEACgkQrIWTYrBBO/obeQCcC18b82NgtFNlsikTDOPti8Jk
iU0AnjauZYGBQDJqGW+hCxWz14KEuwDJ
=fZrh
-----END PGP SIGNATURE-----

Meh. All this sub-currency stuff is a complete distraction, I think.  How about a pair of new script opcodes:

One signifies an intent transaction which declares an intent to spend particular inputs to particular outputs (and has its own inputs and outputs, but only for the purpose of fees and change).

The other specifies that the output of the txn containing it can only be spent if combined as an input with a matching intent transaction from N blocks prior.  The intent output this transaction must be to the same address(s) as the source transaction so the intent transaction can be effectively replaced by the holder of that key by simply transmitting a new intent transaction that redeems the prior one.

Of course, this doesn't really work for three reasons:

One you noticed:


There is no way to end the race.   If you had a "Safe haven" address that you can trust the attacker doesn't have access to, then you should simply multisig escrow the transaction with that address in the first place and avoid all this stuff.

The second is if the attacker works with miners she can arrange so that the miners mysteriously doesn't manage to hear any of your retractions before it is too late, and the miners can plausibly deny their role in the attack.  They can even learn to do this automatically without prior coordination with the attacker by looking for intent transactions which indicate intent to outputs with large fees.

The third is that if the attacker has compromised your machine in order to obtain your wallet in the first place they will simply make your machine either not see their intent and spend, they will disable the functionality, or they will gobble up the attempted race messages.   They can even do this without actually having the machine itself currently compromised if they are able to gain enough control over the network connectivity:  Nothing in bitcoin today makes control of the network seriously worse than a DOS attack, but in this situation control of the network would completely moot the reversal war.  They could also simply DDOS nodes emitting the reversal TXN off the internet.

Namecoin uses a kind of intent traction to lock names so that people watching the txn flow can't claimjump you, it's quite nice. Unfortunately enabling claim jumping is an entirely different matter than preventing it.

Looking at your slides again I see you say no backup in .23— but the bitcoin has had the backupwallet RPC for some time now.  Is this not exposed in the gui?

I have a cron job that uses backupwallet + gpgs to do offsite backups daily. Works great.

Diablo reported that running multiple opencl threads improves utilization substantially, his miner runs three per gpu.  Though this may be due to the excessive usage of blocking IO in the fast path (wtf‽).

I'm looking forward to the phatk kernel.  Getting a miner with a control plane which isn't crap is a dream that I haven't had the free time to realize.

Thanks for working on this!

I recommend microsd and http://www.spy-coins.com/producthtm/micronickle.htm in the future.

Backing (as well as intrinsic value) is a liability for money, not an asset.  It artificially pins the value of the money-units to something other than what the market would reach absent the backing, or it artificially influences the value of the backing asset. E.g. in the case of gold— gold is orders of magnitude more expensive than other substances which are more rare, more difficult to obtain, and more industrially useful— thus leading to an inefficient under-utilization of gold.

The parallel with name backing is pretty obvious: If you fuse naming and bitcoin either names will be wildly under/overpriced due to demand for bitcoin, or bitcoin will be wildly under/overpriced due to demand for names, or both.

This article changed how I thought about money by arguing about why gold is not great money. Perhaps you'll find it interesting: http://www.libertariannews.org/2011/06/21/against-the-gold-standard/

I would instead argue that when people think of backing as a problem what they are really concerned with is guaranteed liquidity. Unfortunately, even if we made it so you could always buy names with bitcoin (perhaps with an automatic variable exchange rate to avoid the backing problems I suggested above) it wouldn't really solve the liquidity problem because you might want something _other_ than names, like food. And if you were having problems getting people to accept bitcoin for food then you're going to have pretty much the same problem with bitcoin-connected names for food.

I don't buy the bitcoin-backed-by-proven-transactions.  I thought I might need certify a document creation time at some point in the future the other day so I dropped a SHA-512 randomly into #bitcoin where is was logged by hundreds of disinterested parties. Should I actually need to prove it I could just subpoena a few of them. I can cheaply put a hash in a newspaper classified, etc.  Timestamping is so cheap that its almost valueless on its own, and the cases where you'd need machine verifiable timestamps that bitcoin provides over and above the cheap options I just gave are few and far between.

I think this is an excellent point which I missed previously because of all the distraction related to restoring the lost coin and the common misconception that the loss of coin itself is a problem.  I think you undermined your argument in the first post by arguing for more than was strictly necessary to achieve these ends.

To remove the uncertainty you simply need to take the coins out of circulation forever, it's not required that they be remined.  Otherwise you end up with another kind of uncertainty: e.g. say bitcoin manages to deflate to the point where 1 BTC = $1m in todays relative value... and a ton of lost coins miss their long hearbeat and show up mining. So no matter what algorithm you choose for dishing out the expired coin it could end up making mining ludicrously and socially destructively valuable compared to any other occupation. Even if there is a long delay from the point where the coin expires to when it shows up again that just moves around the point at which everything blows up.

In some ways your proposal as stated only removes uncertainty in that it makes sure the pessimal case _always_ happens: that after the currency deflates due to high usage, lost money appears out of the abyss and screws everyone up.

However, I don't think that "heartbeat it" _or lose it forever_  violates any of the system invariants in the way that "keep printing" as proposed explicitly by SgtSpike,  and jon_smark. Nor does it create the possibility of a crazy gold rush appearing randomly in the future. (Heartbeating, incidentally would simply mean forming a new transaction, not an explicit heartbeat event.)

The obvious time to implement this would be at the same time as doing a cryptosystem upgrade, as the first expiration could be timed to adequately prevent a bunch of actually lost coins returning from the grave as ecc keys are cracked.  It would be easily argued for then because people will easily see that the failure to implement it will allow the lost coins to return and blow the economy up.

I would expect the only debate at that point would be over if it should be a one time cutoff or a rolling one.

Could be, should be, but isn't right now. The actual blockchain file is a dumb blob of bytes. The BDB file store offsets into that file. Pruning it would require atomic operations which cover both, or building a separate file and switching.... or putting it all in the database, which I assume is not done for performance/space reasons.


Not quite solely: You need to know something to tell if its the right key— otherwise you'd just accept any signature!  Fortunately, the transaction already provides the address, and we're already using the address to determine if the public key is the right one.

Page 48 of http://www.secg.org/download/aid-780/sec1-v2.pdf describes how to do key recovery, see step 1.6.1.  Note that there can be two possible public keys, but I don't think this creates a security issue because if someone can find a case where both candidates hash to the same address then they can already cause trouble with our current system.
Edit: I was corrected that it's up to four possible matching public keys

Right, their concern is theft, so a voluntary delay is pointless— otherwise I would point out that you can already form post-dated transaction in the bitcoin protocol by using the nLocktime field.  (Can't be mined until a particular block number or network time).

I think its a mostly a nonsense concern, and actually insoluble the way they suggest. People already suggest that the confirmation time in bitcoin will cause the system to fail, so adding a mandatory additional time to confirmation would _not_ help.

As far as it being nonsense— no cashlike system has this feature and they work fine. As you suggest the solution to theft in the context of cash is better security.  Transferring your savings into a offline wallet (a piece of paper or usb key) is analogous to locking your cash/gold bars in a safe and is the reasonable and prudent thing to do.

If bitcoin continues to grow in success I expect we'll also see secure hardware wallets— special devices that hold your keys securely and which you plug in via USB to send and receive from.

There are, however, technical things we can do to improve the security beyond just the basic "secure your computer/wallet".

For example, the user could transfer the funds into in-blockchain-escrow by forming a transaction that two signatures (the user's and a third parties) that are required for release of the funds.  Offering the service of being a third party signer for such transactions (perhaps requiring additional authentication or a time delay for release) may eventually be a reasonably profitable bitcoin business.

Another thing we could do is write code for miners that allows you to _bump_ a pending transaction out of their queue prior to it being mined if a conflicting transaction comes in that has a sufficient fee (Perhaps 1 BTC + 3% of the value).  A mode could be offered in the bitcoin client where if it sees someone else spending its coin it generates a fresh and safe keypair then produces a conflicting txn with the appropriate fees which locks the funds under a new key plus a preselected escrow service key, and this transaction hopefully gets mined first. This couldn't be a default because people using the same wallet from multiple places would shoot themselves in the head with it.

This would increase the risk of accepting unconfirmed transactions, because it provides a ready reversal mechanism for unconfirmed transactions to everyone. So as a community we ought to think long and hard about it before allowing it, but it's a possible option which doesn't require any kind of grand redesign or slow down transactions further in the common case.

Of course, there will be other ways to work with bitcoins in the future — e.g. bitcoin backed debit cards that provide centralized confirmation for very fast and low value transactions. But I don't think that additional currencies (be they distributed or centralized) are at all appropriate for addressing the security concerns.

Yea, thats unfairly negative.

"Mining gold takes energy, apart from increasing the supply of gold, most of which will simply be locked away in vaults, the energy is wasted"

"Validating and transporting cash takes energy, apart from discouraging counterfeiting and moving the cash from place to place, the energy is wasted"

People complaining about bitcoin's energy usage are ignoring the externalized (and thus hidden) energy costs in the alternatives.  Perhaps bitcoin is worse right now given the low amount of economic activity, but its nowhere near as bad as a simplistic analysis would make it sound.

Ob pedantry:  The 21M limit comes not from the quantization limit at 1e-8, it arises as the limit of the geometric series.  If the bitcoin precision is increased the total number of bitcoins will not go past that limit.

You're also overstating the current blockchain size.  The client keeps orphan forks that it heard about plus a number of excessively bloated indexes. The blocks themselves are in blk0001.dat.  On client I bootstrapped a few weeks ago (so it has some amount of dead forks in it already) is 285MBytes.

The blockchain can also be significantly compressed because almost all txn use the same script and because public keys in signed transactions can be reliably derived from the signature. (It's not clear that Satoshi knew this, but even so— it takes a bit more computation to validate without the public key.) Just running a simple compression on it that doesn't take advantage of the ability to recover public keys shrinks the file to 190MBytes.