Runtime sha256 should work for arbitrary strings even with length >= 128

[anton-trunov]

sha256 at run-time uses the SHA256U TVM instruction, which only works with data with up to 1023 bits, so strings of length 128 bytes basically get truncated. This is confusing for smart-contract authors because it breaks the abstraction of the String type. Since we allow strings with more than 127 characters, those sha256 should work on those.

See also, #1085

[novusnota]

The statically known strings is one story, where we can accurately compute their hashes with sha256_sync() no matter their length. And FunC can do the same with their "..."H string. But the run-time strings is a different case.

Do you mean to check the length of the string at runtime somehow?

[anton-trunov]

Do you mean to check the length of the string at runtime somehow?

the implementation should traverse all the chunks of the string

[anton-trunov]

related issue: #1085

[imartemy1524]

Maybe we should implement HASHEXT_SHA256 TVM instruction for sha256 to handle strings with length >=128?

This going solve all related issues.

[imartemy1524]

BTW writing such function in TACT which gonna support hashing of strings any length is not that hard, here is an example of a simple fift function, which computes sha256 hash of any string of any length:

asm fun sha256(data: String): Int{
    1 PUSHINT      // pusing the counter of the references to the stack
                   // s0 - counter, s1 - slice
    WHILE:<{
        OVER       // copying the last slice to the top of the stack
                   // s0 - slice (copy), s1 - counter, s2 - slice
        SREFS      // counting the refs in the slice s0 and putting it (the counter) to s0
                   // s0 - number (of refs), s1 - counter, s2 - slice
        0 NEQINT   // comparing the number or refs, if 0 then exit the loop
                   // s0 - bool, s1 - counter, s2 - slice
    }>DO<{
                   // s0 - counter, s1 - slice
        OVER       // copying the slice from s1 to the top of the stack (to s0)
                   // s0 - slice, s1 - counter, s2 - slice
        LDREF      // loading the reference, from s0 (the original data variable/last stack element), not s0 - original, s1 - result
                   // s0 - slice, s1 - cell (ref), s2 - counter, s3 - slice
        s0 POP     // removing the original slice from the stack (we don't need it anymore, only ref needed)
                   // s0 - cell (ref), s1 - counter, s2 - slice
        CTOS       // convert s0 the cell to slice (still in s0)
                   // s0 - slice (ref), s1 - counter, s2 - slice
        s0 s1 XCHG // putting to s1 the value of current slice (it was in s0 prev), and counter to s0
                   // s0 - counter, s1 - slice (ref), s2 - slice
        INC        // increment the counter (in s0)
    }>

    HASHEXT_SHA256 // call the sha256 function
}

P.S. I used FIFT because I don't know an easy way to do manual stack manipulation with tact/func

[novusnota]

BTW writing such function in TACT which gonna support hashing of strings any length is not that hard, here is an example of a simple fift function, which computes sha256 hash of any string of any length:

// ... code above ...

P.S. I used FIFT because I don't know an easy way to do manual stack manipulation with tact/func

Neat approach! However, the Fift-specific constructs like WHILE:<{ … }>DO<{ … }> (and similar) are probably going to be removed in the future Tact versions, as we're thinking about our own flavor of assembly for TVM.

Option 1

So, one option would be to move that function over to FunC and then bind to it from Tact:

int sha256(slice data) impure asm """
    1 PUSHINT      // pusing the counter of the references to the stack
                   // s0 - counter, s1 - slice
    WHILE:<{
        OVER       // copying the last slice to the top of the stack
                   // s0 - slice (copy), s1 - counter, s2 - slice
        SREFS      // counting the refs in the slice s0 and putting it (the counter) to s0
                   // s0 - number (of refs), s1 - counter, s2 - slice
        0 NEQINT   // comparing the number or refs, if 0 then exit the loop
                   // s0 - bool, s1 - counter, s2 - slice
    }>DO<{
                   // s0 - counter, s1 - slice
        OVER       // copying the slice from s1 to the top of the stack (to s0)
                   // s0 - slice, s1 - counter, s2 - slice
        LDREF      // loading the reference, from s0 (the original data variable/last stack element), not s0 - original, s1 - result
                   // s0 - slice, s1 - cell (ref), s2 - counter, s3 - slice
        s0 POP     // removing the original slice from the stack (we don't need it anymore, only ref needed)
                   // s0 - cell (ref), s1 - counter, s2 - slice
        CTOS       // convert s0 the cell to slice (still in s0)
                   // s0 - slice (ref), s1 - counter, s2 - slice
        s0 s1 XCHG // putting to s1 the value of current slice (it was in s0 prev), and counter to s0
                   // s0 - counter, s1 - slice (ref), s2 - slice
        INC        // increment the counter (in s0)
    }>

    HASHEXT_SHA256 // call the sha256 function
""";

import "./sha256.fc";

@name(sha256)
native onchainSha256(data: String): Int;

Option 2

Another approach would be to replace those WHILE:<{ things with something like this:

/// Main function that combines it all together
fun onchainSha256(data: String): Int {
    shaPush(data);
    while (shaShallProceed()) {
        shaOperate();
    }
    return shaHashExt();
}

/// Gets the data onto stack, then pushes the 1 there too
/// Since there's no return value bound, both will remain on stack
asm fun shaPush(data: String) { 1 PUSHINT }

/// The while loop clause, which captures the Bool from the top of the stack
asm fun shaShallProceed(): Bool { OVER SREFS 0 NEQINT }

/// The body of the while loop
asm fun shaOperate() {
    OVER LDREF s0 POP CTOS s0 s1 XCHG INC
}

/// HASHEXT_SHA256
asm fun shaHashExt(): Int { HASHEXT_SHA256 }

Conclusion of sorts

In any case, those or any other options won't appear in the user code directly, only in the emitted/generated code. That's because handling of sha256() is done at compile-time and we, currently, simply emit the FunC code to handle it for us iff we cannot compute the SHA256 right away, of course.

P.S.: Didn't test either of those options yet, just quickly wrote them here directly as a showcase :)
P.P.S.: Both actually work, wow

[novusnota]

The onchainSha256() example is now featured in docs: https://docs.tact-lang.org/book/assembly-functions/#onchainsha256

[i582]

But if we will use such a function (as onchainSha256), it seems that we will increase gas consumption due to additional instructions 🤔