Could anyone help me with this Solidity Fibonacci challenge please?

Question

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)

Answer 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:

And get it:

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.

Answer 2

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.