Track 65,000 Tickets - Arrays in Algorand
Algorand only has native support for two types: unsigned integers and bytes. What happens though if you want to use arrays? You can use scratch space directly as an array, but it suffers from two fundamental issues:
- scratch space can only be used for temporary storage
- it is difficult to manage scratch space as slots may be used unknowingly.
In this tutorial, we are going to explore how we can utilize key-value pairs, bytes, and bits to create persistent arrays. We will do so by looking at four examples:
- string array using key-value pairs
- integer array using byte operators
- boolean array using bit operators
- boolean array using key-value pairs, byte operators, and bit operators.
The fourth example of storing booleans will show the power of arrays where you can go from storing 64 values to almost 65,000 in a smart contract’s global state. This can serve as inspiration for a ticketing system where these booleans can represent unsold/redeemed or bought tickets.
Python
Requirements
You will need the following:
- PyTeal Version 0.8.0
- Python 3. The scripts in the linked GitHub repo assumes the Python executable is called
python3. - The Algorand Node software. A private network is used, hence there is no need to sync up MainNet or TestNet.
goalis assumed to be in the PATH.
Background
As stated, Algorand only has native support for two types: unsigned integers and bytes. However, we have access to an in-built map for storing state in a smart contract, as well as byte operators and bit operators. We can make use of these to mimic the behavior of arrays. Let’s look into each in a bit more detail.
Map
Smart contracts in Algorand can store persistent state. The global state is limited to 64 key-value pairs and the combined size of the key and value must not exceed 128 bytes. To convert a map to an array, we can imagine the keys as the index into the array e.g. keys "0", "1", … etc.
Note: we will make use of a subroutine called convert_uint_to_bytes. All you need to know is that it takes in a uint and converts it to a string e.g. 28 to "28". If you are interested in the inner workings, you can check out its source code here.
Bytes
The plurality of bytes suggests that it can be viewed as an array of single byte values. Take for example the string Hello World!; we can interpret this as an array of 12 characters [H,e,l,l,o,,W,o,r,l,d,!]. Algorand has two opcodes: getbyte and setbyte which we can use to read and write to a specified index.
Bits
The plurality of bits suggests that it can be viewed as an array of single bit values. Take for example the uint 144; we can interpret this as an array of 8 bits [1,0,0,1,0,0,0,0]. Algorand has two opcodes: getbit and setbit which we can use to read and write to a specified index.
Steps
1. String array using key-value pairs
In this first example, we will create a string array using key-value pairs. The image below shows how this works; the keys are the index for the corresponding element in the array. Note global state keys cannot be of type uint so here we are using their bytes equivalent.
We have a smart contract that will store our array. It returns the following:
return Cond(
[Txn.on_completion() == OnComplete.DeleteApplication, Int(0)],
[Txn.on_completion() == OnComplete.UpdateApplication, Int(0)],
[Txn.on_completion() == OnComplete.CloseOut, Int(0)],
[Txn.on_completion() == OnComplete.OptIn, Int(0)],
# On app creation
[Txn.application_id() == Int(0), on_create],
# Must be a NoOp transaction
[Txn.application_args[0] == Bytes("set_string"), on_set_string],
[Txn.application_args[0] == Bytes("contains"), on_contains]
)
The above rejects all non NoOp transactions and accepts NoOp transactions when: the application is first created, set_string is passed, or when contains is passed. Let’s look at each of these.
Creation
On creation, we store the length of the array.
on_create = Seq([
App.globalPut(Bytes("length"), Txn.global_num_byte_slices()),
Int(1)
])
The length of the array is determined by how many global byteslices one specifies when creating the application:
goal app create --creator <ACCOUNT> --approval-prog <APPROVAL_PROG> --clear-prog <CLEAR_PROG> --global-byteslices <ARRAY_LENGTH> --global-ints 1 --local-byteslices 0 --local-ints 0
Set String
To set a string value, we pass an index into the array and the string we would like to store.
goal app call -f <ACCOUNT> --app-id <APP_ID> --app-arg "str:set_string" --app-arg "int:<INDEX>" --app-arg "str:<STRING_VALUE>"
We parse the arguments, assert that the index is not out of bounds and then store the string value at the correct index.
set_string_index = Btoi(Txn.application_args[1])
set_string_value = Txn.application_args[2]
on_set_string = Seq([
Assert(set_string_index < App.globalGet(Bytes("length"))),
App.globalPut(convert_uint_to_bytes(set_string_index), set_string_value),
Int(1)
])
Contains
The last utility function checks whether a given string is in the array. It can be called using
goal app call -f <ACCOUNT> --app-id <APP_ID> --app-arg "str:contains" --app-arg "str:<STRING_VALUE>"
We loop through the array, element by element, and compare whether the stored string is equal to the provided string. If we found a match, we break out the loop and return 1 for success.
searched_string_value = Txn.application_args[1]
found = ScratchVar(TealType.uint64)
i = ScratchVar(TealType.uint64)
length = ScratchVar(TealType.uint64)
key = ScratchVar(TealType.bytes)
cmp_string = App.globalGetEx(Int(0), key.load())
on_contains = Seq([
found.store(Int(0)),
length.store(App.globalGet(Bytes("length"))),
For(i.store(Int(0)), i.load() < length.load(), i.store(i.load() + Int(1))).Do(
Seq([
key.store(convert_uint_to_bytes(i.load())),
cmp_string,
If(
cmp_string.hasValue(),
If(
cmp_string.value() == searched_string_value,
Seq([
found.store(Int(1)),
Break(),
])
)
)
])
),
found.load()
])
2. Integer array using byte operators
In the second example, we will create an integer array using bytes. The image below shows how this works; we have a series of bytes and we interpret each byte as its own integer. The position of the byte is its index.
We have a smart contract that will store our array. It returns the following:
return Cond(
[Txn.on_completion() == OnComplete.DeleteApplication, Int(0)],
[Txn.on_completion() == OnComplete.UpdateApplication, Int(0)],
[Txn.on_completion() == OnComplete.CloseOut, Int(0)],
[Txn.on_completion() == OnComplete.OptIn, Int(0)],
# On app creation
[Txn.application_id() == Int(0), on_create],
# Must be a NoOp transaction
[Txn.application_args[0] == Bytes("set_int"), on_set_int],
[Txn.application_args[0] == Bytes("is_int_odd"), on_is_int_odd],
[Txn.application_args[0] == Bytes("is_sum_greater"), on_is_sum_greater]
)
The above rejects all non NoOp transactions and accepts NoOp transactions when: the application is first created, set_int is passed, is_int_odd is passed, or when is_sum_greater is passed. Let’s look at each of these.
Creation
On creation, we initialize the array:
on_create = Seq([
App.globalPut(
Bytes("array"),
Bytes("base16", "0x00000000000000000000")), # determines array length (10 bytes)
Int(1)
])
The length of the array is determined by how many bytes we initialize. In the above example, each hexadecimal digit is 4 bits or half a byte.
We run the following goal command:
goal app create --creator <ACCOUNT> --approval-prog <APPROVAL_PROG> --clear-prog <CLEAR_PROG> --global-byteslices 1 --global-ints 0 --local-byteslices 0 --local-ints 0
Set Int
To set an integer value, we pass an index into the array and the integer we would like to store.
goal app call -f <ACCOUNT> --app-id <APP_ID> --app-arg "str:set_int" --app-arg "int:<INDEX>" --app-arg "int:<INT_VALUE>"
We parse the arguments, and use SetByte which returns the new array but with the given value at the specified index. TEAL automatically checks if the byte index is out of bounds and that the value of the byte does not exceed 255 - if either of these occur then the transaction will be rejected.
set_int_index = Btoi(Txn.application_args[1])
set_int_value = Btoi(Txn.application_args[2])
on_set_int = Seq([
App.globalPut(
Bytes("array"),
SetByte(
array,
set_int_index,
set_int_value
)
),
Int(1)
])
Is Int Odd
To read an integer value, we can use the following goal command which includes an integer index:
goal app call -f <ACCOUNT> --app-id <APP_ID> --app-arg "str:is_int_odd" --app-arg "int:<INDEX>"
We can then get the corresponding byte and return 1 if and only if the stored value is odd.
int_odd_index = Btoi(Txn.application_args[1])
on_is_int_odd = GetByte(array, int_odd_index) % Int(2)
Is Sum Greater
The last utility function can be accessed using the following where we pass in a value that must be less than the sum of all the integers in the array:
goal app call -f <ACCOUNT> --app-id <APP_ID> --app-arg "str:is_sum_greater" --app-arg "int:<VALUE>"
We then loop through all the elements, continually adding to the total. If the total exceeds the provided value then the transaction succeeds.
is_sum_greater_value = Btoi(Txn.application_args[1])
array_stored = ScratchVar(TealType.bytes)
total = ScratchVar(TealType.uint64)
i = ScratchVar(TealType.uint64)
on_is_sum_greater = Seq([
array_stored.store(array),
total.store(Int(0)),
For(i.store(Int(0)), i.load() < Int(10), i.store(i.load() + Int(1))).Do(
total.store(total.load() + GetByte(array_stored.load(), i.load()))
),
total.load() > is_sum_greater_value
])
3. Boolean array using bit operators
In the third example, we will create a boolean array using bits. The image below shows how this works; the keys are the byte index for the corresponding element in the array. Note global state keys cannot be of type uint so here we are using their bytes equivalent.
We have a smart contract that will store our array. It returns the following:
return Cond(
[Txn.on_completion() == OnComplete.DeleteApplication, Int(0)],
[Txn.on_completion() == OnComplete.UpdateApplication, Int(0)],
[Txn.on_completion() == OnComplete.CloseOut, Int(0)],
[Txn.on_completion() == OnComplete.OptIn, Int(0)],
# On app creation
[Txn.application_id() == Int(0), on_create],
# Must be a NoOp transaction
[Txn.application_args[0] == Bytes("set_bool"), on_set_bool],
[Txn.application_args[0] == Bytes("get_bool"), on_get_bool]
)
The above rejects all non NoOp transactions and accepts NoOp transactions when: the application is first created, set_bool is passed, or when get_bool is passed. Let’s look at each of these.
Creation
On creation, we initialize the array:
on_create = Seq([
App.globalPut(Bytes("array"), Int(0)),
Int(1)
])
We run the following goal command:
goal app create --creator <ACCOUNT> --approval-prog <APPROVAL_PROG> --clear-prog <CLEAR_PROG> --global-byteslices 0 --global-ints 1 --local-byteslices 0 --local-ints 0
Set Boolean
To set a boolean value, we pass an index into the array and the integer we would like to store.
goal app call -f <ACCOUNT> --app-id <APP_ID> --app-arg "str:set_bool" --app-arg "int:<INDEX>" --app-arg "str:<BOOL_VALUE>"
We parse the arguments, and use SetBit which returns the new array but with the given boolean at the specified index. TEAL automatically checks if the bit index is out of bounds. We can convert the boolean value argument to 1/0 by checking if it is greater than 0.
set_bool_index = Btoi(Txn.application_args[1])
set_bool_value = Btoi(Txn.application_args[2]) > 0
on_set_int = Seq([
App.globalPut(
Bytes("array"),
SetBit(
array,
set_int_index,
set_int_value
)
),
Int(1)
])
Get Boolean
To get a boolean value, we just pass an index into the array.
goal app call -f <ACCOUNT> --app-id <APP_ID> --app-arg "str:get_bool" --app-arg "int:<INDEX>"
All we do is return the boolean value for the corresponding index argument. If the value is true then the transaction is approved, and if the boolean value is false it is rejected.
get_bool_index = Btoi(Txn.application_args[1])
on_get_bool = GetBit(App.globalGet(Bytes("array"), get_bool_index))
4. Boolean array using key-value pairs, byte operators and bit operators
In the last step, we will extend the previous example of booleans. In step 3, the array could only store a maximum of 8 boolean values; this will now become 64,592 boolean values. The image below shows how this works; we combine everything we have learnt: key-value pairs, bytes, and bits.
If you recall, in Algorand, key-value pairs must not exceed 128 bytes. If we use a single digit as our key, we have 127 bytes remaining and if we use two digits as our key, we have 126 bytes remaining. In the case of 127 bytes, we have space for 127 x 8 = 1016 bits and in the case of 126 bytes, we have 126 x 8 = 1008 bits. Therefore for the first 10 key-value pairs (from 0-9) we have space for 10,160 boolean values and for all key-value pairs (from 0-63) we have space for 64,592 boolean values.
Set or Get Boolean Value
A lot of the logic is shared between setting and getting boolean values.
We first store the index we would like to access:
index = ScratchVar(TealType.uint64)
store_index = index.store(Btoi(Txn.application_args[1]))
We then calculate the key, byte and bit indexes according to the logic above.
shifted_index = ScratchVar(TealType.uint64)
key = ScratchVar(TealType.uint64)
byte = ScratchVar(TealType.uint64)
bit = ScratchVar(TealType.uint64)
# NOTE: This logic can be optimized for opcode cost but left for readability
store_key_byte_bit = Cond(
[
index.load() < Int(10160), # key is 0-9
Seq([
key.store(index.load() / Int(1016)),
byte.store((index.load() % Int(1016)) / Int(8)),
bit.store((index.load() % Int(1016)) % Int(8))
])
],
[
index.load() < Int(64592), # key is 10-63
Seq([
shifted_index.store(index.load() - Int(10160)),
key.store(Int(10) + (shifted_index.load() / Int(1008))),
byte.store((shifted_index.load() % Int(1008)) / Int(8)),
bit.store((shifted_index.load() % Int(1008)) % Int(8))
])
]
)
We convert the key to its equivalent string representation. As stated above, if you would like to know how this subroutine works, check out the source code here.
key_as_string = ScratchVar(TealType.bytes)
key_as_string.store(convert_uint_to_bytes(key.load())),
An important point is that we lazily initialize the array. Smart contracts have an opcode cost limit of 700 so it would be far too expensive to initialize the array as a whole. Therefore we check whether the global state key has a value before setting or getting a boolean value within it, and if not, we initialize the array with either 127 or 126 bytes.
# initialize global state value with either 127 or 126 bytes depending on key length
initialize = If(
Not(key_has_value.hasValue()),
App.globalPut(
key_as_string.load(),
Cond(
[
index.load() < Int(10160), # key is 0-9
Bytes("base16", "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"),
],
[
index.load() < Int(64592), # key is 10-63
Bytes("base16", "0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")
]
)
)
)
Set Boolean
We can finally set the boolean value by combining what we have seen earlier. We get the key-value array, and then the byte within it, and then set a particular bit.
on_set_bool = Seq([
App.globalPut(
key_as_string.load(),
SetByte(
key_value,
byte.load(),
SetBit(
GetByte(key_value, byte.load()),
bit.load(),
bool_value
)
)
),
Int(1)
])
Get Boolean
We can finally get the boolean value by combining what we have seen earlier. We get the key-value array, and then the byte within it, and then the particular bit we want.
on_get_bool = GetBit(
GetByte(
key_value,
byte.load()
),
bit.load()
)
5. Conclusion
We have learned how we can use arrays in Algorand to persistently store strings, integers, and booleans. We do so by making use of key-value pairs, byte operators, and bit operators. In the end, we combined everything we learned to store close to 65,000 boolean values in a single smart contract, and we didn’t even make use of any local state! You can imagine something like this can be used for a ticketing system, where if an account purchases a ticket, their seat (index) is set to 1. When they enter the venue, they scan their ticket and their seat (index) is set to 0.
If you like, you can access all the source code for the examples here, as well as some bash scripts with the transactions already defined for you.