ENCODING DATA UTILIZING A ZERO INFORMATION GAIN FUNCTION

• US 20140201567A1
• Filed: 03/18/2014
• Published: 07/17/2014
• Est. Priority Date: 10/04/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W.
• Granted Patent: US 10,216,576 B2
• Time in Patent Office: Days
• US Class Current: 714/6.24
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H03M 11/08 by operating selected combinations of multifunction keys
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method begins by a dispersed storage (DS) processing module encoding data using a dispersed storage error coding function to produce a set of encoded data slices. The method continues with the DS processing module encoding a first encoded data slice of the set of encoded data slices using a zero information gain (ZIG) function based on a second encoded data slice of the set of encoded data slices to produce a ZIG encoded data slice. The method continues with the DS processing module outputting the ZIG encoded data slice and a subset of encoded data slices of the set of encoded data slices, wherein the subset of encoded data slices includes less than a decode threshold number of encoded data slices and does not include the first or the second encoded data slice.

Claims

1. A method for execution by a processing module of a computing device, the method comprises:

encoding data in accordance with an encoding scheme to produce a subset of encoded data slices and recovery information regarding at least one encoded data slice, wherein the subset of encoded data slices is not sufficient to reproduce the data and wherein the subset of encoded data slices and the at least one encoded data slice are sufficient to reproduce the data;

sending the subset of encoded data slices to a first memory within a dispersed storage network (DSN) for storage therein; and

sending the recovery information to a second memory within the DSN for storage therein.

2. The method of claim 1, wherein the encoding scheme comprises one or more of:

a number of encoded data slices to encode indicator;

a number of zero information gain (ZIG) slices to encode indicator;

one or more encoded data slice identifiers (IDs);

one or more ZIG slice IDs;

a pillar width number;

a decode threshold number;

an encoding matrix;

a pillar index that identifies a ZIG slice association;

a pillar participant list;

an encryption key;

one or more shared secrets; and

one or more obfuscation values.

3. The method of claim 1, wherein the encoding the data comprises:

encoding the data using a dispersed storage error coding function to produce a set of encoded data slices;

generating a zero information gain (ZIG) encoded data slice as the recovery information for a first encoded data slice of the set of encoded data slices using a ZIG function and a second encoded data slice of the set of encoded data slices; and

selecting the subset of encoded data slices from the set of encoded data slices such that the subset of encoded data slices does not include the first and second encoded data slices.

4. The method of claim 1, wherein the sending the recovery information comprises:

prior to sending, obfuscating the recovery information using an obfuscating function.

5. The method of claim 4, wherein the obfuscating function comprises one of:

exclusive ORing the recovery information with an obfuscating value;

masking the recovery information;

encrypting the recovery information; and

performing a deterministic function on the recovery information.

6. The method of claim 1, wherein encoding the data comprises:

encoding the data using a dispersed storage error coding function to produce a set of encoded data slices;

generating a first zero information gain (ZIG) encoded data slice for a first encoded data slice of the set of encoded data slices using a ZIG function and a second encoded data slice of the set of encoded data slices;

generating a second ZIG encoded data slice for the first encoded data slice using the ZIG function and a third encoded data slice of the set of encoded data slices;

generating a third ZIG encoded data slice for a fourth encoded data slice of the set of encoded data slices using the ZIG function and the second encoded data slice;

generating a fourth ZIG encoded data slice for the fourth encoded data slice using the ZIG function and the third encoded data slice;

generating the recovery information by combining the first and second ZIG encoded data slices and combining the third and fourth ZIG encoded data slices; and

selecting the subset of encoded data slices from the set of encoded data slices such that the subset of encoded data slices does not include the first, second, third, or fourth encoded data slices.

7. A dispersed storage (DS) module comprises:

a first module, when operable within a computing device, causes the computing device to;

encode data in accordance with an encoding scheme to produce a subset of encoded data slices and recovery information regarding at least one encoded data slice, wherein the subset of encoded data slices is not sufficient to reproduce the data and wherein the subset of encoded data slices and the at least one encoded data slice are sufficient to reproduce the data;

a second module, when operable within the computing device, causes the computing device to;

send the subset of encoded data slices to a first memory within a dispersed storage network (DSN) for storage therein; and

send the recovery information to a second memory within the DSN for storage therein.

8. The DS module of claim 7, wherein the encoding scheme comprises one or more of:

a number of encoded data slices to encode indicator;

a number of zero information gain (ZIG) slices to encode indicator;

one or more encoded data slice identifiers (IDs);

one or more ZIG slice IDs;

a pillar width number;

a decode threshold number;

an encoding matrix;

a pillar index that identifies a ZIG slice association;

a pillar participant list;

an encryption key;

one or more shared secrets; and

one or more obfuscation values.

9. The DS module of claim 7, wherein the first module, when operable within the computing device, further causes the computing device to encode the data by:

encoding the data using a dispersed storage error coding function to produce a set of encoded data slices;

generating a zero information gain (ZIG) encoded data slice as the recovery information for a first encoded data slice of the set of encoded data slices using a ZIG function and a second encoded data slice of the set of encoded data slices; and

selecting the subset of encoded data slices from the set of encoded data slices such that the subset of encoded data slices does not include the first and second encoded data slices.

10. The DS module of claim 7, wherein the second module, when operable within the computing device, further causes the computing device to send the recovery information by:

prior to sending, obfuscating the recovery information using an obfuscating function.

11. The DS module of claim 10, wherein the obfuscating function comprises one of:

exclusive ORing the recovery information with an obfuscating value;

masking the recovery information;

encrypting the recovery information; and

performing a deterministic function on the recovery information.

12. The DS module of claim 7, wherein the first module, when operable within the computing device, further causes the computing device to encode the data by:

encoding the data using a dispersed storage error coding function to produce a set of encoded data slices;

generating a first zero information gain (ZIG) encoded data slice for a first encoded data slice of the set of encoded data slices using a ZIG function and a second encoded data slice of the set of encoded data slices;

generating a second ZIG encoded data slice for the first encoded data slice using the ZIG function and a third encoded data slice of the set of encoded data slices;

generating a third ZIG encoded data slice for a fourth encoded data slice of the set of encoded data slices using the ZIG function and the second encoded data slice;

generating a fourth ZIG encoded data slice for the fourth encoded data slice using the ZIG function and the third encoded data slice;

generating the recovery information by combining the first and second ZIG encoded data slices and combining the third and fourth ZIG encoded data slices; and

selecting the subset of encoded data slices from the set of encoded data slices such that the subset of encoded data slices does not include the first, second, third, or fourth encoded data slices.