cat.clsp

; Coins locked with this puzzle are spendable cats.
;
; 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 I_{k}, and I_{k+1} are CATs of the same type.
; 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 cat, 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 neighbours are CATs, ensuring the announcements aren't forgeries.
; Inner puzzles and the CAT layer prepend `CREATE_COIN_ANNOUNCEMENT` with different prefixes to avoid forgeries.
; Ring announcements use 0xcb, and inner puzzles are given 0xca
;
; In summary, I_k generates a coin_announcement Y_k ("Y" for "yell") as follows:
;
;  Y_k: hash of I_k (automatically), I_{k-1}, S_k
;
; Each coin creates an assert_coin_announcement to ensure 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 committing 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 cat.
;
; 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 cats 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.

;; GLOSSARY:
;;  MOD_HASH: this code's sha256 tree hash
;;  TAIL_PROGRAM_HASH: the program that determines if a coin can mint new cats, burn cats, and check if its lineage is valid if its parent is not a CAT
;;  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_id: the id for the previous coin
;;  tail_program_reveal: reveal of TAIL_PROGRAM_HASH required to run the program if desired
;;  tail_solution: optional solution passed into tail_program
;;  lineage_proof: optional proof that our coin's parent is a CAT
;;  this_coin_info: (parent_id puzzle_hash amount)
;;  next_coin_proof: (parent_id inner_puzzle_hash amount)
;;  prev_subtotal: the subtotal between prev-coin and this-coin
;;  extra_delta: an amount that is added to our delta and checked by the TAIL program
;;

(mod (
    MOD_HASH  ;; curried into puzzle
    TAIL_PROGRAM_HASH  ;; curried into puzzle
    INNER_PUZZLE  ;; curried into puzzle
    inner_puzzle_solution  ;; if invalid, INNER_PUZZLE will fail
    lineage_proof  ;; This is the parent's coin info, used to check if the parent was a CAT. Optional if using tail_program.
    prev_coin_id  ;; used in this coin's announcement, prev_coin ASSERT_COIN_ANNOUNCEMENT will fail if wrong
    this_coin_info  ;; verified with ASSERT_MY_COIN_ID
    next_coin_proof  ;; used to generate ASSERT_COIN_ANNOUNCEMENT
    prev_subtotal  ;; included in announcement, prev_coin ASSERT_COIN_ANNOUNCEMENT will fail if wrong
    extra_delta  ;; this is the "legal discrepancy" between your real delta and what you're announcing your delta is
  )

  ;;;;; start library code

  (include condition_codes.clib)
  (include curry-and-treehash.clib)
  (include cat_truths.clib)
  (include utility_macros.clib)

  (defconstant RING_MORPH_BYTE 0xcb)


  ; take two lists and merge them into one
  (defun merge_list (list_a list_b)
    (if list_a
        (c (f list_a) (merge_list (r list_a) list_b))
        list_b
    )
  )

  ; cat_mod_struct = (MOD_HASH MOD_HASH_hash GENESIS_COIN_CHECKER GENESIS_COIN_CHECKER_hash)

  (defun-inline mod_hash_from_cat_mod_struct (cat_mod_struct) (f cat_mod_struct))
  (defun-inline mod_hash_hash_from_cat_mod_struct (cat_mod_struct) (f (r cat_mod_struct)))
  (defun-inline tail_program_hash_from_cat_mod_struct (cat_mod_struct) (f (r (r cat_mod_struct))))

  ;;;;; end library code

  ;; return the puzzle hash for a cat with the given `GENESIS_COIN_CHECKER_hash` & `INNER_PUZZLE`
  (defun-inline cat_puzzle_hash (cat_mod_struct inner_puzzle_hash)
    (puzzle-hash-of-curried-function (mod_hash_from_cat_mod_struct cat_mod_struct)
      inner_puzzle_hash
      (sha256 ONE (tail_program_hash_from_cat_mod_struct cat_mod_struct))
      (mod_hash_hash_from_cat_mod_struct cat_mod_struct)
    )
  )

  ;; assert `CREATE_COIN_ANNOUNCEMENT` doesn't contain the RING_MORPH_BYTE bytes so it cannot be used to cheat the coin ring

  (defun-inline morph_condition (condition cat_mod_struct)
    (if (= (f condition) CREATE_COIN)
        (c CREATE_COIN
          (c (cat_puzzle_hash cat_mod_struct (f (r condition)))
          (r (r condition)))
        )
        (if (= (f condition) CREATE_COIN_ANNOUNCEMENT)
            (assert (not (and
                (= 33 (strlen (f (r condition))))
                (= (substr (f (r condition)) 0 ONE) RING_MORPH_BYTE)  ; lazy eval
              ))
              ; then
              condition
            )
            condition
        )
    )
  )

  ;; given a coin's parent, inner_puzzle and amount, and the cat_mod_struct, calculate the id of the coin
  (defun-inline coin_id_for_proof (coin cat_mod_struct)
    (calculate_coin_id (f coin) (cat_puzzle_hash cat_mod_struct (f (r coin))) (f (r (r coin))))
  )

  ;; utility to fetch coin amount from coin
  (defun-inline input_amount_for_coin (coin)
    (f (r (r coin)))
  )

  ;; calculate the hash of an announcement
  ;; we add 0xcb so ring announcements exist in a different namespace to announcements from inner_puzzles
  (defun-inline calculate_annoucement_id (this_coin_id this_subtotal next_coin_id cat_mod_struct)
    (sha256 next_coin_id RING_MORPH_BYTE (sha256tree (list this_coin_id 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_id this_subtotal next_coin_id cat_mod_struct)
    (list ASSERT_COIN_ANNOUNCEMENT
      (calculate_annoucement_id this_coin_id
        this_subtotal
        next_coin_id
        cat_mod_struct
      )
    )
  )

  ;; here we commit to I_{k-1} and S_k
  ;; we add 0xcb so ring announcements exist in a different namespace to announcements from inner_puzzles
  (defun-inline create_announcement_condition (prev_coin_id prev_subtotal)
    (list CREATE_COIN_ANNOUNCEMENT
      (concat RING_MORPH_BYTE (sha256tree (list prev_coin_id 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
    )
  )

  ;; add two conditions to the list of morphed conditions:
  ;; 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_id
      this_coin_id
      next_coin_id
      cat_mod_struct
    )
    (c (create_announcement_condition prev_coin_id prev_subtotal)
      (c (create_assert_next_announcement_condition this_coin_id this_subtotal next_coin_id cat_mod_struct)
      morphed_conditions)
    )
  )


  ;; This next section of code loops through all of the conditions to do three things:
  ;;   1) Look for a "magic" value of -113 and, if one exists, filter it, and take note of the tail reveal and solution
  ;;   2) Morph any CREATE_COIN or CREATE_COIN_ANNOUNCEMENT conditions
  ;;   3) Sum the total output amount of all of the CREATE_COINs that are output by the inner puzzle
  ;;
  ;; After everything return a struct in the format (morphed_conditions . (output_sum . tail_reveal_and_solution))
  ;; If multiple magic conditions are specified, the later one will take precedence

  (defun-inline condition_tail_reveal (condition) (f (r (r (r condition)))))
  (defun-inline condition_tail_solution (condition) (f (r (r (r (r condition))))))

  (defun cons_onto_first_and_add_to_second (morphed_condition output_value struct)
    (c (c morphed_condition (f struct)) (c (+ output_value (f (r struct))) (r (r struct))))
  )

  (defun find_and_strip_tail_info (inner_conditions cat_mod_struct tail_reveal_and_solution)
    (if inner_conditions
        (if (= (output_value_for_condition (f inner_conditions)) -113)  ; Checks this is a CREATE_COIN of value -113
            (find_and_strip_tail_info
              (r inner_conditions)
              cat_mod_struct
              (c (condition_tail_reveal (f inner_conditions)) (condition_tail_solution (f inner_conditions)))
            )
            (cons_onto_first_and_add_to_second
              (morph_condition (f inner_conditions) cat_mod_struct)
              (output_value_for_condition (f inner_conditions))
              (find_and_strip_tail_info
                (r inner_conditions)
                cat_mod_struct
                tail_reveal_and_solution
              )
            )
        )
        (c () (c 0 tail_reveal_and_solution))
    )
  )

  ;;;;;;;;;;;;;;;;;;;;;;;;;;; lineage checking

  ;; return true iff parent of `this_coin_info` is provably a cat
  ;; A 'lineage proof' consists of (parent_parent_id parent_INNER_puzzle_hash parent_amount)
  ;; We use this information to construct a coin who's puzzle has been wrapped in this MOD and verify that,
  ;; once wrapped, it matches our parent coin's ID.
  (defun-inline is_parent_cat (
      cat_mod_struct
      parent_id
      lineage_proof
    )
    (= parent_id
      (calculate_coin_id (f lineage_proof)
        (cat_puzzle_hash cat_mod_struct (f (r lineage_proof)))
        (f (r (r lineage_proof)))
      )
    )
  )

  (defun check_lineage_or_run_tail_program
    (
      this_coin_info
      tail_reveal_and_solution
      parent_is_cat  ; flag which says whether or not the parent CAT check ran and passed
      lineage_proof
      Truths
      extra_delta
      inner_conditions
    )
    (if tail_reveal_and_solution
        (assert (= (sha256tree (f tail_reveal_and_solution)) (cat_tail_program_hash_truth Truths))
          (merge_list
            (a  (f tail_reveal_and_solution)
              (list
                Truths
                parent_is_cat
                lineage_proof  ; Lineage proof is only guaranteed to be true if parent_is_cat
                extra_delta
                inner_conditions
                (r tail_reveal_and_solution)
              )
            )
            inner_conditions
          )
        )
        (assert parent_is_cat (not extra_delta)
          inner_conditions
        )
    )
  )

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;

  (defun stager_two (
      Truths
      (inner_conditions . (output_sum . tail_reveal_and_solution))
      lineage_proof
      prev_coin_id
      this_coin_info
      next_coin_id
      prev_subtotal
      extra_delta
    )
    (check_lineage_or_run_tail_program
      this_coin_info
      tail_reveal_and_solution
      (if lineage_proof (is_parent_cat (cat_struct_truth Truths) (my_parent_cat_truth Truths) lineage_proof) ())
      lineage_proof
      Truths
      extra_delta
      (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 this_coin_info) output_sum) extra_delta)
        inner_conditions
        prev_coin_id
        (my_id_cat_truth Truths)
        next_coin_id
        (cat_struct_truth Truths)
      )
    )
  )

  ; CAT TRUTHS struct is: ; CAT Truths is: ((Inner puzzle hash . (MOD hash . (MOD hash hash . TAIL hash))) . (my_id . (my_parent_info my_puzhash my_amount)))
  ; create truths - this_coin_info verified true because we calculated my ID from it!
  ; lineage proof is verified later by cat parent check or tail_program

  (defun stager (
      cat_mod_struct
      inner_conditions
      lineage_proof
      inner_puzzle_hash
      my_id
      prev_coin_id
      this_coin_info
      next_coin_proof
      prev_subtotal
      extra_delta
    )
    (c (list ASSERT_MY_COIN_ID my_id) (stager_two
        (cat_truth_data_to_truth_struct
          inner_puzzle_hash
          cat_mod_struct
          my_id
          this_coin_info
        )
        (find_and_strip_tail_info inner_conditions cat_mod_struct ())
        lineage_proof
        prev_coin_id
        this_coin_info
        (coin_id_for_proof next_coin_proof cat_mod_struct)
        prev_subtotal
        extra_delta
    ))
  )

  (stager
    ;; calculate cat_mod_struct, inner_puzzle_hash, coin_id
    (list MOD_HASH (sha256 ONE MOD_HASH) TAIL_PROGRAM_HASH)
    (a INNER_PUZZLE inner_puzzle_solution)
    lineage_proof
    (sha256tree INNER_PUZZLE)
    (calculate_coin_id (f this_coin_info) (f (r this_coin_info)) (f (r (r this_coin_info))))
    prev_coin_id  ; ID
    this_coin_info  ; (parent_id puzzle_hash amount)
    next_coin_proof  ; (parent_id innerpuzhash amount)
    prev_subtotal
    extra_delta
  )
)