/
ModGadget.java
69 lines (55 loc) · 1.81 KB
/
ModGadget.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*******************************************************************************
* Author: Ahmed Kosba <akosba@cs.umd.edu>
*******************************************************************************/
package examples.gadgets;
import java.math.BigInteger;
import circuit.eval.CircuitEvaluator;
import circuit.eval.Instruction;
import circuit.operations.Gadget;
import circuit.structure.Wire;
/**
* This gadget provides the remainder of a % b.
* Use within appropriate ranges so that the prover cannot cheat via overflows.
*
*
*/
public class ModGadget extends Gadget {
private Wire a;
private Wire b;
private Wire r;
private Wire q;
private int bitwidth; // bitwidth for both a, b
public ModGadget(Wire a, Wire b, int bitwidth, String...desc) {
super(desc);
this.a = a;
this.b = b;
this.bitwidth = bitwidth;
if(bitwidth > 126){
throw new IllegalArgumentException("Bitwidth not supported yet.");
}
buildCircuit();
}
private void buildCircuit() {
r = generator.createProverWitnessWire("mod result");
q = generator.createProverWitnessWire("division result");
generator.specifyProverWitnessComputation(new Instruction() {
@Override
public void evaluate(CircuitEvaluator evaluator) {
BigInteger aValue = evaluator.getWireValue(a);
BigInteger bValue = evaluator.getWireValue(b);
BigInteger rValue = aValue.mod(bValue);
evaluator.setWireValue(r, rValue);
BigInteger qValue = aValue.divide(bValue);
evaluator.setWireValue(q, qValue);
}
});
r.restrictBitLength(bitwidth);
q.restrictBitLength(bitwidth);
generator.addOneAssertion(r.isLessThan(b, bitwidth));
generator.addEqualityAssertion(q.mul(b).add(r), a);
}
@Override
public Wire[] getOutputWires() {
return new Wire[] { r };
}
}