Proof an output has not been spent

[UkoeHB]

(note: moving this from Issue #58 for proper scope).

We can prove a given key image does NOT correspond with a one-time address from its corresponding ring. The verifier doesn't require the view key, although in an audit environment the view key is likely to be known so the auditor can verify which outputs are owned in the first place. This proof can be used to show an output has not been spent, without leaking its key image which would reveal when it's spent in the future. It can be implemented right now without changing how transactions are constructed.

Preliminary: assume the verifier knows r*K^v, the sender-receiver shared secret for a given owned output with one-time address K^o and transaction public key r*G. He either knows the view key k^v, or the prover provided r*K^v (or created a 2-base proof like below on the base points G and rG with signing key k^v) which allowed the verifier to calculate the owned-output check K^o - H_n(r*K^v,t)*G ?= K^s so he knows the output being tested belongs to the prover. Proof functions H_n() and H_p() create scalars and curve points respectively.

1. For every time an owned output K^o is referenced in the ring of a transaction, take the key image to be tested KI_? of that ring signature.
2. Create a 3-base and a 2-base signature on base keys: a) generator G, spend key K^s, and computed point KI_? - H_n(k_v*rG,t)*H_p(K^o): signing key k^s b) generator G and H_p(K^o): signing key k^s*k^s
3. The verifier checks that a) second key of (a) == first key of (b) b) third key of (a) != second key of (b), or in other words, k^s[KI_? - H_n(k_v*rG,t)*H_p(K^o)] != k^s*k^s*H_p(K^o)

This seemingly roundabout approach prevents the verifier from learning k^s*H_p(K^o), which he could use in combination with the view key to compute the real key image for that output, while leaving him confident that the tested key image doesn't correspond to that output.

In fact, the prover only needs to do proof (a) for each key image to be tested. There should only be on the order of 11 (current ring size) tests per owned output, since that's around how many times an output is likely to be included in rings as decoys.

[SarangNoether]

Proof-of-concept implementation of spend and non-spend status: https://github.com/SarangNoether/skunkworks/tree/audit-proof