timelock.ml

(* Quick and dirty proof of concept *)

open Hacl_star

module Timelock : sig
  type key = Z.t
  type public
  type secret
  type proof

  val generate: unit -> public * secret
  val key_with_secret:    secret -> time:Z.t -> value:Z.t -> key
  val key_without_secret: public -> time:Z.t -> value:Z.t -> key * proof
  val verify: public -> time:Z.t -> value:Z.t -> key -> proof -> bool

end = struct
  type secret = {p : Z.t ; q : Z.t} 
  type public = Z.t (* RSA modulus = p * q*)
  type proof = Z.t
  type key = Z.t
                                                        
  let generate () =
    let seed = Bytes.create 128 in
    let _ = Hacl.RandomBuffer.randombytes seed in  (*TODO don't ignore return value*)
    let p = (seed |> Bytes.to_string |> Z.of_bits |> Z.nextprime) in
    let _ = Hacl.RandomBuffer.randombytes seed in  (*TODO don't ignore return value*)
    let q = (seed |> Bytes.to_string |> Z.of_bits |> Z.nextprime) in             
    Z.(p * q), {p ; q}

  let bytes_32 = Bytes.of_string "\032"      
  let hash_to_prime public time value key =
    let s = String.concat "\xff\x00\xff\x00\xff\x00\xff\x00" (List.map Z.to_bits [public ; time ; value ; key]) in
    let hash_ : Bytes.t = Bytes.create 32 in
    Hacl.Blake2b_256.hash bytes_32 (Bytes.of_string s) hash_;
    Z.(nextprime (of_bits (Bytes.to_string hash_)))
          
  let key_with_secret secret ~time ~value =
    let phi = Z.((secret.p - one) * (secret.q - one)) in
    let e = Z.powm (Z.of_int 2) time phi in
    Z.powm value e Z.(secret.p * secret.q)

  let key_without_secret public ~time ~value  =
    let rec aux time v =
      if time = Z.zero then v
      else aux Z.(time - one) Z.((v * v) mod public)
    in
    let key = aux time value in
    let l = hash_to_prime public time value key in
    let pi = ref Z.one and r = ref Z.one in
    for i = 1 to (Z.to_int time) do
      pi := Z.(!pi * !pi mod public) ;
      r := Z.(!r lsl 1);
      if Z.(!r >= l) then (
        pi := Z.(!pi * value mod public) ;
        r := Z.(!r - l)
      ) else ()                    
    done;         
    (key, !pi)
    
  let verify public ~time ~value key proof =
    let l = hash_to_prime public time value key in
    let r = Z.(powm (of_int 2) time l) in
    key = Z.((powm proof l public) * (powm value r public) mod public )

      
end

let main () =
  let public,secret = Timelock.generate()
  and value = Z.of_int 42
  and time  = Z.of_int 1000 in
  let key = Timelock.key_with_secret secret ~time ~value
  and same_key, proof = Timelock.key_without_secret public ~time ~value in
  assert (key = same_key) ;
  assert (Timelock.verify public ~time ~value key proof) ;