fix(protocol): Replace LibEthDeposit assembly

[adaki2004]

David asked me today to help investigate why the depositsRoot he calculates (seemingly from same test data) within the golang code does not match the one with the solidity calculates.

After investigation / debugging, the assembly code turned out to be the issue, because the underlying array of struct EthDeposit within a struct State is not stored on a continuous memory location but with the help of pointers rather.

(If it would have been stored on a continuous location, the assembly would have been wrong anyways, because the first 32 bytes is reserved for the length of the array which should have been chopped).

(If anyone wants to debug how the continuous memory area of the 33-byte-long depossitsProcessed variable look like feel free to put this into LibEthDepositing.sol and debug print the value).

bytes memory result = new bytes(33 * 32); // allocate 33*32 bytes
assembly {
            for {let i := 0} lt(i, 34) {i := add(i, 1)} {
                let memLocation := add(depositsProcessed, mul(i, 32)) // calculate the memory location
                let value := mload(memLocation) // load the data from memory which is the memory location of the address (but not the deposit amount)
                mstore(add(result, add(32, mul(i, 32))), value) // store the data in the result variable
             }
        }

@davidtaikocha :
To help you visualizing the encoding this is how the test data looks (in test_deposit_hash_creation test):

0xa9bcf99f5eb19277f48b71f9b14f5960aea58a89000000000de0b6b3a7640000200708d76eb1b69761c23821809d53f65049939e000000001bc16d674ec80000300c9b60e19634e12fc6d68b7fea7bfb26c2e4190000000029a2241af62c0000400147c0eb43d8d71b2b03037bb7b31f8f78ef5f000000003782dace9d90000050081b12838240b1ba02b3177153bca678a86078000000004563918244f40000430c9b60e19634e12fc6d68b7fea7bfb26c2e4190000000053444835ec580000520147c0eb43d8d71b2b03037bb7b31f8f78ef5f000000006124fee993bc000061081b12838240b1ba02b3177153bca678a86078000000006f05b59d3b200000

[Brechtpd]

After investigation / debugging, the assembly code turned out to be the issue, because the underlying array of struct EthDeposit within a struct State is not stored on a continuous memory location but with the help of pointers rather.

Huh I think it should be stored as a continuous chunk of memory! Or at least I remember it always being like that. But yeah, EthDeposit is only stored compactly in storage, never in memory so that's indeed something that needed to be taken into account with the previous solution (64 bytes in memory vs 32 bytes in storage). Also the off by one error on j.

This is the layout in memory I would have expected (in continuous chunk):
| length (32 bytes) | recipient_0 (32 bytes) | amount_0 (32 bytes) | recipient_1 (32 bytes) | amount_1 (32 bytes) | ....

So in case there is at least 8 deposits to be processed (in our case it's indeed 8 person's deposits), the length of this array is 32+1, encoded as you could see above, 1 struct element = 32 bytes and continuously packed.

Length of the array is 8+1?

[adaki2004]

This is the layout in memory I would have expected (in continuous chunk):
| length (32 bytes) | recipient_0 (32 bytes) | amount_0 (32 bytes) | recipient_1 (32 bytes) | amount_1 (32 bytes) | ....

Solidity
Note how in all the functions, a struct type is assigned to a local variable with data location storage. This does not copy the struct but only stores a reference

Length of the array is 8+1?

Nah, ignore it please (i put back the assembly resizing).

[Brechtpd]

Solidity Note how in all the functions, a struct type is assigned to a local variable with data location storage. This does not copy the struct but only stores a reference

This seems to be talking about storage, not memory?

[cyberhorsey]

I am not sure this is producing the correct hash?
https://emn178.github.io/online-tools/keccak_256.html
paste in the data from the topic above that Dani posted:

a9bcf99f5eb19277f48b71f9b14f5960aea58a89000000000de0b6b3a7640000200708d76eb1b69761c23821809d53f65049939e000000001bc16d674ec80000300c9b60e19634e12fc6d68b7fea7bfb26c2e4190000000029a2241af62c0000400147c0eb43d8d71b2b03037bb7b31f8f78ef5f000000003782dace9d90000050081b12838240b1ba02b3177153bca678a86078000000004563918244f40000430c9b60e19634e12fc6d68b7fea7bfb26c2e4190000000053444835ec580000520147c0eb43d8d71b2b03037bb7b31f8f78ef5f000000006124fee993bc000061081b12838240b1ba02b3177153bca678a86078000000006f05b59d3b200000

and select "hex", to receive hash:
8117066d69ff650d78f0d7383a10cc802c2b8c0eedd932d70994252e2438c636

which is the same as this Go code produces:

func CalcWithdrawalsRootTaiko(withdrawals []*Withdrawal) common.Hash {
	// only process withdrawals/deposits of 8 minimum
	if len(withdrawals) < 8 {
		return EmptyWithdrawalsHash
	}

	var b []byte

	for _, withdrawal := range withdrawals {
		// uint96 solidity type needs us to make 12 length byte slice and put
		// the uint64 into the last 8 bytes. solidity is also bigendian by
		// default so we need to be specific.
		amountBytes := make([]byte, 12)
		binary.BigEndian.PutUint64(amountBytes[4:], withdrawal.Amount)

		b = bytes.Join([][]byte{b, withdrawal.Address.Bytes(), amountBytes}, nil)
	}

	return crypto.Keccak256Hash(b)
}

output:
actual  : 0x8117066d69ff650d78f0d7383a10cc802c2b8c0eedd932d70994252e2438c636

but the tests here indicate the correct Solidity hash is 0xcfa788c68a55976de9ba9fbab4038b8ddacedb45242ff4380163cd661d0e873f.

I have a feeling it's hashing the bytes directly not as hash, so 0x is included in the hash and not discarded, which I'll try to implement in Go to see.

I'm not too well versed in the under the hood mechanism of solidity's keccak256, but is it hashing it as a non-hex string, and non-text, and thats the issue?

@Brechtpd you probably know the answer here : ).

EDIT:

Christ, there was another push a few minutes ago that produces the same hash. Lol. It was incorrect before, now it produces the same 811 hash. The assembly resizing fixes the protocol code to produce correct hash.

[cyberhorsey]

corresponding taiko-geth PR:
taikoxyz/taiko-geth#76

[dantaik]

The previous hashing of depositsProcessed is buggy, but I think it can get fixed simply using:

 depositsRoot := keccak256(add(depositsProcessed, 32), mul(j, 32))

[dantaik]

I think maybe the expected value in the test (0x8117066d69ff650d78f0d7383a10cc802c2b8c0eedd932d70994252e2438c636) is also calculated wrong. How is it calculated exactly, better to calculate the hash inside the test.

[adaki2004]

No you cannot calculate the has this way - indeed we need to chop the first 32 bytes because that’s the lenght, but the rest is just a pointer.
Then if you dump the data stired on that pointer is the address, and where the amount stored is somewhere else (maybe next bytes32 - but then it’s too complex to donwith assembly.I spent yestarrday 6 hours debugging assembly content i can try to make it somehow work with assembly but i dont know …

[cyberhorsey]

There is a PR for the looping being done in assembly and keccak256 being done outside here Dani: https://github.com/taikoxyz/taiko-mono/pull/13782/files

Much less readable but saves some gas

[adaki2004]

Solidity Note how in all the functions, a struct type is assigned to a local variable with data location storage. This does not copy the struct but only stores a reference

This seems to be talking about storage, not memory?

with data location storage and we did thihs in the code TaikoData.EthDeposit storage deposit = state.ethDeposits[i]; which then copying to local.. So i guess this applies here as well. (Or at least seems).

[Brechtpd]

Seems like the memory array does indeed store relative offsets to the struct locations! Looks like I remembered wrongly or I just never did this with structs which are different (or solidity now does it differently, I remember them not wanting people to depend on how things are stored in memory because it could change).

I don't think anything storage is related to what we do here because we copy the basic types over to the memory array, which are actual copies.

We could simply skip over the offsets because solidity should always just put the array elements in a continuous chunk after the relative offsets (which is why I don't really understand why it's done this way for memory, maybe it helps minimize the difference with abi encoded calldata). But for what we do here that doesn't solve the issue completely anyway because we want to pack the data tighter than it is stored in memory.

[adaki2004]

I also tried to play around with it a little bit and see what’s on those memory locations.
Addresses were sitting there but i had no ‘luck’ finding the corresponding deposited amount ( 32bytes distance before/after just 0x00 bytes) so it definitely made me curious.

[Brechtpd]

Oh it stores the absolute memory addresses to the struct in the array, not the relative offsets. Okay so then I guess the advantage is cheaper copies and stuff. So the structs are put linearly in memory with padding to 32 byte for its members, with the array storing absolute offsets to those structs.

[adaki2004]

I dumped what's on that absolute address - +before and after (except for the first address):

0x000000000000000000000000a9bcf99f5eb19277f48b71f9b14f5960aea58a890000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200708d76eb1b69761c23821809d53f65049939e0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000300c9b60e19634e12fc6d68b7fea7bfb26c2e4190000000000000000000000000000000000000000000000000000000000000000000000000000000000000000400147c0eb43d8d71b2b03037bb7b31f8f78ef5f000000000000000000000000000000000000000000000000000000000000000000000000000000000000000050081b12838240b1ba02b3177153bca678a860780000000000000000000000000000000000000000000000000000000000000000000000000000000000000000430c9b60e19634e12fc6d68b7fea7bfb26c2e4190000000000000000000000000000000000000000000000000000000000000000000000000000000000000000520147c0eb43d8d71b2b03037bb7b31f8f78ef5f000000000000000000000000000000000000000000000000000000000000000000000000000000000000000061081b12838240b1ba02b3177153bca678a860780000000000000000000000000000000000000000000000000000000000000000

You could see they are the addresses from the tests - but where are the deposited amounts.. ? :)

[Brechtpd]

I didn't test anything in the codebase, just wrote some test code and ran in it remix which seems to work as expected:

struct EthDeposit {
    address recipient;
    uint96 amount;
}

function getValue(uint slot, uint offset) public pure returns (uint) {
    EthDeposit[] memory depositsProcessed = new EthDeposit[](3);

    depositsProcessed[0].recipient = address(1);
    depositsProcessed[0].amount = uint96(2);
    depositsProcessed[1].recipient = address(3);
    depositsProcessed[1].amount = uint96(4);
    depositsProcessed[2].recipient = address(5);
    depositsProcessed[2].amount = uint96(6);

    return loadMemoryValue(depositsProcessed, slot, offset);
}

function loadMemorySlot(EthDeposit[] memory depositsProcessed, uint offset) private pure returns (uint value) {
    assembly {
        value := mload(add(depositsProcessed, mul(offset, 32)))
    }
}

function loadMemoryValue(EthDeposit[] memory depositsProcessed, uint slot, uint v) private pure returns (uint value) {
    uint offset = loadMemorySlot(depositsProcessed, slot);
    assembly {
        value := mload(add(offset, mul(v, 32)))
    }
}

e.g. getValue(1, 1) returns depositsProcessed[0].amount which is 2 as expected.

[adaki2004]

Yes, i tested it in remix yesterday as well (not exactly sure if the exact same way) but canot reproduce it.
Also there are some differences within this and the codebase.

• how the local variable initialized (config val + 1) vs constant
• That object is filled by storage copy
• In the code the state var is a struct array within a struct
  (Im not able to test atm bc not at PC, but for now i guess it’s fine, since we have a solution but still interesting.)