Using OP_CAT

[sukhi]

I want to be able to verify, with the use of secrets and signatures, that the depositor was honest throughout an offline process.  This seems to be achievable only if OP_CAT were enabled, and it unfortunately isn't in bitcoin.

Moreover, I have read that a non-standard transaction script may result in the transaction not being broadcasted by many nodes, namely pool miners, even if the transaction valid.

Among the countless cryptocurrencies that exist, most of which are clones, are there any that allows concatenation (perhaps even a substring function) in the transaction script?

[1714144459]

1714144459

[1714144459]

1714144459

[Omikifuse]

What you talking about?
To the network verify if the transaction is valid, one will need to broadcast the data to the network, and it can't be made offline.

Or I misunderstood you?

[Domino]

OP_CAT has been disabled for a very long time.

Its good if u plz explain this OP_CAT thing. I think this concept is not related to Bitcoin !!!

You can find the details on the bitcoin wiki. https://en.bitcoin.it/wiki/Script

[sukhi]

What you talking about?
To the network verify if the transaction is valid, one will need to broadcast the data to the network, and it can't be made offline.

Or I misunderstood you?

Seems very much that you misunderstood.

I don't want to verify transactions offline.  I want to be able to validate (or not) a transaction based on whether a string validates to a predetermined hash, but that string must be concatenated, i.e. the need for OP_CAT, which is disabled in bitcoin even though I read it is enabled in testnet.  (e.g. hash(secret+phrase)=hardcodedstr)

Perhaps my question wasn't clear:
Among the multitude of cryptocurrencies that are out there, most of which are clone of bitcoin or litecoin, are there any that have the OP_CAT enabled or that provide a way to validate transaction based on a script that is able to concatenate inputs?

[gmaxwell]

An altcoin make a technical change? Keep dreaming.   I am aware of none of them that have this.

It isn't available in testnet either.  It it's just a question of "enabling it"— you have to prevent it from being a memory exhaustion attack via exponential growth. (this isn't theoretically hard but it would, you know, require a little bit of work).

Care to describe your protocol some? it turns out that a lot of things are possible with a bit of transformation.

[sukhi]

An altcoin make a technical change? Keep dreaming.   I am aware of none of them that have this.

Yay!  I like dreaming

I'm trying to look into NXT... and I have a hard time.

It isn't available in testnet either.  It it's just a question of "enabling it"— you have to prevent it from being a memory exhaustion attack via exponential growth. (this isn't theoretically hard but it would, you know, require a little bit of work).

They are enabled already on Testnet so you can try your experiments there.

As for the expodential groth, I read somewhere something like:  Replacing two inputs from the stack with one output that is only as long as the two inputs together... is unlikely to exhaust the memory.  And I agreed very much.

Care to describe your protocol some? it turns out that a lot of things are possible with a bit of transformation.

There are several scenarios:
Casino, dice, gambling:
Say a casino (dice type for this sake) where a secret is held by the house, while the hash of the secret is published in advance of the game.  The numbers "drawned" are determined by hashing the concatenation of a secret and [something else, like a sequence and/or a seed from the player, etc.] which can be verified by the player after the secret is published.

Now, let's say the house is waiting for its "lucky day" and decide that it's the day it cheats, willing to pay the cost of loosing its reputation.  Now the player may prove that the house cheated and may say "well, I can prove that I have been scammed", which doesn't  get him his money back.

Now, let's say the house made a transaction that would pay the player of proof that hash(secret+seq)!=drawnhash, then the player is guaranteed not to be scammed..... unless the house never reveals the secret.

Then the house may make another deposit, which requires the house to publish the secret to the blockchain before a deadline in order to get it refunded.  A transaction that pays the player with a locktime take cares of compensating the player if the secret is never released.

After the funds are deposited, the player may safely play with no possibility of being scammed.  If the house cheats or doesn't publish the secret, it is compensated.

Instant transaction:
Barely-trusted (i.e. untrusted) bank runs its service.

The account holder sends a deposit that is redeemable with:
(proof of bank's wrongdoing + accHolderSig) or
(proof of accHolder's wrongdoing + bankSig) or
(accHolderSig + bankSig)

The account holder signs a transaction, with a locktime that will allow the bank to redeem the funds in the future in case the account holder stops collaborating or disappear.

If the bank wanted to send funds to the account holder, the bank may do so by creating a new transaction that requires the client to declare something like:
"My last transacton was [transaction+amount...] at [sometime in the past]
Today is [date/time]
I collected $y from BankX and acknowledge that [my current balance is now $z"

If we concatenate the parts and verify the signature, the bank could prove that the account holder is not being a gentlemen if he signed contradicting declarations such as "As of today, the last transaction was two days ago" and another message states that a transaction occurred yesterday.

The bank may take that withdrawal at any time, unless the account holder already claimed it legitimately.

The same applies the other way around.  The bank does not fulfill its obligation, the account holder remains unharmed.

And more...
Here, much can be done instantly outside the blockchain, while remaining totally safe for all parties.  If is yet interesting to be able to trust a protocol without having to worry about trusting the centralize bank itself.  Even though this example is about a centralized bank, a protocol can be made so that banks have account with each other... and collaborate in a way that allows inter-bank transactions... and finally a decentralized instant payment network for cryptocurrencies.  (did I say I like dreaming?)

Not only would that allow decentralized instant transaction, but it would also help keeps the blockchain smaller.

...and it seems to me that only OP_CAT is missing. And you know what?  I would argue that this actually IS a bit of transformation, even though it seems that getting it done in bitcoin is not at the door step.  But I am still dreaming

Yes, it also require the actual engines to run this on top of the cryptocurrency... and now I am looking for one over which we can actually build this.

[andytoshi]

I'm trying to look into NXT... and I have a hard time.

Don't waste your energy. They claim to have solved various extremely difficult problems without even acknowledging that they are problems, they are closed-source and they pay a lot of shills. There is not and never has been any evidence of technical innovation from them.

It isn't available in testnet either.  It it's just a question of "enabling it"— you have to prevent it from being a memory exhaustion attack via exponential growth. (this isn't theoretically hard but it would, you know, require a little bit of work).

They are enabled already on Testnet so you can try your experiments there.

I think Peter misunderstood the question he was answering and meant "nonstandard transactions are standard on Testnet". Either that or he was just wrong .

As for the expodential groth, I read somewhere something like:  Replacing two inputs from the stack with one output that is only as long as the two inputs together... is unlikely to exhaust the memory.  And I agreed very much.

Use OP_DUP and OP_CAT in succession, and you will double the size of your (single) input.

[gmaxwell]

As for the expodential groth, I read somewhere something like:  Replacing two inputs from the stack with one output that is only as long as the two inputs together...

Use OP_DUP and OP_CAT in succession, and you will double the size of your (single) input.

To complete the lesson, for those who never liked homework: With a 201 cycle limit, OP_CAT lets you use approximately 534,773,760 YiB memory, vs 102510 bytes without it.

is unlikely to exhaust the memory.  And I agreed very much.

And maybe you will realize why all these altcoins worry me so?  Or perhaps you've got cheaper sources of ram than I do?

[amaclin]

It is possible to set a limit of using OP_CAT. For example, two such operations per script.
I think that original poster can do it himself and play with testnet-in-a-box (or even bitcoin fork!) with extended capabilities.

Later he would share his results with bitcoin community and everyone will receive an answer for what OP_CAT should be included in mainnet.

[jl2012]

As for the expodential groth, I read somewhere something like:  Replacing two inputs from the stack with one output that is only as long as the two inputs together...

Use OP_DUP and OP_CAT in succession, and you will double the size of your (single) input.

To complete the lesson, for those who never liked homework: With a 201 cycle limit, OP_CAT lets you use approximately 534,773,760 YiB memory, vs 102510 bytes without it.

is unlikely to exhaust the memory.  And I agreed very much.

And maybe you will realize why all these altcoins worry me so?  Or perhaps you've got cheaper sources of ram than I do?

I can't get it. If we could overflow the output of OP_ADD, why couldn't we do the same for OP_CAT?

[sukhi]

To complete the lesson, for those who never liked homework: With a 201 cycle limit, OP_CAT lets you use approximately 534,773,760 YiB memory, vs 102510 bytes without it.

is unlikely to exhaust the memory.  And I agreed very much.

And maybe you will realize why all these altcoins worry me so?  Or perhaps you've got cheaper sources of ram than I do?

Touché. Actually, going for a new altcoin... worries me too, which is why I here to try figure is something else out there (something that already exists) would allow the type of conditional transaction validation I am talking about.

Having a maximum output length for the concat would, I guess, solves it.

And how about substr? One could specify the already concatenated string(s) and, if needed, numerical values for the separators.  That would do the job too.

Care to describe your protocol some? it turns out that a lot of things are possible with a bit of transformation.

That's the point.  Maybe bitcoin already has something implemented that allows for what I am trying to do.  Not only that, but what I am trying to do might have already been implemented and I just wasn't successful at finding it.


I have no hope in having any more opcodes enabled in the mainnet, and this threat is not about enabling it; it's about finding the tool(s) to achieve the goal.  Is there another net that allows not necessarily what I think I need (op_cat or op_substr) but at least tools that would allows the type verification I described?  I very much wish that the best answer is NOT an altcoin.

[sukhi]

As for the expodential groth, I read somewhere something like:  Replacing two inputs from the stack with one output that is only as long as the two inputs together...

Use OP_DUP and OP_CAT in succession, and you will double the size of your (single) input.

To complete the lesson, for those who never liked homework: With a 201 cycle limit, OP_CAT lets you use approximately 534,773,760 YiB memory, vs 102510 bytes without it.

is unlikely to exhaust the memory.  And I agreed very much.

And maybe you will realize why all these altcoins worry me so?  Or perhaps you've got cheaper sources of ram than I do?

I can't get it. If we could overflow the output of OP_ADD, why couldn't we do the same for OP_CAT?

There is a big difference between overflowing a numerical value and overflowing memory.

Say you have an 8bit unsigned int, then (200+100) would overflow because the highest value is 255.  The result is then (200+100-256)=44, with a carry bit, or overflow.  In that context, it just means that you passed the maximum numerical value which resets to zero.

Concatenation of strings coupled with duplication would causes the memory (not a number) to overflow, and it could look like this:
abc; OP_DUP;
abc abc; OP_CAT; abcabc; OP_DUP;
abcabc abcabc; OP_CAT; abcabcabcabc; OP_DUP;
abcabcabcabc abcabcabcabc; OP_CAT; abcabcabcabcabcabcabcabc; OP_DUP;
abcabcabcabcabcabcabcabc abcabcabcabcabcabcabcabc; OP_CAT; abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc; OP_DUP;
...and after so long, that would cause a memory overflow, which would result in a CPU fart.

You may read www.redefiningthesacred.com/math4.html which illustrates the power of exponential growth.

[jl2012]

As for the expodential groth, I read somewhere something like:  Replacing two inputs from the stack with one output that is only as long as the two inputs together...

Use OP_DUP and OP_CAT in succession, and you will double the size of your (single) input.

To complete the lesson, for those who never liked homework: With a 201 cycle limit, OP_CAT lets you use approximately 534,773,760 YiB memory, vs 102510 bytes without it.

is unlikely to exhaust the memory.  And I agreed very much.

And maybe you will realize why all these altcoins worry me so?  Or perhaps you've got cheaper sources of ram than I do?

I can't get it. If we could overflow the output of OP_ADD, why couldn't we do the same for OP_CAT?

There is a big difference between overflowing a numerical value and overflowing memory.

Say you have an 8bit unsigned int, then (200+100) would overflow because the highest value is 255.  The result is then (200+100-256)=44, with a carry bit, or overflow.  In that context, it just means that you passed the maximum numerical value which resets to zero.

Concatenation of strings coupled with duplication would causes the memory (not a number) to overflow, and it could look like this:
abc; OP_DUP;
abc abc; OP_CAT; abcabc; OP_DUP;
abcabc abcabc; OP_CAT; abcabcabcabc; OP_DUP;
abcabcabcabc abcabcabcabc; OP_CAT; abcabcabcabcabcabcabcabc; OP_DUP;
abcabcabcabcabcabcabcabc abcabcabcabcabcabcabcabc; OP_CAT; abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc; OP_DUP;
...and after so long, that would cause a memory overflow, which would result in a CPU fart.

You may read www.redefiningthesacred.com/math4.html which illustrates the power of exponential growth.

I surely know what's exponential growth

But the growth could be easily shut down by limiting the length of the output. For example, the script will stop and fail if the output of OP_CAT is bigger than 520bytes (which is also the upper limit of OP_PUSHDATA2)

[sukhi]

I surely know what's exponential growth

I was responding to:

I can't get it. If we could overflow the output of OP_ADD, why couldn't we do the same for OP_CAT?

...pointing out difference between the two overflows.

But the growth could be easily shut down by limiting the length of the output. For example, the script will stop and fail if the output of OP_CAT is bigger than 520bytes (which is also the upper limit of OP_PUSHDATA2)

We established that already:

Having a maximum output length for the concat would, I guess, solves it.

It isn't available in testnet either.  It it's just a question of "enabling it"— you have to prevent it from being a memory exhaustion attack via exponential growth. (this isn't theoretically hard but it would, you know, require a little bit of work).

(my emphasis)

There is also at least one alternative to concatenation, one being:

And how about substr? One could specify the already concatenated string(s) and, if needed, numerical values for the separators.  That would do the job too.

Can you think of any alternative that doesn't require changing the software? (or any software what wouldn't require to be changed?)

[TierNolan]

I can't get it. If we could overflow the output of OP_ADD, why couldn't we do the same for OP_CAT?

OP_CAT allows exponential memory usage.

OP_DUP means duplicate the top item on the stack.

Assume the stack contains a single entry A (length 32 bytes)

Code:

Stack: A  (length=32)

OP_DUP

Stack: A A

OP_CAT

Stack: AA (length=64)

OP_DUP

Stack: AA AA 

OP_CAT

Stack: AAAA (length=128)

OP_DUP

Stack: AAAA AAAA

OP_CAT

Stack: AAAAAAAA (length=256)

Each OP_DUP, OP_CAT call doubles the size of the stack.  After 10 calls, 32 bytes would become 32kB.  After 10 more, it would be 32MB and 10 more would be 32GB and so on (32TB after 10 more). 

An easy fix would be to limit the memory size of the inputs into OP_CAT.

[gmaxwell]

Sure sure, as I said about it's not hard in theory, but theres the lesson— even after I pointed out there was exponential memory usage in a naive implementation the OP thought otherwise.  And before anyone else trips over your egos, it's not that the OP was foolish or anything. There are subtle interactions in the dark corners which make making promises about the behavior difficult.  So while the actual safe behavior isn't fundamentally hard, being confident that all the corner cases and interactions are handled is fundamentally hard.

OP_CAT isn't the only "disabled" opcode with those properties.... e.g. multiplying also does it.

When behavior like this is fixed via limits great care must be taken to make sure the limits are implemented absolutely consistently everywhere or the result is a consensus splitting risk. Alt full node implementers have repeatedly implemented the limits wrong— even when they're obvious in the code, called out in the comments, documented on the wiki, etc... even by just simply not implementing them (... coverage analysis and testing against the blockchain can't tell you about limits that you're just missing completely).

Going back to the OP's question. I'm not seeing how OP_CAT (at least by itself) facilitates any of the high level examples there. Can you give me a specific protocol and set of scripts to show me how it would work?

[jl2012]

When behavior like this is fixed via limits great care must be taken to make sure the limits are implemented absolutely consistently everywhere or the result is a consensus splitting risk. Alt full node implementers have repeatedly implemented the limits wrong— even when they're obvious in the code, called out in the comments, documented on the wiki, etc... even by just simply not implementing them (... coverage analysis and testing against the blockchain can't tell you about limits that you're just missing completely).

I'm not a programmer so this may sound very stupid:

MAX_BLOCK_SIZE = 1MB: not risky(?)
Max push size = 520 bytes: not risky(?)
Max script size = 10000 bytes: not risky(?)
Max OP_CAT output size = 520 bytes: why risky?

I mean, is there any fundamental difference between these cases?

[gmaxwell]

I'm not a programmer so this may sound very stupid:
[...]
Max OP_CAT output size = 520 bytes: why risky?
I mean, is there any fundamental difference between these cases?

All the limits are risks, all complexity— practically every one of them has been implemented incorrectly by one alternative full node implementation or another (or Bitcoin core itself) at some point. They miss them completely, or count wrong for them, or respond incorrectly when they're violated.  E.g. here what happens if you OP_CAT 520 and 10 bytes? Should the verify fail? Should the result be truncated? But even that wasn't the point here.

Point here was that realizing you _needed_ a limit and where you needed it was a risk.  The reasonable and pedantically correct claim was made that OP_CAT didn't increase memory usage, that it just took two elements and replaced them with one which was just as large as the two... and yet having (unfiltered) OP_CAT in the instruction set bypasses the existing limits and allowed exponential memory usage.

None of it insurmountable, but I was answering the question as to why it's not just something super trivial.

[andytoshi]

I'd add that the blocksize and scriptsize limits are easy to check -- you just have to look at the data on the wire, not understand it at all. Any limit on script stack objects is going to be nasty: script is an intricate machine with many, many weird corner cases that interact in surprising (at least) ways.

Point here was that realizing you _needed_ a limit and where you needed it was a risk.

This is probably the most important point. I had initially typed up a long reply explaining what needs to be done for OP_PUSH or OP_CAT limits (which are conceptually not so bad, but you have to be exhaustive and expect all implementors to be identically exhaustive). And then I thought, "Why did I do that? To stop stack size explosions, I guess...but did I stop that? No idea." because I would have to analyze the interactions with every single other part of the script system, and neither I nor anybody else has a complete model there. (Though I *think* I have a complete model of how everything affects the size of stack objects, at least right now.) So that's where the risk comes from.

[TierNolan]

And then I thought, "Why did I do that? To stop stack size explosions, I guess...but did I stop that? No idea." because I would have to analyze the interactions with every single other part of the script system, and neither I nor anybody else has a complete model there. (Though I *think* I have a complete model of how everything affects the size of stack objects, at least right now.) So that's where the risk comes from.

Why indirectly solve the problem?  The problem is limited stack size, so why not just directly solve it?

Set a maximum total memory for the stack and a script that exceeds that value automatically fails.

This requires setting a size for each data type.  I think it is basically integer, byte array and boolean (which is an int).

A slightly less direct method is to focus on the opcodes that can increase the stack size.  Even then, it is still really a global limit.