Skip to content

Instantly share code, notes, and snippets.

Last active November 17, 2021 03:42
What would you like to do?
Seraphis Transaction Protocol
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!
- 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.
- 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 }.
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]
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](
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:
- 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>
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
- 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})]
- existing RingCT cryptos don't need new user addressing scheme
- 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment