Document and/or fix a slight inconsistency in the TEAL specification relating to the `intc/bytecblock` and `intc/bytec` instructions

[sskeirik]

Issue

According to the TEAL specification, the intcblock and bytecblock instructions can create constant blocks which have a larger size than are accessible by the intc and bytec instructions.

How is this possible?

• intcblock and bytecblock take an immediate argument of type varuint which is actually just a variable length encoding of a uint64 (so the max size is 2^64 - 1) and describes the size of the constant block they generate (note: the encoding is defined by the Uvarint function in https://golang.org/src/encoding/binary/varint.go which is used to parse these values in the TEAL interpreter)

• intc and bytec take a immediate argument of type uint8 of max size 2^8 - 1 describing an index into the respective constant block.

• the TEAL interpreter does not check that the size of constant blocks generated by intcblock and bytecblock are bounded to what is indexable by an intc or bytec instruction --- instead, the size is only implicitly bounded by:

  1. the maximum logic signature size in the case of stateless TEAL (currently about 1000 bytes)
  2. the maximum application or clear state program size in the case of stateful TEAL (currently about 2000 bytes)

• since a minimum size byte constant stored in a bytecblock instruction takes two bytes (one byte for the size, one byte for the value), one can store 256+ byte constants in a bytecblock instruction within the program size limit with room to spare

• the same principle applies to intcblock, since each integer constant is stored using the varuint encoding, so the minimum size of an integer constant is just one byte (in order to ensure that each constant is unique, some of the constants would require a two byte representation, since each byte in varuint encoding only stores 7 bits)

Potential Responses

1. do nothing, because most contracts will not require that many constants
2. document this behavior to ensure that people do not run into this issue
3. change the validation function for intblock and bytecblock to ensure that they never create constant blocks that are "too large," i.e. have inaccessible constants

I think option (3) is best, because this change is backwards compatible, assuming that no one has put a contract on the chain which generates inaccessible constants (a check which would not be too hard to do). Option (3) also provides flexibility in case TEAL programs become larger in the future so that people want to store and index more constants.

Option (1) is the easiest, clearly, but somewhat less satisfying.

Option (2) requires only slightly less work than option (3) --- so I think (3) is better for that reason.

[brianolson]

1a. do nothing, hypothetical future expansion int and byte ops could fetch from items 256+ and might live in a world with expanded TEAL programs bigger than 1000 bytes?

[brianolson]

The current compiler goal clerk compile will reject a program with the error "cannot have more than 256 int constants"

[sskeirik]

I acknowledge that I only read the source code and did not test compile contracts; I apologize for any lack of diligence on my part.

Returning to the error you mention, I see that error code coming from function:

https://github.com/algorand/go-algorand/blob/28b7ee11df624389737732b4e5fef32eee0fb547/data/transactions/logic/assembler.go#L132

which, based on my analysis, is called by the assembler if you use intc_n, intc, or int instructions.

If one instead chose to manually assemble an intcblock, from my reading of the code, one can exceed the indexable size limit without an error being generated. As far as I can tell, in the manual assembly case, the error would only appear if you tried to index into the constant block beyond the 256th constant.

From my understanding, the error above will appear if one used the int psuedo-op more than 256 times with unique values, because those would compile down to intc instructions, which would eventually exceed the size limit for intc.

Again, I have not interacted with the system at a level beyond reading the code, so I apologize for any false claims made.

EDIT: I also apologize for my arrogant attitude --- assuming that I know things --- instead of asking questions; please forgive me. I will learn from this and file better issues in the future.

[brianolson]

Yup. That's correct. I read this as "there exist valid but not useful TEAL programs". Someone could create a valid LogicSig program that is intcblock {hundreds of values}; int 1 or bytecblock {950 bytes of junk}; int 1. Most of the values would be just a waste of space. I hope people don't do this, but it's not currently against the spec. Algorand has some features of charging higher transaction fees for larger transactions, and so far the existing climate has people writing efficient programs.

[sskeirik]

I understand that this is the way the spec is written. I think the design makes sense with forward compatibility built-in.

I agree with you that, most people will use the standard assembler and int/byte psuedo-ops and thus, this issue will not come up for them. Assuming that, there is not much need to add a warning to assembler/interpreter, though that could still be helpful for debugging TEAL generators.

So, the only thing I can say is: in my case, as someone writing a TEAL interpreter as part of a project, or even for a curious follower of the system, having lots of detail is helpful. Thus, I feel a brief aside in the descriptions of intcblock and bytecblock about this phenomenon would be helpful:

For example, in the intcblock case:

For future extensibility purposes, this opcode can generate constant blocks with more constants than can be accessed via the intc opcode.

Aside from that, I have nothing to add to this issue. Thanks for your time.

[ian-algorand]

Thanks for your contribution! Closing this issue as it seems the discussion mostly resolves it. If you encounter any more issues, please feel free to open another issue or reopen this here.