You could always make a block chain in which all the blocks are generated on an easy difficulty. After a certain time the difficulty jumps up and you don't bother creating any blocks until it jumps down again whereupon you generate loads of blocks again. It still wouldn't be easy but to generate a longer block chain I don't think you'd have to do it at the same difficulties as the current one.

ByteCoin

It is indeed a problem if spent coinbase transactions get "rolled back" as those coins are deemed never to have existed.

An attack based on an adversary with huge computing power rehashing a decent chunk of block chain to invalidate coinbase transactions that have been spent can be prevented or at least detected as follows:

When a hash of sufficient quality is found for a particular block, all the clients which have generated hashes for that block which are not quite good enough send those hashes to each other, signed by some per client key. Each client that receives this information can use it to get a good estimate of the total hashing power at a given time. If the hashing power falls abruptly to a small value then the client suspects that the network has fragmented and it's on a small fragment and new coins must not be spent. When the hash rate it sees ramps up again then it must compare the incoming near-miss client signatures with the ones it's used to seeing. If they're a lot different then an attack is in progress.
Similarly, clients that seem suddenly to find lots of blocks thereby rewriting the block chain, without previously finding even more lots of near misses must be under suspicion of misleading the other peers about the aggregate hashing power and attacking the scheme.
The block chain could be eligable for locking with no ill effects, a few blocks back from at any point where the current estimated hashing power is some fraction greater than half the max estimated hashing power ever seen.

The astute will notice that these suggestions are dual to "balance sheet" and "regular block creation" ideas.

ByteCoin

I think that only happens if the current block is over 50kb already. Otherwise I think it's just accepted. I might be wrong - if I am, please point out in the source where recieved transactions are checked for the appropriate fees.

I searched the source for "GetMinFee(" and it seems onlyto be called in BitcoinMiner and CreateTransaction. This would lead me to believe that a miner can attempt to hash a block with some arbitrarily large transactions in it and, if it finds a hash of sufficient quality then that block will be transmitted around the network and accepted by all clients without demur. The size of the block might be limited by any size limits of the buffer for receiving transactions and blocks from the network.
Anyway, that's another possible method of attempting to store the latest Lady Gaga video in the block chain!

ByteCoin

You'll never believe it but I typed a big long reply and then lost the whole thing out of preview!
The transaction is identified by the hash as you say below.That's what the index is for. I'm pretty sure they don't HAVE to have different scriptPubKeys. I wonder whether this corner case has been tested but it's probably fine. They are not hashed. One is appended to the other and then parsed as a Forth-like (ie stack based) script. The link you quote actually explains it quite well. OP_DUP for example is a human readable translation of the actual opcode (158 I think). The tables in the link show suceessive stages of how operands are pushed onto the stack, popped off the top, operated on and the results pushed back. The opcodes are specified in a big enum in script.h Yes this is a known problem mentioned in a recent previous post of mine. People minting coins have an incentive to do this as it costs them nothing and the return in the long run for any of them for doing so is positive. Transaction fees discourage this but if no transaction fees are included and the transactions are individually not too large then they just hang around in everyone's memory until they close the client. Another known attack mentioned in that previous post of mine. I presume that a large single transaction requiring fees but including none will be rejected and forgotten from the current client.

ByteCoin

Why would you include a keypair in a transaction? Just to clarify - what private key do you use to generate the signature in the above transaction. Do you sign the transaction containing the private key with the same private key?

The moment you reveal the private key, you lose the ability to stop someone from impersonating you. If you send your card creating transaction to a bad node first, what's to stop the bad node from using the private key to create a new transaction crediting him and then sending that racing across the network?

Is this "private key revelation" just something you've introduced for your scratch-off card scheme or do you think that normal transactions reveal the private key?

ByteCoin

Ok thanks for the prompt reply. There are just a couple of points I still don't get.


Please let me know exactly how the private key can be known to both card creator and redeemer.

The normal meaning of keypair is "public key and private key". The private key can't be made public, that's why it's called a private key. Please explain very carefully precisely who knows about which private keys and how you propose to use them.
 
It's the redeemer's keypair which signs the transaction which spends the scratch-off card. If it has just been generated by the redeemer then the network doesn't know the public key which should be used to check the signature hence you have to tell the network about it hence it's the redeemer's public key not the card creator's public key.

I very much suspect that you have some fundamental misconceptions about how public key cryptography works. Please think carefully and be excruciatingly clear in your reply to show where I am mistaken if you still think I am wrong.


ByteCoin

Thanks for going into a bit more detail. Unfortunately I believe you expect readers to have a lot of shared context to understand your explanation and I for one am still unclear. I'd very much like to understand though.

Please correct me if I'm wrong in any way in the following summary.

What we're discussing is minimizing the amount of typing required to redeem Bitcoin scratch-off cards. I imagine that a basic card shows the public key (or address) credited with Bitcoins so that anyone can check the value and that it's unspent once they type in enough characters into their card-savvy client to uniquely identify it from the block chain. The scratch-off bit protects the private key, most of which needs to be entered but the last few digits can be bruteforced by the client program to save you typing. It does this by trying all possible values of the rest of the private key until it matches the public key. Alternatively, if you've already accepted the card or you just really hate typing, you don't bother typing in any of the public key, you just type enough of the private key until the computer brute-forces the rest of the digits to find they match some public key in the block chain.

The point of your post is that a normal private key is too long to make it easy to enter, and your scheme involves less typing.
In order for the Bitcoin network to accept your transactions, you have to make sure that you can satisfy the conditions stipulated by the script of the "In" transactions that you're using. The vast majority of scripts effectively check that you have knowledge of the private key for the public key which the "In" transaction was intended to credit. The script checks this by making you sign something. What exactly? The idea being that only the holder of the private key can generate such a signature.

In your scheme the card references a transaction with a non-standard script. Since anyone can spend the card on recipt, the script can't require you to demonstrate knowledge of a private key. Instead you have to satisfy some other condition involving "the signature", "the code", "the real code", "the target".

The scratch-off portion reveals a shortish code, the hash of which is included in the script. The hash in the script is salted with something else in the script or otherwise publicly available to discourage "rainbow tables" attacks. What is it? The length of the code must sufficient to prevent exhaustive search by attackers in the time interval between the card-creating transaction being distributed to peers for inclusion in the block chain and the time when the card recipient is able to enter the code into his card-understanding Bitcoin client application.

You say the salt is "the first few bytes of the private key". Whose private key? If it's yours how does the card generator know it. If it's anyone else's how do you know it?

Then the script requires you to provide a signature less than a target value and provide the public key that allows people to check that it's a real signature and not some numbers you just made up. So the person spending the card has to increment a nonce and repeatedly generate signatures until they're good enough.

So, when you spend the card, your transaction provides enough information to allow the Bitcoin nodes to verify that your transaction satisfies the conditions of the script. The problem is that you can't send the transaction to all nodes at the same time and, if the first node you send it to is "bad" it could take the information in your transaction and use it as an "In" for a transaction crediting itself. It would then be a race across the network between the two transactions. The idea of forcing the client to generate a certain quality of signature is that the "bad" node can't generate a signature of sufficient quality before your transaction has reached enough honest nodes and is most likely to be hashed into the block chain first. This depends critically on exactly what is signed. The "bad" node can see the non-standard script in the block chain since the card-creating transaction was distributed. Could it generate the good quality signatures for all cards in advance? (And sell them to other "bad" but lazier nodes ) Could you tell us what information is signed please?

Note that part of the problem was that we couldn't send the transaction to all the peers at the same time. If you could send the transaction a byte at a time in round robin fashion then the problem would disappear! Another way around it is if you could make the satisfaction of the script depend on another transaction which has to be in the block chain - the details are hard to explain.

What numbers are available for pushing on to the stack and what operations work a the moment? Can you specify for example that a transaction using yours as an "In" must have another "In"?  

ByteCoin

Thanks for that. You might feel that you're mailing this stuff into a void but I have taken note for my own project and I appreciate not having to work it out for myself.

ByteCoin

That sounds fascinating. So the scripting language is fully enabled at the moment? I thought it was present but lobotomized.
Could you talk us through the little script you published?
I presume that this requires new clients? If not, how do you do this?


I disagree very strongly. I believe the computations you mention could be done in much less time than network latancies. There must be a cryptographic way of enabling secure cards or else they will fail. Your proof-of-work signature is a good start. What scripting functions would need to be added to support it?


I don't understand how this links with the previous bit of your post. Please explain.

ByteCoin

It's only easy to detect if you bother looking for it. Without noticing the symptoms you mention there's no reason to check.

One way to make this attack a lot more costly is to ensure that a certain small fraction of the nodes you connect to have found a hash at some point. You can do this by asking the node to sign something with the same key that was used to sign a coinbase transaction. If it can't, then it hasn't found any hashes ever.

ByteCoin

This is a nice problem! Public key cryptography to the rescue!
What you need to do is generate an RSA public and private key.
n=p*q where p and q are large primes.
Choose e, 3 or 65537 are popular choices
Calculate d = 1/e mod (p-1)(q-1)
You publish the public key (n,e) on the webside while keeping the secret key (d) private.
When you recieve the payment information, you generate a number x less than n in a verifiable, previously published fashion from the transaction information that nobody can change and everyone can verify.
You calculate  s = x^d mod n, send it to the dart thrower and use that to determine the result of the dart throw in a previously published fashion and then send him winnings if any.
The dart thrower can verify that the dartboard has done the maths correctly by calculating x from the payment and verifying that s^e mod n =x.
The dart thrower can't engineer his transaction to win the darts because he can't compute x^d mod n.
The dartboard can't change any parameters to say that the thrower has not won when he has.

ByteCoin
  

I must correct you jgarzik when you said that you stood corrected!

I believe that theymos has made a mistake in his calculations.
We're assuming that we can generate transactions as close as possible under 1000 bytes long.
The basic charge is 0.01 for 1KB which applies after the block size exceeds 50KB.
So the 200KB between the 50KB and 250KB block size would cost 0.01*200=2BTC. We agree!

After 250KB if the block size is x (in KB) then the charge is approximately multiplied by 500/(500-x)
This means that the charge jumps to 0.01 * 500/(500-250) = 0.02 BTC after 250KB ramping up to 0.01 * 500 /(500-300) = 0.025 BTC at 300K. For the fifty 1KB blocks between 250 and 300 the most expensive one only costs 0.025 BTC so the total can't possibly be more than 1.25 BTC so theymos is easily out by a factor of 100.


More detailed calculations (neglecting the real rounding used in the code and being somewhat cavalier about other details) give

Block Size	Cumulative Cost
KB	BTC
50	0.00
250	2.00
300	3.14
350	4.58
400	6.62
450	10.12
499	32.53
500	5032

So the last transaction of 999 bytes to take the block size to 499999 bytes costs 5000BTC and the preceeding one costs just 5 BTC!

ByteCoin

You seem to be holding two mutually contradictory postions, creighto.

On the one hand, in response to my observation that hashers are rewarded for using up the free transaction quota, you reply that the fee schedule could be altered to discourage it. On the other hand in your response to caveden you imagine that fees will not be charged for all transactions until we're all long dead.

For this to be true one or more of the following would have to occur:

• Bitcoin ceases before fees are levied on all transactions.
• We all die rather sooner than we expect!
• Hashers will forever altruistically refrain from maximising their profit and nobody uses Bitcoin for data storage/distribution purposes.

Please explain.
Ok perhaps not all transactions would have fees but the free ones would immediately be used up by the hasher spam so effectively all transactions would need fees.

The point I was making about buying something expensive urgently is the following:
Suppose I have 90 BTC. My friend is in desperate need of 50 BTC so I send it to him without including a fee. All the "free" transactions in the block are taken and, as it doesn't include a fee it's not included in the block. I realize my mistake and would like to cancel the transaction and am willing to reissue it with a 10BTC fee payment to get it in the next block for sure. However, I don't think I can do that as I've already spent the 50BTC and I only have 40 left. There may be a workaround for this. What is it?

More fundamentally, let's say someone for whatever reason spams the network with lots of transactions with no fee at 1MB per second. Most of the transactions don't get into blocks because they don't have the necessary fee, but they are not forgotten! They have to persist in all the clients to try to get into the next block. Are they stored on disc? If they are stored in memory then the client consumes memory at 3.6 GB every hour! If they are stored on disc then it's the same problem as if they were hashed in the block chain.

Unless there is a scheme for forgetting transactions that have insufficient fee then it's still a big problem. I said that Bitcoin doesn't have effective countermeasures against spamming. I think I have shown that fees are not effective and that the current fee schedule make the problem worse, not better.


ByteCoin

The current fee structure is acknowledged to be tentative and I had assumed that in order for the system to work properly as the transactions ramp up, the fees would mostly be scrapped. The current fee system for example actually encourages abuse by block hash generators as follows:

People trying to earn money hashing blocks have an incentive to spam the network with enough small transactions (1 in and 1 out) to fill up the 50kb "small transactions are free" limit. If any real users of Bitcoin want their transactions to go confirmed then they have to pay the 0.01 fee to get them included in the next block in preference to the spam transactions. The cumulative fees reward the block hashers for their spamming.

When fees start to be effectively mandatory under the above scheme, some interesting cases need to be handled. For example, if someone tries to buy something expensive that they need urgently with bitcoin but they don't include a fee, can they then reissue the transaction with the fee, using the same coins or will the network regard the original unfeed transaction as having already spent them?

ByteCoin

Bitcoin currently provides excellent security guarantees against forgery or other tampering but no effective countermeasures against spamming or other denial of service attacks. Spamming the network with valid transactions at 1MB per second results in a disc usage of at least 2TB per month.  This would cause probably all hash generation to stop after a couple of months. What would happen subsequently is less certain.

Possibly if the attackers ramped their spamming up slowly then people would sell their Bitcoins just before they stopped their client and deleted the transaction data taking up all their disc space. This would drive the price of Bitcoins down and the attackers could buy them cheaply. Then a client more resistant to spamming is released (such as a client using "balance sheets" ). Harmony is restored and the value of Bitcoins soars to its normal level!

ByteCoin

Thank you theymos for taking the time to criticize the scheme in some detail.


After a new block is found the balance sheet is recalculated (possibly incrementally) and the hash of the balance sheet is encoded in a special transaction that serves to encode the data which is then broadcast round the network the same as a normal transaction. This is done by exploiting the broadband subchannel in ECDSA mentioned in another post of mine. There are some details to be fleshed out such as "who generates this balance sheet hash transaction" and "how do you cope with a malicious balance sheet client supplying incorrect data" but I believe there are multiple adequate ways of addressing these problems.

Thanks for supplying some real numbers. I'm afraid that "balance sheet" is not really an accurate description of what is stored. See
We need to store enough information about all the transactions which credit an address to allow appropriate references to those crediting transactions to be recorded in the transaction when you spend money from that address. It's like the stubbing-off-merkle-tree-branches idea in the white paper except that the stub hashes don't need to be stored and neither do the blocks. I doubt at the moment the "balance sheet" idea would save a significant amount of space but that's because Bitcoin is so thinly exchanged. As the fraction of spent transactions rises, the storage savings of the balance sheet method become more persuasive.

I'm not quite sure what you mean. I think this is the same objection that gavinandresen raised earlier in the thread in response to me misunderstanding exactly how transactions worked. After he put me right I changed the scheme. After reading my reply, if you're not satisfied, please explain the problem with my scheme in more detail.

Isn't it true that when you download the block chain you process it all in the current scheme? It seems to be that your criticism is more appropriately leveled at the current scheme because new "balance sheet"-using clients download the current credit list from other similar clients. The client then updates the balance sheet with all the incoming transactions to stay in sync. No processing of spent transactions ever takes place.

I'm not sure what you mean by a "parallel network" or why it would be necessary. I believe it would use the current network, as a "balance sheet"-using client looks, to the network, (mostly) like the existing client. You can't however download the older portions of block chain from it as that's data it has "forgotten". You are right in thinking that the "balance sheet" scheme becomes unmoored from the root hash. You are correct in thinking that this is a problem which needs to be addressed and I believe that my scheme can offer roughly equivalent security guarantees to the current scheme but the details are complex.

Implementing "balance sheets" without altering the current protocol is rather complex and that makes it unattractive. However I believe that Bitcoin will have little choice but to either change the protocol or to move to a client implementation in which nobody remembers all the transactions, such as "balance sheets". There's nothing stopping a small group of people spamming the network with transactions possibly encoding the latest Lady Gaga video or child pornography etc. As a method of storing data on the internet for free it has the benefit of designed-in complete permanence, distributed reliability and plausible deniability. Before becoming bandwidth or CPU limited I believe that the block chain+transaction data could grow at about 30TB a year with the rate only increasing. This is going to exclude the vast majority of people from running full clients. Either Bitcoin would have to give up the p2p label or it's going to have to start forgetting old transactions. Of all the ways of doing the latter, "balance sheets" is the best.

ByteCoin

This would be one reason for splitting the bitcoin client functionality into two orthogonal parts.
One part would maintain the block chain, verify incoming transactions from the network and provide the interface for obtaining useful information from the block chain. It would neither contain nor have access to any private data. It would have large data files which need never be backed up but re-downloaded if lost. This would be the "server".

The other part would run the UI and allow the user to generate transactions, maintain the user's wallet(s), show the user's balance, incoming and outgoing transactions. It would contain the minimum of information that is also encoded in the block chain and the files would be small and easily backed up. This would be the "client"

Possibly hash generation could be a third independent process which is optimised for the individual CPU and other hardware. It requires no storage and just communicates with the server portion. Possibly the server portion could come with the default hash generator built in but most users with serious hardware like CUDA would run specialized hash generators using the interface on the server.

ByteCoin

A competitor to whom from doing what?

Because this relies on the twitter infrastructure which is another point of failure. If the Bitcoin infrastructure fails then no Bitcoin payments are possible. If a messaging infrastructure is implemented within the Bitcoin protocol then (under plausible circumstances) the messaging would only fail if the payment infrastructure failed in which case there was no point sending the message anyway. Nothing lost.

If you implement the messaging in twitter then you have to cope with both the additional scenarios in which exactly one of twitter and Bitcoin fail. This would complicate your implementation.
I don't believe that twitter provides a guaranteed quality of service so you would be vulnurable to the human factors whereby support for your metadata is limited or terminated etc...

Considering that the fundamental size of a number used by the elliptic curve cryptography in Bitcoin is 32 bytes, 512 bytes means you can transmit 16 of them in one metadata packet. If you steer clear of the patent-encumbered point compression then a public key or a signature take two slots each and encrypting a one slot message takes four slots if you're keen on security. This still leaves plenty of room for your payload. The details on how much room is left depend on exactly what sort of security guarantees you're trying to achieve.

However, I suspect that a secure public key cryptography system implemented over twitter would be subject to various kinds of interference until rendered unsuitable.

ByteCoin

PS Thanks for the interesting twitter info.

Using the same definition, "Balance sheets" is essentially done as well! 

ByteCoin


PS

The current Bitcoin client has the undeniable advantage of existing.

Neither the lightweight whitepaper client nor a "balance sheet" based client exist but both are compatible with the current protocol.
They are therefore equal on that basis.

I contend that a "balance sheet" based client is superior in every other practical way to the lightweight whitepaper client or the current client. If it were implemented correctly, it would be superior to the current client. If a new Bitcoin-like protocol were correctly  designed and implemented with "balance sheet" and other improvements in mind then it would be superior to the current protocol.