Inner clearstate (#3556)

* Test current state of inner clear state behavior

* First half of clear state fixes. Prevents inner calls in CSP

Should also implement the "CSP requires 700 budget and can't spend
more than 700 budget" rule, but tests still required.

* Match program version. Don't allow downgrade < 6.

* partition test

* typo

Co-authored-by: Michael Diamant <michaeldiamant@users.noreply.github.com>

* typo

Co-authored-by: Michael Diamant <michaeldiamant@users.noreply.github.com>

* Make the default clear_state program match versions to approval

* Correct some tests that now need programs present

* Fix test to actually test INNER clear state

* Add tests for opcode budget and CSPs

* Improve tracing for inner app calls

* Error now reports what the cost *was* before the attempted inst.

* Simplify type switch and maybe kick CI?

* Fewer copies during inner processing

Co-authored-by: Michael Diamant <michaeldiamant@users.noreply.github.com>

16 files changed, 1106 insertions, 88 deletions

diff --git a/config/consensus.go b/config/consensus.go
index de58af7cc..28af1f843 100644
--- a/config/consensus.go
+++ b/config/consensus.go
@@ -290,6 +290,9 @@ type ConsensusParams struct {
 	// should the number of inner transactions be pooled across group?
 	EnableInnerTransactionPooling bool
 
+	// provide greater isolation for clear state programs
+	IsolateClearState bool
+
 	// maximum number of applications a single account can create and store
 	// AppParams for at once
 	MaxAppsCreated int
@@ -1060,6 +1063,7 @@ func initConsensusProtocols() {
 	// Enable TEAL 6 / AVM 1.1
 	vFuture.LogicSigVersion = 6
 	vFuture.EnableInnerTransactionPooling = true
+	vFuture.IsolateClearState = true
 
 	vFuture.MaxProposedExpiredOnlineAccounts = 32
 
diff --git a/data/transactions/logic/eval.go b/data/transactions/logic/eval.go
index eb4d18f11..57eb25834 100644
--- a/data/transactions/logic/eval.go
+++ b/data/transactions/logic/eval.go
@@ -338,10 +338,8 @@ func NewEvalParams(txgroup []transactions.SignedTxnWithAD, proto *config.Consens
 }
 
 // NewInnerEvalParams creates an EvalParams to be used while evaluating an inner group txgroup
-func NewInnerEvalParams(txg []transactions.SignedTxn, caller *EvalContext) *EvalParams {
-	txgroup := transactions.WrapSignedTxnsWithAD(txg)
-
-	minTealVersion := ComputeMinTealVersion(txgroup, true)
+func NewInnerEvalParams(txg []transactions.SignedTxnWithAD, caller *EvalContext) *EvalParams {
+	minTealVersion := ComputeMinTealVersion(txg, true)
 	// Can't happen currently, since innerAppsEnabledVersion > than any minimum
 	// imposed otherwise.  But is correct to check, in case of future restriction.
 	if minTealVersion < *caller.MinTealVersion {
@@ -351,7 +349,7 @@ func NewInnerEvalParams(txg []transactions.SignedTxn, caller *EvalContext) *Eval
 	// Unlike NewEvalParams, do not add fee credit here. opTxSubmit has already done so.
 
 	if caller.Proto.EnableAppCostPooling {
-		for _, tx := range txgroup {
+		for _, tx := range txg {
 			if tx.Txn.Type == protocol.ApplicationCallTx {
 				*caller.PooledApplicationBudget += caller.Proto.MaxAppProgramCost
 			}
@@ -360,8 +358,9 @@ func NewInnerEvalParams(txg []transactions.SignedTxn, caller *EvalContext) *Eval
 
 	ep := &EvalParams{
 		Proto:                   caller.Proto,
-		TxnGroup:                copyWithClearAD(txgroup),
-		pastScratch:             make([]*scratchSpace, len(txgroup)),
+		Trace:                   caller.Trace,
+		TxnGroup:                txg,
+		pastScratch:             make([]*scratchSpace, len(txg)),
 		MinTealVersion:          &minTealVersion,
 		FeeCredit:               caller.FeeCredit,
 		Specials:                caller.Specials,
@@ -466,9 +465,9 @@ type EvalContext struct {
 	version uint64
 	scratch scratchSpace
 
-	subtxns []transactions.SignedTxn // place to build for itxn_submit
-	cost    int                      // cost incurred so far
-	logSize int                      // total log size so far
+	subtxns []transactions.SignedTxnWithAD // place to build for itxn_submit
+	cost    int                            // cost incurred so far
+	logSize int                            // total log size so far
 
 	// Set of PC values that branches we've seen so far might
 	// go. So, if checkStep() skips one, that branch is trying to
@@ -546,6 +545,19 @@ func (pe PanicError) Error() string {
 var errLogicSigNotSupported = errors.New("LogicSig not supported")
 var errTooManyArgs = errors.New("LogicSig has too many arguments")
 
+// ClearStateBudgetError allows evaluation to signal that the caller should
+// reject the transaction.  Normally, an error in evaluation would not cause a
+// ClearState txn to fail. However, callers fail a txn for ClearStateBudgetError
+// because the transaction has not provided enough budget to let ClearState do
+// its job.
+type ClearStateBudgetError struct {
+	offered int
+}
+
+func (e ClearStateBudgetError) Error() string {
+	return fmt.Sprintf("Attempted ClearState execution with low OpcodeBudget %d", e.offered)
+}
+
 // EvalContract executes stateful TEAL program as the gi'th transaction in params
 func EvalContract(program []byte, gi int, aid basics.AppIndex, params *EvalParams) (bool, *EvalContext, error) {
 	if params.Ledger == nil {
@@ -561,9 +573,26 @@ func EvalContract(program []byte, gi int, aid basics.AppIndex, params *EvalParam
 		Txn:          &params.TxnGroup[gi],
 		appID:        aid,
 	}
+
+	if cx.Proto.IsolateClearState && cx.Txn.Txn.OnCompletion == transactions.ClearStateOC {
+		if cx.PooledApplicationBudget != nil && *cx.PooledApplicationBudget < cx.Proto.MaxAppProgramCost {
+			return false, nil, ClearStateBudgetError{*cx.PooledApplicationBudget}
+		}
+	}
+
+	if cx.Trace != nil && cx.caller != nil {
+		fmt.Fprintf(cx.Trace, "--- enter %d %s %v\n", aid, cx.Txn.Txn.OnCompletion, cx.Txn.Txn.ApplicationArgs)
+	}
 	pass, err := eval(program, &cx)
+	if cx.Trace != nil && cx.caller != nil {
+		fmt.Fprintf(cx.Trace, "--- exit  %d accept=%t\n", aid, pass)
+	}
 
-	// update side effects
+	// update side effects. It is tempting, and maybe even a good idea, to store
+	// the pointer to cx.scratch instead.  Since we don't modify them again,
+	// it's probably safe. However it may have poor GC characteristics (because
+	// we'd be storing a pointer into a much larger structure, the cx), and
+	// copying seems nice and clean.
 	cx.pastScratch[cx.GroupIndex] = &scratchSpace{}
 	*cx.pastScratch[cx.GroupIndex] = cx.scratch
 
@@ -749,12 +778,9 @@ func check(program []byte, params *EvalParams, mode runMode) (err error) {
 }
 
 func versionCheck(program []byte, params *EvalParams) (uint64, int, error) {
-	if len(program) == 0 {
-		return 0, 0, errors.New("invalid program (empty)")
-	}
-	version, vlen := binary.Uvarint(program)
-	if vlen <= 0 {
-		return 0, 0, errors.New("invalid version")
+	version, vlen, err := transactions.ProgramVersion(program)
+	if err != nil {
+		return 0, 0, err
 	}
 	if version > EvalMaxVersion {
 		return 0, 0, fmt.Errorf("program version %d greater than max supported version %d", version, EvalMaxVersion)
@@ -801,6 +827,16 @@ func (cx *EvalContext) remainingBudget() int {
 	if cx.runModeFlags == runModeSignature {
 		return int(cx.Proto.LogicSigMaxCost) - cx.cost
 	}
+
+	// restrict clear state programs from using more than standard unpooled budget
+	// cx.Txn is not set during check()
+	if cx.Proto.IsolateClearState && cx.Txn != nil && cx.Txn.Txn.OnCompletion == transactions.ClearStateOC {
+		// Need not confirm that *cx.PooledApplicationBudget is also >0, as
+		// ClearState programs are only run if *cx.PooledApplicationBudget >
+		// MaxAppProgramCost at the start.
+		return cx.Proto.MaxAppProgramCost - cx.cost
+	}
+
 	if cx.PooledApplicationBudget != nil {
 		return *cx.PooledApplicationBudget
 	}
@@ -856,6 +892,13 @@ func (cx *EvalContext) step() {
 	}
 
 	if cx.remainingBudget() < 0 {
+		// We're not going to execute the instruction, so give the cost back.
+		// This only matters if this is an inner ClearState - the caller should
+		// not be over debited. (Normally, failure causes total txtree failure.)
+		cx.cost -= deets.Cost
+		if cx.PooledApplicationBudget != nil {
+			*cx.PooledApplicationBudget += deets.Cost
+		}
 		cx.err = fmt.Errorf("pc=%3d dynamic cost budget exceeded, executing %s: local program cost was %d",
 			cx.pc, spec.Name, cx.cost)
 		return
@@ -3984,7 +4027,7 @@ func addInnerTxn(cx *EvalContext) error {
 		return fmt.Errorf("too many inner transactions %d with %d left", len(cx.subtxns), cx.remainingInners())
 	}
 
-	stxn := transactions.SignedTxn{}
+	stxn := transactions.SignedTxnWithAD{}
 
 	groupFee := basics.MulSaturate(cx.Proto.MinTxnFee, uint64(len(cx.subtxns)+1))
 	groupPaid := uint64(0)
@@ -4019,6 +4062,10 @@ func opTxBegin(cx *EvalContext) {
 		cx.err = errors.New("itxn_begin without itxn_submit")
 		return
 	}
+	if cx.Proto.IsolateClearState && cx.Txn.Txn.OnCompletion == transactions.ClearStateOC {
+		cx.err = errors.New("clear state programs can not issue inner transactions")
+		return
+	}
 	cx.err = addInnerTxn(cx)
 }
 
@@ -4435,6 +4482,28 @@ func opTxSubmit(cx *EvalContext) {
 				cx.err = fmt.Errorf("appl depth (%d) exceeded", depth)
 				return
 			}
+
+			// Can't call version < innerAppsEnabledVersion, and apps with such
+			// versions will always match, so just check approval program
+			// version.
+			program := cx.subtxns[itx].Txn.ApprovalProgram
+			if cx.subtxns[itx].Txn.ApplicationID != 0 {
+				app, _, err := cx.Ledger.AppParams(cx.subtxns[itx].Txn.ApplicationID)
+				if err != nil {
+					cx.err = err
+					return
+				}
+				program = app.ApprovalProgram
+			}
+			v, _, err := transactions.ProgramVersion(program)
+			if err != nil {
+				cx.err = err
+				return
+			}
+			if v < innerAppsEnabledVersion {
+				cx.err = fmt.Errorf("inner app call with version %d < %d", v, innerAppsEnabledVersion)
+				return
+			}
 		}
 
 		if isGroup {
diff --git a/data/transactions/logic/evalAppTxn_test.go b/data/transactions/logic/evalAppTxn_test.go
index 5a239955a..9833c1c4a 100644
--- a/data/transactions/logic/evalAppTxn_test.go
+++ b/data/transactions/logic/evalAppTxn_test.go
@@ -72,8 +72,9 @@ func TestCurrentInnerTypes(t *testing.T) {
 	// allowed since v6
 	TestApp(t, "itxn_begin; byte \"keyreg\"; itxn_field Type; itxn_submit; int 1;", ep, "insufficient balance")
 	TestApp(t, "itxn_begin; int keyreg; itxn_field TypeEnum; itxn_submit; int 1;", ep, "insufficient balance")
-	TestApp(t, "itxn_begin; byte \"appl\"; itxn_field Type; itxn_submit; int 1;", ep, "insufficient balance")
-	TestApp(t, "itxn_begin; int appl; itxn_field TypeEnum; itxn_submit; int 1;", ep, "insufficient balance")
+	// caught before inner evaluation, because id=0 and bad program
+	TestApp(t, "itxn_begin; byte \"appl\"; itxn_field Type; itxn_submit; int 1;", ep, "invalid program (empty)")
+	TestApp(t, "itxn_begin; int appl; itxn_field TypeEnum; itxn_submit; int 1;", ep, "invalid program (empty)")
 
 	// Establish 888 as the app id, and fund it.
 	ledger.NewApp(tx.Receiver, 888, basics.AppParams{})
@@ -753,8 +754,8 @@ func TestApplCreation(t *testing.T) {
 
 // TestApplSubmission tests for checking of illegal appl transaction in form
 // only.  Things where interactions between two different fields causes the
-// error.  These are not exhaustive, but certainly demonstrate that WellFormed
-// is getting a crack at the txn.
+// error.  These are not exhaustive, but certainly demonstrate that
+// transactions.WellFormed is getting a crack at the txn.
 func TestApplSubmission(t *testing.T) {
 	ep, tx, ledger := MakeSampleEnv()
 	ledger.NewApp(tx.Receiver, 888, basics.AppParams{})
@@ -767,12 +768,14 @@ func TestApplSubmission(t *testing.T) {
 
 	p := "itxn_begin; int appl; itxn_field TypeEnum;"
 	s := ";itxn_submit; int 1"
-	TestApp(t, p+a+s, ep)
+	TestApp(t, p+a+s, ep, "ClearStateProgram: invalid program (empty)")
 
-	// All zeros is v0, so we get a complaint, but that means lengths were ok.
+	a += fmt.Sprintf("byte 0x%s; itxn_field ClearStateProgram;", approve)
+
+	// All zeros is v0, so we get a complaint, but that means lengths were ok when set.
 	TestApp(t, p+a+`int 600; bzero; itxn_field ApprovalProgram;
                   int 600; bzero; itxn_field ClearStateProgram;`+s, ep,
-		"program version must be")
+		"inner app call with version 0")
 
 	TestApp(t, p+`int 601; bzero; itxn_field ApprovalProgram;
                   int 600; bzero; itxn_field ClearStateProgram;`+s, ep, "too long")
@@ -781,7 +784,7 @@ func TestApplSubmission(t *testing.T) {
 	TestApp(t, p+a+`int 1; itxn_field ExtraProgramPages
                   int 1200; bzero; itxn_field ApprovalProgram;
                   int 1200; bzero; itxn_field ClearStateProgram;`+s, ep,
-		"program version must be")
+		"inner app call with version 0")
 	TestApp(t, p+`int 1; itxn_field ExtraProgramPages
                   int 1200; bzero; itxn_field ApprovalProgram;
                   int 1201; bzero; itxn_field ClearStateProgram;`+s, ep, "too long")
@@ -791,9 +794,9 @@ func TestApplSubmission(t *testing.T) {
 	TestApp(t, p+`int 1; itxn_field ExtraProgramPages;
                   int 7; itxn_field ApplicationID`+s, ep, "immutable")
 
-	TestApp(t, p+"int 20; itxn_field GlobalNumUint; int 11; itxn_field GlobalNumByteSlice"+s,
+	TestApp(t, p+a+"int 20; itxn_field GlobalNumUint; int 11; itxn_field GlobalNumByteSlice"+s,
 		ep, "too large")
-	TestApp(t, p+"int 7; itxn_field LocalNumUint; int 7; itxn_field LocalNumByteSlice"+s,
+	TestApp(t, p+a+"int 7; itxn_field LocalNumUint; int 7; itxn_field LocalNumByteSlice"+s,
 		ep, "too large")
 }
 
@@ -802,7 +805,7 @@ func TestInnerApplCreate(t *testing.T) {
 	ledger.NewApp(tx.Receiver, 888, basics.AppParams{})
 	ledger.NewAccount(appAddr(888), 50_000)
 
-	ops := TestProg(t, "int 1", AssemblerMaxVersion)
+	ops := TestProg(t, "int 50", AssemblerMaxVersion)
 	approve := "byte 0x" + hex.EncodeToString(ops.Program)
 
 	TestApp(t, `
@@ -823,8 +826,8 @@ int 5000; app_params_get AppGlobalNumByteSlice; assert; int 0; ==; assert
 
 	call := `
 itxn_begin
-int appl;              itxn_field TypeEnum
-int 5000;               itxn_field ApplicationID
+int appl;    itxn_field TypeEnum
+int 5000;    itxn_field ApplicationID
 itxn_submit
 int 1
 `
@@ -858,7 +861,7 @@ int 5000; app_params_get AppGlobalNumByteSlice; !; assert; !; assert; int 1
 `, ep)
 
 	// Can't call it either
-	TestApp(t, call, ep, "No application")
+	TestApp(t, call, ep, "no such app 5000")
 
 }
 
@@ -868,19 +871,59 @@ func TestCreateOldAppFails(t *testing.T) {
 	ledger.NewAccount(appAddr(888), 50_000)
 
 	ops := TestProg(t, "int 1", InnerAppsEnabledVersion-1)
-	approve := "byte 0x" + hex.EncodeToString(ops.Program)
+	old := "byte 0x" + hex.EncodeToString(ops.Program)
 
 	TestApp(t, `
 itxn_begin
 int appl;    itxn_field TypeEnum
-`+approve+`; itxn_field ApprovalProgram
-`+approve+`; itxn_field ClearStateProgram
+`+old+`; itxn_field ApprovalProgram
+`+old+`; itxn_field ClearStateProgram
 int 1;       itxn_field GlobalNumUint
 int 2;       itxn_field LocalNumByteSlice
 int 3;       itxn_field LocalNumUint
 itxn_submit
 int 1
-`, ep, "program version must be >=")
+`, ep, "inner app call with version 5")
+
+	ops = TestProg(t, "int 1", InnerAppsEnabledVersion)
+	recent := "byte 0x" + hex.EncodeToString(ops.Program)
+
+	TestApp(t, `
+itxn_begin
+int appl;    itxn_field TypeEnum
+`+recent+`; itxn_field ApprovalProgram
+`+recent+`; itxn_field ClearStateProgram
+int 1;       itxn_field GlobalNumUint
+int 2;       itxn_field LocalNumByteSlice
+int 3;       itxn_field LocalNumUint
+itxn_submit
+int 1
+`, ep)
+
+	TestApp(t, `
+itxn_begin
+int appl;    itxn_field TypeEnum
+`+old+`; itxn_field ApprovalProgram
+`+recent+`; itxn_field ClearStateProgram
+int 1;       itxn_field GlobalNumUint
+int 2;       itxn_field LocalNumByteSlice
+int 3;       itxn_field LocalNumUint
+itxn_submit
+int 1
+`, ep, "program version mismatch")
+
+	TestApp(t, `
+itxn_begin
+int appl;    itxn_field TypeEnum
+`+recent+`; itxn_field ApprovalProgram
+`+old+`; itxn_field ClearStateProgram
+int 1;       itxn_field GlobalNumUint
+int 2;       itxn_field LocalNumByteSlice
+int 3;       itxn_field LocalNumUint
+itxn_submit
+int 1
+`, ep, "program version mismatch")
+
 }
 
 func TestSelfReentrancy(t *testing.T) {
@@ -1225,10 +1268,16 @@ int 1
 	tx.ForeignApps = []basics.AppIndex{basics.AppIndex(222)}
 	TestApp(t, `itxn_begin
 int appl;    itxn_field TypeEnum
-	`+fmt.Sprintf("byte 0x%s; itxn_field ApprovalProgram;", hex.EncodeToString(ops.Program))+`
+	`+fmt.Sprintf("byte 0x%s", hex.EncodeToString(ops.Program))+`
+dup
+itxn_field ApprovalProgram;
+itxn_field ClearStateProgram;
 itxn_next
 int appl;    itxn_field TypeEnum
-	`+fmt.Sprintf("byte 0x%s; itxn_field ApprovalProgram;", hex.EncodeToString(ops.Program))+`
+	`+fmt.Sprintf("byte 0x%s;", hex.EncodeToString(ops.Program))+`
+dup
+itxn_field ApprovalProgram;
+itxn_field ClearStateProgram;
 itxn_next
 int appl;    itxn_field TypeEnum
 int 222;     itxn_field ApplicationID
@@ -1483,7 +1532,7 @@ int 1
 	createAndUse := `
   itxn_begin
    int appl;     itxn_field TypeEnum
-   byte	` + hexProgram(t, pay5back) + `; itxn_field ApprovalProgram;
+   byte	` + hexProgram(t, pay5back) + `; dup; itxn_field ApprovalProgram; itxn_field ClearStateProgram;
   itxn_submit
 
   itxn CreatedApplicationID; app_params_get AppAddress; assert
@@ -1515,7 +1564,10 @@ int 1
 	createAndPay := `
   itxn_begin
    int appl;    itxn_field TypeEnum
-	` + fmt.Sprintf("byte %s; itxn_field ApprovalProgram;", hexProgram(t, pay5back)) + `
+	` + fmt.Sprintf("byte %s", hexProgram(t, pay5back)) + `
+  dup
+  itxn_field ApprovalProgram;
+  itxn_field ClearStateProgram;
   itxn_submit
 
   itxn_begin
diff --git a/data/transactions/logic/evalStateful_test.go b/data/transactions/logic/evalStateful_test.go
index 804e2ec77..6d5af8de6 100644
--- a/data/transactions/logic/evalStateful_test.go
+++ b/data/transactions/logic/evalStateful_test.go
@@ -400,6 +400,7 @@ func testAppFull(t *testing.T, program []byte, gi int, aid basics.AppIndex, ep *
 	case 1:
 		evalProblem = problems[0]
 	case 0:
+		// no problems == expect success
 	default:
 		require.Fail(t, "Misused testApp: %d problems", len(problems))
 	}
@@ -2010,8 +2011,7 @@ int 1
 	ledger.NewAccount(txn.Txn.Receiver, 1)
 	ledger.NewLocals(txn.Txn.Receiver, 100)
 
-	sb := strings.Builder{}
-	ep.Trace = &sb
+	ep.Trace = &strings.Builder{}
 
 	delta := testApp(t, source, ep)
 	require.Equal(t, 0, len(delta.GlobalDelta))
@@ -2491,7 +2491,7 @@ func TestPooledAppCallsVerifyOp(t *testing.T) {
 	call := transactions.SignedTxn{Txn: transactions.Transaction{Type: protocol.ApplicationCallTx}}
 	// Simulate test with 2 grouped txn
 	testApps(t, []string{source, ""}, []transactions.SignedTxn{call, call}, LogicVersion, ledger,
-		Expect{0, "pc=107 dynamic cost budget exceeded, executing ed25519verify: local program cost was 1905"})
+		Expect{0, "pc=107 dynamic cost budget exceeded, executing ed25519verify: local program cost was 5"})
 
 	// Simulate test with 3 grouped txn
 	testApps(t, []string{source, "", ""}, []transactions.SignedTxn{call, call, call}, LogicVersion, ledger)
diff --git a/data/transactions/logic/ledger_test.go b/data/transactions/logic/ledger_test.go
index 7efdeebbd..fe771ab15 100644
--- a/data/transactions/logic/ledger_test.go
+++ b/data/transactions/logic/ledger_test.go
@@ -652,6 +652,10 @@ func (l *Ledger) appl(from basics.Address, appl transactions.ApplicationCallTxnF
 		ad.ApplicationID = aid
 	}
 
+	if appl.OnCompletion == transactions.ClearStateOC {
+		return errors.New("not implemented in test ledger")
+	}
+
 	if appl.OnCompletion == transactions.OptInOC {
 		br, ok := l.balances[from]
 		if !ok {
diff --git a/data/transactions/logic/opcodes.go b/data/transactions/logic/opcodes.go
index 59ccf9b3f..75aa9826e 100644
--- a/data/transactions/logic/opcodes.go
+++ b/data/transactions/logic/opcodes.go
@@ -18,6 +18,8 @@ package logic
 
 import (
 	"sort"
+
+	"github.com/algorand/go-algorand/data/transactions"
 )
 
 // LogicVersion defines default assembler and max eval versions
@@ -42,9 +44,10 @@ const backBranchEnabledVersion = 4
 // using an index into arrays.
 const directRefEnabledVersion = 4
 
-// innerAppsEnabledVersion is first version that allowed inner app calls. No old
-// apps should be called as inner apps.
-const innerAppsEnabledVersion = 6
+// innerAppsEnabledVersion is the version that allowed inner app calls. No old
+// apps should be called as inner apps. Set to ExtraProgramChecks version
+// because those checks protect from tricky ClearState Programs.
+const innerAppsEnabledVersion = transactions.ExtraProgramChecksVersion
 
 // txnEffectsVersion is first version that allowed txn opcode to access
 // "effects" (ApplyData info)
diff --git a/data/transactions/teal_test.go b/data/transactions/teal_test.go
index 0d6561b3e..990036895 100644
--- a/data/transactions/teal_test.go
+++ b/data/transactions/teal_test.go
@@ -17,6 +17,7 @@
 package transactions
 
 import (
+	"fmt"
 	"testing"
 
 	"github.com/algorand/go-algorand/data/basics"
@@ -187,3 +188,88 @@ func TestEvalDeltaEqual(t *testing.T) {
 	a.False(d1.Equal(d2))
 
 }
+
+// TestUnchangedAllocBounds ensure that the allocbounds on EvalDelta have not
+// changed.  If they change, EvalDelta.checkAllocBounds must be changed, or at
+// least reconsidered, as well. We must give plenty of thought to whether a new
+// allocound, used by new versions, is compatible with old code. If the change
+// can only show up in new protocol versions, it should be ok. But if we change
+// a bound, it will go into effect immediately, not with Protocol upgrade. So we
+// must be extremely careful that old protocol versions can not emit messages
+// that take advnatage of a new, bigger bound. (Or, if the bound is *lowered* it
+// had better be the case that such messages cannot be emitted in old code.)
+func TestUnchangedAllocBounds(t *testing.T) {
+	partitiontest.PartitionTest(t)
+
+	delta := &EvalDelta{}
+	max := 256 // Hardcodes config.MaxEvalDeltaAccounts
+	for i := 0; i < max; i++ {
+		delta.InnerTxns = append(delta.InnerTxns, SignedTxnWithAD{})
+		msg := delta.MarshalMsg(nil)
+		_, err := delta.UnmarshalMsg(msg)
+		require.NoError(t, err)
+	}
+	delta.InnerTxns = append(delta.InnerTxns, SignedTxnWithAD{})
+	msg := delta.MarshalMsg(nil)
+	_, err := delta.UnmarshalMsg(msg)
+	require.Error(t, err)
+
+	delta = &EvalDelta{}
+	max = 2048 // Hardcodes config.MaxLogCalls, currently MaxAppProgramLen
+	for i := 0; i < max; i++ {
+		delta.Logs = append(delta.Logs, "junk")
+		msg := delta.MarshalMsg(nil)
+		_, err := delta.UnmarshalMsg(msg)
+		require.NoError(t, err)
+	}
+	delta.Logs = append(delta.Logs, "junk")
+	msg = delta.MarshalMsg(nil)
+	_, err = delta.UnmarshalMsg(msg)
+	require.Error(t, err)
+
+	delta = &EvalDelta{}
+	max = 256 // Hardcodes config.MaxInnerTransactionsPerDelta
+	for i := 0; i < max; i++ {
+		delta.InnerTxns = append(delta.InnerTxns, SignedTxnWithAD{})
+		msg := delta.MarshalMsg(nil)
+		_, err := delta.UnmarshalMsg(msg)
+		require.NoError(t, err)
+	}
+	delta.InnerTxns = append(delta.InnerTxns, SignedTxnWithAD{})
+	msg = delta.MarshalMsg(nil)
+	_, err = delta.UnmarshalMsg(msg)
+	require.Error(t, err)
+
+	// This one appears wildly conservative. The real max is something like
+	// MaxAppTxnAccounts (4) + 1, since the key must be an index in the static
+	// array of touchable accounts.
+	delta = &EvalDelta{LocalDeltas: make(map[uint64]basics.StateDelta)}
+	max = 2048 // Hardcodes config.MaxEvalDeltaAccounts
+	for i := 0; i < max; i++ {
+		delta.LocalDeltas[uint64(i)] = basics.StateDelta{}
+		msg := delta.MarshalMsg(nil)
+		_, err := delta.UnmarshalMsg(msg)
+		require.NoError(t, err)
+	}
+	delta.LocalDeltas[uint64(max)] = basics.StateDelta{}
+	msg = delta.MarshalMsg(nil)
+	_, err = delta.UnmarshalMsg(msg)
+	require.Error(t, err)
+
+	// This one *might* be wildly conservative. Only 64 keys can be set in
+	// globals, but I don't know what happens if you set and delete 65 (or way
+	// more) keys in a single transaction.
+	delta = &EvalDelta{GlobalDelta: make(basics.StateDelta)}
+	max = 2048 // Hardcodes config.MaxStateDeltaKeys
+	for i := 0; i < max; i++ {
+		delta.GlobalDelta[fmt.Sprintf("%d", i)] = basics.ValueDelta{}
+		msg := delta.MarshalMsg(nil)
+		_, err := delta.UnmarshalMsg(msg)
+		require.NoError(t, err)
+	}
+	delta.GlobalDelta[fmt.Sprintf("%d", max)] = basics.ValueDelta{}
+	msg = delta.MarshalMsg(nil)
+	_, err = delta.UnmarshalMsg(msg)
+	require.Error(t, err)
+
+}
diff --git a/data/transactions/transaction.go b/data/transactions/transaction.go
index d617160e8..7ab5eb3fb 100644
--- a/data/transactions/transaction.go
+++ b/data/transactions/transaction.go
@@ -368,6 +368,13 @@ func (tx Transaction) WellFormed(spec SpecialAddresses, proto config.ConsensusPa
 			if len(tx.ApprovalProgram) != 0 || len(tx.ClearStateProgram) != 0 {
 				return fmt.Errorf("programs may only be specified during application creation or update")
 			}
+		} else {
+			// This will check version matching, but not downgrading. That
+			// depends on chain state (so we pass an empty AppParams)
+			err := CheckContractVersions(tx.ApprovalProgram, tx.ClearStateProgram, basics.AppParams{})
+			if err != nil {
+				return err
+			}
 		}
 
 		effectiveEPP := tx.ExtraProgramPages
@@ -647,6 +654,51 @@ type TxnContext interface {
 	GenesisHash() crypto.Digest
 }
 
+// ProgramVersion extracts the version of an AVM program from its bytecode
+func ProgramVersion(bytecode []byte) (version uint64, length int, err error) {
+	if len(bytecode) == 0 {
+		return 0, 0, errors.New("invalid program (empty)")
+	}
+	version, vlen := binary.Uvarint(bytecode)
+	if vlen <= 0 {
+		return 0, 0, errors.New("invalid version")
+	}
+	return version, vlen, nil
+}
+
+// ExtraProgramChecksVersion is version of AVM programs that are subject to
+// extra test - approval and clear must match versions, and they may not be
+// downgraded
+const ExtraProgramChecksVersion = 6
+
+// CheckContractVersions ensures that for v6 and higher two programs are version
+// matched, and that they are not a downgrade.
+func CheckContractVersions(approval []byte, clear []byte, previous basics.AppParams) error {
+	av, _, err := ProgramVersion(approval)
+	if err != nil {
+		return fmt.Errorf("bad ApprovalProgram: %v", err)
+	}
+	cv, _, err := ProgramVersion(clear)
+	if err != nil {
+		return fmt.Errorf("bad ClearStateProgram: %v", err)
+	}
+	if av >= ExtraProgramChecksVersion || cv >= ExtraProgramChecksVersion {
+		if av != cv {
+			return fmt.Errorf("program version mismatch: %d != %d", av, cv)
+		}
+	}
+	if len(previous.ApprovalProgram) != 0 { // if creation or in call from WellFormed() previous is empty
+		pv, _, err := ProgramVersion(previous.ApprovalProgram)
+		if err != nil {
+			return err
+		}
+		if pv >= ExtraProgramChecksVersion && av < pv {
+			return fmt.Errorf("program version downgrade: %d < %d", av, pv)
+		}
+	}
+	return nil
+}
+
 // ExplicitTxnContext is a struct that implements TxnContext with
 // explicit fields for everything.
 type ExplicitTxnContext struct {
diff --git a/data/transactions/transaction_test.go b/data/transactions/transaction_test.go
index 037087ee9..fc7d3b516 100644
--- a/data/transactions/transaction_test.go
+++ b/data/transactions/transaction_test.go
@@ -134,16 +134,17 @@ func TestAppCallCreateWellFormed(t *testing.T) {
 	partitiontest.PartitionTest(t)
 
 	feeSink := basics.Address{0x7, 0xda, 0xcb, 0x4b, 0x6d, 0x9e, 0xd1, 0x41, 0xb1, 0x75, 0x76, 0xbd, 0x45, 0x9a, 0xe6, 0x42, 0x1d, 0x48, 0x6d, 0xa3, 0xd4, 0xef, 0x22, 0x47, 0xc4, 0x9, 0xa3, 0x96, 0xb8, 0x2e, 0xa2, 0x21}
-	specialAddr := SpecialAddresses{FeeSink: feeSink}
 	curProto := config.Consensus[protocol.ConsensusCurrentVersion]
 	futureProto := config.Consensus[protocol.ConsensusFuture]
 	addr1, err := basics.UnmarshalChecksumAddress("NDQCJNNY5WWWFLP4GFZ7MEF2QJSMZYK6OWIV2AQ7OMAVLEFCGGRHFPKJJA")
 	require.NoError(t, err)
+	v5 := []byte{0x05}
+	v6 := []byte{0x06}
+
 	usecases := []struct {
 		tx            Transaction
-		spec          SpecialAddresses
 		proto         config.ConsensusParams
-		expectedError error
+		expectedError string
 	}{
 		{
 			tx: Transaction{
@@ -155,13 +156,14 @@ func TestAppCallCreateWellFormed(t *testing.T) {
 					FirstValid: 100,
 				},
 				ApplicationCallTxnFields: ApplicationCallTxnFields{
-					ApplicationID: 0,
+					ApplicationID:     0,
+					ApprovalProgram:   v5,
+					ClearStateProgram: v5,
 					ApplicationArgs: [][]byte{
 						[]byte("write"),
 					},
 				},
 			},
-			spec:  specialAddr,
 			proto: curProto,
 		},
 		{
@@ -174,14 +176,15 @@ func TestAppCallCreateWellFormed(t *testing.T) {
 					FirstValid: 100,
 				},
 				ApplicationCallTxnFields: ApplicationCallTxnFields{
-					ApplicationID: 0,
+					ApplicationID:     0,
+					ApprovalProgram:   v5,
+					ClearStateProgram: v5,
 					ApplicationArgs: [][]byte{
 						[]byte("write"),
 					},
 					ExtraProgramPages: 0,
 				},
 			},
-			spec:  specialAddr,
 			proto: curProto,
 		},
 		{
@@ -194,14 +197,15 @@ func TestAppCallCreateWellFormed(t *testing.T) {
 					FirstValid: 100,
 				},
 				ApplicationCallTxnFields: ApplicationCallTxnFields{
-					ApplicationID: 0,
+					ApplicationID:     0,
+					ApprovalProgram:   v5,
+					ClearStateProgram: v5,
 					ApplicationArgs: [][]byte{
 						[]byte("write"),
 					},
 					ExtraProgramPages: 3,
 				},
 			},
-			spec:  specialAddr,
 			proto: futureProto,
 		},
 		{
@@ -214,20 +218,45 @@ func TestAppCallCreateWellFormed(t *testing.T) {
 					FirstValid: 100,
 				},
 				ApplicationCallTxnFields: ApplicationCallTxnFields{
-					ApplicationID: 0,
+					ApplicationID:     0,
+					ApprovalProgram:   v5,
+					ClearStateProgram: v5,
 					ApplicationArgs: [][]byte{
 						[]byte("write"),
 					},
 					ExtraProgramPages: 0,
 				},
 			},
-			spec:  specialAddr,
 			proto: futureProto,
 		},
+		{
+			tx: Transaction{
+				Type: protocol.ApplicationCallTx,
+				Header: Header{
+					Sender:     addr1,
+					Fee:        basics.MicroAlgos{Raw: 1000},
+					LastValid:  105,
+					FirstValid: 100,
+				},
+				ApplicationCallTxnFields: ApplicationCallTxnFields{
+					ApprovalProgram:   v5,
+					ClearStateProgram: v6,
+				},
+			},
+			proto:         futureProto,
+			expectedError: "mismatch",
+		},
 	}
-	for _, usecase := range usecases {
-		err := usecase.tx.WellFormed(usecase.spec, usecase.proto)
-		require.NoError(t, err)
+	for i, usecase := range usecases {
+		t.Run(fmt.Sprintf("i=%d", i), func(t *testing.T) {
+			err := usecase.tx.WellFormed(SpecialAddresses{FeeSink: feeSink}, usecase.proto)
+			if usecase.expectedError != "" {
+				require.Error(t, err)
+				require.Contains(t, err.Error(), usecase.expectedError)
+			} else {
+				require.NoError(t, err)
+			}
+		})
 	}
 }
 
@@ -242,6 +271,7 @@ func TestWellFormedErrors(t *testing.T) {
 	protoV28 := config.Consensus[protocol.ConsensusV28]
 	addr1, err := basics.UnmarshalChecksumAddress("NDQCJNNY5WWWFLP4GFZ7MEF2QJSMZYK6OWIV2AQ7OMAVLEFCGGRHFPKJJA")
 	require.NoError(t, err)
+	v5 := []byte{0x05}
 	okHeader := Header{
 		Sender:     addr1,
 		Fee:        basics.MicroAlgos{Raw: 1000},
@@ -296,7 +326,9 @@ func TestWellFormedErrors(t *testing.T) {
 				Type:   protocol.ApplicationCallTx,
 				Header: okHeader,
 				ApplicationCallTxnFields: ApplicationCallTxnFields{
-					ApplicationID: 0, // creation
+					ApplicationID:     0, // creation
+					ApprovalProgram:   v5,
+					ClearStateProgram: v5,
 					ApplicationArgs: [][]byte{
 						[]byte("write"),
 					},
@@ -314,7 +346,7 @@ func TestWellFormedErrors(t *testing.T) {
 				ApplicationCallTxnFields: ApplicationCallTxnFields{
 					ApplicationID:     0, // creation
 					ApprovalProgram:   []byte(strings.Repeat("X", 1025)),
-					ClearStateProgram: []byte("junk"),
+					ClearStateProgram: []byte("Xjunk"),
 				},
 			},
 			spec:          specialAddr,
@@ -328,7 +360,7 @@ func TestWellFormedErrors(t *testing.T) {
 				ApplicationCallTxnFields: ApplicationCallTxnFields{
 					ApplicationID:     0, // creation
 					ApprovalProgram:   []byte(strings.Repeat("X", 1025)),
-					ClearStateProgram: []byte("junk"),
+					ClearStateProgram: []byte("Xjunk"),
 				},
 			},
 			spec:  specialAddr,
@@ -383,7 +415,9 @@ func TestWellFormedErrors(t *testing.T) {
 				Type:   protocol.ApplicationCallTx,
 				Header: okHeader,
 				ApplicationCallTxnFields: ApplicationCallTxnFields{
-					ApplicationID: 0,
+					ApplicationID:     0,
+					ApprovalProgram:   v5,
+					ClearStateProgram: v5,
 					ApplicationArgs: [][]byte{
 						[]byte("write"),
 					},
@@ -495,7 +529,9 @@ func TestWellFormedErrors(t *testing.T) {
 				Type:   protocol.ApplicationCallTx,
 				Header: okHeader,
 				ApplicationCallTxnFields: ApplicationCallTxnFields{
-					ApplicationID: 1,
+					ApplicationID:     1,
+					ApprovalProgram:   v5,
+					ClearStateProgram: v5,
 					ApplicationArgs: [][]byte{
 						[]byte("write"),
 					},
diff --git a/data/txntest/txn.go b/data/txntest/txn.go
index 49cb1be96..6119d61a3 100644
--- a/data/txntest/txn.go
+++ b/data/txntest/txn.go
@@ -34,6 +34,7 @@ package txntest
 
 import (
 	"fmt"
+	"reflect"
 	"strings"
 
 	"github.com/algorand/go-algorand/config"
@@ -93,8 +94,8 @@ type Txn struct {
 	ForeignAssets     []basics.AssetIndex
 	LocalStateSchema  basics.StateSchema
 	GlobalStateSchema basics.StateSchema
-	ApprovalProgram   string
-	ClearStateProgram string
+	ApprovalProgram   interface{} // string, nil, or []bytes if already compiled
+	ClearStateProgram interface{} // string, nil or []bytes if already compiled
 	ExtraProgramPages uint32
 
 	CertRound basics.Round
@@ -119,29 +120,52 @@ func (tx *Txn) FillDefaults(params config.ConsensusParams) {
 	if tx.LastValid == 0 {
 		tx.LastValid = tx.FirstValid + basics.Round(params.MaxTxnLife)
 	}
-	if tx.ApprovalProgram != "" && !strings.Contains(tx.ApprovalProgram, "#pragma version") {
-		pragma := fmt.Sprintf("#pragma version %d\n", params.LogicSigVersion)
-		tx.ApprovalProgram = pragma + tx.ApprovalProgram
-	}
-	if tx.ApprovalProgram != "" && tx.ClearStateProgram == "" {
-		tx.ClearStateProgram = "int 0"
-	}
-	if tx.ClearStateProgram != "" && !strings.Contains(tx.ClearStateProgram, "#pragma version") {
-		pragma := fmt.Sprintf("#pragma version %d\n", params.LogicSigVersion)
-		tx.ClearStateProgram = pragma + tx.ClearStateProgram
+
+	if tx.Type == protocol.ApplicationCallTx &&
+		(tx.ApplicationID == 0 || tx.OnCompletion == transactions.UpdateApplicationOC) {
+
+		switch program := tx.ApprovalProgram.(type) {
+		case nil:
+			tx.ApprovalProgram = fmt.Sprintf("#pragma version %d\nint 1", params.LogicSigVersion)
+		case string:
+			if program != "" && !strings.Contains(program, "#pragma version") {
+				pragma := fmt.Sprintf("#pragma version %d\n", params.LogicSigVersion)
+				tx.ApprovalProgram = pragma + program
+			}
+		case []byte:
+		}
+
+		switch program := tx.ClearStateProgram.(type) {
+		case nil:
+			tx.ClearStateProgram = tx.ApprovalProgram
+		case string:
+			if program != "" && !strings.Contains(program, "#pragma version") {
+				pragma := fmt.Sprintf("#pragma version %d\n", params.LogicSigVersion)
+				tx.ClearStateProgram = pragma + program
+			}
+		case []byte:
+		}
 	}
 }
 
-func assemble(source string) []byte {
-	if source == "" {
+func assemble(source interface{}) []byte {
+	switch program := source.(type) {
+	case string:
+		if program == "" {
+			return nil
+		}
+		ops, err := logic.AssembleString(program)
+		if err != nil {
+			fmt.Printf("Bad program %v", ops.Errors)
+			panic(ops.Errors)
+		}
+		return ops.Program
+	case []byte:
+		return program
+	case nil:
 		return nil
 	}
-	ops, err := logic.AssembleString(source)
-	if err != nil {
-		fmt.Printf("Bad program %v", ops.Errors)
-		panic(ops.Errors)
-	}
-	return ops.Program
+	panic(reflect.TypeOf(source))
 }
 
 // Txn produces a transactions.Transaction from the fields in this Txn
diff --git a/ledger/apply/application.go b/ledger/apply/application.go
index bd133fbd5..8b805c2d6 100644
--- a/ledger/apply/application.go
+++ b/ledger/apply/application.go
@@ -360,6 +360,11 @@ func ApplicationCall(ac transactions.ApplicationCallTxnFields, header transactio
 	// If this txn is going to set new programs (either for creation or
 	// update), check that the programs are valid and not too expensive
 	if ac.ApplicationID == 0 || ac.OnCompletion == transactions.UpdateApplicationOC {
+		err := transactions.CheckContractVersions(ac.ApprovalProgram, ac.ClearStateProgram, params)
+		if err != nil {
+			return err
+		}
+
 		err = checkPrograms(&ac, evalParams)
 		if err != nil {
 			return err
diff --git a/ledger/internal/appcow.go b/ledger/internal/appcow.go
index 85511a713..ec1da1ff8 100644
--- a/ledger/internal/appcow.go
+++ b/ledger/internal/appcow.go
@@ -485,6 +485,10 @@ func (cb *roundCowState) StatefulEval(gi int, params *logic.EvalParams, aidx bas
 			pc, det := cx.PcDetails()
 			details = fmt.Sprintf("pc=%d, opcodes=%s", pc, det)
 		}
+		// Don't wrap ClearStateBudgetError, so it will be taken seriously
+		if _, ok := err.(logic.ClearStateBudgetError); ok {
+			return false, transactions.EvalDelta{}, err
+		}
 		return false, transactions.EvalDelta{}, ledgercore.LogicEvalError{Err: err, Details: details}
 	}
 
diff --git a/ledger/internal/apptxn_test.go b/ledger/internal/apptxn_test.go
index fed5a4f06..94c4c4c9b 100644
--- a/ledger/internal/apptxn_test.go
+++ b/ledger/internal/apptxn_test.go
@@ -28,6 +28,7 @@ import (
 	"github.com/algorand/go-algorand/crypto"
 	"github.com/algorand/go-algorand/data/basics"
 	"github.com/algorand/go-algorand/data/bookkeeping"
+	"github.com/algorand/go-algorand/data/transactions"
 	"github.com/algorand/go-algorand/data/transactions/logic"
 	"github.com/algorand/go-algorand/data/txntest"
 	"github.com/algorand/go-algorand/ledger"
@@ -2161,7 +2162,178 @@ assert
 	endBlock(t, l, eval)
 }
 
-func TestCreatedAppsAreAccessible(t *testing.T) {
+// TestInnerAppVersionCalling ensure that inner app calls must be the >=v6 apps
+func TestInnerAppVersionCalling(t *testing.T) {
+	partitiontest.PartitionTest(t)
+
+	genBalances, addrs, _ := ledgertesting.NewTestGenesis()
+	l := newTestLedger(t, genBalances)
+	defer l.Close()
+
+	five, err := logic.AssembleStringWithVersion("int 1", 5)
+	require.NoError(t, err)
+	six, err := logic.AssembleStringWithVersion("int 1", 6)
+	require.NoError(t, err)
+
+	create5 := txntest.Txn{
+		Type:              "appl",
+		Sender:            addrs[0],
+		ApprovalProgram:   five.Program,
+		ClearStateProgram: five.Program,
+	}
+
+	create6 := txntest.Txn{
+		Type:              "appl",
+		Sender:            addrs[0],
+		ApprovalProgram:   six.Program,
+		ClearStateProgram: six.Program,
+	}
+
+	eval := nextBlock(t, l, true, nil)
+	txns(t, l, eval, &create5, &create6)
+	vb := endBlock(t, l, eval)
+	v5id := vb.Block().Payset[0].ApplicationID
+	v6id := vb.Block().Payset[1].ApplicationID
+
+	call := txntest.Txn{
+		Type:   "appl",
+		Sender: addrs[0],
+		// don't use main. do the test at creation time
+		ApprovalProgram: `
+itxn_begin
+	int appl
+	itxn_field TypeEnum
+	txn Applications 1
+	itxn_field ApplicationID
+itxn_submit`,
+		ForeignApps: []basics.AppIndex{v5id},
+	}
+
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &call, "inner app call with version 5")
+	call.ForeignApps[0] = v6id
+	txn(t, l, eval, &call, "overspend") // it tried to execute, but test doesn't bother funding
+	endBlock(t, l, eval)
+
+}
+
+func TestAppVersionMatching(t *testing.T) {
+	partitiontest.PartitionTest(t)
+
+	genBalances, addrs, _ := ledgertesting.NewTestGenesis()
+	l := newTestLedger(t, genBalances)
+	defer l.Close()
+
+	four, err := logic.AssembleStringWithVersion("int 1", 4)
+	require.NoError(t, err)
+	five, err := logic.AssembleStringWithVersion("int 1", 5)
+	require.NoError(t, err)
+	six, err := logic.AssembleStringWithVersion("int 1", 6)
+	require.NoError(t, err)
+
+	create := txntest.Txn{
+		Type:              "appl",
+		Sender:            addrs[0],
+		ApprovalProgram:   five.Program,
+		ClearStateProgram: five.Program,
+	}
+
+	eval := nextBlock(t, l, true, nil)
+	txn(t, l, eval, &create)
+	endBlock(t, l, eval)
+
+	create.ClearStateProgram = six.Program
+
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &create, "version mismatch")
+	endBlock(t, l, eval)
+
+	create.ApprovalProgram = six.Program
+
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &create)
+	endBlock(t, l, eval)
+
+	create.ClearStateProgram = four.Program
+
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &create, "version mismatch")
+	endBlock(t, l, eval)
+
+	// four doesn't match five, but it doesn't have to
+	create.ApprovalProgram = five.Program
+
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &create)
+	endBlock(t, l, eval)
+}
+
+func TestAppDowngrade(t *testing.T) {
+	partitiontest.PartitionTest(t)
+
+	genBalances, addrs, _ := ledgertesting.NewTestGenesis()
+	l := newTestLedger(t, genBalances)
+	defer l.Close()
+
+	four, err := logic.AssembleStringWithVersion("int 1", 4)
+	require.NoError(t, err)
+	five, err := logic.AssembleStringWithVersion("int 1", 5)
+	require.NoError(t, err)
+	six, err := logic.AssembleStringWithVersion("int 1", 6)
+	require.NoError(t, err)
+
+	create := txntest.Txn{
+		Type:              "appl",
+		Sender:            addrs[0],
+		ApprovalProgram:   four.Program,
+		ClearStateProgram: four.Program,
+	}
+
+	eval := nextBlock(t, l, true, nil)
+	txn(t, l, eval, &create)
+	vb := endBlock(t, l, eval)
+	app := vb.Block().Payset[0].ApplicationID
+
+	update := txntest.Txn{
+		Type:              "appl",
+		ApplicationID:     app,
+		OnCompletion:      transactions.UpdateApplicationOC,
+		Sender:            addrs[0],
+		ApprovalProgram:   four.Program,
+		ClearStateProgram: four.Program,
+	}
+
+	// No change - legal
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &update)
+
+	// Upgrade just the approval. Sure (because under 6, no need to match)
+	update.ApprovalProgram = five.Program
+	txn(t, l, eval, &update)
+
+	// Upgrade just the clear state. Now they match
+	update.ClearStateProgram = five.Program
+	txn(t, l, eval, &update)
+
+	// Downgrade (allowed pre 6)
+	update.ClearStateProgram = four.Program
+	txn(t, l, eval, update.Noted("actually a repeat of first upgrade"))
+
+	// Try to upgrade (at 6, must match)
+	update.ApprovalProgram = six.Program
+	txn(t, l, eval, &update, "version mismatch")
+
+	// Do both
+	update.ClearStateProgram = six.Program
+	txn(t, l, eval, &update)
+
+	// Try to downgrade. Fails because it was 6.
+	update.ApprovalProgram = five.Program
+	update.ClearStateProgram = five.Program
+	txn(t, l, eval, update.Noted("repeat of 3rd update"), "downgrade")
+}
+
+func TestCreatedAppsAreAvailable(t *testing.T) {
 	partitiontest.PartitionTest(t)
 
 	genBalances, addrs, _ := ledgertesting.NewTestGenesis()
@@ -2439,3 +2611,424 @@ func BenchmarkMaximumCallStackDepth(b *testing.B) {
 		executeMegaContract(b)
 	}
 }
+
+// TestInnerClearState ensures inner ClearState performs close out properly, even if rejects.
+func TestInnerClearState(t *testing.T) {
+	partitiontest.PartitionTest(t)
+
+	genBalances, addrs, _ := ledgertesting.NewTestGenesis()
+	l := newTestLedger(t, genBalances)
+	defer l.Close()
+
+	// inner will be an app that we opt into, then clearstate
+	// note that clearstate rejects
+	inner := txntest.Txn{
+		Type:              "appl",
+		Sender:            addrs[0],
+		ApprovalProgram:   "int 1",
+		ClearStateProgram: "int 0",
+		LocalStateSchema: basics.StateSchema{
+			NumUint:      2,
+			NumByteSlice: 2,
+		},
+	}
+
+	eval := nextBlock(t, l, true, nil)
+	txn(t, l, eval, &inner)
+	vb := endBlock(t, l, eval)
+	innerId := vb.Block().Payset[0].ApplicationID
+
+	// Outer is a simple app that will invoke the given app (in ForeignApps[0])
+	// with the given OnCompletion (in ApplicationArgs[0]).  Goal is to use it
+	// to opt into, and the clear state, on the inner app.
+	outer := txntest.Txn{
+		Type:   "appl",
+		Sender: addrs[0],
+		ApprovalProgram: main(`
+itxn_begin
+ int appl
+ itxn_field TypeEnum
+ txn Applications 1
+ itxn_field ApplicationID
+ txn ApplicationArgs 0
+ btoi
+ itxn_field OnCompletion
+itxn_submit
+`),
+		ForeignApps: []basics.AppIndex{innerId},
+	}
+
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &outer)
+	vb = endBlock(t, l, eval)
+	outerId := vb.Block().Payset[0].ApplicationID
+
+	fund := txntest.Txn{
+		Type:     "pay",
+		Sender:   addrs[0],
+		Receiver: outerId.Address(),
+		Amount:   1_000_000,
+	}
+
+	call := txntest.Txn{
+		Type:            "appl",
+		Sender:          addrs[0],
+		ApplicationID:   outerId,
+		ApplicationArgs: [][]byte{{byte(transactions.OptInOC)}},
+		ForeignApps:     []basics.AppIndex{innerId},
+	}
+	eval = nextBlock(t, l, true, nil)
+	txns(t, l, eval, &fund, &call)
+	endBlock(t, l, eval)
+
+	outerAcct := lookup(t, l, outerId.Address())
+	require.Len(t, outerAcct.AppLocalStates, 1)
+	require.Equal(t, outerAcct.TotalAppSchema, basics.StateSchema{
+		NumUint:      2,
+		NumByteSlice: 2,
+	})
+
+	call.ApplicationArgs = [][]byte{{byte(transactions.ClearStateOC)}}
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &call)
+	endBlock(t, l, eval)
+
+	outerAcct = lookup(t, l, outerId.Address())
+	require.Empty(t, outerAcct.AppLocalStates)
+	require.Empty(t, outerAcct.TotalAppSchema)
+
+}
+
+// TestInnerClearStateBadCallee ensures that inner clear state programs are not
+// allowed to use more than 700 (MaxAppProgramCost)
+func TestInnerClearStateBadCallee(t *testing.T) {
+	partitiontest.PartitionTest(t)
+
+	genBalances, addrs, _ := ledgertesting.NewTestGenesis()
+	l := newTestLedger(t, genBalances)
+	defer l.Close()
+
+	// badCallee tries to run down your budget, so an inner clear must be
+	// protected from exhaustion
+	badCallee := txntest.Txn{
+		Type:            "appl",
+		Sender:          addrs[0],
+		ApprovalProgram: "int 1",
+		ClearStateProgram: `top:
+int 1
+pop
+b top
+`,
+	}
+
+	eval := nextBlock(t, l, true, nil)
+	txn(t, l, eval, &badCallee)
+	vb := endBlock(t, l, eval)
+	badId := vb.Block().Payset[0].ApplicationID
+
+	// Outer is a simple app that will invoke the given app (in ForeignApps[0])
+	// with the given OnCompletion (in ApplicationArgs[0]).  Goal is to use it
+	// to opt into, and then clear state,  the bad app
+	outer := txntest.Txn{
+		Type:   "appl",
+		Sender: addrs[0],
+		ApprovalProgram: main(`
+itxn_begin
+ int appl
+ itxn_field TypeEnum
+ txn Applications 1
+ itxn_field ApplicationID
+ txn ApplicationArgs 0
+ btoi
+ itxn_field OnCompletion
+ global OpcodeBudget
+ store 0
+itxn_submit
+global OpcodeBudget
+store 1
+
+txn ApplicationArgs 0
+btoi
+int ClearState
+!=
+bnz skip						// Don't do budget checking during optin
+ load 0
+ load 1
+ int 3							// OpcodeBudget lines were 3 instructions apart
+ +								// ClearState got 700 added to budget, tried to take all,
+ ==								// but ended up just using that 700
+ assert
+skip:
+`),
+		ForeignApps: []basics.AppIndex{badId},
+	}
+
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &outer)
+	vb = endBlock(t, l, eval)
+	outerId := vb.Block().Payset[0].ApplicationID
+
+	fund := txntest.Txn{
+		Type:     "pay",
+		Sender:   addrs[0],
+		Receiver: outerId.Address(),
+		Amount:   1_000_000,
+	}
+
+	call := txntest.Txn{
+		Type:            "appl",
+		Sender:          addrs[0],
+		ApplicationID:   outerId,
+		ApplicationArgs: [][]byte{{byte(transactions.OptInOC)}},
+		ForeignApps:     []basics.AppIndex{badId},
+	}
+	eval = nextBlock(t, l, true, nil)
+	txns(t, l, eval, &fund, &call)
+	endBlock(t, l, eval)
+
+	outerAcct := lookup(t, l, outerId.Address())
+	require.Len(t, outerAcct.AppLocalStates, 1)
+
+	// When doing a clear state, `call` checks that budget wasn't stolen
+	call.ApplicationArgs = [][]byte{{byte(transactions.ClearStateOC)}}
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &call)
+	endBlock(t, l, eval)
+
+	// Clearstate took effect, despite failure from infinite loop
+	outerAcct = lookup(t, l, outerId.Address())
+	require.Empty(t, outerAcct.AppLocalStates)
+}
+
+// TestInnerClearStateBadCaller ensures that inner clear state programs cannot
+// be called with less than 700 (MaxAppProgramCost)) OpcodeBudget.
+func TestInnerClearStateBadCaller(t *testing.T) {
+	partitiontest.PartitionTest(t)
+
+	genBalances, addrs, _ := ledgertesting.NewTestGenesis()
+	l := newTestLedger(t, genBalances)
+	defer l.Close()
+
+	inner := txntest.Txn{
+		Type:            "appl",
+		Sender:          addrs[0],
+		ApprovalProgram: "int 1",
+		ClearStateProgram: `global OpcodeBudget
+itob
+log
+int 1`,
+		LocalStateSchema: basics.StateSchema{
+			NumUint:      1,
+			NumByteSlice: 2,
+		},
+	}
+
+	// waster allows tries to get the budget down below 100 before returning
+	waster := txntest.Txn{
+		Type:   "appl",
+		Sender: addrs[0],
+		ApprovalProgram: main(`
+global OpcodeBudget
+itob
+log
+top:
+global OpcodeBudget
+int 100
+<
+bnz done
+ byte "junk"
+ sha256
+ pop
+ b top
+done:
+global OpcodeBudget
+itob
+log
+`),
+		LocalStateSchema: basics.StateSchema{
+			NumUint:      3,
+			NumByteSlice: 4,
+		},
+	}
+
+	eval := nextBlock(t, l, true, nil)
+	txns(t, l, eval, &inner, &waster)
+	vb := endBlock(t, l, eval)
+	innerId := vb.Block().Payset[0].ApplicationID
+	wasterId := vb.Block().Payset[1].ApplicationID
+
+	// Grouper is a simple app that will invoke the given apps (in
+	// ForeignApps[0,1]) as a group, with the given OnCompletion (in
+	// ApplicationArgs[0]).
+	grouper := txntest.Txn{
+		Type:   "appl",
+		Sender: addrs[0],
+		ApprovalProgram: main(`
+itxn_begin
+ int appl
+ itxn_field TypeEnum
+ txn Applications 1
+ itxn_field ApplicationID
+ txn ApplicationArgs 0
+ btoi
+ itxn_field OnCompletion
+itxn_next
+ int appl
+ itxn_field TypeEnum
+ txn Applications 2
+ itxn_field ApplicationID
+ txn ApplicationArgs 1
+ btoi
+ itxn_field OnCompletion
+itxn_submit
+`),
+	}
+
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &grouper)
+	vb = endBlock(t, l, eval)
+	grouperId := vb.Block().Payset[0].ApplicationID
+
+	fund := txntest.Txn{
+		Type:     "pay",
+		Sender:   addrs[0],
+		Receiver: grouperId.Address(),
+		Amount:   1_000_000,
+	}
+
+	call := txntest.Txn{
+		Type:            "appl",
+		Sender:          addrs[0],
+		ApplicationID:   grouperId,
+		ApplicationArgs: [][]byte{{byte(transactions.OptInOC)}, {byte(transactions.OptInOC)}},
+		ForeignApps:     []basics.AppIndex{wasterId, innerId},
+	}
+	eval = nextBlock(t, l, true, nil)
+	txns(t, l, eval, &fund, &call)
+	endBlock(t, l, eval)
+
+	gAcct := lookup(t, l, grouperId.Address())
+	require.Len(t, gAcct.AppLocalStates, 2)
+
+	call.ApplicationArgs = [][]byte{{byte(transactions.CloseOutOC)}, {byte(transactions.ClearStateOC)}}
+	eval = nextBlock(t, l, true, nil)
+	txn(t, l, eval, &call, "ClearState execution with low OpcodeBudget")
+	vb = endBlock(t, l, eval)
+	require.Len(t, vb.Block().Payset, 0)
+
+	// Clearstate did not take effect, since the caller tried to shortchange the CSP
+	gAcct = lookup(t, l, grouperId.Address())
+	require.Len(t, gAcct.AppLocalStates, 2)
+}
+
+// TestClearStateInnerPay ensures that ClearState programs can run inner txns in
+// v30, but not in vFuture. (Test should add v31 after it exists.)
+func TestClearStateInnerPay(t *testing.T) {
+	partitiontest.PartitionTest(t)
+
+	tests := []struct {
+		consensus protocol.ConsensusVersion
+		approval  string
+	}{
+		{protocol.ConsensusFuture, "int 1"},
+		{protocol.ConsensusV30, "int 1"},
+		{protocol.ConsensusFuture, "int 0"},
+		{protocol.ConsensusV30, "int 0"},
+	}
+
+	for i, test := range tests {
+		t.Run(fmt.Sprintf("i=%d", i), func(t *testing.T) {
+
+			genBalances, addrs, _ := ledgertesting.NewTestGenesis()
+			l := newTestLedgerWithConsensusVersion(t, genBalances, test.consensus)
+			defer l.Close()
+
+			app0 := txntest.Txn{
+				Type:   "appl",
+				Sender: addrs[0],
+				ApprovalProgram: main(`
+itxn_begin
+	int pay
+	itxn_field TypeEnum
+	int 3000
+	itxn_field Amount
+    txn Sender
+    itxn_field Receiver
+itxn_submit`),
+				ClearStateProgram: `
+itxn_begin
+	int pay
+	itxn_field TypeEnum
+	int 2000
+	itxn_field Amount
+    txn Sender
+    itxn_field Receiver
+itxn_submit
+` + test.approval,
+			}
+			eval := nextBlock(t, l, true, nil)
+			txn(t, l, eval, &app0)
+			vb := endBlock(t, l, eval)
+			index0 := vb.Block().Payset[0].ApplicationID
+
+			fund0 := txntest.Txn{
+				Type:     "pay",
+				Sender:   addrs[0],
+				Receiver: index0.Address(),
+				Amount:   1_000_000,
+			}
+
+			optin := txntest.Txn{
+				Type:          "appl",
+				Sender:        addrs[1],
+				ApplicationID: index0,
+				OnCompletion:  transactions.OptInOC,
+			}
+
+			eval = nextBlock(t, l, true, nil)
+			txns(t, l, eval, &fund0, &optin)
+			vb = endBlock(t, l, eval)
+
+			// Check that addrs[1] got paid during optin, and pay txn is in block
+			ad1 := micros(t, l, addrs[1])
+
+			// paid 3000, but 1000 fee, 2000 bump
+			require.Equal(t, uint64(2000), ad1-genBalances.Balances[addrs[1]].MicroAlgos.Raw)
+			// InnerTxn in block ([1] position, because followed fund0)
+			require.Len(t, vb.Block().Payset[1].EvalDelta.InnerTxns, 1)
+			require.Equal(t, vb.Block().Payset[1].EvalDelta.InnerTxns[0].Txn.Amount.Raw, uint64(3000))
+
+			clear := txntest.Txn{
+				Type:          "appl",
+				Sender:        addrs[1],
+				ApplicationID: index0,
+				OnCompletion:  transactions.ClearStateOC,
+			}
+
+			eval = nextBlock(t, l, true, nil)
+			txns(t, l, eval, &clear)
+			vb = endBlock(t, l, eval)
+
+			// Check if addrs[1] got paid during clear, and pay txn is in block
+			ad1 = micros(t, l, addrs[1])
+
+			// The pay only happens if the clear state approves (and it was legal back in V30)
+			if test.approval == "int 1" && test.consensus == protocol.ConsensusV30 {
+				// had 2000 bump, now paid 2k, charge 1k, left with 3k total bump
+				require.Equal(t, uint64(3000), ad1-genBalances.Balances[addrs[1]].MicroAlgos.Raw)
+				// InnerTxn in block
+				require.Equal(t, vb.Block().Payset[0].Txn.ApplicationID, index0)
+				require.Equal(t, vb.Block().Payset[0].Txn.OnCompletion, transactions.ClearStateOC)
+				require.Len(t, vb.Block().Payset[0].EvalDelta.InnerTxns, 1)
+				require.Equal(t, vb.Block().Payset[0].EvalDelta.InnerTxns[0].Txn.Amount.Raw, uint64(2000))
+			} else {
+				// Only the fee is paid because pay is "erased", so goes from 2k down to 1k
+				require.Equal(t, uint64(1000), ad1-genBalances.Balances[addrs[1]].MicroAlgos.Raw)
+				// no InnerTxn in block
+				require.Equal(t, vb.Block().Payset[0].Txn.ApplicationID, index0)
+				require.Equal(t, vb.Block().Payset[0].Txn.OnCompletion, transactions.ClearStateOC)
+				require.Len(t, vb.Block().Payset[0].EvalDelta.InnerTxns, 0)
+			}
+		})
+	}
+}
diff --git a/ledger/internal/eval_blackbox_test.go b/ledger/internal/eval_blackbox_test.go
index b468bda83..d2a1e0d37 100644
--- a/ledger/internal/eval_blackbox_test.go
+++ b/ledger/internal/eval_blackbox_test.go
@@ -656,6 +656,41 @@ func asaParams(t testing.TB, ledger *ledger.Ledger, asset basics.AssetIndex) (ba
 	return basics.AssetParams{}, fmt.Errorf("bad lookup (%d)", asset)
 }
 
+func TestGarbageClearState(t *testing.T) {
+	partitiontest.PartitionTest(t)
+
+	genesisInitState, addrs, _ := ledgertesting.Genesis(10)
+
+	l, err := ledger.OpenLedger(logging.TestingLog(t), "", true, genesisInitState, config.GetDefaultLocal())
+	require.NoError(t, err)
+	defer l.Close()
+
+	createTxn := txntest.Txn{
+		Type:            "appl",
+		Sender:          addrs[0],
+		ApprovalProgram: "int 1",
+	}
+
+	eval := nextBlock(t, l, true, nil)
+
+	// Do this "by hand" so we can have an empty / garbage clear state, which
+	// would have been papered over with txn()
+	fillDefaults(t, l, eval, &createTxn)
+	stxn := createTxn.SignedTxn()
+	stxn.Txn.ClearStateProgram = nil
+	err = eval.TestTransactionGroup([]transactions.SignedTxn{stxn})
+	require.Error(t, err)
+	require.Contains(t, err.Error(), "invalid program")
+	err = eval.Transaction(stxn, transactions.ApplyData{})
+	require.Error(t, err)
+	require.Contains(t, err.Error(), "invalid program")
+
+	stxn.Txn.ClearStateProgram = []byte{0xfe} // bad uvarint
+	err = eval.TestTransactionGroup([]transactions.SignedTxn{stxn})
+	require.Error(t, err)
+	require.Contains(t, err.Error(), "invalid version")
+}
+
 func TestRewardsInAD(t *testing.T) {
 	partitiontest.PartitionTest(t)
 
@@ -986,6 +1021,56 @@ func TestAppInsMinBalance(t *testing.T) {
 	require.Len(t, vb.Delta().ModifiedAppLocalStates, 50)
 }
 
+// TestLogsInBlock ensures that logs appear in the block properly
+func TestLogsInBlock(t *testing.T) {
+	partitiontest.PartitionTest(t)
+
+	genesisInitState, addrs, _ := ledgertesting.Genesis(10)
+
+	l, err := ledger.OpenLedger(logging.TestingLog(t), "", true, genesisInitState, config.GetDefaultLocal())
+	require.NoError(t, err)
+	defer l.Close()
+
+	const appid basics.AppIndex = 1
+	createTxn := txntest.Txn{
+		Type:            "appl",
+		Sender:          addrs[0],
+		ApprovalProgram: "byte \"APP\"\n log\n int 1",
+		// Fail the clear state
+		ClearStateProgram: "byte \"CLR\"\n log\n int 0",
+	}
+	eval := nextBlock(t, l, true, nil)
+	txns(t, l, eval, &createTxn)
+	vb := endBlock(t, l, eval)
+	createInBlock := vb.Block().Payset[0]
+	require.Equal(t, "APP", createInBlock.ApplyData.EvalDelta.Logs[0])
+
+	optInTxn := txntest.Txn{
+		Type:          protocol.ApplicationCallTx,
+		Sender:        addrs[1],
+		ApplicationID: appid,
+		OnCompletion:  transactions.OptInOC,
+	}
+	eval = nextBlock(t, l, true, nil)
+	txns(t, l, eval, &optInTxn)
+	vb = endBlock(t, l, eval)
+	optInInBlock := vb.Block().Payset[0]
+	require.Equal(t, "APP", optInInBlock.ApplyData.EvalDelta.Logs[0])
+
+	clearTxn := txntest.Txn{
+		Type:          protocol.ApplicationCallTx,
+		Sender:        addrs[1],
+		ApplicationID: appid,
+		OnCompletion:  transactions.ClearStateOC,
+	}
+	eval = nextBlock(t, l, true, nil)
+	txns(t, l, eval, &clearTxn)
+	vb = endBlock(t, l, eval)
+	clearInBlock := vb.Block().Payset[0]
+	// Logs do not appear if the ClearState failed
+	require.Len(t, clearInBlock.ApplyData.EvalDelta.Logs, 0)
+}
+
 // TestGhostTransactions confirms that accounts that don't even exist
 // can be the Sender in some situations.  If some other transaction
 // covers the fee, and the transaction itself does not require an
diff --git a/test/scripts/e2e_subs/e2e-app-extra-pages.sh b/test/scripts/e2e_subs/e2e-app-extra-pages.sh
index 54732deb8..1b9dd779c 100755
--- a/test/scripts/e2e_subs/e2e-app-extra-pages.sh
+++ b/test/scripts/e2e_subs/e2e-app-extra-pages.sh
@@ -77,7 +77,7 @@ fi
 
 # App create with extra pages, v4 teal
 RES=$(${gcmd} app create --creator ${ACCOUNT} --approval-prog "${BIG_TEAL_V4_FILE}" --clear-prog "${BIG_TEAL_V4_FILE}" --extra-pages 3 --global-byteslices 1 --global-ints 0 --local-byteslices 0 --local-ints 0 2>&1 || true)
-EXPERROR="pc=704 dynamic cost budget exceeded, executing intc_0: local program cost was 701"
+EXPERROR="pc=704 dynamic cost budget exceeded, executing intc_0: local program cost was 700"
 if [[ $RES != *"${EXPERROR}"* ]]; then
     date '+app-extra-pages-test FAIL the application creation should fail %Y%m%d_%H%M%S'
     false
diff --git a/test/scripts/e2e_subs/goal/goal.py b/test/scripts/e2e_subs/goal/goal.py
index d21be52ad..969fc2053 100755
--- a/test/scripts/e2e_subs/goal/goal.py
+++ b/test/scripts/e2e_subs/goal/goal.py
@@ -300,7 +300,8 @@ class Goal:
     ):
         assert not kwargs.pop("index", None)
         if not clear_program:
-            clear_program = self.assemble("#pragma version 2\nint 1")
+            approve = f"#pragma version {approval_program[0]}\nint 1"
+            clear_program = self.assemble(approve)
         return self.appl(
             sender,
             0,