Problem Statement: https://gist.github.com/puma314/6bf27edd39a30419f8feeee884f41488
Open this in zkREPL →
Convert two dimenstion array of input bytes to one large concatenated array of input bits. Transform input_bytes[10][32] to all_bits[10 * 32 * 8].
// Convert to bits and construct one large array
var numInputBytes = n * 32;
signal all_bits[numInputBytes * 8];
component num2Bits[numInputBytes];
for (var i = 0; i < n; i++) {
for (var j = 0; j < 32; j++) {
num2Bits[i * 32 + j] = Num2Bits(8);
num2Bits[i * 32 + j].in <== input_bytes[i][j];
for (var k = 0; k < 8; k++) {
all_bits[(i * 32 + j) * 8 + k] <== num2Bits[i * 32 + j].out[7 - k];
}
}
}SHA256 requires inputs to be padded using the following scheme:
INPUT_BITS || 1 || 0....0 || LENGTH_OF_INPUT_BITSWhere LENGTH_OF_INPUT_BITS is stored in the last 64 bits. The total length of padding is a multiple of 512 bits.
Now, given that length signal is not defined at compile time, we will need to construct a padded input array for each possible value of length.
But we can only feed in a fixed length array to the hash function. So, we will pad the input array with zeroes such that the length of all of them is the same as the length of the padded array of length 10, which is 3072 bits. We will see later how we can avoid hashing the padded zeroes.
So, for length = 1, we will have:
First 256 bits of all_bits || 1 || 0....0 || 256_in_bits || 0...0 until length is 3072for length = 2, we will have:
First 512 bits of all_bits || 1 || 0....0 || 512_in_bits || 0...0 until length is 3072and so on.
// Construct arrays with inputs to the hash functions for all lengths
var maxBlocks = 6;
var maxBits = 6 * 512; // 3072
signal padded_input[n][maxBits];
component padders[n];
for (var i = 0; i < n; i++) {
var inp_size = 256 * (i + 1);
padders[i] = Sha256Padding(inp_size);
for (var t = 0; t < inp_size; t++) {
padders[i].in[t] <== all_bits[t];
}
var nBlocks = ((i + 1) \ 2) + 1;
for (var t = 0; t < nBlocks * 512; t++) {
padded_input[i][t] <== padders[i].out[t];
}
// Pad the rest with zeroes
for (var t = nBlocks * 512; t < maxBits; t++) {
padded_input[i][t] <== 0;
}
}Next out of all the possible 10 padded inputs to the, we select one of them by first constructing a mask and then applying it.
// Select input to hash function based on length
// Create a mask with 1 at index length and 0 otherwise
signal mask[n];
component isEq[n];
for (var i = 0; i < n; i++) {
isEq[i] = IsEqual();
isEq[i].in[0] <== i + 1;
isEq[i].in[1] <== length;
mask[i] <== isEq[i].out;
}
// Apply the mask to select the input array to be fed into Sha256 hash function
signal sha_inp[maxBits];
signal sum[maxBits][n];
for (var i = 0; i < maxBits; i++) {
sum[i][0] <== mask[0] * padded_input[0][i];
for (var j = 1; j < n; j++) {
sum[i][j] <== sum[i][j-1] + mask[j] * padded_input[j][i];
}
sha_inp[i] <== sum[i][n-1];
}This custom SHA256 template leverages the Merkle-Damgard construction of SHA256 function. The SHA256 hash function applies the same compression function to each block of 512 bits of the input. The output of the compression function is then fed into the next compression function along with the next block of 512 bits of the input.
Now, our padded input contains a valid padded input and then a bunch of zeroes. For example, for length 2, we have the following:
First 512 bits of all_bits || 1 || 0....0 || 512_in_bits || 0...0 until length is 3072We want to avoid hasing the padded zeroes. So, we will hash all the bits, but then we will only select the output of the compression function corresponding to the block that contains the valid input. For example, for length 2, we will hash all the bits, but then we will only select the output of the compression function corresponding to the second block, which has hashed values of the first 1024 bits of the input, which is this
First 512 bits of all_bits || 1 || 0....0 || 512_in_bitsand we discard the output of the rest of the compression functions.
Implementation of the CustomSha256 template is as follows:
template CustomSha256(nBlocks) {
var i;
var k;
signal input paddedIn[nBlocks*512];
signal input output_block;
signal output out[256];
/*
Usual SHA256 stuff...
*/
// Create a mask with 1 at output block and 0 otherwise
signal mask[nBlocks];
component isEq[nBlocks];
for (var j = 0; j < nBlocks; j++) {
isEq[j] = IsEqual();
isEq[j].in[0] <== (j + 1);
isEq[j].in[1] <== output_block;
mask[j] <== isEq[j].out;
}
// Apply mask to select the output from output_block
signal sum[256][nBlocks];
for (k=0; k<256; k++) {
sum[k][0] <== mask[0] * sha256compression[0].out[k];
for (var j = 1; j < nBlocks; j++) {
sum[k][j] <== sum[k][j-1] + mask[j] * sha256compression[j].out[k];
}
out[k] <== sum[k][nBlocks - 1];
}
}We feed the selected input to the SHA256 hash function. We determine the sha256 compression function (ouptut_block) from which we want to extract the output based on the length signal.
// Feed sha_inp to SHA256
signal q <-- length \ 2;
signal rem <-- length % 2;
// Make sure rem is < 2, i.e. rem is 0 or 1
rem * (rem - 1) === 0;
q * 2 + rem === length;
component sha256 = CustomSha256(maxBlocks);
for (var i = 0; i < maxBits; i++) {
sha256.paddedIn[i] <== sha_inp[i];
}
sha256.output_block <== q + 1;
// Convert output of sha256 to array of bytes
component bits2Num[32];
for (var i = 0; i < 32; i++) {
bits2Num[i] = Bits2Num(8);
for (var j = 0; j < 8; j++) {
bits2Num[i].in[j] <== sha256.out[i * 8 + j];
}
out[i] <== bits2Num[i].out;
}