FISCO bcos zero knowledge proof Fiat Shamir instance source code

Fiat-Shamir Zero knowledge proof protocol

Scenario introduction

Generally, when a user registers an account on the website , The website will ask users to set a password , Then save the password in the background , Users are required to enter this password again when logging in to the website , Compare with the password saved in the background , Determine whether to give the user login permission , But at this time, users' passwords are vulnerable to dictionary attacks , Some security conscious websites will add salt to save passwords hash, Increase the difficulty of the enemy exhausting user passwords or hitting the Library . However, the user password stored on the background server of the website always increases the risk of disclosure ,Fiat-Shamir Zero knowledge proof protocol allows users to prove to the registered website that they know their password , Without revealing any information about passwords to the website .

Fiat-Shamir with secret password

First Peggy（ Certifier ,Prover） And Victor（ Verifier ,Verifier） Just expose the parameters （ A prime number n, A module n Generators of groups g） Reach a consensus .

1. Peggy First choose her password , Then hash the password , Convert the result to an integer value x.

x=int(Hash(passowrd))
y=g^x mod n

Peggy hold y The value of is sent to Victor, Let him keep it

1. Now? Peggy Want to log in , She chooses a random number v, Calculation

t = g^v mod n

And then put t The value of is sent to Victor

1. Victor received t, Then send random numbers c to Peggy
2. Peggy Generate random number v, Calculation

r =v -cx mod (n-1) 

Peggy hold r Send to Victor

1. Victor Calculation

val=(g^r)(y^c) mod n

And then determine val And t Whether it is equal or not , If equal , be Peggy Proved that he knew the password , Then allow Peggy Sign in .

Use

Source code

SmartDev-Contract/contracts/common_tools/privacy_computation/Fiat-Shamir-ZK at master · WeBankBlockchain/SmartDev-Contract · GitHub

take FiatShamir.sol Deploy to blockchain

0x0a49ecf4d04e32769bdb210ee5be64e5171d5b59

1. Use under the chain contract_step1.py Calculation y value , And then in FiatShamir.sol Call in Step1_register take y Value registration .

2. Use under the chain contract_step2.py Calculation t value , And then in FiatShamir.sol Call in Step2_login Pass on t value .

 3. stay FiatShamir.sol Call in Step3_randomchallenge Generate c value .

4. see c Value and use contract_step45.py Calculation r value .

v It's a random number , In the 2 Generate

5. stay FiatShamir.sol Call in Step45_verify , Input r value , Output true or false, Indicates whether the verification is passed .

Result passed

  Try another

The input of each function is through Run under the chain contract_step1.py Calculation y,contract_step2.py Calculation t, contract_step45.py Calculation r .

fiat_shamir_1.py Reference code for the whole interaction process

reference

[1] Fiat, Amos, and Adi Shamir. “How to prove yourself: Practical solutions to identification and signature problems.” Conference on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1986.

file ：

Fiat-Shamir Zero knowledge proof protocol — WeBankBlockchain-SmartDev-Doc v2.6.0 file

contract_step1.py

import libnum
import hashlib
n=8269
g=11

password = "Hello"

print("Password:\t\t",password)
x = int(hashlib.sha256(password.encode()).hexdigest()[:8], 16) % n
print("Password hash(x):\t",x,"\t (last 8 bits)")

print('\n======Phase 1: Peggy sends y to Victor,Victor store y as Peggy\' token==================')
y= pow(g,x,n)
print('y= g^x mod P=\t\t',y)

contract_step2.py

import libnum
import hashlib
import random
n=8269
g=11

v = random.randint(1,n)

print('\n======Phase 2: Peggy wants to login , She send t to Victor==================')
v = random.randint(1,n)
t = pow(g,v,n)
print('v=',v,'\t(Peggy\'s random value)')
print('t=g**v % n =\t\t',t)

contract_step45.py

import libnum
import hashlib
import random
n=8269
g=11

password = "Hello"
x = int(hashlib.sha256(password.encode()).hexdigest()[:8], 16) % n


print('\n======Phase 4: Peggy recieves c and calculate r=v-cx, sends r to Victor==================')
c = input("c= ")
v = input("v= ")
r = (int(v) - int(c) * x) % (n-1)

print('c=\t\t',c)
print('v=\t\t',v)
print('r=v-cx =\t\t',r)

fiat_shamir_1.py

import sys
import random
import hashlib
import libnum

n=8269
password="Hello"
g= 11

v = random.randint(1,n)
c = random.randint(1,n)


print("Password:\t\t",password)
x = int(hashlib.sha256(password.encode()).hexdigest()[:8], 16) % n
print("Password hash(x):\t",x,"\t (last 8 bits)")


y= pow(g,x,n)

t = pow(g,v,n)

r = (v - c * x) % (n-1)

Result = ( pow(g,r,n) * pow(y,c,n))  % n

print('\n======Phase 0: Agreed parameters============')
print('P=',n,'\t(Prime number)')
print('G=',g,'\t(Generator)')

print('\n======Phase 1: Peggy sends y to Victor,Victor store y with Peggy ==================')
print('y= g^x mod P=\t\t',y)

print('\n======Phase 2: Peggy wants to login , She send t to Victor==================')
print('v=',v,'\t(Peggy\'s random value)')
print('t=g**v % n =\t\t',t)

print('\n======Phase 3: Victor choose c randomly ,and sends it to Peggy==================')
print('c=',c,'\t(Vitor\' random challenge)')

print('\n======Phase 4: Peggy recieves c and calculate r=v-cx, sends r to Victor==================')
print('r=v-cx =\t\t',r)

print('\n======Phase 5: Victor calculates (g^r)*(y^c)== t? ==================')
print('t= % n =\t\t',t)
print('( (g**r) * (y**c) )=\t',Result)
if (t==Result):
	print('\nPeggy has proven she knows password')
else:
	print('\nPeggy has not proven she knows x')

FiatShamir.sol

pragma solidity >=0.4.16 <0.9.0;

contract FiatShamir {
    //============Phase 0: Agreed parameters===================
    // prime
    uint public n = 8269;
    // generator
    uint public g = 11;
    //=========================================================
    
    // g^x mod n
    uint y;
    // Victor's random challenge
    uint public c;
    // peggy sends random t 
    uint t;
    
    //======Phase 1: Peggy sends y to Victor,Victor store y as Peggy' token==================
    // peggy registers with y,  y = g^x mod n
    function Step1_register( uint _y) public {
        y = _y;
    }
    //=======================================================================================
    
    //======Phase 2: Peggy wants to login , She send t to Victor=============================
    function Step2_login(uint _t) public {
        t = _t;
    }
    //=======================================================================================
    
    //======Phase 3: Victor choose c randomly ,and sends it to Peggy=========================
    function Step3_randomchallenge() external returns (uint){
        c = randomgen();
        return c;
    }

    //TODO : NOT secure , low entropy ,change random source.
    function randomgen() private view returns (uint) {
        return uint(keccak256(abi.encodePacked(block.timestamp))) % n;
    }
    //=======================================================================================
    
    //======Phase 4: Peggy recieves c and calculate r=v-cx, sends r to Victor================
    //======Phase 5: Victor calculates (g^r)*(y^c)== t? =====================================
    function Step45_verify(uint r) public  returns (bool){
        uint256 result = 0;
        
        result = (modExp(g,r,n)*modExp(y,c,n)) % n;
        
        return t == result;
    }
    //=======================================================================================
    

    // modular algorithm : calculate  b**e mod m
    function modExp(uint256 _b, uint256 _e, uint256 _m) private returns (uint256 result) {
        assembly {
            // Free memory pointer
            let pointer := mload(0x40)

            // Define length of base, exponent and modulus. 0x20 == 32 bytes
            mstore(pointer, 0x20)
            mstore(add(pointer, 0x20), 0x20)
            mstore(add(pointer, 0x40), 0x20)

            // Define variables base, exponent and modulus
            mstore(add(pointer, 0x60), _b)
            mstore(add(pointer, 0x80), _e)
            mstore(add(pointer, 0xa0), _m)

            // Store the result
            let value := mload(0xc0)

            // Call the precompiled contract 0x05 = bigModExp
            if iszero(call(not(0), 0x05, 0, pointer, 0xc0, value, 0x20)) {
                revert(0, 0)
            }

            result := mload(value)
        }
    }
}