【Python】ゼロ知識証明

ゼロ知識証明とは、証明者がその事実を提示するだけで、その事実の内容を隠すことができる証明方法
Zero-knowledge Proofとしてよく使われるのが、ハミルトングラフの知識を持っていることや秘密のパスワードを証明せず知っていることを示す。

xを知っていおり、 y = x^2 mod p を示す。

import random

p = 23
x = 5
y = pow(x, 2, p)

print(" y =", y)

def prover_step():
    r = random.randint(1, p - 1)
    a = pow(r, 2, p)
    return r, a

def verifier_challenge():
    return random.randint(0, 1)

def prover_response(r, c):
    if c == 0:
        return r
    else:
        return (r * x) % p

def verifier_check(a, z, c):
    if c == 0:
        return pow(z, 2, p) == a
    else:
        return pow(z, 2, p) == (a * y) % p

r, a = prover_step()
print("Prover: 提出 a=", a)

c = verifier_challenge()
print("Verifier: チャレンジ c=", c)

z = prover_response(r, c)
print("Prover: 応答 z =", z)

ok = verifier_check(a, z, c)
print("Verifier: 検証結果 =", ok)

$ python3 zkp.py
y = 2
Prover: 提出 a= 4
Verifier: チャレンジ c= 1
Prover: 応答 z = 10
Verifier: 検証結果 = True

—– 実際の計算
r = ?,
a = 4,
c = 1
z = 10
10 * 10 % 23 = 5 * 2 / 23

x の値を知らせずに、y = x^2 mod p　を証明している。証明の際には、c != 0 の時にのみyの値を利用する
zkpの概念は理解できたが、なぜこれが証明になるのかのロジックはよくわからない..

【Rust】スタックマシンで関数を実装する

変数と同じように、関数名とinstructionをhashmapに保存する

/x 2 def /double { x 2 * } fn

        "fn" => {
            let tmp = func(&mut stack, instructions.clone());
            for (key, value) in &tmp {
                funcs.insert(key.to_string(), value.to_vec());
            }
            println!("{:?}", funcs); 
        } 

// 省略

fn func(stack: &mut Vec<String>, instructions: Vec<String>) -> HashMap<String, Vec<String>> {
    let mut funcs: HashMap<String, Vec<String>> = HashMap::new();
    let name = stack.pop().unwrap();

    funcs.insert(name, instructions);
    funcs
}

{“double”: [“x”, “2”, “*”]}

関数名と式をhashmapに保存したので、後は関数名が書かれていた際に、関数の内容を呼び出すだけ


    } else if funcs.contains_key(word) {
      let _ = op_fn(&mut stack, funcs.get(word).unwrap(), vars.clone());
//

fn op_fn(stack: &mut Vec<String>, input: &Vec<String>, vars: HashMap<String, String>) {
    let mut words = input.clone();
    while let Some((&ref word, rest)) = words.split_first() {
        if word.is_empty() {
          break;
        }
        if let Ok(parsed) = word.parse::<i32>() {
          stack.push(parsed.to_string());
        } else if word.starts_with("/") {
          stack.push((word[1..]).to_string());
        } else if vars.contains_key(word) {
          stack.push(vars.get(word).unwrap().to_string());
        } else {
          match word.as_str() {
            "+" => add(stack),
            "-" => sub(stack),
            "*" => mul(stack),
            "/" => div(stack),
            "%" => r#mod(stack),
            "<" => lt(stack),
            ">" => rt(stack),
            "==" => equal(stack),
            "!=" => nequal(stack),
            "sqrt" => r#sqrt(stack),
            "if" => op_if(stack),
            _ => todo!(),
            }
        }
        words = rest.to_vec();
      }
}

/x 2 def /double { x 2 * } fn double
=> [“4”]

【Rust】スタックマシンでループ文を実装するための準備

ループで実行する処理文を記憶するために、”{ }”で囲まれている中身を取得してベクターで保存しておく。

fn main() {
    let mut stack = vec![];
    let mut instructions = vec![];

    let str = "1 2 + { 10 20 + }".to_string();
    let mut words: Vec<_> = str.split(" ").collect();

    while let Some((&word, mut rest)) = words.split_first() {
        if word.is_empty() {
            break;
        }
        if word == "{" {
            (instructions, rest) = parse_instruction(rest);
        } else if let Ok(parsed) = word.parse::<i32>() {
            stack.push(parsed.to_string());
        } else {
            match word {
              "+" => add(&mut stack),
              _ => panic!("{word:?} could not be parsed"),
            }
        }
        words = rest.to_vec();
    }
    println!("{:?}", stack);
    println!("{:?}", instructions);
}

fn parse_instruction<'src, 'a>(input: &'a [&'src str])-> (Vec<String>, &'a [&'src str]) {
    let mut tokens: Vec<String> = vec![];
    let mut words = input;

    while let Some((&word, mut rest)) = words.split_first() {
        if word.is_empty() {
            break;
        }
        if word == "}" {
            return (tokens, rest);
        } else {
            tokens.push(word.to_string())
        }
        words = rest;
    }
    (tokens, words)
}

fn add(stack: &mut Vec<String>) {
    let rhs: i32 = stack.pop().unwrap().parse::<i32>().unwrap();
    let lhs: i32 = stack.pop().unwrap().parse::<i32>().unwrap();
    stack.push((lhs + rhs).to_string());
}

Running `target/debug/sample`
[“3”]
[“10”, “20”, “+”]

【Rust】sqrtの計算

f64でsqrt()の関数があるので、f64に変換して計算する
https://doc.rust-lang.org/std/primitive.f64.html#method.sqrt

fn main() {
    let n = 10;
    let f = n as f64;
    let s = f.sqrt();
    println!("{}", s);
    println!("{}", s as i32);
}

これをスタックマシンに実装します。とりあえずi32で統一しているので、ここでは、sqrt後 as i32としています。

match word {
        "+" => add(&mut stack),
        "-" => sub(&mut stack),
        "*" => mul(&mut stack),
        "/" => div(&mut stack),
        "%" => r#mod(&mut stack),
        "<" => lt(&mut stack),
        ">" => rt(&mut stack),
        "sqrt" => r#sqrt(&mut stack),
        "if" => op_if(&mut stack),
        "def" => {  
          let tmp = op_def(&mut stack);
          for (key, value) in &tmp {
            vars.insert(key.to_string(), value.to_string());
          }
        },
        _ => panic!("{word:?} could not be parsed"),
      }
//

fn r#sqrt(stack: &mut Vec<String>) {
  let f: f64 = stack.pop().unwrap().parse::<f64>().unwrap();
  let s = f.sqrt();
  stack.push((s as i32).to_string());
}

【Rust】四則演算に括弧{} をつける

fn main() {

  let mut stack = vec![];

  // Reverse Polish Notation
  let str = "100 5 - { 1 2 + } +".to_string();

  let mut words: Vec<_> = str.split(" ").collect();
  while let Some((&word, mut rest)) = words.split_first() {
    if word.is_empty() {
      break;
    }
    if word == "{" {
      let value;
      (value, rest) = parse_block(rest);
      stack.push(value);
    } else if let Ok(parsed) = word.parse::<i32>() {
      stack.push(parsed);
    } else {
      match word {
        "+" => add(&mut stack),
        "-" => sub(&mut stack),
        "*" => mul(&mut stack),
        "/" => div(&mut stack),
        _ => panic!("{word:?} could not be parsed"),
      }
    }
    words = rest.to_vec();
  }
  println!("{:?}", stack); 
}

fn parse_block<'src, 'a>(input: &'a [&'src str]) -> (i32, &'a [&'src str]){
  let mut tokens: Vec<i32> = vec![];
  let mut words = input;

  while let Some((&word, mut rest)) = words.split_first() {
    if word.is_empty() {
      break;
    }
    if word == "}" {
      return (tokens[0], rest);

    } else if let Ok(parsed) = word.parse::<i32>() {
      tokens.push(parsed);
    } else {
      match word {
        "+" => add(&mut tokens),
        "-" => sub(&mut tokens),
        "*" => mul(&mut tokens),
        "/" => div(&mut tokens),
        _ => todo!(),
        // _ => panic!("{word:?} could not be parsed"),
        }
    }
    words = rest;
  }
  (tokens[0], words)
}

fn add(stack: &mut Vec<i32>) {
  let rhs = stack.pop().unwrap();
  let lhs = stack.pop().unwrap();
  stack.push(lhs + rhs);
}

fn sub(stack: &mut Vec<i32>) {
  let rhs = stack.pop().unwrap();
  let lhs = stack.pop().unwrap();
  stack.push(lhs - rhs);
}

fn mul(stack: &mut Vec<i32>) {
  let rhs = stack.pop().unwrap();
  let lhs = stack.pop().unwrap();
  stack.push(lhs * rhs);
}

fn div(stack: &mut Vec<i32>) {
  let rhs = stack.pop().unwrap();
  let lhs = stack.pop().unwrap();
  stack.push(lhs / rhs);
}

[98]

【Rust】&[&str]の加算

&[&str]と&[&str]の加算の方法が不明だったので、一旦Stringに変えてformat!で加算する

fn main() {
    let str = "100 5 - { 1 2 + }".to_string();
    let mut words: Vec<_> = str.split(" ").collect();
    let Some((&word, mut rest)) = words.split_first() else { todo!() };

    println!("{:?}", rest);

    let mut tokens: Vec<_> = vec![];
    tokens.push(1);
    let mut str = "init".to_string();
    str = format!("{} {}", str, tokens[0].to_string());
    for r in rest {
        str = format!("{} {}", str, r);
        println!("{}", str);
    }
    println!("{:?}", str);   
}

“init 1 5 – { 1 2 + }”

うーん、なんか違う気がする..

【Rust】HashMapのValueへのアクセス

employee[“A”].clone().pop() ではなく、要素を指定せずにvalueをpop()したい場合

use std::collections::HashMap;

fn main() {
    let mut employee: HashMap<String, Vec<String>> = HashMap::new();
    employee.insert("A".to_string(), vec!["X".to_string(), "Y".to_string(), "Z".to_string()]);
    employee.insert("B".to_string(), vec!["X".to_string(), "Y".to_string(), "Z".to_string()]);
    for (key, mut value) in employee {
        println!("{:?}", value.pop());
    }
}

for e in employee ってしてしまうと、eからvalueの取り出し方法がわからなくなる。
これに結構時間かかりました。

vectorの要素のindexを取得する方法

        println!("{:?}", value.iter().position(|n| n == "Y"));

use std::collections::HashMap;

fn main() {

   let mut employee: HashMap<String, Vec<String>> = HashMap::new();
   employee.insert("A".to_string(), vec!["X".to_string(), "Y".to_string(), "Z".to_string()]);
   employee.insert("B".to_string(), vec!["X".to_string(), "Y".to_string(), "Z".to_string()]);
   employee.insert("C".to_string(), vec!["Y".to_string(), "Z".to_string(), "X".to_string()]);

   let mut department: HashMap<String, Vec<String>> = HashMap::new();
   department.insert("X".to_string(), vec!["C".to_string(), "A".to_string(), "B".to_string()]);
   department.insert("Y".to_string(), vec!["B".to_string(), "C".to_string(), "A".to_string()]);
   department.insert("Z".to_string(), vec!["A".to_string(), "B".to_string(), "C".to_string()]);

   let res = stable_match(employee, department);
   println!("{:?}", res);
}

fn stable_match(request_dict: HashMap<String, Vec<String>>, accept_dict: HashMap<String, Vec<String>>) -> HashMap<String, String>{
   let mut match_dict: HashMap<String, String> = HashMap::new();
   let req_len = request_dict.len();

   while match_dict.len() < req_len {
      'label: for (req_name, req_value) in &request_dict {
         for value in match_dict.values() {
            if value == req_name {
               break 'label;
            }
         }
         let acc_name = req_value.pop();
         if !match_dict.contains_key(&acc_name) {
            match_dict.insert(acc_name.unwrap(), req_name.to_string());
         } else {
            let rival_name = match_dict[&acc_name];
            if accept_dict[&acc_name].iter().position(|n| n == req_name) < accept_dict[&acc_name].iter().position(|n| n == rival_name) {
               match_dict.insert(acc_name.unwrap(), req_name.to_string());
            }
         }
      }
   }
   return match_dict;
}

うーむ、上手く書けん…

【Rust】ラムダ関数とは

– ラムダ計算とは関数型言語の基盤となっている計算モデルで、数値や演算の具体的な表記ではなく、「関数そのもの」を使って計算を表現する
– Rustにおけるクロージャは、その外側の環境を捕捉した関数のこと
– クロージャの構文や機能は、その場限りの用途で何かを作るのに便利

   let sq = |n| n * n;
   println!("{}", sq(9));

81

   let i = 32;
   let v = |n| n * i;
   println!("{}", v(9));

288

なるほどね

【Rust】ルックアップテーブル【アルゴリズム】

fn main() {

   let Q = [
      100, 200, 250, 300, 360
   ];

   let R = [
      401, 302, 101, 102, 301
   ];

   let mut x = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   let x  = x.trim_end().to_owned();
   let a = x.parse::<i32>().unwrap();

   let n = Q.len();

   while a > 0 {
      let mut i = 0;
      while i < n {
         if a < Q[i] {
            println!("整理番号{}番の方は{}会場です。", a, R[i]);
            i = n;
         } else {
            i += 1;
         }

      }
   }
}

整理番号100番の方は302会場です。

### 選択ソート

fn main() {

   let A = [
      84, 121, 43, 93, 140, 83, 14, 93, 181, 58
   ];

   let n = A.len();
   seq_sort(n, A);
}

fn seq_sort(n: usize, mut A: [i32; 10]) {
   let mut i = 0;
   let mut B: [i32; 10] = [0; 10];
   let mut k;
   for i in 0..n {
      
      let mut a = 999;
      let mut j = 0;
      for j in j..n {
         if a > A[j] {
            a = A[j];
            k = j;
         }
      }
      A[k] = 999;
      B[i] = a;
   }
   
}

【Rust】バイナリーサーチ【アルゴリズム】

fn main() {

   let mut commodity: [String; 8] = [
      "ジュース".to_string(),
      "紅茶".to_string(),
      "アイスティ".to_string(),
      "コーヒー".to_string(),
      "アイスコーヒー".to_string(),
      "ショートケーキ".to_string(),
      "チーズケーキ".to_string(),
      "トースト".to_string(),
   ];

   let mut price: [i32; 8] = [
      280, 300, 320, 350, 370, 550, 600, 650
   ];

   let mut x = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   let x  = x.trim_end().to_owned();
   let a = x.parse::<i32>().unwrap();

   let n = commodity.len() as i32;
   bin_search(a, n, price);
   // seq_search();
}

fn bin_search(a: i32, n: i32, price: [i32; 8]) {
   let mut p = -1;
   let mut l = 0;
   let mut h = n - 1;

   while (l <= h && p == -1) {
      if (a > price[((l+h) / 2) as usize]) {
         l = (l + h) / 2 + 1;
      } else {
         if (a == price[((l+h)/2) as usize]) {
            p = (l +h) / 2;
         } else {
            h = (l + h) / 2 - 1;
         }
      }
   }
   println!("{}", p);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.01s
Running `target/debug/basic`
300
1