crc - CRC をダイジェストとして使用してファイル間の重複を検出する

Question

CRC および同様の計算 (Fletcher や Adler など) の主な用途は、伝送エラーの検出にあるようです。そのため、私が見たほとんどの研究は、2 つのデータセット間の小規模な違いを検出する確率の問題に対処しているようです。私のニーズは少し異なります。

以下は、問題の非常に大まかな説明です。詳細はこれよりもはるかに複雑ですが、以下の説明は私が探している機能を示しています。この小さな免責事項は、「私が提案する別の方法で問題をより簡単に解決できるのに、なぜこの方法で問題を解決しているのですか?」などの回答を避けることを目的としています。- この質問や投稿に関係のない無数の理由により、この方法で問題を解決する必要があるため、そのような回答を投稿しないでください。

分散ネットワーク上でデータ セット (サイズ ~1MB) のコレクションを扱っています。これらのデータセットに対して計算が実行され、速度/パフォーマンスが重要になります。データセットの再送信を回避できるメカニズムが必要です。つまり、特定のサイズのデータ​​ セットごとに一意の識別子 (UID) を生成する何らかの方法が必要です。(次に、あるマシンから別のマシンにデータ セットのサイズと UID を送信します。受信側のマシンは、UID に基づいてデータがローカルにない場合にのみ、データの送信を要求する必要があります。)

これは、CRC を使用してファイルの変更をチェックすることと、CRC をダイジェストとして使用してファイル間の重複を検出することの違いに似ています。後者の使用についての議論は見たことがありません。

私は改ざんの問題には関心がありません。つまり、暗号強度ハッシュは必要ありません。

私は現在、シリアル化されたデータの単純な 32 ビット CRC を使用しており、これまでのところうまく機能しています。ただし、この状況で衝突の可能性を最小限に抑えるために、どの 32 ビット CRC アルゴリズム (つまり、どの多項式) が最適かを誰かが推奨できるかどうか知りたいですか?

私が持っている他の質問は、もう少し微妙です。現在の実装では、データ セットの構造を無視し、事実上、データを表すシリアル化された文字列を CRC するだけです。しかし、さまざまな理由から、CRC 方法論を次のように変更したいと考えています。最上位のデータ セットが、いくつかの生データといくつかの従属データ セットのコレクションであるとします。私の現在のスキームは、本質的に生データとすべての従属データセットを連結し、CRC の結果です。ただし、ほとんどの場合、従属データ セットの CRC を既に持っているため、生データを従属データ セットのCRCと連結してトップレベル データ セットの UID を作成し、次に CRC を作成します。この構築。質問は、

自分の考えを議論できる言語で表現するために、ちょっとした表記法を定義します。最上位データ セットTを呼び出し、生データ セットRと従属データ セットで構成されているとしますSi, i=1..n。のように書けますT = (R, S1, S2, ..., Sn)。データセットの連結を表す場合&、私の元のスキームは次のように考えることができます。

UID_1(T) = CRC(R & S1 & S2 & ... & Sn)

そして、私の新しいスキームは次のように考えることができます

UID_2(T) = CRC(R & CRC(S1) & CRC(S2) & ... & CRC(Sn))

次に、私の質問は次のとおりです。(1)TとT'が非常に異なる場合、どの CRC アルゴリズムが最小化するprob( UID_1(T)=UID_1(T') )か、およびどの CRC アルゴリズムが最小化するprob( UID_2(T)=UID_2(T') )か、これら 2 つの確率はどのように比較されますか?

この問題に関する私の（素朴で情報に通じていない）考えは次のとおりです。Tとの違いがT'1 つの下位データ セットにあるとします。WLOG はS1!=S1'. もしそれが起こればCRC(S1)=CRC(S1')、明らかに私たちは を持つでしょうUID_2(T)=UID_2(T')。一方、 の場合CRC(S1)!=CRC(S1')、 と の差は 4 バイトのみの小さな差R & CRC(S1) & CRC(S2) & ... & CRC(Sn)でR & CRC(S1') & CRC(S2) & ... & CRC(Sn)あるため、差を検出する UID_2 の能力は、伝送エラーを検出する CRC の能力と実質的に同じです。広く分離されていないいくつかのビット。これは CRC が行うように設計されているため、使用している CRC が送信エラーの検出に優れている限り、UID_2 はかなり安全だと思います。私たちの表記法で言えば、

prob( UID_2(T)=UID_2(T') ) = prob(CRC(S1)=CRC(S1')) + (1-prob(CRC(S1)=CRC(S1'))) * probability of CRC not detecting error a few bits.

CRC が数ビットのエラーを検出Pしない確率と、大きなサイズのデータ​​セットで大きな違いを検出しない確率を呼び出しますQ。上記はおおよそ次のように書くことができます。

prob( UID_2(T)=UID_2(T') ) ~ Q + (1-Q)*P

ここで、次のように UID をもう少し変更します。「基本的な」データ、つまりT=(R)R が double、integer、char、bool などであるデータセットの場合は、 を定義しますUID_3(T)=(R)。次に、T下位データ セット のベクトルで構成されるデータ セットT = (S1, S2, ..., Sn)について、定義します。

UID_3(T) = CRC(ID_3(S1) & ID_3(S2) & ... & ID_3(Sn))

T特定のデータセットに下位レベルのネストされた下位データセットがあると仮定すると、m漠然とした意味で、

prob( UID_3(T)=UID_3(T') ) ~ 1 - (1-Q)(1-P)^m

いずれにせよ、これらの確率が小さいとすれば、これは次のように概算できます。

 1 - (1-Q)(1-P)^m = Q + (1-Q)*P*m + (1-Q)*P*P*m*(m-1)/2 + ... ~ Q + m*P

したがって、最大ネスト レベルがわかっている場合m、およびさまざまな CRC についてわかっPてQいる場合、必要なのは、 の最小値を与える CRC を選択することですQ + m*P。私がそうかもしれないと思うなら、P~Q上記はこれに単純化されます。UID_1 のエラー確率は ですP。UID_3 のエラー確率は です(m+1)P。ここmで、 は最大ネスト (再帰) レベルです。

これはすべて合理的に思えますか？

Answer 1

データセットの再送信を回避できるメカニズムが必要です。

rsyncは、一般的に概説したアプローチを使用して、この問題をすでに解決しています。

ただし、この状況で衝突の可能性を最小限に抑えるために、どの 32 ビット CRC アルゴリズム (つまり、どの多項式) が最適かを誰かが推奨できるかどうか知りたいですか?

適切に選択された CRC 多項式の間で大きな違いは見られません。速度の方が重要な場合があります。その場合、crc32最新の Intel プロセッサの命令など、ハードウェア CRC を使用することをお勧めします。それはCRC-32C (Castagnoli) 多項式を使用します。同じループ内の 3 つのバッファーで CRC を計算し、それらを結合することにより、1 つのコアで 3 つの演算ユニットをすべて並列に使用することで、これを非常に高速化できます。CRC を結合する方法については、以下を参照してください。

ただし、ほとんどの場合、従属データ セットの CRC を既に持っているため、生データを従属データ セットの CRC と連結してトップレベル データ セットの UID を構築し、この構築を CRC します。 .

または、全体に対して CRC を実行したかのように、セット全体の CRC をすばやく計算できますが、既に計算された断片の CRC を使用します。zlibcrc32_combine()を見てください。これは、多数の CRC の CRC を取得するよりも優れています。組み合わせることで、CRC アルゴリズムの数学的な長所をすべて保持できます。

Answer 2

マーク・アドラーの答えは見事でした。プログラマーの帽子を脱いで数学者の帽子をかぶっていたら、そのうちのいくつかは明らかだったはずです。彼は数学を説明する時間がなかったので、興味のある人のためにここに書きます。

CRC を計算するプロセスは、本質的に多項式除算を行うプロセスです。多項式は 2 を法とする係数を持ちます。つまり、各項の係数は 0 または 1 です。したがって、次数 N の多項式は、各ビットが項の係数である N ビット数で表すことができます (そして、多項式除算は、一連の XOR 操作とシフト操作を実行することになります)。データ ブロックを CRC する場合、「データ」を 1 つの大きな多項式、つまり長いビット列と見なします。各ビットは多項式の項の係数を表します。データ ブロック多項式を A と呼びます。各 CRC の「バージョン」に対して、CRC の多項式を P と呼びます。32 ビット CRC の場合、P は次数 32 の多項式であるため、33 項と 33 係数を持ちます。一番上の係数は常に 1 であるため、暗黙的であり、32 ビット整数で 32 次多項式を表すことができます。(計算上、これは実際には非常に便利です。) データ ブロック A の CRC を計算するプロセスは、A を P で割ったときの余りを求めるプロセスです。つまり、A は常に記述できます。

A = Q * P + R

ここで、R は次数 P よりも小さい次数の多項式です。つまり、R の次数は 31 以下であるため、32 ビットの整数で表すことができます。R は本質的に CRC です。(小さな注意: 通常、A の前に 0xFFFFFFFF を追加しますが、ここでは重要ではありません。) ここで、2 つのデータ ブロック A と B を連結すると、2 つのブロックの連結に対応する「多項式」は、「シフトされた A の多項式」になります。言い換えると、A&B の多項式は A*S+B です。ここで、S は 1 の後に N 個のゼロが続くことに対応する多項式であり、N はその数です。 B のビット (つまり、 S = x**N )。では、A&B の CRC について何が言えるでしょうか。A=Q*P+R および B=Q'*P+R' がわかっているとします。つまり、R は A の CRC であり、R' は B の CRC です。S=q*P+r もわかっているとします。それで

A * S + B = (Q*P+R)*(q*P+r) + (Q'*P+R')
          = Q*(q*P+r)*P + R*q*P + R*r + Q'*P + R'
          = (Q*S + R*q + Q') * P    + R*r + R'

したがって、A*S+B を P で割ったときの余りを見つけるには、R*r+R' を P で割ったときの余りを見つけるだけで済みます。したがって、2 つのデータ ストリーム A と B の連結の CRC を計算するには、 、データ ストリームの個別の CRC、つまり R と R'、および末尾のデータ ストリーム B の長さ N (したがって、r を計算できる) だけを知る必要があります。これは、マークの他のコメントの 1 つの内容でもあります。後続のデータ ストリーム B の長さがいくつかの値に制限されている場合、これらの長さごとに r を事前に計算して、2 つの CRC の組み合わせを非常に簡単にすることができます。(任意の長さ N の場合、r の計算は自明ではありませんが、B 全体で割り算をやり直すよりもはるかに高速 (log_2 N) です。)

注: 上記は CRC の正確な説明ではありません。進行中のいくつかのシフトがあります。正確には、L が 0xFFFFFFFF で表される多項式、つまり L=x* 31+x *30+...+x+1 で、S_n が「n ビット左シフト」多項式、つまり S_n = x* の場合*n、N ビットの多項式 A を持つデータ ブロックの CRC は、(L * S_N + A) * S_32 を P で割ったときの剰余、つまり、(L&A)*S_32 を P で割ったときの余りです。ここで、& は次のとおりです。 「連結」演算子。

また、Marks のコメントの 1 つに同意できないと思いますが、間違っていれば訂正してくれます。R と R' が既にわかっている場合、上記の方法論を使用して A&B の CRC を計算する時間を比較すると、単純な方法で計算する場合と比較して、len(A) と len(B) の比率に依存しません。 「単純な」方法で計算します。連結されたデータセット全体で CRC を再計算する必要はありません。上記の表記法を使用すると、R*S+B の CRC を計算するだけで済みます。つまり、B の前に 0xFFFFFFFF を追加してその CRC を計算する代わりに、B の前に R を追加してその CRC を計算します。したがって、B の CRC を再度計算する時間と、r を計算する時間の比較です (その後、R*r+R' を P で割りますが、これは些細で時間的に重要ではありません)。

Answer 3

Mark Adler の回答は技術的な質問に対応しているため、ここでは説明しません。ここでは、OP の質問で提案された同期アルゴリズムの潜在的な大きな欠陥を指摘し、小さな改善を提案します。

チェックサムとハッシュは、一部のデータに対して単一の署名値を提供します。ただし、長さが有限であるため、データが長い場合、チェックサム/ハッシュの可能な一意の値の数は、生データの可能な組み合わせよりも常に少なくなります。たとえば、4 バイトの CRC は 4 294 967 296 の一意の値しか取ることができませんが、データである可能性のある 5 バイトの値でさえ、8 倍の値を取ることができます。これは、チェックサム自体よりも長いデータの場合、まったく同じ署名を持つ 1 つ以上のバイトの組み合わせが常に存在することを意味します。

完全性をチェックするために使用する場合、わずかに異なるデータ ストリームが同じ署名になる可能性は小さいため、署名が同じであればデータも同じであると想定できます。いくつかのデータから始めて、チェックサム関数を使用して計算さdれたチェックサム が であることを確認することに注意することが重要です。cff(d) == c

ただし、OP のアルゴリズムでは、使用方法が異なると、微妙で有害な信頼性の低下が生じます。OP のアルゴリズムでは、サーバー A は生データから開始し[d1A,d2A,d3A,d4A]、一連のチェックサムを生成します[c1,c2,c3,c4](dnAはサーバー A の n 番目のデータ項目です)。次に、サーバー B はこのチェックサムのリストを受け取り、独自のチェックサムのリストをチェックして、欠落があるかどうかを判断します。サーバー B にリストがあるとします[c1,c2,c3,c5]。その後、サーバー A から要求がd4行われ、理想的なケースでは同期が適切に機能するはずです。

衝突の可能性と、衝突を生成するのに必ずしもそれほど多くのデータが必要ではないこと (例: CRC("plumless") == CRC("buckeroo")) を思い出すと、私たちのスキームが提供する最善の保証は、サーバー B には絶対にないということであることがすぐにわかりますd4A。あることは保証できません[d1A,d2A,d3A]。これは、 と が異なる可能性があり、f(d1A) = c1両方のサーバーに両方を持たせたいためです。このスキームでは、どちらのサーバーも両方の存在を知ることはできません。f(d1B) = c1d1Ad1Bd1Ad1B. 衝突に強いチェックサムとハッシュをますます使用できますが、このスキームでは完全な同期を保証できません。これは、ネットワークが追跡しなければならないファイルの数が増えるほど、より重要になります。衝突が見つかっていない SHA1 のような暗号化ハッシュを使用することをお勧めします。

このリスクを軽減するために考えられるのは、冗長なハッシュを導入することです。1 つの方法は、完全に異なるアルゴリズムを使用することです。これは可能ですが、同時にcrc32(d1) == crc32(d2)そうなる可能性は低いためです。adler32(d1) == adler32(d2)ただし、この論文では、この方法ではそれほど多くは得られないことを示唆しています。crc32('a' & d1) == crc32('a' & d2)OP 表記を使用すると、と が同時に真になる可能性も低くcrc32('b' & d1) == crc32('b' & d2)なるため、衝突が起こりにくい組み合わせに「ソルト」することができます。ただし、実際にはパフォーマンスに大きな影響を与えないSHA512のような衝突耐性のあるハッシュ関数を使用するだけでもよいと思います。