DIZK是在Spark框架上,用java語言實現的分散式零知識證明系統。原始碼的結構如下:
algebra - 各種計算:橢圓曲線,域/群,FFT以及多倍點(fixedMSM和VarMSM)。
bace - batch證明的相關實現。
relations - 電路的表示:r1cs以及QAP。
reductions - 實現r1cs到QAP的轉化。
zk_proof_systems - Groth26證明系統
profiler - 效能測試邏輯
熟悉libsnark的小夥伴,對這些術語應該感到比較親切。
2. DistributedSetup
DistributedSetup實現了分散式的Setup邏輯:
main/java/zk_proof_systems/zkSNARK/DistributedSetup.java
generate函式實現了Pk/Vk的生成。
public static <FieldT extends AbstractFieldElementExpanded<FieldT>,
G1T extends AbstractG1<G1T>,
G2T extends AbstractG2<G2T>,
GTT extends AbstractGT<GTT>,
PairingT extends AbstractPairing<G1T, G2T, GTT>>
CRS<FieldT, G1T, G2T, GTT> generate(
final R1CSRelationRDD<FieldT> r1cs,
final FieldT fieldFactory,
final G1T g1Factory,
final G2T g2Factory,
final PairingT pairing,
final Configuration config) {
2.1 QAP轉化
final QAPRelationRDD<FieldT> qap = R1CStoQAPRDD.R1CStoQAPRelation(r1cs, t, config);
注意,QAP用QAPRelationRDD類表示。
2.2 計算deltaABC/gammaABC
final JavaPairRDD<Long, FieldT> betaAt = qap.At().mapValues(a -> a.mul(beta));
final JavaPairRDD<Long, FieldT> alphaBt = qap.Bt().mapValues(b -> b.mul(alpha));
final JavaPairRDD<Long, FieldT> ABC = betaAt.union(alphaBt).union(qap.Ct())
.reduceByKey(FieldT::add).persist(config.storageLevel());
final JavaPairRDD<Long, FieldT> gammaABC = ABC.filter(e -> e._1 < numInputs)
.mapValues(e -> e.mul(inverseGamma));
final JavaPairRDD<Long, FieldT> deltaABC = ABC.filter(e -> e._1 >= numInputs)
.mapValues(e -> e.mul(inverseDelta));
2.3 計算At/Bt的密集度
final long numNonZeroAt = qap.At().filter(e -> !e._2.isZero()).count();
final long numNonZeroBt = qap.Bt().filter(e -> !e._2.isZero()).count();
2.4 計算FixedMSM(G1/G2)
final G1T generatorG1 = g1Factory.random(config.seed(), config.secureSeed());
final int scalarSizeG1 = generatorG1.bitSize();
final long scalarCountG1 = numNonZeroAt + numNonZeroBt + numVariables;
final int windowSizeG1 = FixedBaseMSM.getWindowSize(scalarCountG1 / numPartitions, generatorG1);
final List<List<G1T>> windowTableG1 = FixedBaseMSM
.getWindowTable(generatorG1, scalarSizeG1, windowSizeG1);
以上是G1的MSM的計算(G2類似),注意windowSizeG1,是所有的“非零”係數的個數除以Partition的個數。
2.5 生成CRS(Pk/Vk)
final ProvingKeyRDD<FieldT, G1T, G2T> provingKey = new ProvingKeyRDD<>(
alphaG1,
betaG1,
betaG2,
deltaG1,
deltaG2,
deltaABCG1,
queryA,
queryB,
queryH,
r1cs);
final VerificationKey<G1T, G2T, GTT> verificationKey = new VerificationKey<>(
alphaG1betaG2,
gammaG2,
deltaG2,
UVWGammaG1);
注意:Pk使用RDD(ProvingKeyRDD)表示。
3. DistributedProver
DistributedProver實現了分散式的Prover邏輯:
main/java/zk_proof_systems/zkSNARK/DistributedProver.java
prove函式實現了證明生成邏輯。
public static <FieldT extends AbstractFieldElementExpanded<FieldT>, G1T extends
AbstractG1<G1T>, G2T extends AbstractG2<G2T>>
Proof<G1T, G2T> prove(
3.1 生成witness
final QAPWitnessRDD<FieldT> qapWitness = R1CStoQAPRDD .R1CStoQAPWitness(provingKey.r1cs(), primary, oneFullAssignment, fieldFactory, config);
QAPWitnessRDD定義在main/java/relations/qap/QAPWitnessRDD.java,包括輸入資訊以及H多項式係數(FFT計算獲得)。
3.2 產生隨機數
final FieldT r = fieldFactory.random(config.seed(), config.secureSeed());
final FieldT s = fieldFactory.random(config.seed(), config.secureSeed());
3.3 計算Evaluation
final JavaRDD<Tuple2<FieldT, G1T>> computationA = > .join(provingKey.queryA(), numPartitions).values();
final G1T evaluationAt = VariableBaseMSM.distributedMSM(computationA);
透過VariableBaseMSM計算A/B/deltaABC以及H的Evaluation。
3.4 生成證明
// A = alpha + sum_i(a_i*A_i(t)) + r*delta
final G1T A = alphaG1.add(evaluationAt).add(deltaG1.mul(r));
// B = beta + sum_i(a_i*B_i(t)) + s*delta
final Tuple2<G1T, G2T> B = new Tuple2<>(
betaG1.add(evaluationBt._1).add(deltaG1.mul(s)),
betaG2.add(evaluationBt._2).add(deltaG2.mul(s)));
// C = sum_i(a_i*((beta*A_i(t) + alpha*B_i(t) + C_i(t)) + H(t)*Z(t))/delta) + A*s + r*b - r*s*delta
final G1T C = evaluationABC.add(A.mul(s)).add(B._1.mul(r)).sub(rsDelta);
4. Profiling
main/java/profiler/Profiler.java是效能測試的入口類,提供了各種運算元的效能測試能力,包括分散式和單機版本。在scripts目錄下也提供了Spark執行的指令碼。預設,DIZK是使用Amazon的EC2機器進行測試的。
./spark-ec2/copy-dir /home/ec2-user/
export JAVA_HOME="/usr/lib/jvm/java-1.8.0"
for TOTAL_CORES in 8; do
for SIZE in `seq 15 25`; do
export APP=dizk-large
export MEMORY=16G
export MULTIPLIER=2
export CORES=1
export NUM_EXECUTORS=$((TOTAL_CORES / CORES))
export NUM_PARTITIONS=$((TOTAL_CORES * MULTIPLIER))
/root/spark/bin/spark-submit \
--conf spark.driver.memory=$MEMORY \
...
--class "profiler.Profiler" \
/home/ec2-user/dizk-1.0.jar $NUM_EXECUTORS $CORES $MEMORY $APP $SIZE $NUM_PARTITIONS
done
done
感興趣的小夥伴,可以自己改一下指令碼,在本地環境執行DIZK。
總結:
DIZK,是在Spark大資料計算框架下的分散式零知識證明系統。DIZK的程式碼比較清晰,註釋也比較完整。DistributedSetup和DistributedProver是Setup和Prover的實現。DIZK提供了完整的Profiling的程式碼。