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.
During a contract creation, the transaction's data is executed; the output of this transaction is used as the contract's code in subsequent transactions. Here we see this process unfold. The Vyper special form lll ultimately performs a CODECOPY of the enclosing form and that code is then RETURNed in the final step.
NOTE: the remaining code is part of the deployed contract that will exist at PURITY_CHECKER_ADDR on chain.
109 ["mstore", 28, ["calldataload", 0]],
Store calldata[0] in memory position 28.
This form is to grab the "function selector" from the incoming message call. The way Vyper implements function selection is the same way it is performed in Solidity: you take the function's signature and calculate the SHA3 hash and take the first four bytes. Given that the EVM has a 32-byte word size and that the next block of code will overwrite bytes 5-32 of the word loaded by calldataload here, we end up with the first four bytes of the call data in memory[0:32].
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.
These are setup by the Vyper runtime to ensure some bounds checking for type safety. The constants are here: https://github.com/ethereum/vyper/blob/350679db9e67ce52e2bdbbf903ee70e60a4f8aba/vyper/utils.py#L97
These are added by the compiler here: https://github.com/ethereum/vyper/blob/350679db9e67ce52e2bdbbf903ee70e60a4f8aba/vyper/parser/parser.py#L276
submit takes an address as input and scans the bytecode at that address. If the purity checker doesn't find any evidence of impurity then it will store this address as "approved," which can be queried in the check function (below).
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> ...]).
We can verify that the given decimal number corresponds to our function selector algorithm mentioned previously.
sha3('submit(address)') -> 0xa1903eab == 2710585003
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>].
Vyper v0.0.4 doesn't allow for dynamic upper-bound on the number of rounds to execute this loop body as part of its security guarantees. We elect to just loop for the maximal number of times that is possible with a 32-byte word size 2**256-1. The first step in loop_body will be to break out of the loop if we have scanned the entirey of the bytecode at the input address.
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).
Given that the EVM has a 32-byte word size, we have to do a little math to grab just a byte -- we see this here by loading a full word and then taking that value modulo 256. The intuition here is that we can only represent a byte's worth of bits with 256 distinct symbols, i.e. 256 == 2^8.
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 to the dispatch_compound_sequences code and inspect the code at handle_push, which is executed if the opcode (_c) is a 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 function serves to calculate the beginning index in memory of a given "pusharg". Following the original Serpent code, we essentially have two memory regions for "working space" as we parse the input bytecode. We need this space to fully determine the purity as some opcodes can appear in either pure or impure contracts depending on context.
The first region is the ops array. When we encounter an opcode in the input bytecode, we copy it to this array in memory. The second region is the pushargs array; when we encounter a PUSH opcode in the input bytecode, we store its argument in this array.
Again following the Serpent code, an array of size N is implemented as a 32*N byte memory region to account for the EVM word size. The index_pushargs function here helps us perform this array indexing math to keep the rest of the LLL a bit more readable.
We see the beginning of the pushargs array in this function 352 + 33*_EXTCODESIZE and to that we add our index (time 32 to account for word size). As an example, to address pushargs[3] (which would be the argument to the 4th PUSH opcode in the input bytecode), we calculate the memory index at 352 + 33*_EXTCODESIZE + 32*3. This index specifies a 32-byte region in memory where this argument will reside as we continue to process the bytecode.
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"]]]],
The first thing to note is that _op is a counter we use that simply increments for each new opcode we encounter in the bytecode. We want to store the argument to our PUSH opcode in the pushargs array. So the use of index_pushargs gets us the approprite memory index into our array. The next form employs some math to account for the 32-byte word size and the fact that the argument to a PUSH opcode can be any number of bytes between 1 and 32. We grab the 32 bytes at the argument's position in the bytecode with the mload form and then divide out the part of the word we don't need based on the size of the arugment as derived from the opcode. This is what the exp form is doing.
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 from the ops array.
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 2nd 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 4th 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 2nd 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 2nd 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 2nd 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) in the ops array.
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 32-byte number which represents "check".
sha3('check(address)') -> 0xc23697a8 == 3258357672
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 that 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.