Account message scheme

[martriay]

While prototyping the Account contract, I had to come up with a way to encode user intent in a verifiable way. This is, I needed to hash user messages in a way that could be validated by the Account contract before executing any transaction. And since Cairo's hash2 takes two parameters, I came up with a simple algorithm:

• Define a user message as <to, selector, calldata, account, nonce>. (account is needed to prevent replays accross accounts)
• "Fold" that tuple by hashing each component together with the hash of the previous components.

This is how the message hash looks today in python (from Signer.py):

def hash_message(to, selector, calldata, account_address, nonce):
    res = pedersen_hash(to, selector)
    res_calldata = hash_calldata(calldata)
    res = pedersen_hash(res, res_calldata)
    res = pedersen_hash(res, account_address)
    return pedersen_hash(res, nonce)


def hash_calldata(calldata):
    if len(calldata) == 0:
        return 0
    elif len(calldata) == 1:
        return calldata[0]
    else:
        return pedersen_hash(hash_calldata(calldata[1:]), calldata[0])

And this is how it's implemented on Cairo:

func hash_message{pedersen_ptr : HashBuiltin*}(message: Message*) -> (res: felt):
    alloc_locals
    let (res) = hash2{hash_ptr=pedersen_ptr}(message.to, message.selector)
    # we need to make `res` local
    # to prevent the reference from being revoked
    local res = res
    let (res_calldata) = hash_calldata(message.calldata, message.calldata_size)
    let (res) = hash2{hash_ptr=pedersen_ptr}(res, res_calldata)
    let (res) = hash2{hash_ptr=pedersen_ptr}(res, message.this)
    let (res) = hash2{hash_ptr=pedersen_ptr}(res, message.nonce)
    return (res=res)
end

func hash_calldata{pedersen_ptr: HashBuiltin*}(
        calldata: felt*,
        calldata_size: felt
    ) -> (res: felt):
    if calldata_size == 0:
        return (res=0)
    end

    if calldata_size == 1:
        return (res=[calldata])
    end

    let _calldata = [calldata]
    let (res) = hash_calldata(calldata + 1, calldata_size - 1)
    let (res) = hash2{hash_ptr=pedersen_ptr}(res, _calldata)
    return (res=res)
end

But...

While this seems to be good enough, I haven't thought thoroughly about it and there could be issues. It could be expensive, unsafe, hard to extend or generalize, or I don't know! What I do know is many projects are already relying on this implementation (e.g. Argent) so it makes sense to open the discussion around design of this critical piece of infrastructure.

So, what do you think?

[lior-stark]

I think this can work, but note that you have a Cairo module - starkware.Cairo.common.hash_state - that provides you with this functionality and faster.
It basically does an iterative loop for hashing all the elements.

[martriay]

Cool, thanks! For reference, this is the implementation. A couple questions

• Why is it faster?
• Is there a python or non-Cairo implementaiton as well?

[lior-stark]

It's faster because it's iterative and avoids the function call overhead.
It's basically tail recursion optimization done manually.
When I say "faster", it's less about time but rather the number of opcodes. Still, fewer function calls mean less call and return and, therefore, fewer operations.

I'm not sure about another similar implementation. Internally we do use hash chains, e.g., for calculating a transaction hash. But the implementation is very similar to what you wrote, so it's pretty much the same idea.

[martriay]

#37 :)

[juniset]

@martriay I personally think it would be more readable to pass the account, i.e. the from, as the first parameter to match the (from, to, data, ...) pattern.

[martriay]

from is a reserved keyword 😓 , what do you think about sender? or should we go for _from?

[martriay]

I liked sender better.

[fracek]

In my code I use postfix _ in these cases (when the word is a keyword), so I don't confuse it with other meanings of prefix _ (like private functions or storage variables). Sender is a better choice, o from_account.

[juniset]

I feel that sender could be confusing as on L1 it often refers to the EOA that initiated the transaction... a concept that does not exists with Account Abstraction. I think I would keep it simple and go for account.

[martriay]

to me the EOA that originates a tx is called origin, and sender is relative to a specific message. I can imagine an account that's not controlled by a public key (it may have a different mechanism to validate is_valid_signature) and it's not the one originating the tx either but it is the sender.

[janek26]

Hey @martriay
maybe we should implement it the same way as in https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/cairo/common/hash_state.py :)

I think one unexpected result from your hash function is:

hash_calldata([12]) == 12

where as I'd expect a function called hashSomething to return a hash (in any case)

hash_state has also the advantage of already being implemented in python and Cairo.

hash_message would then look like this: (from https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/services/api/gateway/transaction_hash.py#L44)

def hash_message(to, selector, calldata, account_address, nonce):
    calldata_hash = compute_hash_on_elements(calldata)
    return compute_hash_on_elements([to, selector, calldata_hash, account_address,  nonce])

[martriay]

Indeed! there's an issue for that #37 :)

[juniset]

Implemented in [#49].