Can't you work out how many order and the value the merchant was getting just by looking in the block chain at the number and value of payments to the publicly posted "pay me" address? Surely there's no way around this other than the merchant using a new receiving address for every sale he makes?

It would be useful if you would specify the details of what you are trying to achieve in exhaustive detail as at the moment it is unclear.

It is possible to encode fairly significant amounts of information in currently permissible bitcoin transactions by specifying the random value (often termed k) in the ECDSA signing algorithm.  32 bits could be easily encoded without any significant decrease in security.  

An explanation can be found on the Wikipedia page for Subliminal Channels.

ByteCoin

As a sophistication of jav's scheme, and with reference to http://bitcointalk.org/index.php?topic=3441.msg50075#msg50075 I propose the following.

If the customer wishes to buy from the merchant without waiting for confirmation then he creates a transaction with a total value much larger than the value of the goods he wishes to buy from the merchant. Say the merchant's goods are worth 10BTC then the customer creates a transaction for 100BTC. 10BTC goes to the merchant's address and the remaining 90BTC "change" which would normally go to a new address generated by the customer actually goes to one of the customer's addresses listed as an input to the transaction. This signals to the world that the transaction is meant to be consummated immediately and that if the inputs are double spent in another "immediate transaction" elsewhere then the change is forfeit.

The ratio of the amount "at stake" and the price of the goods can be mutually agreed beforehand by the merchant and customer. In the event of a double spend of the same inputs then the merchants are credited in order of decreasing ratio until the value of the inputs expires and any change is lost. Enabling the network to make financial sense of honouring the double spending of inputs in this fashion would be fraught with problems however. The idea does have merit though. Suppose the customer makes three immediate transactions using a total of 100BTC for 30BTC, 40BTC and 50BTC. The network could allow the payees of the first two transactions to be credited. The last merchant could probably be credited 30BTC out of the 50BTC owed although further analysis of strategies where the customer colludes with one or more merchants might decide it's more wise to burn the remaining 30BTC instead.

Gavin's worry about "honest" double spending mistakes by buggy clients can be ameliorated by agreeing that transactions which don't route the "change" back to one of the crediting addresses should never be accepted before being confirmed and therefore the "attempt" at double spending is doomed to fail, is therefore harmless and should go unpunished.

ByteCoin    

Edit:I should acknowledge http://bitcointalk.org/index.php?topic=3168 where jav advocates something amounting to shunning.

An effective way to discourage double spending attempts would be to propagate both attempted transactions and then "shun" the inputs.

"Shunning" is where the network mutually agrees that it will never accept as valid any transactions or blocks which contain a shunned address or shunned TxOut. If shunning is not unanimous then any transactions by non-participants, which transfer money from a shunned address or use a shunned TxOut as an input to a transaction, are themselves shunned.

In the shunning community, the value of these shunned transactions or addresses can be redistributed among themselves as they wish or (preferably) considered forever gone in an even more irrevocable fashion than if the private key had merely been lost.

If a merchant has accepted a transaction and has handed over the goods before a transaction has been incorporated into a block then it's cold comfort that the double spender's money is shunned after the double spend is detected. The merchant is still owed payment for the goods. The solution is as follows:

Firstly, the merchant should require that the transaction paying him for the goods should be from a TxOut or an address that holds many more bitcoins than the value of the transaction. That is, the "change" portion of the transaction that returns the "unspent" portion of the TxOuts referenced back to the payer should be much larger than the value transferred to the payee. If the payer attempts a double spend then the payer runs the risk that all the bitcoins will be shunned even though the value of the attempted fraud is much lower. This scheme has the advantage that it requires little change to the existing infrastructure.

Optionally, in the event of a double spend, the network could elect to honour the payment part of the transaction and shun the "change". This means that the merchant is not out of pocket while the fraudster is punished. In order to signal which is payment and which is "change", the payer structures the transaction such that the "change" is paid to an address that was also used to sign the crediting transaction. Care needs to be taken with such schemes to make sure that double spending remains uneconomical when the double spender acts in undetectable collusion with one or more of the double-spent merchants.

A supplemental scheme would give the sender feedback about the propagation of the transaction across the network but it involves much more infrastructure change and network traffic. We observe that a minority of miners generate the majority of blocks. If the merchant can see that the transaction has been accepted by these miners then he is confident it will not be double spent. The proof of a miner's power is the number of blocks it generates in a given time. If the generated blocks always credited the same address for a particular miner then we would know who the biggest miners were (at the cost of a big loss of pseudonymity for the miner). The merchant would require that the payer construct a transaction which also requires some proportion of the largest miners to sign that they have received the transaction and will include it in their next block, in return for some fee. When the merchant sees the miner's receipts arrive across the network then he is comfortable handing over the goods.

Note that the last supplemental scheme is tentatively included merely to spark off ideas as it is ugly. I would also warn against shunning as, although simple and powerful it easily results in fragmentation and I feel that the schisms it facilitates could weaken or even destroy Bitcoin.

ByteCoin  

When you start talking about "discouraging" blocks based on whether you think the miner is doing something dishonest you're undermining one of the central mechanisms for stopping the network fragmenting. The rule so far is that the block chain with the highest difficulty wins, full stop. If the rules for whether a block is adopted are changed to something where different bits of the network could have different opinions about the block's suitability based on the transactions they have seen then that's a recipe for network fragmentation.

What you're really trying to do is to get transactions to confirm more quickly which you could do by increasing the block rate target.
What are the tradeoffs that resulted in the selection of a 6 blocks per hour target rate?

ByteCoin

In the current Bitcoin scheme, one can't accept transactions until it has been incorporated into a block. Suppose two transactions "spending the same coins" enter the network at different points. On average, half the network will have one transaction and half the other. The only way out of this deadlock is which happens to make it into a block first. So you can see that the race across the network is unimportant but the race to get into a block is the deciding factor.

Hal's attack above would yield a reliable income.

ByteCoin

In the interests of accuracy I would like to point out that "lost" bitcoins can be reclaimed in the long run by someone generating by brute-force (or by some as yet unknown method) a private key capable of generating valid signatures for the transactions crediting the "lost" private keys.
 
It is uncertain whether this is possible in the lifetime of the current universe however.

In http://bitcointalk.org/index.php?topic=1786.msg21998#msg21998 I proposed a new opcode OP_BLOCKNUMBER which would allow (amongst many other things) the construction of transactions where the money would revert to one or more "lost property" locations if private keys were lost. Widespread adoption of such a scheme could effectively minimize the number of lost coins.


ByteCoin

Good catch to spot this pool exploit! I completely missed this in spite of thinking about pooled mining quite a lot.

If you have any doubts about the reality of this exploit then consider the following thought experiment:
Suppose there are ten miners hashing at equal rates. After they each submit one work-unit to the pool, if a block is then found they each get 1/10th of the total profit. If one of the miners leaves and is replaced by a new miner at that stage and each miner then submits another work-unit then, if a block is then found the new miner gets 1/20th of the profit having done the same amount of work as the miner whose place he took. It's only fair if the share of the profit is proportional to the work done.

One solution to the problem is to make the payout for the block proportional to the time since the last block. The mining pool would have to have a slush fund to cover the cases where the block generation rate falls below the long-term average.

ByteCoin

As I have mentioned a few times before, although ECDSA cannot be easily used for encryption, the keypairs used are perfectly suitable for use in some elliptic curve public-key encryption schemes. It is misleading to try to imply that there are significant technological barriers to implementing a public key encryption scheme using bitcoin addresses.

ByteCoin

One plausible option for a future bitcoin-like system is to allow a selection from a numbered range of pre-selected curves. Smaller transactions or balances could use smaller keysizes if necessary.

You can still embed messages into transactions see http://bitcointalk.org/index.php?topic=2393.msg32288#msg32288

ByteCoin

There is no effective solution to this problem until the wallet handling code can be completely separated from the networking client. See http://bitcointalk.org/index.php?topic=1691.msg20718#msg20718
Attempting to improve security by having a password on the client is no improvement as noted by Nefario and has significant problems as noted by gavinandresen.

ByteCoin

I'm not aware of any academic cryptography papers that refer to any curves over prime fields as Koblitz curves. The standards bodies publications do not count as academic papers and I believe that their inclusion of "k" in the name is idiosyncratic.
Indeed the standard states "Here ..[the term "Koblitz"] is generalized to refer also to curves over F_p which possess an efficiently computable endomorphism. [Allong the lines of the paper of Gallant, Lambert and Vanstone "Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms"]
This scheme tends to be referred to in the literature as the "GLV method"

When selecting appropriate cryptography you can vary the "size" parameter which has an obvious effect on security. You can also vary the "peculiarity" paramter which can substantially increase the speed at the cost of a small reduction in the effective "size". Before worrying whether the special nature of the secp256k1 curve loses a few bits of security relative to a random curve we need to examine what reasoning informed the selection of a 256bit curve. Possibly a 224 bit or 192 bit curve would have been perfectly satisfactory. That being the case, the theoretical loss of security due to the special nature of the secp256k1 curve is inconsequential while the speed increase is still useful.

I forsee a general trend towards the use of more specialized curves over the vanilla random elliptic curves as the performance gains are substantial. This is comparable to the shift away from vanilla RSA towards the more specialized ECC in return for shorter keys, that happened about ten years ago.

I see little justification for retiring secp256k1 without a complete redesign of Bitcoin to address existing deficiencies in scalability and implementation security. Future schemes, however, should avoid hard-coding any particular implementation of the essential cryptographic primitives.


ByteCoin

It couldn't possibly be that these relatively impoverished and mostly uneducated young american men, having left a situation engineered by the USA in which they were in danger of killing and being killed and now in a situation run by the Chinese in which their lives were relatively safe, with the time and encouragement to reflect rationally on their circumstances became somewhat more skeptical about the benefits of capitalism and warfare.

Liberal attitudes tend to be correlated with more education and I don't think that's just due to indoctrination by "liberal educators".

Back on topic: Emotional argument is a bit of an oxymoron.

Gavinandresen's slogans are good. About the bankers - I think it's always a case of "I want less corruption or else a larger share of it"

ByteCoin

I can recast my solution in terms of ECDSA signatures, the security of which is a prerequisite for the correct operation of Bitcoin. This might reassure you.

A simpler, essentially equivalent (but actually unsuitable) method is the following.

When you receive a the payment transaction, you sign it with your public key. You use the signature as the result of your dart throw or random numbers or whatever. Everyone can verify that signature using your published public key to check that the calculation is correct.

Puzzle: Can anyone else work out why the RSA solution is appropriate and the ECDSA solution is not?

ByteCoin

There are a variety of different ways of encoding information in a normal transaction in the block chain.
Encoding the information as fractional amounts of bitcoin in transactions has several disadvantages.
It is inefficient - the amount of information encoded per transaction is small.
It is obvious - small transactions which are not round amounts of coin are not typical.
It can be discouraged by fees on small untypical transactions.

Another way would be to send a small amount of bitcoin to an address, were the address is the information to be encoded. This would store about 20 bytes per transaction.
A superior way would be to use the broadband subchannel in ECDSA which I wrote about in
http://bitcointalk.org/index.php?topic=1545.msg18364#msg18364
This allows you to store 32 bytes per transaction and does not require you to waste any money.
Neither of these latter two schemes is obvious, nor can they be discouraged by fees and they are vastly more efficient.

ByteCoin

There are many elliptic curve encryption schemes for which the public and private keys are compatible with the ECDSA keys.
One could use ElGamal or MQV or one of the newer signcryption schemes. There are no technical obstacles to implementing encryption.

ByteCoin

I think that the answer to that question depends very much on what exactly what it is, the primary function of which we are discussing. Bitcoin has recently proved to be a moving target. It used to have an effective scripting language but now it doesn't. There's little point discussing alternative uses if these alternative uses can be easily denied.

Gold is superior to Bitcoin in this regard. Once you have your gold, nobody can decide to change its maleability so you can't make it into jewelry or it's reactivity so that it tarnishes.

Is Bitcoin what the current software permits or is it what the fundamental technology could allow?

ByteCoin

I saw this analogy on the other thread and I thought it was a good short justification for not restricting Bitcoin use.

ByteCoin

Gavin, I believe my simulation is accurate. I will post a longer explanation when I have read davidonpda's pending article.


I saw a post from you which was just a complete quote of my post with the numbers. I followed up to it saying "content?" and that post has disappeared too.

Please try to re-do your post. I'd love to read how a cartel attack works with 50% and nothing less as my simulations and some noddy maths seem to disagree.

If anyone on the forum can easily compute a steady state from a simple infinite Markov chain then we can put this discussion on a rigorous footing.

I believe that either gavinandresen, btchris and davidonpda are all spectacularly wrong or I'm wrong which would be embarassing.

I would like to revise my previous statistics and state that a cartel with no preferential network access can be profitable with 33% of the generating power. If it can get its blocks accepted three times more frequently in the event that two blocks are published at the same time then it's profitable at about 20% of the generating power and at lower powers only suffers a very modest degredation in its performance for it's cartel enforcement activities.

ByteCoin

I meant that I simulated a number (now 6) of different cartel strategies operating in the normal network to see which was most effective. I did not simulate two competing cartels operating at the same time.

I recently simulated the case where the cartel is three times more likely to get the non-cartel members to accept the cartel block when a non-cartel block and a cartel block are published at the same time. In this case the cartel generates more than its fair share of the blocks when it has 34% of the generating power.

ByteCoin

Minimising the attack surface for exploits is vital.

What is the new functionality that you wish to introduce which cannot be implemented using a suitable non-lobotomised script?

ByteCoin