PostgreSQLにおけるSCRAM認証とSCRAMパススルー認証
はじめに
PostgreSQLは複数のクライアント認証方式をサポートしています。外部の認証プロバイダを利用する方法のほか、データベースに保存された資格情報を利用したパスワード認証もサポートしています。 データベースに保存された資格情報を利用したパスワード認証にも複数の方法がありますが、推奨されているのはscram-sha-256認証です。これは前回の記事で言及したSCRAM認証の1種です。
この記事ではPostgreSQLにおけるSCRAM認証の簡単な説明と、PostgreSQL 18でサポートが予定されている、SCRAMパススルー認証について説明します。
SCRAM認証はなぜこの形なのか
はじめに
パスワードを用いる認証方式の1つにSCRAM認証があります。SCRAM認証はパスワードを用いるチャレンジ・レスポンス認証の一種です。SCRAM認証は以下を実現します。
- サーバは、「クライアントがパスワード登録時と同じ知識を持つ存在である」ことを確認できる
- クライアントは、「サーバがパスワード登録時に預けた知識を持つ存在である」ことを確認できる
- パスワード登録時、認証時のいずれの場合においても、平文のパスワードをクライアントの外に持ち出す必要がない 、つまり平文のパスワードをサーバに知らせる必要がない
サーバにパスワードを知らせる必要がないため、たとえパスワードが使いまわされていたとしてもサーバはそれを悪用できません。
続きを読む
ゼロ知識モデルでできなくなること
前回のポストで書いた、アプリケーションに対するゼロ知識がどれくらい強い制限なのかについての補足です。
ちなみに、前回のポストのメインの主張（以下）には反例がありそうでした。こちらは後日まとめたいと思います。
アプリケーションプログラムに対する知識（前提）をスケジューラが持たない場合、アプリケーション（複数）が発行する各トランザクションを、直列化可能なスケジュールで並行にかつ常に成功裡に実行・完了させることはできない。
反例とは、アプリケーションに対する知識がゼロであっても、直列化可能で直列化失敗を引き起こさないスケジューリングが、部分的には並行に（インターリーブ）できるという意味です。
続きを読む3-CNF SATからpolygraphのacyclicity判定問題への帰着
このポストは、papa本で証明されている「スケジュールsが与えられとき、それがview serializableであることのテストはNP完全である」の証明の一部を構成する、3-CNF SAT問題からpolygraphのacyclicity判定問題への帰着についてのメモです。
papa本は以下の本のことです。
Theory of Database Concurrency Control
- 作者: Christos Papadimitriou
- 出版社/メーカー: Computer Science Pr
- 発売日: 1986/07/01
- メディア: ハードカバー
- この商品を含むブログを見る
証明の流れ
- スケジュールsがview serializableである iff polygraph P(s)が非巡回である （Theorem 2.4）
- polygraphが非巡回であることのテストはNP完全である（Theorem 2.5）
- 3-CNF Fが充足可能 iff polygraph P(F)が非巡回である（本ポストの内容）
- 3-CNF Fからpolygraph P(F)が多項式時間で構築できる
- polygraph Pが与えられたとき、「Pが非巡回である iff スケジュールsがview serializableである」ようなスケジュールsをPから構築できる（Lemma 2.4）
