[navcoin-dev] How to prove a Kernel Hash target has been met with ZeroCT?

[Alex Vazquez <alex@xxxxxxxxxxxxx>]

Definitions:

K(in) returns the Kernel Hash of the input ’in’.
v_in is the value in navoshis (64bit integer) of the output ‘in’ being spent in the stake.
T(height) returns the target for a kernel hash to be met at a determined height. This is commonly considered the ‘difficulty’ at the height ‘height'.

The eligibility of a staker in the POS model used currently in NavCoin is determined by following condition:

K(in) < T(height) * v_in

This can be rewritten as:

(K(in) * v_in^-1) < T(height)		 [1]

When using ZeroCT and in the case where the input spends an output which value is obfuscated, v_in is hidden as a committed value in W=g2^v_in g*r. So the maths are not going to be that straightforward.

Before starting, let’s remember how we can prove a commitment c3 is the product of the numbers hidden in other two commitments c1 and c2.

c1 = g2^v1 * g^r1
c2 = g2^v2 * g^r2
c3 = g2^v3 * g^r3 = g2^(v1 * v2) * g^r3

We want to prove the relationship v3 = v1 * v2 without revealing anything about v1, v2 or v3.

Let’s rewrite c3 as:

c3' = c1^v2 * g(r3 - r1 * v2)

We can see c3' is equal to c3:

c1^v2 * g(r3 - r1 * v2) = g2^(v1 * v2) * g^(r1 * v2 + r3 - r1 * v2) = g2^(v1 * v2) * g^(r3) = c3

If we are able to prove the opening of the commitments c1 and c2 using a standard scheme as Schnorr, we will be able to prove that c3 commits to the product of the values committed in c1 and c2 by proving the opening of c3 reusing the challenge/response used for proving c2’s opening and after changing the base g2 to c1.

Using this definitions, first of all, the staker will need to publish a commitment to the inverse of v_in Winv=g2^(v_in^-1) * g^r2 and prove that W and Winv commit to factors of 1 (v_in * v_in^-1 = 1) using the technique previously described. That would be equivalent to considering W, Winv resp. c1, c2, and defining c3 as g2^1 * g^r3. C3’s structure can easily be proven by proving knowledge of h’s exponent r3 for public key c3 * g2^-1 = g^r3.

Let's calculate now a commitment to K(in) * v_in^-1:

c4 = Winv ^ K(in) = g2^(v_in^-1 * K(in)) * g^r3

As per the condition defined above [1], we now need to prove c4’s committed value is in the range [0, T(height)). If we accept (2^64) - 1 is the biggest possible value v_in can take, we can safely assume v_in^-1 * K(in) will always be greater or equal than K(in) / ((2*64) - 1), hence in the range [K(in) / ((2*64) - 1), T(height)). We can further simplify the range by defining it as [0, T(height) - K(in) / ((2*64) - 1)) and multiplying c4 by g2^(-K(in) / ((2*64) - 1)).

This range proof can easily be done using bulletproofs.

Best,

Alex
--
To unsubscribe send a mail to navcoin-dev+unsubscribe@nav.community