Pythonにおけるハッシュの扱いとメモリの削減について

はじめに

こんにちは、D2Cデータサイエンティストの小林です。

本記事では、Pythonによるハッシュの扱い方とハッシュを用いることで使用するメモリの削減ができるのかを検証します。

ハッシュについては簡単な紹介のみとなりますので、ハッシュについて深く知りたい方は他の記事を参考していただければと思います。

開発環境

検証において以下の環境を使用しました。

• AWS EC2 (インスタンスタイプ: r5.2xlarge)
• Python 3.10系（3.10.9）
• pandas 1.5.1
• memory_profiler 0.61.0
• hashlib 3.10系で提供されているモジュール
• random 3.10系で提供されているモジュール
• string 3.10系で提供されているモジュール

ハッシュとは

ハッシュとは、あるデータから特定のアルゴリズムに基づいて不規則な文字列(値)を求めることです。求められた値のことをハッシュ値、ハッシュ値を求めるアルゴリズムのことをハッシュ関数といいます。ハッシュ値/ハッシュ関数の主な使われ方としては以下のものがあります。

1. デジタルデータの送受信時に、ハッシュ関数を使ってデータをハッシュ値に変換
2. データ処理の高速化や検索の高速化
3. データの改ざんの防止

ハッシュ値の利用例としては以下のようなものがあります。

1. 電子署名
2. 電子メール
3. 配布するファイル
4. ビットコイン、ブロックチェーン

ハッシュ値とは

ハッシュ値とは、あるデータをハッシュ関数によって求められる決まった長さの不規則な文字列に変換した値のことです。ハッシュ値は、ダイジェスト値とも呼ばれハッシュ値の桁数には12桁や16桁などの複数の種類があります。文字列や数値のほか、映像や音楽のような情報も数値化され、ハッシュ値で表すことができます。膨大なサイズの情報であってもハッシュ関数の入力には問題ないため、数値化できるデータであればどのようなものでもハッシュ関数に割り当てることができハッシュ値として扱うことができます。

ハッシュ値の特徴

ハッシュ値の特徴としては、元のデータがほんの少しでも変われば、計算されるハッシュ値が全く異なる点です。ハッシュ値同士の関連性もないため、データの関連性を分析される心配も少ないと言われています。ハッシュ関数に入力してはじき出したハッシュ値から元のデータを復元することは不可能(不可逆性。暗号化との大きな違い)と言われています。このような点から元のデータをそのまま扱うより、ハッシュ化して扱った方が安全性は高くなります。しかし、ハッシュ化を行ったとしても、セキュリティ的に完璧な対策にはならない点には注意が必要です。(今回は深く触れないがハッシュ値を平文に戻す方法の一つとしてレインボーテーブルがある。)

代表的なハッシュ関数について

代表的なハッシュ関数をいくつか紹介します。
すでに脆弱性が指摘されているハッシュ関数もあるためセキュリティを最重視するのであれば、使用するハッシュ関数についても理解しておくことが肝心です。

• MD5
  MD5はMessage Digest5の略称で、1991年に考案されたものです。当時はハッシュ関数として有効とされていましたが、現在ではセキュリティ面の脆弱性が指摘されていることから使用は推奨されていないものになります。
• SHA-1
  Secure Hash Algorithm1の略称であるSHA-1は1995年から使われるようになったハッシュ関数です。こちらも2005年頃に攻撃の手法が発見され、現在では安全性に不安が残るものとなってます。グーグルも既にSHA-1の証明書受け入れを停止するなど、現在はあまり使われていないのが実情です。
• SHA-2
  SHA-2（Secure Hash Algorighm2）は2001年から使われるようになったハッシュ関数です。SHA-2にはSHA-224やSHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256といった種類があり、現在はSHA-256が一般的に使われてます。
• SHA-3
  SHA-3（Secure Hash Algorighm3）は2015年に公表された新たなハッシュ関数です。より安全性の高いハッシュ関数を使ったデータの送受信をしたいときにはSHA-3の使用がおすすめです。

理想的なハッシュ関数

理想的なハッシュ関数は以下の3つの性質を備えている必要があると言われています。
本記事では、簡単な紹介のみです。詳しく知りたい方は他の記事を参照してください。

1. 弱衝突耐性:
   入力m1が与えられたとき、hash(m1)=hash(m2)となるような別の入力m2を求めることが困難でなくてはならない
2. 強衝突耐性:
   hash(m1)=hash(m2)となる2つの異なるメッセージm1とm2を探し出すことが困難でなくてはならない
3. 原像計算困難性:
   ハッシュ値Sとハッシュ関数hash()が与えられたときSと一致する任意の入力m1を見つけるのが困難

実装と検証

ここからは実際にPythonでハッシュの扱い方とハッシュを用いることで使用するメモリの削減ができるのかを検証します。

Pythonでのハッシュの使用方法

参照: https://docs.python.org/ja/3/library/hashlib.html

import hashlib

word = "hash"
word2 = "D2C"

# sha256
# ここでは使用するハッシュアルゴリズムを指定
# 今回は「sha256」というハッシュアルゴリズムを使用
sha256 = hashlib.sha256()


# ここでは文字列をバイト文字列に変換して先ほどのハッシュアルゴリズムに渡しています
# updateするたびにたされていく
# このようにすることでバイト文字列に変換できます。
sha256.update(word.encode()) # hash
sha256.update(word2.encode()) # hashD2C

# 最後にハッシュ関数の出力を確認していきましょう。
# ダイジェスト値 = ハッシュ関数により求められた値。
print(f"sha256に渡されたダイジェスト値を確認: {sha256.digest()}")

# 以下のようにすると読みやすくなります。
print(sha256.hexdigest())

sha256_word = hashlib.sha256(word.encode()).hexdigest()

print(f"256-bit 64 hex chars でのハッシュ関数[sha256]に通した結果: {sha256_word}")
print(f"64-bit 16 hex chars でのハッシュ関数[sha256]に通した結果: {sha256_word[:16]}") 
print(f"32-bit 8  hex chars でのハッシュ関数[sha256]に通した結果: {sha256_word[:8]}")

# 1bit * 8 = 1byte
# 256bit = 32byte となる
print(f"バイト数: {sha256.digest_size}")

# ハッシュアルゴリズムのバイト数
print(f"ブロックのバイト数: {sha256.block_size}")

# ハッシュアルゴリズムの正規名を確認
print(f"使用しているハッシュアルゴリズムの正規名の確認: {sha256.name}")

ハッシュ化によるメモリの削減

まず、サンプルデータの生成をします。
user_idは40文字の文字列を想定しています。今回はuser_id, age, genderの3カラムを用意し5,000万レコードのデータで検証します。

import memory_profiler as MP
import hashlib
import pandas as pd
import random, string

def randomname(n):
    randlst = [random.choice(string.ascii_letters + string.digits) for i in range(n)]
    return ''.join(randlst)
 
%%time
user_ids = []
age = []
gender = []
for i in range(0, 50000000):
    user_ids.append(randomname(40))
    age.append(random.randint(18, 80))
    gender.append(random.randint(0, 1))
    
### 現在の使用メモリ
m = MP.memory_usage()[0]
print(f"{m/1000} GB")

### データフレームの作成
df = pd.DataFrame()
df["user_id"] = user_ids
df["age"] = age
df["gender"] = gender

### データの保存
df.to_parquet("sample.parquet")

はじめに、作成したデータフレームの使用メモリを測定します。

%%time 
import memory_profiler as MP
import hashlib
import pandas as pd

df = pd.read_parquet("sample.parquet")

### 現在の使用メモリ
m = MP.memory_usage()[0]
print(f"{m/1000} GB")

結果:
12.8735625 GB
CPU times: user 18.3 s, sys: 8.79 s, total: 27.1 s
Wall time: 25.6 s

次に、user_idをハッシュ化させ使用メモリの測定をします。

%%time
import memory_profiler as MP
import hashlib
import pandas as pd

df = pd.read_parquet("sample.parquet")

### user_idを8文字の文字列に変換(32bit)
df["user_id"] = df["user_id"].apply(lambda x: hashlib.sha256(x.encode()).hexdigest()[:8])

### 現在の使用メモリ
m = MP.memory_usage()[0]
print(f"{m/1000} GB")

結果:
4.3753984375 GB
CPU times: user 1min 10s, sys: 11.8 s, total: 1min 22s
Wall time: 1min 20s

ハッシュ化させることでおよそ8GBの削減ができています。さらに、user_idのカラムの型を16進数のint型に変換してからu4に変換した状態で使用メモリを測定します。

%%time
import memory_profiler as MP
import hashlib
import pandas as pd

df = pd.read_parquet("sample.parquet")

### user_idを8文字の文字列に変換(32bit)後、16進数に変換しu4として扱う。
df["user_id"] = df["user_id"].apply(lambda x: int(hashlib.sha256(x.encode()).hexdigest()[:8], 16))
df["user_id"] = df["user_id"].astype("u4")

### 現在の使用メモリ
m = MP.memory_usage()[0]
print(f"{m/1000} GB")

結果:
1.1217109375 GB
CPU times: user 1min 24s, sys: 11.4 s, total: 1min 36s
Wall time: 1min 34s

最終的にはおよそ11GBのメモリ削減ができています。今回は1カラムのみハッシュ化を適応させた点と5,000万レコードのデータであった点から、より元のデータ量が膨大なほど多く削減できると思われます。 ただし、注意点として今回はメモリの削減がテーマなので衝突については全く考えず実行しています。 実際にハッシュ化させた後のuser_idのユニーク数を数えると5,000万より少なくなっており異なる元データのものが同じハッシュ値に変換されているのがわかります。 実際に使う場合はこの衝突が許される状態なのか、許されない状態であれば衝突確率を計算し衝突が起きない文字数を使用する必要があります。

print(len(df))
print(len(df["user_id"].unique()))

まとめ

本記事では、簡単なハッシュの紹介とPythonにおけるハッシュの扱い、ハッシュ化におけるメモリの削減について紹介しました。ハッシュ化を行うことで、元のデータで扱うより安全性が担保され、かつメモリの削減にもつながることがわかりました。今回はハッシュ化をすることでメモリの削減を行いましたが、最近ではDaskやPolarsといった処理の高速化かつ使用するメモリを制限することができる便利なパッケージもあるのでそちらも調べてみると良いと思います。

実際に使うハッシュを使う場合はハッシュ関数の脆弱性に気をつけ、どのハッシュ関数を使うべきかを吟味する必要があります。元のデータより安全性は高いものになってはいますが、ハッシュ化させているから絶対に安全というわけではありません。
また、本記事では深く触れませんでしたがハッシュには衝突というものがあります。理論上、ハッシュ関数で衝突の起きないハッシュ関数はありません。衝突の起きる確率は極めて低い確率となっていますが、実際に使う場合は注意が必要になります。ハッシュ化はPythonなどで簡単に実装することはできますが安易に使うのではなくハッシュについて調べた上で使用することをお勧めします。本記事が、ハッシュについて興味を示すきっかけになれば幸いです。

最後までお読みいただきありがとうございました。

参照

• https://www.itreview.jp/words/hash
• https://eset-info.canon-its.jp/malware_info/special/detail/211013.html
• https://qiita.com/KEINOS/items/65265a1058db1499bb3a
• https://qiita.com/Shellyhackinglab/items/522e9815373e4b2649ff
• https://qiita.com/kootr/items/1e88f2b241f801bad912