So instead of using a hash we should be using a block cipher?

I presume that the difference between the two with the most practical impact is the presence of collisions in the former and the absence thereof in the latter.

I'm not really calling in to question the validity of what you say but, to make your point more obvious, could you give a realistic example of a situation in which using a hash function instead of a pseudorandom function gives noticable problems?

ByteCoin

Such concerns are not relevant for the security of modern cryptosystems. In particular, public key cryptography relies on the public key being published and used multiple times. Please cite any modern technical publications which claim otherwise.

Codemojo's scheme is simple, viable and secure.

ByteCoin

Bitcoin was developed and is implemented using pre-zero-knowledge crypto technology.


I think that the incorporation of an appropriate generic zero-knowledge-proving scheme which enables such digital contracts would be revolutionary.


Can arbitrary functions f be proved in zero-knowledge? If not, what are the constraints?
Are the proofs non-interactive? If not, how many rounds do they take?
Is there a scheme for generating arbitrary zero-knowldge proofs? Can you send some references to relevant papers please?
Are all the proofs necessarily probabilistic?

Welcome to the forum!

ByteCoin

When MoonShadow says "benchmark" he means "checkpoint". From main.cpp...

Also, the vanilla client has the checkpoints. There are other clients. I don't know whether they have checkpoints...

ByteCoin

But do they accept blocks which are built off blocks mined in the very distant past when the difficulty was minimal?

I think they do.

As patvarilly says (and you overlook) the client can't gratuitously ignore new blocks which branch off very old blocks because that would hinder block chain reorganisation and the adoption of the "longest" chain if the network were split for a long time and then reconnected.

I haven't seen the problem addressed before. If such checks existed I would expect to see them in ProcessBlock() in main.cpp and there's nothing appropriate there. As far as I can tell, patvarilly's post is completely correct.

ByteCoin

By specifying such a large nonce prepended to the message, if an attack on SHA256 were found then the the attacker, by engineering certain parameters into the nonce would probably find it easier to find a collision. The recipient of the signature doesn't have any way of telling one nonce from another so can tell whether the nonce has been "tampered with".

Anyway, if the application decides it needs a nonce it can prepend or append it to the message anyway. Don't specify the nonce as part of the interface as it mandates using space that people can't necessarily spare.

As a general rule, when you're hashing data you should hash just the data you want to hash and not any junk whose values you don't care about. It called "packing the hash"

I was contributing to this thread before in a kind of academic fashion as all the solutions proposed were roughly equally good. I feel quite strongly that the above proposal with the large nonce is a retrograde step and I'm very keen that people understand the problems I outline above. If I have not explained it adequately, PM me and I will edit this post.

ECDSA_SIGN(SHA256(fixed_string+message)) has the benefit of being the simplest adequate solution. Applications wanting a nonce can add it to message so that message = nonce + real_message.

Edit: Let's use industry standard base64 encoding and if we're really going to use base-58 then at least fix the encoding so that it doesn't vary even if it starts with leading zero bytes. PLEASE

Edit2: The paper referenced by gmaxwell concerns itself with the size of the private key and the random number k. The paper would be motive for implementing some bounds checks on d_A and k (using the notation in the wikipedia article but not for any checks on e=SHA256(message).

ByteCoin

I think we need some controls on the quality of the wiki.

One thing that stands out is

https://en.bitcoin.it/wiki/Tonal_Bitcoin

There are a number of calls for its deletion.

Does anyone know the proper procedure for resolving disputes about the contents of a wiki?
Can we start the process please?

ByteCoin

My understanding is that the bulk of the discussion occurring under this subject heading revolves around a proposal by kjj linked to above which is not the behaviour of the current system.

May I suggest that you request help from a moderator to move your posts discussing this special system to a new thread (which it clearly deserves) as someone casually following the new posts to Dev & Tech (like me) gets confused because you appear at first sight to be discussing the behaviour of the current system but incorrectly.

If the proposed system for discouraging block chain re-organizations was in it its own thread (and explained properly) then I believe it would attract wider interest and be more easily found in future when such proposals are discussed again.

ByteCoin

Edit: I gather from kjj that it already has had a thread. In this case it might be useful to mention in your posts that you are discussing the merits of a proposed change and link to a post outlining the change.

I think you'll find that this idea, taken to its logical conclusion is outlined in my post about balance sheets
See the disussion there.

ByteCoin

Correct. Your analysis however assumes that the other miners will blithely accept his blocks if he wins the fee.

The odds for a corrupt miner working by himself are even worse than you suggest because the other miners, seeing that they have not been "cut in" are not going to accept the lone miner's blocks. Even in 1% chance that the 10% miner gets two blocks, the other miners will not accept his blocks and will rapidly regain the longest chain.

The only way in which the rewriting can succeed is if enough of the miners gain "enough" of the profits. Exactly what their negotiating strategies should be is hard to determine though....

It seems plausible, given completely rational miners, that the rewrite would not be accepted unless >50% of the hashing power consents.

ByteCoin

Mike's concern is valid. The solution suggested in the OP_BLOCKNUMBER threads is to reduce the risk to the same level as the invalidation of coinbase transactions. Coinbase transactions take a long time to mature because reorgs that invalidate transactions spending coinbases must be thrown away after the reorg. OP_BLOCKNUMBER transactions could take a very long time to mature, proportional to their value.

nLockTime, sequence numbers and scripting are powerful. There seems to be no way however using scripting, nLockTime etc to send bitcoins to an address and to have them revert back to you if they are unspent for a very long time which seems to be a keenly desirable feature. I will take this back and discard OP_BLOCKNUMBER if someone demonstrates that equivalent functionality can be gained without it.

If there were an OP_DIFFICULTY as well then the futures and bonds suggested by cunicula might be possible.

ByteCoin

The particular issue I'm submitting for consideration in this post is the implementation of a new future-proof address type.

Terminology
An overseen transaction is one where the user requires the assent of one or more third parties to complete the transfer of bitcoin.
The third party is termed the overseer. The service they provide is oversight.
Bitcoins sent to the user which require an overseen transaction to spend are overseen coins. The address they are sent to is an overseen address. Note that sending coins to an overseen address does not require an overseen transaction.


Oversight Service
The user signs up to an oversight service with a certain policy and mechanism on approving spends. The oversight service might be implemented as a USB dongle with a display or a web page accessible by a browser or by a call centre accessible by phone.


Overseen Addresses
The user needs to distribute a new overseen address to receive bitcoins and/or to send his existing bitcoins to. The scriptPubKey for transactions sending to an overseen address must require the users signature (like a normal transaction) and the overseer signature.
This is a non-standard transaction which potentially needs to contain two hash160s of information - one for the user's key and one for the overseer's key. It's troublesome to type in such a lot of information and to come up with a new address format for every new type of non-standard transaction.


Out numbers - a new address type
We observe however that it's very easy for the standard client to create a new transaction by copying the scriptPubKey of an existing transaction. So instead of sending to an address like 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa  which contains the hash160 of the credited public key we could send to scriptPubkey 0 as seen in the block chain. I'm going to refer to this as "out 0".

Address 1PSSGeFHDnKNxiEyFrD1wcEaHr9hrQDDWc would be out 170 as it's the coinbase transaction for block 170. The coinbase transaction for block 171 would be out 172 as block block 170 contains the first ever transaction,  sending 10BTC to 1Q2TWHE3GMdB6BZKafqwxXtWAWgFt5Jvm3 which is then out 171.

The onus for creating the first non-standard transaction and getting it into the block chain can therefore be shifted onto the oversight service.
When the user signs up, the oversight service creates a non-standard transaction crediting a tiny amount of bitcoin to the overseen address and gets it into the block chain. After a suitable number of confirmations the overseer works out the what position that address has in the block chain and passes that "out-number" (typo-protected, see below) to the user. The bitcoins required for the small transaction could have been transferred by the user to the oversight service on subscription as part of the fee for the service.  


Paying to overseen addresses - or to generic out-numbers
We modify the standard client so that when the user types an out number into the "Pay to:" box, the client looks up the relevant scriptPubKey and fills in the fields accordingly. So if a user types "o170" the client finds out that the scriptPubKey is just a simple transaction to address 1PSSGeFHDnKNxiEyFrD1wcEaHr9hrQDDWc and fills it in. If the user types the out number for an overseen transaction then the client looks up the scriptPubKey and recognizes the transaction type. It redraws the Send Coins window to include a box for the overseer address and it populates the "Pay to:" and "Overseen by:" with the destination address and overseer address respectively.

New schemes involving non-standard transactions will be seen to be useful and will be invented and implemented in future. The above solution is completely future-proof as the client software doesn't even need to understand the scriptPubKey in order to create a transaction sending coins to it. If the standard bitcoin client software and UI is altered to allow transactions to out-numbers then users of that software can send money to overseen addresses even if the bitcoin client does not understand overseen transactions. The client should allow the user to send bitcoins to an out-number for which the client does not understand the scriptPubKey after a suitable warning such as "This version of the bitcoin software cannot inform you how coins sent to this address will be disposed".


Preventing bitcoin transfers going astray with out-numbers
There is an issue with preventing the mistyping of an out-number because it's very likely that adjacent numbers will be valid out-numbers and also many transpositions of adjacent characters will also yield valid out-numbers. I suggest that the hash160 of the scriptPubKey base-52 encoded into "a-zA-Z" be appended to the displayed out-number. A typo-protected out-number would therefore look like "o170XcaYfWuomDEsiFqnaXDVxqHHTxMe". The user would not have to distribute, store or remember all the alphabetic part of the out-number as the client would look up the relevant scriptPubKey, hash it and fill it in. So for the above example "o170X" would provide approximately a 98% chance of typo detection, "o170Xc" would provide approximately a 99.9996% chance of typo detection and "o170XcaYfW" would reduce the chance of an undetected typo to about one in about twenty billion. Anyone distributing their out-number to receive payments could decide how long their protected outnumber was going to be up to a max of the number + about 28 characters.

The exact format of protected out-numbers is thrown open for discussion. There must be no confusion between the current address system and protected out-numbers. Out numbers are "numbers" by analogy with bank account numbers and to avoid commerically embarassing issues whereby inappropriate words are spelled out (cf. the issues with rude words in CAPTCHAs). The alphabetical "check" portion can be engineered to be free of inappropriate words.

Sending overseen coins from an untrustworthy computer
Users subscribed to an oversight service are possibly using rootkitted computers and must be running an oversight-enabled version of bitcoin to spend overseen coins. if all the coins in the users wallet are overseen then when the user presses send, the computer can't send a complete transaction as it does not have access to the overseer's key and can't generate the overseer's signature. (Except by using the "disappearing overseer recovery pack" mentioned by Gavin).

One possibility is that incompletely signed transactions be allowed to propagate across the bitcoin p2p network like a normal transaction. The overseers would see all the incomplete transactions which they could sign to complete and after checking with their policies and/or phoning the users etc they sign the transactions and send the complete transactions out across the network to be included in blocks. In this instance, the behaviour of the incompletely signed transaction is similar to a transaction with a nLockTime in the future.

Another possibility is that the bitcoin client has been informed of the IP address of the oversight service that they are using, so the client sends the incompletely signed transaction direct to the overseer who, after suitable checks, signs it and distributes it or sends it back etc..

In the case that the overseer is a USB key, the incompletely signed transaction is sent to the USB device. It checks the transaction and displays the amount and the address to be credited to the user on its own display so that the user can check them. If the user approves then the USB key signs the transaction and sends the completed transaction back to the computer to send to the bitcoin p2p network. It seems likely that some extra USB-key-specific software needs to be installed on the computer to handle the communication between the bitcoin client and the USB key.


General Considerations
I think the system should not prefer any particular oversight service to any other. Anyone should be able to provide oversight service if they follow the protocol and any user should be able to subscribe to any oversight service.

The system should be able to be extensible to facilitate coins overseen by multiple overseers in which case the system should be able to facilitate situations in which both overseers are required to sign, and situations in which only one is required to sign.

If the overseer is a USB key, care has to be taken so that the bitcoin client does not have to concern itself with the details of transacting with the USB device.

In order to facilitate oversight services, bitcoind should be changed to enable the sending of transactions with explicit custom scriptPubKeys, possibly specified as a hexadecimal string encoding of the scriptPubKey contents.

ByteCoin

Indeed the addresses do not have a public key associated with them at the moment or indeed for the foreseeable future.

Most addresses cannot be mistyped into other valid addresses with just the change of one character or one transposition.
I estimate that there's about a 0.1% chance that a given address can be converted into another valid address by substituting just two of the characters, so it's not too much of a risk.

However, given that the checksum ensures that the addresses are 5 or 6 characters longer than an unprotected address, the guarantees that they provide are far from optimal.  It would be better to employ an error correcting code designed to detect and correct substitutions, insertions, deletions and adjacent character transpositions. It's reasonable to imagine that equally protected addresses using the new scheme might be two characters shorter.

It would be an interesting problem to determine which of the bitcoin addresses with known public keys or holding a significant balance are most vulnerable to being mistyped.

ByteCoin

There are a number of possible solutions to this problem. The best solution from a technical point of view would involve an implementation of the paper I referred to earlier.

I gather that you are willing to make changes to the bitcoin client software to enable users to opt into some scheme whereby they are protected even if their computer is compromised.

If the computer running the bitcoin client is rootkitted then strictly, it's impossible to trust anything the computer displays or limit what it sends or ensure the security of any information you input. Practically, there are limits to the complexity of software which anyone is willing to develop for a rootkit and so some use of the computer may be possible.

Possible solutions are:

1) Facilitating the use of an offline secure computer to hold the private key and generate transactions. In this case the engineering effort goes towards implementing an efficient secure communication probably involving copying alphanumeric strings between the two computers. The user has to have another computer and be able securely to install the client.

2) Facilitating the use of a third-party website the approval of which (indicated by quoting an ECDS) would be required before transactions of the client could succeed. In this case, the unapproved transaction generated by the client is sent to the website, the website displays what the transaction would accomplish in some hard-to-spoof fashion and the user approves of the transaction via some hard-to-brute-force pre-arranged password or other such token. The website then signs and either passes the transaction back or sends the transaction onto the network itself. This is a solution which requires multisignatures to be enabled.

There are other solutions, none of them easy or nice.

It would be helpful if you could come up with some use-cases for the private key splitting. What ideally would you like the user experience to be? What degree of deviation and increased complexity from the normal transaction process do you imagine will be tolerable? Is this solution intended to be suitable for crypto-ignorant non technical users of bitcoin?

ByteCoin

The mailing list is rapidly becoming unusable for 'serious work' too.

On the day after the creation of the mailing list.....

13 Jul 08:55 Christian Decker "carries over a topic from the forum".
13 Jul 09:35 & 10:02 Jeff Garzik posts two replies that could have been aggregated into one post
13 Jul 10:03 Christian Decker top-posts to Jeff's entire first email!
13 Jul 10:54 Vladimir Marchenko top-posts to Jeff's entire second email!
13 Jul 11:49 Christian Decker top-posts to Vladimir's ENTIRE top-posting email!

Later on on the 13th there were more posts by Jeff, Vladimir and Gavin which were fine.

14 Jul 07:08 Dave Smith top-posts three lines to Mike Hearn's earlier email.
15 Jul 15:47 Christian Decker replies to Jeff Garzik's earlier email by quoting it ALL including Jeff's signature(!) and interspersing his comments.
16 Jul 17:13 Luke-Jr top-posts 4 lines to Gavin's earlier email.
16 Jul 18:24 phantomcircuit bottom-posts 4 lines to Jeff's earlier email.
17 Jul 08:12 Brendan Molloy top-posts a one-line question to John Smith's earlier email.
17 Jul 14:37 Douglas Huff top posts a one-line reply to Luke-Jr's earlier email including signature.
17 Jul 20:37 Luke-Jr bottom posts two lines to Gavin's earlier email.
19 Jul 21:54 Doug Huff posts some sort of non-plaintext HTML email.
19 Jul 22:36 Doug Huff posts an inconsequential two-line reply to Gavin's entire earlier email including signature!
20 Jul 02:34 Mark Visser top-posts to Pieter Wuille's entire earlier email including signature.
21 Jul 04:49 Doug Huff posts another HTML email.
22 Jul 13:24 Mike Hearn top-posts to Bobby Groff's entire earlier email including sig.

Fortunately later today there were some good emails by Bobby, Gavin and Mike.

ByteCoin

I suggest that a heavily moderated "Best of Forum" subforum be created at the top level.
As "Best" precedes "Bitcoin" alphabetically this forum would be the top of the list when you visit http://forum.bitcoin.org/

At the moment, certain threads start out as a succession of high quality, information rich, well formatted posts and after a while they get diluted by lots of posts of lower quality.
 
Threads could be nominated for inclusion into the "Best of Forum" section and any replies to the threads would have to meet high standards to be approved.

The "Best of Forum" would be the logical opposite of the "Newbie" forum and would serve as an example of good forum contribution and participation.

If a post contained worthwhile content but was not formatted, spelt or referenced correctly then the writer would be asked to amend it before it was included.

Certain contributors of good standing would have the ability to post new topics directly to the "Best of Forum" but if they abuse this privilege then they would be liable to lose it. Most of the time, contributors so entitled would only choose to do so if the topic was likely to be of significant general import.

ByteCoin

That's not really true. The clients have to approve of the blocks which the miners produce. If the miners start creating "bad" blocks or if the client is altered to reject certain blocks then it just looks to the client as if that portion of the hashing power has disappeared.

If there were any real difference in interests there would be an uneasy truce between miners and clients.
Miners need the clients to give their transactions value.
Clients need the miners to give their transactions security.

I think the clients have the upper hand though as in the past Bitcoin operated without dedicated miners and could do so in future (with appropriate client software changes) if the miners held the network to ransom.

ByteCoin

This may be an appropriate thread to mention that the the "checksum" at the end of an address does not effectively prevent single character errors or transpositions.

For instance https://blockexplorer.com/search/1ByteCoin shows that
are both valid addresses even though they only differ by one character.

Similarly, the valid addresses
only differ by one transposition.

ByteCoin

Mike, thanks for the explanation. I appreciate the effort you spent to write it up. Could you please add a section to the Wiki explaining "lock time", "sequence number" and "transaction replacement" since these seem to be prerequisites for understanding the Contracts article you wrote.

In particular, could you clarify exactly what is compared with the LockTime value to prevent it being replaced and a little word on how LockTime interacts with block chain reorgs in a way that makes it superior to OP_BLOCKNUMBER.

You imply in your post that it could either be a time or a blocknumber. How is this distinction managed?

What is the significance of the sequence number applying to each input instead of the transaction as a whole?

"HashType" such as SIGHASH_NONE, SIGHASH_SINGLE and SIGHASH_ALL could do with being explained.

How does CODESEPARATOR work?



Doesn't the user also have to send the index of the relevant TxOut if Tx1 produced change?


"Inputs" and "sequence numbers". I thought there was only one input, Tx1.

ByteCoin

As people have pointed out, you'd have to rewrite the block and all subsequent blocks.

However, the basic idea is sound. It's true that very large fees would induce rational miners to abandon work on continuing the current block chain and start a new branch which would allow the collection of the fee.

In order to encourage miners to work on the new block chain, the miner that got the huge fee would have to pay the other miners for their blocks on the "old" branch which will never mature, as well as cut them in on the remaining profit from the massive fee. As long as >50% of the hashing power feels adequately compensated then the attack should succeed.

So the new block which collects the fee would also contain transactions which compensate the miners and cut them in. No special communication or negotiation with other miners is required if they are "fee aware"!

The miners in the above scenario act as an ad-hoc cartel for a period of time.

ByteCoin