AVM: Adding sumhash and falcon_verify (#5599)

7 files changed, 142 insertions, 29 deletions

diff --git a/data/transactions/logic/assembler_test.go b/data/transactions/logic/assembler_test.go
index e73129b43..3f609fd7e 100644
--- a/data/transactions/logic/assembler_test.go
+++ b/data/transactions/logic/assembler_test.go
@@ -427,6 +427,13 @@ match_label1:
 pushbytess "1" "2" "1"
 `
 
+const stateProofNonsense = `
+pushbytes 0x0123456789abcd
+sumhash512
+dup; dup
+falcon_verify
+`
+
 const v8Nonsense = v7Nonsense + switchNonsense + frameNonsense + matchNonsense + boxNonsense
 
 const v9Nonsense = v8Nonsense
@@ -438,7 +445,7 @@ const spliceNonsence = `
 
 const v10Nonsense = v9Nonsense + pairingNonsense + spliceNonsence
 
-const v11Nonsense = v10Nonsense
+const v11Nonsense = v10Nonsense + stateProofNonsense
 
 const v6Compiled = "2004010002b7a60c26050242420c68656c6c6f20776f726c6421070123456789abcd208dae2087fbba51304eb02b91f656948397a7946390e8cb70fc9ea4d95f92251d047465737400320032013202320380021234292929292b0431003101310231043105310731083109310a310b310c310d310e310f3111311231133114311533000033000133000233000433000533000733000833000933000a33000b33000c33000d33000e33000f3300113300123300133300143300152d2e01022581f8acd19181cf959a1281f8acd19181cf951a81f8acd19181cf1581f8acd191810f082209240a220b230c240d250e230f2310231123122313231418191a1b1c28171615400003290349483403350222231d4a484848482b50512a632223524100034200004322602261222704634848222862482864286548482228246628226723286828692322700048482371004848361c0037001a0031183119311b311d311e311f312023221e312131223123312431253126312731283129312a312b312c312d312e312f447825225314225427042455220824564c4d4b0222382124391c0081e80780046a6f686e2281d00f23241f880003420001892224902291922494249593a0a1a2a3a4a5a6a7a8a9aaabacadae24af3a00003b003c003d816472064e014f012a57000823810858235b235a2359b03139330039b1b200b322c01a23c1001a2323c21a23c3233e233f8120af06002a494905002a49490700b400b53a03b6b7043cb8033a0c2349c42a9631007300810881088120978101c53a8101c6003a"
 
@@ -460,7 +467,9 @@ const spliceCompiled = "d2d3"
 
 const v10Compiled = v9Compiled + pairingCompiled + spliceCompiled
 
-const V11Compiled = v10Compiled
+const stateProofCompiled = "80070123456789abcd86494985"
+
+const V11Compiled = v10Compiled + stateProofCompiled
 
 var nonsense = map[uint64]string{
 	1:  v1Nonsense,
@@ -541,7 +550,7 @@ func TestAssemble(t *testing.T) {
 	}
 }
 
-var experiments = []uint64{}
+var experiments = []uint64{spOpcodesVersion}
 
 // TestExperimental forces a conscious choice to promote "experimental" opcode
 // groups. This will fail when we increment vFuture's LogicSigVersion. If we had
diff --git a/data/transactions/logic/crypto.go b/data/transactions/logic/crypto.go
index feb20725f..c5c39b654 100644
--- a/data/transactions/logic/crypto.go
+++ b/data/transactions/logic/crypto.go
@@ -28,6 +28,7 @@ import (
 	"github.com/algorand/go-algorand/crypto"
 	"github.com/algorand/go-algorand/crypto/secp256k1"
 	"github.com/algorand/go-algorand/protocol"
+	"github.com/algorand/go-sumhash"
 	"golang.org/x/crypto/sha3"
 )
 
@@ -70,6 +71,34 @@ func opSHA512_256(cx *EvalContext) error {
 	return nil
 }
 
+// Sumhash512 corresponds to the hash used in State Proofs
+func opSumhash512(cx *EvalContext) error {
+	last := len(cx.Stack) - 1
+	h := sumhash.New512(nil)
+	h.Write(cx.Stack[last].Bytes)
+	cx.Stack[last].Bytes = h.Sum(nil)
+	return nil
+}
+
+func opFalconVerify(cx *EvalContext) error {
+	last := len(cx.Stack) - 1 // index of PK
+	prev := last - 1          // index of signature
+	pprev := prev - 1         // index of data
+
+	var fv crypto.FalconVerifier
+	if len(cx.Stack[last].Bytes) != len(fv.PublicKey) {
+		return fmt.Errorf("invalid public key size %d != %d", len(cx.Stack[last].Bytes), len(fv.PublicKey))
+	}
+	copy(fv.PublicKey[:], cx.Stack[last].Bytes)
+
+	sig := crypto.FalconSignature(cx.Stack[prev].Bytes)
+
+	err := fv.VerifyBytes(cx.Stack[pprev].Bytes, sig)
+	cx.Stack[pprev] = boolToSV(err == nil)
+	cx.Stack = cx.Stack[:prev]
+	return nil
+}
+
 // Msg is data meant to be signed and then verified with the
 // ed25519verify opcode.
 type Msg struct {
diff --git a/data/transactions/logic/crypto_test.go b/data/transactions/logic/crypto_test.go
index 7f539b8c7..bb6ef59c5 100644
--- a/data/transactions/logic/crypto_test.go
+++ b/data/transactions/logic/crypto_test.go
@@ -55,6 +55,31 @@ byte 0xc195eca25a6f4c82bfba0287082ddb0d602ae9230f9cf1f1a40b68f8e2c41567
 	testAccepts(t, progText, 1)
 }
 
+func TestSumhash(t *testing.T) {
+	partitiontest.PartitionTest(t)
+	t.Parallel()
+
+	/* tests extracted from test vector in go-algorand/sumhash	*/
+	testVectors := []struct{ in, out string }{
+		{
+			"",
+			"591591c93181f8f90054d138d6fa85b63eeeb416e6fd201e8375ba05d3cb55391047b9b64e534042562cc61944930c0075f906f16710cdade381ee9dd47d10a0",
+		},
+		{
+			"a",
+			"ea067eb25622c633f5ead70ab83f1d1d76a7def8d140a587cb29068b63cb6407107aceecfdffa92579ed43db1eaa5bbeb4781223a6e07dd5b5a12d5e8bde82c6",
+		},
+		{
+			"I think, therefore I am. – Rene Descartes.",
+			"2d4583cdb18710898c78ec6d696a86cc2a8b941bb4d512f9d46d96816d95cbe3f867c9b8bd31964406c847791f5669d60b603c9c4d69dadcb87578e613b60b7a",
+		},
+	}
+
+	for _, v := range testVectors {
+		testAccepts(t, fmt.Sprintf(`byte "%s"; sumhash512; byte 0x%s; ==`, v.in, v.out), 11)
+	}
+}
+
 func TestSHA3_256(t *testing.T) {
 	partitiontest.PartitionTest(t)
 	t.Parallel()
@@ -170,6 +195,14 @@ byte 0x13e49a19378bbfa8d55ac81a35b87d7bae456c79fcf04a78803d8eb45b253fab
 byte 0xa2d237cd897ca70787abf04d2155c6dc2fbe26fd642e0472cd75c13dc919ef1a
 ecdsa_verify Secp256r1
 assert`, "int 1"},
+		{"falcon_verify", "", `
+byte 0x62fdfc072182654f163f5f0f9a621d729566c74d0aa413bf009c9800418c19cd // msg
+// public key
+byte  0xba00a5222fbaa5e2a1a61f708198a4dbc3de94b60d925042d9fa5a299ebb4be27156b1d86a174df4939342f11b776dffb8a0e874714f23318ca9acb823e9aeb14a926ed5cf76e736faa0b22e4bdedf7910decd19329f353b926ae4b404653dbc6db1885c010052b94675d4cc209ef2cf3cfe910c4ef51b6af16d8c7ab6651e57934ab19c89f771058f389ad80474740c529d59a3ea9ab9db228415fb9315dee23e8c7229398c4b0a2b7c5d6eff6e7d8cf1a776ae37f6272082796c0b2a0af637f7ce8fa7f1675dfbd1766543cbf3f19544d635298ea1fafe96ad1bb06fcc6ae9ff9c34acacb88653555c37f2ad6c4eb408478b0d2b6269841243f29b18fa8e0d5050f4f93878e53aac466dc4eb5a7194cb2213c26a2b8c7ccea06f89af26ae85315454da1b15952be639bb94fe3e99236291c4a1edfbe9faf8f32589bf47eb536b28e2cfbdea799d9cf4c88ef85ae45d451e1ab3431c247b796cbf12e63b737cc4894ad7a204f680a449cbbd2e86deca1069b3592977bd8ac7c5b5e1c1b436cde65177b6e82b2e666117a8e37b58122d1a31307ca112311e665b32c68bd42531b4e6bc79957d3d865f6470b8213db8175e5c7115f4ad520a4711b12d9004e661346c4da4cb3e95954ac58e075a320b862a6a317e0988d8fc376fb14562773b9d35d5a44ba951d866a3a06ac93a55e1a26fa91718db49a53e78d9e61d6120dfadd2b4929579ac56ccaac0f8e704826b55b4ca6d8020e42a6e62b5e41708e2e6848cd047385fa1df4f51733df35dbee25c96c4176eae332ca4df31c695fff8be31b4be62e63c3e049483c89384fb1d802e58db5514a59eb96e527b202d0cf45dc760fa0439afbc661868b9408e67254c8cf7c689c50d2f29bccd59c71ea7b6dd368de68669fdf889ac1f8cd390ea17894dd0538ff6e7c740bbf03b4fe32ad66c483c823548eea84f85826da44016bd8cdf2315b07a96a9737ebc7cb244547be3f759bdf50b467552c58333ed7e61cde799346bccc29d5d377d9d5364c369ffd88a83f90a699b3622184436b518e9196524ac9b55385b39ec099d9c18386e06b9dcad2499ddb9673cb87c652209ee60511c9249f1b7ab2b948b5e8b9115c218d5b793d65b96e2fc9e2c6c40ba63791bb89d7d96c33536ad7e6668a85e52ec7e1450a69f25766deeaeb41bcd249394b8ab65a286312db461c363cebe431c4dd5fd3b6bb5d26ae2c597799f400abb3ba160522e2e6da5ebd170a45c9ce80b135a5b330656aab26399bcacd857a7f237dfd2b14ecbfbcaabc7291ba78fe19ac2ecf005b66bb9771bf64f090269a2341967e79702733dc617b469ac12123faeb4c70d6fffac25f9fcd7dbd12ca363985b9bd845e939e6caf328e2bf8e53725bae94fbe30bfdbbc21e584ba72d7badbc2a0915c9faf9c69ad3703cf99a16399b38df157be8ec3a78f20d24b2131f9c25b3c1da70fc6c0c7aa9e9da3108368ca6211dcfa4988b1ace3c28b15b0559224570fbe3cde364734c7a66a0525c1d41e26788cd1c8a3888f344c9385804364f8430ca7d22338cc941917da3dc47a00aae13e3e972af49940c8fa179574694e369a3d5e67db6c91bf843151ca0fff512d9c322c690063ae9bd671815e9d03b3a841952ce04683509e415b8d5aebfcdbd6bd55efbffb2463cf2b96ccb8650a6cee732c8d4ce6409b9a747317866759553f1c5bcc392c98d14a034ccaaa6df5723bb88c38e80
+// sig
+byte 0x0a85ea3bb342a95a3941a4c2280c686729c76bc164092c0e203388460c556273e6f0a92640650c37e9d5b08fbd8d6bcca940acac9964e64a9e78bd28086b52898812264985e19c3d26318be2ec8852ca2ae2380746428cd08124cf792790d127d3dad09fe891cbadefef36269ae7d584b77ec428d794a6c3b7555956db00314d14a0aa14936830c8622623916639743b218243344224472240cfd158819190ede108394063c3df9c474eb16aa750e48663515d8229d3849670e30891142b632a6a282d915273a5f219d65ebe6b9e6c88170ac62c16a44895a950bfec82819221dab1358861bf0aa6b6342477016d50502a298840ddc42b3ade784b643c63c5e47993ada37dfdc0d56a1c7e4690b5a1d6485900b84f0b61425383b14d4b7ccc0abe8284a47a6f22050838b0482ad8ad389151c25e790ad670d5530f9b3dc518bb0a410f64346a74dc824238026daaa4ad97518d93670a48cf8f86ece593d23ab3a0d601d49a975db291f0d76263551e9f0b8a1b42396a27d9a122210330c692d5545d67c808b50560fc3d4933fa70c463513d7183e8aa091f34dd4426272620fe4b357deea710c687bb7a475d0ed0a40a26ae8f2a357e7a8fa5d5434050c1a36beaa7a90ee4db213a126db8151f2f4bbb4889d4e42bbd19f62dd7285def148071fb7f4f16b28c1d145d2e621fee275161a3d5b9319e7a59527c3d5c2838ef503e4166f2c22118b22bf80e8a1fc1bbbba00f231d2b1a8d3e592bdcc5fd40a2ecebb5ad27a51e7867715b54185a3e62951a5d808d80c31a59e6a3ca53a51eadc34c76dfd6aac22a6e805163b5e9ac8090869a9cd1e2972af7192bcd1da39c30f423ebc86d1976e8f52052262521d3b8ae7eb99d0ad623d811bac636f447e7dc9dcef6f52befd95861f1917116517b0e9b56a85967ab701ff8f1d4de443efce1b2a3d85b592df7a8c87814e8981575ef4e72757c5afa6bec4358e2f29966ad2830e4782f9a293351dfcaac1d0ca30ec1b5fd08a40a6e82938427a68641b96252a85443141c081982ba4d3c8ab05a1a545ea49c23ee07643ec5f013c2676db09cb834ef61817e615ad19c5829216026e5635dc13cad5ffb8bc267bf58d4ebbf100c3045e250c02c10772e96c580db049c80fdd3188e19ad893d16ac100052c557378416929319c9c262c21b768e6058a09b4e4800ae624c892117ec71504a283f558c623a212d048d5d401b00448b18ac25e1c99ab35d91f78badebcd651e86f3465ef99a0afa1721d2153e4a7b51d22b344a8dd102e7411abfe4bd5b8e2d62015edc08fc461fa90cfa666a9a42a0a86e11d6988913ba0259096cb846a1fd311c4cb693c4e3e1ed2ab57e2a5e0bd4616a79e22b28caa6d10dd09225e44bbdbfa1b7b23887055a90918220252777d5a620351cb013cc28346fc69d348165a39d03243a84a9c9bcd4d557a8e9607256baab893a0a5644520686be935e9ead84501f743a489a431cf10b8c27d3901c87b8771ce65e3130a7fe6ad62b709c23bbef1381b1ed49222f487db16af3c9d6779c01c986ea9f823be017fb8bce8e00f2b32840d54e8f656139a4c492257ee8743a8c5f51450c0366655e2b02d27619d07e556001430b04454891247813c8bc31bdee926d039a5038bfca8dc35e57789950442ad7ab3cfc031a8354bd9c462a37052d0b62066bcee0c292b890a71f4ea65895a7d837283404842c59f08414b20ec1b4fda6cc0c4d62216e8ead74ba90196168bc449a2050b442181ea57b915581bc387ed412e4cd5970fd0fb83c94fbbf960d05ffe6d0a26171c249809604a0b2b411e2d6622145c936e31258baf2b7d3c413a9a1d67bc4026d01b47a10b6c5b87f6a36ba1cedd681ca55b9c042bf9afcfcb636040793e08158dd877c49c16658f819129e26237427a1d80b941fbabb4abd4f1da0b6d428a59fbc450620eeb1651849e5972fb12e6dc8092a9fda70206a48d9dc2645641a147626350cf45b1a7d57724fcab0a594df7c023928a3c7a2fc3c9d33e9af10ae5ed282c475a611671d20d90752f2a28db48b7e5d9184212432fa948fbc885f866c93a0b7f510329aea4d53ecf9482f42974beaf289086afdb4797aa129d10639948f46a805ea4000cf1554505f4bd9d775d5894da115f5840913d5070c860b3a623eb261f5f928a31cbcec17c4274b5d1b28fdb231cc8f606c9dc324db5c12f97518fd03466541f7881762c25d711976c6d4f9271d29fa51dc263f650a32010343a51e7dab344e2f6d768864072ddb5df58486434998a280aad94886ea7a11132184e6274d4cd59a5deabf8a4dbbe29e9c234a52d3972608d0a3ea92a78e08531bb938384444246be5bc594ed4d06168e870924e8913f8242bd35f7c9d5ee238cb6db17496047acce0183f2d10a4cf2bbc8e39daf44e630393a0473b8983863b1998c17026ff35ec32a8058fd603ec369b80a94cb7b555cb469f6468de3909b21293b8d0a53a5c813d218d7c630f4d47bb1eb88253e6e1af721ba8a4453e
+falcon_verify
+assert`, "int 1"},
 		{"vrf_verify", "", `byte 0x72
 byte 0xae5b66bdf04b4c010bfe32b2fc126ead2107b697634f6f7337b9bff8785ee111200095ece87dde4dbe87343f6df3b107d91798c8a7eb1245d3bb9c5aafb093358c13e6ae1111a55717e895fd15f99f07
 byte 0x3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c
@@ -264,6 +297,52 @@ func TestEd25519VerifyBare(t *testing.T) {
 	}
 }
 
+func TestFalconVerify(t *testing.T) {
+	partitiontest.PartitionTest(t)
+	t.Parallel()
+
+	var s crypto.FalconSeed
+	fs, err := crypto.GenerateFalconSigner(s)
+	require.NoError(t, err)
+
+	msg := "62fdfc072182654f163f5f0f9a621d729566c74d0aa413bf009c9800418c19cd"
+	data, err := hex.DecodeString(msg)
+	require.NoError(t, err)
+
+	yes := testProg(t, fmt.Sprintf(`arg 0; arg 1; byte 0x%s; falcon_verify`,
+		hex.EncodeToString(fs.PublicKey[:])), 11)
+	require.NoError(t, err)
+	no := testProg(t, fmt.Sprintf(`arg 0; arg 1; byte 0x%s; falcon_verify; !`,
+		hex.EncodeToString(fs.PublicKey[:])), 11)
+	require.NoError(t, err)
+
+	for v := uint64(11); v <= AssemblerMaxVersion; v++ {
+		t.Run(fmt.Sprintf("v=%d", v), func(t *testing.T) {
+			yes.Program[0] = byte(v)
+			sig, err := fs.SignBytes(data)
+			require.NoError(t, err)
+
+			var txn transactions.SignedTxn
+			txn.Lsig.Args = [][]byte{data[:], sig[:]}
+			testLogicBytes(t, yes.Program, defaultSigParams(txn))
+			testLogicBytes(t, no.Program, defaultSigParams(txn), "REJECT")
+
+			// short sig will fail
+			txn.Lsig.Args[1] = sig[1:]
+			testLogicBytes(t, yes.Program, defaultSigParams(txn), "REJECT")
+			testLogicBytes(t, no.Program, defaultSigParams(txn))
+
+			// flip a bit and it should not pass
+			msg1 := "52fdfc072182654f163f5f0f9a621d729566c74d0aa413bf009c9800418c19cd"
+			data1, err := hex.DecodeString(msg1)
+			require.NoError(t, err)
+			txn.Lsig.Args = [][]byte{data1, sig[:]}
+			testLogicBytes(t, yes.Program, defaultSigParams(txn), "REJECT")
+			testLogicBytes(t, no.Program, defaultSigParams(txn))
+		})
+	}
+}
+
 func keyToByte(tb testing.TB, b *big.Int) []byte {
 	k := make([]byte, 32)
 	require.NotPanics(tb, func() {
@@ -636,26 +715,13 @@ int ` + fmt.Sprintf("%d", testLogicBudget-2500-8) + `
 	testAccepts(t, source, fidoVersion)
 }
 
-func BenchmarkHash(b *testing.B) {
-	for _, hash := range []string{"sha256", "keccak256", "sha512_256"} {
-		b.Run(hash+"-0w", func(b *testing.B) { // hash 0 bytes
-			benchmarkOperation(b, "", "byte 0x; "+hash+"; pop", "int 1")
-		})
-		b.Run(hash+"-32", func(b *testing.B) { // hash 32 bytes
-			benchmarkOperation(b, "int 32; bzero", hash, "pop; int 1")
-		})
-		b.Run(hash+"-128", func(b *testing.B) { // hash 128 bytes
-			benchmarkOperation(b, "int 32; bzero",
-				"dup; concat; dup; concat;"+hash, "pop; int 1")
-		})
-		b.Run(hash+"-512", func(b *testing.B) { // hash 512 bytes
-			benchmarkOperation(b, "int 32; bzero",
-				"dup; concat; dup; concat; dup; concat; dup; concat;"+hash, "pop; int 1")
-		})
-		b.Run(hash+"-4096", func(b *testing.B) { // hash 4k bytes
-			benchmarkOperation(b, "int 32; bzero",
-				"dup; concat; dup; concat; dup; concat; dup; concat; dup; concat; dup; concat; dup; concat;"+hash, "pop; int 1")
-		})
+func BenchmarkHashes(b *testing.B) {
+	for _, hash := range []string{"sha256", "keccak256" /* skip, same as keccak "sha3_256", */, "sha512_256", "sumhash512"} {
+		for _, size := range []int{0, 32, 128, 512, 1024, 4096} {
+			b.Run(hash+"-"+strconv.Itoa(size), func(b *testing.B) {
+				benchmarkOperation(b, "", fmt.Sprintf("int %d; bzero; %s; pop", size, hash), "int 1")
+			})
+		}
 	}
 }
 
diff --git a/data/transactions/logic/doc.go b/data/transactions/logic/doc.go
index cfaadebdf..fde870a9d 100644
--- a/data/transactions/logic/doc.go
+++ b/data/transactions/logic/doc.go
@@ -38,6 +38,9 @@ var opDescByName = map[string]OpDesc{
 	"sha512_256": {"SHA512_256 hash of value A, yields [32]byte", "", nil},
 	"sha3_256":   {"SHA3_256 hash of value A, yields [32]byte", "", nil},
 
+	"sumhash512":    {"sumhash512 of value A, yields [64]byte", "", nil},
+	"falcon_verify": {"for (data A, compressed-format signature B, pubkey C) verify the signature of data against the pubkey", "", nil},
+
 	"ed25519verify":       {"for (data A, signature B, pubkey C) verify the signature of (\"ProgData\" || program_hash || data) against the pubkey => {0 or 1}", "The 32 byte public key is the last element on the stack, preceded by the 64 byte signature at the second-to-last element on the stack, preceded by the data which was signed at the third-to-last element on the stack.", nil},
 	"ed25519verify_bare":  {"for (data A, signature B, pubkey C) verify the signature of the data against the pubkey => {0 or 1}", "", nil},
 	"ecdsa_verify":        {"for (data A, signature B, C and pubkey D, E) verify the signature of the data against the pubkey => {0 or 1}", "The 32 byte Y-component of a public key is the last element on the stack, preceded by X-component of a pubkey, preceded by S and R components of a signature, preceded by the data that is fifth element on the stack. All values are big-endian encoded. The signed data must be 32 bytes long, and signatures in lower-S form are only accepted.", []string{"curve index"}},
@@ -349,7 +352,7 @@ var OpGroups = map[string][]string{
 	"Byte Array Manipulation": {"getbit", "setbit", "getbyte", "setbyte", "concat", "len", "substring", "substring3", "extract", "extract3", "extract_uint16", "extract_uint32", "extract_uint64", "replace2", "replace3", "base64_decode", "json_ref"},
 	"Byte Array Arithmetic":   {"b+", "b-", "b/", "b*", "b<", "b>", "b<=", "b>=", "b==", "b!=", "b%", "bsqrt"},
 	"Byte Array Logic":        {"b|", "b&", "b^", "b~"},
-	"Cryptography":            {"sha256", "keccak256", "sha512_256", "sha3_256", "ed25519verify", "ed25519verify_bare", "ecdsa_verify", "ecdsa_pk_recover", "ecdsa_pk_decompress", "vrf_verify", "ec_add", "ec_scalar_mul", "ec_pairing_check", "ec_multi_scalar_mul", "ec_subgroup_check", "ec_map_to"},
+	"Cryptography":            {"sha256", "keccak256", "sha512_256", "sha3_256", "sumhash512", "falcon_verify", "ed25519verify", "ed25519verify_bare", "ecdsa_verify", "ecdsa_pk_recover", "ecdsa_pk_decompress", "vrf_verify", "ec_add", "ec_scalar_mul", "ec_pairing_check", "ec_multi_scalar_mul", "ec_subgroup_check", "ec_map_to"},
 	"Loading Values":          {"intcblock", "intc", "intc_0", "intc_1", "intc_2", "intc_3", "pushint", "pushints", "bytecblock", "bytec", "bytec_0", "bytec_1", "bytec_2", "bytec_3", "pushbytes", "pushbytess", "bzero", "arg", "arg_0", "arg_1", "arg_2", "arg_3", "args", "txn", "gtxn", "txna", "txnas", "gtxna", "gtxnas", "gtxns", "gtxnsa", "gtxnsas", "global", "load", "loads", "store", "stores", "gload", "gloads", "gloadss", "gaid", "gaids"},
 	"Flow Control":            {"err", "bnz", "bz", "b", "return", "pop", "popn", "dup", "dup2", "dupn", "dig", "bury", "cover", "uncover", "frame_dig", "frame_bury", "swap", "select", "assert", "callsub", "proto", "retsub", "switch", "match"},
 	"State Access":            {"balance", "min_balance", "app_opted_in", "app_local_get", "app_local_get_ex", "app_global_get", "app_global_get_ex", "app_local_put", "app_global_put", "app_local_del", "app_global_del", "asset_holding_get", "asset_params_get", "app_params_get", "acct_params_get", "log", "block"},
diff --git a/data/transactions/logic/evalStateful_test.go b/data/transactions/logic/evalStateful_test.go
index b0c6196e3..fe30d2594 100644
--- a/data/transactions/logic/evalStateful_test.go
+++ b/data/transactions/logic/evalStateful_test.go
@@ -3098,6 +3098,8 @@ func TestReturnTypes(t *testing.T) {
 		"err":    true,
 		"return": true,
 
+		// these have unusual input size requirements not encoded in proto
+		"falcon_verify":       true,
 		"ecdsa_pk_decompress": true,
 
 		"frame_dig":  true, // would need a "proto" subroutine
diff --git a/data/transactions/logic/opcodes.go b/data/transactions/logic/opcodes.go
index 650f26ed9..18af2af1b 100644
--- a/data/transactions/logic/opcodes.go
+++ b/data/transactions/logic/opcodes.go
@@ -77,6 +77,8 @@ const sharedResourcesVersion = 9 // apps can access resources from other transac
 const pairingVersion = 10 // bn256 opcodes. will add bls12-381, and unify the available opcodes.
 const spliceVersion = 10  // box splicing/resizing
 
+const spOpcodesVersion = 11 // falcon_verify, sumhash512
+
 // Unlimited Global Storage opcodes
 const boxVersion = 8 // box_*
 
@@ -503,9 +505,9 @@ var OpSpecs = []OpSpec{
 		is currently a useful pattern that requires hashes on long slices to
 		creating logicsigs in apps.
 
-		{0x01, "sha256", opSHA256, proto("b:b"), unlimitedStorage, costByLength(12, 6, 8)},
-		{0x02, "keccak256", opKeccak256, proto("b:b"), unlimitedStorage, costByLength(58, 4, 8)},
-		{0x03, "sha512_256", opSHA512_256, proto("b:b"), 7, unlimitedStorage, costByLength(17, 5, 8)},
+		{0x01, "sha256", opSHA256, proto("b:b"), ?, costByLength(...)},
+		{0x02, "keccak256", opKeccak256, proto("b:b"), ?, costByLength(...)},
+		{0x03, "sha512_256", opSHA512_256, proto("b:b"), ?, costByLength(...)},
 	*/
 
 	{0x04, "ed25519verify", opEd25519Verify, proto("b63:T"), 1, costly(1900).only(ModeSig)},
@@ -647,6 +649,8 @@ var OpSpecs = []OpSpec{
 	{0x83, "pushints", opPushInts, proto(":", "", "[N items]").stackExplain(opPushIntsStackChange), 8, constants(asmPushInts, checkIntImmArgs, "uint ...", immInts).typed(typePushInts).trust()},
 
 	{0x84, "ed25519verify_bare", opEd25519VerifyBare, proto("b63:T"), 7, costly(1900)},
+	{0x85, "falcon_verify", opFalconVerify, proto("bbb:T"), spOpcodesVersion, costly(1700)}, // dynamic for internal hash?
+	{0x86, "sumhash512", opSumhash512, proto("b:6"), spOpcodesVersion, costByLength(150, 7, 4, 0)},
 
 	// "Function oriented"
 	{0x88, "callsub", opCallSub, proto(":"), 4, detBranch()},
@@ -669,7 +673,7 @@ var OpSpecs = []OpSpec{
 	{0x97, "divw", opDivw, proto("iii:i"), 6, detDefault()},
 	{0x98, "sha3_256", opSHA3_256, proto("b:b"), 7, costly(130)},
 	/* Will end up following keccak256 -
-	{0x98, "sha3_256", opSHA3_256, proto("b:b"), unlimitedStorage, costByLength(58, 4, 8)},},
+	{0x98, "sha3_256", opSHA3_256, proto("b:b"), ?, costByLength(...)},},
 	*/
 
 	// Byteslice math.
diff --git a/data/transactions/logic/teal.tmLanguage.json b/data/transactions/logic/teal.tmLanguage.json
index e414922e8..915957f7f 100644
--- a/data/transactions/logic/teal.tmLanguage.json
+++ b/data/transactions/logic/teal.tmLanguage.json
@@ -76,7 +76,7 @@
         },
         {
           "name": "keyword.operator.teal",
-          "match": "^(\\!|\\!\\=|%|\u0026|\u0026\u0026|\\*|\\+|\\-|/|\\\u003c|\\\u003c\\=|\\=\\=|\\\u003e|\\\u003e\\=|\\^|addw|bitlen|btoi|divmodw|divw|exp|expw|itob|mulw|shl|shr|sqrt|\\||\\|\\||\\~|b\\!\\=|b%|b\\*|b\\+|b\\-|b/|b\\\u003c|b\\\u003c\\=|b\\=\\=|b\\\u003e|b\\\u003e\\=|bsqrt|b\u0026|b\\^|b\\||b\\~|base64_decode|concat|extract|extract3|extract_uint16|extract_uint32|extract_uint64|getbit|getbyte|json_ref|len|replace2|replace3|setbit|setbyte|substring|substring3|ec_add|ec_map_to|ec_multi_scalar_mul|ec_pairing_check|ec_scalar_mul|ec_subgroup_check|ecdsa_pk_decompress|ecdsa_pk_recover|ecdsa_verify|ed25519verify|ed25519verify_bare|keccak256|sha256|sha3_256|sha512_256|vrf_verify|gitxn|gitxna|gitxnas|itxn|itxn_begin|itxn_field|itxn_next|itxn_submit|itxna|itxnas)\\b"
+          "match": "^(\\!|\\!\\=|%|\u0026|\u0026\u0026|\\*|\\+|\\-|/|\\\u003c|\\\u003c\\=|\\=\\=|\\\u003e|\\\u003e\\=|\\^|addw|bitlen|btoi|divmodw|divw|exp|expw|itob|mulw|shl|shr|sqrt|\\||\\|\\||\\~|b\\!\\=|b%|b\\*|b\\+|b\\-|b/|b\\\u003c|b\\\u003c\\=|b\\=\\=|b\\\u003e|b\\\u003e\\=|bsqrt|b\u0026|b\\^|b\\||b\\~|base64_decode|concat|extract|extract3|extract_uint16|extract_uint32|extract_uint64|getbit|getbyte|json_ref|len|replace2|replace3|setbit|setbyte|substring|substring3|ec_add|ec_map_to|ec_multi_scalar_mul|ec_pairing_check|ec_scalar_mul|ec_subgroup_check|ecdsa_pk_decompress|ecdsa_pk_recover|ecdsa_verify|ed25519verify|ed25519verify_bare|falcon_verify|keccak256|sha256|sha3_256|sha512_256|sumhash512|vrf_verify|gitxn|gitxna|gitxnas|itxn|itxn_begin|itxn_field|itxn_next|itxn_submit|itxna|itxnas)\\b"
         }
       ]
     },