Seraphis Transaction Protocol

Seraphis_TxProtocol.txt

Seraphis [Serapis, syncretistic deity, brings together many ideas and cultures]
    - WARNING: unproven protocol, do NOT implement this until/unless there is a well-reviewed professional-grade research paper!

Summary:
    - Seraphis is a RingCT-like abstract transaction protocol.
        - It defines properties for various proofs, but does not require any specific construction.
        - A concrete instantiation of Seraphis must define proof constructions that satisfy those properties.
    - Compared to RingCT, proofs of ownership and double spend proofs are 'outside' of the membership proof (e.g. ring signature).
        - This allows the membership proof itself to be more efficient, potentially enough for arbitrarily large anonymity sets.
    - Introduces a new addressing/key image scheme to solve long-standing issues with the Cryptonote style that were blocking/inhibiting research efforts into better next-gen protocols.

Notation:
    - In the term 'k^v', for example, 'v' is a superscript. This document has no exponents, only superscripts.
    - In the term .G, the dot represents 'any scalar', and the capital letter is an EC curve point.
    - Lower-case letters are EC group scalars.
    - Scalar-point multiplication has the form: x G, for scalar 'x' and EC point 'G'.
    - H() is an arbitrary hash function (e.g. SHA256, Blake2b).
        - Assume that in most/all cases the hash function should be 'domain separated' with a use-case-specific string.
    - Represent a set of points: [S] = { S_1, S_2, ..., S_n }.

Generators:
    U [for one-time address and key image]
    G [for commitments of form .G + P (for any point P)]
    H [for Pedersen commitment to amount 'a': x G + a H]

Points:
    K^o = k^o_a U + k^o_b G
        - one-time address; must prove knowledge of k^o to spend output
        - NEW ADDRESSING APPROACH (inspired by discussion with sarang [and aram, indirectly :p])
            - essential form for privacy vs senders (needs security proof?)
                K^o = (k^o_{a,sender} + k^o_{a,recipient}) U + k^o_{b,recipient} G
                k^o_{a,sender}: known by sender and recipient
                k^o_{a,recipient}, k^o_{b,recipient}: known by recipient
                KI = 1 / (k^o_{a,sender} + k^o_{a,recipient}) G

                - enables key image of form k^i U that:
                    - is friendly to multisig if private spend key is k^o_{b,recipient} (not used in key images)
                    - does not allow sender to link key images no matter how many times they sent to the same person

            - variant 1: CryptoNote style with 3-tier permissions
                k^s [private spend key]
                k^vs [private view-spent key]
                k^vr [private view-received key]

                K^s     = k^vs U + k^s G      [normal address spend key]
                K^{s,i} = H(k^vr, i) U + K^s  [subaddress spend key]

                K^v     = k^vr G       [normal address view key]
                K^{v,i} = k^vr K^{s,i} [subaddress view key]

                K^o = H(r K^v) U + K^s     [normal address]
                k^o_{a,sender} = H(r K^v)
                k^o_{a,recipient} = k^vs
                k^o_{b,recipient} = k^s
                k^i = 1/(H(r K^v) + k^vs)

                K^o = H(r K^{v,i}) U + K^{s,i}  [subaddress]
                k^o_{a,sender} = H(r K^{v,i})
                k^o_{a,recipient} = H(k^vr, i) + k^vs
                k^o_{b,recipient} = k^s
                k^i = 1/(H(r K^{v,i}) + H(k^vr, i) + k^vs)

                - compared to RingCT:
                    - output construction is only slightly different: generator U replaces G in K^o from sender's perspective
                    - wallet adddress: {K^v, K^s}
                    - wallets can have 3 permission tiers
                        - tier 1: view received outputs
                            - wallet knows: {K^s, k^vr}
                            - can recompute all subaddresses, can identify owned outputs
                        - tier 2: full balance recovery
                            - wallet knows: {K^s, k^vs, k^vr}
                            - tier 1 + can compute key images
                        - tier 3: full balance recovery + spend authority
                            - wallet knows: {k^s, k^vs, k^vr}
                            - tier 2 + can spend outputs
                        - note: a wallet with only k^vs is not very useful because k^vr is also needed to compute key images
                        - recommended: k^vs = k^v; k^vr = H("view-received", k^v)
                            - practical challenge: existing RingCT implementations have k^v with only k^vr capabilities; allowing it to have k^vs capabilities as well may violate user assumptions around view-only wallets
                                - alternative: k^vs = H("view-spent", k^s); k^vr = k^v
                        - concern: allowing a non-spend private key to have view-spent capabilities may mean outsiders will expect/demand access to that key for auditing/monitoring purposes, which would increase the 'amount of access outsiders can demand' compared to current CryptoNote-based protocols
                            - recommend: do not give other people any of your private keys as a policy
                            - extreme measure: set k^vs = k^s to eliminate the special view-spent capability; outsiders cannot reasonably demand k^s (spend authority cannot be reasonably demanded)

            - variant 2: variant 1 with [Janus mitigation](https://github.com/monero-project/research-lab/issues/62#issuecomment-870147617)
                K^a = k^vr G                  [normal address ancillary key]
                K^{a,i} = H(k^vr, i) G + K^a  [subaddress ancillary key]

                K^v     = k^vr K^a     [normal address view key]
                K^{v,i} = k^vr K^{a,i} [subaddress view key]

                - wallet address {K^v, K^a, K^s}
                - txout pub key: R = r K^a
                    - note: need one txout pub key per output
                - commitment blinding factor: y = H(r K^v, r G)
                    - Janus test: compute r G = (1/k^a) R, reconstruct commitment, if reconstruction fails then the output is malformed (either due to Janus failure or something else)
                        - note: this may not detect malformed outputs right away in a Fog context if the full commitment is not known, BUT it will be detected when trying to spend the output because tx construction will fail
                - permission tiers are the same as variant 1 (except now tier 1 can detect Janus attacks)

    C = x G + a H
        - amount commitment (amount 'a')
    K' = v_1 G + K^o
        - pseudo-output address; hides original address during ownership and unspentness proofs
    C' = v_2 G + C
        - pseudo-output commitment (amount 'a'); hides commitment of amount being spent during balance check

    k^i = (1 / k^o_a)
        - key image private key
    KI = k^i G
        - key image


Tx protocol
    - inputs: [<K', C'>], commitments to the outputs to spend
        - membership proof: proof that keys in <K', C'> are commitments to zero with respect to G for an output <K^o, C> in a subset of on-chain outputs
        - ownership proof: proof of knowledge of k^o
        - output is unspent proof: proof KI is constructed from K^o, expect KI unique on-chain
        - data
            - membership proofs { undefined }
            - ownership & unspent proofs { dual-proof: K' composition proof & KI signature }
            - [K'], [C'], [KI]
                - torsion element problem: store (1/8)*KI, mul8 at start of verification (or use Ristretto)
    - outputs
        - amount balance proof: sum(pseudo output commitments) ?= sum(output commitments) + fee commitment (f H)
        - range proof for oblivious amounts: range proof on commitment C^output
        - data
            - amount range proofs { C^output range proof }
            - outputs { K^o, C^output, encoded amount, txout pub key }
    - misc
        - fee amount: f
        - coin-specific protocol details (e.g. tombstone block in mobilecoin, unlocktime in monero)
        - memos


Proof properties

1. membership proof
    - given
        - pair <K', C'>
        - set of pairs [S], where S = <K^o, C>
    - prove that the following holds for some S in [S], do not reveal which one it is
        - DL proof: K' - K^o, base G
        - DL proof: C' - C, base G 

    - broken if: S is known to be in [S]', where [S]' is a strict subset of [S] - (outputs known by adversary)

    - examples
        - a trivial solution is a CSAG signature on the ring { K' - K^o_i, C' - C_i }, signing on base point G with keys <v_1, v_2>
        - an advanced solution would be a Groth/Bootle-style parallel one-of-many proof
        - a best solution should scale to arbitrary anon set sizes
            - one possibility is a ZCash-style circuit on a Merkle or Verkle proof for leaf nodes H(K^o, C)
                - Verkle proofs: https://vitalik.ca/general/2021/06/18/verkle.html


    - theoretical optimization: squashed outputs

        S = H(K^o, C) K^o + C
            - squashed output; computed by nodes when a block is added to the blockchain
        Q = v G + S
            - squashed output commitment; hides output being spent by a tx; must be proven to correspond to an output that exists on-chain
        invariant: Q == K' + C'
            - set v = v_1 + v_2

        K' = v_1 G + H(K^o, C) K^o
            - modified version of pseudo-output address
            - prefixing prevents 'amount leakage' between K^o and C

        - must prove legitimacy of pseudo-output commitment
            - prove composition of C', and that amount 'a' is in-range

            range proof: C' = (v_2 + x) G + a H
                - if K^o contains an H component to alter 'a', then H(K^o, C) will randomize that component in 32 bytes
                    - K^o = K^o_real + H(K^o, C)*e H
                        - K' = v_1 G + K^o_real
                        - C' = v_2 G + C + H(K^o, C)*e H = (v_2 + x) G + (a + H(K^o, C)*e) H
                    - since range proofs limit amounts to 8 bytes, the chance 'a + H(K^o, C)*e' can be bulletproofed is 1 in ~23 bytes
                        - ed25519 has 16-byte security for the DLP (e.g. between generators G and H), so at first glance this approach does not weaken amount balance security
                - range proofing here also proves C' has form .G + .H
                    - no 'U' component leakage (could double-spend arbitrary times)
                    - if 'G' component leakage, then DL is proven anyway (otherwise view key holder could sign transactions)

        - note: the value H(K^o, C) is present in key images, a difference from the base protocol
            KI = 1/(H(K^o, C)*k^o_a) G

        - reason to do this: constructing/verifying the membership proof may be simpler/faster
            - instead of a CSAG, do a SAG signature on the ring { Q - S_i }, signing on base point G with key v
            - instead of a parallel Grootle proof, do a simpler proof (faster to verify)

        - reason not to do this: pseudo-output commitment amounts security model different than in normal RingCT

2. range proof
    - given EC point C
    - prove that C has form '.G + a H'
    - prove that '0 <= a < 2^64'

    - examples:
        - bulletproofs+
        - old proof types (Monero's history): bulletproofs, borromean sigs


Validation steps (main points)

1. membership proof for input <K', C'>, given set [S] of pairs <K^o, C>

    undefined

2. proof of knowledge of k^o, double spend proof
    - broken if: K^o can be extracted, 'k^o' is not legit (i.e. signer doesn't know k^o_a and/or k^o_b), can make multiple KI from one K^o

    - prove composition of K' is .G + .U, construct the key image by folding out k^i

    DL proof (dual-base):
        - pubkeys: (1/k^o_a) K', KI
        - bases: K', G
        - privkey: 1/k^o_a

    DL proof:
        - pubkey: (1/k^o_a) K' - U
        - base: G
        - privkey: (v_1 + k^o_b)/k^o_a

    - knowledge of k^i (proven by ability to remove U component of K' and ability to sign on G) implies knowledge of k^o
    - key image KI = k^i G is an 'image' of the address that owns the output, because k^i = 1/k^o_a

3. proof of amount balance

    expect: sum(C') == sum(C^output) + f H

    - set pseudo-commitment blinding factors (v_2 values) so the balance works out
        - for all inputs
            - v_1 = rand()
            - if last input
                - v_2 = sum(y) - sum(v_2 + x)_{except last} - x_last
            - else
                - v_2 = rand()

4. amount range proof for new outputs

    range proof: C^output
        - guarantees C^output has form: y G + b H, 'b' is in-range


Scaling (example instantiation)

- inputs:
    - 2x scalar (1x challenge, 1x response, all input proofs combined in merged Schnorr proof)
        - response is for CLSAG-style merge on all signatures, for common base point G
        - or do a vector knowledge proof (probably equivalent time/space, may be easier/existing security proof)
    = 64 bytes per tx

    - 3x pub keys (K', C', KI)
    - composition proofs (un-compressible signatures [no common base point for CLSAG-style merging])
        - 1x pub keys ((1/[H(K^o, C) * k^o_a]) K')
            - based on the squashed output approach; otherwise there is no H(K^o, C) term
        - 1x scalars (1x responses)
    = 5 * 32 = 160 bytes per input

- membership proofs (150 - 1000 bytes???)
    - SAG: 11 ring members
        - (squashed and non-squashed) 384 bytes
    - Grootle: 64-1024 ring members; for n^m -> 2^m ring size
        - (squashed; m*n + 7) 608-864 bytes
        - (non-squashed; m*(n+1) + 8) 832-1216 bytes

- range proofs
    - aggregate bulletproofs+ (all C', C^output assuming squashed output approach)
        - size = (2 * ceil(log2(64 * (num terms))) + 6) * 32 bytes
        - 1in-1out
            - (squashed) 640 bytes
            - (non-squashed) 576 bytes
        - 16in-16out
            - (squashed) 896 bytes
            - (non-squashed) 832 bytes

- outputs
    - 3x pub keys (K^o, C^output, txout pub key)
    - 1x u8 (encoded amount)
    - 1x pub keys (S; constructed by nodes)
        - only needed by squashed output approach
    = 136 bytes per output

- misc
    - 1x u8 (fee)
    = 8 bytes per tx

tx size
    - 1in-1out
        - (squashed): 1008 + (1x membership proof) bytes
        - (non-squashed): 912 + (1x membership proof) bytes
    - 16in-16out
        - (squashed) 5702 + (16x membership proofs) bytes
        - (non-squashed): 5128 + (16x membership proofs) bytes

- other (optional)
    - 1x u1 (view tag)
    = 1 byte per output

    - 2x pub keys (encrypted fog hint: random pub key, encrypted view key)
    = 64 bytes per output

    - 1x 16-byte nonce (encoded txout priv key entropy, for Janus mitigation)
        - alternative: addressing variant 2
    = 16 bytes per output

    - 1x u8 (tombstone block)
    = 8 bytes per tx

    - 1x varint (unlock time)
    = 4-8 bytes per tx

    - 1x 34-66 (encrypted output memo)
    = 34-66 bytes per output


Other

- transaction chaining: make a tx that spends an output that doesn't exist on-chain, submit the tx after the output is added to the chain
    - don't sign membership proofs in ownership/unspentness DL proofs
    - construct all of a tx EXCEPT membership proofs
    - cache v_1 and v_2, complete membership proofs at an arbitrary later date


Alternate protocol

- Ko = k_{a,sender,1} G + k_{b,recipient} G
    - e.g. normal one-time address, e.g. Ko = H(r Kv) G + Ks
- C = x G + a H
    - normal amount commitment for amount 'a' (must have a range proof)
- Q = H(Ko,C) Ko + C
    - squash (input)
- Q' = v_c G + Q
    - blinded squash (part of e-note-image)

- K_DH = k_DH * G
    - in Monero style...
        - K_DH = G IF normal address
        - K_DH = K^{s,i} IF subaddress
- Kt = k_{a,sender,2} X + K_DH
- Kt' = v_t X + Kt
- Kp = k_{a,sender,3} K_DH + k_{a,recipient} K_DH
    - normal address: k_{a,recipient} K_DH = kv * G
    - subaddress: k_{a,recipient} K_DH = kv * K^{s,i}
- Kp' = v_p X + Kp

- KI = [k_DH/(k_{a,sender,3}+ k_{a,recipient})] * G

membership proof DLs:
    - Q' - Q    vs. G
    - Kt' - Kt  vs. X
    - Kp' - Kp  vs. X

ownership proof:
    - range proof Q'

unspentness proof:
    - dual DL
        - pubkeys: [1/(k_{a,sender,3} + k_{a,recipient})] * Kp', [1/(k_{a,sender,3} + k_{a,recipient})] * Kt'
        - basekeys: Kp', Kt'
        - privkey: [1/(k_{a,sender,3} + k_{a,recipient})]
    - DL
        - pubkey: [1/(k_{a,sender,3} + k_{a,recipient})] * Kp' - Kt'
        - basekey: X
        - privkey: [v_p/(k_{a,sender,3} + k_{a,recipient})] - (v_t + k_{a,sender,2})
    - DL
        - pubkey: [1/(k_{a,sender,3} + k_{a,recipient})] * Kt' - KI
        - basekey: X
        - privkey: [(v_t + k_{a,sender,2})/(k_{a,sender,3} + k_{a,recipient})]
    - DL
        - pubkey: KI
        - basekey: G
        - privkey: [k_DH/(k_{a,sender,3} + k_{a,recipient})]

pros
    - existing RingCT cryptos don't need new user addressing scheme
cons
    - less efficient than Seraphis (with the same assumptions - i.e. squashed or not squashed), less efficient than Triptych
        - both tx size and tx verification time
    - private view key can construct linking tags, for full balance recovery; it's a 'con' because existing view-only wallets will have expanded capabilities, which may be undesirable
        - however, current view-only wallets can identify most spent outputs via change outputs (cross-reference owned output set with rings in any tx where you receive a possible change output; if all rings contain one owned output, then the owned outputs in those rings are almost definitely spent)
        - as a consequence, there are only 2 possible wallet tiers: balance recovery, balance recovery + spend authority
    - similar to the 'squashed e-note' approach, but non-trivially less efficient than Seraphis+squashed (two commitments to zero in membership proof vs only one)


License: public domain