From 10adf75ac7a8a5f277a7d8437bf995db4ff5905c Mon Sep 17 00:00:00 2001 From: alex Date: Tue, 1 Mar 2022 16:23:10 -0800 Subject: [PATCH] ... --- inc/block.h | 3 +- src/block.c | 52 ++++++++++++++++------------ test/unit/block.tests.c | 76 ++++++++++++++++------------------------- 3 files changed, 63 insertions(+), 68 deletions(-) diff --git a/inc/block.h b/inc/block.h index 00e9738..40c127a 100644 --- a/inc/block.h +++ b/inc/block.h @@ -15,11 +15,12 @@ struct block { struct block *next; }; +size_t block_end(struct block**); void block_free(struct block*); int block_init(struct block**); size_t block_length(struct block*); int block_merkle_layer(struct block*,struct block**); -int block_merkle_root(struct block*); +int block_merkle_root(struct block*,struct block**); int block_pad(struct block*); #endif diff --git a/src/block.c b/src/block.c index 76b2a21..3067fa1 100644 --- a/src/block.c +++ b/src/block.c @@ -36,33 +36,43 @@ size_t block_length(struct block *p) { return i; } -const static unsigned char zerod[crypto_hash_sha256_BYTES] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; - -int block_merkle_layer(struct block *root, struct block **next_layer) { - struct block *p, *tail; +int block_merkle_layer(struct block *p, struct block **next_layer) { + struct block *tail; crypto_hash_sha256_state state; + size_t len; int i; - if(NULL==root) { return -1; } + if(NULL==p) { return -1; } if(NULL==next_layer) { return -1; } - tail = root; + (*next_layer) = NULL; + + tail = p; + len = 1; while(tail->next!=NULL) { tail = tail->next; + len++; + } + + // already merkle_root + if(p==tail) { + (*next_layer) = p; + return 1; } - p = root; + // verify tree is balanced/padded + if((len==1)||(len&&(len&(len-1)))) { return -1; } + i = 0; - while(p!=NULL) { - if((NULL==p->next)&&(p==root)) { break; } + while(p!=(*next_layer)) { if(hash_init(&state)<0) { return -1; } if(hash_update(&state,p->hash,crypto_hash_sha256_BYTES)<0) { return -1; } - if(p->next!=NULL) { - if(hash_update(&state,p->next->hash,crypto_hash_sha256_BYTES)<0) { return -1; } - } else { - if(hash_update(&state,zerod,crypto_hash_sha256_BYTES)<0) { return -1; } - } + + // padding should be taken care of outside of this function + if(NULL==p->next) { return -1; } + + if(hash_update(&state,p->next->hash,crypto_hash_sha256_BYTES)<0) { return -1; } if(block_init(&(tail->next))<0) { return -1; } tail = tail->next; @@ -70,25 +80,25 @@ int block_merkle_layer(struct block *root, struct block **next_layer) { if(hash_final(&state,tail->hash,crypto_hash_sha256_BYTES)<0) { return -1; } // set index, marking as padding if both leaves are padding - tail->index = ((p->index<0)||(p->next->index<0))?-1:i; + tail->index = ((p->index<0)&&(p->next->index<0))?-1:i; if(NULL==(*next_layer)) { (*next_layer) = tail; } - p = p->next; + p = p->next->next; i++; } return 1; } -int block_merkle_root(struct block *root) { - struct block *end; +int block_merkle_root(struct block *p, struct block **root) { + if(NULL==p) { return -1; } if(NULL==root) { return -1; } - end = NULL; do { - if(block_merkle_layer(root,&end)<0) { return -1; } - } while(end->index>0); + if(block_merkle_layer(p,root)<0) { return -1; } + p = (*root); + } while((*root)->next!=NULL); return 1; } diff --git a/test/unit/block.tests.c b/test/unit/block.tests.c index 21cd4d9..97b7f7d 100644 --- a/test/unit/block.tests.c +++ b/test/unit/block.tests.c @@ -3,7 +3,6 @@ #include int main(); -static void block_duplicate_basic_test(); static void block_init_basic_test(); static void block_length_basic_test(); static void block_merkle_layer_basic_test(); @@ -14,7 +13,6 @@ int main() { setup_env(); block_init_basic_test(); - block_duplicate_basic_test(); block_length_basic_test(); block_merkle_layer_basic_test(); block_merkle_root_basic_test(); @@ -25,37 +23,6 @@ int main() { return EXIT_SUCCESS; } -static void block_duplicate_basic_test() { - struct block *root, *root2, *p, *p2; - - assert(block_init(&root)==1); - - p = root; - memset(root->hash,rand()%255,crypto_hash_sha256_BYTES); - - for(int i=0;i<(rand()%100)+1;i++) { - assert(block_init(&(p->next))==1); - p = p->next; - memset(p->hash,rand()%255,crypto_hash_sha256_BYTES); - } - - assert(block_duplicate(NULL,root)==-1); - assert(block_duplicate(&root2,NULL)==-1); - assert(block_duplicate(&root2,root)==1); - assert(block_length(root)==block_length(root2)); - - p = root; - p2 = root2; - while(p!=NULL) { - assert(memcmp(p->hash,p2->hash,crypto_hash_sha256_BYTES)==0); - p = p->next; - p2 = p2->next; - } - - block_free(root); - block_free(root2); -} - static void block_init_basic_test() { struct block *root, *p; unsigned char expected[crypto_hash_sha256_BYTES]; @@ -114,26 +81,37 @@ static void block_merkle_layer_basic_test() { unsigned char expected1[crypto_hash_sha256_BYTES] = {92,133,149,95,112,146,131,236,206,43,116,241,177,85,41,24,129,159,57,9,17,129,110,123,180,102,128,90,56,171,135,243}; unsigned char expected2[crypto_hash_sha256_BYTES] = {153,121,92,74,3,46,65,157,17,191,107,18,97,70,202,242,1,125,154,249,248,16,105,232,48,193,223,30,100,201,106,35}; - assert(block_merkle_layer(NULL)==-1); + assert(block_merkle_layer(NULL,NULL)==-1); assert(block_init(&root)==1); memset(root->hash,0,crypto_hash_sha256_BYTES); + root->index = 0; + + assert(block_merkle_layer(root,NULL)==-1); - assert(block_merkle_layer(root)==1); + assert(block_merkle_layer(root,&p)==1); assert(memcmp(root->hash,expected0,crypto_hash_sha256_BYTES)==0); assert(root->next==NULL); + assert(root==p); p = root; for(size_t i=1;i<3;i++) { assert(block_init(&(p->next))==1); p = p->next; + p->index = i; memset(p->hash,i,crypto_hash_sha256_BYTES); } - assert(block_merkle_layer(root)==1); - assert(memcmp(root->hash,expected1,crypto_hash_sha256_BYTES)==0); - assert(memcmp(root->next->hash,expected2,crypto_hash_sha256_BYTES)==0); - assert(NULL==root->next->next); + // verify unpadded tree fails + assert(block_merkle_layer(root,&p)==-1); + assert(block_pad(root)==1); + + assert(block_merkle_layer(root,&p)==1); + assert(memcmp(p->hash,expected1,crypto_hash_sha256_BYTES)==0); + assert(p->index==0); + assert(memcmp(p->next->hash,expected2,crypto_hash_sha256_BYTES)==0); + assert(p->next->index==1); + assert(NULL==p->next->next); block_free(root); } @@ -143,34 +121,40 @@ static void block_merkle_root_basic_test() { unsigned char expected1[crypto_hash_sha256_BYTES] = {92,133,149,95,112,146,131,236,206,43,116,241,177,85,41,24,129,159,57,9,17,129,110,123,180,102,128,90,56,171,135,243}; unsigned char expected2[crypto_hash_sha256_BYTES] = {252,172,191,66,234,208,21,52,228,232,243,175,181,101,38,122,15,81,143,16,87,98,223,146,109,9,25,247,251,145,102,203}; - assert(block_merkle_root(NULL)==-1); + assert(block_merkle_root(NULL,NULL)==-1); assert(block_init(&root)==1); memset(root->hash,0,crypto_hash_sha256_BYTES); + root->index = 0; - assert(block_merkle_root(root)==1); + assert(block_merkle_root(root,&p)==1); assert(block_init(&(root->next))==1); memset(root->next->hash,1,crypto_hash_sha256_BYTES); + root->next->index = 1; - assert(block_merkle_root(root)==1); - assert(memcmp(root->hash,expected1,crypto_hash_sha256_BYTES)==0); - assert(root->next==NULL); + assert(block_merkle_root(root,&p)==1); + assert(memcmp(p->hash,expected1,crypto_hash_sha256_BYTES)==0); + assert(p->next==NULL); block_free(root); assert(block_init(&root)==1); memset(root->hash,0,crypto_hash_sha256_BYTES); + root->index = 0; p = root; for(size_t i=1;i<256;i++) { assert(block_init(&(p->next))==1); p = p->next; + + p->index = i; memset(p->hash,i,crypto_hash_sha256_BYTES); } - assert(block_merkle_root(root)==1); - assert(memcmp(root->hash,expected2,crypto_hash_sha256_BYTES)==0); + assert(block_merkle_root(root,&p)==1); + assert(memcmp(p->hash,expected2,crypto_hash_sha256_BYTES)==0); + assert(p->next==NULL); block_free(root); } -- 2.30.2