Topic: Using OP_CAT (Read 4560 times)

Ah, sweet.

I guess we already fulfill this in my demo example (this script run with the --ecc-voodoo flag):
https://github.com/edmundedgar/realitykeys-examples/blob/master/realitykeysdemo.py
...because for convenience we have Alice and Bob temporarily queue up the funds that they intend to put into the contract transaction by paying to the hash of their own pubkey, so the contract transaction never happens unless they can both fund it by signing with the private keys of the pubkeys they've exchanged.


I haven't been able to find this so any more hints would be helpful, although I'm learning a lot wading through various IRC logs looking for it...

You just have to have alice and bob prove that they know the discrete logs of their own pubkeys (e.g. they sign a message with it while setting up their exchange). Work through the algebra and you'll see why.

If you have logs for #bitcoin from last year, I walked through the somewhat different pay to contract case, which is I think mostly what you're referring to-- in that case you alwas make the contract key G*HMAC(message,pubkey) to avoid someone setting their pubkey to an alternative contract.

Sorry for hijacking the thread over this but just one thing to add on this pattern to avoid people getting into trouble - hopefully gmaxwell will correct me if I've got this wrong.

Since these x + a and y + b operations are invertible, you need to be careful that Alice doesn't know x, and Bob doesn't know y, until they've shown each other their own keys, a and b respectively. If they know the Reality Keys pubkeys in advance, it seems to be possible to make a special tricksy a or b key such that, when combined to make q or r, the owner could get the combined private key Q or R without knowing the relevant Reality Key private key X or Y.

See Alan Reiner's comment here:
http://permalink.gmane.org/gmane.comp.bitcoin.devel/4173

In theory it looks like everything should be OK as long as you don't register the Reality Key until after you've seen the other party's public key, but if you're able to avoid this restriction it would be safer; Not only do you have to make sure you do everything in the right order, you also have to rely on us (Reality Keys) keeping our public keys secret until after you've made the exchange. The public keys are indeed supposed to be secret until they're allocated, but they're harder for us to secure than the private keys, since we need to be able to give them out to people on demand in real time. (Also there are some benefits to the same keys being shared for multiple people's contracts, rather than being assigned uniquely every time.)

I suspect you could defeat tricksy key attacks by Alice and Bob each producing an extra private key, sending it to their counter-party and requiring them to combine it with their Reality Key in a non-invertible operation, but I'm too far out of my depth to assess this. (It might also have some privacy benefits, so I'd be interested to hear what knowledgeable people think.) For now when I've been building demo applications on Reality Keys I've gone with the non-standard branching transaction approach, since sending these transactions to Eligius is practical at the moment and they should become standard in the next major Bitcoin release.

Does that mean yes or no?

What does it mean and imply that it's part of the main branch?

Is there ETA for the next major release?

There is a plan that P2SH will effectively accept nearly all scripts.

https://github.com/gavinandresen/bitcoin-git/commit/7f3b4e95695d50a4970e6eb91faa956ab276f161
https://github.com/bitcoin/bitcoin/blob/master/src/main.cpp#L692

https://gist.github.com/gavinandresen/88be40c141bc67acb247

The limit is that your script must be less than 520 bytes and can't have more than 15 signature operations.

The update will presumably be in the next major release, since it is part of the main branch.

I'd just like to emphasize that it is the core of my last post.  Can anyone answer that?

The script may be perfectly fine, but would bitcoin mainnet nodes broadcast transactions that contains that script?


I need a definition of what a standard script is and what a non-standard script is; the bitcoind gives me:

And I think I missed a few OP_DROPs
What operation do you suspect I am confusing?
The stack goes like this:

inputs	pubkey signature password
OP_DUP	pubkey pubkey signature password
	pubkeyA pubkey pubkey signature password
OP_EQUAL	isAlice pubkey signature password
OP_IF	pubkey signature password
	BobsHash pubkey signature password
OP_ELSE
	pubkeyB pubkey signature password
OP_EQUALVERIF	isBob pubkey signature password
OP_DROP	pubkey signature password
	AlicesHash pubkey signature password
OP_ENDIF	HashY pubkeyX signature passwordY
OP_ROT	pubkeyX signature HashY passwordY
OP_CHECKSIGVERIFY	true HashY passwordY
OP_DROP	HashY passwordY
OP_SWAP	passwordY HashY
OP_HASH160	PasswordY_hash HashY
OP_EQUAL	Signature-Password match

I have seen OP_EVAL in some places, as well as other OPs that I don't find at https://en.bitcoin.it/wiki/Script.  What and where do I find documentation about those?


Starting from the fact that I don't have OP_CAT and that I don't count of having it, I focus on finding alternative ways rather than to develop protocols that requires something I don't have.  I'll give an example if (and when) I get there; what I have is still too incomplete and abstract.


Yes, atomic transaction; for balance update or for winning-losing a dice bet.  A third party is unacceptable, which rules out the reality keys.

So this "semantic leak" is now only apparent in the block layout on the wire and on the disk? But the "abstract virtual machine" of Bitcoin script cannot discover its internal bit ordering? Do I understand you right?

Then can you state again what is the possible attack that the "opcode limit" is protecting against?

Thanks.

Not so. We proved there were no semantic leaks from OpenSSL in the numbers on the stack via exhaustive testing some time ago and removed all use of OpenSSL from the script code (except the calls out for signature verification, of course— so only signature verification and the accompanying signature serialization are handled by it).
Also not so, very intentionally not.

You can't use P2SH to create loops and nobody said anything about loops anyway.

I'm sorry I haven't kept with the advances in the theoretical computer science. But I believe we have already discussed the "non-TC" chestnut here and the consensus was that one can abuse P2SH to escape the "no-loops" restriction.

Let me try to dig the thread and I will edit this message later. Edit:

https://bitcointalksearch.org/topic/m.6533466

The operative words were "opcode limit" in the "Turing complete language vs non-Turing complete (Ethereum vs Bitcoin)" thread.

I apologize for writing too ambiguously the first time. I'm going to try to linearize my thoughts better now:

1) Given the current Bitcoin script language with the following problems (amongst others):

1a) implicit conversions between integers and bit strings with semantics depending on precise detail of OpenSSL implementation (word size, word order in a large integer, byte order in a word)
1b) ostensibly allowing emulating iteration by mutual recursion of P2SH invocations

2) a non-binary compatible but only morally-compatible scripting language featuring:

2a) explicit type conversion operators and type tagging of the stack storage, in particular clean conversions between integers and bit strings
2b) somehow type-safe or type-checking implementation of P2SH invocation that verifies both arguments and return values

3) will allow writing a completely new scripting interpreter

3a) in a theoretically strong programming language like a Lisp subset that is provable (Lisp because I'm most familiar with it, but there are many other candidates, I did not keep up with recent developments in the theoretical computer science)
3b) that can be mechanically/automatically verified and proven to obey certain theorems and conditions

4) said interpreter then can be translated

4a) to C/C++/Java/etc. via completely mechanical translation or manual pattern-based transliteration of a very restricted subset Lisp to be incorporated in a software-only implementation
4b) to SystemC/Verilog/VHDL/etc. to be synthesized into a logic circuit (with stack memory) for the hardware-assisted implementations and for additional verification

The 4a) output in a restricted C++ subset could then replace the current, completely improvised, implementation in Bitcoin core. Because of subset C++ use it most likely would be longer in terms of lines of code, but it would be also much simpler to analyze.

The 3b) step has an additional problem that all the existing Lisp provers use only conventional ring of integers arithmetic. Since Bitcoin depends on an elliptic curve over a finite field the proving software would have to be extended to efficiently handle that. From my school days algebra I remember that the stratification group->ring->field significantly influences the complexity of proofs. Sliding back from "ring of integers" to "abelian group of elliptic curves" could potentially greatly reduce the set of theorems that could be mechanically proven.

I realize that the points 1-4 still read like a complex sentence in a patent application. I'm not good at writing easy to read essays. But from the purely technical point of view the two-level process is the way to maximize correctness (1st language for proving/verification, 2nd language for implementation/integration).
 

We are not talking about von Neumann architecture. We are talking about a small non-TC stack machine without mutability and a fixed opcode limit. In this case the set of allowable programs absolutely does shrink, and more importantly, the space of accepting inputs for (most) given scripts shrinks. This is easy to see --- consider the program OP_VERIFY. There would be one permissible top stack element in a typed script; in untyped script every legal stack element in (0x80|0x00)0x00* is permissible.

That said, nobody actually said that anything about the space of provable programs. What I said is that script would be easier to analyze. This is obviously true because of the tighter restrictions on stack elements, as I already illustrated. As another example, consider the sequence OP_CHECKSIG OP_CHECKSIG which always returns zero. One reason this is true today is that the output of OP_CHECKSIG always has length one while the top element of its accepting input always has length > one. To analyze script today you need to carry around these sorts of length restrictions; with typing you only need to carry around the data that CHECKSIG's output is boolean and its input is a bytestring.

That script is perfectly standard as a P2SH in current code.

Though I suspect you've confused the operation of the machine somewhat.

I'm not asking you to prove that OP_CAT is necessary,  I'm asking you to describe a specific, complete, protocol for which it is sufficient— something that starts with Alice and Bob and Charlie who want to accomplish a task, and a series of specific messages they send, and a series of guaranteed outcomes. Then I could try to help you reimagine a functionally equivalent protocol without it.

It sounds like you're describing an atomic swap or a related transaction. Often they don't need two hashes.  If you really just want something conditionally redeemable by one person or another, I would recommend the transaction type I recommend for reality keys:

Reality keys will reveal private key A if a true/false fact is true, and private key B if it's false.

Alice and Bob want to make a contract to hedge the outcome of a fact because they each have opposing short positions relative to the fact.  Alice will be paid if the fact is true, Bob will be paid if the fact is false.

Reality keys publishes the pubkey pairs  a := gA ; b := gB

Alice has private key X and corresponding pubkey x, Bob has private key Y and corresponding pubkey y.

Alice and Bob compute new pubkeys  q:=x+a  and r:=y+b  and they send their coins to a 1 of 2 multisig of those new pubkeys, q,r.

The values q,r are zero-knoweldge indistinguishable from a and b unless you know x and/or y, so no one except alice and bob, not even reality keys can tell which transaction on the network is mediated by the release of A vs B.

Later, realitykeys releases A or B,  lets say alice wins.  She computes a new private key X+A, and uses it to redeem the multisig.  Bob cannot redeem the multisig because he knows neither X or B.

This looks like a perfectly boring transaction to everyone else. Alice and Bob collectively cannot be robbed by a third party, though they could be held up or if realitykeys conspires with Alice or Bob then there could be cheating. This risk could be reduced by using a threshold of multiple observers— which this scheme naturally extends to.

I absolutely agree that additional type data makes for software which is easier to analyze. The question isn't the result of the program being provable, the question is of the implementations of the interpreter being simple enough to have even a small chance of having multiple absolutely identically behaving implementations, since we are performing this inside of a consensus system.

You continue to miss the point completely.

This claim about "typed data" and "provability" is false. There are actual proofs of that coming from the people involved in designing/implementing Algol 68. I don't have any references handy, but in broad terms the progression "classic Von Neumann" -> "type-tagged Von Neumann" -> "static-typed Von Neumann/Harvard modification" strictly increases the set of programs that have provable results. I also remember than in the USA IBM did pay for some academic research about "PL/I without implicit type coercion" that had similar results.

As an aside to the theoretical results: in school I had side income helping debug/fix/extend several RPN-style / Forth-style language interpreters including then-popular commercial implementations by Tektronix & HP in their IEEE-488 lab-control equipment. For that application type-tagging was (and is) a godsend both for human programming and for automated program analysis/translation.

Right there, I started feeling skeptical about your post.


How is that useful?  The problem is not about being able to do nice scripts and use them properly, but about avoiding the possibility of making any script that could potentially... get naughty.

Quote from: jl2012 on September 03, 2014, 11:08:37 PM

Call it OP_LIMITCAT, and disallow the use of a bare OP_CAT.

How is that better than implementing OP_CAT correctly in the first place?  Wouldn't that "alias" require the nasty bare OP_CAT to be "present"?  It sounds like you are saying "Instead of doing the checks in the OP_CAT itself, let's make an improper OP_CAT that we cannot use directly, and make an alias that does the checks before calling the improper OP_CAT that doesn't do these checks"

Am I totally misunderstanding you?