algorand · tsachiherman · May 14, 2021 · Mar 15, 2021 · Mar 19, 2021 · Apr 27, 2021
diff --git a/cmd/goal/clerk.go b/cmd/goal/clerk.go
@@ -1080,13 +1080,10 @@ var dryrunCmd = &cobra.Command{
 				reportErrorf("program size too large: %d > %d", len(txn.Lsig.Logic), params.LogicSigMaxSize)
 			}
 			ep := logic.EvalParams{Txn: &txn, Proto: &params, GroupIndex: i, TxnGroup: txgroup}
-			cost, err := logic.Check(txn.Lsig.Logic, ep)
+			err := logic.Check(txn.Lsig.Logic, ep)
 			if err != nil {
 				reportErrorf("program failed Check: %s", err)
 			}
-			if uint64(cost) > params.LogicSigMaxCost {
-				reportErrorf("program cost too large: %d > %d", cost, params.LogicSigMaxCost)
-			}
 			sb := strings.Builder{}
 			ep = logic.EvalParams{
 				Txn:        &txn,
@@ -1097,7 +1094,7 @@ var dryrunCmd = &cobra.Command{
 			}
 			pass, err := logic.Eval(txn.Lsig.Logic, ep)
 			// TODO: optionally include `inspect` output here?
-			fmt.Fprintf(os.Stdout, "tx[%d] cost=%d trace:\n%s\n", i, cost, sb.String())
+			fmt.Fprintf(os.Stdout, "tx[%d] trace:\n%s\n", i, sb.String())
 			if pass {
 				fmt.Fprintf(os.Stdout, " - pass -\n")
 			} else {

diff --git a/config/consensus.go b/config/consensus.go
@@ -910,6 +910,9 @@ func initConsensusProtocols() {
 	// Enable transaction Merkle tree.
 	vFuture.PaysetCommit = PaysetCommitMerkle
 
+	// Enable TEAL 4
+	vFuture.LogicSigVersion = 4
+
 	Consensus[protocol.ConsensusFuture] = vFuture
 }
 

diff --git a/daemon/algod/api/server/v2/dryrun_test.go b/daemon/algod/api/server/v2/dryrun_test.go
@@ -346,8 +346,9 @@ func init() {
 
 	// legder requires proto string and proto params set
 	var proto config.ConsensusParams
-	proto.LogicSigVersion = 2
-	proto.LogicSigMaxCost = 1000
+	proto.LogicSigVersion = 4
+	proto.LogicSigMaxCost = 20000
+	proto.MaxAppProgramCost = 700
 	proto.MaxAppKeyLen = 64
 	proto.MaxAppBytesValueLen = 64
 

diff --git a/data/transactions/logic/.gitignore b/data/transactions/logic/.gitignore
@@ -0,0 +1,2 @@
+langspec.json
+teal.tmLanguage.json
diff --git a/data/transactions/logic/README.md b/data/transactions/logic/README.md
@@ -27,7 +27,7 @@ A program can either authorize some delegated action on a normal private key sig
 * If the account has signed the program (an ed25519 signature on "Program" concatenated with the program bytes) then if the program returns true the transaction is authorized as if the account had signed it. This allows an account to hand out a signed program so that other users can carry out delegated actions which are approved by the program.
 * If the SHA512_256 hash of the program (prefixed by "Program") is equal to the transaction Sender address then this is a contract account wholly controlled by the program. No other signature is necessary or possible. The only way to execute a transaction against the contract account is for the program to approve it.
 
-The TEAL bytecode plus the length of any Args must add up to less than 1000 bytes (consensus parameter LogicSigMaxSize). Each TEAL op has an associated cost estimate and the program cost estimate must total less than 20000 (consensus parameter LogicSigMaxCost). Most ops have an estimated cost of 1, but a few slow crypto ops are much higher.
+The TEAL bytecode plus the length of any Args must add up to less than 1000 bytes (consensus parameter LogicSigMaxSize). Each TEAL op has an associated cost and the program cost must total less than 20000 (consensus parameter LogicSigMaxCost). Most ops have a cost of 1, but a few slow crypto ops are much higher. Prior to v4, program costs was estimated as the static sum of all opcode costs in a program (ignoring conditionals that might skip some code).  Beginning with v4, a program's cost is tracked dynamically, while being evaluated. If the program exceeds its budget, it fails.
 
 ## Execution modes
 
@@ -80,11 +80,6 @@ An application transaction must indicate the action to be taken following the ex
 ## Operations
 
 Most operations work with only one type of argument, uint64 or bytes, and panic if the wrong type value is on the stack.
-The instruction set was designed to execute calculator-like expressions.
-What might be a one line expression with various parenthesized clauses should be efficiently representable in TEAL.
-
-Looping is not possible, by design, to ensure predictably fast execution.
-There is a branch instruction (`bnz`, branch if not zero) which allows forward branching only so that some code may be skipped.
 
 Many programs need only a few dozen instructions. The instruction set has some optimization built in. `intc`, `bytec`, and `arg` take an immediate value byte, making a 2-byte op to load a value onto the stack, but they also have single byte versions for loading the most common constant values. Any program will benefit from having a few common values loaded with a smaller one byte opcode. Cryptographic hashes and `ed25519verify` are single byte opcodes with powerful libraries behind them. These operations still take more time than other ops (and this is reflected in the cost of each op and the cost limit of a program) but are efficient in compiled code space.
 
@@ -129,6 +124,7 @@ For two-argument ops, `A` is the previous element on the stack and `B` is the la
 | `~` | bitwise invert value X |
 | `mulw` | A times B out to 128-bit long result as low (top) and high uint64 values on the stack |
 | `addw` | A plus B out to 128-bit long result as sum (top) and carry-bit uint64 values on the stack |
+| `divw` | Pop four uint64 values.  The deepest two are interpreted as a uint128 dividend (deepest value is high word), the top two are interpreted as a uint128 divisor.  Four uint64 values are pushed to the stack. The deepest two are the quotient (deeper value is the high uint64). The top two are the remainder, low bits on top. |
 | `getbit` | pop a target A (integer or byte-array), and index B. Push the Bth bit of A. |
 | `setbit` | pop a target A, index B, and bit C. Set the Bth bit of A to C, and push the result |
 | `getbyte` | pop a byte-array A and integer B. Extract the Bth byte of A and push it as an integer |
@@ -297,6 +293,8 @@ Asset fields include `AssetHolding` and `AssetParam` fields that are used in `as
 | `swap` | swaps two last values on stack: A, B -> B, A |
 | `select` | selects one of two values based on top-of-stack: A, B, C -> (if C != 0 then B else A) |
 | `assert` | immediately fail unless value X is a non-zero number |
+| `callsub target` | branch unconditionally to TARGET, saving the next instruction on the call stack |
+| `retsub` | pop the top instruction from the call stack and branch to it |
 
 ### State Access
 
@@ -384,12 +382,13 @@ A '[proto-buf style variable length unsigned int](https://developers.google.com/
 
 # What TEAL Cannot Do
 
-Current design and implementation limitations to be aware of.
+Design and implementation limitations to be aware of with various versions of TEAL.
 
 * TEAL cannot create or change a transaction, only approve or reject.
 * Stateless TEAL cannot lookup balances of Algos or other assets. (Standard transaction accounting will apply after TEAL has run and authorized a transaction. A TEAL-approved transaction could still be invalid by other accounting rules just as a standard signed transaction could be invalid. e.g. I can't give away money I don't have.)
 * TEAL cannot access information in previous blocks. TEAL cannot access most information in other transactions in the current block. (TEAL can access fields of the transaction it is attached to and the transactions in an atomic transaction group.)
 * TEAL cannot know exactly what round the current transaction will commit in (but it is somewhere in FirstValid through LastValid).
 * TEAL cannot know exactly what time its transaction is committed.
-* TEAL cannot loop. Its branch instructions `bnz` "branch if not zero", `bz` "branch if zero" and `b` "branch" can only branch forward so as to skip some code.
-* TEAL cannot recurse. There is no subroutine jump operation.
+* TEAL cannot loop prior to v4. In v3 and prior, the branch instructions `bnz` "branch if not zero", `bz` "branch if zero" and `b` "branch" can only branch forward so as to skip some code.
+* Until v4, TEAL had no notion of subroutines (and therefore no recursion). As of v4, use `callsub` and `retsub`.
+* TEAL cannot make indirect jumps. `b`, `bz`, `bnz`, and `callsub` jump to an immediately specified address, and `retsub` jumps to the address currently on the top of the call stack, which is manipulated only by previous calls to `callsub`.
diff --git a/data/transactions/logic/README_in.md b/data/transactions/logic/README_in.md
@@ -27,7 +27,7 @@ A program can either authorize some delegated action on a normal private key sig
 * If the account has signed the program (an ed25519 signature on "Program" concatenated with the program bytes) then if the program returns true the transaction is authorized as if the account had signed it. This allows an account to hand out a signed program so that other users can carry out delegated actions which are approved by the program.
 * If the SHA512_256 hash of the program (prefixed by "Program") is equal to the transaction Sender address then this is a contract account wholly controlled by the program. No other signature is necessary or possible. The only way to execute a transaction against the contract account is for the program to approve it.
 
-The TEAL bytecode plus the length of any Args must add up to less than 1000 bytes (consensus parameter LogicSigMaxSize). Each TEAL op has an associated cost estimate and the program cost estimate must total less than 20000 (consensus parameter LogicSigMaxCost). Most ops have an estimated cost of 1, but a few slow crypto ops are much higher.
+The TEAL bytecode plus the length of any Args must add up to less than 1000 bytes (consensus parameter LogicSigMaxSize). Each TEAL op has an associated cost and the program cost must total less than 20000 (consensus parameter LogicSigMaxCost). Most ops have a cost of 1, but a few slow crypto ops are much higher. Prior to v4, program costs was estimated as the static sum of all opcode costs in a program (ignoring conditionals that might skip some code). Beginning with v4, a program's cost is tracked dynamically, while being evaluated. If the program exceeds its budget, it fails.
 
 ## Execution modes
 
@@ -57,11 +57,6 @@ Constants are pushed onto the stack by `intc`, `intc_[0123]`, `bytec`, and `byte
 ## Operations
 
 Most operations work with only one type of argument, uint64 or bytes, and panic if the wrong type value is on the stack.
-The instruction set was designed to execute calculator-like expressions.
-What might be a one line expression with various parenthesized clauses should be efficiently representable in TEAL.
-
-Looping is not possible, by design, to ensure predictably fast execution.
-There is a branch instruction (`bnz`, branch if not zero) which allows forward branching only so that some code may be skipped.
 
 Many programs need only a few dozen instructions. The instruction set has some optimization built in. `intc`, `bytec`, and `arg` take an immediate value byte, making a 2-byte op to load a value onto the stack, but they also have single byte versions for loading the most common constant values. Any program will benefit from having a few common values loaded with a smaller one byte opcode. Cryptographic hashes and `ed25519verify` are single byte opcodes with powerful libraries behind them. These operations still take more time than other ops (and this is reflected in the cost of each op and the cost limit of a program) but are efficient in compiled code space.
 
@@ -183,12 +178,13 @@ A '[proto-buf style variable length unsigned int](https://developers.google.com/
 
 # What TEAL Cannot Do
 
-Current design and implementation limitations to be aware of.
+Design and implementation limitations to be aware of with various versions of TEAL.
 
 * TEAL cannot create or change a transaction, only approve or reject.
 * Stateless TEAL cannot lookup balances of Algos or other assets. (Standard transaction accounting will apply after TEAL has run and authorized a transaction. A TEAL-approved transaction could still be invalid by other accounting rules just as a standard signed transaction could be invalid. e.g. I can't give away money I don't have.)
 * TEAL cannot access information in previous blocks. TEAL cannot access most information in other transactions in the current block. (TEAL can access fields of the transaction it is attached to and the transactions in an atomic transaction group.)
 * TEAL cannot know exactly what round the current transaction will commit in (but it is somewhere in FirstValid through LastValid).
 * TEAL cannot know exactly what time its transaction is committed.
-* TEAL cannot loop. Its branch instructions `bnz` "branch if not zero", `bz` "branch if zero" and `b` "branch" can only branch forward so as to skip some code.
-* TEAL cannot recurse. There is no subroutine jump operation.
+* TEAL cannot loop prior to v4. In v3 and prior, the branch instructions `bnz` "branch if not zero", `bz` "branch if zero" and `b` "branch" can only branch forward so as to skip some code.
+* Until v4, TEAL had no notion of subroutines (and therefore no recursion). As of v4, use `callsub` and `retsub`.
+* TEAL cannot make indirect jumps. `b`, `bz`, `bnz`, and `callsub` jump to an immediately specified address, and `retsub` jumps to the address currently on the top of the call stack, which is manipulated only by previous calls to `callsub`.
diff --git a/data/transactions/logic/TEAL_opcodes.md b/data/transactions/logic/TEAL_opcodes.md
@@ -18,7 +18,7 @@ Ops have a 'cost' of 1 unless otherwise specified.
 - SHA256 hash of value X, yields [32]byte
 - **Cost**:
    - 7 (LogicSigVersion = 1)
-   - 35 (2 <= LogicSigVersion <= 3)
+   - 35 (2 <= LogicSigVersion <= 4)
 
 ## keccak256
 
@@ -28,7 +28,7 @@ Ops have a 'cost' of 1 unless otherwise specified.
 - Keccak256 hash of value X, yields [32]byte
 - **Cost**:
    - 26 (LogicSigVersion = 1)
-   - 130 (2 <= LogicSigVersion <= 3)
+   - 130 (2 <= LogicSigVersion <= 4)
 
 ## sha512_256
 
@@ -38,7 +38,7 @@ Ops have a 'cost' of 1 unless otherwise specified.
 - SHA512_256 hash of value X, yields [32]byte
 - **Cost**:
    - 9 (LogicSigVersion = 1)
-   - 45 (2 <= LogicSigVersion <= 3)
+   - 45 (2 <= LogicSigVersion <= 4)
 
 ## ed25519verify
 
@@ -74,6 +74,8 @@ Overflow is an error condition which halts execution and fails the transaction.
 - Pushes: uint64
 - A divided by B. Panic if B == 0.
 
+`divw` is available to divide the two-element values produced by `mulw` and `addw`.
+
 ## *
 
 - Opcode: 0x0b
@@ -219,6 +221,14 @@ Overflow is an error condition which halts execution and fails the transaction.
 - A plus B out to 128-bit long result as sum (top) and carry-bit uint64 values on the stack
 - LogicSigVersion >= 2
 
+## divw
+
+- Opcode: 0x1f
+- Pops: *... stack*, {uint64 A}, {uint64 B}, {uint64 C}, {uint64 D}
+- Pushes: *... stack*, uint64, uint64, uint64, uint64
+- Pop four uint64 values.  The deepest two are interpreted as a uint128 dividend (deepest value is high word), the top two are interpreted as a uint128 divisor.  Four uint64 values are pushed to the stack. The deepest two are the quotient (deeper value is the high uint64). The top two are the remainder, low bits on top.
+- LogicSigVersion >= 4
+
 ## intcblock uint ...
 
 - Opcode: 0x20 {varuint length} [{varuint value}, ...]
@@ -513,18 +523,18 @@ for notes on transaction fields available, see `txn`. If top of stack is _i_, `g
 
 ## bnz target
 
-- Opcode: 0x40 {0..0x7fff forward branch offset, big endian}
+- Opcode: 0x40 {int16 branch offset, big endian. (negative offsets are illegal before v4)}
 - Pops: *... stack*, uint64
 - Pushes: _None_
 - branch to TARGET if value X is not zero
 
-The `bnz` instruction opcode 0x40 is followed by two immediate data bytes which are a high byte first and low byte second which together form a 16 bit offset which the instruction may branch to. For a bnz instruction at `pc`, if the last element of the stack is not zero then branch to instruction at `pc + 3 + N`, else proceed to next instruction at `pc + 3`. Branch targets must be well aligned instructions. (e.g. Branching to the second byte of a 2 byte op will be rejected.) Branch offsets are currently limited to forward branches only, 0-0x7fff. A future expansion might make this a signed 16 bit integer allowing for backward branches and looping.
+The `bnz` instruction opcode 0x40 is followed by two immediate data bytes which are a high byte first and low byte second which together form a 16 bit offset which the instruction may branch to. For a bnz instruction at `pc`, if the last element of the stack is not zero then branch to instruction at `pc + 3 + N`, else proceed to next instruction at `pc + 3`. Branch targets must be well aligned instructions. (e.g. Branching to the second byte of a 2 byte op will be rejected.) Branch offsets are limited to forward branches only, 0-0x7fff until v4. v4 treats offset as a signed 16 bit integer allowing for backward branches and looping.
 
 At LogicSigVersion 2 it became allowed to branch to the end of the program exactly after the last instruction: bnz to byte N (with 0-indexing) was illegal for a TEAL program with N bytes before LogicSigVersion 2, and is legal after it. This change eliminates the need for a last instruction of no-op as a branch target at the end. (Branching beyond the end--in other words, to a byte larger than N--is still illegal and will cause the program to fail.)
 
 ## bz target
 
-- Opcode: 0x41 {0..0x7fff forward branch offset, big endian}
+- Opcode: 0x41 {int16 branch offset, big endian. (negative offsets are illegal before v4)}
 - Pops: *... stack*, uint64
 - Pushes: _None_
 - branch to TARGET if value X is zero
@@ -534,7 +544,7 @@ See `bnz` for details on how branches work. `bz` inverts the behavior of `bnz`.
 
 ## b target
 
-- Opcode: 0x42 {0..0x7fff forward branch offset, big endian}
+- Opcode: 0x42 {int16 branch offset, big endian. (negative offsets are illegal before v4)}
 - Pops: _None_
 - Pushes: _None_
 - branch unconditionally to TARGET
@@ -851,3 +861,23 @@ pushbytes args are not added to the bytecblock during assembly processes
 - LogicSigVersion >= 3
 
 pushint args are not added to the intcblock during assembly processes
+
+## callsub target
+
+- Opcode: 0x88
+- Pops: _None_
+- Pushes: _None_
+- branch unconditionally to TARGET, saving the next instruction on the call stack
+- LogicSigVersion >= 4
+
+The call stack is separate from the data stack. Only `callsub` and `retsub` manipulate it.`
+
+## retsub
+
+- Opcode: 0x89
+- Pops: _None_
+- Pushes: _None_
+- pop the top instruction from the call stack and branch to it
+- LogicSigVersion >= 4
+
+The call stack is separate from the data stack. Only `callsub` and `retsub` manipulate it.`