merkle-path.c

/*
 * Copyright © [2024] Lita Inc. All Rights Reserved.
 *
 * This software and associated documentation files (the “Software”) are owned by Lita Inc. and are protected by copyright law and international treaties.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to use the Software for personal, non-commercial purposes only, subject to the following conditions:
 *
 * 1. The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 * 2. The Software may not be used for commercial purposes without the express written permission of Lita Inc.
 *
 * For inquiries regarding commercial use, please contact us at: ops@lita.foundation
 *
 * THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

// Merkle opening proof verification for binary Merkle hash trees, where the
// leaves are strings of 32 bytes and the hash is SHA-256. The input consists
// of the leaf (32 bytes), followed by whether the leaf is left or right (one byte,
// 1 = right), followed by the leaf's sibling (32 bytes), followed by whether their
// parent is left or right (one byte), followed by their parent's sibling (32 bytes),
// followed by whether the hash of the parent and the parent's sibling is left or
// right (one byte), etc.

// The below SHA256 code comes from https://github.com/B-Con/crypto-algorithms/
// , was originally written by Brad Conte, and has been modified
// to compile and run in Valida.

/****************************** MACROS ******************************/
#define SHA256_BLOCK_SIZE 32            // SHA256 outputs a 32 byte digest

#ifdef __DELENDUM__
#define size_t unsigned int

void * memset ( void * b, int c, size_t len ) {
  int           i;
  unsigned char *p = b;
  i = 0;
  while(len > 0)
    {
      *p = c;
      p++;
      len--;
    }
  return b;
}
#else
#include <stddef.h>
#endif

/**************************** DATA TYPES ****************************/
typedef unsigned char BYTE;             // 8-bit byte
typedef unsigned int  WORD;             // 32-bit word, change to "long" for 16-bit machines

typedef struct {
	BYTE data[64];
	WORD datalen;
	unsigned long long bitlen;
	WORD state[8];
} SHA256_CTX;

/*********************** FUNCTION DECLARATIONS **********************/
void sha256_init(SHA256_CTX *ctx);
void sha256_update(SHA256_CTX *ctx, const BYTE data[], size_t len);
void sha256_final(SHA256_CTX *ctx, BYTE hash[]);

/****************************** MACROS ******************************/
#define ROTLEFT(a,b) (((a) << (b)) | ((a) >> (32-(b))))
#define ROTRIGHT(a,b) (((a) >> (b)) | ((a) << (32-(b))))

#define CH(x,y,z) (((x) & (y)) ^ (~(x) & (z)))
#define MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))
#define EP0(x) (ROTRIGHT(x,2) ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22))
#define EP1(x) (ROTRIGHT(x,6) ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25))
#define SIG0(x) (ROTRIGHT(x,7) ^ ROTRIGHT(x,18) ^ ((x) >> 3))
#define SIG1(x) (ROTRIGHT(x,17) ^ ROTRIGHT(x,19) ^ ((x) >> 10))

/**************************** VARIABLES *****************************/
static const WORD k[64] = {
	0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,
	0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,
	0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
	0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,
	0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,
	0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
	0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,
	0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
};

/*********************** FUNCTION DEFINITIONS ***********************/
void sha256_transform(SHA256_CTX *ctx, const BYTE data[])
{
	WORD a, b, c, d, e, f, g, h, i, j, t1, t2, m[64];

	for (i = 0, j = 0; i < 16; ++i, j += 4)
		m[i] = (data[j] << 24) | (data[j + 1] << 16) | (data[j + 2] << 8) | (data[j + 3]);
	for ( ; i < 64; ++i)
		m[i] = SIG1(m[i - 2]) + m[i - 7] + SIG0(m[i - 15]) + m[i - 16];

	a = ctx->state[0];
	b = ctx->state[1];
	c = ctx->state[2];
	d = ctx->state[3];
	e = ctx->state[4];
	f = ctx->state[5];
	g = ctx->state[6];
	h = ctx->state[7];

	for (i = 0; i < 64; ++i) {
		t1 = h + EP1(e) + CH(e,f,g) + k[i] + m[i];
		t2 = EP0(a) + MAJ(a,b,c);
		h = g;
		g = f;
		f = e;
		e = d + t1;
		d = c;
		c = b;
		b = a;
		a = t1 + t2;
	}

	ctx->state[0] += a;
	ctx->state[1] += b;
	ctx->state[2] += c;
	ctx->state[3] += d;
	ctx->state[4] += e;
	ctx->state[5] += f;
	ctx->state[6] += g;
	ctx->state[7] += h;
}

void sha256_init(SHA256_CTX *ctx)
{
	ctx->datalen = 0;
	ctx->bitlen = 0;
	ctx->state[0] = 0x6a09e667;
	ctx->state[1] = 0xbb67ae85;
	ctx->state[2] = 0x3c6ef372;
	ctx->state[3] = 0xa54ff53a;
	ctx->state[4] = 0x510e527f;
	ctx->state[5] = 0x9b05688c;
	ctx->state[6] = 0x1f83d9ab;
	ctx->state[7] = 0x5be0cd19;
}

void sha256_update(SHA256_CTX *ctx, const BYTE data[], size_t len)
{
	WORD i;

	for (i = 0; i < len; ++i) {
		ctx->data[ctx->datalen] = data[i];
		ctx->datalen++;
		if (ctx->datalen == 64) {
			sha256_transform(ctx, ctx->data);
			ctx->bitlen += 512;
			ctx->datalen = 0;
		}
	}
}

void sha256_final(SHA256_CTX *ctx, BYTE hash[])
{
	WORD i;

	i = ctx->datalen;

	// Pad whatever data is left in the buffer.
	if (ctx->datalen < 56) {
		ctx->data[i++] = 0x80;
		while (i < 56)
			ctx->data[i++] = 0x00;
	}
	else {
		ctx->data[i++] = 0x80;
		while (i < 64)
			ctx->data[i++] = 0x00;
		sha256_transform(ctx, ctx->data);
    for (unsigned j = 0; j < 56; j++)
      ctx->data[j] = 0;
	}

	// Append to the padding the total message's length in bits and transform.
	ctx->bitlen += ctx->datalen * 8;
	ctx->data[63] = ctx->bitlen;
	ctx->data[62] = ctx->bitlen >> 8;
	ctx->data[61] = ctx->bitlen >> 16;
	ctx->data[60] = ctx->bitlen >> 24;
	ctx->data[59] = ctx->bitlen >> 32;
	ctx->data[58] = ctx->bitlen >> 40;
	ctx->data[57] = ctx->bitlen >> 48;
	ctx->data[56] = ctx->bitlen >> 56;
	sha256_transform(ctx, ctx->data);

	// Since this implementation uses little endian byte ordering and SHA uses big endian,
	// reverse all the bytes when copying the final state to the output hash.
	for (i = 0; i < 4; ++i) {
		hash[i]      = (ctx->state[0] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 4]  = (ctx->state[1] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 8]  = (ctx->state[2] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 12] = (ctx->state[3] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 16] = (ctx->state[4] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 20] = (ctx->state[5] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 24] = (ctx->state[6] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 28] = (ctx->state[7] >> (24 - i * 8)) & 0x000000ff;
	}
}

#define BUF_LEN 256

#ifdef __DELENDUM__
const unsigned EOF = 0xFFFFFFFF;
#else
#include <stdio.h>
#endif

unsigned read_byte() {
#ifdef __DELENDUM__
        return __builtin_delendum_read_advice();
#else
        return getc(stdin);
#endif
}

// Reads SHA256_BLOCK_SIZE many bytes (or as many as are available) into buf.
// Returns EOF if EOF was reached; otherwise, returns 0.
unsigned read_block(BYTE *buf) {
    for (unsigned i = 0; i < SHA256_BLOCK_SIZE; i++) {
        unsigned c = read_byte();
        if (c == EOF) {
            return EOF;
        } else {
            buf[i] = (BYTE)c;
        }
    }
    return 0;
}

void write_block(BYTE *buf) {
    for (unsigned i = 0; i < SHA256_BLOCK_SIZE; i++) {
#ifdef __DELENDUM__
        __builtin_delendum_write(buf[i]);
#else
        putc(buf[i], stdout);
#endif
    }
}

int output(BYTE *leaf, BYTE *root) {
    write_block(leaf);
    write_block(root);
    return 0;
}

void hash_blocks(SHA256_CTX *ctx, BYTE *buf_left, BYTE *buf_right, BYTE *hash) {
    sha256_init(ctx);
    sha256_update(ctx, buf_left, SHA256_BLOCK_SIZE);
    sha256_update(ctx, buf_right, SHA256_BLOCK_SIZE);
    sha256_final(ctx, hash);
}

void copy_block(BYTE *from, BYTE *to) {
    for (unsigned i = 0; i < SHA256_BLOCK_SIZE; i++) {
        to[i] = from[i];
    }
}

int main() {
    BYTE buf_left[SHA256_BLOCK_SIZE];
    BYTE buf_right[SHA256_BLOCK_SIZE];
    BYTE leaf[SHA256_BLOCK_SIZE];
    BYTE hash[SHA256_BLOCK_SIZE];
    SHA256_CTX ctx;

    unsigned result = read_block(buf_left);
    if (result == EOF) {
        while (1) {}
    }
    copy_block(buf_left, leaf);

    unsigned is_right = read_byte();
    if (is_right == 1) {
        copy_block(buf_left, buf_right);
    } else if (is_right == EOF) {
        while (1) {}
    }

    BYTE *buf_empty = is_right ? buf_left : buf_right;
    result = read_block(buf_empty);
    if (result == EOF) {
        return output(leaf, leaf);
    }

    while (1) {
        hash_blocks(&ctx, buf_left, buf_right, hash);

        is_right = read_byte();
        if (is_right == 1) {
            copy_block(hash, buf_right);
        } else {
            copy_block(hash, buf_left);
        }

        BYTE *buf_empty = is_right ? buf_left : buf_right;
        result = read_block(buf_empty);
        if (result == EOF) {
            return output(leaf, hash);
        }
    }
}