Skip to content

Commit e277e89

Browse files
sevkett12sevkett12
authored
[Zellic Audit] fix fq6_hinted_mul_keep_elements (#339)
* fix fq6_hinted_mul_keep_elements * removed unused import * fmt
1 parent 0b398a4 commit e277e89

1 file changed

Lines changed: 249 additions & 32 deletions

File tree

‎bitvm/src/bn254/fq6.rs‎

Lines changed: 249 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11
use crate::bn254::fp254impl::Fp254Impl;
22
use crate::bn254::fq::Fq;
3-
use crate::bn254::fq12::Fq12;
43
use crate::bn254::fq2::Fq2;
54
use crate::bn254::utils::Hint;
65
use crate::treepp::{script, Script};
@@ -218,37 +217,10 @@ impl Fq6 {
218217
// Input: [A, B]
219218
// Output: [C] where C = A x B
220219
pub fn hinted_mul(
221-
a_depth: u32,
222-
a: ark_bn254::Fq6,
223-
b_depth: u32,
224-
b: ark_bn254::Fq6,
225-
) -> (Script, Vec<Hint>) {
226-
Self::hinted_mul_core(a_depth, a, b_depth, b, script! {})
227-
}
228-
229-
// Input: [A, B]
230-
// Output: [A, B, C] where C = A x B
231-
pub fn hinted_mul_keep_elements(
232-
a_depth: u32,
233-
a: ark_bn254::Fq6,
234-
b_depth: u32,
235-
b: ark_bn254::Fq6,
236-
) -> (Script, Vec<Hint>) {
237-
let preserve_scr = script! {
238-
{Fq6::toaltstack()}
239-
{Fq12::copy(0)}
240-
{Fq6::fromaltstack()}
241-
};
242-
243-
Self::hinted_mul_core(a_depth, a, b_depth, b, preserve_scr)
244-
}
245-
246-
fn hinted_mul_core(
247220
mut a_depth: u32,
248221
mut a: ark_bn254::Fq6,
249222
mut b_depth: u32,
250223
mut b: ark_bn254::Fq6,
251-
keep_elements_scr: Script,
252224
) -> (Script, Vec<Hint>) {
253225
// The degree-6 extension on BN254 Fq2 is under the polynomial y^3 - x - 9
254226
// Toom-Cook-3 from https://eprint.iacr.org/2006/471.pdf
@@ -306,8 +278,6 @@ impl Fq6 {
306278
// compute (a-b+c)(d-e+f) = P(-1)
307279
{ hinted_script3 }
308280

309-
{ keep_elements_scr }
310-
311281
// compute 2b
312282
{ Fq2::roll(a_depth + 8) }
313283
{ Fq2::double(0) }
@@ -422,6 +392,184 @@ impl Fq6 {
422392
(script, hints)
423393
}
424394

395+
// Input: [A, B]
396+
// Output: [A, B, C] where C = A x B
397+
pub fn hinted_mul_keep_elements(
398+
mut a_depth: u32,
399+
mut a: ark_bn254::Fq6,
400+
mut b_depth: u32,
401+
mut b: ark_bn254::Fq6,
402+
) -> (Script, Vec<Hint>) {
403+
// The degree-6 extension on BN254 Fq2 is under the polynomial y^3 - x - 9
404+
// Toom-Cook-3 from https://eprint.iacr.org/2006/471.pdf
405+
if a_depth < b_depth {
406+
(a_depth, b_depth) = (b_depth, a_depth);
407+
(a, b) = (b, a);
408+
}
409+
assert_ne!(a_depth, b_depth);
410+
let mut hints = Vec::new();
411+
412+
let (hinted_script1, hint1) = Fq2::hinted_mul(2, a.c0, 0, b.c0);
413+
let (hinted_script2, hint2) = Fq2::hinted_mul(6, a.c0 + a.c1 + a.c2, 2, b.c0 + b.c1 + b.c2);
414+
let (hinted_script3, hint3) = Fq2::hinted_mul(4, a.c0 - a.c1 + a.c2, 2, b.c0 - b.c1 + b.c2);
415+
let (hinted_script4, hint4) = Fq2::hinted_mul(
416+
2,
417+
a.c0 + a.c1 + a.c1 + a.c2 + a.c2 + a.c2 + a.c2,
418+
0,
419+
b.c0 + b.c1 + b.c1 + b.c2 + b.c2 + b.c2 + b.c2,
420+
);
421+
let (hinted_script5, hint5) = Fq2::hinted_mul(2, a.c2, 0, b.c2);
422+
423+
let script = script! {
424+
// compute ad = P(0)
425+
{ Fq2::copy(a_depth + 4) }
426+
{ Fq2::copy(b_depth + 6) }
427+
{ hinted_script1 }
428+
429+
// compute a+c
430+
{ Fq2::copy(a_depth + 6) }
431+
{ Fq2::copy(a_depth + 4) }
432+
{ Fq2::add(2, 0) }
433+
434+
// compute a+b+c, a-b+c
435+
{ Fq2::copy(0) }
436+
{ Fq2::copy(a_depth + 8) }
437+
{ Fq2::copy(0) }
438+
{ Fq2::add(4, 0) }
439+
{ Fq2::sub(4, 2) }
440+
441+
// compute d+f
442+
{ Fq2::copy(b_depth + 10) }
443+
{ Fq2::copy(b_depth + 8) }
444+
{ Fq2::add(2, 0) }
445+
446+
// compute d+e+f, d-e+f
447+
{ Fq2::copy(0) }
448+
{ Fq2::copy(b_depth + 12) }
449+
{ Fq2::copy(0) }
450+
{ Fq2::add(4, 0) }
451+
{ Fq2::sub(4, 2) }
452+
453+
// compute (a+b+c)(d+e+f) = P(1)
454+
{ hinted_script2 }
455+
456+
// compute (a-b+c)(d-e+f) = P(-1)
457+
{ hinted_script3 }
458+
459+
// compute 2b
460+
{ Fq2::copy(a_depth + 8) }
461+
{ Fq2::double(0) }
462+
463+
// compute 4c
464+
{ Fq2::copy(a_depth + 8) }
465+
{ Fq2::double(0) }
466+
{ Fq2::double(0) }
467+
// compute a+2b+4c
468+
{ Fq2::add(2, 0) }
469+
{ Fq2::copy(a_depth + 12) }
470+
{ Fq2::add(2, 0) }
471+
472+
// compute 2e
473+
{ Fq2::copy(b_depth + 10) }
474+
{ Fq2::double(0) }
475+
476+
// compute 4f
477+
{ Fq2::copy(b_depth + 10) }
478+
{ Fq2::double(0) }
479+
{ Fq2::double(0) }
480+
481+
// compute d+2e+4f
482+
{ Fq2::add(2, 0) }
483+
{ Fq2::copy(b_depth + 14) }
484+
{ Fq2::add(2, 0) }
485+
486+
// compute (a+2b+4c)(d+2e+4f) = P(2)
487+
{ hinted_script4 }
488+
489+
// compute cf = P(inf)
490+
{ Fq2::copy(a_depth + 8) }
491+
{ Fq2::copy(b_depth + 10) }
492+
{ hinted_script5 }
493+
494+
// // at this point, we have v_0, v_1, v_2, v_3, v_4
495+
496+
// compute 3v_0
497+
{ Fq2::triple(8) }
498+
499+
// compute 3v_1
500+
{ Fq2::triple(8) }
501+
502+
// compute 6v_4
503+
{ Fq2::triple(4) }
504+
{ Fq2::double(0) }
505+
506+
// compute x = 3v_0 - 3v_1 - v_2 + v_3 - 12v_4
507+
{ Fq2::copy(4) }
508+
{ Fq2::copy(4) }
509+
{ Fq2::sub(2, 0) }
510+
{ Fq2::copy(10) }
511+
{ Fq2::sub(2, 0) }
512+
{ Fq2::copy(8) }
513+
{ Fq2::add(2, 0) }
514+
{ Fq2::copy(2) }
515+
{ Fq2::double(0) }
516+
{ Fq2::sub(2, 0) }
517+
518+
// compute c_0 = 6v_0 + \beta x
519+
{ Fq6::mul_fq2_by_nonresidue() }
520+
{ Fq2::copy(6) }
521+
{ Fq2::double(0) }
522+
{ Fq2::add(2, 0) }
523+
524+
// compute y = -3v_0 + 6v_1 - 2v_2 - v_3 + 12v_4
525+
{ Fq2::copy(4) }
526+
{ Fq2::double(0) }
527+
{ Fq2::copy(8) }
528+
{ Fq2::sub(2, 0) }
529+
{ Fq2::copy(12) }
530+
{ Fq2::double(0) }
531+
{ Fq2::sub(2, 0) }
532+
{ Fq2::roll(10) }
533+
{ Fq2::sub(2, 0) }
534+
{ Fq2::copy(4) }
535+
{ Fq2::double(0) }
536+
{ Fq2::add(2, 0) }
537+
538+
// compute c_1 = y + \beta 6v_4
539+
{ Fq2::copy(4) }
540+
{ Fq6::mul_fq2_by_nonresidue() }
541+
{ Fq2::add(2, 0) }
542+
543+
// compute c_2 = 3v_1 - 6v_0 + 3v_2 - 6v_4
544+
{ Fq2::roll(6) }
545+
{ Fq2::roll(8) }
546+
{ Fq2::double(0) }
547+
{ Fq2::sub(2, 0) }
548+
{ Fq2::roll(8) }
549+
{ Fq2::triple(0) }
550+
{ Fq2::add(2, 0) }
551+
{ Fq2::sub(0, 6) }
552+
553+
// divide by 6
554+
{ Fq2::roll(4) }
555+
{ Fq2::div2() }
556+
{ Fq2::div3() }
557+
{ Fq2::roll(4) }
558+
{ Fq2::div2() }
559+
{ Fq2::div3() }
560+
{ Fq2::roll(4) }
561+
{ Fq2::div2() }
562+
{ Fq2::div3() }
563+
};
564+
hints.extend(hint1);
565+
hints.extend(hint2);
566+
hints.extend(hint3);
567+
hints.extend(hint4);
568+
hints.extend(hint5);
569+
570+
(script, hints)
571+
}
572+
425573
// input:
426574
// p.c0 (2 elements)
427575
// p.c1 (2 elements)
@@ -669,13 +817,15 @@ mod test {
669817
fn test_bn254_fq6_hinted_mul() {
670818
let mut prng: ChaCha20Rng = ChaCha20Rng::seed_from_u64(0);
671819

672-
for _ in 0..100 {
820+
for i in 0..100 {
673821
let a = ark_bn254::Fq6::rand(&mut prng);
674822
let b = ark_bn254::Fq6::rand(&mut prng);
675823
let c = a.mul(&b);
676824

677825
let (hinted_mul, hints) = Fq6::hinted_mul(6, a, 0, b);
678-
println!("Fq6::hinted_mul: {} bytes", hinted_mul.len());
826+
if i == 0 {
827+
println!("Fq6::hinted_mul: {} bytes", hinted_mul.len());
828+
}
679829

680830
let script = script! {
681831
for hint in hints {
@@ -692,6 +842,73 @@ mod test {
692842
}
693843
}
694844

845+
#[test]
846+
fn test_bn254_fq6_hinted_mul_keep_elements() {
847+
let mut prng: ChaCha20Rng = ChaCha20Rng::seed_from_u64(0);
848+
849+
for i in 0..100 {
850+
let a = ark_bn254::Fq6::rand(&mut prng);
851+
let b = ark_bn254::Fq6::rand(&mut prng);
852+
let c = ark_bn254::Fq6::rand(&mut prng);
853+
let d = a.mul(&b);
854+
let e = b.mul(&c);
855+
856+
let (hinted_mul, hints) = Fq6::hinted_mul_keep_elements(12, a, 6, b);
857+
if i == 0 {
858+
println!("Fq6::hinted_mul(12,6): {} bytes", hinted_mul.len());
859+
}
860+
861+
let script = script! {
862+
for hint in hints {
863+
{ hint.push() }
864+
}
865+
{ Fq6::push(a) }
866+
{ Fq6::push(b) }
867+
{ Fq6::push(c) }
868+
{ hinted_mul.clone() }
869+
{ Fq6::push(d) }
870+
{ Fq6::equalverify() }
871+
872+
{ Fq6::push(c) }
873+
{ Fq6::equalverify() }
874+
{ Fq6::push(b) }
875+
{ Fq6::equalverify() }
876+
{ Fq6::push(a) }
877+
{ Fq6::equalverify() }
878+
879+
OP_TRUE
880+
};
881+
run(script);
882+
883+
let (hinted_mul, hints) = Fq6::hinted_mul_keep_elements(6, b, 0, c);
884+
if i == 0 {
885+
println!("Fq6::hinted_mul(12,6): {} bytes", hinted_mul.len());
886+
}
887+
888+
let script = script! {
889+
for hint in hints {
890+
{ hint.push() }
891+
}
892+
{ Fq6::push(a) }
893+
{ Fq6::push(b) }
894+
{ Fq6::push(c) }
895+
{ hinted_mul.clone() }
896+
{ Fq6::push(e) }
897+
{ Fq6::equalverify() }
898+
899+
{ Fq6::push(c) }
900+
{ Fq6::equalverify() }
901+
{ Fq6::push(b) }
902+
{ Fq6::equalverify() }
903+
{ Fq6::push(a) }
904+
{ Fq6::equalverify() }
905+
906+
OP_TRUE
907+
};
908+
run(script);
909+
}
910+
}
911+
695912
#[test]
696913
fn test_bn254_fq6_hinted_mul_by_01() {
697914
let mut prng: ChaCha20Rng = ChaCha20Rng::seed_from_u64(0);

0 commit comments

Comments
 (0)