1

What is the shortest runtime bytecode you can write for a contract that satisfies both the following:

  • Accepts calldata of length 32 bytes representing one uint256 (no function selector)
  • Returns, as one uint256, the Fibonacci number at the index of the input (the sequence can start at either 0 or 1)

2 Answers 2

1

If this is a challenge, you should try to tackle it yourself. I understand that maybe you don't understand the problem well, and I will clarify it to you, then I will spell out the logic and then I'll show you a solution.

But when I clarify what you need to do, try to solve it yourself. If you can't, then check the logic I will show you. If you still can't figure it out, then check my solution:

Clarification

They want you to create a contract that has a function "with no function selector" (meaning, it's the fallback function). That function should receive calldata parameter of length 32 bytesthat will contain data that you need to treat as auint256number (by decoding it). Let's call this numbern`.

Then, you need to calculate the Fibonacci sequence up to that n number and return it.

As we know, the Fibonacci sequence is as follows:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The first is 0, the second is 1, the third is 1, and the fourth is 2. Basically, the Fibonacci sequence is a sequence of numbers where each number is composed of the sum of the previous 2 numbers, starting with 0, 1.

Compile it (maybe with Remix), take the runtime bytecode, and submit it.

Check the fallback function docs: https://docs.soliditylang.org/en/v0.8.14/contracts.html?highlight=fallback#fallback-function

Check the abi.encode, abi.encodePacked and abi.decode functions docs: https://docs.soliditylang.org/en/v0.8.15/units-and-global-variables.html?highlight=abi.decode#abi-encoding-and-decoding-functions

Think about it and try to solve it yourself now.

Logic

Implement the following fallback function:

js fallback(bytes calldata _input) external returns(bytes memory output)

Inside it, decode the _input as a uint256 type (the uint256 type has 32 bytes), in a variable called n.

Calculate the Fibonacci sequence up to n.

Return the result encoding it as bytes (with abi.encode or abi.encodePacked).

Compile it (maybe with Remix), take the runtime bytecode, and submit it.

That's it!

Try to solve it yourself.

If you can't, then take a look at my solution below.

Solution

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

contract Fibonacci {

    uint256 public input;
    uint256 public result;

    fallback(bytes calldata _input) external returns(bytes memory output) {

        (uint256 n) = abi.decode(_input, (uint256));

        uint256 v1 = 0;
        uint256 v2 = 1;
        for (uint256 i = 0; i < n - 1; i++) {
            v2 = v1 + v2;
            v1 = v2 - v1;
        }

        input = n; // No need to do this, just for debugging.
        result = v2; // No need to do this, just for debugging.

        // If called from another contract, the contract will receive this as the bytes response
        return abi.encode(v2);

    }

}

Compile it (maybe with Remix), take the runtime bytecode, and submit it. In my case, it's:

608060405234801561001057600080fd5b506004361061003a5760003560e01c806365372147146100df578063eaed3f4f146100fd5761003b565b5b6000366060600083838101906100519190610162565b90506000806001905060005b60018461006a91906101be565b8110156100a057818361007d91906101f2565b9150828261008b91906101be565b9250808061009890610226565b91505061005d565b508260008190555080600181905550806040516020016100c0919061027d565b6040516020818303038152906040529350505050915050805190602001f35b6100e761011b565b6040516100f4919061027d565b60405180910390f35b610105610121565b604051610112919061027d565b60405180910390f35b60015481565b60005481565b600080fd5b6000819050919050565b61013f8161012c565b811461014a57600080fd5b50565b60008135905061015c81610136565b92915050565b60006020828403121561017857610177610127565b5b60006101868482850161014d565b91505092915050565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052601160045260246000fd5b60006101c98261012c565b91506101d48361012c565b92508282039050818111156101ec576101eb61018f565b5b92915050565b60006101fd8261012c565b91506102088361012c565b92508282019050808211156102205761021f61018f565b5b92915050565b60006102318261012c565b91507fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff82036102635761026261018f565b5b600182019050919050565b6102778161012c565b82525050565b6000602082019050610292600083018461026e565b9291505056fea26469706673582212200a07d1acb375662d0b29a5f80dc05e9effdf73118008d05c193b7417094b1c8064736f6c63430008100033 In Remix, click on Compilation Details and click on Runtime Bytecode:

enter image description here

And get it:

enter image description here

There are many ways to solve the Fibonacci sequence. The solution that I used is very efficient in terms of time and space complexity. This solution uses little gas. Solving it with recursion in Solidity would be really gas expensive. You can try other solutions if you want.

6
  • 1
    What about if I want to find the shortest runtime bytecode? Sep 11, 2022 at 20:06
  • Try removing the state variables input and result. Sep 11, 2022 at 21:10
  • 1
    Okay, yes it helps. What about if I want to solve it with another method i.e., using the formula Fn = {[(√5 + 1) / 2] ^n} / √5 ? Could you please help me with this? Sep 12, 2022 at 6:26
  • 1
    Solidity does not support the square root math function natively yet. Implementing it would still use a loop too and that could be expensive anyways. But you could try it. Check this answer: ethereum.stackexchange.com/questions/2910/… Sep 12, 2022 at 13:14
  • 1
    This answer gives a runtime bytecode of 590 bytes. The question asks me for a runtime bytecode shorter than 50 bytes. Sep 13, 2022 at 17:36
0

Edit: I wrote a Medium article on this - containing the same (and more) information as my answer on your post, see https://medium.com/@annelohmeijer/develop-evm-assembly-opcode-logic-for-fibonacci-107f92dbc9d1

Approach

The approach here is to solve the problem by constructing the runtime bytecode yourself using opcodes (low-level language of a stack machine like the EVM). Writing an algorithm in Solidity or Yul and compile that is not going to give you a solution shorter than 50 bytes in length; an empty contract already compiles to a few hundred bytes. Writing an algorithm in pseudocode does help you though in order to identify what your opcode blocks should do.

This medium article is a great read on how to write opcodes from scratch and test and deploy them. The EVM playground is the best place to play around and to get familiar with opcodes, stack, memory, the EVM, etc.

Algorithm

Jeremy's answer already provide a great start: using the fallback function (since no function selector), and an algorithm to solve the problem. In similar pseudocode:

contract Fibonacci {
    fallback() payable external returns (bytes memory k) {
        initialize j = 0
        initialize k = 1
        for {i = 2, i <= n, i++}:
            m = k + j
            j = k
            k = m
       return k
    }

Now the challenge is: how do you translate this to opcodes?

Separate blocks

First split the function into manageable pieces that do a particular task:

  1. Load calldata n to the stack
  2. Initialize variables.
  3. Loop condition: determine if we need to execute the loop body. If n is 0 or 1, jump to return anchor. This is handled by instantiating i = 2.
  4. Loop body
    1. Increment counter i
    2. Execute body: Fibonacci logic
  5. Jump back to loop condition
  6. Return block

Then, piece by piece, develop the opcode logic that performs the task at hand. Just like Jeremy I recommend to try yourself. Start small: how do I pass calldata to the stack. How do I return data from the stack to the caller. Next: how do I create for-loop in opcodes that does nothing in the body. You get the drill. Using Excel to keep track of your work and adding an additional column with the content of the stack after each operation really helps (see below table).

Solution

When you have figured out how to construct the above opcode blocks separately, you can combine them and iterate to make sure that together the logic still checks out. In overview:

Opcode block Name Value Function Stack after operation
Load calldata PUSH1 0x00 Offset to load calldata [0]
CALLDATALOAD [n]
Prepare / initalize for loop PUSH1 0x01 Instantiate k = 1 [k][n]
PUSH1 0x00 Instantiate j = 0 [j][k][n]
SWAP2 [n][k][j]
PUSH1 0x02 Instantiate i = 2 [i][n][k][j]
Loop condition [loopcondition] JUMPDEST Check if we need to run the loop body
DUP2 Duplicate n [n][i][n][k][j]
DUP2 Duplicate i [i][n][i][n][k][j]
GT Check if i > n, if true jump to return block [0/1][i][n][k][j]
PUSH1 0x1c Add jump destination of return block [returnblock][0/1][i][n][k][j]
JUMPI
Loop body: increment counter PUSH1 0x01 Add increment for i [1][i][n][k][j]
ADD Increment i [i+1][n][k][j]
Loop body: Fibonacci SWAP2 Swap k with i [k][n][i+1][j]
DUP1 Duplicate k [k][k][n][i+1][j]
SWAP4 Swap k with j [j][k][n][i+1][k]
ADD Add k + j = k* [k*][n][i+1][k]
SWAP2 Swap k* with i [i+1][n][k*][k]
Jump back to loop condition PUSH1 0x0a Add jump destination of loop condition [loopcondition][i+1][n][k*][k]
JUMP
Return block [returnblock] JUMPDEST Jump destination for return block
POP Pop i off the stack [n][k*][k]
POP Pop n off the stack [k*][k]
PUSH1 0x00 MSTORE offset [0][k*][k]
MSTORE Store to be returned value in memory
PUSH1 0x20 Return size 32 bytes [20]
PUSH1 0x00 Return offset [0][20]
RETURN Return k* to caller

The bytecode representation of this solution is

600035600160009160025b818111601c576001019180930191600a565b505060005260206000f3

which is 39 bytes in length, satisfying your requirements. It's a valid solution for returning the Fibonacci number at index n, starting at index 1 (if you pass 0 as calldata - in hex padded to 32 bytes of course - then it returns 1, which is not correct). Paste it in the EVM playground and see for yourself.

Optimize

This is not the shortest possible runtime bytecode - for example one can easily get rid of the SWAP2 in the fifth instruction by changing the order of initializing the for-loop variables and loading call data - but I think it demonstrates how to get to a solution yourself. Hope this helps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.