378 lines
15 KiB
Plaintext
378 lines
15 KiB
Plaintext
; Coins locked with this puzzle are spendable ccs.
|
|
;
|
|
; Choose a list of n inputs (n>=1), I_1, ... I_n with amounts A_1, ... A_n.
|
|
;
|
|
; We put them in a ring, so "previous" and "next" have intuitive k-1 and k+1 semantics,
|
|
; wrapping so {n} and 0 are the same, ie. all indices are mod n.
|
|
;
|
|
; Each coin creates 0 or more coins with total output value O_k.
|
|
; Let D_k = the "debt" O_k - A_k contribution of coin I_k, ie. how much debt this input accumulates.
|
|
; Some coins may spend more than they contribute and some may spend less, ie. D_k need
|
|
; not be zero. That's okay. It's enough for the total of all D_k in the ring to be 0.
|
|
;
|
|
; A coin can calculate its own D_k since it can verify A_k (it's hashed into the coin id)
|
|
; and it can sum up `CREATE_COIN` conditions for O_k.
|
|
;
|
|
; Defines a "subtotal of debts" S_k for each coin as follows:
|
|
;
|
|
; S_1 = 0
|
|
; S_k = S_{k-1} + D_{k-1}
|
|
;
|
|
; Here's the main trick that shows the ring sums to 0.
|
|
; You can prove by induction that S_{k+1} = D_1 + D_2 + ... + D_k.
|
|
; But it's a ring, so S_{n+1} is also S_1, which is 0. So D_1 + D_2 + ... + D_k = 0.
|
|
; So the total debts must be 0, ie. no coins are created or destroyed.
|
|
;
|
|
; Each coin's solution includes I_{k-1}, I_k, and I_{k+1} along with proofs that each is a CC.
|
|
; Each coin's solution includes S_{k-1}. It calculates D_k = O_k - A_k, and then S_k = S_{k-1} + D_{k-1}
|
|
;
|
|
; Announcements are used to ensure that each S_k follows the pattern is valid.
|
|
; Announcements automatically commit to their own coin id.
|
|
; Coin I_k creates an announcement that further commits to I_{k-1} and S_{k-1}.
|
|
;
|
|
; Coin I_k gets a proof that I_{k+1} is a CC, so it knows it must also create an announcement
|
|
; when spent. It checks that I_{k+1} creates an announcement committing to I_k and S_k.
|
|
;
|
|
; So S_{k+1} is correct iff S_k is correct.
|
|
;
|
|
; Coins also receive proofs that their neighbors are ccs, ensuring the announcements aren't forgeries, as
|
|
; inner puzzles are not allowed to use `CREATE_COIN_ANNOUNCEMENT`.
|
|
;
|
|
; In summary, I_k generates an announcement Y_k (for "yell") as follows:
|
|
;
|
|
; Y_k: hash of I_k (automatically), I_{k-1}, S_k
|
|
;
|
|
; Each coin ensures that the next coin's announcement is as expected:
|
|
; Y_{k+1} : hash of I_{k+1}, I_k, S_{k+1}
|
|
;
|
|
; TLDR:
|
|
; I_k : coins
|
|
; A_k : amount coin k contributes
|
|
; O_k : amount coin k spend
|
|
; D_k : difference/delta that coin k incurs (A - O)
|
|
; S_k : subtotal of debts D_1 + D_2 ... + D_k
|
|
; Y_k : announcements created by coin k commiting to I_{k-1}, I_k, S_k
|
|
;
|
|
; All conditions go through a "transformer" that looks for CREATE_COIN conditions
|
|
; generated by the inner solution, and wraps the puzzle hash ensuring the output is a cc.
|
|
;
|
|
; Three output conditions are prepended to the list of conditions for each I_k:
|
|
; (ASSERT_MY_ID I_k) to ensure that the passed in value for I_k is correct
|
|
; (CREATE_COIN_ANNOUNCEMENT I_{k-1} S_k) to create this coin's announcement
|
|
; (ASSERT_COIN_ANNOUNCEMENT hashed_announcement(Y_{k+1})) to ensure the next coin really is next and
|
|
; the relative values of S_k and S_{k+1} are correct
|
|
;
|
|
; This is all we need to do to ensure ccs exactly balance in the inputs and outputs.
|
|
;
|
|
; Proof:
|
|
; Consider n, k, I_k values, O_k values, S_k and A_k as above.
|
|
; For the (CREATE_COIN_ANNOUNCEMENT Y_{k+1}) (created by the next coin)
|
|
; and (ASSERT_COIN_ANNOUNCEMENT hashed(Y_{k+1})) to match,
|
|
; we see that I_k can ensure that is has the correct value for S_{k+1}.
|
|
;
|
|
; By induction, we see that S_{m+1} = sum(i, 1, m) [O_i - A_i] = sum(i, 1, m) O_i - sum(i, 1, m) A_i
|
|
; So S_{n+1} = sum(i, 1, n) O_i - sum(i, 1, n) A_i. But S_{n+1} is actually S_1 = 0,
|
|
; so thus sum(i, 1, n) O_i = sum (i, 1, n) A_i, ie. output total equals input total.
|
|
;
|
|
; QUESTION: do we want a secondary puzzle that allows for coins to be spent? This could be good for
|
|
; bleaching coins (sendable to any address), or reclaiming them by a central authority.
|
|
;
|
|
|
|
;; GLOSSARY:
|
|
;; mod-hash: this code's sha256 tree hash
|
|
;; genesis-coin-checker: the function that determines if a coin can mint new ccs
|
|
;; inner-puzzle: an independent puzzle protecting the coins. Solutions to this puzzle are expected to
|
|
;; generate `AGG_SIG` conditions and possibly `CREATE_COIN` conditions.
|
|
;; ---- items above are curried into the puzzle hash ----
|
|
;; inner-puzzle-solution: the solution to the inner puzzle
|
|
;; prev-coin-bundle: the bundle for previous coin
|
|
;; this-coin-bundle: the bundle for this coin
|
|
;; next-coin-bundle: the bundle for next coin
|
|
;; prev-subtotal: the subtotal between prev-coin and this-coin
|
|
;;
|
|
;; coin-info: `(parent_id puzzle_hash amount)`. This defines the coin id used with ASSERT_MY_COIN_ID
|
|
;; coin-bundle: the cons box `(coin-info . lineage_proof)`
|
|
;;
|
|
;; and automatically hashed in to the announcement generated with CREATE_COIN_ANNOUNCEMENT.
|
|
;;
|
|
|
|
(mod (mod-hash ;; curried into puzzle
|
|
genesis-coin-checker ;; curried into puzzle
|
|
inner-puzzle ;; curried into puzzle
|
|
inner-puzzle-solution ;; if invalid, inner-puzzle will fail
|
|
prev-coin-bundle ;; used in this coin's announcement, prev-coin ASSERT_COIN_ANNOUNCEMENT will fail if wrong
|
|
this-coin-bundle ;; verified with ASSERT_MY_COIN_ID
|
|
next-coin-bundle ;; used to generate ASSERT_COIN_ANNOUNCEMENT
|
|
prev-subtotal ;; included in announcement, prev-coin ASSERT_COIN_ANNOUNCEMENT will fail if wrong
|
|
)
|
|
|
|
;;;;; start library code
|
|
|
|
(include condition_codes.clvm)
|
|
|
|
(defmacro assert items
|
|
(if (r items)
|
|
(list if (f items) (c assert (r items)) (q . (x)))
|
|
(f items)
|
|
)
|
|
)
|
|
|
|
;; utility function used by `curry_args`
|
|
(defun fix_curry_args (items core)
|
|
(if items
|
|
(qq (c (q . (unquote (f items))) (unquote (fix_curry_args (r items) core))))
|
|
core
|
|
)
|
|
)
|
|
|
|
; (curry_args sum (list 50 60)) => returns a function that is like (sum 50 60 ...)
|
|
(defun curry_args (func list_of_args) (qq (a (q . (unquote func)) (unquote (fix_curry_args list_of_args (q . 1))))))
|
|
|
|
;; (curry sum 50 60) => returns a function that is like (sum 50 60 ...)
|
|
(defun curry (func . args) (curry_args func args))
|
|
|
|
(defun is-in-list (atom items)
|
|
;; returns 1 iff `atom` is in the list of `items`
|
|
(if items
|
|
(if (= atom (f items))
|
|
1
|
|
(is-in-list atom (r items))
|
|
)
|
|
0
|
|
)
|
|
)
|
|
|
|
;; hash a tree with escape values representing already-hashed subtrees
|
|
;; This optimization can be useful if you know the puzzle hash of a sub-expression.
|
|
;; You probably actually want to use `curry_and_hash` though.
|
|
(defun sha256tree_esc_list
|
|
(TREE LITERALS)
|
|
(if (l TREE)
|
|
(sha256 2 (sha256tree_esc_list (f TREE) LITERALS) (sha256tree_esc_list (r TREE) LITERALS))
|
|
(if (is-in-list TREE LITERALS)
|
|
TREE
|
|
(sha256 1 TREE)
|
|
)
|
|
)
|
|
)
|
|
|
|
;; hash a tree with escape values representing already-hashed subtrees
|
|
;; This optimization can be useful if you know the tree hash of a sub-expression.
|
|
(defun sha256tree_esc
|
|
(TREE . LITERAL)
|
|
(sha256tree_esc_list TREE LITERAL)
|
|
)
|
|
|
|
; takes a lisp tree and returns the hash of it
|
|
(defun sha256tree1 (TREE)
|
|
(if (l TREE)
|
|
(sha256 2 (sha256tree1 (f TREE)) (sha256tree1 (r TREE)))
|
|
(sha256 1 TREE)))
|
|
|
|
;;;;; end library code
|
|
|
|
;; return the puzzle hash for a cc with the given `genesis-coin-checker-hash` & `inner-puzzle`
|
|
(defun cc-puzzle-hash ((mod-hash mod-hash-hash genesis-coin-checker genesis-coin-checker-hash) inner-puzzle-hash)
|
|
(sha256tree_esc (curry mod-hash mod-hash-hash genesis-coin-checker-hash inner-puzzle-hash)
|
|
mod-hash
|
|
mod-hash-hash
|
|
genesis-coin-checker-hash
|
|
inner-puzzle-hash)
|
|
)
|
|
|
|
;; tweak `CREATE_COIN` condition by wrapping the puzzle hash, forcing it to be a cc
|
|
;; prohibit CREATE_COIN_ANNOUNCEMENT
|
|
(defun-inline morph-condition (condition lineage-proof-parameters)
|
|
(if (= (f condition) CREATE_COIN)
|
|
(list CREATE_COIN
|
|
(cc-puzzle-hash lineage-proof-parameters (f (r condition)))
|
|
(f (r (r condition)))
|
|
)
|
|
(if (= (f condition) CREATE_COIN_ANNOUNCEMENT)
|
|
(x)
|
|
condition
|
|
)
|
|
)
|
|
)
|
|
|
|
;; tweak all `CREATE_COIN` conditions, enforcing created coins to be ccs
|
|
(defun morph-conditions (conditions lineage-proof-parameters)
|
|
(if conditions
|
|
(c
|
|
(morph-condition (f conditions) lineage-proof-parameters)
|
|
(morph-conditions (r conditions) lineage-proof-parameters)
|
|
)
|
|
()
|
|
)
|
|
)
|
|
|
|
;; given a coin triplet, return the id of the coin
|
|
(defun coin-id-for-coin ((parent-id puzzle-hash amount))
|
|
(sha256 parent-id puzzle-hash amount)
|
|
)
|
|
|
|
;; utility to fetch coin amount from coin
|
|
(defun-inline input-amount-for-coin (coin)
|
|
(f (r (r coin)))
|
|
)
|
|
|
|
;; calculate the hash of an announcement
|
|
(defun-inline calculate-annoucement-id (this-coin-info this-subtotal next-coin-info)
|
|
; NOTE: the next line containts a bug, as sha256tree1 ignores `this-subtotal`
|
|
(sha256 (coin-id-for-coin next-coin-info) (sha256tree1 (list this-coin-info this-subtotal)))
|
|
)
|
|
|
|
;; create the `ASSERT_COIN_ANNOUNCEMENT` condition that ensures the next coin's announcement is correct
|
|
(defun-inline create-assert-next-announcement-condition (this-coin-info this-subtotal next-coin-info)
|
|
(list ASSERT_COIN_ANNOUNCEMENT
|
|
(calculate-annoucement-id this-coin-info
|
|
this-subtotal
|
|
next-coin-info
|
|
)
|
|
)
|
|
)
|
|
|
|
;; here we commit to I_{k-1} and S_k
|
|
(defun-inline create-announcement-condition (prev-coin-info prev-subtotal)
|
|
(list CREATE_COIN_ANNOUNCEMENT
|
|
(sha256tree1 (list prev-coin-info prev-subtotal))
|
|
)
|
|
)
|
|
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
|
|
|
;; this function takes a condition and returns an integer indicating
|
|
;; the value of all output coins created with CREATE_COIN. If it's not
|
|
;; a CREATE_COIN condition, it returns 0.
|
|
|
|
(defun-inline output-value-for-condition (condition)
|
|
(if (= (f condition) CREATE_COIN)
|
|
(f (r (r condition)))
|
|
0
|
|
)
|
|
)
|
|
|
|
;; this function takes a list of conditions and returns an integer indicating
|
|
;; the value of all output coins created with CREATE_COIN
|
|
(defun output-totals (conditions)
|
|
(if conditions
|
|
(+ (output-value-for-condition (f conditions)) (output-totals (r conditions)))
|
|
0
|
|
)
|
|
)
|
|
|
|
;; ensure `this-coin-info` is correct by creating the `ASSERT_MY_COIN_ID` condition
|
|
(defun-inline create-assert-my-id (this-coin-info)
|
|
(list ASSERT_MY_COIN_ID (coin-id-for-coin this-coin-info))
|
|
)
|
|
|
|
;; add three conditions to the list of morphed conditions:
|
|
;; ASSERT_MY_COIN_ID for `this-coin-info`
|
|
;; CREATE_COIN_ANNOUNCEMENT for my announcement
|
|
;; ASSERT_COIN_ANNOUNCEMENT for the next coin's announcement
|
|
(defun-inline generate-final-output-conditions
|
|
(
|
|
prev-subtotal
|
|
this-subtotal
|
|
morphed-conditions
|
|
prev-coin-info
|
|
this-coin-info
|
|
next-coin-info
|
|
)
|
|
(c (create-assert-my-id this-coin-info)
|
|
(c (create-announcement-condition prev-coin-info prev-subtotal)
|
|
(c (create-assert-next-announcement-condition this-coin-info this-subtotal next-coin-info)
|
|
morphed-conditions)
|
|
)
|
|
)
|
|
)
|
|
|
|
(defun-inline coin-info-for-coin-bundle (coin-bundle)
|
|
(f coin-bundle)
|
|
)
|
|
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;; lineage checking
|
|
|
|
;; return true iff parent of `this-coin-info` is provably a cc
|
|
(defun is-parent-cc (
|
|
lineage-proof-parameters
|
|
this-coin-info
|
|
(parent-parent-coin-id parent-inner-puzzle-hash parent-amount)
|
|
)
|
|
(= (f this-coin-info)
|
|
(sha256 parent-parent-coin-id
|
|
(cc-puzzle-hash lineage-proof-parameters parent-inner-puzzle-hash)
|
|
parent-amount
|
|
)
|
|
)
|
|
)
|
|
|
|
;; return true iff the lineage proof is valid
|
|
;; lineage-proof is of one of two forms:
|
|
;; (1 . (parent-parent-coin-id parent-inner-puzzle-hash parent-amount))
|
|
;; (0 . some-opaque-proof-passed-to-genesis-coin-checker)
|
|
;; so the `f` value determines what kind of proof it is, and the `r` value is the proof
|
|
|
|
(defun genesis-coin-checker-for-lpp ((mod_hash mod_hash_hash genesis-coin-checker genesis-coin-checker-hash))
|
|
genesis-coin-checker
|
|
)
|
|
|
|
(defun-inline is-lineage-proof-valid (
|
|
lineage-proof-parameters coin-info lineage-proof)
|
|
(if
|
|
(f lineage-proof)
|
|
(is-parent-cc lineage-proof-parameters coin-info (r lineage-proof))
|
|
(a (genesis-coin-checker-for-lpp lineage-proof-parameters)
|
|
(list lineage-proof-parameters coin-info (r lineage-proof)))
|
|
)
|
|
)
|
|
|
|
(defun is-bundle-valid ((coin . lineage-proof) lineage-proof-parameters)
|
|
(is-lineage-proof-valid lineage-proof-parameters coin lineage-proof)
|
|
)
|
|
|
|
|
|
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
|
|
|
(defun main (
|
|
lineage-proof-parameters
|
|
inner-conditions
|
|
prev-coin-bundle
|
|
this-coin-bundle
|
|
next-coin-bundle
|
|
prev-subtotal
|
|
)
|
|
(assert
|
|
; ensure prev is a cc (is this really necessary?)
|
|
(is-bundle-valid prev-coin-bundle lineage-proof-parameters)
|
|
|
|
; ensure this is a cc (to ensure parent wasn't counterfeit)
|
|
(is-bundle-valid this-coin-bundle lineage-proof-parameters)
|
|
|
|
; ensure next is a cc (to ensure its announcements can be trusted)
|
|
(is-bundle-valid next-coin-bundle lineage-proof-parameters)
|
|
|
|
(generate-final-output-conditions
|
|
prev-subtotal
|
|
; the expression on the next line calculates `this-subtotal` by adding the delta to `prev-subtotal`
|
|
(+ prev-subtotal (- (input-amount-for-coin (coin-info-for-coin-bundle this-coin-bundle)) (output-totals inner-conditions)))
|
|
(morph-conditions inner-conditions lineage-proof-parameters)
|
|
(coin-info-for-coin-bundle prev-coin-bundle)
|
|
(coin-info-for-coin-bundle this-coin-bundle)
|
|
(coin-info-for-coin-bundle next-coin-bundle)
|
|
)
|
|
)
|
|
)
|
|
|
|
(main
|
|
;; cache some stuff: output conditions, and lineage-proof-parameters
|
|
(list mod-hash (sha256tree1 mod-hash) genesis-coin-checker (sha256tree1 genesis-coin-checker))
|
|
(a inner-puzzle inner-puzzle-solution)
|
|
prev-coin-bundle
|
|
this-coin-bundle
|
|
next-coin-bundle
|
|
prev-subtotal
|
|
)
|
|
)
|