Mechanism to prove UTXO ownership to third-party

[seibelj]

Businesses that use Grin for transactions will have to prove to auditors their current balance, incoming transactions, and outgoing transactions. This is crucial for taxpaying entities to use Grin or any other currency. Other privacy coins such as Monero have this capability through view-only keys and send proofs.

In the gitter chat, @jaspervdm said:

you can prove you are in posession (ie you own UTXOs) of a specific amount, yes, by signing a message with your blinding factor(s). it is however currently not possible with the wallet

Having a wallet feature do this would be ideal, but even without that, the mathematics of how to accomplish this documented would be the bare minimum requirement for a business.

For a third-party auditor with the full blockchain archive synced, the business needs a way to prove these (without giving the third-party the private key):

• Prove current balance (which unspent UTXOs we own)
• Prove incoming transactions (receives)
• Prove outgoing transactions (sends)

Obviously the addresses we receive from or send to don't exist, but the change of UTXO ownership happens in a block height which itself has a timestamp.

[ignopeverell]

To expand a bit on @jaspervdm one line answer, if you recall from the Grin intro doc, a commitment has the form:

C = r*G + v*H

Here, v is the value, r the blinding factor and G and H two elliptic curve point generators. So r*G is the public key derived from the private key r.

The Grin wallet uses a BIP32 key derivation, so you can find all the r used by the wallet easily. Then for each output, sign a message with those r and share it with an auditor, along with the amounts and either each of the r*G or the root pubkey so they can derive them. From there the auditor can check that:

1. You know r that corresponds to r*G, as you were able to produce a valid signature.
2. There is a commitment on chain that's v*H + r*G.

Note that what you sign doesn't matter, as long as you show you can produce a valid signature, it's all good (practically would likely be the empty string).

Now did I mention we gladly accept PRs? :-)

[GandalfThePink]

It does matter what you sign. If you can choose the string to sign it is possible to forge a signature. For simplicity you should probably sign the hash of the Pedersen commitment?

[jaspervdm]

The verifier should pick the message (which should be hashed), to avoid re-use of the signature

[tromp]

for each output, sign a message with those r

this can be done more efficiently by summing the commitments first.

For a set S of outputs, whose commitments sum to C, to prove ownership of S, generate a rangeproof for C + challenge G, where the challenge ensures that prover is not just reusing already published proofs. to prove that S has value v, sign a message with public key C - vH, the message could include a challenge to avoid reuse and prove ownership as well.

[tromp]

Prove outgoing transactions (sends)

Such proofs may not be convincing, since once an output is spent, its owner could leak or reveal its blinding factor, allowing others to "prove" past ownership of that output.

[antiochp]

Such proofs may not be convincing, since once an output is spent, its owner could leak or reveal its blinding factor, allowing others to "prove" past ownership of that output.

Does this imply you really want to prove ownership of the unspent output, prior to spending it?

[tromp]

Yes, proofs of past ownership are not convincing, so proofs of ownership should apply to unspent outputs.

[seibelj]

It may not be 100% convincing but given a large enough sample size it could still prove valuable.

[seibelj]

I propose the following commands for wallet:

wallet sign_message [-m "message"] [-i tx_id] [-f file] Signs the given message with the private key associated with tx_id. If message is not passed, default is SHA256 hash of the Pedersen commitment associated with the tx_id. If tx_id is not passed, private key is wallet seed. If both tx_id and message are not passed, default is to sign the SHA256 hash of the public key associated with the wallet seed. Output is JSON written to file or STDout if file not set. Contents out JSON file is:

{
    "public_key": Array[int], public key used to verify the message,
    "commit": Array[int], tx commitment associated, null if using wallet seed,
    "value": Value of the tx, or null if using wallet seed to sign,
    "message": String, message signed,
    "sig": Array[int]: signature
}

wallet verify_message file Given the output of sign_message, this verifies that everything is accurate

There could also be a command to sign every single UTXO owned by the wallet as a helper function, and a verifier command to verify it, to prove total wallet balance and UTXO ownership.

But any thoughts on this proposal? When I find some free time I can work on this feature.

[ManfredKarrer]

As posted over there (https://github.com/mimblewimble/grin/pull/2374#issuecomment-454522036) Bisq requires such a feature for safe P2P trades!