WARNING: These are notes and are not complete, they may contain errors. They certainly contain awkward language (sorry).
These are my notes from reading the Casper LLL Purity Checker currently being reviewed here: ethereum/casper#143
Specifically, the casper/contracts/purity_checker.py file.
104 ["seq",
105 ["return",
106 0,
107 ["lll",
108 ["seq",
Preamble to deploy the code.
109 ["mstore", 28, ["calldataload", 0]],
Store calldata[0] in memory position 28.
110 ["mstore", 32, 1461501637330902918203684832716283019655932542976],
111 ["mstore", 64, 170141183460469231731687303715884105727],
112 ["mstore", 96, -170141183460469231731687303715884105728],
113 ["mstore", 128, 1701411834604692317316873037158841057270000000000],
114 ["mstore", 160, -1701411834604692317316873037158841057280000000000],
Store some special numbers for later use. In respective order:
- Largest possible Ethereum address (0xFFFF...) represented in decimal. Also can be expressed as
16^40. - 2^127 ???
- -2^127 ???
- ???
- ???
TODO: what are these numbers?
115 ["if",
116 ["eq", ["mload", 0], 2710585003], # submit
117 ["seq",
Check to see if memory[0] represents the submit() function. If so, start a new sequence of expressions using seq. Seq takes zero or more expressions and executes them in sequence (['seq', <expr>, <expr> ...]).
TODO: Confirm number is ABI sig.
118 ["calldatacopy", 320, 4, 32],
119 ["assert", ["iszero", "callvalue"]],
Copy the address (as a 32 byte word) from calldata[4] to memory[320]. Then, assert that there was no wei sent with this transaction (callvalue == 0).
120 ["uclamplt", ["calldataload", 4], ["mload", 32]], # checking address input
Here, a "clamp" is performed (specifically, an "unsigned clamp less than"). A uclamplt takes an unsigned value and a ceiling value: [uclamplt, <value>, <ceil>]. If <value> is greater than <ceil>, the call will revert.
In effect, this clamp causes the call to revert if the supplied address (calldata[4]) is invalid because it is too large. The number stored at memory[32] represents the largest possible Ethereum address.
121 # scan bytecode at address input
122 ["with", "_EXTCODESIZE", ["extcodesize", ["mload", 320]], # addr
123 ["if", ["eq", "_EXTCODESIZE", 0],
124 "invalid", # ban accounts with no code
Now, we declare _EXTCODESIZE to be the length of the code at the specified address (stored in memory[320]). Then, if the length of the code is zero, cause a revert by using the INVALID opcode.
In effect, this revert means that an address without code can never be considered pure. This is sensible because it is possible for someone to deploy impure code to an externally owned account at any time.
125 ["seq",
126 ["extcodecopy", ["mload", 320], 352, 0, "_EXTCODESIZE"],
127 ["with", "_i", ["add", 352, ["mul", 65, "_EXTCODESIZE"]],
128 ["with", "_op", 0,
129 ["repeat", "_i", 0,
130 115792089237316195423570985008687907853269984665640564039457584007913129639935,
131 loop_body]]]]]],
We begin a new sequence of operations (seq):
- Copy the code (all bytes from
0to_EXTCODESIZE) from the specified address (address ismemory[320]) tomemory[352]. In effect, storing the code of the external contract in our memory. - Declare
_iand set it to_EXTCODESIZE * 65. This is thememorylocation where therepeatloop iterator will be stored. - Declare
_opand set it to0. - Start a
repeatoperation, which will execute the code stored in theloop_bodyvariable. An LLLrepeatstatement has the following signature:[repeat, <index_memloc>, <startval>, <rounds>, <body>].
Now we will move onto the code stored at the loop_body variable. It's important to remember here that we're dealing with a Python script which generates LLL code --- the loop_body variable will not exist in the final LLL code, instead it will just be the value of that variable (which is LLL code).
97 loop_body = ["if",
98 ["ge", ["mload", "_i"], "_EXTCODESIZE"],
99 "break",
100 ["with", "_c", ["mod", ["mload", ["add", 352, ["sub", ["mload", "_i"], 31]]], 256],
101 process_byte]]
First, we check to see if our loop index (_i) is greater than or equal to (ge) the length of the contract code we're checking. If so, we break the loop and assume the code is pure (this is covered later in this article).
If we aren't finished checking this code, we declare _c to equal the _i'th byte of the contract code, and then we execute the process_byte code (we jump to that next).
TODO: Figure out what that with statement does...
91 process_byte = ["seq",
92 invalid_if_banned,
The first thing in process_byte, is to execute the invalid_if_banned code. We jump to that now.
19 invalid_if_banned = ["if",
20 # sum([2**x for x in [0x31, 0x32, 0x33, 0x3a, 0x3b, 0x3c, 0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f, 0x54, 0x55, 0xf0, 0xff]])
21 ["and", 57897811465722876096115075801844696845150819816717216876035649536196444422144,
22 ["exp", 2, "_c"]],
23 "invalid"]
We now check the current code byte (_c) against a list of invalid opcodes. The list of invalid opcodes is embodied in the 57897... integer as a bitmap. This bitmap can exist because opcodes are 1 byte, which means there can only be 256 different opcodes. Therefore, you can use each of the 256 bits in a uint256 to represent an single opcode. Opcodes are represented in the bitmap as 2**<opcode>, and we can see that this operation is applied to _c on line 22. As an example, the SUB opcode (0x03) is mapped to the 4th bit, because bin(2**3) = 0b1000.
If the comparision is non-zero, it means that the _c opcode is in the set of invalid opcodes and the contract reverts using the invalid opcode. If the opcode is not in the set of invalid opcodes, we move onto the dispatch_compound_sequences code.
86 dispatch_compound_sequences = ["if", is_push,
87 handle_push,
88 ["if", is_some_call,
89 handle_some_call]]
First, we are redirected to is_push code.
25 is_push = ["and", ["le", 0x60, "_c"], ["le", "_c", 0x7f]]
The is_push code returns true if the opcode (_c) is inside of 0x60 to 0x7f, which are the PUSH1, PUSH2 ... PUSH32 opcodes. In effect, asking "is this a PUSH opcode?"
Now, lets go dispatch_compound_sequences code and inspect the code at handle_push, which is executed if the opcode (_c) is push opcode.
30 handle_push = ["seq",
31 ["mstore", index_pushargs("_op"), ["div", ["mload", ["add", ["add", 352, ["mload", "_i"]], 1]], ["exp", 256, ["sub", 0x7f, "_c"]]]],
32 ["mstore", "_i", ["add", ["sub", "_c", 0x5f], ["mload", "_i"]]]] # there is an extra -1 in here to account for the increment of the repeat loop; -0x5e ~> -0x5f from the serpent code
Now, we start a new sequence of expressions (seq). First up is an mstore to a location defined by the index_pushargs() function. Lets look at that function.
27 def index_pushargs(index):
28 return ["add", ["add", 352, ["mul", 33, "_EXTCODESIZE"]], ["mul", 32, index]]
This code returns a memory location, which starts 33 * _EXTCODESIZE after where the code is stored (memory[252]). index is multiplied by 32 to ensure there is enough space to fit 32 values, which may follow a PUSH32 opcode. You can imagine this memory map as an opcode followed by 32 spare bytes, follwed by another opcode and 32 spare bytes, and so on.
The ultimate purpose of this memory map is to make it easy to go an select the n'th opcode (and potentially read its arguments). Such an exercise is not trival given just the raw byte code because its unknown wether byte_code[n] is an opcode or an argument to an opcode (viz., byte_code[n] is not necessarily equal to opcode[n]).
Ok, back to the handle_push code. Looking at line 31, we now know that we're storing something at a memory location defined by index_pushargs(). Let's examine what is being stored.
31 ["mstore", index_pushargs("_op"), ["div", ["mload", ["add", ["add", 352, ["mload", "_i"]], 1]], ["exp", 256, ["sub", 0x7f, "_c"]]]],
TODO: How does this work?
Ok, back to the next line (line 32) of handle_push.
32 ["mstore", "_i", ["add", ["sub", "_c", 0x5f], ["mload", "_i"]]]] # there is an extra -1 in here to account for the increment of the repeat loop; -0x5e ~> -0x5f from the serpent code
Here we skip _i forward however many bytes were PUSHed. For example, lets consider PUSH32 (0x7f): 0x7F - 0x5f = 0x20 = 32, therefore we skip forward 32 bytes.
Now we know that a PUSH is handled by storing the PUSHed values somewhere safe, then incrementing _i past whatever values were PUSHed. Let's move on to line 88, where things which are not pushes are handled.
88 ["if", is_some_call,
89 handle_some_call]]
The condition of the if statement is the value of the is_some_call Python variable. Let's go to it.
34 is_some_call = ["or", ["eq", "_c", 0xf1],
35 ["or", ["eq", "_c", 0xf2], ["eq", "_c", 0xf4]]]
Here, we do a pretty simple or sequence which returns true if the opcode (_c) is one of the following:
- CALL (
0xf1), or, - CALLCODE (
0xf2), or, - DELEGATECALL (
0xf4).
If the opcode (_c) is not one of these call-type opcodes, the contract is deemed to be pure. Otherwise, the handle_some_call code is executed. We will continue down the impure path and examine handle_some_call.
81 handle_some_call = ["with", "_address_entry", 0,
82 ["seq",
83 find_address,
84 filter_address_usage]]
First, _address_entry is declared and set to zero. Then, a new sequence starts which first runs the code in the find_address Python variable. The find_address code relies upon the index_ops() function, so we're going to look at that first, then get stuck into find_address.
37 def index_ops(index):
38 return ["add", ["add", 352, "_EXTCODESIZE"], ["mul", 32, index]]
index_ops contains code which returns a memory address for the n'th opcode (specified as index). For example, index_ops(10) would return the memory address for the 10th opcode.
Recall the difference between byte_code[n] and an opcode[n], as discussed when examining the index_pushargs() function.
Now we're going to get into the find_address code, which is a series of nested if statements which form a whitelist of acceptable sequences preceeding a call-type opcode.
40 find_address = ["if", ["and", ["ge", "_op", 2],
41 ["and", ["ge", ["mload", index_ops(["sub", "_op", 1])], 0x60],
42 ["le", ["mload", index_ops(["sub", "_op", 1])], 0x7f]]],
43 ["set", "_address_entry", ["sub", "_op", 2]],
find_address starts with an if statement which returns true if:
- We have passed the 3rd opcode, and,
- the previous opcode was greater or equal to
0x60(PUSH1), and, - the previous opcode was less than or equal to
0x7f(PUSH32).
In effect, the statement asks "did we push some stuff onto the stack just before this call-type opcode?" If so, we assume that an address must have been declared two bytecode bytes ago, so we store _op - 2 as _address_entry and then drop into filter_address_usage. However, we will get to that later and keep looking at find_address.
44 ["if",
45 ["and", ["ge", "_op", 4],
46 ["and", ["eq", ["mload", index_ops(["sub", "_op", 1])], 0x03],
47 ["and", ["eq",
48 ["mload", index_ops(["sub", "_op", 2])], 0x5a],
49 ["and", ["ge",
50 ["mload", index_ops(["sub", "_op", 3])], 0x60],
51 ["le",
52 ["mload", index_ops(["sub", "_op", 3])], 0x7f]]]]],
53 ["set", "_address_entry", ["sub", "_op", 4]],
Here we have an if statement which returns true if:
- We have passed the 5th opcode in the entire code, and,
- the previous opcode was SUB (
0x03), and, - the opcode before SUB was GAS (
0x5a), and, - the opcode before GAS was greater than or equal to PUSH1 (
0x60), and, - the opcode before GAS was less than or equal to PUSH32 (
0x7f).
In effect, the statement asks "were the last three opcodes subtracting something from the gas sent to the transaction?" If so, we assume that the address must have been declared four bytecode bytes ago and store _op - 4 as _address_entry and drop into filter_address_usage. As before, we continue with find_address for now.
54 ["if", ["and", ["ge", "_op", 2],
55 ["eq",
56 ["mload", index_ops(["sub", "_op", 1])], 0x5a]],
57 ["set", "_address_entry", ["sub", "_op", 2]],
Here we have an if statement which returns true if:
- We are past the 3rd opcode in the entire code, and,
- the previous opcode was GAS (
0x5a).
In effect, the statement asks "was the previous opcode pushing the entire amount of gas onto the stack?" If so, it is assumed that the address was specified two bytecode bytes ago so, therefore _address_entry is set to _op - 2 and we drop into filter_address_usage. As is tradition, we continue with find_address for now.
58 ["if", ["and", ["ge", "_op", 2],
59 ["eq",
60 ["mload", index_ops(["sub", "_op", 1])], 0x90]],
61 ["set", "_address_entry", ["sub", "_op", 2]],
Here we have an if statement which returns true if:
- We are past the 3rd opcode, and,
- the previous opcode was SWAP1 (
0x90).
In effect, the statement asks "was the last thing we did swapping the top two elements on the stack?" If so, it is assumed the address was specified two bytecode bytes ago, so we set _address_entry to _op - 2 and drop into filter_address_usage. For the very last time, we continue with find_address for now.
62 ["if", ["and", ["ge", "_op", 2],
63 ["and", ["ge",
64 ["mload", index_ops(["sub", "_op", 1])], 0x80],
65 ["lt",
66 ["mload", index_ops(["sub", "_op", 1])], 0x90]]],
67 ["set", "_address_entry", ["sub", "_op", 2]],
68 "invalid"]]]]]
The very last if statement of find_address returns true if:
- We are past the 3rd opcode, and,
- the previous opcode was greater than or equal to DUP1 (
0x80), and - the previous opcode was less than SWAP1 (
0x90). (Note: SWAP1 is the next opcode after DUP16)
In effect, the statement asks "was the last thing we did duplicating some itmes on the stack?" If so, we assume that the address must have been specified two bytecode bytes ago, so we set _address_entry to _op - 2 and drop into filter_address_usage.
If none of these previous five if statements were fulfilled, we revert using the INVALID opcode. In effect, we whitelist the operations which may happen before a call-type opcode.
Now we're (finally) done with find_address we're going to examine filter_address_usage, which is the code which executes next.
70 filter_address_usage = ["if", ["sload", ["add", ["sha3_32", 0], # self.approved_addrs
71 ["mload", index_pushargs("_address_entry")]]],
72 ["seq"],
73 ["if", ["eq",
74 ["mload", index_ops("_address_entry")], 0x30],
75 ["seq"],
76 ["if", ["eq",
77 ["mload", index_ops("_address_entry")], 0x60],
78 ["seq"],
79 "invalid"]]]
First, we start with an if statement which tests to see if the _address_entry is a pre-approved address. The scheme sha3_32(0) + address is used to determine a memory address which, if it stores a 1, indicates that the address has been approved. If this is the case an empty seq is used to continue code execution.
If the address wasn't approved, we check to see if what we thought was the address is actually an ADDRESS (0x30) or PUSH1 (0x60) opcode.
If _address_entry is not a pre-approved address or one of the above two opcodes, a revert is caused with the INVALID opcode. The above two opcodes are accepted because ADDRESS represents the address of the contract being tested, and using it would just be harmless recursion. PUSH1 is permitted because it only permits a single byte and addresses below 256 are designated for precompiles.
Now we have finished with the dispatch_compound_sequences code we can continue with the next lines of the process_byte code.
94 ["mstore", ["add", ["add", 352, "_EXTCODESIZE"], ["mul", 32, "_op"]], "_c"],
95 ["set", "_op", ["add", "_op", 1]]]
First, we store the opcode we were working on (_c) at the a memory location. The memory location is after the code (352:_EXTCODESIZE) and each opcode has 32 words following it (to allow for PUSH values).
Then, we increment our opcode counter (_op) and start the process all over again!
So, now we have covered the process_byte and loop_body code, we can drop back into the main purity_checker_lll code which only executes if no impurity was detected (i.e., the contract code was pure).
132 # approve the address `addr`
133 ["sstore", ["add", ["sha3_32", 0], ["mload", 320]], 1],
134 ["mstore", 0, 1],
135 ["return", 0, 32],
136 "stop"]],
First, we mark this contract address as "approved" by storing a 1 in the storage that is sha3_32(0) + address. Then, return 1 to the caller (by storing 1 in memory[0] and returning all 32 bytes of memory[0]). Yay! We just approved a contract as "pure".
We're not done yet though, we still need to go over the "check" functionality. This should be easy, given what we already know.
137 ["if",
138 ["eq", ["mload", 0], 3258357672], # check
First, we check to see if memory[0] holds the number which represents "submit".
TODO: figure out how this number represents submit.
139 ["seq",
140 ["calldatacopy", 320, 4, 32],
141 ["assert", ["iszero", "callvalue"]],
142 ["uclamplt", ["calldataload", 4], ["mload", 32]], # checking address input
Then, we begin a sequence (seq) which first copies the address (as a 32 byte word) from calldata[4] to memory[320]. Then, we assert that no wei was sent with the transaction (callvalue == 0) and throw if the address supplied is too large to be an Ethereum address (by comparing it to the number we stored earlier in memory[32]).
143 ["mstore", 0, ["sload", ["add", ["sha3_32", 0], ["mload", 320]]]],
144 ["return", 0, 32],
145 "stop"]]],
Now the transaction and address are sanity checked, we read from the storage location defined by sha3_32(0) + address into memory[0], then return all 32 bytes of memory[0]. In effect, this returns a 1 or 0 which indicates, respectively, whether or not the supplied address has been approved as pure.