Solution:
1) Each party publishes their pattern list.
2) Each party generates a keypair and publishes the public key.
3) Everyone adds all the public key points together to get a common public key.
4) Everone searches from that point in some suitable fashion to avoid duplicating work until one of the patterns is matched.
5) The matching offset and all the other private keys are sent to the lucky "owner" of that pattern.
6) Cross off that pattern and go to 2.

A suitable searching strategy for n people would be as follows:
Agree on a numbering x of participants from 0 to n-1 inclusive.
Agree on a batch size m.
Each participant calculates m affine curve points (x+i*n)G where i runs from 0 to m-1 inclusive.
Each participant adds the common public key to each of the above m points, does a bulk inverse, hashes and checks for pattern matches.
If no match is found then the common public key is incremented by mnG and then the last step is repeated.

ByteCoin

For the most efficient method that doesn't waste any coins, read about the subliminal channel in (EC)DSA. Also my posts on the subject 1+ years ago.

ByteCoin

That's pretty well the definition of "spent" for the purposes of this discussion.

Actually, it's more technical than that as you could have a transaction that spends coins from an address and sends them to the same address and it would (probably) still destroy some number of bitcoindays. What you're actually spending is one or more of what is commonly called a "TxOut" which is worth some number of bitcoins. An address can have zero or more spendable TxOuts. In order to spend a TxOut you need to supply an appropriate signature generated using the private key associated with that address.

ByteCoin

I thought I'd transplant Gavin's post to here, rather than derail the original thread.


Using your link for BIP 0012, I didn't see any reference to a timeline. Found it. It could be more prominent.
What's the timeline for enabling relaying of OP_EVAL transactions and for a client that can generate OP_EVAL transactions?
Also, when will clients be patched to start rejecting blocks with the OP_NOP1 interpretation of OP_EVAL?

I presume that, if all goes well, then on the 1st of Feb 2012, blocks containing OP_EVAL will suddenly be interpreted in the new stricter fashion than when it was OP_NOP1. We know that GetTime() seems to return widely disparate results over the bitcoin network. Are we confident that problems are not going to arise because of the pseudorandomly timed nature of the change of interpretation of the opcode?
This is why I suggested a magic transaction in a block to precipitate the changeover.

Majority hashpower support for OP_EVAL is required before changeover. It's conceivable that something might go wrong after OP_EVAL transactions are mainstream which might make miners revert to interpreting OP_EVAL as OP_NOP1. If OP_EVAL loses majority hashpower support then the bitcoin system keeps going but with considerable damage to reputation, prospects and some people's wallets.
Has there been any consideration of this possibility?
I suggest that OP_EVAL transactions be limited to "toy" amounts of bitcoins until enough of the installed base of clients would reject the OP_NOP1 interpretation of OP_EVAL.

ByteCoin

I believe that "crashing when you try to HASH160 an OP_0 byte" is what your scripting code did wrong.

ByteCoin

Correct!

The current block reward scheme and fees schedule incentivizes miners to implement schemes which arguably harm the network. Similarly, some helpful activities like transaction relaying without mining go unrewarded.  There have been forum posts on this topic before but I'm not surprised that they're difficult to find. I touch on a similar issue in the Most transaction relaying is currently pointless and wastefull thread.


Indeed. Also, if the fee is large compared to the block reward then it makes sense for miners to ignore blocks from other miners which include the transaction and try to build a block chain in which they claim the large fee themselves.

If the miners see a double-spent transaction in which the later version includes a very large fee then it would be in their interest to throw away the blocks containing and confirming the first version and build a new chain including the double spend and gaining the fee. Miners who had their blocks orphaned could be reimbursed from the large fees of the double spend.

I'm particularly concerned that there's an incentive for the formation of a mining cartel in which the miners insure that non-cartel miners' blocks become orphaned. The mining cartel could engage in behaviour detrimental to the other users such as refusing to incorporate transactions lacking fees (or lacking inflated fees) into the blocks.

This is just a quick recapitulation of some previous discussions on this topic.

ByteCoin

Interestingly, in order to use LockTime, you have to give at least one of your TxIns a non-standard sequence number. If I recall correctly, there is at least one transaction in the block chain with an unusual sequence number.  
nLockTime affects the flow of execution is in the transaction IsFinal function, which contains the following code (tweaked by me):
It seems that even if nLockTime is larger than some value, the transaction will still be final if all the txins have the normal sequence number. The sequence number seems to have no other effect on execution at the moment as replacement is disabled and so can be set to any other value to produce a "LockTime" transaction.

ByteCoin

I think this is an important point. Currently the analysis that we do is rather ad-hoc and reliant on us thinking of various exploits and how to prevent them. What we should do, as Mike implies is to look at what security guarantees the existing system provides and then systematically check that any proposed changes do not unexpectedly compromise those guarantees.

From the information given, and from the implementation of OP_EVAL that I imagine, I'm having trouble thinking of the assurances that are invalidated by OP_EVAL.

Could you please provide more details Mike?

ByteCoin

This assumption is not safe. If a person is typing in a string they are reading from a piece of paper, when they read a "L" they have it in their heads as a letter "ell" and may type it as "l".


"O" and "0" could be interepreted as the valid "Q" though....

ByteCoin

Ok.

When you see "l", how do you choose whether to change it to "L" or "1" and why?

ByteCoin

This is impossible in general as the checksum does not guarantee the invalidity of an address that differs by the smallest amount from a valid address.

For instance
https://blockexplorer.com/address/1ByteCoinAddressesMatch1kpCWNXmHKW
https://blockexplorer.com/address/1ByteCoinAddressesMatch1kpCxNXmHKW
are both valid addresses even though they differ by only one character.

Similar collisions can be found for omitting one character.

If a new address type is introduced, I suggest the adoption of a shorter error detecting code which provides some guarantees.

If the correction function only results in the replacement of an invalid character with the corresponding valid character then the problem is not relevant. However, if the address contains a lowercase "L" then there's some uncertainty whether it should be converted into "1" or "L" and potentially both might result in valid addresses. I suppose the validity of both interpretations could be checked but this would complicate matters and finding a full set of test cases for the code would not be trivial.

ByteCoin

If such comprehensive changes are being considered then I suggest that the default option should be that the signatures for a transaction should not influence the transaction hash. This would allow transactions spending unsigned transactions to be signed, which is a crucial step in some contracts. Also, the signature data could be pruned from the block chain for transactions occurring at sufficient depth or before a checkpoint. This would effect considerable space savings as the signature data is probably the only data that doesn't compress.

Another improvement would be the introduction of the Bernstein signature scheme with a similar security parameter to the existing ECDSA but a much faster verification. Transactions using the cheaper signatures could get a discount on the fees or be allowed more sigOps. To be clear, the scheme I'm thinking of is "A secure public-key signature system with extremely fast verification" from about 2000.

With regards to key recovery, a 2 bit hint can be used to accellerate the process. Alternatively, a single hint value could be assumed and it would be the responsibility of the signer to redo the signing operation until the assumed hint value is correct.

ByteCoin

I must credit sipa as first raising this issue as far as I know.

There's a bit of a problem with rolling out OP_EVAL using this idea and I believe it may create a more dangerous block chain split than casascius' alternative proposal whereby OP_CHECKSIG gets renamed and re-imagined as a slightly hacked OP_EVAL.

It's true that old clients will be accepting of blocks creating and spending OP_EVAL transactions. This is the advantage you mention.

However, old clients will also be accepting of blocks which contain transactions which incorrectly attempt to spend OP_EVAL transactions with a null scriptSig. As you mentioned in the IRC, the old clients see these OP_EVAL transactions as ones which anyone can redeem.

Miners would be best placed to watch out for transactions in which a null scriptSig can satisfy the scriptPubKey and then include transactions spending them in their blocks. This checking could be implemented now in anticipation of OP_EVAL being introduced in the fashion you propose and the exploit could be fully automated and require no time-consuming user intervention. This means that the bitcoin developers would have little time to react before the fraudulent transactions become confirmed. Clients (and miners) using the new version would reject these blocks but they would at least initially be a minority. People may opt not to upgrade to the new client as it would be easy to portray the new client's behaviour in negative terms. The effect of the above exploit would be to have a block chain split in which the latest clients who are supposedly doing the right thing may end up on the losing side. It would be bad for the public perception of bitcoin if an upgrade voluntarily precipitated a completely optional disaster along these lines.

I think it's more practical for people running old clients to bear the risk of failing to keep their software current. The policy towards incompatible changes will have to decide how much risk is acceptable and how long a time users are guaranteed to be safe running a particular version.

Bitcoin is lacking an effective and reliable mechanism for safely performing block chain splits. The worst-case scenario is one in which mining pools say they have updated their software and patch their clients to look like they are updated but then their software is actually designed maliciously to exploit the incompatibility of the new clients. If a client deployment strategy can cope with this situation then it can probably cope with anything.

Before introducing an incompatible client, I think it's wise to ensure that the existing clients have robust detection of block chain splits.
In particular, if a client sees a succession of what it thinks is invalid blocks with a high difficulty, then instead of banning the peer for misbehaviour, the client should disallow transactions (until overridden) and advise the user that an upgrade may be required.

Another way to limit the financial damage from an exploited rollout would be initially only to allow new incompatible transactions of infinitesimal value; where both the transaction and any change are both suitably small. This limit would increase in some fashion over time unless perhaps a "shutdown" transaction were broadcast which would disable the new behaviour. This shutdown switch could be removed in a subsequent version when no exploits appear and sufficient confidence has been reached. Also, there would have to be an initial prohibition against spending new style transactions into old style transactions.

Also, instead of enabling a feature after a certain block number, it could be introduced after seeing a block containing a particular magic transaction. This protects against the situatuion in which the miners (or the rest of the network) fail to upgrade as quickly as expected.

ByteCoin

True. The fact that it uses the existing scripting system probably makes it easier to implement and considerably reduce the number of test cases to provide code coverage. I am happy to disclaim any credit for the idea if that is desired.

You are right in that OP_CHECKSIG could just be reimplemented so that it effectively does OP_EVAL and appends a OP_CHECKSIG (see postscript) to the decoded script. It would have the advantage of being instantly compatible. I finally understand what you were talking about. In my defense, when you talked about redefining OP_CHECKSIG it sounded very sketchy. I will read your posts more carefully in future.


IsStandard() will probably ensure that OP_EVAL'ed scripts match known whitelisted types with at least one SigOp. So it's not open season on non-standard transaction types yet.  

One disadvantage is that the IsStandard() check will now apply when you're trying to redeem the coins rather than when you're trying to send them. Unfortunately, this means that if IsStandard fails, you probably can't redeem them (short of breaking the hash) until IsStandard is changed. This could result in some distress.

ByteCoin

PS. Obviously the appended OP_CHECKSIG would have to be renamed something else to avoid recursion! This is merely a matter of giving your version of OP_EVAL the number of OP_CHECKSIG and having a new opcode which really just evaluates a sig against a pubkey.

PPS Nope, you're right again. It's no good always having OP_EVAL append an OP_REALCHECKSIG to the decoded script. The case when the decoded script is just a pubKey needs to be recognized and an OP_REALCHECKSIG needs to be appended only in that case for back-compatibility purposes. The special behaviour and the reasons for it would take quite a bit of explaining in the code comments.

I must credit jimrandomh for this quote which put me on the right track.

When I first read this proposal, it sounded to me like casascius was proposing a special scripting language for use with OP_CHECKSIGEX within the existing scripting language. This sounded inelegant; much better to have one scripting language we can use for everything. However I missed the point casascius was trying to make. Here's my version of the same idea using a new opcode OP_EVAL.

At the moment, most scriptPubKeys look like "OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG".
It's easy to see that to satisfy this scriptPubKey you need to supply a scriptSig containing a signature and a public key.
When you send someone your address, it's taken by the current client as an instruction to build a scriptPubKey of the above type when making a payment to that address. This means that one just needs to distribute a shorter public key hash to receive payments rather than the longer public key.
When blockexplorer sees a transaction with the above scriptPubKey it knows that only a public key with the specified hash can be used to satisfy it and hence it's possible to calculate the "balance" of an address.

We could introduce a new address type of the same length (but with incremented version number) and the new opcode. Use of the new address would mean that the intended scriptPubKey would look like "OP_DUP OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_EVAL".
In order to spend the transaction, the holder of that address has to construct a scriptSig which probably looks like "<sig> <script>" where <script> can be treated as a number (OP_DUP'd and OP_HASH160'd) but when OP_EVAL'd expands into a script.

So to duplicate the functionality of the current system, the new address encodes the hash of "<pubKey> OP_CHECKSIG".
Someone sending to that address looks at the version number and knows to construct a scriptPubKey of "OP_DUP OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_EVAL" where scriptHash is decoded from the address in the same way that the pubKeyHash is decoded from current addresses.
To redeem the transaction the address holder supplies the scriptSig of "<sig> <script>" where <script> encodes "<pubKey> OP_CHECKSIG".  Following the explanation of the transaction wiki page

Stack	#	Script	#	Description
Empty	#	<sig> <script> OP_DUP OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_EVAL	#	scriptSig and scriptPubKey are combined.
<sig> <script>	#	OP_DUP OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_EVAL	#	Constants are added to the stack.
<sig> <script><script>	#	OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_EVAL	#	Top stack item is duplicated.
<sig> <script><scriptHashA>	#	<scriptHash> OP_EQUALVERIFY OP_EVAL	#	Top stack item is hashed.
<sig> <script><scriptHashA><scriptHash>	#	OP_EQUALVERIFY OP_EVAL	#	Constant added.
<sig> <script>	#	OP_EVAL	#	Equality is checked between the top two stack items.
<sig>	#	<pubKey> OP_CHECKSIG	#	Script is popped and decoded.
<sig><pubKey>	#	OP_CHECKSIG	#	Constant added.
true	#	empty	#	Signature is checked for top two stack items.

Obviously if the new address encoded the hash of "<pubKey2> CHECKSIGVERIFY <pubKey1> CHECKSIG" then one would have to supply a scriptPubKey of "<sig1> <sig2> <script>" where <script> encodes "<pubKey2> CHECKSIGVERIFY <pubKey1> CHECKSIG" as mentioned above. This would mean that knowledge of two private keys would be needed.
So the above scheme is easily extendable to all multisignature messages.

In order for IsStandard() to still restrict transaction types, it would have to do whitelist template matching on the results of the OP_EVAL.
BlockExplorer could easily be tweaked to show transactions to new addresses.
 
Advantages

• Addresses for arbitraritly complex transactions are fixed forever. No more new address types need be introduced.
• Addresses need only be same length as the current ones, forever.
• Transactions sending to multisignature addresses in this scheme are the same length as normal. This addresses theymos' concern that senders shouldn't be burdened with extra fees from longer scriptPubKeys. Instead, for more complex transactions, the scriptSig is longer which means that the owner of the address bears the cost of potentially increased fees.

On preview - Gavin Andresen has come up with something very similar. I think they are probably functionally identical but my proposal uses only one keyword and I think it will be easier to code than BEGIN & END_DIGEST. Also, in both our schemes the increased length of more complex transactions is in the scriptSig.

I think my proposal might be superior to Gavin's in that it more easily allows both constants and opcodes to be specified whereas Gavin's proposal involves hashing things on the stack and opcodes don't go on the stack, they operate on stack items.

ByteCoin

Could you please outline the contracts which one would be able to construct if one just had nLockTime without transaction replacement?
In particular, there seems to be a lot of general interest in the trust-free cross-chain transactions. Is it possible to do this with the proposed multisignature scripts and the "post-dated cheque" nLockTime you propose.
I believe, the version on the wiki requires replacement.

ByteCoin

I missed this first time round. I will edit this comment on Sunday to address this proposal.

ByteCoin

At the moment, everyone using Bitcoin runs a full-weight network connected client when creating transactions. We hope that this will not be the case in future. In particular it is anticipated that most people will only need to run lightweight clients which don't store the block chain.

I think it's worth agreeing what facilities must be made available in order to have certain functionality.

Firstly, I'd like to discuss creating transactions to new addresses.

At the moment transactions can be created just given the intended recipient's address and knowledge of the details of unspent TxOuts for which one is able to satisfy the scriptPubKey. Your client can create the transaction and you could potentially print it out and send it in a letter.

As an example of the contrary situation, if you just have a FirstBits address as the recipient's address then you no longer have enough information to create a safe transaction. You'd need to either scan the blockchain to work out the full address or (more likely) consult the FirstBits website

So the client doesn't need the block chain or any access to the network. Is the lack of dependence considered vital? How acceptable would it be for the default method of creating a transaction to a new address to require a successful query of the block chain?

ByteCoin

Page 8 of this paper by Bernstein et al. refers to techniques to make signatures deterministic i.e. constant for a given message and key.

A previous comment by khal in this thread shows that some disquiet can arise from the "randomness" of the signature. To avoid this, the random k value could safely be set to the hash of the private key concatenated with the message hash.

This topic also appears here.

Patentability of point compression: I believe that the idea of recovering the y coordinate by plugging x into the field equation and supplying a sign bit is too obvious to be patentable.

ByteCoin

Thanks for that!

My first thought for timejacking is that non-miners have no business having an opinion on what time it is. They should just follow the longest chain. If they choose to start rejecting blocks because they disagree with the time, they should then notice that the apparent hashrate has fallen and freeze. This limits the damage.
With miners, the decision to reject a block based on time is similar to the decision to reject a block because it doesn't clear up enough outstanding transactions, cartel enforcement etc..

ByteCoin