How pedersen commitments are constructed to hide amounts in Monero's RingCT (simplified)

xmr_pedersen_simplified.py

# The goal with this program is to demonstrate how to construct pedersen
# commitments in similar fashion to how the Monero tx protocol does, but in a hugely
# simplified way (read: not exact, but close), to show how we can prove hidden input
# and output amounts balance.
# Some stuff is left as an exercise to the reader where commented.
# **Corrections are very much so welcome.**
# I encourage anyone who doesn't know much about pedersen commitments to
# go through coinstudent2048's excellent tutorial on elliptic curve 
# cryptography [1] first. And anyone interested in this to first read through
# Zero to Monero v2 chapters 5 and 6 [3].
#
# sources: 
# [1]: https://github.com/coinstudent2048/ed25519_tutorials
# [2]: https://github.com/SarangNoether/skunkworks
# [3]: https://web.getmonero.org/library/Zero-to-Monero-2-0-0.pdf#chapter.5

# get dumb25519 from Sarang's https://github.com/SarangNoether/skunkworks/blob/rct3/rct3-single/dumb25519.py
from dumb25519 import hash_to_point, Scalar, random_scalar, G

H = hash_to_point("Pedersen")

# "Monero cryptocurrency uses Pedersen commitment to hide amounts in the blockchain.
# implement Pedersen commitment: given a scalar x, it must output a pair (r, rG + xH) where r is
# a random scalar. for Monero, r should never be in the blockchain, only the rG + xH is."
# 
# https://github.com/coinstudent2048/ed25519_tutorials/blob/7fa21c7b1dd8d7fea184c552c69f14b6f162f4d1/ed25519_tutorial1.py#L116-L118
def pedersen(amount):
    r = random_scalar()
    rG = r * G
    xH = amount * H
    commitment = rG + xH
    return r, commitment

# exercise: construct pedersen commitments that show (3 + 5) - (1 + 7) == 0, without revealing the amounts.
# The intent is to demonstrate that (sum of the inputs) - (sum of the outputs) == 0, without
# revealing amounts of inputs and outputs. In mathematical terms, we want to show that:
#
#       [(r1 * G + 3 * H) + (r2 * G + 5 * H)] - [(r3 * G + 1 * H) + (r4 * G + 7 * H)] == 0
# or    [(c1 + c2) - (c3 + c4)] == 0

# inputs
r1,c1 = pedersen(Scalar(3))
r2,c2 = pedersen(Scalar(5))

# outputs
r3,c3 = pedersen(Scalar(1))

# Recall that pedersen commitments are additively homomorphic (C(a + b) = C(a) + C(b)),
# which means we can re-arrange the above equation to:
#
#   [(r1 + r2) - (r3 + r4)] * G - [(3 + 5) - (1 + 7)] * H == 0
#   [(r1 + r2) - (r3 + r4)] * G - [(8) - (8)] * H == 0
#   [(r1 + r2) - (r3 + r4)] * G - (0) * H == 0
#   [(r1 + r2) - (r3 + r4)] * G == 0
#   [(r1 + r2) - (r3 + r4)] == 0
#   r4 == (r1 + r2) - r3
#
# We re-arrange the equation in the above way to land on a value for r in the final
# output's commitment that ensures the equation balances.
r4 = (r1 + r2) - r3
c4 = (r4 * G) + (Scalar(7) * H)

# Recall only commitments get sent to the blockchain, not secret r values
if c1 + c2 == c3 + c4:
    print("We constructed commitments that show the sum of the inputs - sum of the outputs == 0")
else:
    print("Something's wrong :(")

# Now, we still need to prove that amounts correspond to commitments (among other things left out of scope).
# Otherwise there is no way for the verifier to know that the prover didn't send over some commitments
# that add up right, but use different amounts, like as follows:

# inputs
r1,c1 = pedersen(Scalar(3))
r2,c2 = pedersen(Scalar(5))

# outputs
r3,c3 = pedersen(Scalar(1))

x4H = Scalar(10000) * H
r4G = (c1 + c2) - c3 - x4H
c4 = r4G + x4H

if c1 + c2 == c3 + c4:
    print("We constructed commitments where the final output is a commitment to a coin with amount 10000")
else:
    print("Something's wrong :(")

# There is one interesting caveat with the 10000 amount output commitment above:
# no one knows that the value for r4 is.
#
# Looking at the equation:
#   r4G = (c1 + c2) - c3 - 10000 * H
#   r4G = <some value we can calculate as above>
#   r4 = r4G / G ... dividing by G is not solvable because DL problem is hard
#
# Written another way:
#   r4G = [(r1 + r2) - r3)] * G + (3 + 5 - 1 - 10000) * H
#   r4 = [(r1 + r2) - r3)] + (-9993) * H / G
#   r4 = <some value we can calculate> - (<some other value we can calculate> / G) ... dividing by G is not solvable because DL problem is hard
#
# Thus, because the discrete logarithm problem is hard, we are unable to determine what the
# value for r4 would be that gets the above construction with a 10000 coin output to balance.
#
# Thus, if we are able to prove that we have knowledge of the secret r values when
# spending an output, then we have sufficiently proven that we know how to get the
# equation to balance, with correct amounts, without revealing those amounts.
# However, revealing r values, or rG values would allow a passive observer to
# determine output amounts, and the scheme wouldn't work.
# Monero solves for this by using what are referred to in Monero land as "psuedo out commitments".
# For each input in a transaction, there exists a commitment in the chain already,
# and at tx construction time, we construct a brand NEW commitment to the same amount referred to
# as a pseudo out commitment. 

# inputs (these already exist in the chain)
r1,c1 = pedersen(Scalar(3))
r2,c2 = pedersen(Scalar(5))

# pseudo output commitments (these are created at tx construction time)
pseudo_r1,pseudo_c1 = pedersen(Scalar(3))
pseudo_r2,pseudo_c2 = pedersen(Scalar(5))

# outputs (created at tx construction time)
r3,c3 = pedersen(Scalar(1))

# We then use the pseudo outs to land on a value for r4, same way as before
r4 = (pseudo_r1 + pseudo_r2) - r3
c4 = (r4 * G) + (Scalar(7) * H)

# The chain verifies the following holds to ensure pseudo out commitments
# balance with output commitments:
if pseudo_c1 + pseudo_c2 == c3 + c4:
    print("sum of (pseudo out commitments) inputs - sum of outputs == 0")
else
    print("Something's wrong :(")

# Now here is the interesting part: there exists a private key "z" for each input, that
# we can use to show that we have knoweldge of the input r1 and r2 values.
z1 = r1 - pseudo_r1
z2 = r2 - pseudo_r2

# The chain verifies the following holds to ensure pseudo out commitments
# balance with input commitments:
if c1 - pseudo_c1 == z1 * G and c2 - pseudo_c2 == z2 * G:
    print("Pseudo out commitments balance with input commitments")
else:
    print("Something's wrong :(")

# Then we prove knowledge of z1 and z2, which is accomplished via a ring signature 
# as described in Zero to Monero 6.2.2. That is left out of scope here.
# Source: https://web.getmonero.org/library/Zero-to-Monero-2-0-0.pdf#subsection.6.2.2

# We also still have to prove all output amounts are in the range [0, 2^64],
# since negative values would allow commitments to balance while printing more
# coin. This is accomplished via range proofs and described in Zero to Monero 5.5.
# Also left out of scope for the reader.
# Source: https://web.getmonero.org/library/Zero-to-Monero-2-0-0.pdf#section.5.5