Created
March 24, 2017 20:04
-
-
Save jorpic/2b84d5825f8055e224bc5eff9d7aa294 to your computer and use it in GitHub Desktop.
Generate tree of hashes from seed
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // This one (with nested arrays) has a bit cleaner code but less gas-efficient. | |
| pragma solidity ^0.4.8; | |
| contract salttree { | |
| // "0x98fe01c92ff2a2fa282b3aba5f8aead0", 28 | |
| // Gas usage: ~42k | |
| function gen(bytes16 root, uint size) returns (bytes16[]) { | |
| bytes16[] memory res = new bytes16[](size); | |
| uint height = log2(size); | |
| bytes16[2][] memory stack = new bytes16[2][](height); | |
| stack[height-1] = split(sha256(root)); | |
| uint lvl = height - 1; | |
| for(uint i = 0; i < size; ++i) { | |
| while(lvl > 0) { | |
| uint j = i & (1 << lvl) == 0 ? 0 : 1; | |
| stack[lvl-1] = split(sha256(stack[lvl][j])); | |
| lvl--; | |
| } | |
| res[i] = stack[0][i & 1]; | |
| lvl = least_significant_bit(i+1); | |
| } | |
| return res; | |
| } | |
| function log2(uint x) private returns (uint res) { | |
| while(x > 0) { | |
| x >>= 1; | |
| res++; | |
| } | |
| } | |
| // NB. x > 0 | |
| function least_significant_bit(uint x) private returns (uint res) { | |
| while(x & 1 == 0) { | |
| x >>= 1; | |
| res++; | |
| } | |
| } | |
| function split(bytes32 x) private returns (bytes16[2]) { | |
| bytes16 left; | |
| bytes16 right; | |
| assembly { | |
| let freemem_pointer := mload(0x40) | |
| mstore(freemem_pointer, x) | |
| left := mload(freemem_pointer) | |
| right := mload(add(freemem_pointer,0x10)) | |
| } | |
| return [left, right]; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // This one (with structs) uses less gas compared to the version with nested arrays. | |
| pragma solidity ^0.4.8; | |
| contract salttree { | |
| // "0x98fe01c92ff2a2fa282b3aba5f8aead0", 28 | |
| // Gas usage: ~37k | |
| struct bytes16x2 { | |
| bytes16 l; | |
| bytes16 r; | |
| } | |
| function gen(bytes16 root, uint size) returns (bytes16[]) { | |
| bytes16[] memory res = new bytes16[](size); | |
| uint height = log2(size); | |
| bytes16x2[] memory stack = new bytes16x2[](height); | |
| stack[height-1] = split(sha256(root)); | |
| uint lvl = height - 1; | |
| for(uint i = 0; i < size; ++i) { | |
| while(lvl > 0) { | |
| var xx = i & (1 << lvl) == 0 ? stack[lvl].l : stack[lvl].r; | |
| stack[lvl-1] = split(sha256(xx)); | |
| lvl--; | |
| } | |
| res[i] = i & 1 == 0 ? stack[0].l : stack[0].r; | |
| lvl = least_significant_bit(i+1); | |
| } | |
| return res; | |
| } | |
| function log2(uint x) private returns (uint res) { | |
| while(x > 0) { | |
| x >>= 1; | |
| res++; | |
| } | |
| } | |
| // NB. x > 0 | |
| function least_significant_bit(uint x) private returns (uint res) { | |
| while(x & 1 == 0) { | |
| x >>= 1; | |
| res++; | |
| } | |
| } | |
| function split(bytes32 x) private returns (bytes16x2) { | |
| bytes16 left; | |
| bytes16 right; | |
| assembly { | |
| let freemem_pointer := mload(0x40) | |
| mstore(freemem_pointer, x) | |
| left := mload(freemem_pointer) | |
| right := mload(add(freemem_pointer,0x10)) | |
| } | |
| return bytes16x2(left, right); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment