Bitcoin Forum
November 14, 2019, 01:35:20 AM *
News: Help collect the most notable posts made over the last 10 years.
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Need mathematical proof for CH and MAJ functions in SHA256  (Read 95 times)
Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 701
Merit: 1157


Novice C♯ Coder


View Profile WWW
May 04, 2019, 06:41:18 AM
Last edit: May 04, 2019, 07:13:27 AM by Coding Enthusiast
Merited by ETFbitcoin (1), HeRetiK (1)
 #1

The SHA256 implementation that bitcoin-core is using has a different set of functions for CH and MAJ operations done in this hash function. While they both are nice little optimizations for skipping 1 bitwise operation, I can't figure out the mathematical proof for them being the same.

For reference:
Code:
CH = (x & y) | ((~x) & z)
CH_alt = z ^ (x & (y ^ z))
Code:
MAJ = (x & y) ^ (x & z) ^ (y & z)
MAJ_alt = (x & y) | (z & (x | y))

CH and MAJ are the functions from FIPS 180-3 while CH_alt and MAJ_alt are from bitcoin-core source code

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

The Bitcoin Forum is turning 10 years old! Join the community in sharing and exploring the notable posts made over the years.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2870
Merit: 2606



View Profile
May 04, 2019, 08:14:42 AM
Merited by darosior (2), ETFbitcoin (1)
 #2


These functions are just simply three-bit input boolean functions (used bitslice style in SHA2).

With only 8 possible inputs exhaustion is a perfectly valid proof technique:

Code:
#include <stdio.h>
#include <stdlib.h>
int CH(int x,int y,int z) { return (x & y) | ((~x) & z); }
int CH_alt(int x,int y,int z) { return z ^ (x & (y ^ z)); }
int MAJ(int x,int y,int z) { return (x & y) ^ (x & z) ^ (y & z);}
int MAJ_alt(int x,int y,int z) { return (x & y) | (z & (x | y));};
int main(void){
  int x,y,z;
  for (x=0; x<2; x++) {
    for (y=0; y<2; y++) {
      for (z=0; z<2; z++) {
        if((CH(x,y,z) != CH_alt(x,y,z)) || (MAJ(x,y,z) != MAJ_alt(x,y,z))) {
          printf("quod est absurdum\n");
          exit(1);
        }
      }
    }
  }
  printf("QED\n");
  return 0;
}
darosior
Full Member
***
Offline Offline

Activity: 196
Merit: 223



View Profile WWW
May 04, 2019, 10:12:26 AM
Merited by ETFbitcoin (1), aliashraf (1)
 #3

The SHA256 implementation that bitcoin-core is using has a different set of functions for CH and MAJ operations done in this hash function. While they both are nice little optimizations for skipping 1 bitwise operation, I can't figure out the mathematical proof for them being the same.

For reference:
Code:
CH = (x & y) | ((~x) & z)
CH_alt = z ^ (x & (y ^ z))
Code:
MAJ = (x & y) ^ (x & z) ^ (y & z)
MAJ_alt = (x & y) | (z & (x | y))

CH and MAJ are the functions from FIPS 180-3 while CH_alt and MAJ_alt are from bitcoin-core source code

Code:
CH_alt = z ^ (x & (y ^ z))
CH_alt = (~z) & (x & (y ^ z)) | z & ((~x) | ~(y ^ z))  
CH_alt = x & (~z) & (y ^ z) | (z & (~x)) | (z & ~(y ^ z))
CH_alt = x & y | (z & (~x)) | (z & ~(y ^ z))
CH_alt = (x & y) | ((~x) & z)
CH_alt = CH
Hint :
Code:
(~z) & (y ^ z) = 0
z & ~(y ^ z) = 0

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!