; build an M of N multisig puzzle
; coins are locked by N public keys, any M of which can delegate a sub-puzzle


; glossary of parameter names:

;  public_key_list: a list of N public keys

;  M: the M in "M of N"

;  selectors: a list up of 0s and 1s up to size N where exactly M are 1s
;     It's used to select public keys from public_key_list

;  delegated_puzzle: the puzzle signed by the M public keys
;     This puzzle must return a list of conditions

;  solution: the solution to the delegated puzzle


(mod
  (M public_key_list selectors delegated_puzzle solution)

  (include condition_codes.clib)

  ;; hash a tree
  ;; This is used to calculate a puzzle hash given a puzzle program.
  (defun sha256tree1
    (TREE)
    (if (l TREE)
        (sha256 2 (sha256tree1 (f TREE)) (sha256tree1 (r TREE)))
        (sha256 1 TREE)
    )
  )

  ; "assert" is a macro that wraps repeated instances of "if"
  ; usage: (assert A0 A1 ... An R)
  ; all of A0, A1, ... An must evaluate to non-null, or an exception is raised
  ; return the value of R (if we get that far)

  (defmacro assert items
    (if (r items)
        (list if (f items) (c assert (r items)) (q . (x)))
        (f items)
    )
  )

  ; add_aggsig returns a list of conditions. It includes M AGG_SIG conditions
  ;   corresponding to the given list of public keys (with the given hash)
  ;   plus the conditions that come out of the delegated puzzle.
  ;
  ; hash is the hash of delegated_puzzle.
  ;  Yes it's redundant since we include the delegated_puzzle itself,
  ;  but we don't want to recalculate the hash multiple times as its expensive to do so

  (defun add_aggsig (public_key_list hash delegated_puzzle solution)
    (if public_key_list
        (c (list AGG_SIG_UNSAFE (f public_key_list) hash)
          (add_aggsig (r public_key_list) hash delegated_puzzle solution)
        )
        (a delegated_puzzle solution)
    )
  )

  ; choose_keys takes a list of selectors and the N public keys and
  ; returns a list of the M public keys chosen by the selectors

  (defun choose_keys (selectors public_key_list)
    (if selectors
        (if (f selectors)
            (c (f public_key_list) (choose_keys (r selectors) (r public_key_list)))
        (choose_keys (r selectors) (r public_key_list)))
        ()
    )
  )


  ; count the number of non-0 values in the list of selectors and return it as an integer

  (defun count_selectors (selectors)
    (if selectors
        (+
          (count_selectors (r selectors))
          (if (f selectors) 1 0)
        )
        0
    )
  )

  ; "solve_puzzle" is the main entry point

  (defun-inline solve_puzzle (M public_key_list selectors delegated_puzzle solution)
    ; make sure we have exactly M selectors
    (assert (= M (count_selectors selectors))
      ; return the AGG_SIG conditions plus the conditions from the delegated_puzzle
      (add_aggsig (choose_keys selectors public_key_list)
        (sha256tree1 delegated_puzzle)
        delegated_puzzle
      solution)
    )
  )

  ; main entry point

  (solve_puzzle
    M public_key_list
    selectors delegated_puzzle solution
  )
)
