इस ट्यूटोरियल में, हम Circom में MD5 hash लागू करेंगे ताकि hash की गणना की जा सके और Circom में यह constrain किया जा सके कि इसकी गणना सही ढंग से की गई थी।
हालाँकि MD5 hash function क्रिप्टोग्राफ़िक रूप से सुरक्षित नहीं है (चूंकि इसमें collisions पाए गए हैं), लेकिन इसकी कार्यप्रणाली क्रिप्टोग्राफ़िक रूप से सुरक्षित hash functions के समान ही है।
महत्वपूर्ण बात यह है कि, MD5 hash function को जल्दी से सीखा जा सकता है। निम्नलिखित 14 मिनट का वीडियो बताता है कि MD5 hash कैसे काम करता है। हम पहले इसे देखने की सलाह देते हैं:
https://www.youtube.com/watch?v=5MiMK45gkTY
यह साबित करने के लिए कि हम MD5 hash का preimage बिना उसे उजागर किए जानते हैं, हमें यह साबित करना होगा कि हमने hash के हर step को सही ढंग से execute किया है और एक निश्चित परिणाम उत्पन्न किया है। यह ट्यूटोरियल दिखाता है कि प्रत्येक state transition के लिए constraints को कैसे डिज़ाइन किया जाए।
विशेष रूप से, MD5 hash में निम्नलिखित subroutines होते हैं:
- Bitwise AND, OR, NOT, और XOR
- LeftRotate
- 32-bit numbers को जोड़ना और पर overflow होना
Funcfunction, जो bitwise operators का उपयोग करकेB,C, औरDregisters को एक साथ जोड़ता है- शुरुआत में padding step, जो input के बाद 1 bit जोड़ता है और input की length (bits में) डालता है
इसके अतिरिक्त, MD5 का output आमतौर पर big-endian फॉर्म में 128-bit number के रूप में लिखा जाता है। मान लीजिए कि हमारे पास एक 128-bit value 0x1234567890ABCDEF1122334455667788 है
big-endian में, इसे इस प्रकार लिखा जाएगा:
0x12 0x34 0x56 0x78 0x90 0xAB 0xCD 0xEF 0x11 0x22 0x33 0x44 0x55 0x66 0x77 0x88
little-endian में, यह होगा:
0x88 0x77 0x66 0x55 0x44 0x33 0x22 0x11 0xEF 0xCD 0xAB 0x90 0x78 0x56 0x34 0x12
हमें bytes के क्रम को little endian से big endian में उलटने के लिए एक अलग routine की आवश्यकता होगी। अधिकांश hash implementations का output big endian होता है, इसलिए हमारे परिणाम की स्थापित libraries के साथ आसानी से तुलना करने के लिए, हम चाहते हैं कि हमारा implementation big endian format में output दे। इसके लिए हम बाद में एक ToBytes component बनाएंगे।
हालाँकि इसमें काफी मात्रा में array indexing होती है, लेकिन हम जो index उपयोग करते हैं वह hash के iteration के आधार पर deterministic होता है, इसलिए hash constraints में कहीं भी Quin selector की आवश्यकता नहीं है — हम array indexing को hardcode कर सकते हैं।
Python में एक MD5 prototype बनाना
Hash function जैसी जटिल चीज़ बनाते समय, यह एक अच्छा विचार है कि Python जैसी अधिक परिचित और डीबग करने में आसान भाषा में एक reference implementation बनाया जाए, और फिर Python कोड को Circom में अनुवादित किया जाए।
यहाँ MD5 का Python implementation दिया गया है (जो सरलता के लिए केवल 448 bits के input का समर्थन करता है)। यह Utkarsh87 द्वारा किए गए इस अन्य implementation से काफी प्रेरित है। हमने functions को “component-like” व्यवहार करने वाला बनाने की कोशिश की है, ताकि Circom में इसका अनुवाद अधिक सीधा हो सके।
कुछ implementation नोट्स:
- Addition mod numbers को जोड़कर और फिर
Overflow32()function को कॉल करके किया जाता है। - हम inputs को bits के array के बजाय bytes के array के रूप में स्वीकार करते हैं।
- Byte
0x80बाइनरी में10000000जैसा दिखता है। यह हमें अंत में एक सिंगल bit के साथ input को pad करने की अनुमति देता है। - Output big-endian format में है।
s = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]
K = [0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391]
iter_to_index = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9]
def Overflow32(x):
return x & 0xFFFFFFFF
def leftRotate(x, amount):
#x &= 0xFFFFFFFF
xo = Overflow32(x)
return Overflow32((xo << amount | xo >> (32 -amount)))
def func(B, C, D, i):
out = None
# note that i will be 1..64 inclusive
if i <= 16:
out = (B & C) | (~B & D)
elif i > 16 and i <= 32:
out = (D & B) | (~D & C)
elif i > 32 and i <= 48:
out = B ^ C ^ D
elif i > 48 and i <= 64:
out = C ^ (B | ~D)
else:
assert False, "1) What"
return out
# concatenates four bytes to become 32 bits
def To32BitWord(byte1, byte2, byte3, byte4):
return byte1 + byte2 * 2**8 + byte3 * 2**16 + byte4 * 2**24
# length is the byte where the data stops
# so if we have zero bytes, we write 0x80
# to byte 0
def md5(bytes, length):
data = bytearray(64)
msg = bytearray(bytes, 'ascii')
# 56 bytes, 64 is the max
assert length < 56, "too long"
if length < 56:
data[length] = 0x80
data[56] = (length * 8).to_bytes(1, byteorder='little')[0]
for i in range(57,64):
data[i] = 0x00
for i in range(0, length):
data[i] = msg[i]
# data is a len 64 array of bytes. However, it will be much easier to work
# on if we turn it into a len 16 array of 32 bit words
data_32 = [0] * 16
for i in range(0, 16):
data_32[i] = To32BitWord(data[4*i], data[4*i + 1], data[4*i + 2], data[4*i + 3])
# algo runs for 64 iterations with 4 registers, each using 32 bits
# we allocate 65, because the 0th will be the default starting value
buffer = [[0]*4 for _ in range(65)]
buffer[0][0] = 0x67452301
buffer[0][1] = 0xefcdab89
buffer[0][2] = 0x98badcfe
buffer[0][3] = 0x10325476
A = 0
B = 1
C = 2
D = 3
for i in range(1, 65):
F = func(buffer[i - 1][B], buffer[i - 1][C], buffer[i - 1][D], i)
G = iter_to_index[i - 1]
to_rotate = buffer[i-1][A] + F + K[i - 1] + data_32[iter_to_index[i - 1]]
rotated = leftRotate(to_rotate, s[i - 1])
new_B = Overflow32(buffer[i-1][B] + rotated)
buffer[i][A] = buffer[i - 1][D]
buffer[i][B] = new_B
buffer[i][C] = buffer[i - 1][B]
buffer[i][D] = buffer[i - 1][C]
final = [0,0,0,0]
for i, b in enumerate(buffer[64]):
final[i] = Overflow32((b + buffer[0][i]))
digest = final[0] + final[1] * 2**32 + final[2] * 2**64 + final[3] * 2**96
raw = digest.to_bytes(16, byteorder='little')
return int.from_bytes(raw, byteorder='big')
print(hex(md5("RareSkills", 10)))
आवश्यक Components
Overflow32
Overflow32 एक VM में 32-bit overflow को emulate करता है जो पर होता है:
template Overflow32() {
signal input in;
signal output out;
component n2b = Num2Bits(252);
component b2n = Bits2Num(32);
n2b.in <== in;
for (var i = 0; i < 32; i++) {
n2b.out[i] ==> b2n.in[i];
}
b2n.out ==> out;
}
LeftRotate
LeftRotate bits को इस तरह rotate करता है जैसे कि वे एक circular buffer में हों:
template LeftRotate(s) {
signal input in;
signal output out;
component n2b = Num2Bits(32);
component b2n = Bits2Num(32);
n2b.in <== in;
for (var i = 0; i < 32; i++) {
b2n.in[(i + s) % 32] <== n2b.out[i];
}
out <== b2n.out;
}
Bitwise AND, OR, XOR, और NOT
निम्नलिखित templates हमारे 32-bit emulation वाले ट्यूटोरियल में बनाए गए थे:
template BitwiseAnd32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Ands[32];
for (var i = 0; i < 32; i++) {
Ands[i] = AND();
Ands[i].a <== n2ba.out[i];
Ands[i].b <== n2bb.out[i];
Ands[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseOr32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Ors[32];
for (var i = 0; i < 32; i++) {
Ors[i] = OR();
Ors[i].a <== n2ba.out[i];
Ors[i].b <== n2bb.out[i];
Ors[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseXor32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Xors[32];
for (var i = 0; i < 32; i++) {
Xors[i] = XOR();
Xors[i].a <== n2ba.out[i];
Xors[i].b <== n2bb.out[i];
Xors[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseNot32() {
signal input in;
signal output out;
// range check
component n2ba = Num2Bits(32);
n2ba.in <== in;
component b2n = Bits2Num(32);
component Nots[32];
for (var i = 0; i < 32; i++) {
Nots[i] = NOT();
Nots[i].in <== n2ba.out[i];
Nots[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
Func
Func registers B, C और D को लेता है और उन्हें एक सिंगल output में मिलाता है — और वह संयोजन इस बात पर निर्भर करता है कि हम किस iteration पर हैं:
template Func(i) {
assert(i <= 64);
signal input b;
signal input c;
signal input d;
signal output out;
if (i <= 16) {
signal bAndc;
component a1 = BitwiseAnd32();
a1.in[0] <== b;
a1.in[1] <== c;
component a2 = BitwiseAnd32();
component n1 = BitwiseNot32();
n1.in <== b;
a2.in[0] <== n1.out;
a2.in[1] <== d;
component o1 = BitwiseOr32();
o1.in[0] <== a1.out;
o1.in[1] <== a2.out;
out <== o1.out;
}
else if (i > 16 && i <= 32) {
component a1 = BitwiseAnd32();
a1.in[0] <== d;
a1.in[1] <== b;
component n1 = BitwiseNot32();
n1.in <== d;
component a2 = BitwiseAnd32();
a2.in[0] <== n1.out;
a2.in[1] <== c;
component o1 = BitwiseOr32();
o1.in[0] <== a1.out;
o1.in[1] <== a2.out;
out <== o1.out;
}
else if (i > 32 && i <= 48) {
component x1 = BitwiseXor32();
component x2 = BitwiseXor32();
x1.in[0] <== b;
x1.in[1] <== c;
x2.in[0] <== x1.out;
x2.in[1] <== d;
out <== x2.out;
}
// i must be <= 64 by the assert
// statement above
else {
component o1 = BitwiseOr32();
component n1 = BitwiseNot32();
n1.in <== d;
o1.in[0] <== n1.out;
o1.in[1] <== b;
component x1 = BitwiseXor32();
x1.in[0] <== o1.out;
x1.in[1] <==c;
out <== x1.out;
}
Input padding
चीजों को सरल बनाने के लिए, हमारा hash function bits के array के बजाय bytes के array को input के रूप में स्वीकार करता है। इसके अलावा, हम input की length को 56 bytes तक सीमित करते हैं ताकि हम hash द्वारा उपयोग किए जाने वाले 64 bytes (512 bit) input के 56वें byte index पर length डालने को hardcode कर सकें।
चूंकि input अधिकतम 56 bytes बड़ा होगा, इसलिए length के लिए हमें जिस नंबर का उपयोग करना होगा वह 448 bits से अधिक नहीं होगा, जिसे स्टोर करने के लिए अधिकतम 2 bytes की आवश्यकता होती है।
// n is the number of bytes
template Padding(n) {
// 56 bytes = 448 bits
assert(n < 56);
signal input in[n];
// 64 bytes = 512 bits
signal output out[64];
for (var i = 0; i < n; i++) {
out[i] <== in[i];
}
// add 128 = 0x80 to pad the 1 bit (0x80 = 10000000b)
out[n] <== 128;
// pad the rest with zeros
for (var i = n + 1; i < 56; i++) {
out[i] <== 0;
}
var lenBits = n * 8;
if (lenBits < 256) {
out[56] <== lenBits;
}
else {
var lowOrderBytes = lenBits % 256;
var highOrderBytes = lenBits \ 256;
out[56] <== lowOrderBytes;
out[57] <== highOrderBytes;
}
}
Num2Bytes
Endianness को बदलने के लिए हमें एक signal in को bytes के array out में बदलना होगा:
// n is the number of bytes
template ToBytes(n) {
signal input in;
signal output out[n];
component n2b = Num2Bits(n * 8);
n2b.in <== in;
component b2ns[n];
for (var i = 0; i < n; i++) {
b2ns[i] = Bits2Num(8);
for (var j = 0; j < 8; j++) {
b2ns[i].in[j] <== n2b.out[8*i + j];
}
out[i] <== b2ns[i].out;
}
}
Final Solution
नीचे दिया गया कोड MD5 hash करने के लिए सभी components को एक साथ जोड़ता है। यह परिणाम को big-endian फॉर्म में भी परिवर्तित करता है। पाठक zkrepl में कोड का परीक्षण कर सकते हैं।
include "circomlib/bitify.circom";
include "circomlib/gates.circom";
template BitwiseAnd32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Ands[32];
for (var i = 0; i < 32; i++) {
Ands[i] = AND();
Ands[i].a <== n2ba.out[i];
Ands[i].b <== n2bb.out[i];
Ands[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseOr32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Ors[32];
for (var i = 0; i < 32; i++) {
Ors[i] = OR();
Ors[i].a <== n2ba.out[i];
Ors[i].b <== n2bb.out[i];
Ors[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseXor32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Xors[32];
for (var i = 0; i < 32; i++) {
Xors[i] = XOR();
Xors[i].a <== n2ba.out[i];
Xors[i].b <== n2bb.out[i];
Xors[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseNot32() {
signal input in;
signal output out;
// range check
component n2ba = Num2Bits(32);
n2ba.in <== in;
component b2n = Bits2Num(32);
component Nots[32];
for (var i = 0; i < 32; i++) {
Nots[i] = NOT();
Nots[i].in <== n2ba.out[i];
Nots[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
// n is the number of bytes
template ToBytes(n) {
signal input in;
signal output out[n];
component n2b = Num2Bits(n * 8);
n2b.in <== in;
component b2ns[n];
for (var i = 0; i < n; i++) {
b2ns[i] = Bits2Num(8);
for (var j = 0; j < 8; j++) {
b2ns[i].in[j] <== n2b.out[8*i + j];
}
out[i] <== b2ns[i].out;
}
}
// n is the number of bytes
template Padding(n) {
// 56 bytes = 448 bits
assert(n < 56);
signal input in[n];
// 64 bytes = 512 bits
signal output out[64];
for (var i = 0; i < n; i++) {
out[i] <== in[i];
}
// add 128 = 0x80 to pad the 1 bit (0x80 = 10000000b)
out[n] <== 128;
// pad the rest with zeros
for (var i = n + 1; i < 56; i++) {
out[i] <== 0;
}
var lenBits = n * 8;
if (lenBits < 256) {
out[56] <== lenBits;
}
else {
var lowOrderBytes = lenBits % 256;
var highOrderBytes = lenBits \ 256;
out[56] <== lowOrderBytes;
out[57] <== highOrderBytes;
}
}
template Overflow32() {
signal input in;
signal output out;
component n2b = Num2Bits(252);
component b2n = Bits2Num(32);
n2b.in <== in;
for (var i = 0; i < 32; i++) {
n2b.out[i] ==> b2n.in[i];
}
b2n.out ==> out;
}
template LeftRotate(s) {
signal input in;
signal output out;
component n2b = Num2Bits(32);
component b2n = Bits2Num(32);
n2b.in <== in;
for (var i = 0; i < 32; i++) {
b2n.in[(i + s) % 32] <== n2b.out[i];
}
out <== b2n.out;
}
template Func(i) {
assert(i <= 64);
signal input b;
signal input c;
signal input d;
signal output out;
if (i < 16) {
component a1 = BitwiseAnd32();
a1.in[0] <== b;
a1.in[1] <== c;
component a2 = BitwiseAnd32();
component n1 = BitwiseNot32();
n1.in <== b;
a2.in[0] <== n1.out;
a2.in[1] <== d;
component o1 = BitwiseOr32();
o1.in[0] <== a1.out;
o1.in[1] <== a2.out;
out <== o1.out;
}
else if (i >= 16 && i < 32) {
// (D & B) | (~D & C)
component a1 = BitwiseAnd32();
a1.in[0] <== d;
a1.in[1] <== b;
component n1 = BitwiseNot32();
n1.in <== d;
component a2 = BitwiseAnd32();
a2.in[0] <== n1.out;
a2.in[1] <== c;
component o1 = BitwiseOr32();
o1.in[0] <== a1.out;
o1.in[1] <== a2.out;
out <== o1.out;
}
else if (i >= 32 && i < 48) {
component x1 = BitwiseXor32();
component x2 = BitwiseXor32();
x1.in[0] <== b;
x1.in[1] <== c;
x2.in[0] <== x1.out;
x2.in[1] <== d;
out <== x2.out;
}
// i must be < 64 by the assert statement above
else {
component o1 = BitwiseOr32();
component n1 = BitwiseNot32();
n1.in <== d;
o1.in[0] <== n1.out;
o1.in[1] <== b;
component x1 = BitwiseXor32();
x1.in[0] <== o1.out;
x1.in[1] <==c;
out <== x1.out;
}
}
// n is the number of bytes
template MD5(n) {
var s[64] = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21];
var K[64] = [0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391];
var iter_to_index[64] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12,
5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2,
0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9];
signal input in[n];
signal inp[64];
component Pad = Padding(n);
for (var i = 0; i < n; i++) {
Pad.in[i] <== in[i];
}
for (var i = 0; i < 64; i++) {
Pad.out[i] ==> inp[i];
}
signal data32[16];
for (var i = 0; i < 16; i++) {
data32[i] <== inp[4 * i] + inp[4 * i + 1] * 2**8 + inp[4 * i + 2] * 2**16 + inp[4 * i + 3] * 2**24;
}
var A = 0;
var B = 1;
var C = 2;
var D = 3;
signal buffer[65][4];
buffer[0][A] <== 1732584193;
buffer[0][B] <== 4023233417;
buffer[0][C] <== 2562383102;
buffer[0][D] <== 271733878;
component Funcs[64];
signal toRotates[64];
component SelectInputWords[64];
component LeftRotates[64];
component Overflow32s[64];
component Overflow32s2[64];
for (var i = 0; i < 64; i++) {
Funcs[i] = Func(i);
Funcs[i].b <== buffer[i][B];
Funcs[i].c <== buffer[i][C];
Funcs[i].d <== buffer[i][D];
Overflow32s[i] = Overflow32();
Overflow32s[i].in <== buffer[i][A] + Funcs[i].out + K[i] + data32[iter_to_index[i]];
// rotated = rotate(to_rotate, s[i])
toRotates[i] <== Overflow32s[i].out;
LeftRotates[i] = LeftRotate(s[i]);
LeftRotates[i].in <== toRotates[i];
// new_B = rotated + B
Overflow32s2[i] = Overflow32();
Overflow32s2[i].in <== LeftRotates[i].out + buffer[i][B];
// store into the next state
buffer[i + 1][A] <== buffer[i][D];
buffer[i + 1][B] <== Overflow32s2[i].out;
buffer[i + 1][C] <== buffer[i][B];
buffer[i + 1][D] <== buffer[i][C];
}
component addA = Overflow32();
component addB = Overflow32();
component addC = Overflow32();
component addD = Overflow32();
// we hardcode initial state because we only
// process one 512 bit block
addA.in <== 1732584193 + buffer[64][A];
addB.in <== 4023233417 + buffer[64][B];
addC.in <== 2562383102 + buffer[64][C];
addD.in <== 271733878 + buffer[64][D];
signal littleEndianMd5;
littleEndianMd5 <== addA.out + addB.out * 2**32 + addC.out * 2**64 + addD.out * 2**96;
// convert the answer to bytes and reverse
// the bytes order to make it big endian
component Tb = ToBytes(16);
Tb.in <== littleEndianMd5;
// sum the bytes in reverse
var acc;
for (var i = 0; i < 16; i++) {
acc += Tb.out[15 - i] * 2**(i * 8);
}
signal output out;
out <== acc;
}
component main = MD5(10);
// The result out =
// "RareSkills" in ascii to decimal
/* INPUT = {"in": [82, 97, 114, 101, 83, 107, 105, 108, 108, 115]} */
// The result is 246193259845151292174181299259247598493
// The MD5 hash of "RareSkills" is 0xb93718dd21d2f5081239d7a16cf69b9d when converted to decimal is 246193259845151292174181299259247598493
ZK-friendly hashes के लिए प्रेरणा (Motivation)
ऊपर दिए गए कोड द्वारा निर्मित R1CS बावन हज़ार (52,000) से अधिक rows लंबा है, जैसा कि नीचे दिए गए चित्र में दिखाया गया है। सर्किट के आकार को कम करने के कई अवसर हैं, विशेष रूप से field elements को हर बार उपयोग करते समय 32-bit arrays में परिवर्तित न करके।
हालाँकि, MD5 (और अन्य आधुनिक hashes) में प्रत्येक word 32 bits का होता है, इसलिए इसे regular कोड की तुलना में represent करने के लिए 32 गुना अधिक signals की आवश्यकता होगी।
अगले अध्याय में, हम उन hashes के बारे में जानेंगे जो 32-bit words के बजाय native finite field पर काम करते हैं और XOR जैसे महंगे operations से बचते हैं, जिनके लिए signals को bits में decompose करने की आवश्यकता होती है।