vdf.lurk

;; Hat tip to JP Aumasson.
!(defrec fastexp (lambda (b e)
                    (if (= e 0) 1
                        (if (< (/ e 2) 0) ; is e odd?
                            (* b (fastexp (* b b) (/ (- e 1) 2)))
                            (fastexp (* b b) (/ e 2))))))

(fastexp 2 5)

;; (4p - 3) / 5
!(def r 17510594297471420177797124596205820070838691520332827474958563349260646796493)

!(def fifth-root (lambda (n) (fastexp n r)))

!(def fifth (lambda (n) (fastexp n 5)))

(fifth-root 42)

(fifth 0x2a7b0ae43e98616d25287ce004700ac747ed8f5e95761ee4869ac0a851b3d3ee)

!(def round (lambda (state)
               (let ((x (car state))
                     (y (car (cdr state)))
                     (i (car (cdr (cdr state)))))
                 (cons (fifth-root (+ x y))
                       (cons (+ x i)
                             (cons (+ i 1) nil))))))

!(def inverse-round (lambda (state)
                       (let ((x (car state))
                             (y (car (cdr state)))
                             (i (car (cdr (cdr state))))
                             (new-i (- i 1))
                             (new-x (- y new-i))
                             (new-y (- (fifth x) new-x)))
                         (cons new-x (cons new-y (cons new-i nil))))))

!(defrec minroot (lambda (state rounds)
                    (if (= rounds 0)
                        state
                        (minroot (round state) (- rounds 1)))))

!(defrec minroot-inverse (lambda (state rounds)
                            (if (= rounds 0)
                                state
                                (minroot-inverse (inverse-round state) (- rounds 1)))))

(minroot '(123 456 1) 10)

(minroot-inverse '(0x1896bbc5df5819f436df3f86f6c707bdee372c1046bfa70196cf0f358497acc2 0x0ba0c60958b05f0ca1153cab833cbc315f7f10c4e1b9630ec8829cea907cb688 11) 10)

!(prove)

!(verify "supernova_bn256_10_2b96123c7e47229622beeef7080c005e9d18ed0cfd2c0b7f06e1d9f1cfcf83a8")

!(def timelock-encrypt (lambda (secret-key plaintext rounds)
                          (let ((ciphertext (+ secret-key plaintext))
                                (timelocked-key-state (minroot-inverse (cons secret-key '(0 1)) rounds)))
                            (cons timelocked-key-state ciphertext))))

!(def timelock-decrypt (lambda (timelocked-key-state ciphertext rounds)
                          (let ((secret-key (car (minroot timelocked-key-state rounds)))
                                (plaintext (- ciphertext secret-key)))
                            plaintext)))

; (timelock-encrypt (num (commit <REDACTED SECRET KEY>)) <REDACTED PLAINTEXT> 10000)

; [2370068 iterations] => ((0x2b7a3b8ddd37f5729671b40f14ea588eb74e0474516503cae76114c80c3e68b3 0x39766ed0c1d5a61b0a0b5146585f01ea78bac01860ce0f8653bb098d42efcce3 0x40000000000000000000000000000000224698fc0994a8dd8c46eb20ffffd8f2) . 0x0fbc16c244caeec63f5e0316c9b36ad5eba0b1c10f7ecf5d681a911e9dfa74d0)

; (timelock-decrypt  ;; timelocked key state
;                   '(0x2b7a3b8ddd37f5729671b40f14ea588eb74e0474516503cae76114c80c3e68b3
;                     0x39766ed0c1d5a61b0a0b5146585f01ea78bac01860ce0f8653bb098d42efcce3
;                     0x40000000000000000000000000000000224698fc0994a8dd8c46eb20ffffd8f2)
;                   ;; ciphertext
;                   0x0fbc16c244caeec63f5e0316c9b36ad5eba0b1c10f7ecf5d681a911e9dfa74d0
;                   ;; rounds
;                   10000)

;; [97420052 iterations] => <REDACTED PLAINTEXT>