Knowledge Commitments With Polynomials

Knowledge Commitments With Polynomials

Do you remember polynomials at school? I hope so because the world of privacy and security is built on these algebraic structures. They are the basis of the AES methods and for lattice methods.

Now, let’s see if we can use them to show a commitment to the knowledge of something. For this, we need a puzzle for someone to solve and then commit to their answer. Ron Rivest defined this a while ago with a game of mental poker, where two players could play a game of poker without needing a trusted person to deal or check their cards [1]:

So, let’s say that Peggy (the Prover) wants to prove to Victor (the Verifier) that she knows the answer to something. For this, we might use the polynomial of:

f(x)=5x³+x²+6

The coefficients of this polynomial are then [5,1,0,6]. Now, Victor asks for f(x=2), and Peggy generates:

f(2)=5*8+4+6 = 50

Peggy then sends this and also a root Merkle Hash of the polynomial she has used [here]:

Method:  sha256
[ 5 ] [ 1 ] [ 0 ] [ 6 ] 

== Leafs == 
1 ef2d127de37b942baad06145e54b0c619a1f22327b2ebbcfbec78f5564afe39d
2 6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b
3 5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9
4 e7f6c011776e8db7cd330b54174fd76f7d0216b612387a5ffcfb81e6f0919683


== States == 
1 ef2d127de37b942baad06145e54b0c619a1f22327b2ebbcfbec78f5564afe39d
2 44d0911ffb57370d57467ef53b6471856da71ab1af35b3732844e71ebfd1050d
3 4c731fa04ff5c866ff0a7d5d0985f3fb552aaec2afc5fc4ea1e86d3968cb91c5
4 2883851812cce5b2fe54e181937ed563c1e59fd35bd32fec043eb24f01053dcc

Root:  2883851812cce5b2fe54e181937ed563c1e59fd35bd32fec043eb24f01053dcc

In this case, we see for [‘5’,’1',’0',’6'] with a SHA-256 hash, we get a root hash of 2883851812cce5b2fe54e181937ed563c1e59fd35bd32fec043eb24f01053dcc. Peggy thus makes a commitment to the answer and also the problem she is solving. She now cannot cheat with the answer. Victor then checks the commitment and the answer, and if they tally, he knows that Peggy knows the polynomial used. Eve, though, is scratching her head — trying to work out what Peggy did.

The code used is:

from pymerkle import InmemoryTree
import sys

import hashlib

vals=["5","1","0","6"]
hash='sha256'
if (len(sys.argv)>1):
    v=sys.argv[1]
    vals = eval(v)

if (len(sys.argv)>2):
    hash=str(sys.argv[2])
  
# sha224, sha256, sha384, sha512, sha3_224, sha3_256, sha3_384, sha3_512
# keccak_224, keccak_256, keccak_384, keccak_512

print("Method: ",hash)

tree = InmemoryTree(algorithm=hash,disable_security=True)

for e in vals:
    print("[",e,"]",end=" ")
    index = tree.append_entry(str(e).encode('utf-8'))


print("\n\n== Leafs == ")
for i in range(1,index+1):
    print(i,tree.get_leaf(i).hex())

print("\n\n== States == ")
for i in range(1,index+1):
    print(i,tree.get_state(i).hex())

state = tree.get_state()

print("\nRoot: ",state.hex())
print("Root: ",state)

Conclusions

This is a very simple method and can be expanded into the Kate (“kay-tey”) commitment — KZG polynomial commitment. I will cover this in a future article. For just now, here are some Merkle Trees:

https://asecuritysite.com/merkle

Reference

[1] A. Shamir, R.L. Rivest and L.M. Adleman, “Mental Poker,” MIT/LCS/TM-125, Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, February 1979